北京雁栖湖应用数学研究院

Multivariate public-key cryptography, or MPKC for short, is one of the main
families of post-quantum cryptosystems and has increasingly been seen as a possible
alternative to classical public-key schemes such as RSA and DSA.
A result from complexity theory states that solving a set of randomly chosen
nonlinear multivariate polynomial equations over a finite field is NP-hard. So far,
quantum computers have not yet been shown to be able to solve a set of multivariate
polynomial equations efficiently, and the consensus is that quantum computers are
unlikely to provide an advantage for this type of problem.