On the uniqueness of a type of cascade connection representations for NFSRs. (English) Zbl 1419.94027

Summary: Cascade connection architectures of nonlinear feedback shift registers (NFSRs) have been widely used in cryptography. In particular, the Grain family of stream ciphers uses the cascade connection architecture of an LFSR into an NFSR. A cascade connection representation is not always unique. The nonuniqueness of the representation may threat the security of a cipher. Inspired by the Grain family of stream ciphers, in this paper, we focus on cascade connections of an LFSR into an NFSR. A necessary and sufficient condition for the uniqueness of this class of cascade connection representations is provided under a reasonable condition that the involved NFSR has only trivial cascade connection decompositions. In particular, as a direct application of new results, it is theoretically proved that the cascade connection representation of a Grain-like structure, an \(n\)-bit primitive LFSR into an \(n\)-bit NFSR with a positive integer \(n\), is unique not considering some trivial distinct representations if the involved \(n\)-bit NFSR satisfies the condition. Besides, it is verified that all the main registers used in the Grain family of stream ciphers satisfy the condition.


94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
Full Text: DOI


[1] Ågren, M.; Hell, M.; Johansson, T.; Meier, W., Grain-128a: a new version of grain-128 with optional authentication, IJWMC, 5, 48-59, (2011)
[2] Armknecht, F.; Mikhalev, V.; Leander, G. (ed.), On lightweight stream ciphers with shorter internal states, No. 9054, 451-470, (2015), New York · Zbl 1382.94050
[3] Aumasson, J.; Henzen, L.; Meier, W.; Naya-Plasencia, M., Quark: a lightweight hash, J. Cryptol., 26, 313-339, (2013) · Zbl 1279.94053
[4] Cannière, CD; Dunkelman, O.; Knezevic, M.; Clavier, C. (ed.); Gaj, K. (ed.), KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers, No. 5747, 272-288, (2009), New York · Zbl 1290.94060
[5] Cannière, CD; Preneel, B.; Robshaw, MJB (ed.); Billet, O. (ed.), Trivium, No. 4986, 244-266, (2008), New York · Zbl 1285.94054
[6] Courtois, N.; Meier, W.; Biham, E. (ed.), Algebraic attacks on stream ciphers with linear feedback, No. 2656, 345-359, (2003), New York · Zbl 1038.94525
[7] Golomb S.W.: Shift Register Sequences. Aegean Park Press, Laguna Hills (1981). · Zbl 1152.94383
[8] Hamann, M.; Krause, M.; Meier, W., LIZARD—a lightweight stream cipher for power-constrained devices, IACR Trans. Symmetric Cryptol., 2017, 45-79, (2017)
[9] Hell, M.; Johansson, T.; Maximov, A.; Meier, W.; Robshaw, MJB (ed.); Billet, O. (ed.), The grain family of stream ciphers, No. 4986, 179-190, (2008), New York
[10] Jiang, Y.; Lin, D., On affine sub-families of grain-like structures, Des. Codes Cryptogr., 82, 531-542, (2017) · Zbl 1370.94471
[11] Ma, Z.; Qi, W.; Tian, T., On the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR, J. Complex., 29, 173-181, (2013) · Zbl 1261.94028
[12] Mikhalev, V.; Armknecht, F.; Müller, C., On ciphers that continuously access the non-volatile key, IACR Trans. Symmetric Cryptol., 2016, 52-79, (2016)
[13] Mykkeltveit, J.; Siu, M.; Tong, P., On the cycle structure of some nonlinear shift register sequences, Inf. Control, 43, 202-215, (1979) · Zbl 0431.68059
[14] Robshaw M.J.B., Billet O. (eds.): New Stream Cipher Designs-The eSTREAM Finalists. Lecture Notes in Computer Science, vol. 4986. Springer, New York (2008). · Zbl 1259.94006
[15] Zhang, J.; Qi, W.; Tian, T.; Wang, Z., Further results on the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR, IEEE Trans. Inf. Theory, 61, 645-654, (2015) · Zbl 1359.94563
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.