# 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:```pythondef 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**15sage: 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}`.