Theory of Computing Seminar

 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.