Summer 2015

An Improved BKW Algorithm for LWE

Wednesday, Jul. 8, 2015 4:00 pm4:25 pm

Add to Calendar


Calvin Lab Auditorium

We show how the Blum-Kalai-Wasserman algorithm for Learning With Errors can be modified to require sub-exponential time when the secret is small. This gives the first subexponential algorithm for several other problems, such as subset-sum, NTRU and new lattice problems.