Algebra and Cryptography Seminar, Fall 2017

Organizers: Delaram Kahrobaei, Vladimir Shpilrain, Robert Gilman, and Alexei Myasnikov


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

Spring 2017 talks

Fall 2016 talks

Spring 2016 talks

Fall 2015 talks

Spring 2015 talks

Fall 2014 talks

Spring 2014 talks

Fall 2013 talks

Spring 2013 talks

Fall 2012 talks

Spring 2012 talks

Fall 2011 talks

Spring 2011 talks

Fall 2010 talks

Spring 2010 talks

Fall 2009 talks

Spring 2009 talks

Fall 2008 talks

Spring 2008 talks

Fall 2007 talks

Spring 2007 talks

Fall 2006 talks

Spring 2006 talks

Fall 2005 talks