On observability of Galois nonlinear feedback shift registers over finite fields

Zhe GAO; Jun'e FENG; Yongyuan YU; Yanjun CUI

doi:10.1631/FITEE.2200228

Your Location：

Home >

Browse articles >

On observability of Galois nonlinear feedback shift registers over finite fields

Regular Papers | Updated：2022-10-28

- On observability of Galois nonlinear feedback shift registers over finite fields
- 有限域上Galois型非线性移位寄存器的能观性
- Frontiers of Information Technology & Electronic Engineering Vol. 23, Issue 10, Pages: 1533-1545(2022)
- Affiliations：
  
  1.School of Mathematics, Shandong University, Jinan 250100, China
  2.Department of Computer Science & Engineering, University of Minnesota Twin Cities, Minneapolis, MN 55455, USA
- Author bio：
  
  E-mail: gaoz_0202@163.com
  ‡Corresponding author
  yyyu@sdu.edu.cn
  cui00022@umn.edu
- Funds：
- DOI：10.1631/FITEE.2200228
  CLC： O23
- Received：24 May 2022，
  
  Revised：2022-09-07，
  
  Accepted：17 August 2022，
  
  Published Online：28 September 2022，
  
  Published：0 October 2022
- Accepted：
Scan QR Code
Zhe GAO, Jun'e FENG, Yongyuan YU, et al. On observability of Galois nonlinear feedback shift registers over finite fields[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(10): 1533-1545.
DOI：

Zhe GAO, Jun'e FENG, Yongyuan YU, et al. On observability of Galois nonlinear feedback shift registers over finite fields[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(10): 1533-1545. DOI： 10.1631/FITEE.2200228.

摘要

能观性可以确保任何两个不同初始状态都可以由它们的输出序列唯一确定，因此流密码必须避免不可观的非线性反馈移位寄存器，以防止等效密钥的出现。本文讨论了有限域上Galois型非线性反馈移位寄存器的能观性。通过半张量积，Galois型非线性反馈移位寄存器可被视为逻辑网络。本文介绍了状态转移矩阵的向量形式，据此提出一个充分必要条件以及判定一般Galois型非线性反馈移位寄存器能观性的算法。此外，本文定义了一个新的能观性矩阵，通过该矩阵可推导出计算复杂度较低的矩阵方法。此外，研究两种特殊类型的Galois型非线性反馈移位寄存器的能观性：全长Galois型非线性反馈移位寄存器和非奇异Galois型非线性反馈移位寄存器。提出两种方法确定这两种特殊类型的非线性反馈移位寄存器的能观性，并提供一些数值示例支持这些结果。

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.

关键词

Keywords

references

JP Aumasson , , I Dinur , , W Meier , , et al. , . 2009 . . Cube testers and key recovery attacks on reduced-round MD6 and Trivium . . Int Workshop on Fast Software Encryption , p. . 1 - - 22 . . https://doi.org/10.1007/978-3-642-03317-9_1 https://doi.org/10.1007/978-3-642-03317-9_1 , .

DZ Cheng , , HS Qi , , ZQ Li , . 2011 . . Analysis and Control of Boolean Networks: a Semi-tensor Product Approach . , : Springer London . https://doi.org/10.1007/978-0-85729-097-7 https://doi.org/10.1007/978-0-85729-097-7 , .

DZ Cheng , , HS Qi , , Y Zhao , . 2012 . . An Introduction to Semi Tensor Product of Matrices and Its Applications . , : Hackensack : World Scientific . , https://doi.org/10.1142/8323 https://doi.org/10.1142/8323 , .

PP Deepthi , , PS Sathidevi , . 2009 . . Design, implementation and analysis of hardware efficient stream ciphers using LFSR based hash functions . . Comput Secur , , 28 ( ( 3-4 ): ): 229 - - 241 . . https://doi.org/10.1016/j.cose.2008.11.006 https://doi.org/10.1016/j.cose.2008.11.006 , .

