/ informatics / security /

[edit]

Definition

Multivariate cryptography is the generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field 𝔽\mathbb F.

Properties

The Multivariate Quadratic (MQ) System

Given mm quadratic polynomials

p1(x1,...,xn),...,pm(x1,...,xn)p_1(x_1,..., x_n), ..., p_m(x_1,..., x_n)

with polynomial pp of nn variables xx

in nn variables x=x1,...,xnx = x_1,..., x_n over a finite field 𝔽q\mathbb F_q, find a vector 𝐱\boldsymbol x such that

p1(x0)=...=pm(x0)=0p_1(x_0) = ... = p_m(x_0) = 0

Solving MQ polynomial systems is worst case NP-hard and in general doubly exponential over any finite field.

Construction

The private key consists of two affine transformations, SS and TT, and an easy to invert quadratic map P:FmFnP':F^{m}\rightarrow F^{n}.

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

Implementations

Crypto-Systems based on multivariate cryptography:

References