Nathan Keller (BIU) - Cryptanalysis, via discrete Fourier analysis

Colloquium online lecture by Nathan Keller (BIU), May 24, 2021, at The School of Computer Science and Engineering, The Hebrew University. 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. While the discovered attack techniques have been very successful, and have allowed discarding insecure encryption schemes and developing strategies for better designs, their analysis has always been somewhat ad-hoc. For most of the techniques, we don't know whether they are optimal, and for some, we don't even know how to estimate their complexity well. 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. Joint work with Itai Dinur and Ohad Klein