Towards Practical Zero-Knowledge Proof for PSPACE
By: Ashwin Karthikeyan , Hengyu Liu , Kuldeep S. Meel and more
Potential Business Impact:
Lets computers prove hard math problems are true.
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.
Similar Papers
Semi-Algebraic Proof Systems for QBF
Logic in Computer Science
Proves hard computer problems faster than before.
Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge
Cryptography and Security
Proves programs match without showing secrets.
Towards Fuzzing Zero-Knowledge Proof Circuits (Short Paper)
Cryptography and Security
Finds hidden mistakes in secret computer codes.