单圈T-函数的2-adic复杂度和1-错2-adic复杂度

doi:10.3969/j.issn.1000-436x.2014.03.015

通信学报 ›› 2014, Vol. 35 ›› Issue (3): 135-139.doi: 10.3969/j.issn.1000-436x.2014.03.015

单圈T-函数的2-adic复杂度和1-错2-adic复杂度

游伟¹,戚文峰^2,³

¹ 国家数字交换系统工程技术研究中心，河南郑州 450002
² 解放军信息工程大学四院，河南郑州 450002
³ 解放军信息工程大学数学工程与先进计算国家重点实验室，河南郑州 450002

出版日期:2014-03-25 发布日期:2017-08-17
基金资助:
国家自然科学基金资助项目

The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions

Wei YOU¹,Wen-feng QI^2,³

¹ National Digital Switching System Engineering ＆ Technological Research Center,Zhengzhou 450002,China
² Fourth Institute,PLA Information Engineering University,Zhengzhou 450002,China
³ State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Information Engineering University,Zhengzhou 450002,China

Online:2014-03-25 Published:2017-08-17
Supported by:
The National Natural Science Foundation of China

摘要/Abstract

摘要：

研究了由F₂n上单圈 T-函数所导出权位序列的2-adic 复杂度，设 j为整数，0≤ j≤n?1。结论表明，第 j权位序列2-adic复杂度的上界为lb(2^2j+1)。另外，讨论了与所有单圈 T-函数所导出第 j权位序列相对应的2-adic整数的分布，分布情况说明这个上界是可以达到的。最后，研究了权位序列的1-错2-adic复杂度。研究结果表明对所有1≤ j≤n?1，权位序列x _j的1-错2-adic 复杂度都与其2-adic复杂度相同。

关键词: 序列密码, 2-adic复杂度, k-错2-adic复杂度, 单圈T-函数, 权位序列

Abstract:

The 2-adic complexities of the coordinate sequences derived from single cycle T-functions over F ₂n were investigated.Let j be an integer such that 0≤ j≤n?1.It is shown that the 2-adic complexity of the j th coordinate sequence is upper bounded by lb(2^2j+1).The distribution of the corresponding 2-adic number associated with the j th coordinate sequence of all single cycle T-functions was also discussed,which implies that the upper bound is attainable.Moreover,1-error 2-adic complexity was also studied.It was proved that the 1-error 2-adic complexity of the j th coordinate sequence is equal to its 2-adic complexity except for j=0.

Key words: stream cipher, 2-adic complexity, k-error 2-adic complexity, single cycle T-functions, coordinate se-quences

游伟,戚文峰. 单圈T-函数的2-adic复杂度和1-错2-adic复杂度[J]. 通信学报, 2014, 35(3): 135-139.

Wei YOU,Wen-feng QI. The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions[J]. Journal on Communications, 2014, 35(3): 135-139.

图/表 2

参考文献 11

[1]	COURTOIS N , MEIER W . Algebraic attacks on stream ciphers with linear feedback[A]. Cryptology-EUROCRYPT 2003[C]. Warsaw,Poland, 2003. 345-359.
[2]	SIEGENTHALER T . Decrypting a class of stream ciphers using ciphertext only[J]. IEEE Transactions on Computers, 1985,C-34(1): 81-85.
[3]	MEIER W , STAFFELBACH O . Fast correlation attacks on certain stream ciphers[J]. Journal of Cryptology, 1989,1(3): 159-176.
[4]	KLIMOV A , SHAMIR A . A new class of invertible mappings[A]. Workshop on Cryptographic Hardware and Embedded Systems-CHES 2002[C]. Redwood Shores,CA,USA, 2003. 470-483.
[5]	KLAPPER A , GORESKY M . 2-adic shift registers[A]. Fast Software Encryption-FSE 1993[C]. Cambridge,UK, 1993. 174-178.
[6]	KLAPPER A , GORESKY M . Cryptanalysis based on 2-adic rational approximation[A]. Cryptology-CRYPTO 1995[C]. Santa Barbara,California,USA, 1995. 262-273.
[7]	KLIMOV A , SHAMIR A . Cryptographic applications of T-functions[A]. Workshop on Selected Areas in Cryptography-SAC 2003[C]. Ottawa,Canada, 2004. 248-261.
[8]	ZHANG W Y , WU C-K . The algebraic normal form,linear complexity and k-error linear complexity of single-cycle T-function[A]. Sequences and Their Applications-SETA 2006[C]. Beijing,China, 2006. 391-401.
[9]	KLIMOV A , SHAMIR A . New cryptographic primitives based on multiword T-functions[A]. Fast Software Encryption-FSE 2004[C]. Delhi,India, 2004. 1-15.
[10]	KLIMOV A , SHAMIR A . New applications of T-functions in block ciphers and hash functions[A]. Fast Software Encryption-FSE 2005[C]. Paris,France, 2005. 18-31.
[11]	HU H G , FENG D G . On the 2-adic complexity and the k-error 2-adic complexity of periodic binary sequences[J]. IEEE Transactions on Information Theory, 2008,54(2): 874-883.

单圈T-函数的2-adic复杂度和1-错2-adic复杂度

The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 11

相关文章 11

Metrics

推荐阅读 0

[1]	王艳,李顺波,薛改娜. SLCE序列的2-adic复杂度[J]. 通信学报, 2019, 40(8): 151-156.
[2]	吴晨煌,许春香,杜小妮. 周期为p²的q元序列的k–错线性复杂度[J]. 通信学报, 2019, 40(12): 21-28.
[3]	游伟1，戚文峰2,3. 单圈T-函数的2-adic复杂度和1-错2-adic复杂度[J]. 通信学报, 2014, 35(3): 15-139.
[4]	高海英,金晨辉. 基于多个独立区分特征的序列密码最优联合区分器[J]. 通信学报, 2012, 33(7): 44-48.
[5]	谭刚敏,曾光,韩文报,张娜. 本原σ-LFSR序列距离向量的计算[J]. 通信学报, 2011, 32(9): 33-37.
[6]	杨阳,曾光. 序列密码算法RAKAPOSHI的动态移存器构造[J]. 通信学报, 2011, 32(11A): 178-183.
[7]	李鹤龄,戚文峰. F_p上pⁿ-周期序列的k-错误序列[J]. 通信学报, 2010, 31(6): 19-24.
[8]	谭林,戚文峰. 2^p周期二元序列的线性复杂度和k错线性复杂度[J]. 通信学报, 2008, 29(7): 44-49.
[9]	罗永龙,戚文峰. Klimov-Shamir T-函数的代数结构[J]. 通信学报, 2008, 29(10): 143-148.
[10]	刘训寿,戚文峰. 给定线性复杂度谱的序列的条数[J]. 通信学报, 2006, 27(12): 10-13.
[11]	陈兰芳,戚文峰. 周期为2^mpⁿ的二元序列的2-adic复杂度[J]. 通信学报, 2005, 26(6): 6-10.