I am currently attending ESC 2013 in Mondorf, Luxembourg. Over dinner someone mentioned that there is no known reduction from LPN to lattice reduction, i.e., it is not known that you can solve LPN with LLL and friends. This seems rather strange to me, because the standard lattice attack on LWE seems to be carrying over as is:

sage: n = 100 # number of variables sage: m = 400 # number of samples sage: A = random_matrix(GF(2), m, n) sage: s = random_vector(GF(2), n) # our secret sage: p = 0.25 # our error rate sage: v = A*s + vector(GF(2),[1 if random() < p else 0 for _ in range(m)]) # we are searching for a short vector in the dual lattice sage: B = A.kernel().matrix() sage: L = B.change_ring(ZZ).LLL() # because a short vector there, means few additions which means a higher bias in the sum sage: Av = A.augment(v) sage: sum(map(lambda x: abs(x) % 2,L[0])), (L[0]*Av)[-1]

Of course, this means running lattice reduction many times, but still: what am I missing?

**PS:** Obligatory, Sage cell here.

Advertisements