2:30-3:30 pm

Room 3307, CUNY Graduate Center

365 Fifth Avenue at 34th Street

**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