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 difficult 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.

*Join work with Dan Boneh.