Paper 2005/241

On the binary sequences with high linear complexities and low linear complexities

Hao Chen and Liqing Xu

Abstract

Klapper [1] showed that there are binary sequences of period ( is a prime power , is an odd prime) with the maximal possible linear complexity when considered as sequences over , while the sequences have very low linear complexities when considered as sequences over . This suggests that the binary sequences with high linear complexities and low linear complexities are note secure in cryptography. In this note we give some simple constructions of the binary sequences with high linear complexities and low linear complexities. We also prove some lower bounds on the linear complexities of binary sequences and a lower bound on the number of the binary sequences with high linear complexities and low linear complexities .

Metadata
Available format(s)
PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Cryptographystream cipher linear complexity linear complexity
Contact author(s)
chenhao @ fudan edu cn
History
2005-07-30: received
Short URL
https://ia.cr/2005/241
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/241,
      author = {Hao Chen and Liqing Xu},
      title = {On the binary sequences with high ${GF}(2)$ linear complexities and low ${GF}(p)$ linear complexities},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/241},
      year = {2005},
      url = {https://eprint.iacr.org/2005/241}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.