Towards Practical Zero-Knowledge Proof for PSPACE

• URL: http://arxiv.org/abs/2511.15071v1
• Date: Wed, 19 Nov 2025 03:22:48 GMT
• Title: Towards Practical Zero-Knowledge Proof for PSPACE
• Abstract summary: This work presents the first practical zero-knowledge (ZK) protocols for PSPACE-complete statements.<n>We develop an efficient encoding of Q-Res proofs, enabling proof validation through low-overhead arithmetic checks.<n>We also design a ZK protocol to prove knowledge of a winning strategy related to the QBF, which is often equally important in practice.
• Score: 26.648887511985652
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient zero-knowledge proofs (ZKPs) have been restricted to NP statements so far, whereas they exist for all statements in PSPACE. This work presents the first practical zero-knowledge (ZK) protocols for PSPACE-complete statements by enabling ZK proofs of QBF (Quantified Boolean Formula) evaluation. The core idea is to validate quantified resolution proofs (Q-Res) in ZK. We develop an efficient polynomial encoding of Q-Res proofs, enabling proof validation through low-overhead arithmetic checks. We also design a ZK protocol to prove knowledge of a winning strategy related to the QBF, which is often equally important in practice. We implement our protocols and evaluate them on QBFEVAL. The results show that our protocols can verify 72% of QBF evaluations via Q-Res proof and 82% of instances' winning strategies within 100 seconds, for instances where such proofs or strategies can be obtained.

Related papers

• ProofPulse: Interactive Proof Coverage Analysis for Dafny [47.23158426199152]
  Deductive verification ensures that an implementation satisfies its specification, but successful verification does not guarantee the quality of the specification.<n>We present proofpulse, a tool for Dafny that diagnoses specification quality using a three-valued proof coverage model.
  arXiv  Detail & Related papers  (2026-08-31T14:00:31Z)
• Does Accuracy Equal Evidence? Reasoning Faithfulness under KV Cache Compression [42.94199567901975]
  KV cache compression is commonly evaluated by final-answer accuracy, implicitly assuming that preserving the answer also preserves the reasoning that supports it.<n>We test this assumption for large reasoning models and show that it can fail.<n>We evaluate ten token-eviction KV compression methods and one quantization method on three models across mathematical reasoning, scientific QA, clinical calculation, and long-context retrieval.
  arXiv  Detail & Related papers  (2026-08-03T03:03:53Z)
• Rigorous Security Proofs for Practical Quantum Key Distribution [0.0]
  This thesis is concerned with rigorous security analyses of Quantum Key Distribution (QKD) protocols.<n>We establish a security proof for variable-length QKD protocols against IID collective attacks, and extend this result to coherent attacks using the postselection technique.<n>Second, we develop a method to bound phase error rates in entropic uncertainty relation-based and phase error rate-based proofs, using only the observed statistics of the protocol.<n>Third, we present a very general security analysis based on the marginal-constrained entropy accumulation theorem.
  arXiv  Detail & Related papers  (2026-04-23T15:48:02Z)
• Quantum Key Distribution with Imperfections: Recent Advances in Security Proofs [0.0]
  Quantum Key Distribution (QKD) can enable two spatially separated parties to establish an information-theoretically secure encryption.<n>Security proofs robust against a wide range of eavesdropping strategies have established the theoretical soundness of several QKD protocols.<n>Most proofs are based on idealized models of the physical systems involved in such protocols and often include assumptions that are not satisfied in practical implementations.
  arXiv  Detail & Related papers  (2026-02-04T21:16:33Z)
• Protocol-level description and self-contained security proof of decoy-state BB84 QKD protocol [1.0923877073891446]
  We present a self-contained information-theoretic security proof for the decoy-state BB84 quantum key distribution protocol.<n>Our proof yields a key rate consistent with previous findings.
  arXiv  Detail & Related papers  (2025-04-29T04:28:15Z)
