International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lattice Trapdoors and IBE from Middle-Product LWE

Authors:
Alex Lombardi
Vinod Vaikuntanathan
Thuy Duong Vuong
Download:
DOI: 10.1007/978-3-030-36030-6_2
Search ePrint
Search Google
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.
BibTeX
@article{tcc-2019-29966,
  title={Lattice Trapdoors and IBE from Middle-Product LWE},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11891},
  pages={24-54},
  doi={10.1007/978-3-030-36030-6_2},
  author={Alex Lombardi and Vinod Vaikuntanathan and Thuy Duong Vuong},
  year=2019
}