[quantum-info] IQC Colloquium May 6th Mark Zhandry QNC 0101

Erin Cronin emcronin at uwaterloo.ca
Mon May 6 07:51:04 EDT 2013


IQC Colloquium
Monday May 6th, 2013
2:30pm 
QNC 0101

Talk given by visitor Mark Zhandry
The Rank Method and Applications to Post-Quantum Cryptography

Abstract

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.

We use this characterization to construct classical cryptographic schemes that are secure, even when implemented on a quantum computer. In this setting, a quantum adversary may be able to establish a quantum channel to attack the scheme. Proving security then becomes much more di
cult than in the classical case. Our
characterization of the Quantum Oracle Interrogation Problem allows us to give new quantum security proofs for message authentication codes and digital signatures that were previously not known to be secure in our setting.

Joint work with Dan Boneh.





More information about the quantum-info mailing list