E Dubrova , . 2009 . . A transformation from the Fibonacci to the Galois NLFSRs . . IEEE Trans Inform Theory , , 55 ( ( 11 ): ): 5263 - - 5271 . . https://doi.org/10.1109/TIT.2009.2030467 https://doi.org/10.1109/TIT.2009.2030467 , .

E Dubrova , . 2010 . . Finding matching initial states for equivalent NLFSRs in the Fibonacci and the Galois configurations . . IEEE Trans Inform Theory , , 56 ( ( 6 ): ): 2961 - - 2966 . . https://doi.org/10.1109/TIT.2010.2046250 https://doi.org/10.1109/TIT.2010.2046250 , .

E Fornasini , , ME Valcher , . 2013 . . Observability, reconstructibility and state observers of Boolean control networks . . IEEE Trans Autom Contr , , 58 ( ( 6 ): ): 1390 - - 1401 . . https://doi.org/10.1109/TAC.2012.2231592 https://doi.org/10.1109/TAC.2012.2231592 , .

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

S Hellebrand , , J Rajski , , S Tarnick , , 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 . . https://doi.org/10.1109/12.364534 https://doi.org/10.1109/12.364534 , .

C Huang , , DWC Ho , , JQ Lu , , et al. , . 2022 . . Synchronization of an array of coupled probabilistic Boolean networks . . IEEE Trans Syst Man Cybern Syst , , 52 ( ( 6 ): ): 3834 - - 3846 . . https://doi.org/10.1109/TSMC.2021.3073201 https://doi.org/10.1109/TSMC.2021.3073201 , .

WH Kong , , JH Zhong , , DD Lin , . 2022 . . Observability of Galois nonlinear feedback shift registers . . Sci China Inform Sci , , 65 ( ( 9 ): ): 192206 . https://doi.org/10.1007/s11432-021-3346-6 https://doi.org/10.1007/s11432-021-3346-6 , .

XJ Lai , . 1987 . . Condition for the nonsingularity of a feedback shift-register over a general finite field (Corresp.) . . IEEE Trans Inform Theory , , 33 ( ( 5 ): ): 747 - - 749 . . https://doi.org/10.1109/TIT.1987.1057338 https://doi.org/10.1109/TIT.1987.1057338 , .

R Li , , M Yang , , TG Chu , . 2014 . . Observability conditions of Boolean control networks . . Int J Robust Nonl Contr , , 24 ( ( 17 ): ): 2711 - - 2723 . . https://doi.org/10.1002/rnc.3019 https://doi.org/10.1002/rnc.3019 , .

YF Li , , JD Zhu , . 2020 . . Cascading decomposition of Boolean control networks: a graph-theoretical method . . Front Inform Technol Electron Eng , , 21 ( ( 2 ): ): 304 - - 315 . . https://doi.org/10.1631/FITEE.1900422 https://doi.org/10.1631/FITEE.1900422 , .

K Limniotis , , N Kolokotronis , , N Kalouptsidis , . 2006 . . New results on the linear complexity of binary sequences . . Proc IEEE Int Symp on Information Theory , p. . 2003 - - 2007 . . https://doi.org/10.1109/ISIT.2006.261900 https://doi.org/10.1109/ISIT.2006.261900 , .

K Limniotis , , N Kolokotronis , , N Kalouptsidis , . 2008 . . On the linear complexity of sequences obtained by state space generators . . IEEE Trans Inform Theory , , 54 ( ( 4 ): ): 1786 - - 1793 . . https://doi.org/10.1109/TIT.2008.917639 https://doi.org/10.1109/TIT.2008.917639 , .

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

JQ Lu , , ML Li , , Y Liu , , et al. , . 2018a . . Nonsingularity of Grain-like cascade FSRs via semi-tensor product . . Sci China Inform Sci , , 61 ( ( 1 ): ): 010204 . https://doi.org/10.1007/s11432-017-9269-6 https://doi.org/10.1007/s11432-017-9269-6 , .

