Proving UNSAT in Zero Knowledge
Ning Luo, Timos Antonopoulos, William R. Harris, Ružica Piskač, Eran Tromer, Xiao Shaun Wang · Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security · 2022
Zero-knowledge (ZK) protocols enable one party to prove to others that it knows a fact without revealing any information about the evidence for such knowledge. There exist ZK protocols for all problems in NP, and recent works developed highly efficient protocols for proving knowledge of satisfying assignments to Boolean formulas, circuits and other NP formalisms. This work shows an efficient protocol for the converse: proving formula unsatisfiability in ZK (when the prover posses a non-ZK proof). An immediate practical application is efficiently proving safety of secret programs.