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,[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. 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.
-Problems and advantages
A primary advantage is that the mathematical problem to be solved in the algorithm is quantum-resistant. When 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
m
{\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.[2] Beullens discovered a new attack in 2022, which recovers the private key for the Rainbow L1 parameterset in a weekend.[3] UOV itself is not affected by this attack.
https://en.wikipedia.org/wiki/Unbalanced_oil_and_vinegar_scheme
