UOV and its Variants: Digital Signatures Based on Multivariate Systems

24 Nov

In the previous exploration of multivariate cryptography, we examined how systems of polynomial equations over finite fields can form the basis for cryptographic schemes resistant to quantum computing attacks. The Unbalanced Oil and Vinegar (UOV) scheme is one of the most robust and efficient proposals for constructing digital signatures.

Building on the fundamental concepts we previously discussed — particularly the computational difficulty of solving multivariate quadratic (MQ) systems — UOV is classified among bipolar constructions, introducing an elegant central map design.

Originally developed by Jacques Patarin in 1997 and refined in 1999 following an attack by Kipnis and Shamir, UOV extends the basic construction of Oil and Vinegar by introducing an asymmetry in the core map variables, hence the term “unbalanced”. This asymmetry has proven essential for avoiding algebraic attacks that had compromised the original balanced version.

Unbalanced Oil and Vinegar

The primary characteristic of Oil and Vinegar (OV) constructions lies in the specific structure of the core map $\mathcal{F} = (f^{(1)}, \ldots, f^{(m)}) \colon \mathbb{F}_q^n \to \mathbb{F}_q^m$ , where each component $f^{(k)}$ is a polynomial of the form

$\begin{equation*} f^{(k)}(\mathbf{x}) = \sum_{i=1}^{n-m} \sum_{j=1}^{n-m} \alpha_{i,j}^{(k)}x_i x_j + \sum_{i=1}^{n-m} \sum_{j=n-m+1}^{n} \beta_{i,j}^{(k)}x_i x_j + \sum_{i=1}^{n} \gamma_{i}^{(k)}x_i + \delta^{(k)}. \end{equation*}$

The distinctive feature of these polynomials is the absence of quadratic terms in the last $m$ variables. This property makes the core map $\mathcal{F}$ easily invertible, enabling its use in bipolar constructions. Specifically, once the first $n-m$ variables are randomly fixed, what remains is a linear system of $m$ equations in $m$ variables, for which a solution typically exists and can be efficiently computed using Gaussian elimination. In the unlikely case that the system lacks a solution, the process can be repeated with a new random assignment of values to the first $n-m$ variables.

Patarin named this scheme Oil and Vinegar to describe the behavior of the variables involved. Indeed, within the polynomials $f^{(1)}, \ldots, f^{(m)}$
the first $n-m$ variables, called vinegar variables, never completely mix with the last $m$ variables, termed oil variables. This separation mirrors what happens in cooking, where oil and vinegar do not blend uniformly.

Typically, in practical applications, the central map $\mathcal{F}$ is chosen to have homogeneous components, meaning that the polynomials $f^(k)$ have coefficients $\gamma_i^{(k)}=\delta^{(k)}=0$ . We will adopt the same convention in the following discussion.

Initially, Patarin proposed using a central map with $n=2m$ resulting in an equal number of oil and vinegar variables. However, in 1999, Kipnis and Shamir highlighted a vulnerability arising from this configuration. Consequently, modern versions of the scheme employ a greater number of vinegar variables than oil variables, i.e., $n>2m$ , hence the name “Unbalanced” Oil and Vinegar.

Modern description of UOV

Recently, Beullens proposed an alternative, yet equivalent, description of the UOV scheme. This new description emerged following recent cryptanalysis attempts and proved instrumental in mounting an attack on the Rainbow scheme, one of the participants in the PQC competition convened by NIST. Instead of relying on the concept of an easily invertible central map $\mathcal{F}$ , Beullens’ description bases the construction of the private key on specific properties of the public key $\mathcal{P}$ .

More specifically, the map $\mathcal{P}$ can be inverted by knowing a subset $\mathcal{O} \subset \mathbb{F}_q^n$ of dimension $m$ on which $\mathcal{P}$ vanishes, i.e., such that

$\mathcal{P}(\mathbf{o})=\mathbf{0} \ \mbox{for each} \ \mathbf{o} \in \mathcal{O}.$

Consequently, while the public key remains the map $\mathcal{P}$ , the private key is simply a basis of the space $\mathcal{O}$ .

To understand how knowledge of the space $\mathcal{O}$ enables finding a solution to the system $\mathcal{P}(\mathbf{x})=\mathbf{t}$ , it is necessary to introduce the concept of the polar form. For a homogeneous multivariate quadratic polynomial $f: \mathbb{F}_q^n \to \mathbb{F}_q$ , its polar form is a multivariate polynomial $\bar{f}\colon\mathbb{F}_q^n \times \mathbb{F}_q^n \to \mathbb{F}_q$ defined as

