TU Darmstadt / ULB / TUbiblio

Using Indistinguishability Obfuscation via UCEs

Brzuska, Christina and Mittelbach, Arno (2014):
Using Indistinguishability Obfuscation via UCEs.
In: Advances in Cryptology – ASIACRYPT 2014. 20th International Conference on the Theory and Application of Cryptology and Information Security., Berlin, Heidelberg, Springer, pp. 22-141, DOI: 10.1007/978-3-662-45608-8, [Book Section]

Abstract

We provide the first standard model construction for a powerful class of Universal Computational Extractors (UCEs; Bellare et al. Crypto 2013) based on indistinguishability obfuscation. Our construction suffices to instantiate q-query correlation-secure hash functions and to extract polynomially many hardcore bits from any one-way function. For many cryptographic primitives and in particular for correlation-secure hash functions all known constructions are in the random-oracle model. Indeed, recent negative results by Wichs (ITCS 2013) rule out a large class of techniques to prove the security of correlation-secure hash functions in the standard model. Our construction is based on puncturable PRFs (Sahai und Waters; STOC 2014) and indistinguishability obfuscation. However, our proof also relies on point obfuscation under auxiliary inputs (AIPO). This is crucial in light of Wichs’ impossibility result. Namely, Wichs proves that it is often hard to reduce two-stage games (such as UCEs) to a “one-stage assumption” such as DDH. In contrast, AIPOs and their underlying assumptions are inherently two-stage and, thus, allow us to circumvent Wichs’ impossibility result. Our positive result is also noteworthy insofar as Brzuska, Farshim and Mittelbach (Crypto 2014) have shown recently, that iO and some variants of UCEs are mutually exclusive. Our results, hence, validate some of the new UCE notions that emerged as a response to the iO-attack.

Item Type: Book Section
Erschienen: 2014
Creators: Brzuska, Christina and Mittelbach, Arno
Title: Using Indistinguishability Obfuscation via UCEs
Language: English
Abstract:

We provide the first standard model construction for a powerful class of Universal Computational Extractors (UCEs; Bellare et al. Crypto 2013) based on indistinguishability obfuscation. Our construction suffices to instantiate q-query correlation-secure hash functions and to extract polynomially many hardcore bits from any one-way function. For many cryptographic primitives and in particular for correlation-secure hash functions all known constructions are in the random-oracle model. Indeed, recent negative results by Wichs (ITCS 2013) rule out a large class of techniques to prove the security of correlation-secure hash functions in the standard model. Our construction is based on puncturable PRFs (Sahai und Waters; STOC 2014) and indistinguishability obfuscation. However, our proof also relies on point obfuscation under auxiliary inputs (AIPO). This is crucial in light of Wichs’ impossibility result. Namely, Wichs proves that it is often hard to reduce two-stage games (such as UCEs) to a “one-stage assumption” such as DDH. In contrast, AIPOs and their underlying assumptions are inherently two-stage and, thus, allow us to circumvent Wichs’ impossibility result. Our positive result is also noteworthy insofar as Brzuska, Farshim and Mittelbach (Crypto 2014) have shown recently, that iO and some variants of UCEs are mutually exclusive. Our results, hence, validate some of the new UCE notions that emerged as a response to the iO-attack.

Title of Book: Advances in Cryptology – ASIACRYPT 2014. 20th International Conference on the Theory and Application of Cryptology and Information Security.
Series Name: Lecture Notes in Computer Science
Volume: 2
Number: 8874
Place of Publication: Berlin, Heidelberg
Publisher: Springer
ISBN: 978-3-662-45607-1
Uncontrolled Keywords: foundations / correlation-secure hash functions, hardcore functions, indistinguishability obfuscation, differing-inputs obfuscation, point-function obfuscation, auxiliary-input obfuscation, universal computational extractors (UCEs)
Divisions: Profile Areas
Profile Areas > Cybersecurity (CYSEC)
Event Location: Kaoshiung, Taiwan
Date Deposited: 21 Aug 2017 12:59
DOI: 10.1007/978-3-662-45608-8
Identification Number: TUD-CS-2014-1095
Export:

Optionen (nur für Redakteure)

View Item View Item