More Web Proxy on the site http://driver.im/

Article

Lattice Trapdoors and IBE from Middle-Product LWE

Authors:

Vinod Vaikuntanathan,

Thuy Duong VuongAuthors Info & Claims

Theory of Cryptography: 17th International Conference, TCC 2019, Nuremberg, Germany, December 1–5, 2019, Proceedings, Part I

Pages 24 - 54

https://doi.org/10.1007/978-3-030-36030-6_2

Published: 01 December 2019 Publication History

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 (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.

References

[1]

Abdalla M et al. Shoup V et al. Searchable encryption revisited: consistency properties, relation to anonymous IBE, and extensions Advances in Cryptology – CRYPTO 2005 2005 Heidelberg Springer 205-222

[2]

Agrawal S, Boneh D, and Boyen X Gilbert H Efficient lattice (H)IBE in the standard model Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 553-572

[3]

Agrawal, S., Boyen, X.: Identity-based encryption from lattices in the standard model (2009)

[4]

Bai S, Langlois A, Lepoint T, Stehlé D, and Steinfeld R Iwata T and Cheon JH Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance Advances in Cryptology – ASIACRYPT 2015 2015 Heidelberg Springer 3-24

[5]

Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 394–403. IEEE (1997)

[6]

Boneh D and Franklin M Kilian J Identity-based encryption from the weil pairing Advances in Cryptology — CRYPTO 2001 2001 Heidelberg Springer 213-229 http://dl.acm.org/citation.cfm?id=646766.704155

[7]

Cash D, Hofheinz D, Kiltz E, and Peikert C Gilbert H Bonsai trees, or how to delegate a lattice basis Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 523-552

[8]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM (2008)

[9]

Hanrot G, Quercia M, and Zimmermann P The middle product algorithm I Appl. Algebra Eng. Commun. Comput. 2004 14 6 415-438

[10]

Impagliazzo, R., Zuckerman, D.: How to recycle random bits. In: 30th Annual Symposium on Foundations of Computer Science, pp. 248–253. IEEE (1989)

[11]

Lyubashevsky V Cheon JH and Takagi T Digital signatures based on the hardness of ideal lattice problems in all rings Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 196-214

[12]

Lyubashevsky V and Micciancio D Bugliesi M, Preneel B, Sassone V, and Wegener I Generalized compact knapsacks are collision resistant Automata, Languages and Programming 2006 Heidelberg Springer 144-155

[13]

Lyubashevsky V, Peikert C, and Regev O Gilbert H On ideal lattices and learning with errors over rings Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 1-23

[14]

Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS 2002, pp. 356–365. IEEE Computer Society, Washington, DC, USA (2002). http://dl.acm.org/citation.cfm?id=645413.652130

[15]

Micciancio D and Peikert C Pointcheval D and Johansson T Trapdoors for lattices: simpler, tighter, faster, smaller Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 700-718

[16]

Micciancio D and Regev O Worst-case to average-case reductions based on Gaussian measures SIAM J. Comput. 2007 37 1 267-302

[17]

Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 461–473. ACM (2017)

[18]

Peikert C and Rosen A Halevi S and Rabin T Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices Theory of Cryptography 2006 Heidelberg Springer 145-166

[19]

Peikert C, Vaikuntanathan V, and Waters B Wagner D A framework for efficient and composable oblivious transfer Advances in Cryptology – CRYPTO 2008 2008 Heidelberg Springer 554-571

[20]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 84–93. ACM (2005)

[21]

Roşca M, Sakzad A, Stehlé D, and Steinfeld R Katz J and Shacham H Middle-product learning with errors Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 283-297

[22]

Shoup, V.: Efficient computation of minimal polynomials in algebraic extensions of finite fields. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, Vancouver, BC (1999). Citeseer

[23]

Stehlé D, Steinfeld R, Tanaka K, and Xagawa K Matsui M Efficient public key encryption based on ideal lattices Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 617-635

Cited By

Ling CMendelsohn A(2023)Middle-Products of Skew Polynomials and Learning with ErrorsCryptography and Coding10.1007/978-3-031-47818-5_11(199-219)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-47818-5_11
Fan JLu XAu M(2023)Adaptively Secure Identity-Based Encryption from Middle-Product Learning with ErrorsInformation Security and Privacy10.1007/978-3-031-35486-1_15(320-340)Online publication date: 5-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-35486-1_15
Bai SDas DHiromasa RRosca MSakzad AStehlé DSteinfeld RZhang Z(2020)MPSign: A Signature from Small-Secret Middle-Product Learning with ErrorsPublic-Key Cryptography – PKC 202010.1007/978-3-030-45388-6_3(66-93)Online publication date: 4-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45388-6_3

Index Terms

Lattice Trapdoors and IBE from Middle-Product LWE
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
2. Theory of computation
  1. Computational complexity and cryptography

Index terms have been assigned to the content through auto-classification.

Recommendations

MDMR-IBE: efficient multiple domain multi-receiver identity-based encryption

In The International Conference on Practice and Theory in Public-Key Cryptography PKC'05, Baek et al. proposed the first multi-receiver identity-based encryption scheme. Their scheme is highly efficient in that it only needs one pairing computation to ...
Adaptively Secure Identity-Based Encryption from Middle-Product Learning with Errors
Information Security and Privacy
Abstract
Introduced in 2017, Middle-Product Learning with Errors (MPLWE) and its variants offer a way to construct cryptographic primitives which preserve the efficiency of those based on Polynomial-LWE (PLWE) while being at least as secure as them over a ...
A strong provably secure IBE scheme without bilinear map

Identity-based encryption (IBE) allows one party to send ciphered messages to another using an arbitrary identity string as an encryption key. Since IBE does not require prior generation and distribution of keys, it greatly simplifies key management in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Theory of Cryptography: 17th International Conference, TCC 2019, Nuremberg, Germany, December 1–5, 2019, Proceedings, Part I

Dec 2019

595 pages

ISBN:978-3-030-36029-0

DOI:10.1007/978-3-030-36030-6

Editors:
Dennis Hofheinz
Karlsruhe Institute of Technology, Karlsruhe, Germany
,
Alon Rosen
IDC Herzliya, Herzliya, Israel

© International Association for Cryptologic Research 2019.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ling CMendelsohn A(2023)Middle-Products of Skew Polynomials and Learning with ErrorsCryptography and Coding10.1007/978-3-031-47818-5_11(199-219)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-47818-5_11
Fan JLu XAu M(2023)Adaptively Secure Identity-Based Encryption from Middle-Product Learning with ErrorsInformation Security and Privacy10.1007/978-3-031-35486-1_15(320-340)Online publication date: 5-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-35486-1_15
Bai SDas DHiromasa RRosca MSakzad AStehlé DSteinfeld RZhang Z(2020)MPSign: A Signature from Small-Secret Middle-Product Learning with ErrorsPublic-Key Cryptography – PKC 202010.1007/978-3-030-45388-6_3(66-93)Online publication date: 4-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45388-6_3

View Options

View options

Media

Figures

Other

Tables

View Table of Contents