TU Darmstadt / ULB / TUbiblio

Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources

Brzuska, Christina and Farshim, Pooya and Mittelbach, Arno
Garay, Arno A. and Gennaro, Rosario (eds.) (2014):
Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources.
In: Advances in Cryptology – CRYPTO 2014. 34th Annual Cryptology Conference. Santa Barbara, CA, USA. August 17-21, 2014. Proceedings., Springer, Santa Barbara, CA, USA, In: Lecture Notes in Computer Science 8616, ISBN 978-3-662-44370-5,
DOI: 10.1007/978-3-662-44371-2_11, [Conference or Workshop Item]

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.

Item Type: Conference or Workshop Item
Erschienen: 2014
Editors: Garay, Arno A. and Gennaro, Rosario
Creators: Brzuska, Christina and Farshim, Pooya and Mittelbach, Arno
Title: Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources
Language: German
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.

Title of Book: Advances in Cryptology – CRYPTO 2014. 34th Annual Cryptology Conference. Santa Barbara, CA, USA. August 17-21, 2014. Proceedings.
Series Name: Lecture Notes in Computer Science 8616
Volume: 1
Publisher: Springer
ISBN: 978-3-662-44370-5
Uncontrolled Keywords: Randomized encodings, obfuscation, UCE, random oracle
Divisions: Profile Areas
Profile Areas > Cybersecurity (CYSEC)
Event Location: Santa Barbara, CA, USA
Date Deposited: 21 Aug 2017 14:24
DOI: 10.1007/978-3-662-44371-2_11
Identification Number: TUD-CS-2014-1101
Export:

Optionen (nur für Redakteure)

View Item View Item