Multivariate cryptography

Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field F {displaystyle F} . In certain cases those polynomials could be defined over both a ground and an extension field. If the polynomials have the degree two, we talk about multivariate quadratics. Solving systems of multivariate polynomial equations is proven to be NP-hard or NP-complete. That's why those schemes are often considered to be good candidates for post-quantum cryptography. Multivariate cryptography has been very productive in terms of design and cryptanalysis. Overall, the situation is now more stable and the strongest schemes have withstood the test of time. It is commonly admitted that Multivariate cryptography turned out to be more successful as an approach to build signature schemes primarily because multivariate schemes provide the shortest signature among post-quantum algorithms. Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field F {displaystyle F} . In certain cases those polynomials could be defined over both a ground and an extension field. If the polynomials have the degree two, we talk about multivariate quadratics. Solving systems of multivariate polynomial equations is proven to be NP-hard or NP-complete. That's why those schemes are often considered to be good candidates for post-quantum cryptography. Multivariate cryptography has been very productive in terms of design and cryptanalysis. Overall, the situation is now more stable and the strongest schemes have withstood the test of time. It is commonly admitted that Multivariate cryptography turned out to be more successful as an approach to build signature schemes primarily because multivariate schemes provide the shortest signature among post-quantum algorithms. In 1988, T. Matsumoto and H. Imai presented their so-called C* scheme at the Eurocrypt conference. Although C* has been broken , the general principle of Matsumoto and Imai has inspired a generation of improved proposals. In later work, the 'Hidden Monomial Cryptosystems' was developed by (in French) Jacques Patarin. It is based on a ground and an extension field. 'Hidden Field Equations' (HFE), developed by (in French) Jacques Patarin in 1996, remains a popular multivariate scheme today . The security of HFE has been thoroughly investigated, beginning with a direct Gröbner basis attack , key-recovery attacks , and more. 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 one to strengthen the basic HFE against all known attacks. In addition to 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 . 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’ P ′ : F m → F n {displaystyle P':F^{m} ightarrow F^{n}} . We denote the n {displaystyle n} by n {displaystyle n} matrix of the affine endomorphisms S : F n → F n {displaystyle S:F^{n} ightarrow F^{n}} by M S {displaystyle M_{S}} and the shift vector by v S ∈ F n {displaystyle v_{S}in F^{n}} and similarly for T : F m → F m {displaystyle T:F^{m} ightarrow F^{m}} . In other words, The triple ( S − 1 , P ′ − 1 , T − 1 ) {displaystyle (S^{-1},{P'}^{-1},T^{-1})} is the private key, also known as the trapdoor. The public key is the composition P = S ∘ P ′ ∘ T {displaystyle P=Scirc P'circ T} which is by assumption hard to invert without the knowledge of the trapdoor. Signatures are generated using the private key and are verified using the public key as follows. The message is hashed to a vector in y ∈ F n {displaystyle yin F^{n}} via a known hash function. The signature is x = P − 1 ( y ) = T − 1 ( P ′ − 1 ( S − 1 ( y ) ) ) {displaystyle x=P^{-1}(y)=T^{-1}left({P'}^{-1}left(S^{-1}(y) ight) ight)} . 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 P ( x ) = y {displaystyle P(x)=y} .