We held our annual ACE-CSR event in November 2016. The last talk was my inaugural lecture to full professor. I did not write the summary below myself, hence the use of third person, not because I now consider myself royalty! 🙂
In introducing Jens Groth, professor of cryptology, George Danezis, head of the information security group, commented that Groth’s work provided the only viable solutions to many of the hard privacy problems he himself was tackling. To most qualified engineers, he said, the concept of zero-knowledge proofs seems impossible: the idea is to show the properties of a secret without revealing them. A zero-knowledge proof could, for example, verify the result of a computation on some data without revealing the data itself. Most engineers believe that you must choose between integrity and confidentiality; Groth has proved this is not true. In addition, Danezis praised Groth’s work as highly creative, characterised by great mathematical depth and subtlety, and admired Groth’ willingness to speak his mind fearlessly even to government funders. Angela Sasse, head of the department, called Groth’s work “security tools we’re going to need for future generations”, and noted that simultaneously with these other accomplishments Groth helped put in place the foundation for the group as it is today.
Groth, jokingly opted to structure his talk around papers he’s had rejected to illustrate how hard it can be to publish innovative research. The concept of zero-knowledge proofs originated with a 1985 paper by Shafi Goldwasser, Silvio Micali, and Charles Rackoff. Zero-knowledge proofs have three characteristics: completeness (the prover can convince the verifier that the statement is true); soundness (the claiming prover cannot convince the verifier when the statement is false); and secrecy (no information other than the truth of the statement is leaked, even when the prover is interacting with a verifier who cheats). Groth illustrated the latter idea with a simple card trick: he asked an audience member to choose a card and then say whether the card was a heart or not. If the respondent shows all the cards that are not hearts, counting these proves that the selected card must be a heart without revealing what it is.
Zero-knowledge proofs can be extended to think about more complicated statements. Groth listed some examples:
- Assert that a logical formula has an assignment to the variables that makes it true
- Verify that a graph is Hamiltonian – that is, there is a path that touches each vertex exactly once
- That a set of inputs into a Boolean circuit will produce an output of 1
- Any statement of the general form U belongs to some NP-language L
Groth could see many possible applications for these proofs: signatures, encryption, electronic cash, electronic auctions, internet voting, multiparty computation, and verifiable cloud computing. His overall career has focused on building versatile and efficient proofs with the goal of moving them from being expensive and slow to being just a fraction of the cost of the task that’s being executed so that people would stop thinking about the cost and just toss them in as a standard part of any transaction.
Groth began his work in this area as a PhD student in the security provider Cryptomathic with a project on internet voting. In that system, the vote was encrypted and submitted as ciphertext to the election authorities. They then used cryptographic techniques to tally the result without decrypting any individual encrypted votes. Zero-knowledge proofs made it possible both to ensure the integrity of the vote without revealing the vote cast, and to prove that the encrypted data is a valid vote – a crucial point in making sure that someone hasn’t gamed the system by voting multiple times or deducting votes from a particular candidate’s tally inside their ciphertext. However, the cost of using them was significant: it took several minutes for a voter to prove their vote was valid, an unacceptably long amount of time. Groth and his colleagues at Cryptomathic managed to reduce the time to seconds and build a viable internet voting system.
The efficiency of zero-knowledge proofs can be measured in the time it takes for the prover and verifier to compute them, number of bits that need to be transmitted, and how many messages that need to be exchanged. A crucial distinction is whether the proof is interactive or non-interactive. Non-interactive proofs require only one message instead of a repeated exchange. More than that, non-interactive proofs afford additional opportunities: they can be attached to an email, inserted in a document, and copied to as many verifiers as you like.
In 2005, Groth took up a post-doc at UCLA, where he began working on unconditional, non-interactive zero knowledge that would guarantee everlasting privacy. Cryptographic protocols often depend on assumptions about what mathematical functions an adversary can compute; for example, that it’s hard to factor large integers. Without disproving P=NP, the biggest open theoretical problem in computer science, it’s impossible to verify these assumptions. An “unconditional” zero-knowledge proof accordingly means that the zero-knowledge property holds even if the adversary has infinite computing power. In 1986, Gilles Brassard and Claude Crépeau had shown it was possible to create unconditional interactive zero knowledge proofs. Unconditional non-interactive proofs would have obvious benefits: adversaries storing such proofs could not hope advances in computing power would eventually allow them to extract useful information.
In 2006, Groth, with Rafail Ostrovsky and Amit Sahai, managed to solve this problem. First, the group established that existing techniques were not a useful approach. Groth instead sought to blend recent techniques developed for pairing-based cryptography with the work already done on non-interactive zero knowledge. At a conference, however, he fortuitously encountered a new pairing-based encryption scheme introduced by Boneh, Eu-Jin Goh, and Kobbi Nissim, which provided double-homomorphic public key encryption.
Homomorphic encryption sounds like wizardry the first time you hear about it: the technique allows computation to be performed on encrypted data without decrypting it. Techniques had already been established for additive homomorphic encryption – that is, that when you multiply together two ciphertexts the underlying plaintext contains the sum of their two plaintexts. Boneh-Goh-Nissim showed that homomorphic cryptography can also be multiplicative, a mathematical operation known as a pairing allows the creation of a ciphertext that contains the product of two plaintexts. Once he had his eureka moment, finding that this work could enable non-interactive zero knowledge proofs was, he said, “the easiest thing I’ve ever done in my career”.
Groth applied these ideas to Boolean circuit satisfiability, where the prover wants to convince the verifier that there exists an input for the circuit that will make it output 1. Boolean circuit satisfiability is very versatile and has a property known as NP-completeness, which means other types of statements can be rewritten as a Boolean circuit satisfiability problem. Groth and his co-authors published their resulting paper at Eurocrypt 2006.
Groth’s new technique provided unconditional non-interactive zero-knowledge based on standard assumptions, which had been a long standing open question in the cryptographic community. Moreover, it did so at a cost of kilobytes per gate, so the research was also a big leap forward in efficiency from the gigabytes per gate other methods used. The work thus initiated a process taking zero-knowledge from being a theoretical concept to being implementable.
However, what Groth wanted, like most cryptographers, was to prove the validity of specific statements arising in cryptographic protocols more efficiently than using generic Boolean satisfiability. In 2008, Groth completed what he in constrast to the previous work called his hardest paper to write, outlining an efficient non-interactive proof system. The equations used in the proof system took many months of painstaking puzzling back and forth to find. However, the result was a very simple proof system that could be used to give direct and efficient proofs for statements relating to pairing-based cryptography. The non-interactive zero-knowledge proof system is now used in numerous cryptographic schemes applications and is still today the state of the art system.
Groth did not stop here, since even though the proofs were very efficient for small statements, their cost would still grow proportionally to the complexity of the statements. He therefore set the goal to create constant size proofs, which would remain small even for large and complex statements. Switching from encryption of the witness as in the previous constructions, he now used commitments. The advantage of commitments is that they can be very compact, smaller than the size of the committed values, since they do not need to be decryptable. Using commitments, Groth found a way to check many gates in parallel inside the commitments, yielding constant size proofs, which have later been dubbed “succinct non-interactive arguments of knowledge” or SNARKs. Groth continues working in this area, and his latest research on SNARKs has given proofs that are less than 200 bytes, even for very large and complex statements.