Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and Towards NL
Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and Towards NL
复制标题
DOI：
10.1007/978-3-030-45727-3_9
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Huijia Lin;Ji Luo
中科院分区：
文献类型：
--
作者：
Huijia Lin;Ji Luo
提出了在非对称双线性对群中利用k-LIN构造紧致且自适应安全的基于属性的加密(ABE)方案的一个新的通用框架。以前，唯一从静态假设中同时实现紧凑性和自适应安全性的结构[Cotalczyk and Wee，Eurocrypt]支持由布尔公式表示的策略。该框架支持由算术分支程序表示的更具表现力的策略，并扩展到ABE以图灵机等统一计算模型表示的策略。这样的策略具有适用于任意长度的属性的特点。对于确定性和非确定性有限自动机(DFA和NFA)，我们从k-Lin得到了第一个紧致的自适应安全ABE。在有限自动机的基础上，我们得到了基于Onk-Lin的确定和非确定逻辑空间图灵机(复杂性类和)所捕获的大类一致计算的第一个ABE。我们的ABE方案具有紧凑的密钥，其大小与图灵机的描述大小M成线性关系。密文大小在输入长度中线性增长，在时间复杂度中线性增长，在空间复杂度中线性增长。不管紧凑性如何，我们强调，我们的方案是第一个仅基于标准假设支持大类图灵机的方案。相比之下，以前用于通用图灵机的ABE都依赖于与不可分辨混淆相关的强原语。
We present a new general framework for constructingcompactandadaptively secureattribute-based encryption (ABE) schemes fromk-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 byBoolean formulae. Our framework enables supporting more expressive policies represented byarithmetic 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) fromk-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-deterministiclogspaceTuring machines (the complexity classesand) based onk-Lin. Our ABE scheme has compact secret keys of size linear in the description size of the Turing machineM. 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.