Certified-Everlasting Quantum NIZK Proofs

Nikhil Pappu

Paper 2025/2262

Certified-Everlasting Quantum NIZK Proofs

Nikhil Pappu

, Portland State University

Abstract

We study non-interactive zero-knowledge proofs (NIZKs) for NP satisfying: 1) statistical soundness, 2) computational zero-knowledge and 3) certified-everlasting zero-knowledge (CE-ZK). The CE-ZK property allows a verifier of a quantum proof to revoke the proof in a way that can be checked (certified) by the prover. Conditioned on successful certification, the verifier's state can be efficiently simulated with only the statement, in a statistically indistinguishable way. Our contributions regarding these certified-everlasting NIZKs (CE-NIZKs) are as follows: - We identify a barrier to obtaining CE-NIZKs in the CRS model via generalizations of known interactive zero-knowledge proofs that satisfy CE-ZK. - We circumvent this by constructing CE-NIZK from black-box use of NIZK for NP satisfying certain properties, along with OWFs. As a result, we obtain CE-NIZKs for NP in the CRS model, based on polynomial hardness of the learning with errors (LWE) assumption. - In addition, we observe that the aforementioned barrier does not apply to the shared EPR model. We leverage this fact to construct a CE-NIZK for NP in this model based on any statistical binding hidden-bits generator, which can be based on LWE. The only quantum computation in this protocol involves single-qubit measurements of the shared EPR pairs.

Note: Bug fixes

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Certified Everlasting Quantum NIZK Quantum Zero-Knowledge Certified Deletion Revocable Cryptography
Contact author(s): nikpappu @ pdx edu
History: 2026-02-12: revised; 2025-12-16: received; See all versions
Short URL: https://ia.cr/2025/2262
License: CC BY

BibTeX

@misc{cryptoeprint:2025/2262,
      author = {Nikhil Pappu},
      title = {Certified-Everlasting Quantum {NIZK} Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2262},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2262}
}