TU Darmstadt / ULB / TUbiblio

Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources

Brzuska, Christina ; Farshim, Pooya ; Mittelbach, Arno
eds.: Garay, Arno A. ; Gennaro, Rosario (2014)
Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources.
Santa Barbara, CA, USA
doi: 10.1007/978-3-662-44371-2_11
Conference or Workshop Item, Bibliographie

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. ; Gennaro, Rosario
Creators: Brzuska, Christina ; Farshim, Pooya ; Mittelbach, Arno
Type of entry: Bibliographie
Title: Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources
Language: German
Date: August 2014
Publisher: Springer
Book Title: Advances in Cryptology – CRYPTO 2014. 34th Annual Cryptology Conference. Santa Barbara, CA, USA. August 17-21, 2014. Proceedings.
Series: Lecture Notes in Computer Science 8616
Series Volume: 1
Event Location: Santa Barbara, CA, USA
DOI: 10.1007/978-3-662-44371-2_11
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.

Uncontrolled Keywords: Randomized encodings, obfuscation, UCE, random oracle
Identification Number: TUD-CS-2014-1101
Divisions: Profile Areas
Profile Areas > Cybersecurity (CYSEC)
Date Deposited: 21 Aug 2017 14:24
Last Modified: 22 Jan 2019 10:37
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details