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.

Classically, selective-opening attack (SOA) has been studied for \emph{randomized} primitives, like randomized encryption schemes and commitments. The study of SOA for deterministic primitives, which presents some unique challenges, was initiated by Bellare \emph{et al.} (PKC 2015), who showed negative results. Subsequently, Hoang \emph{et al.} (ASIACRYPT 2016) showed positive results in the non-programmable random oracle model. Here we show the first positive results for SOA security of deterministic primitives in the \emph{standard} (RO devoid) model. Our results are: \begin{itemize} \item Any $2t$-wise independent hash function is SOA secure for an unbounded number of ``$t$-correlated'' messages, meaning any group of up to $t$ messages are arbitrarily correlated. \item A construction of a deterministic encryption scheme with analogous security, combining a regular lossy trapdoor function with a $2t$-wise independent hash function. \item The one-more-RSA problem of Bellare \emph{et al.} (J.~Cryptology 2003), which can be seen as a form of SOA, is hard under the $\Phi$-Hiding Assumption with large enough encryption exponent. \end{itemize} Somewhat surprisingly, the last result yields the first proof of RSA-based Chaum's blind signature scheme (CRYPTO 1982) based on a ``standard'' computational assumption. Notably, it avoids the impossibility result of Pass (STOC 2011) because lossiness of RSA endows the scheme with non-unique signatures.

We show new partial and full instantiation results under chosen-ciphertext security for the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and two variants. Prior work on such instantiations either showed negative results or settled for “passive” security notions like IND-CPA. More precisely, recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round functions are modeled as random oracles (ROs), with RSA. Our main results are: Either of the two oracles (while still modeling the other as a RO) can be instantiated in RSA-OAEP under IND-CCA2 using mild standard-model assumptions on the round functions and generalizations of algebraic properties of RSA shown by Barthe, Pointcheval, and Báguelin (CCS 2012). The algebraic properties are only shown to hold at practical parameters for small encryption exponent ( $$e=3$$ ), but we argue they have value for larger e as well. Both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called “ t -clear” and “ s -clear” RSA-OAEP. For this we use extractability-style assumptions in the sense of Canetti and Dakdouk (TCC 2010) on the round functions, as well as novel yet plausible “XOR-type” assumptions on RSA. While admittedly strong, such assumptions may nevertheless be necessary at this point to make positive progress. In particular, our full instantiations evade impossibility results of Shoup (J. Cryptology 2002), Kiltz and Pietrzak (EUROCRYPT 2009), and Bitansky et al. (STOC 2014). Moreover, our results for s -clear RSA-OAEP yield the most efficient RSA-based encryption scheme proven IND-CCA2 in the standard model (using bold assumptions on cryptographic hashing) to date.