Classical Cryptosystems in a Quantum World
Shor [Sho`96] demonstrated the power of quantum computing by showing how a quantum computer could break many of
the cryptosystems used today. The goal of post-quantum cryptography is to protect classical cryptosystems from such
quantum computing attacks. In this talk, we go a step further and explore a world where all parties are using quantum
computers. Now the adversary may be able to mount an even stronger quantum channel attack, where he exchanges quantum
information with the honest parties. In this setting, we demonstrate that even schemes secure against the computational
power of a quantum computer may not be safe. I will discuss new security models associated with these kinds of attacks,
the difficulties faced when trying to construct secure schemes, and some of our techniques for overcoming these challenges.
Quantum Computers and Cryptography
Quantum computers will have far-reaching impacts on cryptography. Shor showed that many of the cryptosystems used today can be broken using a quantum computer, and I will begin my talk by describing Shor's algorithm for factoring integers. Next, I will give an overview of my research on attacking classical cryptosystems over a quantum channel, showing that even schemes resistant to Shor's algorithm may be vulnerable to other forms of quantum attack. On the positive side, quantum computing gives rise to the possibility of quantum key distribution with unparalleled security guarantees, which I will cover at the end of the talk.
The Rank Method and Applications to Post-Quantum Cryptography
We present a new general quantum lower-bound technique called the Rank Method, and use it to solve certain
cryptographic problems in a quantum world. We define a new quantity for quantum algorithms, called the Rank,
and show how to bound the success probability of any quantum algorithm using its Rank. We then give exact
bounds for the Rank of quantum query algorithms. Combining these two bounds, we give an exact characterization
of the difficulty of the Quantum Oracle Interrogation Problem: given q quantum queries to a random oracle H,
produce k distinct input/output pairs of H, where k is greater than q.
Beyond Post-Quantum Cryptography
Post-quantum cryptography attempts to build classical cryptosystems that are secure, even against a quantum
adversary. The security definitions are left mostly unchanged from the classical setting, keeping the
adversary’s interaction with the cryptosystem classical. This models a world where the adversary has a quantum
computer, but the honest parties remain classical.
New York Area CryptoDay