Abstract
In [4], H. Imai and T. Matsumoto presented new candidate trapdoor one-way permutations with a public key given as multivariate polynomials over a finite field. One of them, based on the idea of hiding a monomial field equation, was later presented in [7] under the name C *. It was broken by J. Patarin in [8]. J. Patarin and L. Goubin then suggested ([9], [10], [11], [12]) some schemes to repair C *, but with slightly more complex public key or secret key computations. In part I, we study some very simple variations of C * — such as C *−+ — where the attack of [8] is avoided, and where the very simple secret key computations are kept. We then design some new cryptanalysis that are efficient against some of — but not all — these variations.
[C] is another scheme of [4], very different from C * (despite the name), and based on the idea of hiding a monomial matrix equation. In part II, we show how to attack it (no cryptanalysis had been published so far). We then study more general schemes, still using the idea of hiding matrix equations, such as HM.
An extended version of this paper can be obtained from the authors.
Chapter PDF
Similar content being viewed by others
References
D. Coppersmith, S. Winograd, Matrix Multiplication via Arithmetic Progressions, J. Symbolic Computation, 1990, vol. 9, pp. 251–280.
J.C. Faugere, Rough evaluation (personal communication).
F.R. Gantmacher, The Theory of Matrices, volume 1, Chelsae Publishing Company, New-York.
H. Imai, T. Matsumoto, Algebraic Methods for Constructing Asymmetric Cryptosystems, Algebraic Algorithms and Error Correcting Codes (AAECC-3), Grenoble, 1985, Lectures Notes in Computer Science nℴ 229, pp.108–119.
N. Koblitz, Algebraic Aspects of Cryptography, Algorithms and Computation in Mathematics, Volume 3, Springer, 1998.
R. Lidl, H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its applications, Volume 20, Cambridge University Press.
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.
J. Patarin, Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88, Advances in Cryptology, Proceedings of CRYPTO’95, Springer, 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, pp. 33–48.
J. Patarin, Asymmetric Cryptography with a Hidden Monomial, Advances in Cryptology, Proceedings of CRYPTO’96, Springer, pp. 45–60.
J. Patarin, L. Goubin, Trapdoor One-way Permutations and Multivariate Polynomials, Proceedings of ICICS’97, Springer, LNCS nℴ 1334, pp. 356–368.
J. Patarin, L. Goubin, Asymmetric Cryptography with S-Boxes, Proceedings of ICICS’97, Springer, LNCS nℴ1334, pp. 369–380.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patarin, J., Goubin, L., Courtois, N. (1998). C *−+ and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai. In: Ohta, K., Pei, D. (eds) Advances in Cryptology — ASIACRYPT’98. ASIACRYPT 1998. Lecture Notes in Computer Science, vol 1514. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49649-1_4
Download citation
DOI: https://doi.org/10.1007/3-540-49649-1_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65109-3
Online ISBN: 978-3-540-49649-6
eBook Packages: Springer Book Archive