International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Adaptively Secure ABE for DFA from k-Lin and More

Authors:
Junqing Gong , East China Normal University and CNRS, ENS, PSL
Hoeteck Wee , CNRS, ENS, PSL
Download:
DOI: 10.1007/978-3-030-45727-3_10 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
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.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30203,
  title={Adaptively Secure ABE for DFA from k-Lin and More},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={12105},
  doi={10.1007/978-3-030-45727-3_10},
  author={Junqing Gong and Hoeteck Wee},
  year=2020
}