Nicholas Spooner

STOC Conference 2025 Conference Paper

A Zero-Knowledge PCP Theorem

• Tom Gur
• Jack O'Connor
• Nicholas Spooner

We show that for every polynomial 𝑞∗ there exist polynomial-size, constant-query, non-adaptive PCPs for NP which are perfect zero knowledge against (adaptive) adversaries making at most 𝑞∗ queries to the proof. In addition, we construct exponential-size constant- query PCPs for NEXP with perfect zero knowledge against any polynomial-time adversary. This improves upon both a recent con- struction of perfect zero-knowledge PCPs for #P (STOC 2024) and the seminal work of Kilian, Petrank and Tardos (STOC 1997).

STOC Conference 2024 Conference Paper

An Efficient Quantum Parallel Repetition Theorem and Applications

• John Bostanci
• Luowen Qian
• Nicholas Spooner
• Henry Yuen

STOC Conference 2024 Conference Paper

Perfect Zero-Knowledge PCPs for #P

• Tom Gur
• Jack O'Connor
• Nicholas Spooner

FOCS Conference 2022 Conference Paper

Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably

• Alex Lombardi
• Fermi Ma
• Nicholas Spooner

When do classical zero-knowledge protocols remain secure against quantum attacks? In this work, we develop the techniques, tools, and abstractions necessary to answer this question for foundational protocols: 1)We prove that the Goldreich-Micali-Wigderson protocol for graph non-isomorphism and the Feige-Shamir protocol for NP remain zero-knowledge against quantum adversaries. At the heart of our proof is a new quantum rewinding technique that enables extracting information from multiple invocations of a quantum adversary without disturbing its state. 2)We prove that the Goldreich-Kahan protocol for NP is post-quantum zero knowledge using a simulator that can be seen as a natural quantum extension of the classical simulator. Our results achieve negligible simulation error, appearing to contradict a recent impossibility result due to Chia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution: 3. We introduce coherent-runtime expected quantum polynomial time, a simulation notion that (a) precisely captures all of our zero-knowledge simulators, (b) cannot break any polynomial hardness assumptions, (c) implies strict polynomial-time ε-simulation and (d) is not subject to the CCLY impossibility. In light of our positive results and the CCLY negative results, we propose coherent-runtime simulation to be the appropriate quantum analogue of classical expected polynomial-time simulation.

FOCS Conference 2021 Conference Paper

Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

• Alessandro Chiesa
• Fermi Ma
• Nicholas Spooner
• Mark Zhandry

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). This yields the first post-quantum succinct argument system from any falsifiable assumption. At the heart of our proof is a new quantum rewinding procedure that enables a reduction to repeatedly query a quantum adversary for accepting transcripts as many times as desired. Prior techniques were limited to a constant number of accepting transcripts.

FOCS Conference 2018 Conference Paper

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

• Alessandro Chiesa
• Michael A. Forbes 0001
• Tom Gur
• Nicholas Spooner

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP* model captures this setting. In this work we study the following question: does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP*. Our proof consists of constructing a zero knowledge interactive PCP with a strong algebraic structure, and then lifting it to the MIP* model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.