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

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

Journal on Communications ›› 2014, Vol. 35 ›› Issue (3): 135-139.doi: 10.3969/j.issn.1000-436x.2014.03.015

• Academic paper • Previous Articles Next Articles

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

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

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.

Figures/Tables 2

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

[1]	Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis [J]. Journal on Communications, 2022, 43(11): 183-198.
[2]	Yan WANG,Shunbo LI,Gaina XUE. 2-adic complexity of SLCE sequence [J]. Journal on Communications, 2019, 40(8): 151-156.
[3]	Chenhuang WU,Chunxiang XU,Xiaoni DU. k-error linear complexity of q-ary sequence of period p² [J]. Journal on Communications, 2019, 40(12): 21-28.
[4]	Ruilin LI,Jiao HU,Chaojing TANG. Collision analysis of the GMR-2 cipher used in the satellite phone [J]. Journal on Communications, 2018, 39(2): 88-95.
[5]	Long-fei LIU,Kai YANG,Xiao-yuan YANG. On the linear complexity of a new generalized cyclotomic sequence with length ^mover GF(h) [J]. Journal on Communications, 2017, 38(9): 39-45.
[6]	Meng MA,Ya-qun ZHAO. Research on linear approximations of simplified Trivium [J]. Journal on Communications, 2016, 37(6): 185-191.
[7]	. The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions [J]. Journal on Communications, 2014, 35(3): 15-139.
[8]	Hai-ying GAO,Chen-hui JIN. Optimal combined distinguisher of stream cipher with multiple independent distinguishing characters [J]. Journal on Communications, 2012, 33(7): 44-48.
[9]	Li-hua DONG,Yu-pu HU,Yong ZENG. Computing on the joint quadratic complexity of multiple periodic sequences [J]. Journal on Communications, 2012, 33(6): 11-18.
[10]	Gang-min TAN,Guang ZENG,Wen-bao HAN,Na ZHANG. Calculation of interval vectors of primitive σ-LFSR sequences [J]. Journal on Communications, 2011, 32(9): 33-37.
[11]	Yang YANG,Guang ZENG. Construction of dynamic linear feedback shift registers in RAKAPOSHI stream cipher [J]. Journal on Communications, 2011, 32(11A): 178-183.
[12]	Feng-rong ZHANG,Yu-pu HU,Hua MA,Min XIE,Jun-tao GAO. Recursive constructions and counting of orthomorphic permutations [J]. Journal on Communications, 2011, 32(11A): 204-208.
[13]	Si-wei SUN,Lei HU. Two improved attacks on the WEP data encryption protocol [J]. Journal on Communications, 2010, 31(9): 103-109.
[14]	He-ling LI,Wen-feng QI. k-error sequences ofpⁿ-periodic sequences overF_p [J]. Journal on Communications, 2010, 31(6): 19-24.
[15]	Guang ZENG,Yang YANG,Wen-bao HAN,Shu-qin FAN. Primitive polynomials and word oriented linear feedback shift registers [J]. Journal on Communications, 2009, 30(11A): 111-116.

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

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 2

References 11

Related Articles 15

Metrics

Recommended 0