Efficient Public Key Encryption Based on Ideal Lattices

By Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa. International Conference on the Theory and Application of Cryptology and Information Security, 2009

430 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/5623c2b44236e9ee661ff535009ecbc371537bf2

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

In Computer Networks and Communications

Citations in the corpus

Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages (2011, background): “They also construct a very efficient ring counterpart to Regev’s [34] public-key encryption scheme, as well as a counterpart to the identity based encryption scheme of [17] (using the basis sampling techniques of [39]).”
Efficient Lattice (H)IBE in the Standard Model (2010, background): “It would be interesting to improve these constructions by adapting them to ideal lattices [37].”
A Toolkit for Ring-LWE Cryptography (2013, background): “(His work is specialized to the ring R = Z[x]/〈xn − 1〉, but can be extended to other rings, as observed in [34].”
Homomorphic Signatures for Polynomial Functions (2011, methodology): “Ideal lattices also appear in the lattice-based public key encryption schemes of Stehle, Steinfeld, Tanaka, and Xagawa [34] and Lyubashevsky, Peikert, and Regev [25] and in the hash functions of Lyubashevsky and Micciancio [24].”
Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems (2012, methodology): “We consider it somewhat unlikely that the algebraic structure causes any weaknesses since for certain parameters, our signature scheme is as hard as Ring-LWE (which has a quantum reduction from worst-case lattice problems [25]), but we do encourage cryptanalysis for our particular parameters because”
An Efficient and Parallel Gaussian Sampler for Lattices (2010, neutral): “, [16, 21, 14]).”
Bonsai Trees, or How to Delegate a Lattice Basis (2010, positive): “Fortunately, the principles of bonsai trees may be applied equally well using analogous hard problems and tools for cyclic/ideal lattices (developed in, e.g., [Mic07, PR06, LM06, PR07, SSTX09, LPR10]).”
Making NTRU as Secure as Worst-Case Problems over Ideal Lattices (2011, methodology): “[34] introduced a structured variant of LWE, which they proved as hard as Ideal-SIS (under a quantum reduction), and allowed for the design of an asymptotically efficient CPA-secure encryption scheme.”
Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller (2012, background): “See the representative works [32, 37, 28, 30, 44, 31] for more details on these functions and their security foundations.”
TFHE: Fast Fully Homomorphic Encryption Over the Torus (2019, background): “There is instead an asymptotic equivalence between ring [41,51] and module LWE [39] problems for large modulus [5].”
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM (2017, methodology): “Based on the idea from the NTRU cryptosystem [43] of working with elements over polynomial rings rather than over the integers, and following a series of works on this topic [54, 56, 61, 68], Lyubashevsky et al.”
Worst-case to average-case reductions for module lattices (2014, methodology): “A similar adaptation for LWE, called R-LWE, was introduced by Lyubashevsky et al [14] (see also [33]).”
On Ideal Lattices and Learning with Errors over Rings (2010, methodology): “Unlike almost all previous works in the area (e.g., [Mic02, PR06, LM06, LM08, Gen09, Lyu09, SSTX09]), we choose not to use the na¨ıve coefﬁcient embedding, but instead exclusively use the so-called canonical embedding from algebraic number theory (also adopted in the prior work [PR07]), whose…”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, background): “At this point it is not possible to give an accurate comparison of our signature scheme to the hash-and-sign signature schemes [9,37] because no concrete parameters were given for those schemes.”