Abstract
In 2003 and 2004, Kasahara and Sakai suggested the two schemes RSE(2)PKC and RSSE(2)PKC, respectively. Both are examples of public key schemes based on \(\mathcal{M}\)ultivariate\(\mathcal{Q}\)uadratic equations. In this article, we first introduce Step-wise Triangular Schemes (STS) as a new class of \(\mathcal{M}\)ultivariate \(\mathcal{Q}\)uadratic public key schemes. These schemes have m equations, n variables, L steps or layers, r the number of equations and new variables per step and q the size of the underlying finite field \(\mathbb{F}\). Then, we derive two very efficient cryptanalytic attacks. The first attack is an inversion attack which computes the message/signature for given ciphertext/message in O(mn 3 Lq r + n 2 Lrq r), the second is a structural attack which recovers an equivalent version of the secret key in O(mn 3 Lq r + mn 4) operations. As the legitimate user also has a workload growing with q r to recover a message/compute a signature, q r has to be small for efficient schemes and the attacks presented in this article are therefore efficient. After developing our theory, we demonstrate that both RSE(2)PKC and RSSE(2)PKC are special instances of STS and hence, fall to the attacks developed in our article. In particular, we give the solution for the crypto challenge proposed by Kasahara and Sakai. Finally, we demonstrate that STS cannot be the basis for a secure \(\mathcal{M}\)ultivariate \(\mathcal{Q}\)uadratic public key scheme by discussing all possible variations and pointing out their vulnerabilities.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Menezes AJ, van Oorschot PC, Vanstone SA (1996) Handbook of Applied Cryptography. CRC Press, Boca Raton, ISBN 0-8493-8523-7, online-version: http://www.cacr.math.uwaterloo.ca/hac/
PW Shor (1997) ArticleTitlePolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer SIAM J Comput 26 IssueID5 1484–1509 Occurrence Handle1005.11065 Occurrence Handle1471990 Occurrence Handle10.1137/S0097539795293172
Wolf C, Preneel B (2005) Taxonomy of public key schemes based on the problem of multivariate quadratic equations. Cryptology ePrint Archive, Report 2005/077, http://eprint.iacr.org/2005/077/, p 64
H Fell W Diffie (1985) Analysis of public key approach based on polynomial substitution HC Williams (Eds) Advances in cryptology—CRYPTO 1985, volume 218 of Lecture Notes in Computer Science Springer Berlin 340–349
T Matsumoto H Imai (1988) Public quadratic polynomial-tuples for efficient signature verification and message-encryption CG Günther (Eds) Advances in cryptology—EUROCRYPT 1988, volume 330 of Lecture Notes in Computer Science Springer Berlin 419–545
Courtois NT (2001) The security of Hidden Field Equations (HFE). In: Naccache D (ed) The cryptographer’s track at RSA conference 2001, volume 2020 of Lecture Notes in Computer Science, Springer, Berlin pp 266–281, http://www.minrank.org/hfesec.ps|dvi|pdf
Patarin J (1996) Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms. In: Maurer U (ed) Advances in cryptology—EUROCRYPT 1996, volume 1070 of Lecture Notes in Computer Science, Springer, Berlin, pp 33–48, Extended Version: http://www.minrank.org/hfe.pdf
A Kipnis J Patarin L Goubin (1999) Unbalanced Oil and Vinegar signature schemes J Stern (Eds) Advances in cryptology—EUROCRYPT 1999, volume 1592 of Lecture Notes in Computer Science Springer Berlin 206–222
MR Garey DS Johnson (1979) Computers and intractability—A guide to the theory of NP-completeness W.H. Freeman and Company New York
Patarin J, Goubin L (1997) Trapdoor one-way permutations and multivariate polynomials. In: International conference on information security and cryptology 1997, volume 1334 of Lecture Notes in Computer Science, International Communications and Information Security Association, Springer, Berlin, pp 356–368, Extended Version: http://citeseer.nj.nec.com/patarin97trapdoor.html
Geiselmann W, Meier W, Steinwandt R (2002) An attack on the Isomorphisms of Polynomials problem with one secret. Cryptology ePrint Archive, Report 2002/143, http://eprint.iacr.org/2002/143, version from 2002-09-20, p 12 (2000)
F Levy-dit-Vehel L Perret (2003) Polynomial equivalence problems and applications to multivariate cryptosystems T Johanson s Maitra (Eds) Progress in cryptology—INDOCRYPT 2003, volume 2904 of Lecture Notes in Computer Science Springer Berlin 235–251
J Patarin L Goubin N Courtois (1998) Improved algorithms for Isomorphisms of Polynomials K Nyberg (Eds) Advances in cryptology—EUROCRYPT 1998, volume 1403 of Lecture Notes in Computer Science Springer Berlin 184–200
Shamir A Efficient signature schemes based on birational permutations. In Cr [11], pp 1–12
L Goubin NT Courtois (2000) Cryptanalysis of the TTM cryptosystem T Okamoto (Eds) Advances in cryptology—ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science Springer Berlin 44–57
Kasahara M, Sakai R (2004) A construction of public key cryptosystem for realizing ciphtertext of size 100 bit and digital signature scheme. IEICE Trans. fundamentals, E87–A(1):102–109, Electronic version: http://search.ieice.org/2004/files/e000a01.htm#e87-a,1,102
Kasahara M, Sakai R (2004) A construction of public-key cryptosystem based on singular simultaneous equations. In: Symposium on cryptography and information security—SCIS 2004. The Institute of Electronics, Information and Communication Engineers, January 27–30, p 6
Coppersmith D, Stern J, Vaudenay S Attacks on the birational permutation signature schemes. In: Cr [11], pp 435–443
D Coppersmith J Stern S Vaudenay (1997) ArticleTitleThe security of the birational permutation signature schemes J Cryptol 10 207–221 Occurrence Handle0905.94026 Occurrence Handle1456328 Occurrence Handle10.1007/s001459900028
T Theobald (1995) How to break Shamir’s asymmetric basis D Coppersmith (Eds) Advances in Cryptology—CRYPTO 1995, volume 963 of Lecture Notes in Computer Science Springer Berlin 136–147
MacWilliams FJ, Sloane NJA (1991) The theory of error-correcting codes. Elsevier Science Publisher, ISBN 0-444-85193-3
N Courtois L Goubin W Meier JD Tacier (2002) Solving underdefined systems of multivariate quadratic equations D Naccache P Paillier (Eds) Public key cryptography—PKC 2002, volume 2274 of Lecture Notes in Computer Science Springer Berlin 211–227
Computational Algebra Group, University of Sydney. The MAGMA computational algebra system for algebra, number theory and geometry, http://magma.maths.usyd.edu.au/magma/
Courtois N, Goubin L, Patarin J (2001) Quartz: Primitive specification (second revised version), https://www.cosic.esat.kuleuven.ac.be/nessie Submissions, Quartz, p 18
Toli I (2003) Cryptanalysis of HFE, arXiv preprint server, http://arxiv.org/abs/cs.CR/0305034, p 7
Wolf C, Preneel B (2005) Equivalent keys in HFE, C*, and variations. In: Vaudenay S (ed) Proceedings of MyCrypt 2005, volume 3715 of Lecture Notes in Computer Science, Springer, Berlin, pp 33–49, Extended version http://eprint.iacr.org/2004/360/, p 15
C Wolf B Preneel (2005) Superfluous keys in \(\mathcal{M}\)ultivariate \(\mathcal{Q}\)uadratic asymmetric systems S Vaudenay (Eds) Public key cryptography—PKC 2005, volume 3386 of Lecture Notes in Computer Science Springer Berlin 275–287
T Moh (1999) ArticleTitleA public key system with signature and master key function Communi Algebra 27 IssueID5 2207–2222 Occurrence Handle0933.94022 Occurrence Handle1683861
Yang BY, Chen JM (2004) Rank attacks and defence in Tame-like multivariate PKC’s. Cryptology ePrint Archive, Report 2004/061, http://eprint.iacr.org/, p 21
Ding J, Yin Z (2004) Cryptanalysis of TTS and Tame-like multivariate signature schemes. Pre-Proceedings of the The Third International Workshop for Applied PKI, Fukuoka, Japan, October 3–5, 2004.
Akivis MA, Goldberg VV (1972) An introduction to linear algebra and tensors. Dover New York
A Braeken C Wolf B Preneel (2005) A study of the security of unbalanced oil and vinegar signature schemes AJ Menezes (Eds) The cryptographer’s track at RSA conference 2005, volume 3376 of Lecture Notes in Computer Science. Springer Berlin 13
DR Stinson (Eds) (1993) Advances in cryptology—CRYPTO 1993, volume 773 of Lecture Notes in Computer Science Springer Berlin
C Wolf (2004) Efficient public key generation for HFE and variations Dawson Klimm (Eds) Cryptographic algorithms and their uses 2004 QUT University Brisbane
Wolf C, Braeken A, Preneel B (2004) Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC. In: Conference on Security in Communication Networks—SCN 2004, volume 3352 of Lecture Notes in Computer Science, Springer, Berlin, pp 294–309, September 8–10, Extended version: http://eprint.iacr.org/2004/237
Wolf C, Preneel B (2004) Asymmetric cryptography: Hidden Field Equations. In: Neittaanmäki P, Rossi T, Korotov S, Oñate E, Périaux J, Knörzer D (eds) European congress on computational methods in applied sciences and engineering 2004. Jyväskylä University, p 20, extended version: http://eprint.iacr.org/2004/072/
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by H. Imai
Rights and permissions
About this article
Cite this article
Wolf, C., Braeken, A. & Preneel, B. On the security of stepwise triangular systems. Des Codes Crypt 40, 285–302 (2006). https://doi.org/10.1007/s10623-006-0015-5
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10623-006-0015-5