Cryptology ePrint Archive: Report 2020/1179

Optimal Broadcast Encryption from LWE and Pairings in the Standard Model

Shweta Agrawal and Daniel Wichs and Shota Yamada

Abstract: Broadcast Encryption with optimal parameters was a long-standing problem, whose first solution was provided in an elegant work by Boneh, Waters and Zhandry [BWZ14]. However, this work relied on multilinear maps of logarithmic degree, which is not considered a standard assumption. Recently, Agrawal and Yamada [AY20] improved this state of affairs by providing the first construction of optimal broadcast encryption from Bilinear Maps and Learning With Errors (LWE). However, their proof of security was in the generic bilinear group model. In this work, we improve upon their result by providing a new construction and proof in the standard model. In more detail, we rely on the Learning With Errors (LWE) assumption and the Knowledge of OrthogonALity Assumption (KOALA) [BW19] on bilinear groups.

Our construction combines three building blocks: a (computational) nearly linear secret sharing scheme with compact shares which we construct from LWE, an inner-product functional encryption scheme with special properties which is constructed from the bilinear Matrix Decision Diffie Hellman (MDDH) assumption, and a certain form of hyperplane obfuscation, which is constructed using the KOALA assumption. While similar to that of Agrawal and Yamada, our construction provides a new understanding of how to decompose the construction into simpler, modular building blocks with concrete and easy-to-understand security requirements for each one. We believe this sheds new light on the requirements for optimal broadcast encryption, which may lead to new constructions in the future.

Category / Keywords: public-key cryptography / Broadcast Encryption, learning with errors, bilinear maps, optimal parameter size, standard model

Original Publication (with minor differences): IACR-TCC-2020

Date: received 26 Sep 2020, last revised 26 Sep 2020

Contact author: shota yamada enc at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200930:073916 (All versions of this report)

Short URL: ia.cr/2020/1179