Rating:

# Random ZKP - 250 points - 11 solves
## Lattice-based ZKP (with randomness).

This time we get to play with the actual protocol. We need to find a n-vector s to get the flag. We get a nxn-matrix A and a n-vector b such that A*s+e=b, with e following a normal distribition around 0.

The server gives random n-vectors r or r+s along with A*r+e with e having the same distribution as above. We cannot get both r and r+s (otherwise the challenge would again be trivial).

The way I solved it (there are maybe other ways) is to realize that given r+s and A*r+e, we can compute

A*(r+s)-A*r-e=A*s-e

for many random values of r and e by asking the server K times.

Averaging the results, we get A*s-sum(e_i)/K. By the law of large numbers, sum(e_i)/K converges to 0 as K grows to infinity.

I ran this with K=300, then rounded the average to get c and assumed it was equal to A*s. If it's not the case, you can increase K:
python
def get_A_s():
r = remote('54.159.113.26', 19004)
x = r.recvuntil('Choice: ')
d = DerSequence()
s = unhexlify(x.split(b': ')[1].split(b'\n')[0])
y = d.decode(s)
A_r = np.array(y)

r.sendline('1')
x = r.recvuntil('\n')[:-1]
d = DerSequence()
r_s = unhexlify(x.split(b'r+s: ')[1])
z = d.decode(r_s)
r_s = np.array(z)

r.close()
return np.mod(lwe.mul(A,r_s)-A_r,q)

c_mat = []
for i in range(300):
print(i)
rs = get(1)
c_mat.append(rs)

c_mat = np.array(c_mat)
c = c_mat.mean(0)


Then, I used sage to compute the solution s of the system of equations A*s=c mod q:

sage: q = 2**15
sage: A = matrix(Integers(q),A)
sage: c = matrix(Integers(c),c).transpose()
sage: s = A.solve_right(c)


I then decrypted the flag as in the challenge LatticeZKP to get the flag actf{oops_sorry_for_the_lack_of_randomness}.