Publication details

When Lagged Fibonacci Generators jump


CHETRY Moon K. BISHOI Susil Kumar MATYÁŠ Václav

Year of publication 2019
Type Article in Periodical
Magazine / Source Discrete Applied Mathematics
MU Faculty or unit

Faculty of Informatics

Keywords Stream cipher; Primitive polynomial; LFSR; LFG; Jump index
Description Jansen introduced a primitive called jumped Linear Feedback Shift Register (LFSR) for building LFSRs that can be clocked a large number of times with a single simple operation. This is useful in the construction of stream ciphers based on clock-controlled LFSRs. A concept of Lagged Fibonacci Generator (LFG) is also used as an important building block of key-stream generators in stream cipher cryptography. In this paper, we use the jumping concept of Jansen in case of LFG. We show that unlike LFSRs, LFGs need not jump always in the state space itself, even though the characteristic polynomial is primitive. Instead, it may have a hyper space jump depending on the characteristic primitive polynomial. We give a necessary and sufficient condition for an LFG to jump within the state space itself and when it exists, it is same as the degree of the characteristic polynomial.