International Association
for Cryptologic Research

We propose the abstractions of Functional Encryption (FE) and Indistinguishability Obfuscation (iO) for {\it pseudorandom} functionalities which are strictly weaker than their general counterparts. Intuitively, a pseudorandom functionality means that the output of the circuit is indistinguishable from uniform for {\it every} input seen by the adversary. We then leverage weak indistinguishability style security of these tools to obtain the following applications: 1. {\it Attribute Based Encryption for Unbounded Depth Circuits.} Assuming $\IND$-secure FE for pseudorandom functionalities and LWE, we construct Attribute Based Encryption (ABE) for circuits of unbounded depth. Previously, such ABE required the circular Evasive LWE assumption (Hseih, Lin and Luo, Focs 2023) which has recently been subject to zeroizing attacks. 2. {\it Attribute Based Encryption for Turing Machines.} Assuming $\IND$-secure FE for pseudorandom functionalities and circular small-secret LWE, we construct Attribute Based Encryption (ABE) for Turing machines. Previously, such ABE required either private coin Evasive LWE (Agrawal, Kumari and Yamada, Crypto 2024) or circular Evasive LWE (Cini and Wee, Eurocrypt 2025), both of which admit attacks in the general case. 3. {\it Multi Input Predicate Encryption for Polynomial Arity.} Assuming $\IND$-secure multi-input FE for pseudorandom functionalities, we construct Multi Input Predicate Encryption (${\sf MIPE}$) for ${\sf P}$ for polynomial arity. Previously, ${\sf MIPE}$ for ${\sf P}$ was known only for {\it constant} arity, using private coin evasive LWE (Agrawal, Rossi, Yadav and Yamada, Crypto 2023). 4. {\it Instantiating the Random Oracle.} We use our $\IND$-secure iO for pseudorandom functionalities to instantiate the random oracle in several applications that previously used iO (Hohenberger, Sahai and Waters, Eurocrypt 2014) such as full-domain hash signature based on trapdoor permutations and more. %, the adaptive security of RSA FDH signatures, the selective security of BLS signatures, and the adaptive security of BLS signatures in the standard model. Our pseudorandom $\iO$ can be used to instantiate these applications, thus reducing their security to strong evasive $\LWE$ and $\LWE$ assumptions. We provide heuristic constructions of FE and MIFE for pseudorandom functionalities from private coin evasive LWE and plain LWE, where private coin evasive LWE is suitably parametrized to avoid all know attacks for the functionalities we consider in this work. This implies iO for pseudorandom functionalities from the same assumptions.

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.

A {\it broadcast, trace and revoke} system generalizes broadcast encryption as well as traitor tracing. In such a scheme, an encryptor can specify a list $L \subseteq N$ of revoked users so that (i) users in $L$ can no longer decrypt ciphertexts, (ii) ciphertext size is independent of $L$, (iii) a pirate decryption box supports tracing of compromised users. The ``holy grail'' of this line of work is a construction which resists unbounded collusions, achieves all parameters (including public and secret key) sizes independent of $|L|$ and $|N|$, and is based on polynomial hardness assumptions. In this work we make the following contributions: 1. {\it Public Trace Setting:} We provide a construction which (i) achieves optimal parameters, (ii) supports embedding identities (from an exponential space) in user secret keys, (iii) relies on polynomial hardness assumptions, namely compact functional encryption (${\sf FE}$) and a key-policy attribute based encryption (${\sf ABE}$) with special efficiency properties, and (iv) enjoys adaptive security with respect to the revocation list. The previous best known construction by Nishimaki, Wichs and Zhandry (Eurocrypt 2016) which achieved optimal parameters and embedded identities, relied on indistinguishability obfuscation, which is considered an inherently subexponential assumption and achieved only selective security with respect to the revocation list. 2. {\it Secret Trace Setting:} We provide the first construction with optimal ciphertext, public and secret key sizes and embedded identities from any assumption outside Obfustopia. In detail, our construction relies on Lockable Obfuscation which can be constructed using ${\sf LWE}$ (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two ${\sf ABE}$ schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy ${\sf ABE}$ for ${\sf P}$ which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called {\it evasive and tensor} ${\sf LWE}$. This assumption, introduced to build an ${\sf ABE}$, is believed to be much weaker than lattice based assumptions underlying ${\sf FE}$ or ${\sf iO}$ -- in particular it is required even for lattice based broadcast, without trace. Moreover, by relying on subexponential security of ${\sf LWE}$, both our constructions can also support a {\it super-polynomial} sized revocation list, so long as it allows efficient representation and membership testing. Ours is the first work to achieve this, to the best of our knowledge.