Zero-knowledge proof allows a prover to prove a statement is true without disclosing that statement to the verifier.
Traditionally, the nature of proofs is to reveal more information than necessary. For instance, if a person goes to the movie theatre to watch an A-rated movie, they’d be asked to prove they’re of legal age. They might produce a driver’s license, a college ID, or some other form of identification that mentions their age. While the ID proof establishes that the person is of legal age, it also reveals their exact age. The verifier just needed to know if the prover was an adult but ended up knowing the prover’s exact age in the process.
Zero-knowledge protocols are designed in a way that stops the disclosure of excess information during the verification of a statement or identity. Zero-knowledge encryption employs the zero-knowledge protocols to encrypt data. This post will discuss how zero-knowledge encryption works, the math behind it, and its applications across industries.
In this article…
A simple explanation of zero-knowledge proof
We’ve already mentioned that zero-knowledge proof allows a verifier to verify the authenticity of a statement without knowing anything else about it. The question is, how is that possible?
There’s a beloved puzzle series called Where’s Wally (Where’s Waldo in the USA and Canada) that challenges the readers to find a character named Wally on a page full of characters and objects. Wally can be identified by his red and white striped shirt, bobble hat, and glasses. The problem is that once one person finds Wally and points out his position on the page, the game loses meaning to all other participants. But if he doesn’t point out Wally’s position, how would he prove that he’s found him?
This is where one of the simplest applications of zero-knowledge proof is observed. The first player to find Wally cups out Wally’s position with their hand showing it to the other players through the little peephole in the cup. This way everyone can see that the player has found Wally but they cannot see who he is standing next to.
Similarly, zero-knowledge proofs can allow people to
- Prove that they have a good enough credit score to be eligible for a loan without revealing additional financial data.
- Verify the transactions on a blockchain without learning the transaction details.
- Determine if a weapon is nuclear without revealing any more information.
- Encrypt data in cloud storage without revealing the decryption key to the service provider.
How does zero-knowledge encryption work in real-life
Zero-knowledge proof is not absolute proof but a probabilistic way of establishing the truth. It works because of three essential properties.
- Completeness: If the prover possesses the secret, the verifier will definitely be convinced.
- Soundness: If the prover is dishonest in any way, the verifier will not be convinced.
- Zero-knowledge: The verifier will have gained no knowledge during its interaction with the prover.
So, when you try to log into an account protected with zero knowledge encryption, instead of asking for the decryption key, the verifier asks you to perform a task that only the possessor of the key would be able to perform. Numerous iterations of the process decrease the probability of the prover getting lucky, making a guess, or applying dishonest means.
Zero-knowledge protocols are mathematical algorithms that allow the authentication of data while maintaining the essence of zero-knowledge.
The mathematical foundation of zero-knowledge encryption
Imagine a cryptographic scenario where a piece of information is encrypted and the decryption key is possessed only by the prover. Let’s call the key x. The verifier needs to establish that the prover really knows the value of x without learning it himself. We’ll see how that can be done mathematically.
The first characters to appear in this mathematical drama are
Two integers, g & y
A large prime P
And of course, the variable x.
g, P, and y are known to both the verifier and the prover but x is known to the prover alone.
Equation 1:
gxmodP=Y
You could say if the values of g, P, and y are known to the verifier, what’s stopping them from calculating x?
- The nature of the problem. The equation represents a discrete logarithm problem which dictates that the only way to find out x is to try every possible value until you find out the right one.
- The size of the numbers. The largeness of the prime number and the other constants involved in the equation ensures that it takes years for even the smartest computers to calculate x by trying each possible value.
So, how does the verifier verify that the prover knows the value of x?
This part will require one more key character to step in.
A random integer, r
First, the prover will calculate C where
C = grmodP [equation 2]
And send C to the verifier.
Then, the verifier asks for the value of w. Is that another character? No. It’s actually a combination of the existing characters.
w=x+rmod (P-1) [equation 3]
At this point, the verifier knows g, P, y, C, and w where C=grmodP and w=x+rmod (P-1)
If yCmodP = gwmodP [equation 4] holds true then the prover has the right value for x.
If you are interested, here’s how the equation forms:
yCmodP = gxgrmodP [refer to equation 1 and equation 2]
We can write that as gx+r modP [22x23 = 22+3]
That equals gx+rmod(p-1)modP
[According to Fermat’s Theorem, axmodP=axmod(P-1)modP when P is a prime.]
From equation 3, we know that w = x+rmod(P-1)
Therefore, gx+rmod(p-1)modP = gwmodP
So, while the prover never really mentions the value of x and the verifier never really finds out the value of x, it is established that the prover has the correct value for x.
But is this protocol sound? Is there a way for the prover to fake it? Well, this mathematical fortress does have a chink in the armour.
Let’s go back to equation 2, C = grmodP
If instead of selecting a random integer r, the prover takes a calculated integer z where
C = gz/ymodP [equation 5]
The protocol can be fooled. Here’s how:
The proof is accepted if
yCmodP = gwmodP holds true.
Now, based on equation 5
yCmodP = ygz/ymodP
The y on the right-hand side gets cancelled and you end up with
yCmodP = gzmodP
When the verifier asks for w, all the dishonest prover has to do is give z.
Thus, the fake prover will establish authenticity without knowing the key at all.
How does the protocol maintain soundness?
The verifier can ask for the value of r to make sure that the prover is not trying to rig the equation.
But there is a problem. If the verifier knows r and also knows x+r [remember w=x+rmod (P-1)], finding out x is just simple arithmetic. In that case, the “zero-knowledge” property of the protocol is compromised.
This leads us to the next question:
How does the protocol maintain zero-knowledge status?
The verifier has to ask for either r or x+r randomly but never for both in the same iteration. Since the prover does not know what it will be asked to provide, it can only prepare for one query. The random verification queries over many iterations ensure the soundness as well as the zero-knowledge properties.
How is zero-knowledge encryption used in blockchain?
Each block in a blockchain contains some information – in the case of Bitcoin, it is the information about a transaction. Each block contains a hash, the transaction details, and the hash from the previous block (unless it’s the first or the genesis block).
The validity of the blocks is evaluated by multiple verifiers. And before the transaction data is uploaded to a block, it is handled by miners. So, when you conduct a transaction in bitcoins, a bunch of people have access to that data.
Why is this bad? For instance, the miners can use the knowledge of large transactions in cryptocurrency as insider knowledge in terms of trading.
Blockchain provides decentralized control over data, collating that with data privacy is tricky and that is where zero knowledge protocols come in. ZKP enables the verification of transactions without viewing the transaction details.
📖 Curious to know the comparison between ZKE vs other encryption methods? Read our guide here.
How Uniqkey uses zero-knowledge encryption to protect passwords
Uniqkey keeps your passwords in an encrypted vault. The key to decrypt the passwords is stored locally on your device. At the time of logging into an account, you have to request access from the web extension and approve the request from your Uniqkey mobile application. Your master password or decryption key never leaves your device and the server never stores it. The password manager uses zero-knowledge proof to verify your identity and grants you access.
While Uniqkey’s server has never been breached, even if were ever to get hacked, your passwords will be protected, since the decryption key is not stored on the server.
Zero-knowledge encryption is the future of cryptography and it is the only method of encryption that provides security against the theoretical quantum computer. Uniqkey brings the future to you.
