## Introduction

Cryptography is a method to achieve confidentiality among mutually trusted people and organizations. The messages are sent via an unsecured network with no proper security. If we do not use Cryptography to encrypt the messages, it may hamper the confidentiality of the text.

In this blog, we will understand one of the concepts of Post-Quantum Cryptography- Multivariate Cryptography. This includes its history, construction, signature, and applications.

## Multivariate Cryptography

Asymmetric Cryptography based on multivariate polynomials over a few finite fields is known as Multivariate Cryptography. In certain cases, those polynomials could be defined over both a ground and an extension field. The solving procedure of multivariate polynomial equations is taken as NP-hard or NP-complete. So, there are only a few applications of Multivariate Cryptography. It is used as the basis of both signature schemes and public-key cryptosystems.

A user must find a solution **w**= (w_{1},w_{2},.....,w_{n}) of the system for a given m-tuple **z**= (z_{1},z_{2},.....,z_{m}) to authenticate, decrypt, or sign digitally.

### Public Key Cryptosystems (PKCs)

Multivariate Cryptography involves a public and a private key. The private key consists of three transformations- S, Pâ€™, and T

where,

P' is the private transformation designed separately for each scheme. It maps elements from â†’ ,

S transforms from â†’ , and

T transforms from â†’ .

Note that each transformation mentioned above must be invertible. Also, the elements are mapped in a field, not a group. The triple is also known as a trapdoor.

The public key results by linking the private transformation. Public key P can be stated as P = S â€¢ P' â€¢ T.

### Signature Schemes

Signature Schemes are built using the private key and are authenticated using the public key. The flow chart below shows how each party does it. The process of how Signature Schemes work is given below.

The formulae for both the transformations, S and T are given below.

The output of S is fed as the new input for the private transformation P'. Since P' is applied from the last transformation, T could be performed, and the signature is obtained.

A complete signature consists of the elements (x,y) as bit vectors. An expected receiver of this tuple must have the public key along. Since he has the key, he can verify if y is a valid signature of x.

Therefore the receiver can fill the public equation set with the elements of the bit vectors. A public equation set could look like any of the one shown below.

### Applications of Multivariate Cryptography

**Unbalanced Oil and Vinegar Scheme (UOV):**It is the modified version of Oil and Vinegar Scheme. It is the Digital Signature Scheme used in Multivariate Cryptography. The security of this Multivariate Signature Scheme is based on the NP-hard mathematical problem. A minimal quadratic equations system has to be solved to create and validate the signatures.**Hidden Field Equations (HFE):**Hidden Field Equations is a Public Key Cryptosystem scheme used in Multivariate Cryptosystems. HFE is sometimes known as HFE trapdoor function. It is based on the polynomials over finite fields of different sizes. HFE is like a family that consists of basic HFE and combinatorial versions of HFE. It is dependent on the problem's hardness in finding solutions to a system of equations.**Rainbow:**The idea behind the Rainbow Scheme is to utilize n UOV instances iteratively. A UOV instance contains v_{u+1}-v_{u}polynomials in v_{u+1}-v_{u }oil and v_{u }vinegar variables. Using n instead of v_{u+1 }variables, the obtained equation contains m= n-v_{1}polynomials in n variables. We can easily solve this by applying the UOV principle recursively. The signer has to solve more but smaller equations than UOV.**TTS:**It is the predecessor of Rainbow Scheme. It is an aggressive variant of the Rainbow Scheme with sparse coefficients. This makes it faster and quicker.