### DIMACS Theoretical Computer Science Seminar

Title: Quantum algorithms for highly non-linear Boolean functions

Speaker: **Martin Roetteler**, NEC Laboratories

Date: Wednesday, April 21, 2010 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We provide new examples for exponential separations between quantum
and classical query complexity by considering hidden shift problems
over families of highly non-linear Boolean functions. These so-called
bent functions arise in cryptography, where their property of having
perfectly flat Fourier spectra on the Boolean hypercube gives them
resilience against certain types of attack. We present quantum
algorithms that solve the hidden shift problems for several well-known
classes of bent functions in polynomial time and with a polynomial
number of queries, while the classical query complexity is shown to be
exponential. Our approach uses a technique that exploits the duality
between bent functions and their Fourier transforms.

Based on a SODA'10 paper. See also http://arxiv.org/abs/0811.3208