CRYPTOGRAPHY IN THE AGE OF QUANTUM COMPUTERS 2.0

Abstract

People widely believe that full-scale quantum computers will eventually be viable in the near future. Quantum computers pose threats to many existing cryptosystems (most prominently, Shor's algorithm) while raising the possibility of using quantum-mechanical phenomena to achieve never-before-possible capabilities. First, I will present my work on quantum query complexity: I will show tight bounds for multi-collision finding problems and tight time-space tradeoffs for function inversion problems. The latter indicates that Grover's search cannot be sped up even with a piece of preprocessed quantum advice. This technique can be extended to prove the post-quantum non-uniform security of many existing cryptographic schemes. Second, I will present my work on post-quantum zero-knowledge proof. I will start by showing that post-quantum constant-round zero-knowledge protocols for NP with black-box simulators do not exist in the plain model unless NP is in BQP. Then, I will show how to achieve non-interactive zero-knowledge in the quantum random oracle model by proving that the famous Fiat-Shamir transformation is secure. Third, I will present my work on quantum copy-protection, which aims to use the unclonability of quantum states to achieve programs that cannot be copied. Towards this goal, I will show that any unlearnable function can be copy-protected relative to classical oracles. For specific cryptographic functionalities (such as signatures and RPFs), I will show that they can be copy-protected in the plain model.