⚛️ quantum physics

Certified-Everlasting Quantum NIZK Proofs

This paper introduces certified-everlasting non-interactive zero-knowledge (CE-NIZK) proofs for NP, overcoming barriers in the CRS model via LWE-based constructions and leveraging the shared EPR model to achieve the same goal with minimal quantum computation.

Original authors: Nikhil Pappu

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikhil Pappu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a secret recipe for the world's best chocolate cake. You want to prove to your friend (the Verifier) that you actually know the recipe and that the cake is delicious, without showing them the recipe itself. This is the classic problem of Zero-Knowledge Proofs.

Now, imagine a twist: Your friend is worried that in 20 years, their computer might become so powerful that it could crack your proof and steal your secret recipe. You want a guarantee that even if their computer becomes a super-genius in the future, they still won't be able to learn your secret, provided they agree to delete the proof right now.

This paper introduces a new way to do exactly that, using the strange rules of Quantum Physics.

Here is the breakdown of the paper's ideas using simple analogies.

1. The Problem: The "Forever" Proof

In the digital world, once you send a proof, it's usually there forever. If you send a digital file proving you know a secret, a hacker could steal it today, store it, and wait 50 years until their computers are strong enough to break the encryption and read the secret.

The Quantum Solution:
Quantum physics has a rule called the "No-Cloning Theorem." You cannot make a perfect copy of a quantum object. If you try to look at it too closely, you change it.
The paper proposes a system where the Verifier must prove they have deleted the proof. If they delete it correctly, the secret is gone forever, even if they have infinite computing power later. This is called Certified-Everlasting Zero-Knowledge (CE-ZK).

2. The Big Hurdle: The "Splitting" Trick

The author, Nikhil Pappu, first discovered a major roadblock.
Imagine the proof is a magical envelope. The Verifier wants to keep the secret safe, but they also want to prove they deleted it.

The Bad Idea: The Verifier tries to split the envelope into two parts: Part A (which proves they deleted it) and Part B (which keeps the secret).
The Result: If they can do this, they can keep Part B forever and just show Part A to the Prover to say, "Look, I deleted it!" But they still have the secret!
The Barrier: The paper proves that in standard setups, you cannot build a system that stops this "splitting" trick. If you try, the system fails to be secure.

3. The Solution: Two Different Worlds

Since the "splitting" trick breaks standard systems, the author builds two different types of solutions to bypass it.

Solution A: The "Double-Layered" Envelope (CRS Model)

This is for a setup where everyone agrees on a public "Common Reference String" (like a shared public key).

The Analogy: Imagine the proof is a complex, multi-layered puzzle made of quantum superposition (being in two states at once).
How it works:
1. The Prover creates a "Quantum Envelope" that contains the proof, but it's locked with a quantum key.
2. The Verifier has to measure this envelope to check it.
3. To prove they deleted it, they must return the "quantum dust" (the measurement results).
4. The Magic: Because the proof exists in a superposition, the Verifier cannot split it. If they try to keep a piece to read later, the act of measuring it to prove deletion destroys the ability to read the secret.
The Catch: This requires the Verifier to do some heavy quantum math (like measuring particles in specific ways). It's secure but a bit "heavy" for a regular computer.

Solution B: The "Entangled Twin" (Shared EPR Model)

This is for a setup where the Prover and Verifier start with a special quantum resource: Entangled Pairs (like two coins that are magically linked, no matter how far apart they are).

The Analogy: Imagine the Prover and Verifier each hold one half of a "Quantum Twin" pair.
How it works:
1. They don't send a complex proof. Instead, they agree on a "basis" (a direction to look).
2. They measure their twin coins. Because they are entangled, they get matching results.
3. The Verifier keeps the "matching" results as the proof.
4. To delete the proof, the Verifier measures their remaining coins in a different direction (Hadamard basis). This destroys the link to the original secret.
The Benefit: This is super efficient. The Verifier only needs to do simple measurements (like flipping a coin) and send a simple message. It's much lighter than Solution A.
Why it works: Because the Verifier didn't create the entangled twins (they were pre-shared), they can't "split" the proof. They never had full control over the whole system to begin with.

