[Back] 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]:

## 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=101 g= 3 x = random.randint(5,10) v = random.randint(100,150) c = random.randint(5,10) y= g**x % n t = g**v % n r = v - c * x Result = ( (g**r) * (y**c) ) % 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: