Summary: In [Eurocrypt 1988, Lect. Notes Comput. Sci. 330, 419–453 (1988; Zbl 0655.94013)] T. Matsumoto and H. Imai described a new asymmetric algorithm based on multivariate polynomials of degree two over a finite field, which was subsequently broken in [the author, Crypto 1995, Lect. Notes Comput. Sci. 963, 248–261 (1995; Zbl 0868.94025)], extended version in [Des. Codes Cryptography 20, No. 2, 175–209 (2000; Zbl 1025.94014)]. Here we present two new families of asymmetric algorithms that so far have resisted all attacks, if properly used: hidden field equations (HFE) and isomorphism of polynomials (IP). These algorithms can be seen as two candidate ways to repair the Matsumoto-Imai algorithm. HFE can be used to do signatures, encryption or authentication in an asymmetric way, with very short signatures and short encryptions of short messages. IP can be used for signatures and for zero knowledge authentication.
An extended version of this paper can be obtained from the author. Another way to repair the Matsumoto-Imai algorithm has been presented in [the author, Crypto 1996, Lect. Notes Comput. Sci. 1109, 45–60 (1996; Zbl 1066.94500)].
For the entire collection see [Zbl 0847.00051].