Professor Ian Goldberg and former Cheriton School of Computer Science doctoral students Aniket Kate and Gregory Zaverucha have received the 2025 Asiacrypt Test-of-Time Award. Their paper, Constant-Size Commitments to Polynomials and Their Applications, was presented originally at Asiacrypt 2010, the 16th International Conference on the Theory and Application of Cryptology and Information Security.
The Test-of-Time Award honours a paper presented 15 years earlier that has had a significant and lasting impact on the theory and practice of cryptography and information security.
“Congratulations to Ian and his colleagues, Aniket and Greg,” said Raouf Boutaba, University Professor and Director of the Cheriton School of Computer Science. “Their significant and enduring work on polynomial commitment schemes significantly reduces communication costs in cryptographic systems, allowing for more scalable and efficient secure protocols.”
L to R: Ian Goldberg, Aniket Kate, Gregory Zaverucha
Ian Goldberg is a Professor at the Cheriton School of Computer Science and the Canada Research Chair in Privacy Enhancing Technologies, a position he has held since 2019. He was named a Fellow of the Association for Computing Machinery and a Senior Member of IEEE in 2023. His research has received numerous distinctions, including the USENIX Security Test of Time Award in 2019, and the Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies in 2018. Professor Goldberg is the only person whose papers with students have received the Andreas Pfitzmann Best Student Paper Award three times — in 2013, 2018 and 2023 — at the Privacy Enhancing Technologies Symposium.
He was named an ACM Distinguished Member in 2017, received the Electronic Frontier Foundation’s Pioneer Award in 2011, the Outstanding Young Computer Science Researcher Award from the Canadian Association of Computer Science in 2011, and an Early Researcher Award from CS-Can | Info-Can in 2010.
Aniket Kate is an Associate Professor of Computer Science and a University Faculty Scholar at Purdue University, where he also serves as research head at Supra. His research builds on and expands cryptography, distributed computing, and game theory to solve security and privacy problems in decentralized environments. His current projects focus on distributed ledgers and secure computations. He is a recipient of the 2019 NSF CAREER Award.
He received his PhD in Computer Science from Waterloo in 2010 under the supervision of Professor Goldberg.
Greg Zaverucha is a software engineer in the Microsoft Research Security and Cryptography group. He conducts research in applied cryptography, implements cryptographic primitives and systems, and helps product teams use cryptography securely.
Before joining Microsoft, he worked in applied research, standardization and product security at Certicom/Blackberry. He received his PhD in Computer Science from Waterloo in 2010 under the supervision of Professor Douglas Stinson.
More about this research
In their paper, the researchers introduce and formally define polynomial commitment schemes, and present two efficient constructions. Polynomial commitment schemes are a cryptographic method that allows someone to commit to a polynomial so that others can verify claimed evaluations of it without learning the entire polynomial. Commitment schemes are fundamental components of many cryptographic protocols that require both secrecy and verifiability.
Although homomorphic commitment schemes can achieve similar goals, the sizes of their commitments are linear in the degree of the committed polynomial. In contrast, the polynomial commitment schemes introduced by Ian Goldberg, Aniket Kate and Greg Zaverucha are of constant size. Moreover, the overhead of opening a commitment — the number of bits transferred — is also constant. Opening even multiple evaluations requires only a constant amount of communication overhead.
To demonstrate their usefulness, the researchers applied their schemes to four cryptographic problems: verifiable secret sharing, zero-knowledge sets, credentials, and content extraction signatures.
Nomination statement
The work’s significance lies in its ability to dramatically reduce communication costs in cryptographic systems that depend on polynomial commitments. The nomination statement to the Asiacrypt 2025 award committee highlighted the paper’s lasting impact, detailing how introduction of polynomial commitment schemes has become a foundational tool in both cryptographic research and its applications. An excerpt from the nomination statement follows.
“The concept of polynomial commitments introduced in this paper is now central in the design of (succinct and/or zk) proof systems. Many proofs are now designed as polynomial interactive oracle proofs, which can be efficiently compiled with any polynomial commitment scheme. In the blockchain space, polynomial commitments are used to commit to the entire state of the blockchain. In secure distributed computing, polynomial commitments enable efficient verifiable secret sharing (VSS) and verifiable information dispersal schemes. The impact on academic research is supported by the paper’s high citation count (1,000+).
“The paper offered an efficient polynomial commitment scheme (often called KZG) based on bilinear pairings, where the commitment to the entire polynomial is a single group element, independent of the degree of the committed polynomial, and the proof of evaluation is also a single group element. The commitment is homomorphic, batches efficiently, and has since been extended to the multi-variate setting. The KZG construction remains unique among known constructions as having the most succinct opening proofs and efficient verification. Improvements along one axis always seem to come with performance drawbacks along another axis; no new scheme to date is strictly better.”
To learn more about the research on which this article is based, please see Aniket Kate, Gregory M. Zaverucha, Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In: M. Abe (eds). Advances in Cryptology – ASIACRYPT 2010. ASIACRYPT 2010. Lecture Notes in Computer Science, vol 6477. Springer, Berlin, Heidelberg