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. A significant drawback with UOV is that the key size can be large. Typically n, the number of variables, is chosen to be double m, the number of equations. Encoding the coefficients of all these equations in the key requires considerable space, at least 200 kilobytes for a system that would offer security comparable to the Digital Signature Algorithm or Elliptic Curve Digital Signature Algorithm.
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 m {\displaystyle m} equations with n {\displaystyle n} variables. The whole equations system is the public key. To use a mathematical problem for cryptography, it must be modified. The computing of the n {\displaystyle n} 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 T {\displaystyle T} and S {\displaystyle S} and a polynomial vector P ´ {\displaystyle {\acute {P}}} . Both transformations are used to transform elements in certain groups. T {\displaystyle T} transforms y {\displaystyle y} to y 1 , y 2 , . . . , y n {\displaystyle y_{1},y_{2},...,y_{n}} . The second transformation S {\displaystyle S} transforms the variable vector to the valid signature. The third secret element P ´ {\displaystyle {\acute {P}}} provides certain tools for the equations' creation. The equations are built with rules known only to the owner of the signing key.
Signature creation To create a valid signature, the following equations system has to be solved
y 1 = f 1 ( x 1 , … , x n ) y 2 = f 2 ( x 1 , … , x n ) ⋮ y m = f m ( x 1 , … , x n ) {\displaystyle {\begin{aligned}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{aligned}}}
… excerpt ends here. Continue reading the full article.
