Paper 2019/1067
Lattice Trapdoors and IBE from Middle-Product LWE
Alex Lombardi, Vinod Vaikuntanathan, and Thuy Duong Vuong
Abstract
Middle-product learning with errors (MP-LWE) was recently introduced by Rosca, Sakzad, Steinfeld and Stehlé (CRYPTO 2017) as a way to combine the efficiency of Ring-LWE with the more robust security guarantees of plain LWE. While Ring-LWE is at the heart of efficient lattice-based cryptosystems, it involves the choice of an underlying ring which is essentially arbitrary. In other words, the effect of this choice on the security of Ring-LWE is poorly understood. On the other hand, Rosca et al. showed that a new LWE variant, called MP-LWE, is as secure as Polynomial-LWE (another variant of Ring-LWE) over any of a broad class of number fields. They also demonstrated the usefulness of MP-LWE by constructing an MP-LWE based public-key encryption scheme whose efficiency is comparable to Ring-LWE based public-key encryption. In this work, we take this line of research further by showing how to construct Identity-Based Encryption (IBE) schemes that are secure under a variant of the MP-LWE assumption. Our IBE schemes match the efficiency of Ring-LWE based IBE, including a scheme in the random oracle model with keys and ciphertexts of size $\tilde{O}(n)$ (for $n$-bit identities). We construct our IBE scheme following the lattice trapdoors paradigm of [Gentry, Peikert, and Vaikuntanathan, STOC'08]; our main technical contributions are introducing a new leftover hash lemma and instantiating a new variant of lattice trapdoors compatible with MP-LWE. This work demonstrates that the efficiency/security tradeoff gains of MP-LWE can be extended beyond public-key encryption to more complex lattice-based primitives.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in TCC 2019
- Contact author(s)
- tdvuong @ stanford edu
- History
- 2019-09-23: received
- Short URL
- https://ia.cr/2019/1067
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1067, author = {Alex Lombardi and Vinod Vaikuntanathan and Thuy Duong Vuong}, title = {Lattice Trapdoors and {IBE} from Middle-Product {LWE}}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/1067}, year = {2019}, url = {https://eprint.iacr.org/2019/1067} }