Adaptively Secure ABE for DFA from k-Lin and More

Junqing Gong; Hoeteck Wee

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2020
Contact author(s): gongjunqing @ gmail com
wee @ di ens fr
History: 2020-02-18: received
Short URL: https://ia.cr/2020/194
License: CC BY

BibTeX

@misc{cryptoeprint:2020/194,
      author = {Junqing Gong and Hoeteck Wee},
      title = {Adaptively Secure {ABE} for {DFA} from k-Lin and More},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/194},
      year = {2020},
      url = {https://eprint.iacr.org/2020/194}
}