Multivariate cryptography

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Multivariate cryptography" – news · newspapers · books · scholar · JSTOR (February 2022) (Learn how and when to remove this message)

Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field ${\displaystyle F}$. In certain cases those polynomials could be defined over both a ground and an extension

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 ${\displaystyle P'\colon F^{m}\rightarrow F^{n}}$. We denote the ${\displaystyle n\times n}$ matrix of the affine endomorphisms ${\displaystyle S\colon F^{n}\rightarrow F^{n}}$ by ${\displaystyle M_{S}}$ and the shift vector by ${\displaystyle v_{S}\in F^{n}}$ and similarly for ${\displaystyle T\colon F^{m}\rightarrow F^{m}}$. In other words,

• ${\displaystyle S(x)=M_{S}x+v_{S}}$ and
• ${\displaystyle T(y)=M_{T}y+v_{T}}$.

The triple ${\displaystyle (S^{-1},{P'}^{-1},T^{-1})}$ is the private key, also known as the trapdoor. The public key is the composition ${\displaystyle 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 ${\displaystyle y\in F^{n}}$ via a known hash function. The signature is

${\displaystyle 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 ${\displaystyle y}$ and checks that the signature ${\displaystyle x}$ fulfils ${\displaystyle P(x)=y}$.

Applications

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (August 2018) (Learn how and when to remove this message)

• 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]

References