6 citations · 12 across the 7 of their papers we have counts for
14 papers
Two-Sided Product Expanding Codes via Rademacher Matrices
Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner
We give a proof of the existence of two-sided product expanding codes which, unlike the earlier result of Kalachev and Panteleev (FOCS, 2025), does not rely on explicit constructio…
Computational Bounds for -Routing
Oren Renard, Nicholas Spooner
The -routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited. W…
Tight Post-Quantum Parallel Repetition for Private-Coin Arguments
Zvika Brakerski, Andrew Huang, Yael Tauman Kalai +1
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness…
Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in NP
Eshan Chattopadhyay, Oren Renard, Nicholas Spooner
We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the QMA-complete Local Hamiltonian problem (Kitaev, Shen, and Vyalyi, 2002)…
On Removing Interaction from Quantum Proofs
Nicholas Spooner, Max Tromanhauser
An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model…
A Zero-Knowledge PCP Theorem
Tom Gur, Jack O'Connor, Nicholas Spooner
We show that for every polynomial q* there exist polynomial-size, constant-query, non-adaptive PCPs for NP which are perfect zero knowledge against (adaptive) adversaries making at…
Quantum Rewinding for IOP-Based Succinct Arguments
Alessandro Chiesa, Marcel Dall Agnol, Zijing Di +2
We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. We prove that an interactive…
Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor, Nicholas Spooner
We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP…
An efficient quantum parallel repetition theorem and applications
John Bostanci, Luowen Qian, Nicholas Spooner +1
We prove a tight parallel repetition theorem for -message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We als…
Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)
Alex Lombardi, Fermi Ma, Nicholas Spooner
A major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it. This is especially problem…
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier
Alessandro Chiesa, Fermi Ma, Nicholas Spooner +1
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 colla…
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Alessandro Chiesa, Michael A. Forbes, Tom Gur +1
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…
A Zero Knowledge Sumcheck and its Applications
Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner
Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortun…
On Probabilistic Checking in Perfect Zero Knowledge
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes +3
We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The com…