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

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]	周游段瑞枫蒋伯峰. Reduced-state noncoherent MLSD method for CPM in aeronautical telemetry [J]. 中国邮电高校学报(英文版), 2020, 27(4): 43-53.
[2]	商玉洁张乐友高小旭. Continual auxiliary leakage-resilient attribute-based broadcast encryption with constant size ciphertexts [J]. 中国邮电高校学报(英文版), 2020, 27(4): 69-82.
[3]	Lin Qiaomin, Fa Anqi, Pan Min, Xie Qiang, Du Kun, Sheng Michael. Cleaning RFID data streams based on K-means clustering method[J]. 中国邮电高校学报(英文版), 2020, 27(2): 72-81.
[4]	宋成顾心安平源张亚东. Conditional privacy protection authentication scheme based on bilinear pairings for VANET[J]. 中国邮电高校学报(英文版), 2020, 27(1): 62-71.
[5]	Yu Cuiping, Gao Yuan, Wu Fan, Liu Yuanan. Miniaturized single-channel concurrent dual-band mixing architecture with one frequency-divided local oscillator[J]. 中国邮电高校学报(英文版), 2019, 26(4): 1-7.
[6]	Tang Yongli, Wang Mingming, Ye Qing, Qin Panke, Zhao Zongqu. Lattice-based hierarchical identity-based broadcast encryption scheme in the standard model[J]. 中国邮电高校学报(英文版), 2019, 26(4): 70-79.
[7]	张孝甜赵生妹. High Efficiency Polar coding key reconciliation scheme in wireless channel[J]. 中国邮电高校学报(英文版), 2019, 26(3): 50-55.
[8]	刘振亚李曦纪红张鹤立. Hierarchical mobility prediction in the future heterogeneous networks for the tradeoff between accuracy and complexity[J]. 中国邮电高校学报(英文版), 2019, 26(3): 15-21.
[9]	张志军牛凯董超. Iterative list decoding approach for Reed-Solomon codes[J]. 中国邮电高校学报(英文版), 2019, 26(3): 8-14.
[10]	吴涛景晓军. Two-party certificateless authenticated key agreement protocol with enhanced security[J]. 中国邮电高校学报(英文版), 2019, 26(1): 12-20.
[11]	Qu Tuosi, Cao Haiyan, Xu Fangmin, Wang Xiumin. Low complexity detection algorithm based on optimized Neumann series for massive MIMO system[J]. 中国邮电高校学报(英文版), 2018, 25(6): 97-100.
[12]	朱晓荣董天才 Wang Yong. Concurrent streaming over heterogeneous wireless networks: technology and realization[J]. 中国邮电高校学报(英文版), 2018, 25(5): 49-59.
[13]	宋成张亚东王磊刘志中. Research on k-anonymity privacy protection scheme based on bilinear pairings [J]. 中国邮电高校学报(英文版), 2018, 25(5): 12-19.
[14]	孙书龙 Linmin. Low complexity NB-LDPC decoder based on shared comparator architecture for ECN/EVN[J]. 中国邮电高校学报(英文版), 2018, 25(3): 65-70.
[15]	Li Shunbo, Huang Guangqiu, Wang Yan, Hui Feifei, Peng Jialong. Improved distinguisher for Achterbahn-128 stream cipher[J]. 中国邮电高校学报(英文版), 2018, 25(2): 23-27.

On GF(p)-linear complexities of binary sequences

On GF(p)-linear complexities of binary sequences

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价