logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 1: 010204(2018) https://doi.org/10.1007/s11432-017-9269-6

Nonsingularity of Grain-like cascade FSRs via semi-tensor product

More info
  • ReceivedSep 7, 2017
  • AcceptedOct 17, 2017
  • PublishedDec 12, 2017

Abstract

In this paper, Grain-like cascade feedback shift registers (FSRs) are regarded as two Boolean networks (BNs), and the semi-tensor product (STP) of the matrices is used to convert the Grain-like cascade FSRs into an equivalent linear equation. Based on the STP, a novel method is proposed herein to investigate the nonsingularity of Grain-like cascade FSRs. First, we investigate the property of the state transition matrix of Grain-like cascade FSRs. We then propose their sufficient and necessary nonsingularity condition. Next, we regard the Grain-like cascade FSRs as Boolean control networks (BCNs) and further provide a sufficient condition of their nonsingularity. Finally, two examples are provided to illustrate the results obtained in this paper.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61573102, 11671361), Natural Science Foundation of Jiangsu Province of China (Grant No. BK20170019), Jiangsu Provincial Key Laboratory of Networked Collective Intelligence (Grant No. BM2017002), China Postdoctoral Science Foundation (Grant Nos. 2014M560377, 2015T80483), Jiangsu Province Six Talent Peaks Project (Grant No. 2015-ZNDW-002), and Fundamental Research Funds for the Central Universities.


References

[1] Goresky M, Klapper A. Algebraic Shift Register Sequences. Cambridge: Cambridge University Press, 2012. Google Scholar

[2] Golomb S W. Shift Register Sequences. Walnut Creek: Aegean Park Press, 1982. Google Scholar

[3] Goresky M, Klapper A. Pseudonoise sequences based on algebraic feedback shift registers. IEEE Trans Inf Theory, 2006, 52: 1649--1662. Google Scholar

[4] Li C Y, Zeng X Y, Helleseth T, et al. The properties of a class of linear FSRs and their applications to the construction of nonlinear FSRs. IEEE Trans Inf Theory, 2014, 60: 3052--3061. Google Scholar

[5] Massey J. Shift-register synthesis and BCH decoding. IEEE Trans Inf Theory, 1969, 15: 122--127. Google Scholar

[6] Meier W, Staffelbach O. Fast correlation attacks on certain stream ciphers. J Cryptology, 1989, 1: 159--176. Google Scholar

[7] Hell M, Johansson T, Meier M. Grain: a stream cipher for constrained environments. Int J Wirel Mobile Comput, 2007, 2: 86--93. Google Scholar

[8] Gammel B M, Gottfert R, Kniffler O. An NLFSR-based stream cipher. In: Proceedings of IEEE International Symposium on Circuits and Systems, Island of Kos, 2006. Google Scholar

[9] Chen K, Henricksen M, Millan W, et al. Dragon: a fast word based stream cipher. In: Proceedings of International Conference on Information Security and Cryptology. Berlin: Springer, 2004. 33--50. Google Scholar

[10] Gammel B, Gottfert R, Kniffler O. Achterbahn-128/80: design and analysis. ECRYPT Network of Excellence -- SASC Workshop Record, 2007. https://www.cosic.esat.kuleuven.be/ecrypt/stream/papersdir/2007/020.pdf. Google Scholar

[11] Courtois N T, Meier W. Algebraic attacks on stream ciphers with linear feedback. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2003. 345--359. Google Scholar

[12] Robshaw M, Matsumoto M, Saito M, et al. New Stream Cipher Designs: the eSTREAM Finalists. Berlin: Springer, 2008. Google Scholar

[13] Hell M, Johansson T, Maximov A. The grain family of stream ciphers. Lect Notes Comput Sci, 2008, 4986: 179--190. Google Scholar

[14] Babbage S, Dodd M. The MICKEY Stream Ciphers. Berlin: Springer, 2008. Google Scholar

[15] Maximov A. Cryptanalysis of the “Grain family of stream ciphers. In: Proceedings of the 2006 ACM Symposium on Information, Computer and Communications Security, Taipei, 2006. 283--288. Google Scholar

[16] Berbain C, Gilbert H, Joux A. Algebraic and correlation attacks against linearly filtered non linear feedback shift registers. In: Proceedings of the 15th International Workshop on Selected Areas in Cryptography, Sackville, 2008. 184--198. Google Scholar

[17] Hu H G, Gong G. Periods on two kinds of nonlinear feedback shift registers with time varying feedback functions. Int J Found Comput Sci, 2011, 22: 1317--1329. Google Scholar

[18] Cheng D Z, Qi H S, Li Z Q. Analysis and Control of Boolean Networks. Berlin: Springer, 2011. Google Scholar

[19] Li H T, Zhao G D, Meng M, et al. A survey on applications of semi-tensor product method in engineering. Sci China Inf Sci, 2018, 61: 010202. Google Scholar

