Grain-like structures with minimal and maximal period sequences. (English) Zbl 1470.94071

Summary: Nonlinear feedback shift registers (NFSRs) are important building blocks for stream ciphers. The cascade connection of an \(n\)-stage full-length linear feedback shift register (LFSR) into an \(m\)-stage NFSR is called a Grain-like structure. In this paper, we focus on Grain-like structures which can generate minimal and maximal possible period sequences. The existence of Grain-like structures which can generate minimal possible period sequences is proved for the cases \(m=n\) and \(m>n\). The number of such Grain-like structures is estimated in both cases. Two necessary conditions are presented for Grain-like structures to generate maximal possible period sequences. Moreover, some interesting properties of such Grain-like structures are discussed.


94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography
11B50 Sequences (mod \(m\))


Grain; Quark; Trivium
Full Text: DOI


[1] Aumasson, J.; Henzen, L.; Meier, W.; Nayaplasencia, M., QUARK: a lightweight hash, J. Cryptol., 26, 4, 313-339 (2013) · Zbl 1279.94053 · doi:10.1007/s00145-012-9125-6
[2] Cannière, C.; Preneel, B., Trivium, Lecture Notes in Computer Science, 244-266 (2008), Berlin: Springer, Berlin · Zbl 1285.94054
[3] Cannière, C.; Dunkelman, O.; Knežević, M., KATAN and KATANTAN—A Family of Small and Efficient Hardware-Oriented Block Ciphers. Lecture Notes in Computer Science,, 272-288 (2009), Berlin: Springer, Berlin · Zbl 1290.94060
[4] Courtois N., Meier W.: Algebraic Attacks on Stream Ciphers with Linear Feedback. Lecture Notes in Computer Science, vol. 2656, pp. 346-359. Springer, Berlin (2003). · Zbl 1038.94525
[5] Golomb, SW, Shift Register Sequences (1982), California: Aegean Park Press, California · Zbl 1152.94383
[6] Green, DH; Dimond, KR, Nonlinear product-feedback shift registers, Proc. Inst. Electr. Eng., 117, 4, 681-686 (1970) · doi:10.1049/piee.1970.0134
[7] Hell M., Johansson T., Meier W.: “The Grain Family of Stream Ciphers”. Lecture Notes in Computer Science, vol. 4986, pp. 179-190. Springer, Berlin (2008).
[8] Hu, HG; Gong, G., Periods on two kinds of nonlinear feedback shift registers with time varying feedback functions, Int. J. Found. Comput. Sci., 22, 6, 1317-1329 (2011) · Zbl 1236.94046 · doi:10.1142/S0129054111008738
[9] Jiang, YP; Lin, DD, On affine sub-families of Grain-like structures, Des. Codes Crypt., 82, 3, 531-542 (2017) · Zbl 1370.94471 · doi:10.1007/s10623-016-0178-7
[10] Lidl, R.; Niedereiter, H., Finite Field (1983), Canada: Addison-Wesley, Canada
[11] Meier, W.; Staffelbach, O., Fast correlation attacks on certain stream cipher, J. Cryptol., 1, 3, 159-176 (1989) · Zbl 0673.94010 · doi:10.1007/BF02252874
[12] Mykkeltveit, J.; Siu, MK; Tong, P., On the cycle structure of some nonlinear shift register sequences, Inf. Control, 43, 2, 202-215 (1979) · Zbl 0431.68059 · doi:10.1016/S0019-9958(79)90708-3
[13] Yang, YH; Zeng, XY; Xu, YG, Periods on the cascade connection of an LFSR and an NFSR, Chin. J. Electron., 28, 2, 301-308 (2019) · doi:10.1049/cje.2019.01.018
[14] Zhang B., Li Z.Q., Feng D.G., Lin D.D.: Near Collision Attack on the Grain v1 Stream Cipher. Lecture Notes in Computer Science, vol. 8424, pp. 518-538. Springer, Berlin (2014). · Zbl 1321.94097
[15] Zhang, JM; Qi, WF; Tian, T.; Wang, ZX, Further results on the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR, IEEE Trans. Inf. Theory, 61, 1, 645-654 (2015) · Zbl 1359.94563 · doi:10.1109/TIT.2014.2371542
[16] Zhang, B.; Xu, C.; Meier, W., Fast Near Collision Attack on the Grain v1 Stream Cipher. Lecture Notes in Computer Science, vol. 10821, 771-802 (2018), Cham: Springer, Cham · Zbl 1428.94099
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.