Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 6/2021

18-04-2021

Cryptanalysis of the extension field cancellation cryptosystem

Authors: Olive Chakraborty, Jean-Charles Faugère, Ludovic Perret

Published in: Designs, Codes and Cryptography | Issue 6/2021

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this article, we present algebraic attacks against the Extension Field Cancellation (\(\texttt {EFC}\)) scheme, a multivariate public-key encryption scheme which was published at PQCRYPTO’2016. First, we present a successful Gröbner basis message-recovery attack on the first and second proposed parameters of the scheme. For the first challenge parameter, a Gröbner-based hybrid attack has a \(2^{65}\) bit complexity which beats the claimed 80 bit security level. We further show that the algebraic system arising from an \(\texttt {EFC}\) public-key is much easier to solve than a random system of the same size. Briefly, this is due to the apparition of many lower degree equations during the Gröbner basis computation. We present a polynomial-time method to recover such lower-degree relations and also show their usefulness in improving the Gröbner basis attack complexity on \(\texttt {EFC}\). Thus, we show that there is an algebraic structural weakness in the system of equations coming from \(\texttt {EFC}\) and hence makes the scheme not suitable for encryption.
previous article A Legendre pair of length 77 using complementary binary matrices with fixed marginals
next article Correction to: Cubic bent functions outside the completed Maiorana-McFarland class
Appendix
Available only for authorised users
Literature
1.
Bardet M., Faugere J.-C., Salvy B.: On the complexity of gröbner basis computation of semi-regular overdetermined algebraic equations. In: Proceedings of the International Conference on Polynomial System Solving, pp. 71–74 (2004).
2.
Bardet M., Faugère J.-C., Salvy B.: On the complexity of the f5 gröbner basis algorithm. J. Symb. Comput. 70, 49–70 (2015).CrossRef
3.
Bardet M., Faugere J.-C., Salvy B., Yang B.-Y.: Asymptotic behaviour of the index of regularity of quadratic semi-regular polynomial systems. In: Gianni, P. (ed.) The Effective Methods in Algebraic Geometry Conference (MEGA’05), pp. 1–14. Citeseer (2005).
4.
Barker E., Roginsky A.: Transitions: recommendation for transitioning the use of cryptographic algorithms and key lengths. NIST Spec. Publ. 800, 131A (2011).
5.
Berbain C., Billet O., Gilbert H.: Efficient implementations of multivariate quadratic systems. In: International Workshop on Selected Areas in Cryptography, pp. 174–187. Springer (2006).
6.
Bettale L.: Cryptanalyse algébrique: outils et applications. PhD thesis, Paris 6 (2011).
7.
Bettale L., Faugere J.-C., Perret L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3(3), 177–197 (2009).MathSciNetCrossRef
8.
Bettale L., Faugère J.-C., Perret L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Des. Codes Cryptogr. 69(1), 1–52 (2013).MathSciNetCrossRef
9.
Beullens W., Preneel B.: Field lifting for smaller UOV public keys. In: International Conference on Cryptology in India, pp. 227–246. Springer (2017).
10.
Bouillaguet C., Fouque P.-A., Macario-Rat G.: Practical key-recovery for all possible parameters of sflash. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 667–685. Springer (2011).
11.
Buchberger B.: An algorithm for finding the base elements of the residual class ring after a zero-dimensional polynomial ideal. PhD thesis, Universitat Insbruck (1965).
12.
Buchberger B.: An algorithmical criteria for the solvability of algebraic systems of equations. Aequationes Math. 4, 374–383 (1970).MathSciNetCrossRef
13.
Buchberger B.: A criterion for detecting unnecessary reductions in the construction of gröbner-bases. In: International Symposium on Symbolic and Algebraic Manipulation, pp. 3–21. Springer (1979).
14.
Buchberger B.: Grobner bases: an algorithmic method in polynomial ideal theory. Multidimensional systems theory (1985).
15.
Buchmann J.A., Ding J., Mohamed M.S.E., Mohamed W.S.E.: Mutantxl: solving multivariate polynomial equations for cryptanalysis. In: Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2009).
16.
Cabarcas D., Smith-Tone D., Verbel J.A.: Practical key recovery attack for ZHFE.
17.
Cartor R., Smith-Tone D.: Eflash: a new multivariate encryption scheme. In: International Conference on Selected Areas in Cryptography, pp. 281–299. Springer (2018).
18.
Casanova A., Faugère J.-C., Macario-Rat G., Patarin J., Perret L., Ryckeghem J.: Gemss: a great multivariate short signature. Submission to NIST (2017).
19.
Chen L., Chen L., Jordan S., Liu Y.-K., Moody D., Peralta R., Perlner R., Smith-Tone D.: Report on Post-quantum Cryptography. US Department of Commerce, National Institute of Standards and Technology (2016).
20.
Chen M.-S., Yang B.-Y., Smith-Tone D.: Pflash-secure asymmetric signatures on smart cards. In: Lightweight Cryptography Workshop (2015).
21.
Courtois N.T.: The security of hidden field equations (HFE). In: Cryptographers’ Track at the RSA Conference, pp. 266–281. Springer (2001).
22.
Devoret M.H., Schoelkopf R.J.: Superconducting circuits for quantum information: an outlook. Science 339(6124), 1169–1174 (2013).CrossRef
23.
Ding J., Schmidt D.: Rainbow, a new multivariable polynomial signature scheme. In: International Conference on Applied Cryptography and Network Security, pp. 164–175. Springer (2005).
24.
Ding J., Zhang Z., Deaton J.: The singularity attack to the multivariate signature scheme HIMQ-3. Adv. Math. Commun. 15(1), 65 (2021).MathSciNetCrossRef
25.
Ding J., Zhang Z., Deaton J., Schmidt K., Vishakha F.: New attacks on lifted unbalanced oil vinegar. In: The 2nd NIST PQC Standardization Conference (2019).
26.
Dubois V., Fouque P.-A., Shamir A., Stern J.: Practical cryptanalysis of SFLASH. In: Annual International Cryptology Conference, pp. 1–12. Springer (2007).
27.
Faugere J.-C.: A new efficient algorithm for computing gröbner bases (f4). J. Pure Appl. Algebra 139(1–3), 61–88 (1999).MathSciNetCrossRef
28.
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, pp. 75–83. ACM (2002).
29.
Faugere J.-C., Joux A.: Algebraic cryptanalysis of hidden field equation (hfe) cryptosystems using gröbner bases. In: Annual International Cryptology Conference, pp. 44–60. Springer (2003).
30.
Faugere J.-C., Joux A., Perret L., Treger J.: Cryptanalysis of the hidden matrix cryptosystem. In: International Conference on Cryptology and Information Security in Latin America, pp. 241–254. Springer (2010).
31.
32.
Garey M.R., Johnson D.S.: Computers and Intractability, vol. 174. Freeman, San Francisco (1979).MATH
33.
34.
Jao D., De Feo L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: International Workshop on Post-quantum Cryptography, pp. 19–34. Springer (2011).
35.
Kipnis A., Patarin J., Goubin L.: Unbalanced oil and vinegar signature schemes. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 206–222. Springer (1999).
36.
Lazard D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: European Conference on Computer Algebra, pp. 146–156. Springer (1983).
37.
Matsumoto T., Imai H: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Workshop on the Theory and Application of of Cryptographic Techniques, pp. 419–453. Springer (1988).
38.
Mus K., Islam S., Sunar B.: QuantumHammer: a practical hybrid attack on the LUOV signature scheme. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1071–1084 (2020).
39.
Overbeck R., Sendrier N.: Code-based cryptography. In: Post-quantum Cryptography, pp. 95–145. Springer (2009).
40.
Patarin J.: Cryptanalysis of the Matsumoto and Imai public key scheme of eurocrypt’88. In: Annual International Cryptology Conference, pp. 248–261. Springer (1995).
41.
Patarin J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 33–48. Springer (1996).
42.
Patarin J., Courtois N., Goubin L.: Quartz, 128-bit long digital signatures. In: Cryptographers’ Track at the RSA Conference, pp. 282–297. Springer (2001).
43.
Petzoldt A., Chen M.S., Yang B.Y., Tao C., Ding J.: Design principles for HFEv based signature schemes. In: ASIACRYPT 2015-part 1, LNCS vol. 9452, (2015).
44.
45.
Regev O.: Lattice-based cryptography. In: Annual International Cryptology Conference, pp. 131–141. Springer (2006).
46.
Shamir A., Kipnis A.: Cryptanalysis of the HFE public key cryptosystem. In: Advances in Cryptology, Proceedings of Crypto, vol. 99 (1999).
47.
48.
Smith-Tone D.: Properties of the discrete differential with cryptographic applications. In: International Workshop on Post-Quantum Cryptography, pp. 1–12. Springer (2010).
49.
Szepieniec A., Ding J., Preneel B.: Extension field cancellation: a new central trapdoor for multivariate quadratic systems. In: International Workshop on Post-quantum Cryptography, pp. 182–196. Springer (2016).
50.
Vates J., Smith-Tone D.: Key recovery attack for all parameters of HFE. In: International Workshop on Post-Quantum Cryptography, pp. 272–288. Springer (2017).
51.
Zhang W., Tan C.H.: On the security and key generation of the ZHFE encryption scheme. In: International Workshop on Security, pp. 289–304. Springer (2016).
Metadata
Title
Cryptanalysis of the extension field cancellation cryptosystem
Authors
Olive Chakraborty
Jean-Charles Faugère
Ludovic Perret
Publication date
18-04-2021
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 6/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00873-9

Other articles of this Issue 6/2021

Designs, Codes and Cryptography 6/2021 Go to the issue

Correction

Correction to: Cubic bent functions outside the completed Maiorana-McFarland class

OriginalPaper

Average of complete joint weight enumerators and self-dual codes

OriginalPaper

Binary Hamming codes and Boolean designs

OriginalPaper

Traceable ring signatures: general framework and post-quantum security

OriginalPaper

LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding

OriginalPaper

Differential spectra of a class of power permutations with characteristic 5

Premium Partner

    Image Credits