Kevin Qipeng Liu will present his FPO "Cryptography in the Age of Quantum Computers 2.0" on Tuesday, July 27, 2021 at 4PM via Zoom.

Zoom link: https://princeton.zoom.us/j/6541841088

The members of Kevin’s committee are as follows: Mark Zhandry (Adviser); Readers: Ran Raz and Gillat Kol; Examiners: Mark Braverman, Matthew Weinberg and Mark Zhandry.

A copy of his thesis is available upon request. Please email gradinfo@cs.princeton.edu if  you would like a copy of the thesis.

Everyone is invited to attend his talk.

Abstract follows below:

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[1]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.