On Equivalence of Cascade Connections of Two Nonlinear Feedback Shift Registers. (3rd September 2019)

• Record Type: Journal Article
• Authors: Zhong, Jianghua; Lin, Dongdai
• Is Part Of: Computer journal. Volume 62:Number 12(2019)
• Page Start: 1793
• Page End: 1804
• Publication Date: 2019-09-03
• Subjects: nonlinear feedback shift register -- stream cipher -- Grain -- equivalence -- Boolean network; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz057
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Grain is a hardware-oriented finalist in the eSTREAM Stream Cipher Project. As a particular Galois nonlinear feedback shift register (NFSR), cascade connection of two NFSRs has been used as the main building block in the Grain family of stream ciphers. Two NFSRs are said to be equivalent if their sets of output sequences are equal. Finding properties of equivalent cascade connections of two NFSRs is useful to the design of the Grain family of stream ciphers. This paper first gives some properties of feedback functions between equivalent cascade connections of two NFSRs. It then shows that a cascade connection of two NFSRs and its equivalent Galois NFSR have isomorphic state diagrams if they have the same stage number. Finally, the paper reveals that for any given cascade connection of an $m$ -stage NFSR1 into an $n$ -stage NFSR2, there is only another one equivalent cascade connection of an $m$ -stage NFSR3 into an $n$ -stage NFSR4; moreover, the feedback functions of NFSR1 and NFSR3 are dual complementary, and the feedback functions of NFSR2 and NFSR4 are complementary. As an application of this property, the paper shows that the existing Grain family of stream ciphers have used the ones with lower cost of hardware implementations between their own two equivalent cascade connections, confirming their good design criteria.