# zbMATH — the first resource for mathematics

Practical construction of ring LFSRs and ring FCSRs with low diffusion delay for hardware cryptographic applications. (English) Zbl 1362.14028
The article proposes a method for building LFSR (Linear Feedback Shift Register) and FCSR (Feedback with Carry Shift Register) used in cryptographic applications, with higher performance criteria. The authors use a small generalized definition – Ring LFSR and Ring FCSR – and improve the diffusion delay (that is the diameter of the digraph which defines the shift register), from exactly $$n-1$$ in [F. Arnault et al., Cryptogr. Commun. 3, No. 2, 109–139 (2011; Zbl 1251.94019)], to maximum $$\lceil\sqrt{n}\rceil+6$$, where $$n$$ is the size (number of flip-flops) of these registers. The construction of the presented FCSR Ring can resist – using an adequate nonlinear choice of the feedback function – to the usual attack against stream ciphers (LFSRization).
Section 3.3 presents some interesting examples for improving the stream ciphers F-FCSR-H v3 (diffusion delay is reduced from 27 to 16) and F-FCSR-16 v3 (diffusion delay reduced from 27 to 19) respectively.

##### MSC:
 14G50 Applications to coding theory and cryptography of arithmetic geometry 94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
##### Keywords:
stream cipher; LFSR; FCSR; m-sequences; l-sequences
X-FCSR
Full Text:
##### References:
 [1] Arnault, F., Berger, T.P.: F-FCSR: design of a new class of stream ciphers. In: Gilbert, H., Handschuh, H. (eds.) FSE. Lecture Notes in Computer Science, vol. 3557, pp. 83-97. Springer, New York (2005) · Zbl 1140.68381 [2] Arnault, F; Berger, TP; Benjamin, P, A matrix approach for FCSR automata, Cryptogr. Commun., 3, 109-139, (2010) · Zbl 1251.94019 [3] Arnault, F., Berger, T.P., Lauradoux, C.: Update on F-FCSR Stream Cipher. ECRYPT-Network of Excellence in Cryptology (Call for stream Cipher Primitives-Phase 2 2006) (2006). [http://www.ecrypt.eu.org/stream/] · Zbl 0515.94027 [4] Arnault, F., Berger, T.P., Lauradoux, C., Minier, M., Pousse, B.: A new approach for FCSRs. In: M.J.J. Jr., Rijmen, V., Safavi-Naini, R. (eds.) Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 5867, pp 433-448. Springer, New York (2009) · Zbl 1267.94032 [5] Arnault, F; Berger, TP; Minier, M; Pousse, B, Revisiting LFSRs for cryptographic applications, IEEE Trans. Inf. Theory, 57, 8095-8113, (2011) · Zbl 1365.94369 [6] Berger, T.P., Minier, M., Pousse, B.: Software oriented stream ciphers based upon FCSRs in diversified mode. In: Roy, B.K., Sendrier, N. (eds.) INDOCRYPT. Lecture Notes in Computer Science, vol. 5922, pp 119-135. Springer, New York (2009) · Zbl 1252.94048 [7] Flajolet, P., Odlyzko, A.M.: Random mapping statistics. Advances in cryptologyEUROCRYPT’89, pp 329-354. Springer, Berlin (1990) · Zbl 0747.05006 [8] Goresky, M; Klapper, A, Arithmetic crosscorrelations of feedback with carry shift register sequences, IEEE Trans. Inf. Theory, 43, 1342-1345, (1997) · Zbl 0878.94047 [9] Goresky, M; Klapper, A, Fibonacci and Galois representations of feedback-with-carry shift registers, IEEE Trans. Inf. Theory, 48, 2826-2836, (2002) · Zbl 1062.94028 [10] Hell, M., Johansson, T.: Breaking the F-FCSR-H Stream Cipher in Real Time. In: Pieprzyk, J. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 5350, pp 557-569. Springer, New York (2008) · Zbl 1206.94071 [11] Imase, M; Itoh, M, Design to minimize diameter on building-block network, IEEE Trans. Comput., 100, 439-442, (1981) · Zbl 0456.94030 [12] Imase, M; Itoh, M, A design for directed graphs with minimum diameter, IEEE Trans. Comput., 32, 782-784, (1983) · Zbl 0515.94027 [13] Klapper, A., Goresky, M.: 2-adic shift registers. In: Anderson, R.J. (ed.) FSE. Lecture Notes in Computer Science, vol. 809, pp 174-178. Springer, New York (1993) · Zbl 0943.94515 [14] Klapper, A., Goresky, M.: Large Period Nearly deBruijn FCSR Sequences. Advances in Cryptology-EUROCRYPT’95, pp 263-273. Springer, Berlin (1995) · Zbl 0973.94510 [15] Lin, Z; Ke, L; Lin, D; Gao, J, On the lfsrization of a class of FCSR automata, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 98, 434-440, (2015) [16] Lin, Z., Pei, D., Lin, D.: Construction of Transition Matrices for Binary FCSRs. Tech. Rep. 2015/1181. Available: http://eprint.iacr.org/ · Zbl 1391.14049 [17] Mruglaski, G; Rajski, J; Tyszer, J, Ring generators-new devices for embedded test applications. computer-aided design of integrated circuits and systems, IEEE Trans. Comput.-Aided Design, 23, 1306-1320, (2004) [18] Tian, T; Qi, WF, Linearity properties of binary FCSR sequences, Des. Codes Cryptography, 52, 249-262, (2009) · Zbl 1173.94005 [19] Wang, H; Stankovski, P; Johansson, T, A generalized birthday approach for efficiently finding linear relations in l-sequences, Des. Codes Cryptography, 74, 41-57, (2015) · Zbl 1351.94070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.