Homomorphic encryption improves error rates in quantum-safe interactive proofs
Tight Parallel Repetition for Private-Coin Arguments
Cryptography and Security
Summary
Interactive arguments are ways to check if a statement is true by asking questions multiple times. Often, repeating these checks reduces mistakes exponentially, but this was not well understood for quantum attackers or when using private coins. The authors show that using homomorphic encryption, these repeated checks reduce errors as tightly as possible even against quantum cheating strategies. They also extend this to cases where acceptance requires multiple checks to pass. This leads to the first short and efficient arguments for quantum verification classes with very low error rates.
What this means in practice
- •For cryptographic protocol designers: Create interactive proofs that remain secure against quantum adversaries and reduce error rates efficiently using homomorphic encryption.
- •For blockchain developers: Build succinct and constant-round arguments that verify complex quantum statements with high confidence and low communication overhead.
A theory result. No direct application yet.
Authors
Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner
Abstract
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least $t$ of the executions are accepted (for some threshold $t$). Prior to this work, these results were known only when the cheating prover was assumed to be classical, and it was not known how to achieve tight bounds. As a corollary, we construct the first constant-round succinct argument for $\mathsf{QMA}$ with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.