Skip navigation
Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorZhandry, Mark
dc.contributor.authorLiu, Qipeng
dc.contributor.otherComputer Science Department
dc.description.abstractPeople 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.
dc.publisherPrinceton, NJ : Princeton University
dc.relation.isformatofThe Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: <a href=></a>
dc.subjectQuantum Computing
dc.subject.classificationComputer science
dc.typeAcademic dissertations (Ph.D.)
pu.departmentComputer Science
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Liu_princeton_0181D_13836.pdf2.32 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.