Cryptology ePrint Archive: Report 2019/224

Compact Adaptively Secure ABE for NC1 from k-Lin

Lucas Kowalczyk and Hoeteck Wee

Abstract: We present compact attribute-based encryption (ABE) schemes for NC1 that are adaptively secure under the k-Lin assumption with polynomial security loss. Our KP-ABE scheme achieves ciphertext size that is linear in the atttribute length and independent of the policy size even in the many-use setting, and we achieve an analogous efficiency guarantee for CP-ABE. This resolves the central open problem posed by Lewko and Waters (CRYPTO 2011). Previous adaptively secure constructions either impose an attribute ``one-use restriction'' (or the ciphertext size grows with the policy size), or require q-type assumptions.

Category / Keywords: public-key cryptography / attribute-based encryption, adaptive security, bilinear maps

Original Publication (with major differences): IACR-EUROCRYPT-2019

Date: received 25 Feb 2019, last revised 27 Feb 2019

Contact author: luke at cs columbia edu

Available format(s): PDF | BibTeX Citation

Version: 20190227:191749 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]