On lattices, learning with errors, random linear codes, and cryptography

FREE-DOWNLOAD O Regev – Journal of the ACM (JACM),
Abstract. Our main result is a reduction from worst-case lattice problems such as GAPSVP and
SIVP to a certain learning problem. This learning problem is a natural extension of the “learning
from parity with error” problem to higher moduli. It can also be viewed as the problem of