Cryptology ePrint Archive: Report 2020/194

Adaptively Secure ABE for DFA from k-Lin and More

Junqing Gong and Hoeteck Wee

Abstract: In this work, we present:

- the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO'12];

- the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security;

- the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT'19].

Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO'19 and EUROCRYPT'19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.

Category / Keywords: public-key cryptography /

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

Date: received 16 Feb 2020

Contact author: gongjunqing at gmail com,wee@di ens fr

Available format(s): PDF | BibTeX Citation

Version: 20200218:090928 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]