With Zero-knowledge proof (ZPF) we can prove that we know something with actually revealing our information. Bob and Alice know g and p (a prime number), and Alice wants Bob to prove he knows x. For this he creates a random value (r):
Zero-knowledge proof (ZKP) |
Method
When our banks ask for our second, third and fifth letter of our password, we are actually giving away our password. Slowly we will reveal the whole password. Surely there must be better ways of proving that we know something, without actually revealing what we know?
We could use some fancy encryption keys, but can we do better with a bit of maths? For this we turn to logs, and derive things from the work of John Napier.
There are many applications in proving things without actually revealing the information that you are proving. This could be to prove your identity or even your date of birth. Overall this is defined as Privacy Enhancing Technologies (PET), and where we can reveal information without revealing our answer.
In cryptography, let's say that Alice wants to prove that Bob knows a value (x), such that:
\(g^x \mod P = Y\)
where g is a pre-selected value, P is a prime and Y is a result. Both Bob and Alice know these values, and it's difficult to know the value of x, as there are many values of x that would fit.
To prove that Bob knows the value of x, he creates a random number (r) and sends the result of this calculation to Alice:
\(C = g^r \mod P \)
He then sends:
\(Cipher_1 = g^{(x+r)\mod (P-1)} \mod P \)
Alice then calculates:
\( Cipher_2 = C.Y\mod P \)
If the values are the same (\(Cipher_1\) equals \(Cipher_2\)), Bob has proven that he knows the secret (which is x).
Example
The following provides an example:
p= 6353 (the prime number) g= 5436 x= 54643 (the secret) r= 643215 (the random value) ============== Y=g**x % p= 369 ====Bob sends==== C=g**r % p= 925 Cipher1=g^(x+r)%(p-1) mod p= 4616 ====Alice calculates==== Cipher2=C.Y mod P= 4616 =============== Well done ... have you proven that you know x
Code
An outline of the code used is:
import sys p=71 g=13 x=7 r=8 print ('p=',p) print ('g=',g) print ('x=',x) print ('r=',r) print ('========') y= g**x % p print ('Y=',y) C = g**r % p print ('C=',C) print ('========') val1=g**((x+r)%(p-1)) % p print ('g^(x+r)%(p-1) mod p=',val1) val2=C*y %p print ('C.y mod P=',val2) if (val1==val2): print ('Well done ... have you proven that you know x') else: print ('Not proven')