Full Text:   <110>

Summary:  <10>

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: 158

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Jun-e Feng

https://orcid.org/0000-0003-3881-3042

Zhe GAO

https://orcid.org/0000-0002-9464-977X

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2022 Vol.23 No.10 P.1533-1545

http://doi.org/10.1631/FITEE.2200228


On observability of Galois nonlinear feedback shift registers over finite fields


Author(s):  Zhe GAO, Jun'e FENG, Yongyuan YU, Yanjun CUI

Affiliation(s):  School of Mathematics, Shandong University, Jinan 250100, China; more

Corresponding email(s):   gaoz_0202@163.com, fengjune@sdu.edu.cn, yyyu@sdu.edu.cn, cui00022@umn.edu

Key Words:  Observability, Nonlinear feedback shift registers (NFSRs), Galois NFSRs, Semi-tensor product, Finite fields, Logical networks


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, 2022, 23(10): 1533-1545.

@article{title="On observability of Galois nonlinear feedback shift registers over finite fields",
author="Zhe GAO, Jun'e FENG, Yongyuan YU, Yanjun CUI",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="23",
number="10",
pages="1533-1545",
year="2022",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2200228"
}

%0 Journal Article
%T On observability of Galois nonlinear feedback shift registers over finite fields
%A Zhe GAO
%A Jun'e FENG
%A Yongyuan YU
%A Yanjun CUI
%J Frontiers of Information Technology & Electronic Engineering
%V 23
%N 10
%P 1533-1545
%@ 2095-9184
%D 2022
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2200228

TY - JOUR
T1 - On observability of Galois nonlinear feedback shift registers over finite fields
A1 - Zhe GAO
A1 - Jun'e FENG
A1 - Yongyuan YU
A1 - Yanjun CUI
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 23
IS - 10
SP - 1533
EP - 1545
%@ 2095-9184
Y1 - 2022
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2200228


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,冯俊娥1,于永渊1,崔彦君2
1山东大学数学学院,中国济南市,250100
2明尼苏达大学双城分校计算机科学与工程系,美国明尼苏达州,55455
摘要:能观性可以确保任何两个不同初始状态都可以由它们的输出序列唯一确定,因此流密码必须避免不可观的非线性反馈移位寄存器,以防止等效密钥的出现。本文讨论了有限域上Galois型非线性反馈移位寄存器的能观性。通过半张量积,Galois型非线性反馈移位寄存器可被视为逻辑网络。本文介绍了状态转移矩阵的向量形式,据此提出一个充分必要条件以及判定一般Galois型非线性反馈移位寄存器能观性的算法。此外,本文定义了一个新的能观性矩阵,通过该矩阵可推导出计算复杂度较低的矩阵方法。此外,研究两种特殊类型的Galois型非线性反馈移位寄存器的能观性:全长Galois型非线性反馈移位寄存器和非奇异Galois型非线性反馈移位寄存器。提出两种方法确定这两种特殊类型的非线性反馈移位寄存器的能观性,并提供一些数值示例支持这些结果。

关键词:能观性;非线性反馈移位寄存器(NFSRs);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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE