Pseudorandom Obfuscation and Applications

Pedro Branco; Nico Döttling; Abhishek Jain; Giulio Malavolta; Surya Mathialagan; Spencer Peters; Vinod Vaikuntanathan

Paper 2024/1742

Pseudorandom Obfuscation and Applications

Pedro Branco, Bocconi University

Nico Döttling, Helmholtz Center for Information Security

Abhishek Jain, NTT Research, John Hopkins University

Giulio Malavolta, Bocconi University

Surya Mathialagan, Massachusetts Institute of Technology

Spencer Peters, Cornell University

Vinod Vaikuntanathan, Massachusetts Institute of Technology

Abstract

We introduce the notion of pseudorandom obfuscation, a way to obfuscate (keyed) pseudorandom functions in an average-case sense. We study several variants of pseudorandom obfuscation and show a number of applications. 1. Applications in the iO World: Our weakest variant of pseudorandom obfuscation, named obfuscation for identical pseudorandom functions (iPRO), is weaker than indistinguishability obfuscation (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. 2. From iPRO to iO: Despite being a weaker notion than iO, we show two transformations from iPRO to iO. Our first (and main) construction builds iO from iPRO plus standard assumptions on cryptographic bilinear maps. Our second construction builds iO, and even ideal obfuscation, from iPRO alone in the pseudorandom oracle model (Jain, Lin, Luo and Wichs, CRYPTO 2023). We also formulate stronger variants of pseudorandom obfuscation that help us go beyond the applications of indistinguishability obfuscation. 3. Applications outside the iO World: We show how to construct a succinct witness encryption scheme from a strong version of 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. 4. Construction: We show a *heuristic* construction of the strongest version of PRO, secure under the sub-exponential hardness of the learning with errors (LWE) problem, and the private-coin evasive LWE heuristic (Wee, EUROCRYPT 2022; Tsabary, CRYPTO 2022). Finally, we highlight some barriers in achieving the strongest version of pseudorandom obfuscation.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Contact author(s): pedrodemelobranco @ gmail com
nico doettling @ gmail com
abhishek jain @ ntt-research com
giulio malavolta @ hotmail it
smathi @ mit edu
sp2473 @ cornell edu
vinodv @ mit edu
History: 2025-02-27: revised; 2024-10-25: received; See all versions
Short URL: https://ia.cr/2024/1742
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1742,
      author = {Pedro Branco and Nico Döttling and Abhishek Jain and Giulio Malavolta and Surya Mathialagan and Spencer Peters and Vinod Vaikuntanathan},
      title = {Pseudorandom Obfuscation and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1742},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1742}
}