CryptoDB
Pseudorandom FE and iO with Applications
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | 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. |
BibTeX
@inproceedings{tcc-2025-36237,
title={Pseudorandom FE and iO with Applications},
publisher={Springer-Verlag},
author={Simran Kumari and Shweta Agrawal and Shota Yamada},
year=2025
}