Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field
Contents
History
In 1988, T. Matsumoto and H. Imai [MI88] presented their so-called C* scheme at the Eurocrypt conference. Although the C* has been broken [P95], the general principle of Matsumoto and Imai inspired a whole generation of researchers that proposed improved variants based on that original blueprint On later work the "Hidden Monomial Cryptosystems" was developed by (French) Jacques Patarin. It is based on a ground and an extension field. In particular, "Hidden Field Equations" (HFE), developed by (French) Jacques Patarin in 1996, remains probably today the most popular multivariate scheme [P96]. The security of HFE has been thoroughly investigated starting from a direct Gröbner basis attack [FJ03,GJS06], key-recovery attacks [KS99b,BFP13], .... The plain version of HFE is considered to be practically broken in the sense that secure parameters lead to an impractical scheme. However, some simple variants of HFE such as the minus variant and the vinegar variant allow to strengthen the basic HFE against all known attacks.
Besides HFE, J. Patarin developed other schemes . In 1997 he presented “Balanced Oil & Vinegar” and 1999 “Unbalanced Oil and Vinegar” in cooperation with Aviad Kipnis and Louis Goubin [KS99a].
Construction
Multivariate Quadratics involves a public and a private key. The private key consists of two affine transformations, S and T, and an easy to invert quadratic map P’
The triple
Signature
Signatures are generated using the private key and are verified using the public key as follows. The message is hashed to a vector in
The receiver of the signed document must have the public key P in possession. He computes the hash y and checks that the signature x fulfils