Paper 2024/1742

Pseudorandom Obfuscation and Applications

Abstract

We introduce the notion of pseudorandom obfuscation (PRO), a way to obfuscate (keyed) pseudorandom functions $f_K$ in an average-case sense. We introduce several variants of pseudorandom obfuscation and show constructions and applications. For some of our applications that can be achieved using full-fledged indistinguishability obfuscation (iO), we show constructions using lattice-based assumptions alone; the other applications we enable using PRO are simply not known even assuming iO. We briefly summarize our contributions below. - Constructions of PRO: We show how to construct the strongest version of PRO, assuming the sub-exponential hardness of the learning with errors (LWE) problem, and of the evasive LWE problem (Wee, EUROCRYPT 2022; Tsabary, CRYPTO 2022). - Applications outside the iO World: We show how to construct a succinct witness encryption scheme from PRO, where the size of the ciphertext is independent of the witness size. Such a witness encryption scheme is not known to exist even assuming iO. - Applications in the iO World: Our weakest variant of pseudorandom obfuscation, named obfuscation for identical pseudorandom functions (iPRO), is weaker than iO: rather than obfuscating arbitrary circuits as in iO, iPRO only obfuscates circuits computing pseudorandom functions. We show that iPRO already enables several applications of iO, such as unleveled fully homomorphic encryption (without assuming circular security) and succinct randomized encodings. - From iPRO to iO: Despite being a seemingly weaker notion than iO, we show two pathways to constructing full-fledged iO from iPRO. Our first construction builds iO from iPRO and (standard assumptions on) cryptographic bilinear maps. Combined with our construction of iPRO, this gives us a construction of iO from a new combination of assumptions, namely LWE, evasive LWE and bilinear maps. Our second construction builds iO (and even ideal obfuscation) from iPRO in the pseudorandom oracle model (Jain, Lin, Luo and Wichs, CRYPTO 2023). To our knowledge, this is the first purely lattice-based, and hence plausibly post-quantum secure, construction of iO with a proof of security from LWE and evasive LWE. Finally, we highlight some barriers in achieving the strongest version of pseudorandom obfuscation.