A Subfield Lattice Attack on Overstretched NTRU Assumptions - Cryptanalysis of Some FHE and Graded Encoding Schemes

By Martin R. Albrecht, Shi Bai, Léo Ducas. 2016

256 citations recorded by the source corpus.

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

HEAX: An Architecture for Computing on Encrypted Data (2019, background): “6 provides a breakdown of FPGA resource consumption for different HE parameter sets.”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “Recently, Albrecht et al. (2011) introduced a Polly Cracker with Noise cryptosystem, where the homomorphic addition operations do not increase the ciphertext size, while the multiplications square it. Another idea of evaluating operations on encrypted data is realized over different sets. Sander, Yo”
A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes (2016, background): “Despite the fact that the security of YASHE has been called into question recently [3], this scheme can also benefit from the present work.”
Post-quantum Key Exchange - A New Hope (2016, methodology): “We note that NTRU is a potentially a weaker problem than Ring-LWE: it is in principle subject to a subfield-lattice attack [2], but the parameters proposed for NTRUENCRYPT are immune.”
HEAX: High-Performance Architecture for Computation on Homomorphically Encrypted Data in the Cloud (2019, background): “These constructions – based on an overstretched NTRU assumption – are subject to a subfield lattice attack [2] and are no longer secure.”
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM (2017, background): “There have been recent attacks exploiting the algebraic structure of cyclotomic ideal lattices [15, 24, 31, 32], and others that exploit the presence of dense sub-lattices in NTRU lattices [2, 47].”
HEPCloud: An FPGA-Based Multicore Processor for FV Somewhat Homomorphic Function Evaluation (2018, background): “Recently in 2016, Albrecht et al. [25] published a subﬁeld lattice attack that runs in sub-exponential time on overstretched NTRU assumptions.”
FPGA-Based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data (2019, unknown): “[35] in 2016.”