# 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
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:
def get_A_s():
r = remote('', 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)

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)

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

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

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}`.