$\Bar{f}(\mathbf{x}, \mathbf{y}) := f(\mathbf{x} + \mathbf{y}) - f(\mathbf{x}) -f(\mathbf{y}).$

The polar form of a homogeneous multivariate quadratic map $\mathcal{F} = (f^{(1)}, \ldots, f^{(m)}) \colon \mathbb{F}_q^n \to \mathbb{F}_q^m$ is a multivariate quadratic map $\mathcal{\Bar{F}} = (\Bar{f}^{(1)}, \ldots, \Bar{f}^{(m)}) \colon \mathbb{F}_q^n \times \mathbb{F}_q^n \to \mathbb{F}_q^m$ where each component is the polar form of the corresponding components of the original map $\mathcal{F}$ .

An extremely important property of the polar form of a quadratic map is that it is bilinear, meaning it is linear with respect to both inputs.

Given the map $\mathcal{P}$ and a space $\mathcal{O}$ of dimension $m$ on which $\mathcal{P}$ vanishes, a solution to $\mathcal{P}(\mathbf{x})=\mathbf{t}$ can be found as follows. The first step is to randomly select an element $\mathbf{v}$ in $\mathbb{F}_q^n$ .
Then, we attempt to find a solution of the form $\mathbf{v}+\mathbf{o}$ for some $\mathbf{o} \in \mathcal{O}$ . This strategy transforms the problem of finding an element $\mathbf{x}$ such that $\mathcal{P}(\mathbf{x})=\mathbf{t}$ into the problem of finding an element $\mathbf{o} \in \mathcal{O}$ such that $\mathcal{P}(\mathbf{v}+\mathbf{o})=\mathbf{t}$ .

Using the concept of polar form, the last equation can be broken down as follows:

$\mathcal{P}(\mathbf{v}+\mathbf{o}) = \mathcal{P}(\mathbf{v}) + \mathcal{P}(\mathbf{o}) + \mathcal{\bar{P}}(\mathbf{v},\mathbf{o})=\mathbf{t}.$

Note that $\mathcal{P}(\mathbf{v})$ is a fixed and known element, $\mathcal{P}(\mathbf{o})= \mathbf{0}$ by the definition of $\mathcal{O}$ , and $\mathcal{\bar{P}}(\mathbf{v},\mathbf{o})$ is a linear map in $\mathbf{o}$ becuase $\mathbf{v}$ is fixed and the polar forms are bilinear. Consequently, solving the system $\mathcal{P}(\mathbf{x})=\mathbf{t}$ reduces to finding a solution to a linear system.

With high probability, the resulting system has a unique solution, and in this case, it can be obtained using Gaussian elimination. If this is not the case, the process can be repeated by selecting a new value for $\mathbf{v}$ different from the previously chosen one.

Rainbow and MAYO

Confidence in the security of the UOV scheme has inspired numerous researchers to come up with variants with the aim of reducing its key size and improving its usability.

A well-known variant of UOV is the Rainbow signature scheme, in which several UOV levels are combined, resulting in smaller keys and better performance.
Unlike UOV, in which the private key is represented by a single subspace, the Rainbow private key is described by three distinct subspaces $\mathcal{O}_1, \mathcal{O}_2, \mathcal{W}$ , which satisfy the following properties:

$\mathcal{O}_2\subset\mathcal{O}_1\subset\mathbb{F}_q^n$ and $\mathcal{W}\subset\mathbb{F}_q^m$ ,
$\dim(\mathcal{O}_2)=\dim(\mathcal{W})$ , $\dim(\mathcal{O}_1)=m$ ,
for all $\mathbf{o}_2\in\mathcal{O}_2$ and $\mathbf{x}\in\mathbb{F}_q^n$ , it holds $\mathcal{P}(\mathbf{o}_2)=0$ and $\mathcal{P}'(\mathbf{x},\mathbf{o}_2)\in\mathcal{W}$ ,
for all $\mathbf{o}_1\in\mathcal{O}_1$ it holds $\mathcal{P}(\mathbf{o}_1)\in\mathcal{W}.$

This layered structure — summarised in the diagram below — gives Rainbow a more complex trapdoor, which has attracted strong interest from the cryptographic community and led to important advances in the cryptanalysis of these schemes.

