Paper 2021/1476

Multivariate public key cryptography with polynomial composition

Emile Hautefeuille

Abstract

This paper presents a new public key cryptography scheme using multivariate polynomials in a finite field. Each multivariate polynomial from the public key is obtained by secretly and repeatedly composing quadratic polynomials (of a single variable) with linear combinations of the input variables. Decoding a message involves recursively computing the roots of these quadratic polynomials, and finally solving some linear systems. The main drawback of this scheme is the length of the public key.