en>ChrisGualtieri: General Fixes using AWB

2013-10-25T03:38:48Z

General Fixes using AWB

New page

'''Multivariate cryptography''' is the generic term for asymmetric [[Cryptography|cryptographic]] primitives based on [[Polynomial|multivariate polynomials]] over [[finite field]]s. In certain cases those polynomials could be defined over both a ground and an extension [[Field (mathematics)|field]]. If the polynomials have the [[Degree of a polynomial|degree]] two, we talk about multivariate [[Quadratic polynomial|quadratics]]. Solving systems of multivariate [[Polynomial#Polynomial equations|polynomial equations]] is proven to be [[NP-Hard]] or [[NP-Complete]]. That's why those schemes are often considered to be good candidates for [[post-quantum cryptography]], once quantum computers can break the current schemes. Today multivariate quadratics could be used only to build [[Digital signature|signatures]]. All attempts to build a secure encryption scheme have so far failed.

== History ==
In 1988 T. Matsumoto and H. Imai presented their scheme "Matsumoto-Imai-Scheme" on the [[Eurocrypt]] conference.
On later work the "Hidden Monomial Cryptosystems" was developed by {{fr}} [[:fr:Jacques Patarin|Jacques Patarin]]. It is based on a ground and an extension field. On this "[[Hidden Field Equations]]" was designed and presented in 1996. In the following years J. Patarin developed other schemes. In 1997 he presented “Balanced Oil & Vinegar” and 1999 “[[Unbalanced Oil and Vinegar]]” in cooperation with Aviad Kipnis and Louis Goubin.

==Construction==
Multivariate Quadratics involves a public and a private key. The private key consists of three affine transformations (S,P’,T).
In this triple P' is the private transformation which is specially designed for each scheme. P’ maps elements from
<math>GF^n</math> → <math>GF^m</math>. S transforms from <math>GF^n</math> → <math>GF^n</math> and T from <math>GF^m</math> → <math>GF^m</math>. Each transformation must be invertible. Note that the elements are map in a field not in a group. Sometimes the triple is called a trapdoor. The public key results by linking the private transformation. Public key P can be stated as P=S • P' • T.

==Signature==
Signatures are generated using the private key and are verified using the public key. The flow chart below shows how it is done by each party. First the sender takes its message and interpret it as a vector in a small field (for example, if the field has only two elements, then a bit vector). By now S takes <math>x=\langle x_1,...,x_n\rangle </math> as input. During S, <math>x</math> is multiplied with a matrix <math>M_S</math> in addition a vector <math>v_s</math> with length <math>n</math> is added. The dimension of <math>M_S</math> is <math>n</math> x <math>n</math>. T is a similar transformation to S. Both transformation in a mathematically form are shown below
#<math>S = M_S * x + v_S</math>
#<math>T = M_T * y' + v_T</math>
The output of S is the new input for the private transformation P'. Since P' is applied the last transformation T could be performed and the signature is obtained.



A complete signature consists of the elements (x,y) as bit vectors. A potential receiver of this tuple must have the public key in possession. Since he has the key he is able to verify if y is a valid signature of x. Therefore the receiver fill the public equation set with the elements of the bit vectors. A public equations set could look like shown below.

<math>y_1 = x_1x_2 + x_1x_4 + x_3x_4</math><br />
<math>y_2 = x_1x_3 + x_2x_4</math><br />
<math>y_3 = x_1x_4 + x_2x_3 + x_2x_4 + x_3x_4</math><br />
<math>y_4 = x_1x_2 + x_1x_3 + x_1x_4 + x_2x_3 + x_2x_4 + x_3x_4</math>

==Applications==
* [[Unbalanced Oil and Vinegar]]
* [[Hidden Field Equations]]
* SFLASH by [[NESSIE]]
* Rainbow
* TTS
* QUARTZ
* [[QUAD (cipher)]]

==References==
*J. Patarin, Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (extended version); Eurocrypt '96

*Aviad Kipnis, Jacques Patarin, and Louis Goubin, Unbalanced Oil and Vinegar Signature Schemes - Extended Version; Eurocrypt'99

*Christopher Wolf, and [[Bart Preneel]], Taxonomy of Public Key Schemes based on the problem of
Multivariate Quadratic equations; Current Version: 2005-12-15

*An Braeken, Christopher Wolf, and Bart Preneel, A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes, Current Version: 2005-08-06

*Jintai Ding, Research Project: Cryptanalysis on Rainbow and TTS multivariate public key signature scheme

*Jacques Patarin, Nicolas Courtios, Louis Goubin, SFLASH, a fast asymmetric signature scheme for low-cost smartcards. Primitive specification and supporting documentation.

*Bo-Yin Yang, Chen-Mou Cheng, Bor-Rong Chen, and Jiun-Ming Chen, Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems, 2006

*Bo-Yin Yang, Jiun-Ming Chen, and Yen-Hung Chen, TTS: High-Speed Signatures on a Low-Cost Smart Card, 2004

*Nicolas T. Courtois, Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash, 2005

*Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Crypthography, 1997

==External links==
* [http://www.s1on1.com/main/index.cgi/000000A/http://www.minrank.org/hfe/] The HFE public key encryption and signature

{{Cryptography navbox}}

[[Category:Multivariate cryptography]]

Rauch comparison theorem - Revision history

en>ChrisGualtieri: General Fixes using AWB