新的周期为pm的GF(h)上广义割圆序列的线性复杂度

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

Journal on Communications ›› 2017, Vol. 38 ›› Issue (9): 39-45.doi: 10.11959/j.issn.1000-436x.2017181

• Papers • Previous Articles Next Articles

On the linear complexity of a new generalized cyclotomic sequence with length ^mover GF(h)

Long-fei LIU¹,Kai YANG¹,Xiao-yuan YANG^1,²

¹ Key Laboratory of Network ＆Information Security of Armed Police Force,Engineering University of Armed Police Force,Xi’an 710086,China
² Key Laboratory of Computer Network ＆Information Security of the Ministry of Education,Xidian University,Xi’an 710071,China

Revised:2017-04-05 Online:2017-09-01 Published:2017-10-18
Supported by:
The National Cryptography Development Fund of China(MMJJ20170112);The National Key Research and Development Program of China(2017YFB0802002);The National Natural Science Foundation of China(61562077);The National Natural Science Foundation of China(U1636114);The National Natural Science Foundation of China(64572521);The National Natural Science Foundation of China(61402530);The Basic Research Foundation of Engineering College of APF(WJY201518)

Abstract

Abstract:

Based on the Ding-generalized cyclotomy,a new class of generalized cyclotomic sequences with length p^m over the finite field of power of odd prime order was constructed,and the sequence was balanced.The linear complexity of the sequences was determined using the relationship between h and p and the theory of polynomial over finite field.It is shown that the sequence has good linear complexity,and it can resist attacks from the application of the Berlekamp-Massey algorithm.

Key words: stream cipher, pseudo-random sequence, generalized cyclotomy, linear complexity

CLC Number:

TP302

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.

Figures/Tables 1

序列	域	周期	最大线性复杂度	最小线性复杂度
文献[20]构造序列	GF(2)	p	p	$\frac{p - 1}{2}$
文献[21]构造序列	GF(q)	n	n	$\frac{n - 1}{2}$
文献[4]构造序列	GF(2)	p²	p²	$\frac{p^{2} + 1}{2}$
文献[18]构造序列	GF(q)	n²	n²	$\frac{n^{2} - 1}{2}$
文献[6]构造序列	GF(2)	p^m	p^m	$\frac{p^{m} + 1}{2}$
本文构造序列	GF(h)	p^m	p^m	$p^{m} - (\frac{p^{m - 1} (p - 1)}{2} + \dots + \frac{p (p - 1)}{2} + \frac{p - 1}{2}) - 1$

References 21

[1]	KLAPPER A . The vulnerability of geometric sequences based on fields of odd characteristic[J]. Journal of Crypto, 1994,7(1): 33-51.
[2]	DING C S . Linear complexity of generalized cyclotomic binary sequences of order 2[J]. Finite Fields and Their Applications, 1997,8: 159-174.
[3]	DING C S , HELLESETH T . New generalized cyclotomy and its applications[J]. Finite Fields and Their Applications, 1998,4(2): 140-166.
[4]	YAN T J , HUANG B J , XIAO G Z . Cryptographic properties of some binary generalized cyclotomic sequences with the length p²[J]. Information Sciences, 2008,178(3): 1078-1086.
[5]	KIM Y J , JIN S Y , SONG H Y . Linear complexity and autocorrelation of prime cube sequences[C]// Applicable Algebra in Engineering,Communication and Computing. 2007: 188-197.
[6]	YAN T J , LI S Q , XIAO G Z . On the linear complexity of generalized cyclotomic sequences with the period p^m[J]. Applied Mathematics Letters, 2008,21(2): 187-193.
[7]	DU X N , CHEN Z X . Trace representation of binary generalized cyclotomic sequences with length p^m[J]. IEICE Transaction on Fundamentals, 2011,E94-A(2): 761-765.
[8]	DING C S . Cyclic codes from the two primes sequences[J]. IEEE Transactions on Information Theory, 2012,58(6): 3881-3891.
[9]	DING C S . Cyclic codes from cyclotomic sequences of order four[J]. Finite Fields and Their Applications, 2013,23(1): 8-34.
[10]	CAI H , ZHOU Z C , YANG Y.et al . A new construction of frequency-hopping sequences optimal partial hamming correlation[J]. IEEE Transactions on Information Theory, 2014,60(9): 5782-5790.
[11]	柯品惠, 章海辉, 张胜元 . 新的具有最优平均汉明相关性的跳频序列族[J]. 通信学报, 2012,33(9): 168-175.
	KE P H , ZHANG H H , ZHANG S Y . New class of frequency-hopping sequences set with optimal average Hamming correlation property[J]. Journal on Communications, 2012,33(9): 168-175.
