Welcome to the resource topic for 2025/001
Title:
Attribute Based Encryption for Turing Machines from Lattices
Authors: Shweta Agrawal, Simran Kumari, Shota Yamada
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 \mathbf{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(\mathbf{x})=1. Crucially, the input \mathbf{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 ({\sf 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 \textit{ symmetric} key setting (Agrawal, Maitra and Yamada, Crypto 2019).
In more detail, our results are:
- We construct the first ABE for {\sf NL} from the LWE, evasive LWE (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) and Tensor LWE (Wee, Eurocrypt 2022) assumptions. This yields the first (conjectured) post-quantum ABE for {\sf NL}.
- Relying on LWE, evasive LWE and a new assumption called \textit{circular tensor} LWE, we construct ABE for all Turing machines. At a high level, the circular tensor LWE assumption incorporates circularity into the tensor LWE (Wee, Eurocrypt 2022) assumption.
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.
ePrint: https://eprint.iacr.org/2025/001
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .