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.