The private key of a multivariate polynomial-based scheme consists of a triple: one easy-to-invert quadratic map and two invertible linear maps. The public key is their composition – a random nonlinear transformation. To encrypt a message, one needs to apply a transformation corresponding to the public key to it. For decryption, one applies the inverse of the private-key transformations to the message one by one.
The main challenges associated with multivariate cryptographic algorithms are:
- the private transformation has a definite structure, necessary for the efficiency, but at the same time, it makes it possible to construct specific algebraic attacks;
- quadratic equation systems over a finite field determine rather large key lengths.
Many years of successfully cryptanalyzing this algorithm class demonstrate how necessary it is to be particularly careful when selecting synthesis parameters.
At the same time these algorithms are relatively simple and efficient compared to other quantum-resistant algorithms. Moreover, they have relatively small signatures.