{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T09:50:59Z","timestamp":1781344259736,"version":"3.54.1"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T00:00:00Z","timestamp":1567468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772029"],"award-info":[{"award-number":["61772029"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872359"],"award-info":[{"award-number":["61872359"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61702124"],"award-info":[{"award-number":["61702124"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,12,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz057","type":"journal-article","created":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T11:17:44Z","timestamp":1557832664000},"page":"1793-1804","source":"Crossref","is-referenced-by-count":9,"title":["On Equivalence of Cascade Connections of Two Nonlinear Feedback Shift Registers"],"prefix":"10.1093","volume":"62","author":[{"given":"Jianghua","family":"Zhong","sequence":"first","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongdai","family":"Lin","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2019,9,3]]},"reference":[{"key":"2019121909072477900_ref1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-3-540-68351-3_14","article-title":"The Grain family of stream ciphers","author":"Hell","year":"2008","journal-title":"New Stream Cipher Designs: The eSTREAM Finalists"},{"key":"2019121909072477900_ref2","first-page":"451","article-title":"On lightweight stream ciphers with shorter internal states","author":"Armknecht","year":"2015","journal-title":"FSE 2015"},{"key":"2019121909072477900_ref3","first-page":"52","article-title":"On ciphers that continuously access the non-volatile key","volume":"2","author":"Mikhalev","year":"2016","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"2019121909072477900_ref4","doi-asserted-by":"crossref","first-page":"45","DOI":"10.46586\/tosc.v2017.i1.45-79","article-title":"Lizard\u2014a lightweight stream cipher for power-constrained devices","volume":"2017","author":"Hamann","year":"2017","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"2019121909072477900_ref5","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1007\/978-3-662-47989-6_32","article-title":"Cryptanalysis of full spout","author":"Lallemand","year":"2015","journal-title":"CRYPTO 2015"},{"key":"2019121909072477900_ref6","doi-asserted-by":"crossref","first-page":"5263","DOI":"10.1109\/TIT.2009.2030467","article-title":"A transformation from the Fibonacci to the Galois NLFSRs","volume":"55","author":"Dubrova","year":"2009","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2019121909072477900_ref7","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1016\/S0019-9958(79)90708-3","article-title":"On the cycle structure of some nonlinear shift register sequences","volume":"43","author":"Mykkeltveit","year":"1979","journal-title":"Inf. Control"},{"key":"2019121909072477900_ref8","first-page":"378","volume-title":"Equivalence of nonlinear shift-register","author":"Massey","year":"1964"},{"key":"2019121909072477900_ref9","first-page":"335","volume-title":"2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies","author":"Lin","year":"2013"},{"key":"2019121909072477900_ref10","doi-asserted-by":"crossref","first-page":"2961","DOI":"10.1109\/TIT.2010.2046250","article-title":"Finding matching initial states for equivalent NLFSRs in the Fibonacci and the Galois configurations","volume":"56","author":"Dubrova","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2019121909072477900_ref11","first-page":"187","article-title":"An equivalence-preserving tranformation of shift register","author":"Dubrova","year":"2014","journal-title":"Sequences and Their Applications\u2014SETA"},{"key":"2019121909072477900_ref12","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/0022-5193(69)90015-0","article-title":"Metabolic stability and epigenesis in randomly constructed genetic nets","volume":"22","author":"Kauffman","year":"1969","journal-title":"J. Theor. Biol."},{"key":"2019121909072477900_ref13","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1006\/excr.2000.5044","article-title":"Shape-dependent control of cell growth, differentiation, and apotosis: switching between attractors in cell regulatory networks","volume":"261","author":"Huang","year":"2000","journal-title":"Exp. Cell Res."},{"key":"2019121909072477900_ref14","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1093\/bioinformatics\/18.2.261","article-title":"Probabilistic Boolean neworks: a rule-based uncertainty model for gene regulatory networks","volume":"18","author":"Shmulevich","year":"2002","journal-title":"Bioinformatics"},{"key":"2019121909072477900_ref15","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1109\/TCBB.2016.2616470","article-title":"Classification of state trajectories in regulatory networks","volume":"15","author":"Karbalayghareh","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2019121909072477900_ref16","doi-asserted-by":"crossref","first-page":"5660","DOI":"10.1103\/PhysRevLett.84.5660","article-title":"Dynamics of complex systems: scaling laws or the period of Boolean networks","volume":"84","author":"Albert","year":"2000","journal-title":"Phys. Rev. Lett."},{"key":"2019121909072477900_ref17","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0167-2789(03)00174-X","article-title":"Boolean dynamics of networks with scale-free topology","volume":"185","author":"Aldana","year":"2003","journal-title":"Physica D"},{"key":"2019121909072477900_ref18","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.90.098701","article-title":"Superpolynomial growth in the number of attractots in Kauffman networks","volume":"90","author":"Samuelsson","year":"2003","journal-title":"Phys. Rev. Lett."},{"key":"2019121909072477900_ref19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.automatica.2017.04.040","article-title":"Asymptotic stability in probability for stochastic Boolean networks","volume":"83","author":"Possieri","year":"2017","journal-title":"Automatica"},{"key":"2019121909072477900_ref20","doi-asserted-by":"crossref","first-page":"1798","DOI":"10.1109\/TAC.2017.2754947","article-title":"Finite horizon tracking control of Boolean control networks","volume":"63","author":"Zhang","year":"2018","journal-title":"IEEE Trans. Automat. Contr."},{"key":"2019121909072477900_ref21","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.sysconle.2018.03.004","article-title":"Observability of Boolean networks via set controllability approach","volume":"115","author":"Cheng","year":"2018","journal-title":"Syst. Control Lett."},{"key":"2019121909072477900_ref22","first-page":"1","article-title":"Novel way to research nonlinear feedback shift register","volume":"57","author":"Zhao","year":"2014","journal-title":"Sci. China Inf. Sci."},{"key":"2019121909072477900_ref23","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1016\/j.jcss.2014.12.030","article-title":"A new linearization method for nonlinear feedback shift registers","volume":"81","author":"Zhong","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"key":"2019121909072477900_ref24","doi-asserted-by":"crossref","first-page":"2274","DOI":"10.1109\/TCOMM.2016.2557330","article-title":"Driven stability of nonlinear feedback shift registers","volume":"64","author":"Zhong","year":"2016","journal-title":"IEEE Trans. Commun."},{"key":"2019121909072477900_ref25","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-85729-097-7","volume-title":"Analysis and Control of Boolean Networks","author":"Cheng","year":"2011"},{"key":"2019121909072477900_ref26","first-page":"123","article-title":"Logic and logic-based control","volume":"6","author":"Qi","year":"2008","journal-title":"J. Contr. Theory Appl."},{"key":"2019121909072477900_ref27","volume-title":"Topics in Matrix Analysis","author":"Roger","year":"1991"},{"key":"2019121909072477900_ref28","doi-asserted-by":"crossref","DOI":"10.1142\/8323","volume-title":"An Introduction To Semi-Tensor Product of Matrices And Its Applications","author":"Cheng","year":"2012"},{"key":"2019121909072477900_ref29","first-page":"039110:1","volume-title":"Sci. China Inf. Sci.","author":"Zhong","year":"2018"},{"key":"2019121909072477900_ref30","doi-asserted-by":"crossref","first-page":"6429","DOI":"10.1109\/TIT.2018.2849392","article-title":"On minimum period of nonlinear feedback shift registers in Grain-like structure","volume":"64","author":"Zhong","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2019121909072477900_ref31","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.jco.2012.09.003","article-title":"On the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR","volume":"29","author":"Ma","year":"2013","journal-title":"J. Complexity"},{"key":"2019121909072477900_ref32","first-page":"1656","article-title":"On the uniqueness of decomposition of a NFSR into a cascade connection of smaller NFSRs","volume":"36","author":"Wang","year":"2014","journal-title":"J. Electron. Inf. Tech."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/62\/12\/1793\/31568458\/bxz057.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/62\/12\/1793\/31568458\/bxz057.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,12]],"date-time":"2020-12-12T19:34:01Z","timestamp":1607801641000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/62\/12\/1793\/5554328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,3]]},"references-count":32,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,9,3]]},"published-print":{"date-parts":[[2019,12,10]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz057","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,12]]},"published":{"date-parts":[[2019,9,3]]}}}