Paper 2021/928
Necessary and Sufficient Conditions for Galois NFSRs Equivalent to Fibonacci Ones and Their Application to the Stream Cipher Trivium
Jianghua Zhong, Yingyin Pan, 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.
Note: Several grammatical errors and typos were corrected. A theorem (i.e., Theorem 4.12') and its short proof were added to Page 17.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Shift registerBoolean functionstream cipherTriviumequivalenceobservabilityBoolean network
- Contact author(s)
- zhongjianghua @ iie ac cn
- History
- 2021-08-20: revised
- 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} 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}
}
