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.
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 mailto: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.
participants (1)
-
jfarquer@cs.princeton.edu