2:30-3:30 pm
October 27: Kelsey Horan (CUNY Graduate Center), Fast Quantum Algorithm for Solving Multivariate Quadratic Equations
Abstract: In this talk we consider the quantum security of the classically NP-hard problem of solving a system of m Boolean Multivariate Quadratic equations in n variables, MQ2. The MQ problem is central to cryptography, as the security of a majority of multivariate cryptographic schemes is closely related - and even more schemes can be tied to the MQ problem via algebraic cryptanalysis, including post-quantum schemes. We present a quantum algorithm for solving MQ2 as the quantization of a state of the art classical algorithm for the same problem, along with a full complexity analysis of the quantum algorithm and suggestions for parameter choices in multivariate cryptosystems. When n = m, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving MQ2 that requires the evaluation of, on average, O(2^0.462n) quantum gates. To our knowledge this is the fastest algorithm for solving MQ2, outperforming quantum exhaustive search via Grover's algorithm.
This is joint work with J-C. Faugere, D. Kahrobaei, M. Kaplan, E. Kashefi, and L. Perret.
November 3: Alexander A. Mikhalev (Moscow State University), Three examples of old ideas with modern applications
Abstract: We consider three examples of old ideas with modern applications:
(1) row-complete Latin squares and sequenceable groups (1961); (2) A.N.Krylov's
method of subspaces (1931); (3) the method of four Russians (1970).
November 10: Florian Walsh (University of Passau and Stevens Institute of Technology), Finding binomials in polynomial ideals
Abstract: We will describe an algorithm by A. Jensen, T. Kahle, and L. Katthän that computes binomials in a given polynomial ideal over the rationals and present a partial implementation together with possible applications of the algorithm.
December 8: Manhattan Algebra Day
To subscribe to the seminar mailing list, click here