However, during the third round of the NIST competition, Rainbow was withdrawn following the discovery of an attack by Beullens. Although it is possible to mitigate this attack by increasing the size of the parameters, the resulting scheme would still not be really usable due to the excessive size of the keys and an overall reduced efficiency compared to the standard version of UOV.

Despite attempts at improvement, UOV still remains the most robust and efficient unstructured multivariate proposal for constructing digital signatures. The vulnerability identified in Rainbow, in fact, does not affect the security of the original UOV scheme, but on the contrary provides new clues on the strength of the underlying assumption.

The feasibility of reducing the key size of UOV by introducing more structure continued to be analysed in subsequent schemes.
In 2017, the Lifted UOV (LUOV) variant was proposed and participated in the first NIST process until, during the second round, the lifting structure on which it is based proved to be insecure.
Subsequently, in 2021, Beullens again sparked new interest in this approach with the MAYO scheme.
The idea behind MAYO is to allow the choice of an “Oil” secret space with a dimension $o$ smaller than $m$ , in order to achieve smaller key sizes than the original UOV scheme.

To achieve this, it would be sufficient for the signature generation process to involve solving a linear system of $m$ equations in $o < m$ variables. But since such a system with high probability does not admit a solution, its use would cause the signature generation algorithm to fail.

MAYO addresses this problem by proposing a “whipping transformation” (from which the scheme takes its name) which extends the quadratic map $\mathcal{P}\colon\mathbb{F}_q^n\to \mathbb{F}_q^m$ into a map $\mathcal{P}^*\colon\mathbb{F}_q^{kn}\to \mathbb{F}_q^m$ , with $k$ integer. The extended map $\mathcal{P}^*$ is constructed in such a way that it cancels on Oil space, itself extended, of dimension $ko \ge m$ , thus allowing the resolution of the linear system required for the signature.

More precisely, after randomly choosing an Oil subspace $\mathcal{O}\subset \mathbb{F}^n$ of dimension $o < m$ , a public UOV map $\mathcal{P}\colon\mathbb{F}_q^n\to \mathbb{F}_q^m$ is constructed such that $\mathcal{P}(\mathcal{O})=0$ . In this way from $\mathcal{P}$ it is always possible to derive a map $\mathcal{P}^*$ that cancels on $\mathcal{O}^k\subset \mathbb{F}_q^{kn}$ .
This procedure makes it possible to transform a UOV map with $o < m$ , which is unusable for creating signature schemes directly, into a useful map that cancels on a space of size at least $m$ .

UOV in the NIST competition

The first post-quantum scheme selection competition, held by NIST in 2017, featured two UOV-based schemes: LUOV and Rainbow. Although both of these schemes turned out to be partially insecure and were not selected for standardisation, their analysis was crucial for the design and definition of the most recent proposals.

In 2023, NIST started a new competition dedicated to post-quantum signatures, with the aim of diversifying security assumptions. Of the 40 submissions accepted in the first round, 11 are based on multivariate assumptions. Among the latter, there are 7 submissions directly based on or derived from UOV.
Some of the new constructions present only minor variations from the original scheme (e.g. Provable and Triangular UOV).
Others, such as MAYO, SNOVA and QR-UOV, introduce substantial changes to improve the efficiency and compactness of the original construction.
In October 2024, following the passage to the second round of the competition, NIST selected the original version of UOV and all structured variants for a new, more focused analysis phase.

Generally, UOV and its closest variants are considered unstructured multivariate schemes, characterised by good robustness and efficiency but with high public key sizes. The introduction of more structure within the problem makes it possible to significantly reduce the key size. On the other hand, such approaches require special attention, as this same structure could be exploited for new cryptanalytic attacks, as was the case with Rainbow.
Currently, no vulnerabilities have been revealed for any of the new proposals submitted to NIST.

sig_plot_eng — The figure shows a graph of the size of signatures and public keys, comparing UOV-based schemes as the security parameter varies. To simplify the comparison, different symbols have been used for structured and unstructured variants.

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Federica Zanetti, holds a bachelor’s degree in Mathematics from the University of Trento, where she is currently pursuing a Master’s degree with a specialization in Cryptography. From June to October 2024, she was an intern at Telsy in the Cryptography Research Group.

Edoardo Signorini, Cryptography Specialist at Telsy, where he has been part of the Cryptography Research Group since 2020. He received his PhD in Pure and Applied Mathematics from the Polytechnic University of Turin in 2024 with a thesis on Post-Quantum Digital Signature Aggregation. His work focuses on research in the area of Post-Quantum Cryptography and the analysis and development of cryptographic protocols.