# Overview of Multi-Variate Function Based Public-Key Cryptography and Cryptanalysis

Calvin Lab Auditorium

In this talk, we will first give an introduction on multivariate public key cryptography with the emphasis on the fundamental cryptanalysis tools. We will then discuss a new quantum attack algorithm developed by Gao etc against the multivariate schemes using the HHL quantum algorithm. The complexity of this algorithm depends on the so-called condition numbers.

The work of Gao etc claims that there is a possibility such an algorithm is polynomial asymptotically. If it is indeed true, then we will have a quantum algorithm to solve a NP-complete problem in polynomial time. We will present a proof we developed recently that in general this new algorithm is actually exponential in terms of its complexity in solving a set of quadratic equations over a finite field. This second part of the talk is a joint work with Vlad Gheorghiu from University of Waterloo.

Attachment | Size |
---|---|

mpkc-hhl-1.pdf | 731.87 KB |