International Association
for Cryptologic Research

Assuming the existence of an indistinguishability obfuscator (iO), we show that a number of prominent constructions in the random-oracle model are uninstantiable in the standard model. We first show that the Encrypt-with-Hash (EwH) transform of Bellare, Boldyreva, and O\'Neill (CRYPTO 2007) for converting randomized public-key encryption (PKE) to deterministic PKE is not instantiable in the standard model. The techniques that we use to establish this result are flexible and lend themselves easily to other transformations. These include the classical Fujisaki-Okamoto transform (CRYPTO 1998) for converting CPA to CCA security, a transformation akin to that by Bellare and Keelveedhi (CRYPTO 2011) for obtaining key-dependent security, as well as the convergent encryption transform for obtaining messaged-locked encryption by Bellare, Keelveedhi, and Ristenpart (EUROCRYPT 2013). Our techniques build on the recent work of Brzuska, Farshim, and Mittelbach (CRYPTO 2014) and rely on the existence of iO for Turing machines or circuits to derive two flavors of uninstantiability. Our results call for a re-assessment of scheme design in the random-oracle model and point out the need for new transforms which do not suffer from our attacks.