4. The Takeaway

This paper is a breakthrough because it solves a problem that many thought was impossible: How do you prove you deleted a secret quantum proof without the proof being split and saved?

In the "Standard" world: It's hard, but possible if you use complex quantum superpositions (Solution A).
In the "Entangled" world: It's easy and efficient if you use pre-shared quantum twins (Solution B).

Why should you care?
As we move toward a future with quantum computers, our current digital locks (like passwords and signatures) might become breakable. This research gives us a blueprint for digital proofs that are truly ephemeral. It allows you to prove you know a secret today, and guarantee that tomorrow, even if your friend has a super-computer, they can't go back and read what you proved. It's the ultimate "burn after reading" for the digital age.

1. Problem Statement

The paper addresses the construction of Certified-Everlasting Non-Interactive Zero-Knowledge (CE-NIZK) proofs for the complexity class NP.

Context: Standard NIZKs typically offer either statistical soundness (secure against unbounded provers) or computational zero-knowledge (secure against efficient verifiers), but rarely both simultaneously. In the post-quantum era, there is a desire for Statistical Soundness (to protect against future quantum computers breaking soundness) combined with Everlasting Zero-Knowledge (to protect against future unbounded adversaries who might store proof transcripts).
The Challenge: The "Certified-Everlasting" (CE) property requires that a verifier can delete their quantum proof state in a way that is certifiable by the prover. If the deletion is certified, the verifier's remaining state must be simulatable using only the statement (not the witness), even by an unbounded adversary.
The Barrier: Previous attempts to generalize interactive CE-ZK protocols to the non-interactive setting (specifically in the Common Reference String or CRS model) failed. The paper identifies a fundamental barrier: a class of protocols called "Deletion-Resistant" protocols (where the proof state can be split into a part that passes verification and a part that passes deletion certification) implies the existence of NIZKs that are both statistically sound and statistically zero-knowledge. Such NIZKs are widely believed not to exist for general NP languages.

2. Methodology and Technical Approach

The paper proposes two distinct constructions to overcome the identified barriers, utilizing different setup models.

A. The CRS Model (Common Reference String)

The authors construct a CE-NIZK in the CRS model by avoiding the "Deletion-Resistant" trap through a novel two-level proof structure involving quantum superposition.

Core Mechanism:
1. Inner Proof: An actual NIZK proof ( $\pi_{in}$ ) for the statement $x$ is generated.
2. Encryption: $\pi_{in}$ is encrypted using a One-Time Pad (OTP) derived from a BB84 quantum state ( $|y\rangle_\theta$ ). The pad is computed as the XOR of bits in the BB84 state corresponding to specific basis choices.
3. Outer Proofs: Instead of sending the encrypted ciphertext directly, the prover generates a superposition of "outer" NIZK proofs. Each term in the superposition proves that the decrypted ciphertext (using the specific BB84 basis string $z$ ) is a valid proof for $x$ .
4. OR-Proof Strategy: To enable the simulation of the proof without the witness, the protocol uses a 2-slot technique (inspired by Naor-Yung). It creates two ciphertexts ( $ct_0, ct_1$ ) and proves an OR statement: either $ct_0$ decrypts to a valid proof, OR $ct_1$ decrypts to a valid proof.
Security Logic:
- Soundness: Relies on the statistical adaptive soundness of the underlying NIZK.
- Certified-Everlasting ZK: The verifier is asked to return the BB84 state. If the prover verifies the deletion (using the certified deletion theorem for BB84 states by Bartusek and Khurana), the OTP pad becomes information-theoretically hidden.
- Simulation: The simulator uses the Quantum-Secure Adaptive Zero-Knowledge property of the underlying NIZK. It swaps the real inner proof with a simulated one bit-by-bit within the superposition. Because of the OR-proof structure, the simulator can maintain the validity of the outer proof even while changing the inner ciphertext, eventually replacing the entire witness-dependent data with a simulated view.

B. The Shared EPR Model

