TU Darmstadt / ULB / TUbiblio

Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources

Brzuska, Christina ; Farshim, Pooya ; Mittelbach, Arno
Hrsg.: 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
Konferenzveröffentlichung, Bibliographie

Kurzbeschreibung (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.

Typ des Eintrags: Konferenzveröffentlichung
Erschienen: 2014
Herausgeber: Garay, Arno A. ; Gennaro, Rosario
Autor(en): Brzuska, Christina ; Farshim, Pooya ; Mittelbach, Arno
Art des Eintrags: Bibliographie
Titel: Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources
Sprache: Deutsch
Publikationsjahr: August 2014
Verlag: Springer
Buchtitel: Advances in Cryptology – CRYPTO 2014. 34th Annual Cryptology Conference. Santa Barbara, CA, USA. August 17-21, 2014. Proceedings.
Reihe: Lecture Notes in Computer Science 8616
Band einer Reihe: 1
Veranstaltungsort: Santa Barbara, CA, USA
DOI: 10.1007/978-3-662-44371-2_11
Kurzbeschreibung (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.

Freie Schlagworte: Randomized encodings, obfuscation, UCE, random oracle
ID-Nummer: TUD-CS-2014-1101
Fachbereich(e)/-gebiet(e): Profilbereiche
Profilbereiche > Cybersicherheit (CYSEC)
Hinterlegungsdatum: 21 Aug 2017 14:24
Letzte Änderung: 22 Jan 2019 10:37
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen