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

• Others • 上一篇    下一篇

On GF(p)-linear complexities of binary sequences

许丽卿   

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

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

摘要:

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:

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