From discrete Fourier analysis to Cryptanalysis

Speaker
Nathan Keller, BIU
Date
08/05/2022 - 13:00 - 12:00Add to Calendar 2022-05-08 12:00:00 2022-05-08 13:00:00 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 Seminar rm, Math Bldg 216 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Seminar rm, Math Bldg 216
Abstract

 

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

Last Updated Date : 04/05/2022