The decomposition of an NFSR into the cascade connection of two smaller NFSRs revisited. (English) Zbl 1512.94053

Summary: The cascade connection of two NFSRs is an important class of NFSRs which has been used in the design of many recently proposed stream ciphers, such as Grain v1, Grain-128a, Fruit and Sprout. In this paper, we consider the decomposition of an NFSR into the cascade connection of two smaller NFSRs, which is equivalent to the factorization of a characteristic function \(h\) into \(f*g\) where \(f\) and \(g\) are both characteristic functions. Inspired by the problem of factoring a large integer, we firstly consider a special case – that is, factoring \(h\) into the form \(h=g*g\). Based on the idea of “finding derivatives”, we completely solve this case in theory, and present an algorithm to compute \(g\) from \(h\). Moreover, if the characteristic function \(f\) is “close” to \(g\), then one can also use the same algorithm to determine \(g\) and then get \(f\) by the existing method. For the general case, the idea of “finding derivatives” can also be used and some interesting results can be derived.


94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
94A60 Cryptography


Trivium; Grain; Quark
Full Text: DOI


[1] Armknecht F., Mikhalev V.: On lightweight stream ciphers with shorter internal states. In: Fast Software Encryption, pp. 451-470. Springer, Berlin (2015). · Zbl 1382.94050
[2] 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
[3] Cannière, C.; Preneel, B., Trivium, 244-266 (2008), Berlin: Springer, Berlin · Zbl 1285.94054
[4] Cannière, C.; Dunkelman, O.; Knežević, M., KATAN and KATANTAN—A Family of Small and Efficient Hardware-Oriented Block Ciphers, 272-288 (2009), Berlin: Springer, Berlin · Zbl 1290.94060
[5] Courtois, N.; Meier, W., Algebraic Attacks on Stream Ciphers with Linear Feedback, 346-359 (2003), Berlin: Springer, Berlin · Zbl 1038.94525
[6] Coven, EM; Hedlund, GA; Rhodes, F., The commuting block maps problem, Trans. Am. Math. Soc., 249, 1, 113-138 (1979) · Zbl 0367.54019 · doi:10.1090/S0002-9947-1979-0526313-4
[7] Golomb, S., Shift Register Sequences (1982), Laguna Hills: Aegean Park Press, Laguna Hills
[8] Green, DH; Dimond, KR, Nonlinear product-feedback shift registers, Proc. Inst. Electr. Eng., 117, 4, 681-686 (1970) · doi:10.1049/piee.1970.0134
[9] Hamann, M.; Krause, M.; Meier, M., LIZARD—a lightweight stream cipher for power-constrained devices, IACR Trans. Symmetric Cryptol., 2017, 1, 45-79 (2017) · doi:10.46586/tosc.v2017.i1.45-79
[10] Hell, M.; Johansson, T.; Meier, W., The Grain Family of Stream Ciphers, 179-190 (2008), Berlin: Springer, Berlin
[11] Ma, Z.; Qi, WF; Tian, T., On the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR, J. Complex., 29, 2, 173-181 (2013) · Zbl 1261.94028 · doi:10.1016/j.jco.2012.09.003
[12] Meier, W.; Staffelbach, O., Fast correlation attacks on certain stream ciphers, J. Cryptol., 1, 3, 159-176 (1989) · Zbl 0673.94010 · doi:10.1007/BF02252874
[13] Mykkeltveit, J.; Siu, MK; Tong, P., On the cycle structure of some nonlinear shift register sequences, Inf. Control, 43, 202-215 (1979) · Zbl 0431.68059 · doi:10.1016/S0019-9958(79)90708-3
[14] Tian T., Zhang J.M., Ye C.D., Qi W.F.: A survey and new results on the decomposition of an NFSR into a cascade connection of two smaller NFSRs. Cryptology ePrint Archive 536 (2014). https://eprint.iacr.org/2014/536.
[15] Tian, T.; Zhang, JM; Qi, WF, On the uniqueness of a type of cascade connection representations for NFSRs, Des. Codes Cryptogr., 87, 10, 2267-2294 (2019) · Zbl 1419.94027 · doi:10.1007/s10623-019-00617-w
[16] Weger, B., Cryptanalysis of RSA with small prime difference, Appl. Algebra Eng. Commun. Comput., 13, 1, 17-28 (2002) · Zbl 1010.94007 · doi:10.1007/s002000100088
[17] 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
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.