CryptoDB
Attribute Based Encryption for Turing Machines from Lattices
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2024 |
| Abstract: | We provide the first attribute based encryption (ABE) scheme for Turing machines supporting unbounded collusions from lattice assumptions. In more detail, the encryptor encodes an attribute x together with a bound t on the machine running time and a message m into the ciphertext, the key generator embeds a Turing machine M into the secret key and decryption returns m if and only if M (x) = 1. Crucially, the input x and machine M can be of unbounded size, the time bound t can be chosen dynamically for each input and decryption runs in input specific time. Previously the best known ABE for uniform computation supported only non-deterministic log space Turing machines (NL from pairings (Lin and Luo, Eurocrypt 2020). In the post-quantum regime, the state of the art supports non-deterministic finite automata from LWE in the symmetric key setting (Agrawal, Maitra and Yamada, Crypto 2019). In more detail, our results are: 1. We construct the first ABE for NL from the LWE and evasive LWE assumptions. This yields the first (conjectured) post-quantum ABE for NL. 2. Relying on new and arguably natural assumptions which we call path LWE, evasive path LWE and circular tensor LWE, in addition to standard LWE, we construct ABE for all Turing machines. Towards our ABE for Turing machines, we obtain the first CP-ABE for circuits of unbounded depth and size from the same assumptions – this may be of independent interest. At a high level, our path LWE assumption states that the joint distribution of specially constructed FHE and ABE encodings are pseudorandom. The evasive path LWE assumption incorporates path LWE into the celebrated evasive LWE assumption (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022), while the circular tensor LWE assumption incorporates circularity into the tensor LWE (Wee, Eurocrypt 2022) assumption. We believe these assumptions provide an important new tool for encrypted computation and are likely to find other applications. |
BibTeX
@inproceedings{crypto-2024-34330,
title={Attribute Based Encryption for Turing Machines from Lattices},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68382-4_11},
author={Shweta Agrawal and Simran Kumari and Shota Yamada},
year=2024
}