Similar articles

Abstract: observability ensures that any two distinct initial states can be uniquely determined by their outputs, so the stream ciphers can avoid unobservable nonlinear feedback shift registers (NFSRs) to prevent the occurrence of equivalent keys. This paper discusses the observability of galois NFSRs over finite fields. galois NFSRs are treated as logical networks using the semi-tensor product. The vector form of the state transition matrix is introduced, by which a necessary and sufficient condition is proposed, as well as an algorithm for determining the observability of general galois NFSRs. Moreover, a new observability matrix is defined, which can derive a matrix method with lower computation complexity. Furthermore, the observability of two special types of galois NFSRs, a full-length Galois NFSR and a nonsingular Galois NFSR, is investigated. Two methods are proposed to determine the observability of these two special types of NFSRs, and some numerical examples are provided to support these results.

有限域上Galois型非线性移位寄存器的能观性

[1]Aumasson JP, Dinur I, Meier W, et al., 2009. Cube testers and key recovery attacks on reduced-round MD6 and Trivium. Int Workshop on Fast Software Encryption, p.1-22.

[2]Cheng DZ, Qi HS, Li ZQ, 2011. Analysis and Control of Boolean Networks: a Semi-tensor Product Approach. Springer London.

[3]Cheng DZ, Qi HS, Zhao Y, 2012. An Introduction to Semi Tensor Product of Matrices and Its Applications. Hackensack: World Scientific.

[4]Deepthi PP, Sathidevi PS, 2009. Design, implementation and analysis of hardware efficient stream ciphers using LFSR based hash functions. Comput Secur, 28(3-4):229-241.

[5]Dubrova E, 2009. A transformation from the Fibonacci to the Galois NLFSRs. IEEE Trans Inform Theory, 55(11):5263-5271.

[6]Dubrova E, 2010. Finding matching initial states for equivalent NLFSRs in the Fibonacci and the Galois configurations. IEEE Trans Inform Theory, 56(6):2961-2966.

[7]Fornasini E, Valcher ME, 2013. Observability, reconstructibility and state observers of Boolean control networks. IEEE Trans Autom Contr, 58(6):1390-1401.

[8]Golomb SW, 1967. Shift Register Sequences. San Francisco: Holden-Day.

[9]Hellebrand S, Rajski J, Tarnick S, et al., 1995. Built-in test for circuits with scan based on reseeding of multiple-polynomial linear feedback shift registers. IEEE Trans Comput, 44(2):223-233.

[10]Huang C, Ho DWC, Lu JQ, et al., 2022. Synchronization of an array of coupled probabilistic Boolean networks. IEEE Trans Syst Man Cybern Syst, 52(6):3834-3846.

[11]Kong WH, Zhong JH, Lin DD, 2022. Observability of Galois nonlinear feedback shift registers. Sci China Inform Sci, 65(9):192206.

[12]Lai XJ, 1987. Condition for the nonsingularity of a feedback shift-register over a general finite field (Corresp.). IEEE Trans Inform Theory, 33(5):747-749.

[13]Li R, Yang M, Chu TG, 2014. Observability conditions of Boolean control networks. Int J Robust Nonl Contr, 24(17):2711-2723.

[14]Li YF, Zhu JD, 2020. Cascading decomposition of Boolean control networks: a graph-theoretical method. Front Inform Technol Electron Eng, 21(2):304-315.

[15]Limniotis K, Kolokotronis N, Kalouptsidis N, 2006. New results on the linear complexity of binary sequences. Proc IEEE Int Symp on Information Theory, p.2003-2007.

[16]Limniotis K, Kolokotronis N, Kalouptsidis N, 2008. On the linear complexity of sequences obtained by state space generators. IEEE Trans Inform Theory, 54(4):1786-1793.

[17]Ljung L, Sèoderstrèom T, 1983. Theory and Practice of Recursive Identification. Cambridge: MIT Press.

[18]Lu JQ, Li ML, Liu Y, et al., 2018a. Nonsingularity of Grain-like cascade FSRs via semi-tensor product. Sci China Inform Sci, 61(1):010204.

[19]Lu JQ, Li ML, Huang TW, et al., 2018b. The transformation between the Galois NLFSRs and the Fibonacci NLFSRs via semi-tensor product of matrices. Automatica, 96:393-397.

[20]Lu JQ, Li BW, Zhong J, 2021. A novel synthesis method for reliable feedback shift registers via Boolean networks. Sci China Inform Sci, 64(5):152207.

[21]Massey J, 1969. Shift-register synthesis and BCH decoding. IEEE Trans Inform Theory, 15(1):122-127.

[22]Meier W, Staffelbach O, 1989. Fast correlation attacks on certain stream ciphers. J Cryptol, 1(3):159-176.

[23]Roger AH, Johnson CR, 1991. Topics in Matrix Analysis. Cambridge University Press.

[24]Shen YW, Guo YQ, Gui WH, 2021. Stability of Boolean networks with state-dependent random impulses. Front Inform Technol Electron Eng, 22(2):222-231.

[25]Wang B, Feng JE, 2019. On detectability of probabilistic Boolean networks. Inform Sci, 483:383-395.

[26]Wang HY, Zhong JH, Lin DD, 2017. Linearization of multi-valued nonlinear feedback shift registers. J Syst Sci Complexity, 30(2):494-509.

[27]Wang QY, Jin CH, 2013. Nonsingularity decision of Trivium-like cascade connection of feedback shift registers. J Inform Eng Univ, 14(5):519-523 (in Chinese).

[28]Wang XJ, Tian T, Qi WF, 2022. A necessary and sufficient condition for a class of nonsingular Galois NFSRs. Finit Fields Their Appl, 77:101952.

[29]Yu YY, Meng M, Feng JE, et al., 2021. Observability criteria for Boolean networks. IEEE Trans Autom Contr, early access.

[30]Zhang QL, Wang B, Feng JE, 2021. Solution and stability of continuous-time cross-dimensional linear systems. Front Inform Technol Electron Eng, 22(2):210-221.

[31]Zhao XY, Wang B, Yan YY, et al., 2021. The equivalence transformation between Galois NFSRs and Fibonacci NFSRs. Asian J Contr, 23(6):2865-2873.

[32]Zheng YT, Feng JE, 2020. Output tracking of delayed logical control networks with multi-constraint. Front Inform Technol Electron Eng, 21(2):316-323.

[33]Zhong J, Li BW, Liu Y, et al., 2020. Output feedback stabilizer design of Boolean networks based on network structure. Front Inform Technol Electron Eng, 21(2):247-259.

[34]Zhong JH, Lin DD, 2015. A new linearization method for nonlinear feedback shift registers. J Comput Syst Sci, 81(4):783-796.

[35]Zhong JH, Lin DD, 2016a. Driven stability of nonlinear feedback shift registers with inputs. IEEE Trans Commun, 64(6):2274-2284.

[36]Zhong JH, Lin DD, 2016b. Stability of nonlinear feedback shift registers. Sci China Inform Sci, 59(1):1-12.

[37]Zhong JH, Lin DD, 2018. On minimum period of nonlinear feedback shift registers in Grain-like structure. IEEE Trans Inform Theory, 64(9):6429-6442.

[38]Zhong JH, Lin DD, 2019a. Decomposition of nonlinear feedback shift registers based on Boolean networks. Sci China Inform Sci, 62(3):39110.

[39]Zhong JH, Lin DD, 2019b. On equivalence of cascade connections of two nonlinear feedback shift registers. Comput J, 62(12):1793-1804.