skip to main content

Theory of Computing Seminar

Friday, August 12, 2016
3:00pm to 4:00pm
Add to Cal
Annenberg 213
Breaking symmetric cryptosystems using quantum period finding
Marc Kaplan, Paris Tech,


 In the mid-nineties, Shor's celebrated algorithm revealed that quantum computers, when available, may threaten currently used public-key cryptography. At the core of this algorithm is a procedure to find periods of elements for specific groupe structures. In this talk, we will show that the simplest quantum period algorithm, known as Simon's algorithm, can also be used to attack symmetric cryptographic construction.
When a function collides with a fixed periodicity, Simon's algorithm allow to find this period with O(n) quantum queries to the function. This leads to simple attacks in the quantum chosen plaintext model. We apply this idea to a number of cryptosystems including widely used modes of operation for authentication, authenticated encryption and candidates to the CEASAR competition. Finally, we show that slide attacks reveal a similar structure and can be exponentially more efficient in the quantum regime than in the classical one.
For more information, please contact Thomas Vidick by email at [email protected].