CryptoDB
Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and towards NL
| Authors: |
- Huijia Lin , University of Washington, Seattle
- Ji Luo , University of Washington, Seattle
|
| Download: |
- DOI: 10.1007/978-3-030-45727-3_9
(login may be required)
- Search ePrint
- Search Google
|
| Presentation: |
Slides
|
|
Conference:
|
EUROCRYPT 2020
|
| Abstract: |
We present a new general framework for constructing compact and
adaptively secure attribute-based encryption (ABE) schemes from
k-Lin in asymmetric bilinear pairing groups. Previously, the only
construction [Kowalczyk and Wee, Eurocrypt '19] that simultaneously
achieves compactness and adaptive security from static assumptions supports
policies represented by Boolean formulae. Our framework enables
supporting more expressive policies represented by arithmetic
branching programs.
Our framework extends to ABE for policies represented by uniform models
of computation such as Turing machines. Such policies enjoy the feature
of being applicable to attributes of arbitrary lengths. We obtain the first
compact adaptively secure ABE for deterministic and non-deterministic finite
automata (DFA and NFA) from k-Lin, previously unknown from any static
assumptions. Beyond finite automata, we obtain the first ABE for large
classes of uniform computation, captured by deterministic and
non-deterministic logspace Turing machines (the complexity classes
L and NL) based on k-Lin. Our ABE scheme has compact
secret keys of size linear in the description size of the Turing machine M.
The ciphertext size grows linearly in the input length, but also linearly in
the time complexity, and exponentially in the space complexity.
Irrespective of compactness, we stress that our scheme is the first
that supports large classes of Turing machines based solely on standard
assumptions. In comparison, previous ABE for general Turing machines all
rely on strong primitives related to indistinguishability obfuscation. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30237,
title={Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and towards NL},
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},
keywords={ABE;adaptive security;compactness;k-Lin;logspace Turing machine;arithmetic branching program;IPFE},
volume={12105},
doi={10.1007/978-3-030-45727-3_9},
author={Huijia Lin and Ji Luo},
year=2020
}
