Paper 2017/967

Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions

Zvika Brakerski, Alex Lombardi, Gil Segev, and Vinod Vaikuntanathan


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 $(1-o(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 $\Omega(\log^2(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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
identity-based encryptionanonymityleakage resiliencecircular security
Contact author(s)
alexjl @ mit edu
2017-10-03: received
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Alex Lombardi and Gil Segev and Vinod Vaikuntanathan},
      title = {Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/967},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.