Abstract
In this paper, we study the security of 2R− schemes [17,18], which are the “minus variant” of two-round schemes. This variant consists in removing some of the n polynomials of the public key, and permits to thwart an attack described at Crypto’99 [25] against two-round schemes. Usually, the “minus variant” leads to a real strengthening of the considered schemes. We show here that this is actually not true for 2R− schemes. We indeed propose an efficient algorithm for decomposing 2R− schemes. For instance, we can remove up to \(\left \lfloor\frac{n}{2} \right \rfloor\) equations and still be able to recover a decomposition in O(n 12). We provide experimental results illustrating the efficiency of our approach. In practice, we have been able to decompose 2R− schemes in less than a handful of hours for most of the challenges proposed by the designers [18]. We believe that this result makes the principle of two-round schemes, including 2R− schemes, useless.
Chapter PDF
Similar content being viewed by others
References
Adams, A.W., Loustaunau, P.: An Introduction to Gröbner Bases. Graduate Studies in Mathematics, vol. 3. AMS, Providence, RI (1994)
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)
Ars, G., Faugère, J.-C.: Algebraic Immunities of functions over finite fields. In: Proceedings of BFCA 2005, Rouen (2005), Also available at: http://eprint.iacr.org/2004/188.ps
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, Eighth International Symposium on Effective Methods in Algebraic Geometry, pages. 15 (2005)
Bardet, M., Faugère, J.-C., Salvy, B.: On the Complexity of Gröbner Basis Computation of Semi-Regular Overdetermined Algebraic Equations. In: Proc. of International Conference on Polynomial System Solving (ICPSS), pp. 71–75 (2004)
Biham, E.: Cryptanalysis of Patarin’s 2-Round Public Key System with S Boxes (2R). In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 408–416. Springer, Heidelberg (2000)
Buchberger, B.: Gröbner Bases : an Algorithmic Method in Polynomial Ideal Theory. Recent trends in multidimensional systems theory. Reider ed. Bose (1985)
Buchberger, B., Collins, G.-E., Loos, R.: Computer Algebra Symbolic and Algebraic Computation, 2nd edn. Springer, Heidelberg (1982)
Carlier, V., Chabanne, H., Dottax, E.: Grey Box Implementation of Block Ciphers Preserving the Confidentiality of their Design. In: Proceedings of BFCA 2005, Rouen (2005), Also available at: http://eprint.iacr.org/2004/188.ps
Courtois, N., Goubin, L., Patarin, J.: SFLASH, a Fast Asymmetric Signature Scheme for low-cost Smartcards – Primitive Specification and Supporting Documentation, Available at: http://www.minrank.org/sflash-b-v2.pdf
Cox, D.A., Little, J.B., O’Shea, D.: Ideals, Varieties, and Algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (1992)
Dickerson, M.: The functional Decomposition of Polynomials. Ph.D Thesis, TR 89-1023, Departement of Computer Science, Cornell University, Ithaca, NY (July 1989)
Faugère, J.-C.: A New Efficient Algorithm for Computing Gröbner Casis without Reduction to Zero: F5. In: Proceedings of ISSAC, July 2002, pp. 75–83. ACM press, New York (2002)
Faugère, J.C., Gianni, P., Lazard, D., Mora, T.: Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering. Journal of Symbolic Computation 16(4), 329–344 (1993)
Kozen, D., Landau, S.: Polynomial decomposition algorithms. J. Symb. Comput. (7), 445–456 (1989)
Goubin, L., Patarin, J.: Trapdoor One-way Permutations and Multivariate Polynomials. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 356–368. Springer, Heidelberg (1997)
Goubin, L., Patarin, J.: Asymmetric Cryptography with S-Boxes. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 369–380. Springer, Heidelberg (1997)
Goubin, L., Patarin, J.: Asymmetric Cryptography with S-Boxes – Extended Version, Available at: http://citeseer.ist.psu.edu/patarin97asymmetric.html
Gutierrez, J., Rubio, R., von Zur Gathen, J.: Multivariate Polynomial Decomposition. Algebra in Engineering, Communication and Computing 14(1), 11–31
Matsumoto, T., Imai, H.: Algebraic Methods for Constructing Asymmetric Cryptosystems. In: Algebraic and Error-Correcting Codes. Prod. Third Intern. Conf., Grenoble, France, pp. 108–119. Springer, Heidelberg (1985)
Matsumoto, T., Imai, H.: Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 419–453. Springer, Heidelberg (1988)
Patarin, J.: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt ’88. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248–261. Springer, Heidelberg (1995)
von ZurGathen, J.: Functional decomposition of polynomials: the tame case. J. Symb. Comput. (9), 281–299 (1990)
von Zur Gathen, J.: Functional decomposition of polynomials: the wild case. J. Symb. Comput. (10), 437–452 (1990)
Ding-Feng, Y., Kwok-Yan, L., Zong-Duo, D.: Cryptanalysis of 2R schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 315–325. Springer, Heidelberg (1999)
Ye, D.F., Dai, Z.D., Lam, K.Y.: Decomposing Attacks on Asymmetric Cryptography Based on Mapping Compositions. Journal of Cryptology (14), 137–150 (2001)
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
Faugère, JC., Perret, L. (2006). Cryptanalysis of 2R− Schemes. In: Dwork, C. (eds) Advances in Cryptology - CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science, vol 4117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11818175_21
Download citation
DOI: https://doi.org/10.1007/11818175_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37432-9
Online ISBN: 978-3-540-37433-6
eBook Packages: Computer ScienceComputer Science (R0)