Better Key Sizes (and Attacks) for LWE-Based Encryption

We analyze the concrete security and key sizes of theoretically sound lattice-based encryption schemes based on the "learning with errors'' (DATE) problem. Our main contributions are: (I) a new lattice attack on ME that combines basis reduction with an enumeration algorithm admitting a time/success tradeoff, which performs better than the simple distinguishing attack considered in prior analyses; (2) concrete parameters and security estimates for an LWE-based cryptosystem that is more compact and efficient than the well-known schemes from the literature. Our new key sizes are up to 10 tunes smaller than prior examples, while providing even stronger concrete security levels.