Multivariate cryptography

Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field F . In certain cases, those polynomials could be defined over both a ground and an extension field. If the polynomials have degree two, we talk about multivariate quadratics. Solving systems of multivariate polynomial equations is proven to be NP-complete. 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 . In certain cases, those polynomials could be defined over both a ground and an extension field. If the polynomials have degree two, we talk about multivariate quadratics. Solving systems of multivariate polynomial equations is proven to be NP-complete. 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. ==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' \colon F^m \rightarrow F^n . We denote the n \times n matrix of the affine endomorphisms S\colon F^n \rightarrow F^n by M_S and the shift vector by v_S \in F^n and similarly for T\colon F^m \rightarrow F^m . In other words, S(x) = M_S x + v_S and T(y) = M_T y + v_T . The triple (S^{-1},{P'}^{-1},T^{-1}) is the private key, also known as the trapdoor. The public key is the composition P = S \circ P' \circ T which is by assumption hard to invert without the knowledge of the trapdoor. ==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 y \in F^n via a known hash function. The signature is x=P^{-1}(y) = T^{-1} \left({P'}^{-1}\left(S^{-1}(y)\right)\right) . 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 . ==Applications== Unbalanced Oil and Vinegar Hidden Field Equations SFLASH by NESSIE Rainbow TTS QUARTZ QUAD (cipher) ==References== [BFP13] L. Bettale, Jean-Charles Faugère, and L. Perret, Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic. DCC'13 [FJ03] Jean-Charles Faugère and A. Joux, Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases. CRYPTO'03 [GJS06] L. Granboulan, Antoine Joux, J. Stern: Inverting HFE Is Quasipolynomial. CRYPTO'06. [P96] Jacques Patarin, Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (extended version); Eurocrypt '96 Christopher Wolf and Bart Preneel, Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations; Current Version: 2005-12-15 An Braeken, Christopher Wolf, and Bart Preneel, A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes, Current Version: 2005-08-06 Jintai Ding, Research Project: Cryptanalysis on Rainbow and TTS multivariate public key signature scheme Jacques Patarin, Nicolas Courtois, Louis Goubin, SFLASH, a fast asymmetric signature scheme for low-cost smartcards. Primitive specification and supporting documentation. Bo-Yin Yang, Chen-Mou Cheng, Bor-Rong Chen, and Jiun-Ming Chen, Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems, 2006 Bo-Yin Yang, Jiun-Ming Chen, and Yen-Hung Chen, TTS: High-Speed Signatures on a Low-Cost Smart Card, 2004 Nicolas T. Courtois, Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash, 2005 Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, 1997 ==External links== The HFE public key encryption and signature [http://www-polsys.lip6.fr/Links/hfeboost.html HFEBoost

Text derived from https://en.wikipedia.org/w/index.php?oldid=1342122953 under CC BY-SA 4.0; modifications have been made.