Paper 2012/492

A Method for Generating Full Cycles by a Composition of NLFSRs

Elena Dubrova

Abstract

Non-Linear Feedback Shift Registers (NLFSR) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are usually hard to break with existing cryptanalytic methods. However, it is still not known how to construct large $n$-stage NLFSRs which generate full cycles of $2^n$ possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an $n*k$-stage register with period $O(2^{2n})$ can be constructed from $k$ $n$-stage NLFSRs by adding to their feedback functions a logic block of size $O(n*k)$. This logic block implements Boolean functions representing the set of pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size $O(n*k^2)$ and an extra time step. The presented method is feasible for generating very large full cycles.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. submitted to IEEE Transactions on Information Theory
Contact author(s)
dubrova @ kth se
History
2012-09-03: received
Short URL
https://ia.cr/2012/492
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/492,
      author = {Elena Dubrova},
      title = {A Method for Generating Full Cycles by a Composition of NLFSRs},
      howpublished = {Cryptology ePrint Archive, Paper 2012/492},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/492}},
      url = {https://eprint.iacr.org/2012/492}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.