[20] Lu J Q, Li H T, Liu Y, et al. Survey on semi-tensor product method with its applications in logical networks and other finite-valued systems. IET Control Theory Appl, 2017, 11: 2040--2047. Google Scholar

[21] Lu J Q, Zhong J, Ho D W C, et al. On controllability of delayed Boolean control networks. SIAM J Control Optim, 2016, 54: 475--494. Google Scholar

[22] Liu Y, Chen H W, Wu B. Controllability of Boolean control networks with impulsive effects and forbidden states. Math Method Appl Sci, 2014, 37: 1--9. Google Scholar

[23] Zhu Q, Liu Y, Lu J. Observability of Boolean control networks. Sci China Inf Sci, 2018, 61: 092201 CrossRef Google Scholar

[24] Lu J Q, Zhong J, Huang C, et al. On pinning controllability of Boolean control networks. IEEE Trans Autom Control, 2016, 61: 1658--1663. Google Scholar

[25] Zhong J, Lu J Q, Liu Y, et al. Synchronization in an array of output-coupled Boolean networks with time delay. IEEE Trans Neural Netw Learn Syst, 2014, 25: 2288--2294. Google Scholar

[26] Liu Y, Li B, Lu J. Pinning Control for the Disturbance Decoupling Problem of Boolean Networks. IEEE Trans Automat Contr, 2017, 62: 6595-6601 CrossRef Google Scholar

[27] Liu Y, Sun L J, Lu J Q, et al. Feedback controller design for the synchronization of Boolean control networks. IEEE Trans Neural Netw Learn Syst, 2016, 27: 1991--1996. Google Scholar

[28] Li F F, Sun J T. Controllability of Boolean control networks with time delays in states. Automatica, 2011, 47: 603--607. Google Scholar

[29] Cheng D Z, Qi H S. Controllability and observability of Boolean control networks. Automatica, 2009, 45: 1659--1667. Google Scholar

[30] Laschov D, Margaliot M. Controllability of Boolean control networks via the perron-frobenius theory. Automatica, 2012, 48: 1218--1223. Google Scholar

[31] Li H T, Wang Y Z, Xie L H. Output tracking control of Boolean control networks via state feedback: constant reference signal case. Automatica, 2015, 59: 54--59. Google Scholar

[32] Cheng D Z, Qi H S, Li Z Q, et al. Stability and stabilization of Boolean networks. Int J Robust Nonlinear Control, 2011, 21: 134--156. Google Scholar

[33] Li H T, Wang Y Z. Controllability analysis and control design for switched Boolean networks with state and input constraints. SIAM J Control Optim, 2015, 53: 2955--2979. Google Scholar

[34] Zhong J, Lu J Q, Huang T W, et al. Controllability and synchronization analysis of identical-hierarchy mixed-valued logical control networks. IEEE Trans Cybern, 2017, 47: 3482--3493. Google Scholar

[35] Guo P L, Wang Y Z, Li H T. A semi-tensor product approach to finding Nash equilibria for static games. In: Proceedings of the 32nd Chinese Control Conference (CCC), Xian, 2013. 107--112. Google Scholar

[36] Li H T, Xie L H, Wang Y Z. On robust control invariance of Boolean control networks. Automatica, 2016, 68: 392--396. Google Scholar

[37] Zhong J H, Lin D D. A new linearization method for nonlinear feedback shift registers. J Comput Syst Sci, 2014, 81: 783--796. Google Scholar

[38] Zhong J H, Lin D D. Stability of nonlinear feedback shift registers. Sci China Inf Sci, 2016, 59: 012204. Google Scholar

[39] Zhong J H, Lin D D. Driven stability of nonlinear feedback shift registers with inputs. IEEE Trans Commun, 2016, 64: 2274--2284. Google Scholar

[40] Zhong J, Ho D W C, Lu J Q, et al. Global robust stability and stabilization of Boolean network with disturbances. Automatica, 2017, 84: 142--148. Google Scholar

[41] Liu Y, Cao J D, Sun L J, et al. Sampled-data state feedback stabilization of Boolean control networks. Neural Comput, 2016, 28: 778--799. Google Scholar

[42] Wu H J, Huang T, Nguyen P H, et al. Differential attacks against stream cipher ZUC. In: Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, 2012. 262--277. Google Scholar

[43] Lai X J. Condition for the nonsingularity of a feedback shift-register over a general finite field (corresp.). IEEE Trans Inf Theory, 1987, 33: 747--749. Google Scholar

[44] Wang Q Y, Jin C H. Criteria for nonsingularity of Grain-like cascade feedback shift register (in Chinese). Comput Eng, 2014, 40: 519--523. Google Scholar

[45] Girard J Y. Linear logic. Theor Comput Sci, 1987, 50: 1--101. Google Scholar

[46] Liu Z B, Wang Y Z, Cheng D Z. Nonsingularity of feedback shift registers. Automatica, 2015, 55: 247--253. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1