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

          @misc{ scivideos_15464,
            doi = {},
            url = {https://simons.berkeley.edu/talks/overview-attacks-elliptic-curve-isogenies-based-systems},
            author = {},
            keywords = {},
            language = {en},
            title = {Overview of Multi-Variate Function Based Public-Key Cryptography and Cryptanalysis},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15464 see, \url{https://scivideos.org/index.php/Simons-Institute/15464}}
          }
          

Abstract

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.