Necessary and Sufficient Conditions for Galois NFSRs Conditionally Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium

Jianghua Zhong; Yingyin Pan; Wenhui Kong; Dongdai Lin

Paper 2021/928

Necessary and Sufficient Conditions for Galois NFSRs Conditionally Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium

Jianghua Zhong, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences

Yingyin Pan, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences

Wenhui Kong, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences

Dongdai Lin, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences

Abstract

Grain and Trivium are two typical stream ciphers based on nonlinear feedback shift registers (NFSRs). The 160-stage Galois NFSR used in Grain was found conditionally equivalent to a 160-stage Fibonacci NFSR before Grain was introduced. But it remains unknown whether the 288-stage Galois NFSR used in Trivium is conditionally equivalent to a Fibonacci NFSR, though Trivium exists for over ten years and several types of Galois NFSRs have been found conditionally equivalent to Fibonacci ones with same stage number over the last decades. This paper applies the NFSR's dynamic system description, and obtains some necessary and sufficient conditions for Galois NFSRs to be conditionally equivalent to Fibonacci ones with same stage number, covering and improving the previous work on this research. As an application, the paper reveals that the 288-stage Galois NFSR used in Trivium is not conditionally equivalent to any Fibonacci NFSR, indicating the infeasibility of applying a conditionally equivalent Fibonacci NFSR to simplify its cryptanalysis, and indicating the good confusion and diffusion of the initial state to the output sequence generated from the Galois NFSR's 288-th bit that is used as one of inputs of Trivium's filtering function. This provides a formal extra justification of Trivium's good design, and allows future designs to be built by the same principle.

Note: Main results are extended.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: Shift register Boolean function stream cipher Trivium equivalence
Contact author(s): zhongjianghua @ iie ac cn
History: 2025-08-01: last of 2 revisions; 2021-07-09: received; See all versions
Short URL: https://ia.cr/2021/928
License: CC BY

BibTeX

@misc{cryptoeprint:2021/928,
      author = {Jianghua Zhong and Yingyin Pan and Wenhui Kong and Dongdai Lin},
      title = {Necessary and Sufficient Conditions for Galois {NFSRs} Conditionally Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/928},
      year = {2021},
      url = {https://eprint.iacr.org/2021/928}
}