Jens Groth, World-Renowned Cryptographer and Principal Researcher at DFINITY, Receives the IACR Test-of-Time Award for the second time.
“Zero-knowledge proofs allow you to prove a statement is true without revealing anything else but the fact the statement is true,” explains Jens Groth, as he pulls out a deck of cards to illustrate what he means by this. “Let’s say I pick a card, look at it, and tell you it’s a red card. What I tell you could be true or false, and sure, I could show you the card to prove it’s really red, but showing you the card would reveal more than just the fact that the card is, in fact, red.” Groth then spreads out a pile of all the black cards with the red card face down. “Now you know the card is red, but not that it’s the queen of hearts, for example.”
This is how Groth — a leading cryptographer known for revolutionizing the area of zero-knowledge proofs with the invention of practical pairing-based non-interactive zero-knowledge (NIZK) proofs — humbly explains the essence of the research paper he co-authored with Amit Sahai. This very paper, titled Efficient Non-interactive Proof Systems for Bilinear Groups, has been used in many research works that followed to develop practical cryptographic schemes and applications, since its publication at Eurocrypt 2008. Today, the International Association for Cryptologic Research (IACR) is crowning the authors with a Test-of-Time award for the lasting impact their proofs have had on public key cryptography.
“I’m very happy and proud that the Test-of-Time award recognizes this piece of research as an important step in that evolution. I long had an intuition that zero-knowledge proofs hold a lot of potential for applications, but back then the actual use cases were still specialized to specific cryptographic protocols. Now, the whole field of zero-knowledge proofs is blooming, and seeing both research and engineering making a lot of progress in tandem shows how important the general field has become.”
How it All Started
It all started with a love for mathematics but also a desire to work in a field where research can be translated into practical applications. Groth began to attend various cryptography courses during his time at Aarhus University, fully unaware of his luck in being taught by world-class cryptographers like Prof. Peter Landrock and Prof. Ivan Damgaard. He ended up doing a MSc under Prof. Damgaard’s supervision, and later an industrial PhD in collaboration with a company called Cryptomathic, which was developing an e-voting solution at the time.
After completing his PhD, Groth took a postdoc position at UCLA where he met his co-author Amit Sahai. The line of research leading to the Groth-Sahai winning paper got started by wanting to connect the construction of non-interactive zero-knowledge proofs to pairing-based cryptography, which had shown itself versatile in other cryptographic constructions. An initial work with Rafail Ostrovsky and Amit Sahai first showed that you could use pairings to build efficient NIZK proofs that show a Boolean circuit has a satisfying input that makes the circuit output true. However, the kind of statements you want to prove in cryptographic protocols are usually not expressed directly as Boolean circuits.
In a later paper, which won the IACR test-of-time award in 2021, Groth demonstrated that it’s possible to give pairing-based NIZK proofs that work directly for the kind of statements that arise naturally in pairing-based cryptography. The downside is that these NIZK proofs are very expensive. Persisting, Groth asked the next logical question: whether there are NIZK proofs that are both efficient and broadly applicable in pairing-based cryptographic protocol design.
Over several grueling months Groth and Sahai managed to continually reduce the complexity of the NIZK proofs to be small in size, and also formulate a general description of statements they can prove that express most of the operations in pairing-based cryptography.
NIZK Proofs in a Nutshell
What it comes down to is, this research explores how cryptography enables us to prove statements about digital data in a way that nothing else is revealed but the truth of the statement. Essentially, zero-knowledge proofs allow the prover to demonstrate she/he is acting in accordance with a protocol or an expected behavior without revealing her/his confidential data. There are many possible practical use cases where NIZK proofs would be useful. For example, in an e-voting protocol you may want to prove that an encrypted vote is valid for one of the possible candidates and that it’s not a double vote or a negative vote. Another use case would be in a managed fund, where you may want to prove solvency without revealing the composition of assets.
Applications
Whatever the use case, zero-knowledge proofs need to be efficient. Groth-Sahai zero-knowledge proofs are non-interactive, meaning they do not require back-and-forth communication between the prover and verifier. The prover just constructs a proof that can be sent in a single message to the verifier — like showing all the black cards at once. They are also reasonable in size, growing proportionally with the complexity of the statement. Moreover, they can be applied directly to the kind of statements cryptographers usually want to express when they design pairing-based protocols.
The NIZK proof systems that Groth and Sahai constructed are being used in pairing-based cryptographic schemes, such as ring signatures, group signatures, encryption schemes, etc. Often a scheme has several sub-components and NIZK proofs can serve as a sort of glue holding them together by proving that the components are correctly constructed and consistent with each other. There has also been some research on structure-preserving cryptography, a purist way of doing pairing-based cryptography that lends itself particularly well to Groth-Sahai proofs.
Subsequent work by Groth and other researchers in the field have shown that you can get even better efficiency with something that has since been labeled Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARKs). Groth-Sahai proofs work well on small-scale statements, whereas zk-SNARKs are ideal for large-scale statements. SNARKs form the core of several privacy-focused blockchain. They are also the foundation of zk-rollups, which allow people to do off-chain computation and submit the end result to a blockchain together with a succinct NIZK proof that the end result is correct. SNARKs are ideal here as they are compact, which means storage and communication cost is low, and require little computation to verify.
Groth and the Internet Computer
While Groth mainly focuses on the security of the Internet Computer Protocol, he has designed some special-purpose zk-SNARKs that the Internet Computer uses in the distributed key generation protocol.
Beyond DFINITY, there are developers in the Internet Computer ecosystem implementing zero-knowledge proofs to the protocol. Jordan Last of Demergent Labs has been a strong advocate of using zkWasm to provide additional guarantees for correct computation of smart contracts on the Internet Computer, and Wyatt Benno from ICME is developing a prototype.
Groth on Life
Groth likes to spend his free time doing improvisation theater and playing badminton. And when he’s not thinking about cryptographic proofs and the security of the Internet Computer, Groth fills his mind reading about politics, economics, history, and contemplates the potential positive benefits of things like technological progress on society. While the sophistication of modern society gives us enormous benefits, he recognizes no single human can grasp modern society in its entirety, which he worries can create a democratic deficit. Groth’s hope is that zero-knowledge proofs can help here:
“Philosophically speaking, SNARKs tell us that the cost of verifying a statement can be much smaller than the complexity of the statement itself. Extrapolating from this concept, even if we cannot grasp all of society, maybe we can verify the things that matter to us. Misinformation, in particular, is a problem where zero-knowledge proofs may be part of the solution.”
About Jens Groth
Jens Groth is a leading cryptographer whose works have been published at the top cryptology conferences ASIACRYPT, EUROCRYPT and CRYPTO over the last decade. His work has revolutionized the area of zero-knowledge proofs with the invention of practical pairing-based non-interactive zero-knowledge proofs, which was recognized early on with the UCLA Chancellor’s Award for Postdoctoral Research in 2007 and now by two IACR Test-of-Time awards.
About the IACR Test-of-Time Award
The IACR Test-of-Time Award is an annual award given at the IACR General Conferences (Eurocrypt, Crypto, and Asiacrypt). It recognizes outstanding papers that have had a lasting impact on public key cryptography and were published 15 or more years prior.
Written by Angela Harp
