Unbalanced Oil and Vinegar
Encyclopedia
The Unbalanced Oil and Vinegar scheme is a modified version of the Oil and Vinegar scheme designed by J. Patarin. Both are Digital signature
schemes, used in Cryptography
. 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 has to be solved. Solving m equations with n variables is an NP-hard problem, even when using a real existing quantum computer
. Therefore the signature schemes based on multivariate equations systems are considered to be quantum resistant.
). In known schemes like RSA the keys are bit strings. In the UOV scheme, and in every other multivariate signature scheme the keys are more complex.
The mathematical problem is to solve
equations with 
variables. The whole equations system is the public key.
To use a mathematical problem for cryptography it has to be modified. The computing of the
variables would need a lot of resources. A standard computer isn't able to compute this in an acceptable time. Therefore a special Trapdoor gets insert in the equations system. This trapdoor is the private key. It consists of three parts: Two Affine transformation
s
and 
and a polynomial vector 
. Both transformations are used to transform elements in certain groups. 
transforms 
to 
. The second transformation 
transforms the variable vector to the valid signature.
The third secret element
provides certain tools for the equations creation. The equations are build with certain rules which are only known to the owner of the private key.
...
Here the
is a given message which should be signed. The valid signature is 
.
To sign a given
certain steps have to be performed. At first the message has to be transformed to fit in the equations system. 
is used to "split" the message to acceptable pieces 
. Then the equations have to be built.
Every single equation has the same form:
The next steps sign a given message
and the result is a valid signature 
.
The vinegar and oil variables build the pre-signature
. Finally 
gets transformed by the private affine transformation 
to 
, the valid signature. 
The great advantage is, that the equations system get 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 for example with the help of the Gaussian reduction algorithm. The signature creation is fast and computational easy.
This equations system is a slight modified version of the system needed for signature creation. It is modified, because an attacker should not get information about the secret coefficients and the special formatting of the oil and vinegar variables. Every equation of these public key has to be solved, to validate the signature. The input is the signature itself. If every result
is equal to the corresponding part of the original message, the verification succeeded.
The second advantage are the inner operations. Signatures get created and validated only with addition and multiplication of "small" values. Especially for systems with very small resources this signature scheme may be interesting (Smart card
).
Problems of this signature scheme are the key-lengths. The public key is a whole equations system. Someone who wants to verify a signature needs all
equations to compute 
and compare it with the original message. The public key is in the range of some Kilobyte
s.
The UOV scheme is a young digital signature scheme. Some attacks are known and prevented at present, but certainly in the next years other attacks will follow. The actual state of the art can't be used for commercial purposes.
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
schemes, used in Cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. They belong to the group of multivariate cryptography
Multivariate Cryptography
Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over finite fields. In certain cases those polynomials could be defined over both a ground and an extension field. If the polynomials have the degree two, we talk about...
. The security of this signature scheme is based on an NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
mathematical problem. To create and validate signatures a minimal quadratic equations system has to be solved. Solving m equations with n variables is an NP-hard problem, even when using a real existing quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
. Therefore the signature schemes based on multivariate equations systems are considered to be quantum resistant.
Public and Private Key
Every asymmetric scheme has a public and a private key (Public-key cryptographyPublic-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
). In known schemes like RSA the keys are bit strings. In the UOV scheme, and in every other multivariate signature scheme the keys are more complex.
The mathematical problem is to solve
equations with variables. The whole equations system is the public key.To use a mathematical problem for cryptography it has to be modified. The computing of the
variables would need a lot of resources. A standard computer isn't able to compute this in an acceptable time. Therefore a special Trapdoor gets insert in the equations system. This trapdoor is the private key. It consists of three parts: Two Affine transformationAffine transformation
In geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...
s
and and a polynomial vector . Both transformations are used to transform elements in certain groups. transforms to . The second transformation transforms the variable vector to the valid signature.The third secret element
provides certain tools for the equations creation. The equations are build with certain rules which are only known to the owner of the private key.Creation of a Signature
To create a valid signature the following equations system has to be solved...
Here the
is a given message which should be signed. The valid signature is .To sign a given
certain steps have to be performed. At first the message has to be transformed to fit in the equations system. is used to "split" the message to acceptable pieces . Then the equations have to be built.Every single equation has the same form:
The next steps sign a given message
and the result is a valid signature . - The secret coefficients (
) must be chosen secretly. - The vinegar variables (
) are chosen randomly - The resulting linear equations system gets solved for the oil variables (
)
The vinegar and oil variables build the pre-signature
. Finally gets transformed by the private affine transformation to , the valid signature. The great advantage is, that the equations system get linear
Linear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
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 for example with the help of the Gaussian reduction algorithm. The signature creation is fast and computational 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.This equations system is a slight modified version of the system needed for signature creation. It is modified, because an attacker should not get information about the secret coefficients and the special formatting of the oil and vinegar variables. Every equation of these public key has to be solved, to validate the signature. The input is the signature itself. If every result
is equal to the corresponding part of the original message, the verification succeeded.Problems and Advantages of the UOV scheme
A great advantage is certainly that the mathematical problem, which is used for this signature scheme, is quantum resistant. 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 keeps secure. Today no algorithm exists that gives a quantum computer a great advantage in solving the multivariate equations systems.The second advantage are the inner operations. Signatures get created and validated only with addition and multiplication of "small" values. Especially for systems with very small resources this signature scheme may be interesting (Smart card
Smart card
A smart card, chip card, or integrated circuit card , is any pocket-sized card with embedded integrated circuits. A smart card or microprocessor cards contain volatile memory and microprocessor components. The card is made of plastic, generally polyvinyl chloride, but sometimes acrylonitrile...
).
Problems of this signature scheme are the key-lengths. The public key is a whole equations system. Someone who wants to verify a signature needs all
equations to compute and compare it with the original message. The public key is in the range of some KilobyteKilobyte
The kilobyte is a multiple of the unit byte for digital information. Although the prefix kilo- means 1000, the term kilobyte and symbol KB have historically been used to refer to either 1024 bytes or 1000 bytes, dependent upon context, in the fields of computer science and information...
s.
The UOV scheme is a young digital signature scheme. Some attacks are known and prevented at present, but certainly in the next years other attacks will follow. The actual state of the art can't be used for commercial purposes.