Rating:
# Learning with Exploitation
[Video](https://www.youtube.com/live/9IUsP3CBwZc?si=yXL4Iytu9eUj8rcs&t=2142)
This problem can be solved by solving r.
Since there are not enough columns in A, we use LLL to find r.
r can be derived by constructing a matrix that can be solved by SVP using the following 2 formulas and finding LLL.
```
r*A - U mod p = 0
r is small
```
```py
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples
from sage.misc.prandom import randrange
from params import *
from Crypto.Util.number import *
p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = int(p // (2 ** 64))
D = DiscreteGaussianDistributionIntegerSampler(q // d // 6) # six sigma
A, T = public_key
A = matrix(GF(p), A)
T = vector(GF(p), T)
# print(A)
for i in range(8):
U, v = ciphertext[i]
mat = []
for i in range(A.ncols()):
ps = [0]*10
ps[i]=p
mat.append(list(A.column(i)) + [-U[i]] + ps)
for i in range(100):
vec = [0]*101 + [0]*10
vec[i] = 2
vec[-11] = -1
mat.append(vec)
mat = matrix(ZZ, mat).transpose()
lll = mat.LLL()
# print(lll[1])
rr = []
for l in lll[1][10:]:
rr.append(1 if l == 1 else 0)
rr = vector(rr)
# print(rr)
print(long_to_bytes(int((v - rr*T)//q)))
rr = []
for l in lll[1][10:]:
rr.append(0 if l == 1 else 1)
rr = vector(rr)
# print(rr)
print(long_to_bytes(int((v - rr*T)//q)))
```
