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.

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

School of Mathematics,Shandong University,Jinan 250100,China;Department of Computer Science&Engineering,University of Minnesota Twin Cities,Minneapolis,MN 55455,USA

信息与电子工程前沿（英文）

[1]Zhe GAO;Jun'e FENG;Yongyuan YU;Yanjun CUI-.On observability of Galois nonlinear feedback shift registers over finite fields)[J].信息与电子工程前沿（英文）,2022(10):1533-1545

Observability,NFSRs,NFSR

On,observability,Galois,nonlinear,feedback,shift,registers,finite,fields,ensures,that,any,distinct,initial,states,can,be,uniquely,determined,by,their,outputs,stream,ciphers,avoid,unobservable,prevent,occurrence,equivalent,keys,This,paper,discusses,are,treated,as,logical,networks,using,semi,tensor,product,vector,form,transition,matrix,introduced,which,necessary,sufficient,condition,proposed,well,algorithm,determining,general,Moreover,new,defined,derive,lower,computation,complexity,Furthermore,special,types,full,length,nonsingular,investigated,Two,methods,these,some,numerical,examples,provided,support,results

0.503499