| Title | : | Attribute Based Encryption for Turing Machines from Lattices |
| Speaker | : | Simran Kumari (IITM) |
| Details | : | Wed, 6 Nov, 2024 11:00 AM @ Turing Hall,SSB 334 |
| 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, 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 NL. 2. Relying on LWE, evasive LWE and a new assumption called 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. This is a joint work with Shweta Agrawal (IIT Madras) and Shota Yamada (AIST Tokyo) and appears in the proceedings of Crypto 2024. |
