### Abstract

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent crypto- graphic constructions, most notably fully homomorphic encryption schemes.

Original language | English (US) |
---|---|

Title of host publication | STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing |

Pages | 575-584 |

Number of pages | 10 |

DOIs | |

State | Published - 2013 |

Event | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 |
---|---|

Country | United States |

City | Palo Alto, CA |

Period | 6/1/13 → 6/4/13 |

### Keywords

- Lattices
- Learning with errors

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'Classical hardness of learning with errors'. Together they form a unique fingerprint.

## Cite this

Brakerski, Z., Langlois, A., Peikert, C., Regev, O., & Stehlé, D. (2013). Classical hardness of learning with errors. In

*STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing*(pp. 575-584). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488680