On the Cycle Structure of Some Nonlinear Feedback Shift Registers

WANG Zhongxiao; XU Hong; QI Wenfeng

Article Contents

Article Navigation > Chinese Journal of Electronics > 2014 > 23(4): 801-804

WANG Zhongxiao, XU Hong, QI Wenfeng, “On the Cycle Structure of Some Nonlinear Feedback Shift Registers,” Chinese Journal of Electronics, vol. 23, no. 4, pp. 801-804, 2014,

Citation:

WANG Zhongxiao, XU Hong, QI Wenfeng, “On the Cycle Structure of Some Nonlinear Feedback Shift Registers,” Chinese Journal of Electronics, vol. 23, no. 4, pp. 801-804, 2014,

WANG Zhongxiao, XU Hong, QI Wenfeng, “On the Cycle Structure of Some Nonlinear Feedback Shift Registers,” Chinese Journal of Electronics, vol. 23, no. 4, pp. 801-804, 2014,

Citation:

WANG Zhongxiao, XU Hong, QI Wenfeng, “On the Cycle Structure of Some Nonlinear Feedback Shift Registers,” Chinese Journal of Electronics, vol. 23, no. 4, pp. 801-804, 2014,

PDF( 725 KB)

On the Cycle Structure of Some Nonlinear Feedback Shift Registers

1.
State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou Information Science and Technology Institute, Zhengzhou 450002, China;
2.
Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61272042, No.61100202, No.61170235, No.61100200) and China Postdoctoral Science Foundation (No.2013M531174).

Received Date: 2013-04-01
Rev Recd Date: 2013-10-01
Publish Date: 2014-10-05

Abstract

Abstract

In this paper, we partly determine the cycle structure of two types of Nonlinear feedback shift registers (NFSRs). Based on these results, the cycle structure of a class of NFSRs with symmetric feedback functions can be completely characterized. Furthermore, an alternative proof of Kjeldsen's results is presented. Compared with the original proof based on abstract algebra theory, ours is straightforward and easy to understand.
- Cryptography,
- Stream ciphers,
- Nonlinear feedback shift registers,
- Symmetric functions

FullText(HTML)

References(16)

References

W. Meier, O. Staffelbach, Fast correlation attacks on certain stream ciphers", J. Crypt., Vol.1, No.3, pp.159-176, 1989.

A. Canteaut, M. Trabbia, Improved fast correlation attacks using parity-check equations of weight 4 and 5", EUROCRYPT 2000, Bruges, Belgium, pp.573-588, 2000.

N. Courtois, W. Meier, Algebraic attacks on stream ciphers with linear feedback", EUROCRYPT 2003, Warsaw, Poland, pp.346-359, 2003.

N. Courtois, Fast algebraic attacks on stream ciphers with linear feedback", CRYPTO 2003, Santa Barbara, California, USA, pp.176-194, 2003.

L. Jiao, M. Wang, Y. Li et al., On annihilators in fewer variables: Basic theory and applications", Chinese Journal of Electronics, Vol.22, No.3, pp.489-494, 2013.

M. Hell, T. Johansson, The Grain family of stream ciphers", LNCS, Springer-Verlag, Berlin, Germany, Vol.4986, pp.179-190, 2008.

S. Baggage, M. Dodd, The MICKEY stream ciphers", LNCS, Springer-Verlag, Berlin, Germany, Vol.4986, pp.191-209, 2008.

C. de Canniére, B. Preneel, Trivium", of LNCS, Springer-Verlag, Berlin, Germany, Vol.4986, pp.244-266, 2008.

K. Kjeldsen, On the cycle structure of a set of nonlinear shift registers with symmetric feedback functions", J. Combinatorial Theory, Vol.A, No.20, pp.154-169, 1976.

J. Soreng, The periods of the sequences generated by some symmetric shift registers", J. Combinatorial Theory, Vol.A, No.21, pp.164-187, 1976.

J. Soreng, Symmetric shift registers", Pacific J. Math., Vol.85, No.1, pp.201-229, 1979.

E. A. Walker, Non-linear recursive sequences", Canadian J. Math., Vol.11, No.3, pp.370-378, 1959.

H. Hu, G. Gong, Periods on two kinds of nonlinear feedback shift registers with time varying feedback functions", Int. J. Found. Comput. Sci., Vol.22, No.6, pp.1317-1329, 2011.

S. Golomb, Shift Register Sequences, Aegean Park Press, New York, USA, 1982.

G. Birkhoff, S. Maclane, A Survey of Modern Algebra, Macmillan, New York, USA, 1962.

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, USA, 1968.

Relative Articles

Supplements(0)

Cited By

Proportional views