Unbalanced oil and vinegar scheme

Signature creation

To create a valid signature, the following equations system has to be solved

$${\displaystyle \begin{array}{cc}{y}_1& =f_1(x_1,\dots ,x_n)\\ y_2& =f_2(x_1,\dots ,x_n)\\ & ⋮\\ y_m& =f_m(x_1,\dots ,x_n)\end{array}}$$

Here the ${\displaystyle y=(y_1,y_2,\dots ,y_m)}$ is a given message which should be signed. The valid signature is ${\displaystyle x=(x_1,x_2,\dots ,x_n)}$.

To sign a given ${\displaystyle y}$, the message must first be transformed to fit in the equations system. ${\displaystyle T}$ is used to "split" the message to acceptable pieces ${\displaystyle y_1,y_2,\dots ,y_m}$. Then the equations have to be built. Every single equation has the same form:

$${\displaystyle y_i=\sum {\gamma }_{ijk}{a}_j{\acute{a}}_k+\sum {\lambda }_{ijk}{\acute{a}}_j{\acute{a}}_k+\sum {\xi }_{ij}{a}_j+\sum {\acute{\xi }}_{ij}{\acute{a}}_j+{\delta }_i}$$

The next steps sign a given message ${\displaystyle y}$ and the result is a valid signature ${\displaystyle x}$.

1. The coefficients, ${\displaystyle {\gamma }_{ijk},{\lambda }_{ijk},{\xi }_{ij},{\acute{\xi }}_{ij},{\delta }_i}$, must be chosen secretly.
2. The vinegar variables (${\displaystyle {\acute{a}}_j}$) are chosen randomly
3. The resulting linear equations system gets solved for the oil variables (${\displaystyle a_i}$)

The vinegar and oil variables build the pre-signature ${\displaystyle A=(a_1,\dots ,a_n,{\acute{a}}_1,\dots ,{\acute{a}}_v)}$. Finally ${\displaystyle A}$ gets transformed by the private transformation ${\displaystyle S}$ to give the valid signature ${\displaystyle x=S^{-1}(A)}$.

The system of equations becomes linear if the vinegar variables are fixed – no oil variable is multiplied with another oil variable in the equation. Therefore, the oil variables can be computed easily using, for example, a Gaussian reduction algorithm. The signature creation is itself fast and computationally easy.

Signature validation

The signature is transmitted to the communication partner. Validation of the signature is performed with the help of the public key, which is an equations system.

$${\displaystyle \begin{array}{cc}{y}_1& ={f_1}^{\ast }(x_1,x_2,\dots ,x_n)\\ y_2& ={f_2}^{\ast }(x_1,x_2,\dots ,x_n)\\ & ⋮\\ y_m& ={f_m}^{\ast }(x_1,x_2,\dots ,x_n)\end{array}}$$

This system of equations is a slightly modified version of the system needed for signature creation. It is modified so that an attacker cannot get information about the secret coefficients and the special formatting of the oil and vinegar variables. Every equation of the public key has to be solved to validate the signature. The input is the signature itself. If every result ${\displaystyle y_i}$ is equal to the corresponding part of the original message, then the verification succeeded.

Problems and advantages

A primary advantage is that the mathematical problem to be solved in the algorithm is believed to be quantum-resistant. If ever a quantum computer is built that can factor large composite numbers using Shor's Algorithm, this will break commercial signature schemes like RSA or ElGamal that rely upon the discrete logarithm problem being unsolvable. UOV may remain secure because no algorithm is known to give quantum computers a great advantage in solving multivariate systems of equations.

The second advantage is that the operations used in the equations are relatively simple. Signatures get created and validated only with addition and multiplication of "small" values, making this signature viable for low-resource hardware as found in smart cards.

A disadvantage is that UOV uses very long key-lengths, with the public key involving the entire system of ${\displaystyle m}$ equations, which can require several hundred kilobytes. UOV has not been used widely. While several attack methods are already known, more may appear if UOV becomes widely used. UOV is not yet ready for commercial use because its security requires more investigation.

The Rainbow cryptosystem is based on UOV and is one of three finalists in the NIST competition for a post-quantum digital signature standard, though significant concerns have recently been brought to light regarding its security as proposed in the NIST competition. A new MinRank attack against Rainbow was discovered, which reduces the security of the proposed Rainbow instantiation to a level below the requirements set out by NIST. Beullens discovered a new attack in 2022, which recovers the private key for the Rainbow L1 parameterset in a weekend. UOV itself is not affected by this attack.