Xiao Wang Wins Distinguished Paper Award at ACM CCS 2022
Wang was recognized for his recent paper on efficient protocol for proving UNSAT in zero-knowledge
Xiao Wang, assistant professor of computer science, won a Distinguished Paper Award at the Association for Computing Machinery (ACM) Conference on Computer and Communications Security (CCS), held in Los Angeles on November 7-11.
The winning paper, “Proving UNSAT in Zero Knowledge,” is coauthored by Timos Antonopoulos, Ning Luo, and Ruzica Piskac (Yale University); William R. Harris (Galois Inc.); and Eran Tromer (Columbia University).
Zero-knowledge proofs enable a “prover” to verify the validity of a claim to a second party, without revealing information about the evidence. Zero-knowledge protocols exist for all problems in NP, a complex class of computational decision problems.
“The paper pushes the boundary of practical zero-knowledge and connects cryptography and formal methods from a new perspective,” Wang said.
The research team examined instances of the UNSAT problem, a Boolean satisfiability problem, and designed and implemented a novel, efficient protocol for proving UNSAT in zero-knowledge.
Building on research that earned Wang and collaborators runner-up for the 2021 ACM CCS Best Paper Award, the protocol enables security applications such as verification of program safety without revealing the structure of the proof itself, which may reveal sensitive intellectual property; and verification that a secret program developed by a code producer is safe and functional.
“Zero-knowledge proofs for NP problems have been widely studied, but zero-knowledge for co-NP was only a feasibility result. This paper, for the first time, shows that zero-knowledge for co-NP can achieve reasonable efficiency,” said Wang, a member of the Northwestern Security and Privacy Group. “One direct application is to prove that a private program or private smart contract is secure with regard to some definition without revealing the program.”
Wang and the coauthors plan to extend the system for more powerful logic solvers and build an end-to-end provably secure private program execution.
Wang’s research in zero-knowledge is supported by the Defense Advanced Research Projects Agency (DARPA) SIEVE program, which aims to advance the state of the art in zero-knowledge proofs to enable complex, applications relevant to the Department of Defense.
The CCS is the flagship annual conference of the ACM Special Interest Group on Security, Audit and Control (SIGSAC). The annual event draws information security researchers, practitioners, developers, and users. Accepted submissions present new research related to practical aspects of computer security and privacy.