Cryptology ePrint Archive: Report 2021/928

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

Jianghua Zhong and Yingyin Pan and Wenhui Kong and Dongdai Lin

Abstract: Many recent stream ciphers use Galois NFSRs as their main building blocks, such as the hardware-oriented finalists Grain and Trivium in the eSTREAM project. Previous work has found some types of Galois NFSRs equivalent to Fibonacci ones, including that used in Grain. Based on the observability of an NFSR on [0,N-1], which means any two initial states of an NFSR are distinguishable from their corresponding output sequences of length N, the paper first presents two easily verifiable necessary and sufficient conditions for Galois NFSRs equivalent to Fibonacci ones. It then validates both conditions by the Galois NFSRs previously found (not) equivalent to Fibonacci ones. As an application, the paper finally reveals that the 288-stage Galois NFSR used in Trivium is neither equivalent to a 288-stage Fibonacci NFSR, nor observable on [0,287], theoretically verifying Trivium's good design criteria of confusion and diffusion.

Category / Keywords: secret-key cryptography / Shift register, Boolean function, stream cipher, Trivium, equivalence, observability, Boolean network

Date: received 8 Jul 2021, last revised 20 Aug 2021

Contact author: zhongjianghua at iie ac cn

Available format(s): PDF | BibTeX Citation

Note: Several grammatical errors and typos were corrected. A theorem (i.e., Theorem 4.12') and its short proof were added to Page 17.

Version: 20210820:073227 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]