International Association
for Cryptologic Research

Extending a line of work leveraging program obfuscation to instantiate random oracles (ROs) (\emph{e.g.}, Hohenberger \emph{et al.}, EUROCRYPT 2014, Kalai \emph{el al.}, CRYPTO 2017), we show that, using program obfuscation and other suitable assumptions, there exist standard-model hash functions that suffice to instantiate the classical RO-model encryption transforms OAEP (Bellare and Rogaway, EUROCRYPT 1994) and Fujisaki-Okamoto (EUROCRYPT 1998) under IND-CCA. Our result for Fujisaki-Okamoto employs a simple modification to the scheme that may be interesting for the current NIST PQC competition. For the most part, our instantiations do not require much stronger assumptions on the base schemes compared to their corresponding RO-model proofs. For example, to instantiate low-exponent RSA-OAEP, the assumption we need on RSA is sub-exponential partial one-wayness, matching the assumption on RSA needed by Fujisaki \emph{et al.} (J.~Cryptology 2004) in the RO model up to sub-exponentiality. Similarly, for the part of Fujisaki-Okamoto that upgrades indistinguishability under plaintext-checking to attack (OW-PCA) to IND-CCA, we again do not require much stronger assumptions up to sub-exponentiality. We obtain our hash functions in a unified way, extending a technique of Brzuska and Mittelbach (ASIACRYPT 2014). We incorporate into their technique: (1) extremely lossy functions (ELFs), a notion by Zhandry (CRYPTO 2016), and (2) \emph{multi-bit} auxiliary-input point function obfuscation (MB-AIPO). While MB-AIPO is impossible in general (Brzuska and Mittelbach, ASIACRYPT 2014), we give plausible constructions for the special cases we need, which may be of independent interest. We stress that our hash functions are not practical, but are meant to justify that when using the transforms in practice with cryptographic hashing, the end goal is plausible.