LWE

と

秘密の

エラー

があって、

判定LWE(Desicional LWE)

とを受け取って、か かを判定する問題

探索LWE(Search LWE)

とを受け取って、を復元する問題

を取る場合もあって、その場合はRing LWEと呼ばれる

判定RLWEをSISを解いて解決する

複数のインスタンスが与えられているときの話

SISの解を求める

もしなら

がなりたつのですなわちは十分に小さくなるはずである

例題と回答

#LLL

#CVP

#babai's_rounding

with open("flag.txt", "rb") as f:
  flag = f.read()

flag = vector(list(flag))
p = 65537

def encrypt(m, noise_size=1):
  n = len(m)
  a = random_vector(GF(p), n)
  e = randint(-noise_size, noise_size)
  return a, a.dot_product(m) + e

A = []
B = []
for _ in range(len(flag) * 2):
  a, b = encrypt(flag)
  A.append(list(a))
  B.append(int(b))

print({"A": A, "B": B})

def babai_closest_vector(M, G, target):
  small = target
  for i in reversed(range(M.nrows())):
    c = ((small * G[i]) / (G[i] * G[i])).round()
    small -=  M[i] * c
  return target - small

with open("output.txt") as f:
  data = eval(f.read())
  A = data["A"]
  B = data["B"]

target = vector(B)
p = 65537

n = len(A[0])
m = len(A)


L = matrix(ZZ, m + n, m)
L.set_block(0, 0, matrix(A).transpose())
L.set_block(n, 0, matrix.identity(m) * p)

B = L.LLL()
G = B.gram_schmidt()[0]
closest = babai_closest_vector(B[-m:, -m:], G, target)

print(closest)

flag = matrix(GF(p), A).solve_right(closest)
print(flag)