zbMATH — the first resource for mathematics

A matrix approach for FCSR automata. (English) Zbl 1251.94019
Summary: LFSRs are primitives widely used in information theory, coding theory and cryptography. However, since 2002, they have faced algebraic attacks. To avoid this kind of attacks, FCSRs have been proposed as an alternative. In this paper, we first give a general representation of 2-adic automata using a traditional matrix representation. We then explore the special case of binary and ternary automata. We also study the complexity in terms of memory to implement such automata. Finally, we expose some proposed FCSR constructions for hardware- and software-oriented stream ciphers.

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
68Q45 Formal languages and automata
Full Text: DOI
[1] Arnault, F., Berger, T.P.: Design and properties of a new pseudorandom generator based on a filtered FCSR automaton. IEEE Trans Comput 54(11), 1374–1383 (2005) · Zbl 05105993 · doi:10.1109/TC.2005.181
[2] 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
[3] Arnault, F., Berger, T.P., Lauradoux, C.: The FCSR: primitive specification and supporting documentation. ECRYPT - Network of Excellence in Cryptology. http://www.ecrypt.eu.org/stream/ (2005)
[4] Arnault, F., Berger, T.P., Lauradoux, C.: Update on F-FCSR stream cipher. ECRYPT - Network of Excellence in Cryptology. http://www.ecrypt.eu.org/stream/ (2006)
[5] Arnault, F., Berger, T.P., Lauradoux, C., Minier, M.: X-FCSR–a new software oriented stream cipher based upon FCSRs. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT. Lecture Notes in Computer Science, vol. 4859, pp. 341–350. Springer, New York (2007) · Zbl 1153.68370
[6] 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
[7] Arnault, F., Berger, T.P., Minier, M.: Some results on FCSR automata with applications to the security of FCSR-Based pseudorandom generators. IEEE Trans. Inf. Theory 54(2), 836–840 (2008) · Zbl 1308.94056 · doi:10.1109/TIT.2007.913244
[8] Arnault, F., Berger, T.P., Necer, A.: Feedback with carry shift registers synthesis with the Euclidean algorithm. IEEE Trans. Inf. Theory 50(5), 910–917 (2004) · Zbl 1247.94023 · doi:10.1109/TIT.2004.826651
[9] 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
[10] Ebeid, N.M., Hasan, A.: On binary signed digit representations of integers. Des. Codes Cryptography 42(1), 43–65 (2007) · Zbl 1148.11006 · doi:10.1007/s10623-006-9014-9
[11] Fischer, S., Meier, W., Stegemann, D.: Equivalent representations of the F-FCSR keystream generator. In: ECRYPT Network of Excellence–SASC Workshop, pp. 87–94. Available at http://www.ecrypt.eu.org/stvl/sasc2008/ (2008)
[12] Goresky, M., Klapper, A.: Arithmetic crosscorrelations of feedback with carry shift register sequences. IEEE Trans. Inf. Theory 43(4), 1342–1345 (1997) · Zbl 0878.94047 · doi:10.1109/18.605605
[13] Goresky, M., Klapper, A.: Fibonacci and Galois representations of feedback-with-carry shift registers. IEEE Trans. Inf. Theory 48(11), 2826–2836 (2002) · Zbl 1062.94028 · doi:10.1109/TIT.2002.804048
[14] Goresky, M., Klapper, A.: Periodicity and distribution properties of combined FCSR sequences. In: Gong, G., Helleseth, T., Song, H.Y., Yang, K., (eds.) SETA. Lecture Notes in Computer Science, vol. 4086, pp. 334–341. Springer, New York (2006) · Zbl 1152.94384
[15] Goresky, M., Klapper, A.: Algebraic shift register sequences. Available at http://cs.engr.uky.edu/\(\sim\)klapper/algebraic.html (2009) · Zbl 1248.94002
[16] Hankerson, D., Vanstone, S., Menezes, A.: Guide to Elliptic Curve Cryptography. Springer, New York (2004) · Zbl 1059.94016
[17] 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
[18] Joux, A., Delaunay, P.: Galois LFSR, embedded devices and side channel weaknesses. In: Progress in Cryptology–INDOCRYPT 2006. Lecture Notes in Computer Science 4329, pp. 436–451. Springer, New York (2006) · Zbl 1175.94084
[19] 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
[20] Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10(2), 111–147 (1997) · Zbl 0874.94029 · doi:10.1007/s001459900024
[21] Klapper, A., Xu, J.: Algebraic feedback shift registers. Theor. Comput. Sci. 226(1–2), 61–92 (1999) · Zbl 0965.94014 · doi:10.1016/S0304-3975(99)00066-3
[22] Lauradoux, C.: Extended windmill polynomials. In: ISIT’09: Proceedings of the 2009 IEEE International Conference on Symposium on Information Theory, pp. 1120–1124. IEEE Press, Piscataway, NJ, USA (2009)
[23] Marsaglia, G.: Xorshift RNGs. J. Stat. Softw. 8(14), 1–6 (2003)
[24] Panneton, F., L’Ecuyer, P.: On the xorshift random number generators. ACM Trans. Model. Comput. Simul. 15(4), 346–361 (2005) · Zbl 05458266 · doi:10.1145/1113316.1113319
[25] Smeets, B.J.M., Chambers, W.G.: Windmill generators: a generalization and an observation of how many there are. In: EUROCRYPT, pp. 325–330 (1988) · Zbl 0655.94008
[26] Stankovski, P., Hell, M., Johansson, T.: An efficient state recovery attack on X-FCSR-256. In: Dunkelman, O. (ed.) FSE. Lecture notes in computer science, vol. 5665, pp. 23–37. Springer, New York (2009) · Zbl 1248.94096
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.