Quantum NIZK Proofs Advance Certified-Everlasting Zero-Knowledge with Statistical Indistinguishability

Non-interactive zero-knowledge proofs, which allow verification of information without revealing the information itself, represent a cornerstone of modern cryptography, but ensuring their long-term security remains a significant challenge. Nikhil Pappu from Portland State University and colleagues address this problem by introducing a new framework for ‘certified-everlasting’ zero-knowledge proofs, offering a mechanism to revoke compromised proofs in a verifiable manner. This research overcomes a fundamental barrier previously thought to limit the construction of such proofs, achieving a breakthrough by building these proofs from existing cryptographic tools and the well-established learning with errors assumption. The team also demonstrates a more efficient approach within a specific quantum communication model, relying solely on single-qubit measurements, and establishes a pathway towards more robust and future-proof cryptographic systems.

The team focuses on proofs with three key properties: statistical soundness, computational zero-knowledge, and certified-everlasting zero-knowledge, or CE-ZK. CE-ZK introduces the ability for a verifier of a quantum proof to revoke it in a way that the prover can certify, allowing efficient reconstruction of the verifier’s state, and represents a crucial step towards practical and robust quantum security protocols.

The researchers developed certified-everlasting Non-Interactive Zero-Knowledge proofs, or CE-NIZKs, and identified a significant obstacle to their construction using existing methods. They overcame this barrier by building a CE-NIZK system from established non-interactive zero-knowledge proofs and one-way functions, resulting in a CE-NIZK system applicable to any problem within the complexity class NP. This system’s security relies on the presumed difficulty of solving the learning with errors problem, a well-studied challenge in cryptography. Furthermore, the team demonstrated that this barrier does not apply when using a shared EPR model, where the prover and verifier share entangled quantum particles.

Lattice Cryptography and Obfuscation Foundations

This body of work builds upon core cryptographic concepts and techniques, establishing foundational elements for advanced schemes. Lattice-based cryptography, particularly the Learning With Errors (LWE) technique, forms a cornerstone of modern post-quantum cryptography. Indistinguishability obfuscation, a powerful technique for concealing program logic, is another key element, alongside early work on bit commitment and characterizations of non-interactive zero-knowledge proofs. Recent advances include reusable designated-verifier NIZKs and new NIZK techniques based on LWE. The research also encompasses quantum cryptography and post-quantum cryptography, focusing on systems that leverage quantum mechanics or resist attacks from quantum computers.

This includes work on quantum key leasing and distribution, revocable quantum timed-release encryption, and public-key quantum money. Quantum random functions and post-quantum signatures are also explored, alongside research into quantum statistical zero-knowledge. Advanced ZKP techniques are applied to problems such as anonymous payments and the construction of NIZKs for QMA. A significant focus lies on deletion and revocation, addressing the secure removal of data or the invalidation of access rights. This includes publicly verifiable deletion schemes and revocable signature systems.

The research also considers leakage resilience, analyzing the security of cryptographic systems against partial information leaks. Specific cryptographic primitives, such as tokenized signatures and functional encryption, are explored, alongside attribute-based encryption schemes. A central theme throughout is the development of post-quantum cryptography, building systems resistant to attacks from future quantum computers, and the widespread use of zero-knowledge proofs as a fundamental building block for many advanced cryptographic schemes.

Certified Revocation via Learning with Errors

Researchers have significantly advanced non-interactive zero-knowledge proofs by developing certified-everlasting zero-knowledge (CE-NIZK) systems. These systems enable proofs to be revoked, with the revocation verifiable by an independent party, and allow the verifier’s state to be efficiently reconstructed from the original statement. The team identified a fundamental limitation in constructing CE-NIZKs using conventional methods, but circumvented this by building a CE-NIZK system from existing non-interactive zero-knowledge proofs and one-way functions. This resulted in a CE-NIZK system applicable to any problem within the complexity class NP, relying on the presumed difficulty of solving the learning with errors problem.

Furthermore, the researchers demonstrated that this limitation does not apply when using a shared EPR model, where the prover and verifier share entangled quantum particles. This enabled the construction of a CE-NIZK system based on statistically binding hidden-bits generators, requiring only single-qubit measurements. This shared EPR model approach offers a more efficient use of quantum resources compared to systems relying on a common reference string.