CLC number: O23
On-line Access: 2022-10-24
Received: 2022-05-24
Revision Accepted: 2022-10-24
Crosschecked: 2022-08-17
Cited: 0
Clicked: 1381
Citations: Bibtex RefMan EndNote GB/T7714
Zhe GAO, Jun'e FENG, Yongyuan YU, Yanjun CUI. On observability of Galois nonlinear feedback shift registers over finite fields[J]. Frontiers of Information Technology & Electronic Engineering,in press.https://doi.org/10.1631/FITEE.2200228 @article{title="On observability of Galois nonlinear feedback shift registers over finite fields", %0 Journal Article TY - JOUR
有限域上Galois型非线性移位寄存器的能观性1山东大学数学学院,中国济南市,250100 2明尼苏达大学双城分校计算机科学与工程系,美国明尼苏达州,55455 摘要:能观性可以确保任何两个不同初始状态都可以由它们的输出序列唯一确定,因此流密码必须避免不可观的非线性反馈移位寄存器,以防止等效密钥的出现。本文讨论了有限域上Galois型非线性反馈移位寄存器的能观性。通过半张量积,Galois型非线性反馈移位寄存器可被视为逻辑网络。本文介绍了状态转移矩阵的向量形式,据此提出一个充分必要条件以及判定一般Galois型非线性反馈移位寄存器能观性的算法。此外,本文定义了一个新的能观性矩阵,通过该矩阵可推导出计算复杂度较低的矩阵方法。此外,研究两种特殊类型的Galois型非线性反馈移位寄存器的能观性:全长Galois型非线性反馈移位寄存器和非奇异Galois型非线性反馈移位寄存器。提出两种方法确定这两种特殊类型的非线性反馈移位寄存器的能观性,并提供一些数值示例支持这些结果。 关键词组: Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article
Reference[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. Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou
310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE |
Open peer comments: Debate/Discuss/Question/Opinion
<1>