JQ Lu , , ML Li , , TW Huang , , et al. , . 2018b . . The transformation between the Galois NLFSRs and the Fibonacci NLFSRs via semi-tensor product of matrices . . Automatica , , 96 : 393 - - 397 . . https://doi.org/10.1016/j.automatica.2018.07.011 https://doi.org/10.1016/j.automatica.2018.07.011 , .

JQ Lu , , BW Li , , J Zhong , . 2021 . . A novel synthesis method for reliable feedback shift registers via Boolean networks . . Sci China Inform Sci , , 64 ( ( 5 ): ): 152207 . https://doi.org/10.1007/s11432-020-2981-4 https://doi.org/10.1007/s11432-020-2981-4 , .

J Massey , . 1969 . . Shift-register synthesis and BCH decoding . . IEEE Trans Inform Theory , , 15 ( ( 1 ): ): 122 - - 127 . . https://doi.org/10.1109/TIT.1969.1054260 https://doi.org/10.1109/TIT.1969.1054260 , .

W Meier , , O Staffelbach , . 1989 . . Fast correlation attacks on certain stream ciphers . . J Cryptol , , 1 ( ( 3 ): ): 159 - - 176 . . https://doi.org/10.1007/BF02252874 https://doi.org/10.1007/BF02252874 , .

AH Roger , , CR Johnson , . 1991 . . Topics in Matrix Analysis . , Cambridge University Press . , https://doi.org/10.1017/CBO9780511840371 https://doi.org/10.1017/CBO9780511840371 , .

YW Shen , , YQ Guo , , WH Gui , . 2021 . . Stability of Boolean networks with state-dependent random impulses . . Front Inform Technol Electron Eng , , 22 ( ( 2 ): ): 222 - - 231 . . https://doi.org/10.1631/FITEE.1900454 https://doi.org/10.1631/FITEE.1900454 , .

B Wang , , JE Feng , . 2019 . . On detectability of probabilistic Boolean networks . . Inform Sci , , 483 : 383 - - 395 . . https://doi.org/10.1016/j.ins.2019.01.055 https://doi.org/10.1016/j.ins.2019.01.055 , .

HY Wang , , JH Zhong , , DD Lin , . 2017 . . Linearization of multi-valued nonlinear feedback shift registers . . J Syst Sci Complexity , , 30 ( ( 2 ): ): 494 - - 509 . . https://doi.org/10.1007/s11424-016-5156-7 https://doi.org/10.1007/s11424-016-5156-7 , .

QY Wang , , CH Jin , . 2013 . . Nonsingularity decision of Trivium-like cascade connection of feedback shift registers . . J Inform Eng Univ , , 14 ( ( 5 ): ): 519 - - 523 ( . in Chinese ). https://doi.org/10.3969/j.issn.1671-0673.2013.05.002 https://doi.org/10.3969/j.issn.1671-0673.2013.05.002 , .

XJ Wang , , T Tian , , WF Qi , . 2022 . . A necessary and sufficient condition for a class of nonsingular Galois NFSRs . . Finit Fields Their Appl , , 77 : 101952 . https://doi.org/10.1016/j.ffa.2021.101952 https://doi.org/10.1016/j.ffa.2021.101952 , .

YY Yu , , M Meng , , JE Feng , , et al. , . 2021 . . Observability criteria for Boolean networks . . IEEE Trans Autom Contr , , early access . https://doi.org/10.1109/TAC.2021.3131436 https://doi.org/10.1109/TAC.2021.3131436 , .

QL Zhang , , B Wang , , JE Feng , . 2021 . . Solution and stability of continuous-time cross-dimensional linear systems . . Front Inform Technol Electron Eng , , 22 ( ( 2 ): ): 210 - - 221 . . https://doi.org/10.1631/FITEE.1900504 https://doi.org/10.1631/FITEE.1900504 , .

