Verification Without Information: The Promise of Zero-Knowledge Proofs

Many of the transactions we engage in on a daily basis require divulging personal, financial, health, and other information—private details that most of us would rather not repeatedly release into the world. But what if you could provide verification of private information without revealing the information itself at all? It sounds almost nonsensical, but a cryptographic technique known as a zero-knowledge proof can do just that.

Zero-knowledge proofs provide a means to verify, or provide “proof” that one party has knowledge of certain information, without having to reveal any further details beyond that fact. This could mean providing proof of identity without revealing your social security number, address, or anything else; or demonstrating that you have enough funds for a transaction without revealing the balance of your bank account. “Zero knowledge” means that the person or company seeking to verify your information learns no new knowledge beyond the fact that you do indeed know the information or meet a certain qualification.

The idea of providing proof without any actual information might seem mystifying at first. The story of the cave is a classic analogy that explains how zero-knowledge proofs work: Imagine a cave with two entrances, A and B. Inside the cave, the paths of A and B connect through a combination-locked door. Alice (the prover) goes into the cave by one of the entrances. Bob (the verifier) didn’t see which entrance Alice went in, but now calls randomly for her to come out one of the entrances. If Bob yells “B” and Alice emerges from B… well, it could just be luck. However, if Bob repeats this exercise with Alice emerging from A or B a number of times, reliably coming out the entrance Bob calls out, then Bob can be reasonably certain that Alice knows the combination to the lock, without Alice ever having to reveal it.

Probability is the key to understanding zero-knowledge proofs. If we repeat a test like that in the cave story enough times, it becomes statistically close to impossible that you could pass the test every time without actually knowing the information that is being tested. In the real-world, “the cave” is a cryptographic algorithm. Simplifying, and not getting too deep into the (often very high-level) math involved, Alice can demonstrate she knows secret value x, by running a mathematical test repeatedly, using random value r as an input each time, and providing the results y to Bob. In other words, Alice isn’t providing any direct information of use, only information that’s mathematically based off of her secret value. On his side, Bob is able to check, again using math, that Alice’s answers are ones that only someone knowing the secret value x could generate. If we only ran this test once or twice, there would be a small chance that Alice is providing the correct y values simply by guessing them. However, the probability of Alice actually knowing value x increases each time she answers with a correct y. After enough rounds of Alice providing the correct values, Bob can be statistically certain that Alice does indeed know x.

Zero knowledge proofs have existed in concept since the 1980’s, when MIT researchers Shafi Goldwasser, Silvio Micali and Charles Rackoff developed the idea in their paper “The knowledge complexity of interactive proof systems”. Like secure-multiparty computation, the zero-knowledge proof is a privacy idea that has been around for some time, but is only now coming to practical fruition. The main application of zero-knowledge proofs thus far has been in protecting the privacy of blockchain transactions. They’re being used in the cryptocurrency Zcash (for which a new form of “succinct”, faster processing zero-knowledge proof was developed), and by J.P. Morgan as part of their Quorum blockchain system. There are also currently projects in development that use zero-knowledge proofs to develop a “digital identity” that would allow you to verify your identity without providing the usual information (social security number, passport number, etc.). Some current digital identity projects do use other cryptographic protections, but there’s some possibility that the coded information passed can be decoded by an attacker. The application of zero-knowledge proofs, and the useless numbers they pass, would provide even more security.

Zero-knowledge proofs might also prove to be valuable in moving us away from passwords, the vulnerabilities of which have become increasingly clear. While passwords are currently protected cryptographically, you still have to enter them (in clear text) in a browser or app. With zero-knowledge proofs, you could provide authentication without a password (or any other useful information) ever leaving your device. Companies and organizations, such as the FIDO alliance, are currently working on efforts to use zero-knowledge proofs as part of a password-less authentication solution.

A more unexpected use being considered for zero-knowledge proofs is in verification of arms control agreements. Nuclear warhead verification might be possible using properties of radiographic and emission data as the inputs to zero-knowledge proofs, avoiding concerns about revealing classified military information (concerns that have hampered some inspections processes in the past).

Relevant to the current pandemic and increased sharing of health-related data, zero-knowledge proofs could help keep information private. For example, by allowing you to confirm you have valid health insurance without divulging id numbers or other personal information, or to show that your medical data is in a healthy range across a set of metrics while keeping your exact data private.

It’s taken a few decades, but zero-knowledge proofs’ time may have arrived. As they become easier to implement and more efficient computationally, we’re likely to see increasingly interesting and unexpected applications of zero-knowledge proofs across industries and services--opportunities abound for creating an improved balance between technological convenience, personal privacy, and digital security.