Qipeng Liu will present his Pre FPO “Cryptography in the age of quantum computers” on Monday, April 12, 2021 at 12pm via Zoom.

Zoom link:

Committee:

Mark Zhandry (advisor, examiner)

Mark Braverman (examiner)

Matt Weinberg (examiner)

Ran Raz (reader)

Gillat Kol (reader)

Talk abstract follows below. All are welcome to attend.

Abstract:

It is widely believed that full-scale quantum computers will eventually be viable. 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. My talk consists of the following topics: understanding security of existing cryptosystems in a quantum world and developing new schemes with the power of quantum computers.

First, I will present my work on quantum query complexity: I will show tight bounds for multi-collision finding problem, and tight time-space tradeoffs for function inversion problem. The latter shows that even with a piece of preprocessed quantum advice, Grover’s search can not be sped up. This technique can be extended to prove 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 post-quantum constant-round zero-knowledge protocols with black-box simulators for NP do not exist, unless NP is in BQP; then I will show how to achieve non-interactive zero-knowledge, by proving the famous Fiat-Shamir transformation is secure in the quantum random oracle model.

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.