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

By Richard Lindner, Chris Peikert. 2011

796 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

In Computational Theory and Mathematics

Citations in the corpus

XPIR : Private Information Retrieval for Everyone (2016, methodology): “Each of the encryption schemes has a predefined list of possible parameters for security varying from 80 to 256 bits (following NIST recommendations for factoring-based cryptography for Paillier and [32] for lattice-based schemes).”
Multiparty Computation from Somewhat Homomorphic Encryption (2012, background): “In [20] the authors take a different approach and simply extrapolate run times for the NTL implementation of BKZ.”
ML Confidential: Machine Learning on Encrypted Data (2012, methodology): “For the exact details of the security evaluation, we refer to [15, 14, 6].”
Encrypted statistical machine learning: new privacy preserving methods (2015, methodology): “…of 2 × 8192 × 224 ÷ (8 × 1024) = 448KB per encrypted value, ignoring keys and overhead. oﬀer These parameters around 158-bits of security (using bounds in Lindner and Peikert (2011)) — informally this means on the order of 2 158 fundamental operations must be performed on average in order to…”
Lattice Signatures Without Trapdoors (2012, methodology): “On the encryption front, lattice-based schemes have been making a lot of progress with recent provably-secure schemes [39, 28, 24, 41] being almost as practical as (and actually looking quite similar to) the deployed NTRU [20] encryption scheme, which in turn has many advantages over number theory-b”
FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second (2015, methodology): “The security estimate methodology follows the analysis of [27].”
Post-quantum Key Exchange - A New Hope (2016, background): “It is claimed that these parameters provide a classical security level of at least 128 bits considering the distinguishing attack [66] with distinguishing advantage less than 2−128 and 281.”
Privacy-Preserving Deep Learning via Additively Homomorphic Encryption (2018, methodology): “We will use the following lemmas [12], [13], [21].”
Somewhat Practical Fully Homomorphic Encryption (2012, methodology): “Section 6 uses the analysis of Lindner and Peikert [14] to derive parameters for a fully homomorphic scheme with a given security level.”
Private genome analysis through homomorphic encryption (2015, methodology): “from the security analysis of [18] based on Lindner and Peikert’s method [32].”
BKZ 2.0: Better Lattice Security Estimates (2011, methodology): “First, these benchmarks were all computed with only usage 1: NTRU [18] “never observed a noticeable improvement from the pruning procedure, so the pruning procedure was not called” and used β ≤ 25, while [39,23] use β ≤ 30.”
Compact Ring-LWE Cryptoprocessor (2014, methodology): “To estimate the security level offered by these two parameter sets we follow the security analysis in [16] and [14] which improves upon [15, 29].”
Simple Encrypted Arithmetic Library - SEAL v2.1 (2016, background): “[29]; ‘kannan’ denotes the attack described in [6].”
Simple Encrypted Arithmetic Library-SEAL (2017, background): “[29]; ‘kannan’ denotes the attack described in [6].”