Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2904))
Included in the following conference series:
876Accesses
Abstract
At Eurocrypt’96, J.Patarin proposed a signature and authentication scheme whose security relies on the difficulty of the Isomorphism of Polynomials problem [P]. In this paper, we study a variant of this problem, namely the Isomorphism of Polynomials with one secret problem and we propose new algorithms to solve it, which improve on all the previously known algorithms. As a consequence, we prove that, when the number of polynomials (u) is close to the number of variables (n), the instances considered in [P] and [P1] can be broken. We point out that the casen-u small is the most relevant one for cryptographic applications. Besides, we show that a large class of instances that have been presumed difficult in [P] and [P1] can be solved in deterministic polynomial time. We also give numerical results to illustrate our methods.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Becker, T., Weispfenning, V.: Gröbner Bases, A Computational Approach to Commutative Algebra. In cooperation with Heinz Kredel. Graduate Texts in Mathematics, vol. 141. Springer, Heidelberg (1993)
Courtois, N., Goubin, L., Patarin, J.: Improved Algorithms for Isomorphism of Polynomials. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 184–200. Springer, Heidelberg (1998)
Cox, D.A., O’Shea, D., Little, J.B.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (1992)
Faugère, J.-C.: Algebraic cryptanalysis of HFE using Gröbner bases. INRIA report: RR-4738, Available fromhttp://www.inria.fr/rrrt/rr-4738.html
Faugère, J.-C.: A new efficient algorithm for computing Gröbner basis: F4. Journal of pure and applied algebra 139, 61–68 (1999)
Faugère, J.-C.: A new efficient algorithm for computing Gröbner basis without reduction to zero: F5. In: Proceedings of ISSAC, July 2002, pp. 75–83. ACM press, New York (2002)
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)
Geiselmann, W., Meier, W., Steinwandt, R.: An Attack on the Isomorphisms of Polynomials Problem with One Secret. Cryptology ePrint Archive: Report 2002/143, Available fromhttp://eprint.iacr.org/2002/143
Levy-dit-Vehel, F., Perret, L.: Polynomial equivalence problems and applications to multivariate cryptosystems. Rapport INRIA (2003) (to appear)
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.: Hidden Fields 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)
Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymmetric Algorithms, Extended versionhttp://www.cp8.com/sct/uk/partners/page/publi/eurocryptb.ps
Moh, T.-T.: A Fast Public Key System With Signature And Master Key Functions. In: CrypTEC 1999, July 1999, pp. 63–69. Hong Kong City University Press (1999)
Author information
Authors and Affiliations
ENSTA, 32 Boulevard Victor, 75739, Paris cedex 15
Françoise Levy-dit-Vehel & Ludovic Perret
- Françoise Levy-dit-Vehel
You can also search for this author inPubMed Google Scholar
- Ludovic Perret
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Dept. of Electrical and Information Technology, Lund University, P.O. Box 118, 221 00, Lund, Sweden
Thomas Johansson
Indian Statistical Institute, 203 B T Road, 700 108, Kolkata, India
Subhamoy Maitra
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Levy-dit-Vehel, F., Perret, L. (2003). Polynomial Equivalence Problems and Applications to Multivariate Cryptosystems. In: Johansson, T., Maitra, S. (eds) Progress in Cryptology - INDOCRYPT 2003. INDOCRYPT 2003. Lecture Notes in Computer Science, vol 2904. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24582-7_18
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-20609-5
Online ISBN:978-3-540-24582-7
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative