Unbalanced Oil and Vinegar

From HandWiki

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 schemes. They belong to the group 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 equations system must be solved. Solving m equations with n variables is an NP-hard problem, which means the problem is almost certainly difficult to solve efficiently in the worst case, even when using a quantum computer. While the problem is easy if m is either much much larger or much much smaller than n,[1] 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. As a result, a number of signature schemes have been devised based on multivariate equations with the goal of achieving quantum resistant signatures.

Signing and Verification Key

A signature scheme has a signing key, which is kept private, and a verification key, which is publicly revealed. For instance, in signature schemes based on RSA the keys are both exponents. In the UOV scheme, and in every other multivariate signature scheme the keys are more complex.

The mathematical problem is to solve [math]\displaystyle{ m }[/math] equations with [math]\displaystyle{ n }[/math] variables. The whole equations system is the public key.

To use a mathematical problem for cryptography it must be modified. The computing of the [math]\displaystyle{ n }[/math] variables would need a lot of resources. A standard computer isn't able to compute this in an acceptable time. Therefore, a special Trapdoor is inserted into the equations system. This trapdoor is the signing key. It consists of three parts: Two affine transformations [math]\displaystyle{ T }[/math] and [math]\displaystyle{ S }[/math] and a polynomial vector [math]\displaystyle{ \acute{P} }[/math]. Both transformations are used to transform elements in certain groups. [math]\displaystyle{ T }[/math] transforms [math]\displaystyle{ y }[/math] to [math]\displaystyle{ y_1,y_2,...,y_n }[/math]. The second transformation [math]\displaystyle{ S }[/math] transforms the variable vector to the valid signature.

The third secret element [math]\displaystyle{ \acute{P} }[/math] provides certain tools for the equations' creation. The equations are built with certain rules known only to the owner of the signing key.

Creation of a signature

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

[math]\displaystyle{ \begin{align} y_1 & = f_1(x_1, \ldots, x_n) \\ y_2 & = f_2(x_1, \ldots, x_n) \\ & ~ \vdots \\ y_m & = f_m(x_1, \ldots, x_n) \\ \end{align} }[/math]

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

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

[math]\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 }[/math]

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

  1. The coefficients, [math]\displaystyle{ \gamma_{ijk}, \lambda_{ijk}, \xi_{ij}, \acute{\xi}_{ij}, \delta_i }[/math], must be chosen secretly.
  2. The vinegar variables ([math]\displaystyle{ \acute{a}_j }[/math]) are chosen randomly
  3. The resulting linear equations system gets solved for the oil variables ([math]\displaystyle{ a_i }[/math])

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

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.

Validation of a signature

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

[math]\displaystyle{ \begin{align} y_1 & = {f_1}^*(x_1, x_2, \ldots, x_n) \\ y_2 & = {f_2}^*(x_1, x_2, \ldots, x_n) \\ & ~ \vdots \\ y_m & = {f_m}^*(x_1, x_2, \ldots,x _n ) \\ \end{align} }[/math]

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 [math]\displaystyle{ y_i }[/math] is equal to the corresponding part of the original message, then the verification succeeded.

Problems and advantages of the UOV scheme

A primary advantage is that the mathematical problem to be solved in the algorithm is quantum-resistant. That is, if someday a quantum computer is built that can handle enough states to break commercial signature schemes like RSA or ElGamal, the Unbalanced Oil and Vinegar signature scheme remains secure, as no algorithm currently exists that gives a quantum computer a great advantage in solving these 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 like in smart cards.

A disadvantage is that UOV uses very long key-lengths, with the public key being the entire system of [math]\displaystyle{ m }[/math] equations, which can require several kilobytes of storage. UOV is also a young digital signature scheme. While some attack methods are already known, many more will certainly appear if UOV becomes widely used. It is not yet ready for commercial use because its security requires more research.

References

  1. ↑ Courtois, Nicolas. "Solving Underdefined Systems of Multivariate Equations". http://www.goubin.fr/papers/CG02.pdf. Retrieved 16 October 2016. 




Retrieved from "https://handwiki.org/wiki/index.php?title=Unbalanced_Oil_and_Vinegar&oldid=105407"