Cryptology ePrint Archive: Report 2019/1067

Lattice Trapdoors and IBE from Middle-Product LWE

Alex Lombardi and 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.

Category / Keywords: public-key cryptography / Middle-Product LWE and Identity-Based Encryption and Lattice Trapdoors.

Original Publication (in the same form): IACR-TCC-2019

Date: received 19 Sep 2019, last revised 19 Sep 2019

Contact author: tdvuong at stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20190923:071322 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]