Zero Knowledge Proofs (ZKPs) hinge on a beautifully complex interplay between mathematics and computer science. It’s such an eerie concept that it almost seems unreal. Essentially, a zero-knowledge proof demonstrates that a statement or a condition is true without revealing any information beyond the validity of the statement itself. You can’t know what the thing is, just whether it’s true or not.
A curious concept
“The definition of zero-knowledge proofs is quite mind-boggling,” says Avi Wigderson, a prominent figure in the field of theoretical computer science who is recognized for his work on zero-knowledge proofs. “It suggests that there might be theorems for which you have proofs — but there may also exist another proof that does not reveal anything except the fact that the theorem is true. You learn nothing else from the proof. They call this the zero-knowledge proof, you learn nothing from the proof except that it’s true.”
If that sounds too complicated, let’s take an example.
Imagine you have two balls of the same size and shape, one red and one green, but your friend is color-blind and cannot distinguish between them. You claim that the balls are of different colors. How can you prove this without revealing which one is red and which one is green?
You ask your friend to hide the balls behind their back and either switch them between hands or keep them in the same hands. Then, they present the balls to you again. Because you can see the colors, you can correctly state whether or not the balls were switched. Repeating this process enough times, without making any mistakes, convinces your friend that the balls are indeed differently colored, without you ever revealing which is which.
It’s a completely different, probabilistic way of proving things — and it isn’t applied just to mathematics and cryptography. It’s applied a lot in the real world.
Probabilistic proofs
This concept, introduced in the 1980s by Shafi Goldwasser, Silvio Micali, and Charles Rackoff, revolutionized the way we think about privacy and security in digital communications. In a sense, it paved the way for modern cryptography and revolutionized proofs in general.
Proofs were studied for over two thousand years, since the age of the Ancient Greeks, says Yael Tauman Kalai. Kalai is a distinguished researcher in the fields of cryptography and theoretical computer science, with significant contributions to zero-knowledge proofs. She also has her definition of what a ZKP is.
“The idea is beautiful and simple. Suppose you want to give someone a proof. Usually, when people think about proofs, they think of mathematical proofs where you just verify things line by line. But suppose that your goal is to give a proof that reveals no information about why the theorem is true. So, you want to convince someone that the statement or the theory [you try] to prove is correct is true, without revealing any additional information beyond the validity of the actual statement. This is what a zero-knowledge proof is.”
Think of it this way: a mathematical proof is a complete, step-by-step demonstration of the truth of a statement. It’s transparent, everything is out in the open, and it can be publicly verified and repeated. Meanwhile, a zero-knowledge proof is a minimal information proof that requires a verifier. It’s designed to preserve privacy so it’s not open, and the need for a verifier means it’s often interactive.
This is all reasonably intuitive — or at least, understandable. But a mathematical proof doesn’t work on intuition and “understandable”. You need a rigorous framework. What is “reveal” — what is “information”?
“That’s the beauty in this zero-knowledge work, how do you make it precise and mathematical? In order to do that, they actually needed to change the way we even think about proofs,” says Kalai.
Errors close to zero
When the idea of a zero-knowledge proof was first published, it was regarded with a bit of skepticism, in part because the concept was so eerie. But it wasn’t long before researchers started to understand just how impactful this concept was. This became even more impactful when researchers found a way to prove any theorem — anything that has a proof — also has a zero-knowledge proof (at least in the context of cryptography).
Wigderson, one of the pioneers behind this work, says that even he found this conclusion strange.
“We proved that despite the seemingly paradoxical nature, there are some theorems that have proofs that are convincing, with extremely high probability, but do not reveal any information besides the validity of the theorem. It’s sort of strange to say the least because we never expect to convince anybody of anything if we don’t tell them something they didn’t know.”
If we want to be mathematically correct, zero-knowledge proofs are not “proofs” in the strictest sense, because there is some small probability (called a soundness error) that the proof is wrong. But that probability is so small it’s virtually negligible. We’re talking about 0.000…1% — with over a hundred zeroes.
This negligible error comes from the nature of the proof. Remember the colorblind ball example? Instead of having proofs where you kind of verify line by line, in your model, proofs are actually an interactive process.
Here’s another example.
Imagine there’s a door locked with a password, and you want to prove to a friend that you know the password without revealing it.
Your friend goes inside the room through another door and chooses to shout from either the room you claim to have access to or from an adjacent room. If you truly know the password, you can enter the correct room every time your friend calls out. By repeating this test multiple times and always going into the room your friend is in, you demonstrate knowledge of the password without ever disclosing it.
The more times you repeat the test, the higher the probability of it being true and not just some random guess. But ultimately, the proof is verifier-dependent, says Kalay.
“If I’m the prover and you’re my verifier, the proof is an interactive process between the two of us, it doesn’t give you the full soundness guarantees that traditional proofs give you. However, with these interactive proofs, the only guarantee is a very, very high probability with a probability 99.999….%. You can make it as close to 100% as you want, but never exactly 100%. So it’s a very different type of proof system. And they defined it rigorously mathematically, how they construct such a proof. So this type of proof is kind of a miracle in my opinion. It’s a statement, which says, any proof any mathematical proof can be converted into zero-knowledge one with some very, very mild cryptographic assumption.”
You can use zero-knowledge proof for many things
Zero-knowledge proofs are more than just a cool concept. They’re already implemented in today’s society, and they actually have some very broad applications. For instance, when you verify someone’s identity online.
“Usually the way it works is I convince you I have some secret key and the secret key is authorized,” explains Kalai. “So one way this is done is through a bunch of public keys that are authorized to enter the webpage. I can just give you my secret key and it’s very easy to see that a secret key is correct. But maybe I don’t want to give you my secret keys — my secret key is my identity. So, I give you zero-knowledge proof instead. A lot of the way cryptography is used today is via these identification protocols or signature protocols that use the zero-knowledge proofs. So, this is really kind of became a little bit, I would say, the bread and butter of cryptography.”
Wigderson also agrees that the applications are broad.
“There are many different cryptographic applications: you want to sign documents, you want to exchange secrets, you want to play poker online, and so on. I mean, a very fascinating example is that you can do it digitally. For this type of thing, different protocols were designed. Then of course, you have to protect against people who don’t play fairly, people want to vote twice or cheat, and zero-knowledge proofs allow you to get rid of this problem in a very simple way: you just demand every player to prove that they are acting according to the protocol. If they do this with zero-knowledge, they don’t disrupt their secrets. So, there is a way to enforce the correct behavior to any participants of any cryptographic puzzle.”
It’s also zero-knowledge proofs that enable blockchain technology to function. ZKPs enable transactions or other data exchanges on a blockchain to be verified without revealing any sensitive information about the transactions themselves. By integrating ZKPs, blockchain networks can provide users with the benefits of transparent, decentralized ledger technology, while also safeguarding their privacy, making it a revolutionary step forward in the evolution of digital transactions.
For this to be practical, however, the computation behind the zero-knowledge proof needs to be done quickly and efficiently. This is something that Wigderson was concerned about. But thanks to research from Kalai and other researchers, this is feasible with today’s technology.
“But one thing is that was worrying is the practicality of this because it was quite complex and heavy, computationally. However, to my amazement, applications that have zero knowledge embedded in them are run every day, including in blockchain technology and digital cash. So, people made it efficient”.
Zero-knowledge in the physical world
Until now, we’ve mostly focused on the cryptographic applications of zero-knowledge proofs. That’s already enough interest, but ZKPs have applications in the physical world as well.
In 2016, the Princeton Plasma Physics Laboratory and Princeton University demonstrated a stunning technique that could be applied to future nuclear disarmament talks. Essentially, the technique would allow inspectors to confirm whether or not an object is indeed a nuclear weapon without recording, sharing or revealing the internal workings which might be secret.
“Zero-knowledge, protocol for nuclear disarmament, for example, developed by Boaz Barak and other physicists, are extremely interesting” says Wigderson. “You can use zero-knowledge proofs between Russia and the United States to show that you will really dismantle this nuclear missile.” The same approach could be used to protect the privacy of people in criminal investigations, for instance.
“There’s also DNA testing. I mean, you want to make sure that if you sample DNA for many people suspected of a crime, you catch the guilty party — but for all the other people, the knowledge of the DNA should disappear from the system for privacy reasons. So, you want zero knowledge of whether the DNA matches.”
Applications are extremely broad. But in an interesting circular way, one important application is in the field of science itself. Kalai, who still works on making zero-knowledge proofs more efficient, says this has enabled scientists to look for proofs of theorems in a very different way.
“As a very interesting consequence of this work (which I think was unexpected), once they incorporated the model of an interactive proof, they basically developed a new proof model. As it turns out, with this model, proofs can be made much more succinct. If you give a classical proof, they’re going to be very, very long, so long that it’s kind of infeasible to verify, sorry, but in using an interactive proof, you can make it very efficient to verify. So, these proofs became much more efficient. “
You could probably never guess that our entire online security hinges on something so bizarre and unintuitive as zero-knowledge proofs. But it does, and the implications of this extend far beyond just securing online transactions. ZKPs are more than just a cryptographic curiosity: they are a pivotal leap in how we approach the delicate balance between transparency and privacy. No doubt, the evolving landscape of digital security and privacy will continue to be shaped by the foundational work of researchers like Wigderson and Kalai.
The researchers’ comments come from press conferences and interviews conducted at the Heidelberg Laureate Forum 2023.
