Abstract: We investigate several previously suggested scenarios of instantiating random oracles (ROs) with ``realizable'' primitives in cryptographic schemes. As candidates for such ``instantiating'' primitives we pick perfectly one-way hash functions (POWHFs) and verifiable pseudorandom functions (VPRFs). Our analysis focuses on the most practical encryption schemes such as OAEP and its variant PSS-E and the Fujisaki-Okamoto hybrid encryption scheme. We also consider the RSA Full Domain Hash (FDH) signature scheme.
We first show that some previous beliefs about instantiations for some of these schemes are not true. Namely we show that, contrary to Canetti's conjecture, in general one cannot instantiate either one of the two ROs in the OAEP encryption scheme by POWHFs without losing security. We also confirm through the FDH signature scheme that the straightforward instantiation of ROs with VPRFs may result in insecure schemes, in contrast to regular pseudorandom functions which can provably replace ROs (in a well-defined way).
But unlike a growing number of papers on negative results about ROs, we bring some good news. We show that one can realize \emph{one} of the two ROs in a variant of the PSS-E encryption scheme and \emph{either one} of the two ROs in the Fujisaki-Okamoto hybrid encryption scheme through POWHFs, while preserving the IND-CCA security in both cases (still in the RO model). Although this partial instantiation in form of substituting only one RO does not help to break out of the random oracle model, it yet gives a better understanding of the necessary properties of the primitives and also constitutes a better security heuristic.
Ref: An extended abstract of this paper appeared in Advances in Cryptology -Crypto 2005 Proceedings, Lecture Notes in Computer Science Vol. 3621, V. Shoup ed., Springer-Verlag, 2005. Full paper available below.
Full paper: Available as pdf. ( Help if this doesn't work).