With Fiat–Shamir we can prove that we know a value without actually revealing the orginal value. In the following Alice will prove to Bob that she knows x. Alice generates a random number (\(v\)) and Bob generates a random value (\(c\)) [paper][1]:
Fiat–Shamir |
Method
Can I prove to you that I actually know something without ever revealing what it is I know? So how can Alice the Teacher prove to Bob that she knows Peggy's mark for her coursework, without actually giving away the mark? For this we use the Fiat–Shamir heuristic.
Initially Alice marks Peggy's paper defines the grade as x (which she keeps secret). Alice will tell Bob \(g^v \mod P\) (where Alice can't tell the value of \(v\). Alice then creates a random value \(v\) and sends this value to Bob:
\(t= g^v \mod P\)
where \(g\) is the generator, and \(P\) is a prime number. Now Alice creates a random number (\(c\)) and sends this to Bob. Bob then calculates:
\(r = v - cx\)
and send this back to Alice. Alice the checks:
\(t = g^r y^c \mod P\)
If they are equal, Bob has proven that he knows Peggy's mark. This is because:
\(g^r \times y^c = g^{(v-cx)} \times y^c = g^{(v-cx)} \times (g^{x})^{c} = g^{(v-cx)} \times g^{xc} = g^{v}\)
Code
Here is the code:
import sys import random n=2**255-19 g= 3 x = random.randint(1,2**80) v = random.randint(1,2**80) c = random.randint(1,2**80) y= pow(g,x,n) t = pow(g,v,n) r = v - c * x Result = ( pow(g,r,n) * pow(y,c,n) ) % n print ('x=',x) print ('c=',c) print ('v=',v) print ('P=',n) print ('G=',g) print ('======') print ('t=',t) print ('r=',Result) if (t==Result): print ('Alice has proven she knows x') else: print ('Alice has not proven she knows x')
and when we run we should always get the same value for \(t\) and \(Result\).
Outline presentation
The following is an oultine of this and related methods:
References
Fiat, A., & Shamir, A. (1986, August). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the theory and application of cryptographic techniques (pp. 186-194). Springer, Berlin, Heidelberg [paper].