1from hashlib import sha256
  2
  3def hash_two_points(a, b):
  4    h = sha256((str(a)+str(b)).encode('utf-8'))
  5    return int(h.hexdigest(), 16)
  6
  7def generic_verify(g, X, A, c, z):
  8    return g * int(z) == X * int(c) + A
  9
 10###
 11# Sigma protocol interactive
 12###
 13
 14class Prover_interactive(object):
 15    def __init__(self, F, g):
 16        self.F = F # Z_p
 17        self.g = g # elliptic curve generator
 18
 19    def new_key(self):
 20        self.w = self.F.random_element()
 21        X = self.g * int(self.w)
 22        return X
 23
 24    def new_commitment(self):
 25        self.a = self.F.random_element()
 26        A = self.g * int(self.a)
 27        return A
 28
 29    def gen_proof(self, c):
 30        return int(self.a) + int(c) * int(self.w)
 31
 32class Verifier_interactive(object):
 33    def __init__(self, F, g):
 34        self.F = F
 35        self.g = g
 36
 37    def new_challenge(self, A):
 38        self.A = A
 39        self.c = self.F.random_element()
 40        return self.c
 41    
 42    def verify(self, X, z):
 43        return self.g * int(z) == X * int(self.c) + self.A
 44
 45
 46###
 47# Sigma protocol non-interactive
 48###
 49class Prover(object):
 50    def __init__(self, F, g):
 51        self.F = F # Z_p
 52        self.g = g # elliptic curve generator
 53
 54    def new_key(self):
 55        self.w = self.F.random_element()
 56        X = self.g * int(self.w)
 57        return X
 58
 59    def gen_proof(self, X):
 60        a = self.F.random_element()
 61        A = self.g * int(a)
 62        c = hash_two_points(A, X)
 63        z = int(a) + c * int(self.w)
 64        return A, z
 65
 66
 67class Verifier(object):
 68    def __init__(self, F, g):
 69        self.F = F
 70        self.g = g
 71
 72    def verify(self, X, A, z):
 73        c = hash_two_points(A, X)
 74        return self.g * int(z) == X * c + A
 75
 76class Simulator(object):
 77    def __init__(self, F, g):
 78        self.F = F
 79        self.g = g
 80
 81    def simulate(self, X):
 82        c = self.F.random_element()
 83        z = self.F.random_element()
 84        #  A = g * int(z) + X*(-int(c))
 85        A = g * int(z) - X * int(c)
 86        return A, c, z
 87
 88###
 89# OR proof (with 2 parties)
 90###
 91
 92class ORProver_2parties(object):
 93    def __init__(self, F, g):
 94        self.F = F # Z_p
 95        self.g = g # elliptic curve generator
 96
 97    def new_key(self):
 98        self.w = self.F.random_element()
 99        X = self.g * int(self.w)
100        return X
101
102    def gen_commitments(self, xs):
103        # gen commitment A
104        self.a = self.F.random_element()
105        A = self.g * int(self.a)
106
107        # run the simulator for 1-b
108        sim = Simulator(self.F, self.g)
109        A_1, c_1, z_1 = sim.simulate(xs[1])
110
111        self.A_1 = A_1
112        self.c_1 = c_1
113        self.z_1 = z_1
114
115        return [A, A_1]
116
117    def gen_proof(self, s):
118        # split the challenge s = c xor c_1
119        c = int(s) ^^ int(self.c_1)
120        # compute z
121        z = int(self.a) + int(c) * int(self.w)
122        # note, here the order of the returned elements is always the same, in
123        # a real-world implementation would be shuffled
124        return [c, self.c_1], [z, self.z_1]
125
126class ORVerifier_2parties(object):
127    def __init__(self, F, g):
128        self.F = F
129        self.g = g
130
131    def new_challenge(self, As):
132        self.As = As
133        self.s = self.F.random_element()
134        return self.s
135
136    def verify(self, Xs, cs, zs):
137        assert self.s == int(cs[0]) ^^ int(cs[1])
138        assert self.g * int(zs[0]) == Xs[0] * int(cs[0]) + self.As[0]
139        assert self.g * int(zs[1]) == Xs[1] * int(cs[1]) + self.As[1]
140
141###
142# OR proof (with n parties)
143###
144
145class ORProver(object):
146    def __init__(self, F, g):
147        self.F = F # Z_p
148        self.g = g # elliptic curve generator
149
150    def new_key(self):
151        self.w = self.F.random_element()
152        X = self.g * int(self.w)
153        return X
154
155    def gen_commitments(self, xs):
156        # gen commitment A
157        self.a = self.F.random_element()
158        A = self.g * int(self.a)
159        self.As = [A]
160
161
162        # run the simulator for the rest of Xs
163        sim = Simulator(self.F, self.g)
164        self.cs = []
165        self.zs = []
166        for i in range(1, len(xs)):
167            A_1, c_1, z_1 = sim.simulate(xs[i])
168            self.As.append(A_1)
169            self.cs.append(c_1)
170            self.zs.append(z_1)
171
172        return self.As
173
174    def gen_proof(self, s):
175        # split the challenge s = c xor c_1 xor c_2 xor ... xor c_n
176        c = int(s)
177        for i in range(len(self.cs)):
178            c = c ^^ int(self.cs[i])
179
180        self.cs.insert(0, c) # add c at the beginning of cs array
181
182        # compute z
183        z = int(self.a) + int(c) * int(self.w)
184        self.zs.insert(0, z) # add z at the beginning of zs array
185
186        # note, here the order of the returned elements is always the same, in
187        # a real-world implementation would be shuffled
188        return self.cs, self.zs
189
190class ORVerifier(object):
191    def __init__(self, F, g):
192        self.F = F
193        self.g = g
194
195    def new_challenge(self, As):
196        self.As = As
197        self.s = self.F.random_element()
198        return self.s
199
200    def verify(self, Xs, cs, zs):
201        # check s == c_0 xor c_1 xor c_2 xor ... xor c_n
202        computed_s = int(cs[0])
203        for i in range(1, len(cs)):
204            computed_s = computed_s ^^ int(cs[i])
205
206        assert self.s == computed_s
207
208        # check g*z == X*c + A (in multiplicative notation would g^z ==X^c * A)
209        for i in range(len(Xs)):
210            assert self.g * int(zs[i]) == Xs[i] * int(cs[i]) + self.As[i]