| Abstract | Random oracles are powerful cryptographic objects. They facilitate the security proofs
of an impressive number of practical cryptosystems ranging from KDM-secure and deterministic
encryption to point-function obfuscation and many more. However, due to an uninstantiability result
of Canetti, Goldreich, and Halevi (STOC 1998) random oracles have become somewhat controversial.
Recently, Bellare, Hoang, and Keelveedhi (BHK; CRYPTO 2013 and ePrint 2013/424, August 2013)
introduced a new abstraction called Universal Computational Extractors (UCEs), and showed that
they suffice to securely replace random oracles in a number of prominent applications, including all
those mentioned above, without suffering from the aforementioned uninstantiability result. This,
however, leaves open the question of constructing UCEs in the standard model.
We show that the existence of indistinguishability obfuscation (iO) implies (non-black-box) attacks
on all the definitions that BHK proposed within their UCE framework in the original version of
their paper, in the sense that no concrete hash function can satisfy them. We also show that this
limitation can be overcome, to some extent, by restraining the class of admissible adversaries via a
statistical notion of unpredictability. Following our attack, BHK (ePrint 2013/424, September 2013),
independently adopted this approach in their work.
In the updated version of their paper, BHK (ePrint 2013/424, September 2013) also introduce two
other novel source classes, called bounded parallel sources and split sources, which aim at recovering
the computational applications of UCEs that fall outside the statistical fix. These notions keep to
a computational notion of unpredictability, but impose structural restrictions on the adversary so
that our original iO attack no longer applies. We extend our attack to show that indistinguishability
obfuscation is sufficient to also break the UCE security of any hash function against bounded parallel
sources. Towards this goal, we use the randomized encodings paradigm of Applebaum, Ishai, and
Kushilevitz (STOC 2004) to parallelize the obfuscated circuit used in our attack, so that it can be
computed by a bounded parallel source whose second stage consists of constant-depth circuits. We
conclude by discussing the composability and feasibility of hash functions secure against split sources. |
|---|
