Paper 2011/632

A Scalable Method for Constructing Galois NLFSRs with Period $2^n-1$ using Cross-Join Pairs

Elena Dubrova

Abstract

This paper presents a method for constructing $n$-stage Galois NLFSRs with period $2^n-1$ from $n$-stage maximum length LFSRs. We introduce nonlinearity into state cycles by adding a nonlinear Boolean function to the feedback polynomial of the LFSR. Each assignment of variables for which this function evaluates to 1 acts as a crossing point for the LFSR state cycle. By adding a copy of the same function to a later stage of the register, we cancel the effect of nonlinearity and join the state cycles back. The presented method requires no extra time steps and it has a smaller area overhead compared to the previous approaches based on cross-join pairs. It is feasible for large $n$. However, it has a number of limitations. One is that the resulting NLFSRs can have at most $\lfloor n/2 \rfloor$-1 stages with a nonlinear update. Another is that feedback functions depend only on state variables which are updated linearly. The latter implies that sequences generated by the presented method can also be generated using a nonlinear filter generator.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
NLFSRLFSRcross-join pairstream cipher
Contact author(s)
dubrova @ kth se
History
2011-11-23: received
Short URL
https://ia.cr/2011/632
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/632,
      author = {Elena Dubrova},
      title = {A Scalable Method for Constructing Galois NLFSRs with Period $2^n-1$ using Cross-Join Pairs},
      howpublished = {Cryptology ePrint Archive, Paper 2011/632},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/632}},
      url = {https://eprint.iacr.org/2011/632}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.