Unbalanced Oil and Vinegar


Unbalanced Oil and Vinegar

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 stays even with a real existing quantum computer NP-hard. Therefore the signature schemes based on multivariate equations systems are quantum resistant signature schemes.

Public and Private Key

Every asymmetric scheme has a public and a private key (Public-key cryptography). 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 m equations with n 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 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 gets insert in the equations system. This trapdoor is the private key. It consists of three parts: Two Affine transformations T and S and a polynomial vector acute{P}. Both transformations are used to transform elements in certain groups. T transforms y to y_1,y_2,...,y_n. The second transformation S transforms the variable vector to the valid signature.
The third secret element acute{P} 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

y_1={f_1}^{}(x_1,...,x_n)
y_2=f_2^{}(x_1,...,x_n)
...
y_n = f_n^{}(x_1,...,x_n)

Here the y=(y_1,y_2,...,y_m) is a given message which should be signed. The valid signature is x = (x_1,x_2,...,x_n).
To sign a given y certain steps have to be performed. At first the message has to be transformed to fit in the equations system. T is used to "split" the message to acceptable pieces y_1, y_2, ..., y_n. Then the equations have to be build. Every single equation has the same form:

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

The next steps sign a given message y and the result is a valid signature x.

# The secret coefficients (gamma_{ijk}, lambda_{ijk}, xi_{ij}, acute {xi}_{ij}, delta_i) must be chosen secretly.
# The vinegar variables (acute{a}_j) are chosen randomly
# The resulting linear equations system gets solved for the oil variables (a_i)

The vinegar and oil variables build the pre-signature A = (a_1,...,a_n,acute{a}_1,...,acute{a}_v). Finally A gets transformed by the private affine transformation S to x, the valid signature. x= S^{-1}(A)
The great advantage is, that the equations system get linear if the vinegar variables are fixed. No oil variable is multiplied with an other 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.

y_1 = {f_1}^*(x_1, x_2, ..., x_n)
y_2 = {f_2}^*(x_1, x_2, ..., x_n)
...
y_m = {f_m}^*(x_1, x_2, ...,x _n )

This equations system is a slight modified version of the system needed for signature creation. It is modified, because an attacker should not get informations 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 y_i 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 build, 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, which 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).

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 m equations to compute y_1,...,y_m and compare it with the original message. The public key is in the range of some Kilobyte.
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 purpose.

References

* [http://eprint.iacr.org/2004/297.pdf Buchmann, Johannes; Coronado, Carlos; Doring, Martin; Engelbert, Daniela; Ludwig, Christoph; Overbeck, Raphael; Schmidt, Arthur; Vollmer, Ulrich; Weinmann, Ralf-Philipp: Post-Quantum Signatures, -, October 29. 2004]
* [http://www.win.tue.nl/diamant/symposium05/abstracts/wolf.pdf Wolf, Christopher: Multivariate Quadratic Polynomials in Public Key Cryptography, DIAMANT/EIDMA symposium 2005]
* [http://citeseer.ist.psu.edu/707018.html Braeken, An; Wolf, Christopher; Preneel, Bart: A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes, ESAT-COSIC, September 2. 2004]
* [http://www.ecrypt.eu.org/documents/D.AZTEC.6.pdf Coron, Jean-Sebastien; de Weger, Benne: Hardness of the Main Computational Problems Used in Cryptography, ECRYPT D.AZTEC.6, March 14. 2007]
* [http://citeseer.ist.psu.edu/kipnis99unbalanced.html Kipnis, Aviad: Unbalanced Oil and Vinegar Signature Schemes - extended version, EURO-CRYPT, 1999]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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… …   Wikipedia

  • 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… …   Wikipedia

  • Jacques Patarin — est un cryptologue français né en 1965, ancien élève de l École Centrale (promotion 1987) et actuellement professeur à l université de Versailles Saint Quentin en Yvelines. Thèmes de recherche Jacques Patarin travaille à la fois aux problèmes… …   Wikipédia en Français

  • china — /chuy neuh/, n. 1. a translucent ceramic material, biscuit fired at a high temperature, its glaze fired at a low temperature. 2. any porcelain ware. 3. plates, cups, saucers, etc., collectively. 4. figurines made of porcelain or ceramic material …   Universalium

  • China — /chuy neuh/, n. 1. People s Republic of, a country in E Asia. 1,221,591,778; 3,691,502 sq. mi. (9,560,990 sq. km). Cap.: Beijing. 2. Republic of. Also called Nationalist China. a republic consisting mainly of the island of Taiwan off the SE coast …   Universalium


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.