/ informatics / security /



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


The Multivariate Quadratic (MQ) System

Given $m$ quadratic polynomials

$$p_1(x_1,..., x_n), ..., p_m(x_1,..., x_n)$$

with polynomial $p$ of $n$ variables $x$

in $n$ variables $x = x_1,..., x_n$ over a finite field $\mathbb F_q$, find a vector ${\boldsymbol x}$ such that

$$p_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.


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

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 ...


Crypto-Systems based on multivariate cryptography: