Theory of Computing Seminar

Friday August 12, 2016 3:00 PM

Breaking symmetric cryptosystems using quantum period finding

Speaker: Marc Kaplan, Paris Tech
Location: Annenberg 213

Abstract:

 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.
Series Theory of Computing Seminar Series

Contact: Thomas Vidick vidick@cms.caltech.edu