On GF(p)-linear complexities of binary sequences

doi:lqxu@sei.ecnu.edu.cn

Acta Metallurgica Sinica(English letters) ›› 2009, Vol. 16 ›› Issue (4): 112-115.doi: lqxu@sei.ecnu.edu.cn

• Others • Previous Articles Next Articles

On GF(p)-linear complexities of binary sequences

XU Li-qing

Software Engineering Institute, East China Normal University, Shanghai 200062, China

Received:2009-01-03 Revised:1900-01-01 Online:2009-08-31
Contact: XU Li-qing

Abstract

Abstract:

Several geometric sequences have very low linear complexities when considered as sequences over GF(p), such as the binary sequences of period constructed by Chan and Games [1–2] (q is a prime power pm, p is an odd prime) with the maximal possible linear complexity when considered as sequences over GF(2). This indicates that binary sequences with high GF(2) linear complexities LC2 and low GF(p)-linear complexities LCp are not secure for use in stream ciphers. In this article, several lower bounds on the GF(p)-linear complexities of binary sequences is proved and the results are applied to the GF(p)-linear complexities of Blum-Blum-Shub, self-shrinking, and de Bruijn sequences. A lower bound on the number of the binary sequences with LC2 > LCp is also presented.

Key words:

cryptography;stream cipher;binary sequences;GF(2) linear complexity;GF(p)-linear complexity

XU Li-qing. On GF(p)-linear complexities of binary sequences[J]. Acta Metallurgica Sinica(English letters), 2009, 16(4): 112-115.

References

1. Menezes A, Van Oorschot P, Vanstone S. Handbook of applied cryptography. Boca Raton, FL, USA: CRC Press, 1997

2. Klapper A. The vulnerability of geometric sequences based on fields of odd characteristic. Journal of Cryptology, 1994, 7(1): 33-51

3. Chan A H , Games R A. On the linear span of binary sequences obtained from finite geometries. Advances in Cryptology: Proceedings of the 4th Annual International Cryptology Conference (Crypto’'86), Aug 11-15, 1986, Santa Barbara, CA, USA. LNCS 263. Berlin, Germany: Springer-Verlag, 1987: 405-417

4. Shamir A. On the generation of cryptographically strong pseudorandom sequences. ACM Transactions on Computer Systems, 1983, 1 (1): 38-44

5. Blum L, Blum M, Shub M. A simple unpredictable pseudo-random number generator. SIAM Journal on Computing, 1986, 15(2): 364-383

6. Cusick T W. Properties of the pseudorandom number generator. IEEE Transactions on Information Theory, 1995, 41(4): 1155-1159

7. Friedlander J B, Pomerance C, Shparlinski I E. Period of the power generator and small values of Carmuchael’s function. Mathematics of Computation, 2001, 70: 1591-1605

8. Blake I F, Gao S H, Mullin R C. Explicit factorization of over F_p with prime . Applicable Algebra in Engineering, Communication and Computing , 1993, 4(2): 89-94

9. Kaida T, Uehara S, Imamura K. An algorithm for the k-error linear complexity of sequences over GF(pm) with period p_n, p a prime. Information and Computation, 1999, 151(1/2): 134-147

10. Xiao G Z , Wei S M, Lam K Y, et al. A fast algorithm for determining the linear complexity of a sequence with period over GF(q). IEEE Transactions on Information Theory, 2000, 46(6): 2203-2206

11. Meier W, Staelbach O. The self-shrinking generator. Advances in Cryptology: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT’94), May 9-12, 1994, Perugia, Italy. LNCS 950. Berlin, Germany: Springer-Verlag, 1995: 205-214

12. Etzion T. Linear complexity of de Bruijn sequences-old and new results. IEEE Transactions on Information Theory, 1999, 45(2): 693-698

Metrics

Comments

Copyright © 2020 The Journal of China Universities of Posts and Telecommunications
　 Adress: P.O. Box 231,Beijing University of Posts and Telecommunications,10 Xi Tucheng Road,Beijing 100876,P.R.China　Post Code: 100081
Tel：86-010-62282493　Fax： 86-010-62283461　E-mail: jchupt@bupt.edu.cn
Support by: Beijing Magtech Co.Ltd

[1]	Yang Yatao, Zhang Ruoqing, Dong hui, Ma Yingjie, Zhang Xiaowei. WBZUC: novel white-box ZUC-128 stream cipher [J]. The Journal of China Universities of Posts and Telecommunications, 2023, 30(2): 96-106.
[2]	He Yefeng, Yue Yuru, Li Guoqing, Liu Jixiang, Di Man, Pang Yibo. New controlled quantum key agreement protocols based on Bell states [J]. The Journal of China Universities of Posts and Telecommunications, 2022, 29(4): 42-50.
[3]	Xu Yan, Li Zheng, Ding Long, Xu Rui. Cross-domain data cloud storage auditing scheme based on certificateless cryptography [J]. The Journal of China Universities of Posts and Telecommunications, 2021, 28(6): 36-47.
[4]	Liu Jun, Hu Yupu, Chen Jie. General digital rights management solution based on white-box cryptography [J]. The Journal of China Universities of Posts and Telecommunications, 2021, 28(1): 52-63.
[5]	Shang Yujie, Zhang Leyou, Gao Xiaoxu. Continual auxiliary leakage-resilient attribute-based broadcast encryption with constant size ciphertexts [J]. The Journal of China Universities of Posts and Telecommunications, 2020, 27(4): 69-82.
[6]	Tang Yongli, Wang Mingming, Ye Qing, Qin Panke, Zhao Zongqu. Lattice-based hierarchical identity-based broadcast encryption scheme in the standard model [J]. The Journal of China Universities of Posts and Telecommunications, 2019, 26(4): 70-79.
[7]	. Two-party certificateless authenticated key agreement protocol with enhanced security [J]. The Journal of China Universities of Posts and Telecommunications, 2019, 26(1): 12-20.
[8]	Li Shunbo, Huang Guangqiu, Wang Yan, Hui Feifei, Peng Jialong. Improved distinguisher for Achterbahn-128 stream cipher [J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2018, 25(2): 23-27.
[9]	Zhang Yanhua, Hu Yupu, Jiang Mingming, Xue Lili. Lattice-based sequential aggregate signatures with lazy verification [J]. Acta Metallurgica Sinica(English letters), 2015, 22(6): 36-44.
[10]	. Algebraic immunities of vector-valued functions over finite fields [J]. Acta Metallurgica Sinica(English letters), 2015, 22(5): 16-21.
[11]	. Identity-based strong designate verifier signature over lattices [J]. Acta Metallurgica Sinica(English letters), 2014, 21(6): 52-60.
[12]	LIU Xuan, ZHANG Wen-ying, LIU Xiang-zhong, LIU Feng. Eight-sided fortress: a lightweight block cipher [J]. Acta Metallurgica Sinica(English letters), 2014, 21(1): 104-108.
[13]	PANG Lei,SUN Mao-hua,LUO Shou-shan,WANG Bai,XIN Yang. Full privacy preserving electronic voting scheme [J]. Acta Metallurgica Sinica(English letters), 2012, 19(4): 86-93.
[14]	. Correlation power analysis of DECIMv2 [J]. Acta Metallurgica Sinica(English letters), 2011, 18(5): 118-123.
[15]	WANG Yan, HU Yu-pu, LI Shun-bo, YANG Yang. Linear complexity of sequences produced by single cycle T-function [J]. Acta Metallurgica Sinica(English letters), 2011, 18(4): 123-128.

On GF(p)-linear complexities of binary sequences

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments