Anonymous IBE, leakage resilience and circular security from new assumptions

Zvika Brakerski, Alex Lombardi, Gil Segev, Vinod Vaikuntanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

49 Scopus citations

Abstract

In anonymous identity-based encryption (IBE), ciphertexts not only hide their corresponding messages, but also their target identity. We construct an anonymous IBE scheme based on the Computational Diffie-Hellman (CDH) assumption in general groups (and thus, as a special case, based on the hardness of factoring Blum integers). Our approach extends and refines the recent tree-based approach of Cho et al. (CRYPTO’17) and Döttling and Garg (CRYPTO’17). Whereas the tools underlying their approach do not seem to provide any form of anonymity, we introduce two new building blocks which we utilize for achieving anonymity: blind garbled circuits (which we construct based on any one-way function), and blind batch encryption (which we construct based on CDH). We then further demonstrate the applicability of our newly-developed tools by showing that batch encryption implies a public-key encryption scheme that is both resilient to leakage of a (1o(1)) -fraction of its secret key, and KDM secure (or circular secure) with respect to all linear functions of its secret key (which, in turn, is known to imply KDM security for bounded-size circuits). These yield the first high-rate leakage-resilient encryption scheme and the first KDM-secure encryption scheme based on the CDH or Factoring assumptions. Finally, relying on our techniques we also construct a batch encryption scheme based on the hardness of the Learning Parity with Noise (LPN) problem, albeit with very small noise rate Ω(log2(n)/n). Although this batch encryption scheme is not blind, we show that it still implies standard (i.e., non-anonymous) IBE, leakage resilience and KDM security. IBE and high-rate leakage resilience were not previously known from LPN, even with extremely low noise.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings
EditorsJesper Buus Nielsen, Vincent Rijmen
PublisherSpringer Verlag
Pages535-564
Number of pages30
ISBN (Print)9783319783802
DOIs
StatePublished - 2018
Externally publishedYes
Event37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018 - Tel Aviv, Israel
Duration: Apr 29 2018May 3 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10820 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018
Country/TerritoryIsrael
CityTel Aviv
Period4/29/185/3/18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Anonymous IBE, leakage resilience and circular security from new assumptions'. Together they form a unique fingerprint.

Cite this