XY Zhao , , B Wang , , YY Yan , , et al. , . 2021 . . The equivalence transformation between Galois NFSRs and Fibonacci NFSRs . . Asian J Contr , , 23 ( ( 6 ): ): 2865 - - 2873 . . https://doi.org/10.1002/asjc.2390 https://doi.org/10.1002/asjc.2390 , .

YT Zheng , , JE Feng , . 2020 . . Output tracking of delayed logical control networks with multi-constraint . . Front Inform Technol Electron Eng , , 21 ( ( 2 ): ): 316 - - 323 . . https://doi.org/10.1631/FITEE.1900376 https://doi.org/10.1631/FITEE.1900376 , .

J Zhong , , BW Li , , Y Liu , , et al. , . 2020 . . Output feedback stabilizer design of Boolean networks based on network structure . . Front Inform Technol Electron Eng , , 21 ( ( 2 ): ): 247 - - 259 . . https://doi.org/10.1631/FITEE.1900229 https://doi.org/10.1631/FITEE.1900229 , .

JH Zhong , , DD Lin , . 2015 . . A new linearization method for nonlinear feedback shift registers . . J Comput Syst Sci , , 81 ( ( 4 ): ): 783 - - 796 . . https://doi.org/10.1016/j.jcss.2014.12.030 https://doi.org/10.1016/j.jcss.2014.12.030 , .

JH Zhong , , DD Lin , . 2016a . . Driven stability of nonlinear feedback shift registers with inputs . . IEEE Trans Commun , , 64 ( ( 6 ): ): 2274 - - 2284 . . https://doi.org/10.1109/TCOMM.2016.2557330 https://doi.org/10.1109/TCOMM.2016.2557330 , .

JH Zhong , , DD Lin , . 2016b . . Stability of nonlinear feedback shift registers . . Sci China Inform Sci , , 59 ( ( 1 ): ): 1 - - 12 . . https://doi.org/10.1007/s11432-015-5311-0 https://doi.org/10.1007/s11432-015-5311-0 , .

JH Zhong , , DD Lin , . 2018 . . On minimum period of nonlinear feedback shift registers in Grain-like structure . . IEEE Trans Inform Theory , , 64 ( ( 9 ): ): 6429 - - 6442 . . https://doi.org/10.1109/TIT.2018.2849392 https://doi.org/10.1109/TIT.2018.2849392 , .

JH Zhong , , DD Lin , . 2019a . . Decomposition of nonlinear feedback shift registers based on Boolean networks . . Sci China Inform Sci , , 62 ( ( 3 ): ): 39110 . https://doi.org/10.1007/s11432-017-9460-4 https://doi.org/10.1007/s11432-017-9460-4 , .

JH Zhong , , DD Lin , . 2019b . . On equivalence of cascade connections of two nonlinear feedback shift registers . . Comput J , , 62 ( ( 12 ): ): 1793 - - 1804 . . https://doi.org/10.1093/comjnl/bxz057 https://doi.org/10.1093/comjnl/bxz057 , .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Analysis of the Pareto equilibrium in multi-objective games using semi-tensor product

A joint image compression and encryption scheme based on a novel coupled map lattice system and DNA operations

State space optimization of finite state machines from the viewpoint of control theory

Output tracking of delayed logical control networks with multi-constraint

Cascading decomposition of Boolean control networks: a graph-theoretical method

Related Author

Jun'e FENG

Fanyueyang ZHANG

Jungang LOU

Jianquan LU

Xiaoqing YOU

Yuanyuan LI

Jumei YUE

Yongyi YAN

Related Institution

School of Computer Science and Technology, Zhejiang Normal University

Yangtze Delta Region (Huzhou) Institute of Intelligent Transportation, Huzhou University

Department of Systems Science, School of Mathematics, Southeast University

School of Cyber Science and Engineering, Southeast University

Department of Applied Mathematics, College of Science, Nanjing Forestry University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