On the concrete hardness of Learning with Errors

By Martin R. Albrecht, Rachel Player, Sam Scott. 2015

1,055 citations recorded by the source corpus.

Abstract The learning with errors (LWE) problem has become a central building block of modern cryptographic constructions. This work collects and presents hardness results for concrete instances of LWE. In particular, we discuss algorithms proposed in the literature and give the expected resources required to run them. We consider both generic instances of LWE as well as small secret variants. Since for several methods of solving LWE we require a lattice reduction step, we also review lattice reduction algorithms and use a refined model for estimating their running times. We also give concrete estimates for various families of LWE instances, provide a Sage module for computing these estimates and highlight gaps in the knowledge about algorithms for solving the LWE problem.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, background): “[2] to obtain concrete parameters that provide sufficiently high security based on the best current LWE attack algorithms.”
PIR with Compressed Queries and Amortized Query Processing (2018, background): “Based on recommended security parameters [10, 27], N is typically 2048 or 4096 (larger N improves security but reduces performance).”
Gazelle: A Low Latency Framework for Secure Neural Network Inference (2018, methodology): “Based on the analysis of [1], we set m = 4096 and σ = 4 to obtain our desired security level.”
Efficient Multi-Key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference (2019, methodology): “They are default parameter sets in Microsoft SEAL which provide at least 128-bit of security level according to LWE-estimator [3] and HE security standard [2].”
Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem (2015, methodology): “[34] provide a variety of Sage scripts for calculating the runtime of several different algorithms for (classically) solving LWE.”
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds (2016, methodology): “Our analysis is based on the work described in [2].”
Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme (2019, methodology): “To choose the ring dimension n, we ran the Learning With Errors security estimator(5) (commit f59326c) [33] to find the TABLE 7.”
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE (2016, methodology): “series assumption and the Gaussian heuristic [20, 5]), one concludes that the primal attack is successful if and only if”
Bootstrapping for Approximate Homomorphic Encryption (2018, background): “[1] to guarantee the concrete security of the proposed parameters.”
Post-quantum Key Exchange - A New Hope (2016, background): “There are many algorithms to consider in general (see the survey [3]), yet many of those are irrelevant for our parameter set.”
Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography (2020, methodology): “In order to estimate security, we followed [APS15, ACD + 18] by estimating the time-complexity of the BKZ algorithm [SE94] using sieving as its SVP oracle 17 .”
Simple Encrypted Arithmetic Library-SEAL (2017, methodology): “To label the other attacks we follow the notation of [7]: ‘bkw’ denotes a variant [23] of the BKW attack [10, 5], ‘sis’ denotes a distinguishing attack as described in [32]; ‘dec’ denotes a decoding attack as described in e.”
Private Join and Compute from PIR with Default (2020, methodology): “In order to execute the query results summed and masked, we have C instead use a modiﬁed version of PIR, which we call Sum-PIR .”