Indistinguishability and Non-deterministic Encryption of the Quantum Safe Multivariate Polynomial Public Key Cryptographic System
Randy Kuang, Michel Barbeau · 2021
Multivariate Polynomial Public Key (MPPK) is a cryptographic system, over a prime Galois field. A key pair is generated using a multiplier multivariate polynomial and two multiplicand univariate solvable polynomials. They yield two product multivariate polynomials. The first variable is used for carrying the message or secret and others are used as noise sources. The public key consists of all the coefficients of the product multivariate polynomials, except the two constant coefficients, in terms with coefficients attached to the message variable, and a noise function or a polynomial of only noise variables generated from the constant term of the multiplier multivariate polynomial by multiplying a private random variable R. The private key is made of both univariate solvable multiplicand polynomials and the private R. Encryption takes a secret message and random numbers for noises, adding noise that is automatically cancelled by decryption. Decryption is achieved evaluating a solvable equation. We review security analysis that can be employed to crack MPPK secrets and private keys. Finally, we discuss indistinguishability and non-deterministic encryption, key properties of MPPK.