A new post-quantum multivariate polynomial public key encapsulation algorithm

We propose a new quantum-safe cryptosystem called multivariate polynomial public key (MPPK). Its security stems from the hardness of finding integer solutions to multivariate equations over a prime field GF(p). Indeed, for a large prime p, solving modular Diophantine equations is an NP-complete problem. MPPK introduces a novel way of key pair generation that involves multiplying a base n-degree multiplicand multivariate polynomial with respect to a message variable and two univariate multiplier polynomials, solvable by radicals over GF(p). The coefficients of the two resulting polynomial products are used to construct the public key, except for the coefficients of the constant and highest degree terms with respect to the message variable. The base multivariate polynomial's constant and highest degree terms are used to form two noise functions, as parts of the public key, through multiplications with random variables. The private key consists of the two multiplier polynomials and the two random noise constants. MPPK encryption performs multivariate polynomial evaluations with a randomly chosen secret as the message variable and multiple noise values for other variables. The ciphertext tuple is created by calculating the values of two product multivariate polynomials and two noise functions. MPPK decryption eliminates the base multivariate polynomial by dividing by the two-product multivariate polynomial values and then extracting the secret from the resulting univariate polynomial with a radical. For adversarial extraction of the private key from the public key alone, the best complexity is exponential with respect to the bit length of the prime finite field. The same holds for the adversarial extraction of the plaintext from the ciphertext.

Automated summary

This article proposes a new quantum-safe cryptosystem called multivariate polynomial public key (MPPK), which derives its security from the difficulty of finding integer solutions to multivariate equations over a prime field GF(p). MPPK introduces a novel key pair generation method involving the multiplication of a base multivariate polynomial with two univariate multiplier polynomials, solvable by radicals over GF(p). The encryption and decryption process of MPPK involves polynomial evaluations and extraction.