Abstract
In this paper, we study the new class step-wise Triangular Schemes (STS) of public key cryptosystems (PKC) based on multivariate quadratic polynomials. In these schemes, we have m the number of equations, n the number of variables, L the number of steps/layers, r the number of equations/variables per step, and q the size of the underlying field. We present two attacks on the STS class by exploiting the chain of the kernels of the private key polynomials. 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. Since the legitimate user has workload q r for decrypting/computing a signature, the attacks presented in this paper are very efficient. As an application, we show that two special instances of STS, namely RSE(2)PKC and RSSE(2)PKC, recently proposed by Kasahara and Sakai, are insecure.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Computational Algebra Group, University of Sydney. The MAGMA Computational Algebra System for Algebra, Number Theory and Geometry, http://magma.maths.usyd.edu.au/magma/
Coppersmith, D., Stern, J., Vaudenay, S.: Attacks on the birational permutation signature schemes. In: Cr [7], pp. 435–443 (1994)
Coppersmith, D., Stern, J., Vaudenay, S.: The security of the birational permutation signature schemes. Jounal of Cryptology 10, 207–221 (1997)
Courtois, N., Goubin, L., Meier, W., Tacier, J.-D.: Solving underdefined systems of multivariate quadratic equations. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 211–227. Springer, Heidelberg (2002)
Courtois, N., Goubin, L., Patarin, J.: Quartz: Primitive specification (second revised version), 18 pages (October 2001) https://www.cosic.esat.kuleuven.ac.be/nessie/workshop/submissions/quartzv21-b.zip
Courtois, N.T.: The security of Hidden Field Equations (HFE). In: CT-RSA 2001. LNCS, vol. 2020, pp. 266–281. Springer, Heidelberg (2001), http://www.minrank.org/hfesec.{ps|dvi|pdf}
Stinson, D.R. (ed.) Advances in Cryptology — CRYPTO 1993. LNCS, vol. 773, Springer, Heidelberg (1993)
Fell, H., Diffie, W.: Analysis of public key approach based on polynomial substitution. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 340–349. Springer, Heidelberg (1986)
Garay, M.R., Johnson, D.S.: Computers and Intractability — A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Goubin, L., Courtois, N.T.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 44–57. Springer, Heidelberg (2000)
Kasahara, M., Sakai, R.: private communication, (April 3, 2004)
Kasahara, M., Sakai, R.: 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 (2004)
Kasahara, M., Sakai, R.: 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 (2004), Electronic version: http://search.ieice.org/2004/files/e000a01.htm#e87-a,1,102
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206–222. Springer, Heidelberg (1999); Extended version: [15]
Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes — extended version, 17 pages, (2003)citeseer/231623.html, 2003-06-11, based on [14]
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. Elsevier Science Publisher, Amsterdam (1991)
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–545. Springer, Heidelberg (1988)
Menezes,, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996), online-version: http://www.cacr.math.uwaterloo.ca/hac/
Patarin, J.: Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 33–48. Springer, Heidelberg (1996), Extended Version: http://www.minrank.org/hfe.pdf
Patarin, J., Goubin, L.: Trapdoor one-way permutations and multivariate polynomials. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 356–368. Springer, Heidelberg (1997), Extended Version: http://citeseer.nj.nec.com/patarin97trapdoor.html
Patarin, J., Goubin, L., Courtois, N.: Improved algorithms for Isomorphisms of Polynomials. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 184–200. Springer, Heidelberg (1998), Extended Version: http://www.minrank.org/ip6long.ps
Shamir, A.: Efficient signature schemes based on birational permutations. In: Cr [7], pp. 1–12 (1994)
Theobald, T.: How to break shamir’s asymmetric basis. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 136–147. Springer, Heidelberg (1995)
Toli, I.: Cryptanalysis of HFE, (June 2003), arXiv preprint server 7 pages, http://arxiv.org/abs/cs.CR/0305034
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wolf, C., Braeken, A., Preneel, B. (2005). Efficient Cryptanalysis of RSE(2)PKC and RSSE(2)PKC. In: Blundo, C., Cimato, S. (eds) Security in Communication Networks. SCN 2004. Lecture Notes in Computer Science, vol 3352. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30598-9_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-30598-9_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24301-4
Online ISBN: 978-3-540-30598-9
eBook Packages: Computer ScienceComputer Science (R0)