Quantum Zero-Knowledge Proofs Resist Superposition Attacks Using Learning with Errors.

The secure exchange of information remains a fundamental challenge in cryptography, particularly as computational power advances and the threat of quantum computing looms. Researchers continually refine methods to ensure privacy and authenticity, even against adversaries possessing capabilities beyond current technology. A recent contribution addresses the vulnerability of zero-knowledge proofs, protocols allowing one party to prove a statement to another without revealing any information beyond the truth of the statement itself, to attacks leveraging quantum superposition. Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, and Hendrik Waldner detail their work, titled “MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)”, which generalises a technique known as ‘MPC-in-the-head’ – a method for constructing efficient zero-knowledge protocols – to scenarios involving computations performed within the protocol itself. Their approach offers new three-round protocols for verifying statements in both classical complexity classes, NP (nondeterministic polynomial time), and the quantum analogue, QMA (quantum nondeterministic polynomial time), relying on the well-established cryptographic assumption of learning with errors (LWE). This builds upon earlier work by Damgard et al, who demonstrated a superposition-resistant zero-knowledge protocol utilising specialised commitments, but avoids the need for such commitments by leveraging LWE.

Recent advances in cryptography address the increasing threat posed by quantum computing through the development of zero-knowledge proofs resilient to potential ‘superposition attacks’. Researchers now utilise ‘learning with errors’ (LWE) as a foundational assumption for these protocols, building upon the established ‘multi-party computation in the head’ (MPC-in-the-head) technique initially proposed by Ishai et al. MPC-in-the-head allows a computation to be performed as part of a cryptographic protocol, effectively embedding it within the proof itself, and this work extends its application to scenarios where the multiparty computation executes a computation within the protocol.

Researchers demonstrate the construction of zero-knowledge protocols that withstand superposition attacks, where a verifier obtains a quantum superposition of possible protocol transcripts. This capability is crucial for maintaining security in a post-quantum world. Previous approaches relied on ‘perfectly hiding and unconditionally binding dual-mode commitments’, cryptographic tools lacking foundations in standard computational assumptions. This work circumvents this limitation by constructing protocols based on the well-established learning with errors (LWE) problem. LWE is a mathematical problem considered computationally difficult, forming a cornerstone of many post-quantum cryptographic schemes, and its use enhances confidence in the security of the proposed protocols.

Specifically, the team proposes two novel three-round protocols operating within the ‘common reference string’ model, a cryptographic paradigm where both prover and verifier share a publicly known random string. These protocols offer a practical and efficient solution for verifying computations without revealing underlying information. The first protocol constitutes a zero-knowledge argument for NP, the class of problems solvable in polynomial time, reducing its security directly to the hardness of the LWE problem, providing a strong guarantee. The second protocol extends this resilience to QMA, the quantum analogue of NP, offering a zero-knowledge argument for quantum problems also grounded in the LWE assumption, demonstrating the framework’s versatility.

These protocols achieve security by carefully managing information flow, ensuring the verifier’s superposition state reveals no additional information about the secret being proven, essential for preventing attacks that exploit quantum superposition. The reliance on the LWE problem positions these protocols as viable candidates for deployment in a future where quantum computers threaten current cryptographic standards, crucial for ensuring long-term viability. This work represents a step towards building quantum-resistant zero-knowledge proofs, essential for secure communication and computation, and paves the way for more advanced systems.

The team tackles a critical security concern by protecting against adversaries leveraging quantum superposition to gain information during proof verification, a significant advancement in the field of post-quantum cryptography.