Paper 2022/1204

The Pseudorandom Oracle Model and Ideal Obfuscation

Aayush Jain, Carnegie Mellon University
Huijia Lin, University of Washington
Ji Luo, University of Washington
Daniel Wichs, Northeastern University, NTT Research
Abstract

We introduce a new idealized model of hash functions, which we refer to as the *pseudorandom oracle* (${\mathrm{Pr}\mathcal{O}}$) model. Intuitively, it allows us to model cryptosystems that use the code of an ideal hash function in a non-black-box way. Formally, we model hash functions via a combination of a pseudorandom function (PRF) family and an ideal oracle. A user can initialize the hash function by choosing a PRF key $k$ and mapping it to a public handle $h$ using the oracle. Given the handle $h$ and some input $x$, the oracle can also be called to evaluate the PRF at $x$ with the corresponding key $k$. A user who chooses the PRF key $k$ therefore has a complete description of the hash function and can use its code in non-black-box constructions, while an adversary, who just gets the handle $h$, only has black-box access to the hash function via the oracle. As our main result, we show how to construct ideal obfuscation in the ${\mathrm{Pr}\mathcal{O}}$ model, starting from functional encryption (FE), which in turn can be based on well-studied polynomial hardness assumptions. In contrast, we know that ideal obfuscation cannot be instantiated in the basic random oracle model under any assumptions. We believe our result provides heuristic justification for the following: (1) most natural security goals implied by ideal obfuscation can be achieved in the real world; (2) obfuscation can be constructed from FE at polynomial security loss. We also discuss how to interpret our result in the ${\mathrm{Pr}\mathcal{O}}$ model as a construction of ideal obfuscation using simple hardware tokens or as a way to bootstrap ideal obfuscation for PRFs to that for all functions.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2023
DOI
10.1007/978-3-031-38551-3_8
Contact author(s)
aayushja @ andrew cmu edu
rachel @ cs washington edu
luoji @ cs washington edu
wichs @ ccs neu edu
History
2023-08-10: revised
2022-09-12: received
See all versions
Short URL
https://ia.cr/2022/1204
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1204,
      author = {Aayush Jain and Huijia Lin and Ji Luo and Daniel Wichs},
      title = {The Pseudorandom Oracle Model and Ideal Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1204},
      year = {2022},
      doi = {10.1007/978-3-031-38551-3_8},
      note = {\url{https://eprint.iacr.org/2022/1204}},
      url = {https://eprint.iacr.org/2022/1204}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.