The authors observe that the "Deletion-Resistant" impossibility barrier does not apply when the prover and verifier share entangled EPR pairs (Einstein-Podolsky-Rosen pairs) beforehand.

Core Mechanism:
1. Hidden Bits Paradigm: The protocol adapts the classic Hidden-Bits Generator (HBG) paradigm to the quantum setting.
2. Entanglement: The prover and verifier share EPR pairs. The HBG commitment fixes a basis string $\theta$ .
3. Measurement: Both parties measure their EPR halves in the basis $\theta$ . Due to entanglement, they obtain correlated outcomes, effectively generating "hidden bits" that are unknown to the verifier until revealed.
4. Deletion: To certify deletion, the verifier measures the unopened EPR pairs in the Hadamard basis. This collapses the state, destroying the information about the hidden bits.
Efficiency: This approach is significantly more efficient than the CRS model. It requires only single-qubit measurements (in either computational or Hadamard basis) and classical computation, avoiding the need for complex superposition of NIZK proofs.

3. Key Contributions

Definition and Impossibility Result:
- Formally defined CE-NIZKs in both CRS and Shared EPR models.
- Proved that "Deletion-Resistant" CE-NIZKs (where proof and deletion states are separable) imply the existence of NIZKs with both statistical soundness and statistical zero-knowledge, which are likely impossible for general NP. This explains why simple generalizations of interactive protocols fail.
CE-NIZK in the CRS Model:
- Constructed the first CE-NIZK for NP in the CRS model.
- Assumptions: Based on the Learning With Errors (LWE) assumption (specifically, polynomial hardness).
- Technique: Utilized a quantum superposition of NIZK proofs entangled with BB84 states, leveraging the "Two-Slot" technique and Quantum-Secure Adaptive Zero-Knowledge.
CE-NIZK in the Shared EPR Model:
- Demonstrated that the impossibility barrier vanishes in the Shared EPR model.
- Constructed a highly efficient CE-NIZK based on any Statistically Binding Hidden-Bits Generator (which can be built from LWE).
- Efficiency: The protocol requires only single-qubit measurements, making it practically more feasible than the CRS construction.
Security Guarantees:
- Both constructions satisfy Statistical Soundness (secure against unbounded provers).
- Both satisfy Computational Zero-Knowledge (standard) and Certified-Everlasting Zero-Knowledge (secure against unbounded adversaries after successful deletion certification).

4. Results

Theorem 2.4: CE-NIZKs for NP exist in the CRS model assuming OWFs and specific properties of quantum-secure NIZKs (satisfied by LWE-based constructions).
Theorem 2.6: CE-NIZKs for NP exist in the Shared EPR model assuming the existence of Statistically Binding Hidden-Bits Generators (satisfied by LWE).
Corollary 2.5 & 2.7: Concrete instantiations of both protocols are possible based solely on the polynomial hardness of the LWE problem.

5. Significance

Bridging the Gap: This work resolves a major open question in quantum cryptography: Can we achieve NIZKs that are both statistically sound and offer everlasting zero-knowledge guarantees via certified deletion? The answer is yes, provided we use quantum resources (BB84 states or EPR pairs).
Overcoming Impossibility: The paper provides a deep theoretical insight into why previous attempts failed (the "Deletion-Resistant" barrier) and how to circumvent it using quantum entanglement and superposition.
Practical Implications:
- The Shared EPR model offers a highly efficient protocol suitable for near-term quantum networks where entanglement distribution is feasible.
- The CRS model construction provides a solution for settings where pre-shared entanglement is not available, relying only on standard post-quantum assumptions (LWE).
Future Directions: The paper opens avenues for constructing CE-NIZKs for QMA (Quantum NP) and exploring Publicly Verifiable Deletion (currently, the verification of deletion is private to the prover).

In summary, this paper establishes the theoretical feasibility of Certified-Everlasting NIZKs, providing concrete constructions that leverage the unique properties of quantum mechanics (no-cloning, entanglement, and gentle measurement) to achieve security guarantees that are impossible in the classical world.