Abstract
This article is divided into three parts. The first part describes the known candidates of trapdoor one-way permutations. The second part presents a new algorithm, called D *. As we will see, this algorithm is not secure. However, in the third part, D * will be a useful tool to present our new candidate trapdoor one-way permutation, called D **. This candidate is based on properties of multivariate polynomials on finite fields, and has similar characteristics to T. Matsumoto and H. Imai's schemes.
What makes trapdoor one-way permutations particularly interesting is the fact that they immediately provide ciphering, signature, and authentication asymmetric schemes.
Our candidate performs excellently in secret key, and secret key computations can be implemented in low-cost smart-cards, i.e. without co-processors. An extended version of this paper can be obtained from the authors.
Preview
Unable to display preview. Download preview PDF.
References
D. Bleichenbacher, W. Bosma, A.K. Lenstra, Some Remarks on Lucas-Based Cryptosystems, Advances in Cryptology, Proceedings of CRYPTO'95, Springer-Verlag, pp. 386–396.
I. Blake, X. Gao, R. Mullin, S. Vanstone, T. Yaghoobian, Applications of finite Fields, Kluwer Academic Publishers, p. 25.
N. Courtois, Les cryptosystémes asymétriques à représentation obscure, Rapport de stage de DEA, Bull PTS — Université Paris 6, 1997. (This paper is available from J. Patarin and L. Goubin).
N. Demytko, A New Elliptic Curve Based Analogue of RSA, Advances in Cryptology, Proceedings of EUROCRYPT'93, Springer-Verlag, pp. 40–49.
M. Dickerson, The functional Decomposition of Polynomials, Ph.D Thesis, TR 89-1023, Department of Computer Science, Cornell University, Ithaca, NY, July 1989.
M. Garey, D. Johnson, Computers and Intractability, a Guide to the Theory of NP-Completeness, Freeman, p. 251.
K. Koyama, U.M. Maurer, T. Okamoto, S.A. Vanstone, New Public-Key Schemes Based on Elliptic Curves over the Ring Z n , Advances in Cryptology, Proceedings of CRYPTO'91, Springer-Verlag, pp. 252–266.
J.H. Loxton, D.S.P. Khoo, G.J. Bird, J. Seberry, A Cubic RSA Code Equivalent to Factorization, Journal of Cryptology, v.5, n.2, 1992, pp. 139–150.
R. Lidl, G.L. Mullen, G. Turwald, Pitman Monographs and Surveys in Pure and Applied Mathematics 65: Dickson Polynomials, London, Longman Scientific and Technical, 1993.
R. Lidl, W.B. Müller, Permutation Polynomials in RSA-Cryptosystems, Advances in Cryptology, Proceedings of CRYPTO'83, Plenum Press, 1984, pp. 293–301.
T. Matsumoto, H. Imai, Algebraic Methods for Constructing Asymmetric Cryptosystems, AAECC-3, Grenoble, 1985.
T. Matsumoto, H. Imai, Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption, Advances in Cryptology, Proceedings of EUROCRYPT'88, Springer-Verlag, pp. 419–453.
W.B. Müller, Polynomial Functions in Modern Cryptology, Contributions to General Algebra 3: Proceedings of the Vienna Conference, Vienna: Verlag Holder-Pichler-Tempsky, 1985, pp. 7–32.
W.B. Müller, R. Nöbauer, Some Remarks on Public-Key Cryptography, Studia Scientiarum Mathematicarum Hungarica, v.16, 1981, pp. 71–76.
W.B. Müller, R. Nöbauer, Cryptanalysis of the Dickson-scheme, Advances in Cryptology, Proceedings of EUROCRYPT'85, Springer-Verlag, pp. 50–61.
J. Patarin, Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88, Advances in Cryptology, Proceedings of CRYPTO'95, Springer-Verlag, pp. 248–261.
J. Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP) Two New Families of Asymmetric Algorithms, Advances in Cryptology, Proceedings of EUROCRYPT'96, Springer-Verlag, pp. 33–48.
J. Patarin, Asymmetric Cryptography with a Hidden Monomial, Advances in Cryptology, Proceedings of CRYPTO'96, Springer-Verlag, pp. 45–60.
J. Patarin, L. Goubin, Asymmetric Cryptography with S-boxes, ICICS'97 (this conference.
M.O. Rabin, Digitized Signatures and Public-Key Functions as Intractable as Factorization, Technical Report LCS/TR-212, M.I.T. Laboratory for Computer Science, 1979.
R.L. Rivest, A. Shamir, L.M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, v.21, n.2, 1978, pp. 120–126.
P.J. Smith, LUC Public-Key Encryption, Dr. Dobb's Journal, January 1993, pp. 44–49.
P.J. Smith, M.J.J. Lennon, LUC. a New Public Key System, Proceedings of the Ninth IFIP Int. Symp. on Computer Security, 1993, pp. 103–117.
H.C. Williams, A Modification of the RSA Public-Key Encryption Procedure, IEEE Transactions on Information Theory, v.IT-26, n.6, 1980, pp. 726–729.
H.C. Williams, An M 3 Public-Key Encryption Scheme, Advances in Cryptology, Proceedings of CRYPTO'85, Springer-Verlag, pp. 358–368.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Patarin, J., Goubin, L. (1997). Trapdoor one-way permutations and multivariate polynomials. In: Han, Y., Okamoto, T., Qing, S. (eds) Information and Communications Security. ICICS 1997. Lecture Notes in Computer Science, vol 1334. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028491
Download citation
DOI: https://doi.org/10.1007/BFb0028491
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63696-0
Online ISBN: 978-3-540-69628-5
eBook Packages: Springer Book Archive