[12]	XU S D . Optimal frequency-hopping sequences sets based on cyclotomy[J]. International Journal of Foundations of Computer Science, 2016,27(4): 443-462.
[13]	CAI H , LIANG H B , TANG X H . Constructions of optimal 2-D optical orthogonal codes via generalized cyclotomic classes[J]. IEEE Transactions on Information Theory, 2015,61(1): 688-695.
[14]	CUSICK T W , DING C S , RENVALL A . Stream ciphers and number theory[M]. Elsevier Science Pub Co, 1998.
[15]	FAN C L , GE G . A unified approach to whiteman's and Ding- Helleseth's generalized cyclotomy over residue class rings[J]. IEEE Transactions on Information Theory, 2014,60(2): 1326-1336.
[16]	LI D D , CHANG Z L . Linear complexity of generalised cyclotomic quaternary sequences of length 2p(m+1)q(n+1)[J]. IET Information Security, 2016,10(2): 104-111.
[17]	ZHOU Y Q , CHANG Z L . Linear complexity of new generalized cyclotomic sequences of order two with odd length[J]. IEICE Transaction on Fundamentals, 2016,E99-A(8): 1639-1644.
[18]	WANG Q Y , JIANG Y P , LIN D D . Linear complexity of binary generalized cyclotomic sequences over GF(q)[J]. Journal of Complexity, 2015,31(5): 731-740.
[19]	WANG Q Y , JIANG Y P , LIN D D . Linear complexity of Ding-Helleseth sequences of order 2 over GF(l)[J]. Cryptography and Communications, 2015,8(1): 33-49.
[20]	DING C S , HELLESETH T , SHAN W . On the linear complexity of legendre sequences[J]. IEEE Transactions on Information Theory, 1998,44(3): 1276-1278.
[21]	WANG Q Y , LIN D D , GUANG X . On the linear complexity of legendre sequences over Fq[J]. IEICE Transaction on Fundamentals, 2014,E97-A(7): 1627-1630.

Metrics

Recommended 0

No Suggested Reading articles found!

On the linear complexity of a new generalized cyclotomic sequence with length ^mover GF(h)

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 21

Related Articles 15

Metrics

Recommended 0

[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]	Zhixiong CHEN,Chenhuang WU. k-error linear complexity of binary cyclotomic generators [J]. Journal on Communications, 2019, 40(2): 197-206.
[4]	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.
[5]	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.
[6]	Yubo LI,Miao CHEN,Tao LIU,Ying ZHANG. Constructions of perfect Gaussian integer sequences of odd prime length [J]. Journal on Communications, 2018, 39(11): 190-197.
[7]	Chun-jie CAO,Jing-zhang SUN,Zhi-qiang ZHANG,Long-juan WANG,Meng-xing HUANG. Analysis of super-long and sparse feature in pseudo-random sequence based on similarity [J]. Journal on Communications, 2016, 37(Z1): 25-29.
[8]	Meng MA,Ya-qun ZHAO. Research on linear approximations of simplified Trivium [J]. Journal on Communications, 2016, 37(6): 185-191.
[9]	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.
[10]	. 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.
[11]	Pin-hui KE,Hai-hui ZHANG,Sheng-yuan ZHANG. New class of frequency-hopping sequences set with optimal average Hamming correlation property [J]. Journal on Communications, 2012, 33(9): 168-175.
[12]	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.
[13]	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.
[14]	Jun-tao GAO,Yu-pu HU,Xue-lian LI,Shang-rong XIANG. Linear complexity of two classes of optimal sets frequency-hopping sequences [J]. Journal on Communications, 2012, 33(2): 175-181.
[15]	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.

On the linear complexity of a new generalized cyclotomic sequence with length mover GF(h)

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 21

Related Articles 15

Metrics

Recommended 0

On the linear complexity of a new generalized cyclotomic sequence with length ^mover GF(h)