DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Bryan Ek, Rutgers University, bryan [dot] t [dot] ek {at} math [dot] rutgers [dot] edu

Title: Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Speaker: Kelsey Horan, CUNY

Date: Thursday, February 22, 2018 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

After the announcement for the transition to post-quantum secure cryptographic constructions by the US National Security Agency the cryptography community has been working towards developing and evaluating standards. Of particular interest is the calculation of the quantum bit security for many proposed post-quantum cryptosystems. This talk addresses the problem of solving a system of m boolean multivariate quadratic equations in n variables, the MQ2 problem -- a problem that is central to evaluating the quantum security of many cryptosystems. A Las-Vegas quantum algorithm for solving the boolean multivariate quadratic problem, which requires in expectation the evaluation of O(2^(0.462n)) quantum gates, will be presented.

See: http://sites.math.rutgers.edu/~bte14/expmath/