Complexity of proof systems in classical and quantum world
Event details
| Date | 15.05.2024 |
| Hour | 09:30 › 11:30 |
| Speaker | Zijing Di |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Rüdiger Urbanke
Abstract
Ever since Adi Shamir's groundbreaking IP = PSPACE result, there has been a surge of interest in exploring the powers and limitations of different proof systems. We consider prover and verifier with different computational resources, and what properties can be satisfied under different protocol complexities such as number of rounds. We also consider the quantum variants where the prover or verifier has quantum power, or access to quantum oracles.
In this report, we first present an impossibility result on the non-existence of three-round zero-knowledge protocols except for the trivial class BPP. Then we offer an error amplification construction for QMA without blowing up the witness size. Finally, we discuss the motivation of the quantum random model for why classical random oracle is insufficient to prove security against quantum adversaries. Building upon this research trajectory, we aim to have a better understanding of (quantum) proof system complexity, and use this understanding to improve the security analysis of primitives believed to be secure, or create new constructions when assumptions fall apart.
Background papers
[1]
Oded Goldreich, Hugo Krawczyk:
On the Composition of Zero-Knowledge Proof Systems. SIAM J. Comput. 25(1): 169-192 (1996)
https://epubs.siam.org/doi/pdf/10.1137/S0097539791220688
[2]
Chris Marriott, John Watrous:
Quantum Arthur-Merlin Games. CCC 2004: 275-285
https://ieeexplore.ieee.org/abstract/document/1313850
[3]
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, Mark Zhandry:
Random Oracles in a Quantum World. ASIACRYPT 2011: 41-69
https://link.springer.com/chapter/10.1007/978-3-642-25385-0_3
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Rüdiger Urbanke
Abstract
Ever since Adi Shamir's groundbreaking IP = PSPACE result, there has been a surge of interest in exploring the powers and limitations of different proof systems. We consider prover and verifier with different computational resources, and what properties can be satisfied under different protocol complexities such as number of rounds. We also consider the quantum variants where the prover or verifier has quantum power, or access to quantum oracles.
In this report, we first present an impossibility result on the non-existence of three-round zero-knowledge protocols except for the trivial class BPP. Then we offer an error amplification construction for QMA without blowing up the witness size. Finally, we discuss the motivation of the quantum random model for why classical random oracle is insufficient to prove security against quantum adversaries. Building upon this research trajectory, we aim to have a better understanding of (quantum) proof system complexity, and use this understanding to improve the security analysis of primitives believed to be secure, or create new constructions when assumptions fall apart.
Background papers
[1]
Oded Goldreich, Hugo Krawczyk:
On the Composition of Zero-Knowledge Proof Systems. SIAM J. Comput. 25(1): 169-192 (1996)
https://epubs.siam.org/doi/pdf/10.1137/S0097539791220688
[2]
Chris Marriott, John Watrous:
Quantum Arthur-Merlin Games. CCC 2004: 275-285
https://ieeexplore.ieee.org/abstract/document/1313850
[3]
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, Mark Zhandry:
Random Oracles in a Quantum World. ASIACRYPT 2011: 41-69
https://link.springer.com/chapter/10.1007/978-3-642-25385-0_3
Practical information
- General public
- Free