On GF(p)-linear complexities of binary sequences

doi:lqxu@sei.ecnu.edu.cn

中国邮电高校学报(英文) ›› 2009, Vol. 16 ›› Issue (4): 112-115.doi: lqxu@sei.ecnu.edu.cn

On GF(p)-linear complexities of binary sequences

许丽卿

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

收稿日期:2009-01-03 修回日期:1900-01-01 出版日期:2009-08-31
通讯作者: 许丽卿

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

摘要：

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.

关键词:

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

Abstract:

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.

参考文献

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

[1]	张晓娇, 吴祥. Distributed consensus of Lurie multi-agent systems under directed topology: a contraction approach [J]. 中国邮电高校学报(英文版), 2023, 30(6): 11-21.
[2]	吴岳, 陈向勇, 邱建龙, 胡顺伟, 赵峰. Dynamic event-triggered leader-follower consensus of nonlinear multi-agent systems under directed weighted topology [J]. 中国邮电高校学报(英文版), 2023, 30(6): 3-10.
[3]	吕鹏超, 黄俊杰, 刘波. Linear-quadratic optimal control for time-varying descriptor systems via space decompositions [J]. 中国邮电高校学报(英文版), 2023, 30(6): 38-48.
[4]	孟慧任利娜赵宗渠. Identity-based proxy re-encryption scheme from RLWE assumption with ciphertext evolution[J]. 中国邮电高校学报(英文版), 2023, 30(5): 51-60.
[5]	Fan Xinyue, Wu Kai, Chen Shuai. RB-SLAM: visual SLAM based on rotated BEBLID feature point description [J]. 中国邮电高校学报(英文版), 2023, 30(3): 1-13.
[6]	路畅方园邱玲梁晓雯. Performance analysis and low complexity receiver design for extra-large scale MIMO systems with residual hardware impairments[J]. 中国邮电高校学报(英文版), 2023, 30(2): 18-25.
[7]	杨亚涛, 张若菁, 董辉, 马英杰, 张筱薇. WBZUC: novel white-box ZUC-128 stream cipher[J]. 中国邮电高校学报(英文版), 2023, 30(2): 96-106.
[8]	Zheng Zhidong, Yu Yanming, Liu Ning, Yuan Honggang, Lou Ning. Low-complexity detection based on maximum cumulative measure and Laurent decomposition for multi-h CPM signal [J]. 中国邮电高校学报(英文版), 2022, 29(6): 64-72.
[9]	He Yefeng, Yue Yuru, Li Guoqing, Liu Jixiang, Di Man, Pang Yibo. New controlled quantum key agreement protocols based on Bell states[J]. 中国邮电高校学报(英文版), 2022, 29(4): 42-50.
[10]	Xu Yan, Li Zheng, Ding Long, Xu Rui. Cross-domain data cloud storage auditing scheme based on certificateless cryptography [J]. 中国邮电高校学报(英文版), 2021, 28(6): 36-47.
[11]	杨帆, 姜梦雅, . Exo-LSTM: traffic flow prediction based on multifractal wavelet theory [J]. 中国邮电高校学报(英文版), 2021, 28(5): 102-110.
[12]	Guo Hairu, Meng Xueyao, Liu Yongli, Liu Shen. Improved HHO algorithm based on good point set and nonlinear convergence formula[J]. 中国邮电高校学报(英文版), 2021, 28(2): 48-67.
[13]	刘君胡予濮陈杰. General digital rights management solution based on white-box cryptography [J]. 中国邮电高校学报(英文版), 2021, 28(1): 52-63.
[14]	周游段瑞枫蒋伯峰. Reduced-state noncoherent MLSD method for CPM in aeronautical telemetry [J]. 中国邮电高校学报(英文版), 2020, 27(4): 43-53.
[15]	商玉洁张乐友高小旭. Continual auxiliary leakage-resilient attribute-based broadcast encryption with constant size ciphertexts [J]. 中国邮电高校学报(英文版), 2020, 27(4): 69-82.

On GF(p)-linear complexities of binary sequences

On GF(p)-linear complexities of binary sequences

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价