Cryptographic Research Receives Distinguished Paper Award at ACM CCS 23

A team of cryptographers received recognition from the Conference on Computer and Communications Security (CCS) in November for creating a cryptographic method for zero-knowledge proofs more efficient than some of the most advanced methods developed in recent years.

Georgia Tech Professor Vlad Kolesnikov and Ph.D. candidate Yibin Yang received a distinguished paper award for their work, Batchman and Robin: Batched and Non-batched Branching for Interactive ZK.

Zero-knowledge proofs are cryptographic schemes allowing someone to prove a statement is true without revealing any additional information to the verifier.

For example, in a bug bounty program, an ethical hacker has discovered a problem in a company’s software. The hacker wants to prove the bug exists without revealing to the company, the verifier, anything about how the exploit works.

With a zero-knowledge proof, the prover can demonstrate the bug’s presence in the program without disclosing any problematic inputs. The main difficulty is that the execution path - along with specific CPU instructions that were executed - must be hidden from the verifier. 

“Traditionally, this was achieved by both prover and verifier evaluating each possible CPU instruction at each step, incurring significant costs,” said Kolesnikov. “At the core of our improvement is a new mechanism for verifiable evaluation of a conditional statement. Because a CPU step is really a large conditional, this immediately implies greatly reduced cost.”

While zero-knowledge proofs are complex, they are Yang’s specialty. The Ph.D. student has been studying these proofs with Kolesnikov as his advisor for the past several years in the School of Cybersecurity and Privacy (SCP). The CCS recognition has encouraged and motivated Yang to continue designing advanced zero-knowledge schemes to help deploy them in practice.

“Winning this award is a great honor and shows that the security community recognizes the importance of efficient zero-knowledge systems for high-level programming languages. It’s like a gift to me and, I think, for all co-authors,” said Yang.

“SCP is one of the top places in the world for highly technical and practically relevant cryptography and security research.”

Yang and Kolesnikiv worked with co-authors from University of Illinois Urbana-Champaign, Bar-Ilan University and Ligero Inc. on the CCS 23 award-winning paper.

Two of the ‘heroic’ ZK proof systems Yang and Kolesnikov improved on also follow a superhero motif. Developed at peer institutions, QuickSilver (CCS 21) and AntMan (CCS 22), were used as a benchmark for Batchman and Robin.