Multivariate cryptography

Last updated January 27, 2024

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 the degree two, we talk about multivariate quadratics. Solving systems of multivariate polynomial equations is proven to be NP-complete.^[1] 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.

History

TsutomuMatsumotoand Hideki Imai ( 1988 ) presented their so-called C* scheme at the Eurocrypt conference. Although C* has been broken by JacquesPatarin ( 1995 ), 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 Patarin in 1996, remains a popular multivariate scheme today [P96]. The security of HFE has been thoroughly investigated, beginning with a direct Gröbner basis attack [FJ03, GJS06], key-recovery attacks ( Kipnis & Shamir 1999 ) [BFP13], 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, Patarin developed other schemes. In 1997 he presented “Balanced Oil & Vinegar” and in 1999 “Unbalanced Oil and Vinegar”, in cooperation with Aviad Kipnis and Louis Goubin ( Kipnis, Patarin & Goubin 1999 ).

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)
Four multivariate cryptography signature schemes (GeMMS, LUOV, Rainbow and MQDSS) have made their way into the 2nd round of the NIST post-quantum competition: see slide 12 of the report.^[2]

Related Research Articles

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography to provide equivalent security.

In mathematics, the discriminant of a polynomial is a quantity that depends on the coefficients and allows deducing some properties of the roots without computing them. More precisely, it is a polynomial function of the coefficients of the original polynomial. The discriminant is widely used in polynomial factoring, number theory, and algebraic geometry.

<span class="mw-page-title-main">Quadratic function</span> Polynomial function of degree two

In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before the 20th century, the distinction was unclear between a polynomial and its associated polynomial function; so "quadratic polynomial" and "quadratic function" were almost synonymous. This is still the case in many elementary courses, where both terms are often abbreviated as "quadratic".

A birthday attack is a bruteforce collision attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties. The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes). With a birthday attack, it is possible to find a collision of a hash function with $chance in, with being the classical preimage resistance security with the same probability. There is a general result that quantum computers can perform birthday attacks, thus breaking collision resistance, in .$

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization.

In cryptography, the eXtended Sparse Linearization (XSL) attack is a method of cryptanalysis for block ciphers. The attack was first published in 2002 by researchers Nicolas Courtois and Josef Pieprzyk. It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard (AES) cipher, also known as Rijndael, faster than an exhaustive search. Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.

<span class="mw-page-title-main">Boolean function</span> Function returning one of only two values

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

Hidden Fields Equations (HFE), also known as HFE trapdoor function, is a public key cryptosystem which was introduced at Eurocrypt in 1996 and proposed by (in French)Jacques Patarin following the idea of the Matsumoto and Imai system. It is based on polynomials over finite fields $of different size to disguise the relationship between the private key and public key. HFE is in fact a family which consists of basic HFE and combinatorial versions of HFE. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate quadratic equations since it uses private affine transformations to hide the extension field and the private polynomials. Hidden Field Equations also have been used to construct digital signature schemes, e.g. Quartz and Sflash.$

In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers.

In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

A hash chain is the successive application of a cryptographic hash function to a piece of data. In computer security, a hash chain is a method used to produce many one-time keys from a single key or password. For non-repudiation, a hash function can be applied successively to additional pieces of data in order to record the chronology of data's existence.

In cryptography, the QUAD cipher is a stream cipher which was designed with provable security arguments in mind.

In cryptography, the unbalanced oil and vinegar (UOV) scheme is a modified version of the oil and vinegar scheme designed by J. Patarin. Both are digital signature protocols. They are forms of multivariate cryptography. The security of this signature scheme is based on an NP-hard mathematical problem. To create and validate signatures, a minimal quadratic equation system must be solved. Solving $m$ equations with $n$ variables is NP-hard. While the problem is easy if $m$ is either much much larger or much much smaller than $n$ , importantly for cryptographic purposes, the problem is thought to be difficult in the average case when $m$ and $n$ are nearly equal, even when using a quantum computer. Multiple signature schemes have been devised based on multivariate equations with the goal of achieving quantum resistance.

An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication. While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group $, of elliptic curves over a finite field, where q = p k and p is a prime. The DLP, as it has come to be known, is a widely used approach to public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p -adic methods exist.$

The Coppersmith method, proposed by Don Coppersmith, is a method to find small integer zeroes of univariate or bivariate polynomials modulo a given integer. The method uses the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) to find a polynomial that has the same zeroes as the target polynomial but smaller coefficients.

Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe or quantum-resistant, is the development of cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems could be easily solved on a sufficiently powerful quantum computer running Shor's algorithm or even faster and less demanding alternatives.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

In cryptography, a round or round function is a basic transformation that is repeated (iterated) multiple times inside the algorithm. Splitting a large algorithmic function into rounds simplifies both implementation and cryptanalysis.

References

↑ Garey, Michael R. (1979). Computers and intractability : a guide to the theory of NP-completeness. Johnson, David S., 1945-. San Francisco: W.H. Freeman. ISBN 0-7167-1044-7. OCLC 4195125.
↑ Moody, Dustin. "The 2nd Round of the NIST PQC Standardization Process". NIST. Retrieved 11 October 2020.

[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.
Kipnis, Aviad; Shamir, Adi (1999). "Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization". Advances in Cryptology – CRYPTO' 99. Berlin, Heidelberg: Springer. doi:10.1007/3-540-48405-1_2. ISBN 978-3-540-66347-8. ISSN 0302-9743. MR 1729291.
Kipnis, Aviad; Patarin, Jacques; Goubin, Louis (1999). "Unbalanced Oil and Vinegar Signature Schemes" (PDF). In Jacques Stern (ed.). Advances in Cryptology – CRYPTO' 99. Eurocrypt'99. Springer. doi: 10.1007/3-540-48910-x_15 . ISBN 3-540-65889-0. ISSN 0302-9743. MR 1717470.
Matsumoto, Tsutomu; Imai, Hideki (1988). "Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. doi:10.1007/3-540-45961-8_39. ISBN 978-3-540-50251-7. ISSN 0302-9743. MR 0994679.
Patarin, Jacques (1995). "Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88". Advances in Cryptology – CRYPT0' 95. Lecture Notes in Computer Science. Vol. 963. Berlin, Heidelberg: Springer. pp. 248–261. doi:10.1007/3-540-44750-4_20. ISBN 978-3-540-60221-7. ISSN 0302-9743. MR 1445572.
[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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Garey, Michael R. (1979). Computers and intractability : a guide to the theory of NP-completeness. Johnson, David S., 1945-. San Francisco: W.H. Freeman. ISBN 0-7167-1044-7. OCLC 4195125.

[2] Moody, Dustin. "The 2nd Round of the NIST PQC Standardization Process". NIST. Retrieved 11 October 2020.

[1]

[2]