Post-quantum Zero Knowledge in Constant Rounds

2019/12/10 by Bitansky, Nir, Shmueli, Omri
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.1912.04769

Abstract

We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.

Related

• On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
• Zero-knowledge against quantum attacks
• The Black-Box Simulation Barrier Persists in a Fully Quantum World
• Post-Quantum Multi-Party Computation
• MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)