Non-interactive random oracle access

[Back] We can use the Fiat-Shamir heuristic with non-interactive random oracle access in order to prove that we know a secret. In this case the non-interactive oracle is a hash function [here]

Method

Alice can prove her identity with a little bit of a calculation, and then anyone who wants to prove her ID can then do a calculation, and if it is correct, she has proven herself. This is known as a "non-interactive random oracle access" for zero-knowledge proofs. In the case we will look at the use of a hash value for the non-interactive random oracle part.

Normally Alice would pass a random value to whoever it is that wants to prove her identity, but in this case she will use the hash value to randomise the puzzle and answer.

The stages are:

1. First everyone agrees on a puzzle and has a secret (x). The puzzle is:

\(y=g^x\)

where we agree on g and x is the secret that Alice proves that she knows. Let's say that g is 13, and x is 11, so \(g^x\) is:

1792160394037

2. Next Alice generates a random number (v) and calculates t, which is:

\(t = g^v\)

Let's say that the value of v is 8. This gives t of:

815730721

3. She now computes a hash value (c) created from g, y and t:

\(c = MD5(g+y+t)\)

Let's say this gives us 12 (we would normally limit the range of the value produced).

4. Now she computes r of \(r= v -c \times t\) to get:

-124

5. Now she sends out t and r to prove her identity:

[815730721, -124]

6. Everyone who knows who wants to prove her ID will then compute (where c can be calculated as a hash of g, y and t):

\(t = g^r \times y^c\)

In this case the calculation gives 815,730,720, which is the same as the value of t that Alice sent, so they have proven her ID.

Every time Alice generates a new random number and proves that she knows the value of t each time.

Example

The following provides an example:

g= 13
x= 11  (the secret)
v= 7  (random)
==============
t= 62748517
y= 1792160394037
c= 13
==============
Alice sends (t,r)=( 62748517 , -136 )
My calc for g^r x y^c= 62748517

Code

An outline of the code used is:

import random

p=59
g=13
x=11
v=9

	
def string2numeric_hash(text):
    import hashlib
    return int(hashlib.md5(text).hexdigest()[:8], 16)

if (len(sys.argv)>1):
	g=int(sys.argv[1])

if (len(sys.argv)>2):
	x=int(sys.argv[2])

v= random.randint(3, 8)

print 'g=',g
print 'x=',x, ' (the secret)'
print 'v=',v, ' (random)'
print '=====Alice computes========='

import hashlib

y= g**x 
t= g**v  

print 't=',t

print 'y=',y

c = string2numeric_hash(str(g)+str(y)+str(t))
c =c % p

print 'c=',c

r= v -c*x

print '=============='

print 'Alice sends (t,r)=(',str(t),',',(r),')'

t1 = (g**r)
t2= (y**c)

val=int(t1*t2)
print 'My calc for g^r x y^c=',val

if (val==t):
	print "Alice has proven her ID"
else:
	print "You are a fraud"

Non-interactive random oracle access

Parameters

Method

Example

Code

Presentation