Paper 2020/318

Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and towards NL

Huijia Lin and Ji Luo

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 $\mathsf{L}$ and $\mathsf{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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Contact author(s)
rachel @ cs washington edu
luoji @ cs washington edu
History
2020-03-15: received
Short URL
https://ia.cr/2020/318
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/318,
      author = {Huijia Lin and Ji Luo},
      title = {Compact Adaptively Secure {ABE} from k-Lin: Beyond {NC1} and towards {NL}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/318},
      year = {2020},
      url = {https://eprint.iacr.org/2020/318}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.