Pseudo-random sequences with good statistical properties, such as low autocorrelation, high linear complexity and large 2-adic complexity, have been used in designing reliable stream ciphers. In this paper, we obtain the exact autocorrelation distribution of a class of binary sequences with three-level autocorrelation and analyze the 2-adic complexity of this class of sequences. Our results show that the 2-adic complexity of such a binary sequence with period N is at least (N + 1) − log2 (N + 1). We further show that it is maximal for infinitely many cases. This indicates that the 2-adic complexity of this class of sequences is large enough to resist the attack of the rational approximation algorithm (RAA) for feedback with carry shift registers (FCSRs).

Additional Metadata
Keywords 2-adic complexity, Autocorrelation, Pseudo-random sequences, Stream ciphers
Persistent URL dx.doi.org/10.1007/s12095-017-0233-x
Journal Cryptography and Communications
Citation
Sun, Y. (Yuhua), Wang, Q, & Yan, T. (Tongjiang). (2018). The exact autocorrelation distribution and 2-adic complexity of a class of binary sequences with almost optimal autocorrelation. Cryptography and Communications, 10(3), 467–477. doi:10.1007/s12095-017-0233-x