NDLI: On the largest affine sub-families of a family of NFSR sequences

Content Provider	Springer Nature Link
Author	Qi, Wen Feng Tian, Tian
Copyright Year	2012
Abstract	Recently nonlinear feedback shift registers (NFSRs) have frequently been used as building blocks for designing stream ciphers. Let NFSR (g) be an m-stage NFSR with characteristic function $${g=x_{0}\oplus g_{1}(x_{1},\cdots ,x_{m-1})\oplus x_{m}}$$ . Up to now there has been no known method to determine whether the family of output sequences of the NFSR (g), denoted by S(g), contains a sub-family of sequences that are exactly the output sequences of an NFSR(f) of stage n < m. This paper studies affine cases, that is, finding an affine function f such that S(f) is a subset of S(g). If S(g) contains an affine sub-family S(f) whose order n is close to m, then a large number of sequences generated by the NFSR (g) have low linear complexities. First, we give two methods to bound the maximal order of affine sub-families included in S(g). Experimental data indicate that if S(g) contains an affine sub-family of order not smaller than m/2, then the upper bound given in the paper is tight. Second, we propose two algorithms to solve affine sub-families of a given order n included in S(g), both of which aim at affine sub-families with the maximal order. Algorithm 1 is applicable when n is close to m, while the feasibility of Algorithm 2 relies on the distribution of nonlinear terms of g. In particular, if Algorithm 2 works, then its computation complexity is less than that of Algorithm 1 and it is quite efficient for a number of cases.
Ending Page	181
Page Count	19
Starting Page	163
File Format	PDF
ISSN	09251022
e-ISSN	15737586
Journal	Designs, Codes and Cryptography
Issue Number	1
Volume Number	71
Language	English
Publisher	Springer US
Publisher Date	2012-07-15
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Information and Communication, Circuits Data Structures, Cryptology and Information Theory Stream ciphers Discrete Mathematics in Computer Science Nonlinear feedback shift registers Data Encryption Families of NFSR sequences Shift register sequences and sequences over finite alphabets Coding and Information Theory Cryptography Combinatorics
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Discrete Mathematics and Combinatorics Theoretical Computer Science Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On affine sub-families of the NFSR in Grain

On the nonlinearity of maximum-length NFSR feedbacks

On affine sub-families of Grain-like structures

The adjacency graphs of some feedback shift registers

Linearity properties of binary FCSR sequences

Expected values for the rational complexity of finite binary sequences

On the distinctness of modular reductions of primitive sequences over Z/(232−1)

A note on the crosscorrelation of maximal length FCSR sequences

Asymptotic analysis on the normalized k-error linear complexity of binary sequences

On the largest affine sub-families of a family of NFSR sequences

Similar Documents

On affine sub-families of the NFSR in Grain

On the nonlinearity of maximum-length NFSR feedbacks

On affine sub-families of Grain-like structures

The adjacency graphs of some feedback shift registers

Linearity properties of binary FCSR sequences

Expected values for the rational complexity of finite binary sequences

On the distinctness of modular reductions of primitive sequences over Z/(232−1)

A note on the crosscorrelation of maximal length FCSR sequences

Asymptotic analysis on the normalized k-error linear complexity of binary sequences

On the largest affine sub-families of a family of NFSR sequences