Paper 2025/2323 Original: eprint.iacr.org/2025/2323 ↗

An Improved Method for Predicting Truncated Fibonacci LFSRs over Integer Residue Rings

Abstract

Sequences over the residue ring of integers modulo $m$ generated by linear feedback shift registers (LFSRs) exhibit ring-level linearity and bit-level nonlinearity, making such kind of LFSRs (denoted as $\mathbb{Z}/(m)$-LFSRs) a key component of stream ciphers. Beyond fundamental cryptographic properties, the unpredictability of truncated $\mathbb{Z}/(m)$-LFSRs has attracted considerable attention as a critical security consideration in the design of stream cipher components. This paper investigates the unpredictability of truncated Fibonacci $\mathbb{Z}/(m)$-LFSRs under various scenarios. First, we provide a practical heuristic estimation for the values of two key parameters based on lattice theory, thereby avoiding previous blind search. This estimation is subsequently applied to determine the number of truncated digits required in different scenarios. Next, we develop a lattice-based method for finding annihilating polynomials over $\mathbb{Z}/(m)$ by the high-order truncated digits when the modulus $m$ is known but coefficients are unknown, filling a methodological gap for this specific case. Finally, we demonstrate that when both the modulus $m$ and coefficients are unknown but $m$ is close to a power of 2, our lattice constructed by the high-order truncated digits can yield annihilating polynomials over $\mathbb{Z}/(m)$ rather than $\mathbb{Z}$ as in [1], achieving a 41% reduction in digits and a 4x speedup for the recovery of ZUC's driving sequence with 17 high-order truncated digits. Experimental results confirm the efficacy of our methods.