T函数Walsh谱值与差分转移概率快速算法

doi:10.11959/j.issn.1000-436x.2015112

通信学报 ›› 2015, Vol. 36 ›› Issue (5): 167-173.doi: 10.11959/j.issn.1000-436x.2015112

T函数Walsh谱值与差分转移概率快速算法

刘燕,胡斌,徐立平

解放军信息工程大学密码工程学院，河南郑州 450001

出版日期:2015-05-20 发布日期:2015-07-17
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目

Efficient algorithm for computing Walsh spectrum and differential probability

IUYan L,UBin H,ULi-ping X

School of Cryptography Engineering,Information Engineering University,Zhengzhou 450001,China

Online:2015-05-20 Published:2015-07-17
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China

摘要/Abstract

摘要：

根据T函数自身输入与输出结构特点，结合T函数窄度相关定义，研究了T函数线性性质和差分性质。通过构造马尔可夫链和概率转移矩阵，给出了其Walsh谱值与差分转移概率计算的多项式时间快速算法，时间复杂度为O(n)，并将该算法应用于对TSC系列T函数的研究，得到任意输入输出线性组合的Walsh谱值表达式。

关键词: T函数, 窄度, Walsh谱值, 差分转移概率, 马尔可夫链

Abstract:

According to the characteristic of T-functions,along with the definition of narrow T-functions,the linear prop-erty and differential property were studied.Markov chain and transition matrices were constructed to propose fast algo-rithm for computing Walsh spectrum and differential probability,of which the time complexity is O(n).In addition,the algorithm is applied in the T-functions in TSC-family and finally the result expression is given.

Key words: T-function, narrowness, Walsh spectrum, differential probability, Markov chain

刘燕,胡斌,徐立平. T函数Walsh谱值与差分转移概率快速算法[J]. 通信学报, 2015, 36(5): 167-173.

IUYan L,UBin H,ULi-ping X. Efficient algorithm for computing Walsh spectrum and differential probability[J]. Journal on Communications, 2015, 36(5): 167-173.

图/表 1

参考文献 14

[1]	KLIMOV A , SHAMIR A . A new class of invertible mappings[A]. Workshop on Cryptographic Hardware and Embedded Systems (CHES)[C]. 2003. 470-483.
[2]	WIRT K . ASC-A stream cipher with built-in Mac functionality[J]. International Journal of Computer Science, 2007,2(2): 131.
[3]	HONG , J LEE D , YEOM Y , HAN D . A new class of single cycle T-functions[J]. Fast Software Encryption, Springer, 2005,3557: 68-82.
[4]	HONG J , LEE D , YEOM Y , HAN D , CHEE S . T-function based stream cipher TSC-3,2005[EB/OL]. .
[5]	MOON D , KWON D , HAN D , et al. T-function based stream cipher TSC-4,2005[EB/OL]. .
[6]	MAXIMOV A . A new stream cipher “Mir-1”[EB/OL]. , 2008.
[7]	DAUM M . Narrow T-function[J]. Fast Software Encryption, Springer, 2005,3557: 50-67.
[8]	ANASHIN V , KHRENNILOV A . Applied algebraic dynamics[J]. P-Adic Numbers,Ultrahcetric Analysis,and Application, 2010,2(4): 360-362.
[9]	ANASHIN V , KHRENNILOV A , YUROVA E . T-function revisited:new criteria for bijectivity/transitivity[J]. Designs,Codes and Cryptography, 2014,71(3): 383-407.
[10]	NYBERG K , WALLEN J . Improved linear distinguishers for SNOW2.0[J]. Fast Software Encryption, Springer, 2006,4047: 144-162.
[11]	常亚勤，金晨辉．环Z/2n上仿射函数Walsh谱的快速算法[J]．上海交通大学学报， 2011,45(3):321-326. CHANG Y Q , JIN C H . Fast computation of Walsh spectrum of affine function over the ring Z/2n[J]. Journal of shanghai Jiaotong University (Science), 2011,45(3):321-326.
[12]	方兆本，缪柏其．随机过程第2版[M]．北京：科学出版社， 2004. FANG Z B , MIN B Q . Stochastic Process(2nd Edition)[M]. Beijing: Science Press, 2004.
[13]	金晨辉，郑浩然，张少武等．密码学[M]．北京：高等教育出版社， 2009. JIN C H , ZHENG H R , ZHANG S W , et al. Cryptology(2nd Edition)[M]. Beijing: Higher Education Press, 2009.
[14]	LE G , FRAN?OIS . Powers of tensors and fast matrix multiplication[A]. Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014)[C]. 2014.

[1]	康海燕, 龙墨澜. 基于吸收马尔可夫链攻击图的网络攻击分析方法研究[J]. 通信学报, 2023, 44(2): 122-135.
[2]	佘维, 荣欣鹏, 刘炜, 田钊. 基于马尔可夫链的生成式区块链隐蔽通信模型[J]. 通信学报, 2022, 43(10): 121-132.
[3]	简鑫,韦一笑,刘钰芩,宋健,曾孝平,谭晓衡. 窄带物联网非连续接收机制功耗模型与优化[J]. 通信学报, 2019, 40(4): 107-116.
[4]	简鑫,刘钰芩,韦一笑,宋健,王芳,付澍,谭晓衡. 窄带物联网覆盖类别更新机制性能分析与优化[J]. 通信学报, 2018, 39(11): 70-79.
[5]	田贤忠,郭敏,何佳存,刘高,祝驿楠. 能量捕获协作中继网络多中继节点选择策略[J]. 通信学报, 2017, 38(Z2): 1-7.
[6]	李峰,司亚利,陈真,申利民. 基于马尔可夫链的轻量级机会路由转发策略[J]. 通信学报, 2017, 38(5): 108-120.
[7]	赵泉华,石雪,王玉,李玉. 可变类空间约束高斯混合模型遥感图像分割[J]. 通信学报, 2017, 38(2): 34-43.
[8]	李致远,陈汝龙,王汝传. 基于兴趣和行为预测的移动社交网络动态资源发现机制[J]. 通信学报, 2016, 37(4): 34-43.
[9]	周翰逊,郭薇,刘建,贾大宇. 基于马尔可夫链的网络蠕虫传播模型[J]. 通信学报, 2015, 36(5): 66-71.
[10]	陈曙晖，徐成成. 基于两级存储的正则表达式匹配技术[J]. 通信学报, 2014, 35(6): 7-55.
[11]	陈曙晖,徐成成. 基于两级存储的正则表达式匹配技术[J]. 通信学报, 2014, 35(6): 47-55.
[12]	屈毓锛,陈晨,董超,王海. 基于Markov状态转移方法的网络编码时延分析[J]. 通信学报, 2013, 34(9): 77-83.
[13]	王叶群,黄国策,张衡阳,郑博,景渊. Ad hoc网络中一种生命周期约束的自适应退避算法[J]. 通信学报, 2012, 33(11): 57-66.
[14]	任传伦,刘凤梅,李忠献,钮心忻,杨义先. 关于Negabent函数的若干结论[J]. 通信学报, 2011, 32(8): 179-182.
[15]	张凤荣,胡予濮,马华,谢敏,高军涛. 正形置换的迭代构造与计数[J]. 通信学报, 2011, 32(11A): 204-208.

T函数Walsh谱值与差分转移概率快速算法

Efficient algorithm for computing Walsh spectrum and differential probability

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 14

相关文章 15

Metrics

推荐阅读 0