International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities

Authors:
Hao Chen
Liqing Xu
Download:
URL: http://eprint.iacr.org/2005/241
Search ePrint
Search Google
Abstract: Klapper [1] showed that there are binary sequences of period $q^n-1$ ($q$ is a prime power $p^m$, $p$ is an odd prime) with the maximal possible linear complexity $q^n-1$ when considered as sequences over $GF(2)$, while the sequences have very low linear complexities when considered as sequences over $GF(p)$. This suggests that the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities are note secure in cryptography. In this note we give some simple constructions of the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities. We also prove some lower bounds on the $GF(p)$ linear complexities of binary sequences and a lower bound on the number of the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities .
BibTeX
@misc{eprint-2005-12576,
  title={On the binary sequences with high $GF(2)$ linear complexities and low $GF(p)$ linear complexities},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Cryptography, stream cipher, $GF(2)$ linear complexity, $GF(p)$ linear complexity},
  url={http://eprint.iacr.org/2005/241},
  note={ chenhao@fudan.edu.cn 12986 received 22 Jul 2005},
  author={Hao Chen and Liqing Xu},
  year=2005
}