• Quantum Rewinding for IOP-Based Succinct Arguments [42.12045681000549]
  We prove that an interactive variant of the BCS transformation is secure in the standard model against quantum adversaries when the vector commitment scheme is collapsing.<n>As a consequence of our results, we obtain standard-model post-quantum secure succinct arguments with the best complexity known.
  arXiv  Detail & Related papers  (2024-11-08T06:33:08Z)
• Collaborative CP-NIZKs: Modular, Composable Proofs for Distributed Secrets [3.3373764108905455]
  Composability allows users to combine different specialized NIZKs. We present the first, general definition for collaborative commit-and-prove NIZK.
  arXiv  Detail & Related papers  (2024-07-27T08:45:34Z)
• The Round Complexity of Proofs in the Bounded Quantum Storage Model [0.7366405857677227]
  We study the study of round compression of protocols in the bounded quantum storage model (BQSM) In this model, the malicious parties have a bounded quantum memory and they cannot store the all the qubits that are transmitted in the protocol. We show that NIZK in the plain model against BQS adversaries is unlikely with standard techniques.
  arXiv  Detail & Related papers  (2024-05-28T15:24:48Z)
• The Road to Near-Capacity CV-QKD Reconciliation: An FEC-Agnostic Design [53.67135680812675]
  A new codeword-based QKD reconciliation scheme is proposed. Both the authenticated classical channel (ClC) and the quantum channel (QuC) are protected by separate forward error correction (FEC) coding schemes. The proposed system makes QKD reconciliation compatible with a wide range of FEC schemes.
  arXiv  Detail & Related papers  (2024-03-24T14:47:08Z)
• Comprehensive Analysis of BB84, A Quantum Key Distribution Protocol [0.0]
  Quantum Key Distribution (QKD) is a technique that enables secure communication by sharing a secret key. One of the most well-known QKD protocols is the BB84 protocol, proposed by Charles Bennett and Gilles Brassard in 1984.
  arXiv  Detail & Related papers  (2023-12-09T16:32:54Z)
• Robust and efficient verification of graph states in blind measurement-based quantum computation [52.70359447203418]
  Blind quantum computation (BQC) is a secure quantum computation method that protects the privacy of clients. It is crucial to verify whether the resource graph states are accurately prepared in the adversarial scenario. Here, we propose a robust and efficient protocol for verifying arbitrary graph states with any prime local dimension.
  arXiv  Detail & Related papers  (2023-05-18T06:24:45Z)
• Succinct Classical Verification of Quantum Computation [30.91621630752802]
  We construct a classically succinct interactive argument for quantum computation (BQP) Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning Errors (LWE)
  arXiv  Detail & Related papers  (2022-06-29T22:19:12Z)
• Data post-processing for the one-way heterodyne protocol under composable finite-size security [62.997667081978825]
  We study the performance of a practical continuous-variable (CV) quantum key distribution protocol. We focus on the Gaussian-modulated coherent-state protocol with heterodyne detection in a high signal-to-noise ratio regime. This allows us to study the performance for practical implementations of the protocol and optimize the parameters connected to the steps above.
  arXiv  Detail & Related papers  (2022-05-20T12:37:09Z)
• COPA: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attacks [49.15885037760725]
  We focus on certifying the robustness of offline reinforcement learning (RL) in the presence of poisoning attacks. We propose the first certification framework, COPA, to certify the number of poisoning trajectories that can be tolerated. We prove that some of the proposed certification methods are theoretically tight and some are NP-Complete problems.
  arXiv  Detail & Related papers  (2022-03-16T05:02:47Z)
• PRover: Proof Generation for Interpretable Reasoning over Rules [81.40404921232192]
  We propose a transformer-based model that answers binary questions over rule-bases and generates the corresponding proofs. Our model learns to predict nodes and edges corresponding to proof graphs in an efficient constrained training paradigm. We conduct experiments on synthetic, hand-authored, and human-paraphrased rule-bases to show promising results for QA and proof generation.
  arXiv  Detail & Related papers  (2020-10-06T15:47:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.