SOURCE RECORD · wikipedia
Unbalanced oil and vinegar scheme
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.