Alex Lombardi: Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions

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

In this talk, we will define and explore the new building block “(blind) batch encryption”, including a proof 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. We will then discuss how to obtain (anonymous) IBE from (blind) batch encryption and the implications for IBE constructions and beyond.

When combined with constructions of our base primitives from concrete assumptions, we obtain the following new results:

1) Anonymous IBE from the CDH assumption
2) IBE from the Learning Parity with Noise (LPN) assumption, albeit with very small noise rate
3) Highly leakage resilient and KDM secure public key encryption from CDH and (low noise) LPN

Joint work with Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan.