Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Divesh Aggarwal:

TR24-077 | 19th April 2024
Divesh Aggarwal, JinMing Leong, Alexandra Veliche

Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective

Revisions: 4

In this work, we study the worst-case to average-case hardness of the Learning with Errors problem (LWE) under an alternative measure of hardness - the maximum success probability achievable by a probabilistic polynomial-time (PPT) algorithm. Previous works by Regev (STOC 2005), Peikert (STOC 2009), and Brakerski, Peikert, Langlois, Regev, Stehle ... more >>>

ISSN 1433-8092 | Imprint