94 lines
1.7 KiB
Python
94 lines
1.7 KiB
Python
|
import random
|
||
|
|
import math
|
||
|
|
|
||
|
|
n = 8
|
||
|
|
k = 3
|
||
|
|
x = "11110101"
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
def findS():
|
||
|
|
for s_candidate in range(k, n+1):
|
||
|
|
binom = math.factorial(s_candidate) / ( math.factorial(k-1) * (math.factorial(s_candidate - (k-1))) )
|
||
|
|
if binom >= n:
|
||
|
|
return s_candidate
|
||
|
|
|
||
|
|
|
||
|
|
s = findS()
|
||
|
|
|
||
|
|
|
||
|
|
def makeOneSeq(seq):
|
||
|
|
ones_remainding_counter = k - 1
|
||
|
|
while ones_remainding_counter != 0:
|
||
|
|
rand_idx = random.randint(0, s - 1)
|
||
|
|
if seq[rand_idx] == "0":
|
||
|
|
seq_temp = list(seq)
|
||
|
|
seq_temp[rand_idx] = "1"
|
||
|
|
seq = "".join(seq_temp)
|
||
|
|
ones_remainding_counter -= 1
|
||
|
|
return seq
|
||
|
|
|
||
|
|
def makeSequences():
|
||
|
|
sequnces = [ "0"*s for j in range(n) ]
|
||
|
|
for i, seq in enumerate(sequnces):
|
||
|
|
candidate = makeOneSeq(seq)
|
||
|
|
while( candidate in sequnces):
|
||
|
|
candidate = makeOneSeq(seq)
|
||
|
|
sequnces[i] = candidate
|
||
|
|
sequnces.sort()
|
||
|
|
return sequnces
|
||
|
|
|
||
|
|
|
||
|
|
sequnces = makeSequences()
|
||
|
|
|
||
|
|
#print(sequnces)
|
||
|
|
|
||
|
|
|
||
|
|
def user_send(rands, i):
|
||
|
|
gs = [[rands[l] * z + int(i[l]) for l in range(0, s)] for z in range(1, k+1)]
|
||
|
|
return gs
|
||
|
|
|
||
|
|
|
||
|
|
def servers_comp(gs):
|
||
|
|
Fs = []
|
||
|
|
for g in gs:
|
||
|
|
F = 0
|
||
|
|
for j in range(0, n):
|
||
|
|
f = 1
|
||
|
|
j_bitstring = sequnces[j]
|
||
|
|
for l in range(s):
|
||
|
|
if int(j_bitstring[l]) == 1:
|
||
|
|
f *= g[l]
|
||
|
|
F += f * int(x[j])
|
||
|
|
Fs.append(F)
|
||
|
|
return Fs
|
||
|
|
|
||
|
|
def poly_interpolation(x, Fs):
|
||
|
|
add_product = 0
|
||
|
|
for i in range(0, k):
|
||
|
|
mult_product = 1
|
||
|
|
for j in range(0, k):
|
||
|
|
if j != i:
|
||
|
|
mult_product *= (x - (j+1))/((i+1) - (j+1))
|
||
|
|
add_product += mult_product * Fs[i]
|
||
|
|
return int(add_product)
|
||
|
|
|
||
|
|
|
||
|
|
def protocol(i):
|
||
|
|
rands = [random.randint(1,20) for r in range(s)]
|
||
|
|
|
||
|
|
gs = user_send(rands, i)
|
||
|
|
Fs = servers_comp(gs)
|
||
|
|
F0 = poly_interpolation(0, Fs)
|
||
|
|
|
||
|
|
# print(F0)
|
||
|
|
|
||
|
|
return F0
|
||
|
|
|
||
|
|
|
||
|
|
for i in range(n):
|
||
|
|
i_bitstring = sequnces[i]
|
||
|
|
F0 = protocol(i_bitstring)
|
||
|
|
assert (F0 == int(x[i]))
|