Danish researcher explains zero-knowledge proofs and post-quantum encryption
A graduate from the University of Aarhus, a Danish researcher is now a leading player in some of the most important issues in cyber security
By
Pat Brans,Pat Brans Associates/Grenoble Ecole de Management
Published: 26 Apr 2022 14:15
A native of Denmark, Jens Groth became interested in cryptography as a student at the University of Aarhus, where he obtained a master’s degree in mathematics and a PhD in computer science – specifically in cryptography. From there, he went to the University of California, Los Angeles (UCLA), where he took a postdoc that revolutionised “zero-knowledge proofs” – a technology that has become very important in blockchains.
Groth has been working on zero-knowledge proofs ever since, making more major contributions along the way.
A zero-knowledge proof is a protocol between two parties – a “prover” and a “verifier”. Through an interaction, the prover demonstrates to the verifier that something is true but doesn’t reveal any specific information about why it is true.
“This idea goes back to the 1980s,” says Groth. “Computer scientists were looking at the concept of mathematical proofs and noticed the magical fact that you don’t actually have to give information beyond the fact that something is true.
“In my research, I introduced some new techniques for building zero-knowledge proofs in a more efficient manner, allowing the proofs to be extremely compact. You can have a huge, complicated statement that takes up gigabytes of space and you can prove that it’s correct with just a few hundred bytes. That is super compact.”
Groth adds: “I got into this area when I was doing my PhD and was looking at voting protocols. There you have voters encrypt their votes, so nobody else sees what their vote was. There are some tallying mechanisms, so you can aggregate a lot of encrypted votes and get out the right results without looking inside each individual ciphertext.
“But those aggregation methods mess up if voters input invalid votes. For example, you could have somebody input minus 1,000 votes for Alice in their ciphertext. It turns out that you can use zero-knowledge proofs to prove that the ciphertext you’re sending contains a correct vote – that it’s one of the eligible options – without indicating which of those options it is.”
These same protocols can be used in many other ways. They could allow a user to show that they fall within a certain age range, without having to reveal exactly how old they are. Users could also prove they have sufficient income to obtain a loan, without having to disclose the exact income or the sources.
Groth describes zero-knowledge as a “Swiss Army knife” for assurance. When a computer runs a protocol, you can use a zero-knowledge proof to ensure it is doing so correctly and without deviation from the protocol. And this assurance comes with total privacy – the zero-knowledge proofs do not reveal confidential data that the computer holds.
The remaining challenge is to make the zero-knowledge proofs efficient enough that they do not cause an unacceptable slowdown. Groth’s inventions have drastically reduced this cost – and have inspired more research. Finding further efficiency improvements is now a very active area of research.
The Internet Computer
Groth has transitioned from academia to industry and now applies his expertise to the Internet Computer, which was founded on the idea of having a distributed computer platform that never shuts down. The idea is that just like you have a shared internet, you can have shared computing services that everyone can access, and developers can build upon. The intention is to protect not only against technical failures and attacks, but also against corporate control, through decentralised governance.
All computation is replicated on multiple computers running in different datacentres around the world, so even if one of them breaks down, or gets hacked, the Internet Computer still runs.
Groth is director of research at DFINITY, a not-for-profit organisation based in Zurich that built and launched the Internet Computer. The platform is open source and DFINITY is currently its biggest contributor. The long-term vision is to grow a large community around the Internet Computer, with DFINITY being only one of many contributors.
The Internet Computer uses blockchain technology to allow machines around the world to come to an agreement about the order in which they execute inputs. Getting agreement among machines comes with a cost, however.
“For any blockchain, it is expensive to write to the blockchain,” says Groth. “Every time you do a write, all the machines have to be updated in exactly the same way. They have to reach a consensus on what that way is. All the machines talk back and forth and agree on the order in which they want to execute all the incoming messages from thousands of users.
“The Internet Computer has a mechanism built in to make it resilient to this situation”
Jens Groth
“If one of the machines is down, or cannot connect to another machine, it doesn’t get to vote on the order of the messages. The Internet Computer has a mechanism built in to make it resilient to this situation – it requires only a super majority of machines to agree, so if one of the machines is hacked, the rest can continue without it.”
One important aspect of the Internet Computer is that it provides general-purpose computation. Developers can create applications on it, using their favourite language. Most people program in Rust or Motoko, which is a special language developed by DFINITY. They compile their code to something called WebAssembly, which is closer to machine code. This allows developers to write an application and deploy it around the world. By doing this on the Internet Computer, the application is executed with guaranteed security.
The Internet Computer is expected to be a major enabler of Web3, the next iteration of the World Wide Web, which will be highly decentralised and powered by blockchain technologies. Futurists speculate that this decentralised version of the Web would reduce the reliance on major technology players, such as Google and Facebook, and more cooperative business models could be developed with less reliance on advertising revenue.
Web3 would also lead to decentralised finance, allowing users to exchange currency in the form of tokens, without involving banks or governments.
But such a big overhaul is not expected in the current decade. This means that by the time Web3, or some variant, becomes dominant, quantum computing may have become practical. If that is the case, a whole new set of security concerns will have to be addressed.
Post-quantum security
“We have known for a long time that quantum computers will be able to break some of the cryptography we use today,” says Groth. “Not all cryptographic algorithms will be susceptible to quantum attacks, but some of the most popular will. Anything based on either the discrete logarithm problem or the factorisation problem needs to be changed.
“Quantum computing is not at the point where we can break key cryptography as it is deployed today on the internet. We don’t know exactly how long that is going to take, but it’s definitely on the horizon, and we need to prepare for it now because it takes a long time to develop and deploy the cryptography that we will need to protect against quantum computers.”
Groth adds: “There is a distinction to be made in the cryptography we use to check things and the cryptography we use to store or exchange information. For instance, if I create a digital signature on a document, send it to you and you check it right now, we don’t have to worry because quantum computers are not at a state where they can forge the digital signatures commonly used.
“However, when information is stored or exchanged in encrypted messages, it is important to think about post-quantum cryptography right now. An attacker could intercept a message and save it for five or 10 years, then use a quantum computer to decrypt it.
“Secure multi-party computation is an example of something that requires post-quantum protection. Its goal is to facilitate computation with privacy. In order to keep confidential information private, you have to encrypt the data. You also have this storage problem. If a hacker takes and stores all the communication for a few years – until quantum computers become real – then when they get access to a quantum computer, they can decrypt the information they have stored.”
Groth notes that organisations such as the National Security Agency in the US are already storing encrypted information that they might decrypt later when quantum computing can break the cypher. Intelligence agencies in other countries around the world are certainly doing the same.
Fortunately, the cryptographic community is waking up to this concern. The National Institute of Standards and Technology has been organising competitions for researchers to standardise new cryptographic protocols that are secure against quantum attackers.
“We are definitely interested in post-quantum security at DFINITY,” says Groth. “Currently, our cryptography relies on the discrete logarithm problem. This works well now, but in the long run it would jeopardise the Internet Computer. Take, for instance, our digital signatures. We use them to certify all data that is coming from the Internet Computer. If you had a quantum computer right now, you could just go and impersonate somebody.
“We have known for a long time that quantum computers will be able to break some of the cryptography we use today”
Jens Groth
“We need to find a replacement technology for that. We don’t need to implement it right now, but we would need to have it ready before quantum computers become a real thing.”
Post-quantum security is critical for the future not only of the Internet Computer, but also for blockchain in general, banking transactions, and a lot more. In many cases, the Internet Computer relies on standard protocols that are in widespread use. For example, digital signatures and transport layer security (TLS) are both used.
Groth does not expect to have to work much on these standard protocols, because the wider cryptographic community is already working to standardise post-quantum digital signatures and TLS. The task of people working on the Internet Computer will just be to find the best one of those tools and implement it. The challenge is in the advanced solution that the Internet Computer uses.
“Not only do we have to tweak our protocols to use some of the post-quantum security solutions being developed, but we also have to come up with some tools ourselves,” says Groth. “There are areas, sophisticated special-purpose solutions, where we cannot expect the community to solve problems for us. We want to keep the same functionality and security for the Internet Computer without being vulnerable to quantum attacks. There is a lot of research to do on that.
“And then there’s a final thing, which is cryptography that we don’t have yet, but also needs to be post-quantum secure. One of the research projects we have is to build in confidentiality on the Internet Computer. We want to be able to encrypt the data that the Internet Computer holds. We may want to compute on encrypted data such that nobody can learn what’s going on. We want a trusted runtime environment.”
Groth adds: “There are different approaches. One is that you could have a trusted execution environment ,which is basically you trust that the chip has a trusted execution environment. The idea is that if you tamper with it, it will break. The problem is that it’s hard to rely on hardware because there have been quite a lot of attacks in these trusted execution environments.
“If you’re shipping hardware and you find a bug later, it’s hard to replace. An alternative approach is secure multi-party computation, which relies on cryptography to protect confidentiality. But this relies very much on encryption and so needs to be post-quantum secure.“
The changing role of trust
Breakthroughs in cyber security, such as the invention of public-key cryptography, have enabled internet commerce, where two or more parties who have never met and will never meet are able to establish a secure link and exchange money. With increasing decentralisation and more reliance on peer-to-peer exchanges, cyber security is likely to become even more important in the coming decades.
Economies are becoming increasingly dependent on electronic exchanges, and banks and governments no longer have the control they had before. At first glance, you might assume more trust is required. But, thanks to researchers like Jens Groth, the need for trust has diminished – computer systems can be made to cooperate without reliance on a central party.
Read more on IT innovation, research and development
