The UCL information security group’s Jens Groth, a cryptographer, is one of 17 UCL researchers who have been awarded a Starting Grant by the European Research Council. The five-year grant will fund his work on the cryptographic building block known as “zero-knowledge proofs”, a widely applicable technique that underpins both security and trust. ERC Starting Grants are intended to support up-and-coming research leaders who are beginning to set up a research team and conduct independent research. Groth’s focus is on making zero- knowledge proofs more efficient so that they can become cheap enough to become a commonly used, standard security technology. Groth is also the recipient of a second grant from the Engineering and Physical Sciences Research Council to fund his work on another related topic, structure-preserving pairing-based cryptography.
“My line of thinking,” says Groth, “is that there’s been a lot of research into zero-knowledge proofs, but I don’t know of any groups taking entire systems from theory through to very practical implementations. I am hoping to build a group that will cover this entire span, and by covering it thoroughly get some very significant gains in efficiency.” Covering that entire spectrum from the purely abstract to the built system is important, he says, because “Practice can influence theory and give us some insight into what we should be looking at. Also, when you start implementing things, lots of surprising discoveries can come up.”
Unlike other types of cryptographic tools, such as public key cryptography, used in such widely used mass-market applications as SSL (used to secure data passed over the Web while in transit), Groth notes that zero-knowledge proofs are more likely to be a behind-the-scenes technology that end users will never touch directly.
“It will be hidden inside the system,” he says. “The main properties we want are completeness, soundness – and zero-knowledge.” Completeness means the prover can convince the verifier when a statement is true. Soundness means the prover cannot convince the verifier when the statement is false. Finally, zero-knowledge means that there is no leakage of information even if the prover is interacting with a fraudulent verifier.
The basic concept behind zero-knowledge proofs is relatively simple although the underlying mathematics is complex. The goal is to give strangers a way to trust each other – that is, to verify that a particular statement is true – without having to disclose secret information. Take, for example, an investor who is asking a hedge fund manager to prove that his money is safe. The hedge fund manager (the prover), to whom the details of how the money is invested are trade secrets that can’t be disclosed needs to provide reassurance to the investor (the verifier). In a system designed for electronic voting, zero-knowledge proofs can be used by the election commissioner to verify that a vote is valid without disclosing which candidate any particular voter chose. Or, finally, in a system to send anonymous email, zero-knowledge proofs can guarantee that a message hasn’t been altered without disclosing the identity of the sender or the message’s contents. Groth’s interest in this area derives from an early interest in electronic voting.
The quest to make zero-knowledge proofs more efficient began almost as soon as they were invented in 1985 and were, as Groth puts it, “horribly inefficient”. In addition, the earliest concept required direct interaction; advances since have included creating the basis for non-interactive zero knowledge proofs, where given a trusted setup such as a common reference string provided by a trusted source the prover only needs to send a single message to convince the verifier.
A key milestone came in 2006, when Groth and fellow researchers Rafail Ostrovsky and Amit Sahai presented a paper at Eurocrypt, to be published later in 2012 in the Journal of the Association for Computing Machinery as “New Techniques for Noninteractive Zero-Knowledge”. This paper introduced a new paradigm for constructing non-interactive zero-knowledge proofs based on pairing-based techniques derived from the mathematical field of algebraic geometry.
A second milestone came two years later, when Groth became the first to propose the first general non-interactive zero knowledge proofs that are efficient enough to be used in practice. Groth and Amit Sahai presented Efficient Non-interactive Proof Systems for Bilinear Groups at Eurocrypt 2008.
Historically zero-knowledge proofs have been inefficient and require significant computing resources when used in complex systems. This is what Groth hopes to change with his research so that zero knowledge proofs become a standard feature providing security against active attacks.