Non-Interactive Zero Knowledge Proof (NI-ZKP) allows us to prove knowledge of a value, without giving away the value. This example uses Fiat-Shamir transformation and where Alice has a secret value of \(x\). Alice can then show a public value of \(g^x \pmod p\). Bob can then prove that Alice knows the value of \(x\) with NI-ZKP. In this case, Alice will generate a random value (\(v\) and then send Bob the values of \(g^v \pmod p\), r and c, and where Bob can then tell that Alice knows the value of \(x\).
NI-ZKP (Zero Knowledge Proof) - using discrete logs |
Theory
We use a Fiat Shamir method to prove that Alice knows \(x\). As we are using a non-interative method, Alice will create her own challenge with:
\(c=Hash((G) || (x) || (g^x \pmod p))\)
and where Alice has provided:
\(X=g^x \pmod p\)
Alice then creates a random value (\(v\)) and computes:
\(V = g^v \pmod p\)
and:
\(r=(v-c x_1) \pmod {p-1}\)
She sends the value of \(V\), \(r\) and \(c\) to Bob, and who computes:
\(\textrm{check} = (g^r \pmod p \times X^c \pmod p) \pmod p\)
If \(V\) is equal to check, Alice has proven that she knows \(x\).
Coding
The following is the code:
import sys import random import hashlib from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes primebits=64 # secret="Hello" # s=int(hashlib.md5(secret.encode()).hexdigest(),16) if (len(sys.argv)>1): primebits=int(sys.argv[1]) p = getPrime(primebits, randfunc=get_random_bytes) g=3 x = random.randint(0, p-1) if (len(sys.argv)>2): x=int(sys.argv[2]) X = pow(g,x,p) print ("\n\nNow let's prove that Alice knows x with Fiat Shamir") chal=str(g)+str(x)+str(X) h=hashlib.md5() h.update(chal.encode()) v= random.randint(0, p-1) V=pow(g,v,p) c=int(h.hexdigest(),16) r=(v-c*x) % (p-1) check=(pow(g,r,p)*pow(X,c,p)) %p print (f"Value to prove is {x}") print (f"\nX= {g^x}") print (f"\nv= {v}, V={V}") print (f"\nr= {r}, c={c}") print (f"\nCheck= {check}") if (V==check): print("It has been proven") else: print("Not proven")
And a sample run:
Now let's prove that Alice knows x with Fiat Shamir Value to prove is 999 X= 996 v= 5114137091327423200228495331506871897156427623034101582736550480599875396241011478576302247186171949514365258576177556035763900120536346877180062756129509, V=1639941442228361211060759493221100357193173698679947334074556659709437163418315152890332657169398268989499662928968982248605495746299050921153479912027009 r= 5114137091327423200228495331506871897156427623034101582736550480599875396241011478576302247186171949514365258575995537521283443314700164826707497665779514, c=182200715195652458294476526999564655005 Check= 1639941442228361211060759493221100357193173698679947334074556659709437163418315152890332657169398268989499662928968982248605495746299050921153479912027009 It has been proven