Predicting Lattice Reduction

By Nicolas Gama, Phong Q. Nguyen. International Conference on the Theory and Application of Cryptographic Techniques, 2008

494 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/c737fa891210a712c009cb9e922787b1c5276067

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 Information Systems

Citations in the corpus

Lattice Signatures and Bimodal Gaussians (2013, methodology): “In this work (described in detail in the full version of this paper [5]) we undertake a more careful cryptanalysis by using the results on BKZ 2.0 of Chen and Nguyen [3] in combination with other techniques – namely dual lattice reduction and the combinatorial meet-in-the-middle attack of Howgrave-G”
Lattice Signatures Without Trapdoors (2012, methodology): “For security, we use the analysis of [13, 32] (also discussed in the full version of this paper), where it is shown that the smallest vector v such that Av = 0”
Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems (2012, methodology): “According to experiments in [12,8] a factor of 1.”
Somewhat Practical Fully Homomorphic Encryption (2012, background): “Gamma and Nguyen [6] defined the Hermite factor δ of a basis B of an m-dimensional lattice Λ as ||b1|| = δ · det(Λ), with b1 the shortest vector in B.”
BKZ 2.0: Better Lattice Security Estimates (2011, methodology): “Our simulation refines the Gama-Nguyen security estimates [9] on the concrete hardness of lattice problems, which did not take into account pruning, like the security estimates of NTRU [19] [16] and those of [23] [39].”
Lattice Enumeration Using Extreme Pruning (2010, methodology): “We expect extreme pruning to improve the performance of lattice reduction algorithms [32,13], but we leave it to future work to assess its precise impact.”
Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE (2010, background): “Randomizing a basis: Cash et al. [CHKP10] show how to randomize a lattice basis (see also [GN08, Sec.”
Faster Fully Homomorphic Encryption (2010, result): “The experimental results in [7] seem to be consistent with this conjecture.”
From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again (2012, unknown): “, [33] conjecture, from experimental evidence, that 1.”
An Efficient and Parallel Gaussian Sampler for Lattices (2010, background): “Based on current estimates of the concrete security for random cryptographic lattices [ GN08 , MR09], we believe that our new algorithm can offer a significant net gain in efficiency for comparable levels of security, especially when exploiting parallelism.”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, background): “Interestingly, the computational resources needed to do so can increase dramatically with only a moderate decrease in the bound β (see, e.g., [GN08, MR09]).”
Bandwidth Efficient PIR from NTRU (2014, methodology): “The Hermite factor was introduced by Gama and Nguyen [14] to estimate the 7 hardness of the shortest vector problem (SVP) in an n-dimensional lattice L and is defined as γ2n = ||b|| vol(L) 12n where ||b|| is the length of the shortest vector or the length of the vector for which we are searching.”
On the concrete hardness of Learning with Errors (2015, methodology): “The value ó is taken to be a constant,which is experimentally derived in [29] andwhichdependsonboth thenature of the lattices considered, the lattice reduction algorithm used and the target success rate.”
Hardness of SIS and LWE with Small Parameters (2013, background): “, [11, 8]), only find solutions with bounded `2 norm, whereas combinatorial attacks such as [5, 25] (see also [20]) or theoretical lattice attacks [9] that can guarantee an `∞ bound are much more costly in practice, and also require exponential space.”
Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, methodology): “Gama and Nguyen [ 14 ] performed a comprehensive study of the behavior of basis reduction for various families of lattices.”
Multiparty Computation from Somewhat Homomorphic Encryption (2012, methodology): “Following the work of [14] we can estimate, for t N , the size of the output of a lattice reduction algorithm operating on the lattice Λq(A T)∗.”
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds (2016, background): “0[8], D-BKZ [20], or the slide reduction with large blocksize [14, 20]).”