Abstract
The recently developed algebraic attacks apply to all keystream generators whose internal state is updated by a linear transition function, including LFSR-based generators. Here, we describe this type of attacks and we present some open problems related to their complexity. We also investigate the design criteria which may guarantee a high resistance to algebraic attacks for keystream generators based on a linear transition function.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Anderson, R.J.: Searching for the optimum correlation attack. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 137–143. Springer, Heidelberg (1995)
Armknecht, F.: Improving fast algebraic attacks. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 65–82. Springer, Heidelberg (2004)
Armknecht, F.: Algebraic attacks and annihilators. In: Proceedings of the Western European Workshop on Research in Cryptology (WEWoRC 2005). Lecture Notes in Informatics. Springer, Heidelberg (2005)
Armknecht, F., Krause, M.: Algebraic attacks on combiners with memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–175. Springer, Heidelberg (2003)
Ars, G., Faugère, J.-C., Imai, H., Kawazoe, M., Sugita, M.: Comparison between XL and gröbner basis algorithms. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 338–353. Springer, Heidelberg (2004)
Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In: Proc. International Conference on Polynomial System Solving (ICPSS 2004) (2004)
Bardet, M., Faugère, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: MEGA 2005, Porto Conte, Italy (May 2005)
Carlet, C., Prouff, E.: On a new notion of nonlinearity relevant to multi-output pseudo-random generators. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 291–305. Springer, Heidelberg (2004)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic programming. Journal of Symbolic Computation (9), 251–280 (1990)
Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Courtois, N.T., Klimov, A.B., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)
Courtois, N.T.: Algebraic attacks on combiners with memory and several outputs. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 3–20. Springer, Heidelberg (2005)
Courtois, N.T., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: ESORICS 2002. LNCS, pp. 267–287. Springer, Heidelberg (2002)
Dalai, D.K., Gupta, K.C., Maitra, S.: Results on algebraic immunity for cryptographically significant boolean functions. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 92–106. Springer, Heidelberg (2004)
Dalai, D.K., Gupta, K.C., Maitra, S.: Cryptographically significant boolean functions: Construction and analysis in terms of algebraic immunity. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 98–111. Springer, Heidelberg (2005)
Dalai, D.K., Sarkar, S., Maitra, S.: Balanced Boolean functions with maximum possible algebraic immunity, April 2005 (preprint)
Diem, C.: The XL-algorithm and a conjecture from commutative algebra. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 323–337. Springer, Heidelberg (2004)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F 4). Journal of Pure and Applied Algebra 139(1-3), 61–88 (1999)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5). In: Proceedings of the 2002 international symposium on Symbolic and algebraic computation. ACM, New York (2002)
Faugère, J.-C., Ars, G.: An algebraic cryptanalysis of nonlinear filter generators using Gröbner bases. Technical Report 4739, INRIA (2003), Available at: ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-4739.pdf
Faugère, J.-C., Joux, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using gröbner bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)
Key, J.D., McDonough, T.P., Mavron, V.C.: Information sets and partial permutation decoding for codes from finite geometries. Finite Fields and Their Applications (to appear, 2005)
Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of boolean functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004)
Pasalic, E.: On algebraic immunity of Maiorana-McFarland like functions and applications of algebraic attack. In: Proceedings of the ECRYPT Symmetric Key Encryption Workshop (SKEW), Aarhus, Danemark (May 2005)
Shannon, C.E.: Communication theory of secrecy systems. Bell system technical journal 28, 656–715 (1949)
Steel, A.: Allan Steel’s Gröbner basis timings page (2004), http://magma.maths.usyd.edu.au/users/allan/gb/
Zhang, M., Chan, A.H.: Maximum correlation analysis of nonlinear S-boxes in stream ciphers. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 501–514. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Canteaut, A. (2006). Open Problems Related to Algebraic Attacks on Stream Ciphers. In: Ytrehus, Ø. (eds) Coding and Cryptography. WCC 2005. Lecture Notes in Computer Science, vol 3969. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11779360_10
Download citation
DOI: https://doi.org/10.1007/11779360_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35481-9
Online ISBN: 978-3-540-35482-6
eBook Packages: Computer ScienceComputer Science (R0)