From discrete Fourier analysis to Cryptanalysis

Discrete Fourier analysis studies functions on the discrete cube {-1,1}^n, using their discrete Fourier expansion and functional-analytic tools. Results in discrete Fourier analysis have applications in diverse fields, ranging from social choice and machine learning to mathematical physics. Cryptanalysis studies the practical security of the encryption schemes we use. The central object in cryptanalysis is "attack techniques" – which are algorithms that allow an adversary to intercept communications, forge digital signatures, etc. 

In this talk we propose a new approach to understanding cryptanalytic attacks, using seemingly unrelated techniques from discrete Fourier analysis. We will show that Fourier-analytic techniques can be helpful in addressing core questions, such as: "Can we prove that certain cryptanalytic attacks are optimal?" and "Is there a need for post-quantum secret-key cryptosystems?".  We will mostly concentrate on open questions, but will also show promising results following the new approach.

Based on joint works with Itai Dinur and Ohad Klein