Functional Encryption for Turing Machines with Dynamic Bounded Collusion from LWE

The classic work of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2012) and follow-ups provided constructions of bounded collusion Functional Encryption (FE) for circuits from mild assumptions. In this work, we improve the state of affairs for bounded collusion FE in several ways:

1. $New$ $Security$ $Notion$. We introduce the notion of $dynamic$ bounded collusion FE, where the declaration of collusion bound is delayed to the time of encryption. This enables the encryptor to dynamically choose the collusion bound for different ciphertexts depending on their individual level of sensitivity. Hence, the ciphertext size grows linearly with its own collusion bound and the public key size is independent of collusion bound. In contrast, all prior constructions have public key and ciphertext size that grow at least linearly with a fixed bound $Q$.

2. $CPFE$ $for$ $circuits$ $with$ $Dynamic$ $Bounded$ $Collusion$. We provide the first CPFE schemes for circuits enjoying dynamic bounded collusion security. By assuming identity based encryption (IBE), we construct CPFE for circuits of $unbounded$ size satisfying $non-adaptive$ simulation based security. By strengthening the underlying assumption to IBE with receiver selective opening security, we obtain CPFE for circuits of $bounded$ size, output length and depth enjoying $adaptive$ simulation based security. Moreover, we show that IBE is a necessary assumption for these primitives.

Moreover, by relying on the Learning With Errors (LWE) assumption, we obtain the first $succinct$ CPFE for circuits, i.e. supporting circuits with unbounded size, but fixed output length and depth. This scheme achieves $adaptive$ simulation based security.

3. $KPFE$ $for$ $circuits$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE for circuits of unbounded size, but bounded depth and output length satisfying dynamic bounded collusion security. Our construction relies on LWE and achieves $adaptive$ simulation based security. This improves the security of succinct KPFE by Goldwasser et al. [GKPVZ13b].

4. $KP$ $and$ $CP$ $FE$ $for$ $TM/NL$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE and CPFE constructions of bounded collusion functional encryption for Turing machines in the public key setting from LWE. Our constructions achieve non-adaptive simulation based security. Both the input and the machine in our construction can be of $unbounded$ polynomial length but the ciphertext size grows with the upper bound on the running time of the Turing machine on the given input. Given RAM access to the ciphertext, the scheme enjoys input specific decryption time.

We provide a variant of the above scheme that satisfies $adaptive$ security, but at the cost of supporting a smaller class of computation, namely Nondeterministic Logarithmic-space (NL). Since NL contains Nondeterministic Finite Automata (NFA), this result subsumes $all$ prior work of bounded collusion FE for uniform models from standard assumptions [AMY19,AS17].