Multivariate cryptography

Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field $F$ . 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 multivariate quadratics. Solving systems of multivariate 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. As of today, multivariate quadratics have been used to build signature schemes, but all attempts to build a secure encryption scheme have 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 (French) 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 two affine transformations, S and T, and an easy to invert quadratic map P’ $P' : F^m \rightarrow F^n$ . We denote the $n$ by $n$ matrix of the affine endomorphisms $S: F^n \rightarrow F^n$ by $M_S$ and the shift vector by $v_S \in F^n$ and similarly for $T: F^m \rightarrow F^m$ . In other words,

$S(x) = M_S x + v_S$ and
$T(y) = M_T y' + v_T$ .

The triple $(S^{-1},{P'}^{-1},T^{-1})$ is the private key, also known as the trapdoor. The public key is the composition $P = S \circ P' \circ T$ which is by assumption hard to invert without the knowledge of the trapdoor.

Signature

Signatures are generated using the private key and are verified using the public key as follows. The message is hashed to a vector in $y \in F^n$ via a known hash function. The signature is $x=P^{-1}(y) = T^{-1} \left({P'}^{-1}\left(S^{-1}(y)\right)\right)$ .

The receiver of the signed document must have the public key P in possession. He computes the hash y and checks that the signature x fulfils $P(x)=y$ .

Applications

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

The HFE public key encryption and signature

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Portal

This article is issued from Wikipedia - version of the Wednesday, November 04, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.