TU Darmstadt / ULB / TUbiblio

Indistinguishability Obfuscation versus Multi-Bit Point Obfuscation with Auxiliary Input

Brzuska, Christina and Mittelbach, Arno Sarkar, Palash and Iwata, Tetsu (eds.) (2014):
Indistinguishability Obfuscation versus Multi-Bit Point Obfuscation with Auxiliary Input.
In: Lecture Notes in Computer Science, In: Advances in Cryptology – ASIACRYPT 2014. 20th International Conference on the Theory and Application of Cryptology and Information Security. Proceedings., Berlin, Heidelberg, Springer, pp. 142-161, DOI: 10.1007/978-3-662-45608-8_8,
[Online-Edition: https://link.springer.com/chapter/10.1007/978-3-662-45608-8_...],
[Book Section]

Abstract

In a recent celebrated breakthrough, Garg et al. (FOCS 2013) gave the first candidate for so-called indistinguishability obfuscation (iO) thereby reviving the interest in obfuscation for a general purpose. Since then, iO has been used to advance numerous sub-areas of cryptography. While indistinguishability obfuscation is a general purpose obfuscation scheme, several obfuscators for specific functionalities have been considered. In particular, special attention has been given to the obfuscation of so-called point functions that return zero everywhere, except for a single point x. A strong variant is point obfuscation with auxiliary input (AIPO), which allows an adversary to learn some non-trivial auxiliary information about the obfuscated point x (Goldwasser, Tauman-Kalai; FOCS, 2005). Multi-bit point functions are a strengthening of point functions, where on x, the point function returns a string m instead of 1. Multi-bit point functions with auxiliary input (MB-AIPO) have been constructed from composable AIPO by Canetti and Dakdouk (Eurocrypt 2008) and have been used by Matsuda and Hanaoka (TCC 2014) to construct CCA-secure public-key encryption schemes and by Bitansky and Paneth (TCC 2012) to construct three-round weak zero-knowledge protocols for NP. In this paper we present both positive and negative results. We show that if indistinguishability obfuscation exists, then MB-AIPO does not. Towards this goal, we build on techniques by Brzuska, Farshim and Mittelbach (Crypto 2014) who use indistinguishability obfuscation as a mean to attack a large class of assumptions from the Universal Computational Extractor framework (Bellare, Hoang and Keelveedhi; Crypto 2013). On the positive side we introduce a weak version of MB-AIPO which we deem to be outside the reach of our impossibility result. We build this weak version of MB-AIPO based on iO and AIPO and prove that it suffices to construct a public-key encryption scheme that is secure even if the adversary can learn an arbitrary leakage function of the secret key, as long as the secret key remains computationally hidden. Thereby, we strengthen a result by Canetti et al. (TCC 2010) that showed a similar connection in the symmetric-key setting.

Item Type: Book Section
Erschienen: 2014
Editors: Sarkar, Palash and Iwata, Tetsu
Creators: Brzuska, Christina and Mittelbach, Arno
Title: Indistinguishability Obfuscation versus Multi-Bit Point Obfuscation with Auxiliary Input
Language: English
Abstract:

In a recent celebrated breakthrough, Garg et al. (FOCS 2013) gave the first candidate for so-called indistinguishability obfuscation (iO) thereby reviving the interest in obfuscation for a general purpose. Since then, iO has been used to advance numerous sub-areas of cryptography. While indistinguishability obfuscation is a general purpose obfuscation scheme, several obfuscators for specific functionalities have been considered. In particular, special attention has been given to the obfuscation of so-called point functions that return zero everywhere, except for a single point x. A strong variant is point obfuscation with auxiliary input (AIPO), which allows an adversary to learn some non-trivial auxiliary information about the obfuscated point x (Goldwasser, Tauman-Kalai; FOCS, 2005). Multi-bit point functions are a strengthening of point functions, where on x, the point function returns a string m instead of 1. Multi-bit point functions with auxiliary input (MB-AIPO) have been constructed from composable AIPO by Canetti and Dakdouk (Eurocrypt 2008) and have been used by Matsuda and Hanaoka (TCC 2014) to construct CCA-secure public-key encryption schemes and by Bitansky and Paneth (TCC 2012) to construct three-round weak zero-knowledge protocols for NP. In this paper we present both positive and negative results. We show that if indistinguishability obfuscation exists, then MB-AIPO does not. Towards this goal, we build on techniques by Brzuska, Farshim and Mittelbach (Crypto 2014) who use indistinguishability obfuscation as a mean to attack a large class of assumptions from the Universal Computational Extractor framework (Bellare, Hoang and Keelveedhi; Crypto 2013). On the positive side we introduce a weak version of MB-AIPO which we deem to be outside the reach of our impossibility result. We build this weak version of MB-AIPO based on iO and AIPO and prove that it suffices to construct a public-key encryption scheme that is secure even if the adversary can learn an arbitrary leakage function of the secret key, as long as the secret key remains computationally hidden. Thereby, we strengthen a result by Canetti et al. (TCC 2010) that showed a similar connection in the symmetric-key setting.

Title of Book: Advances in Cryptology – ASIACRYPT 2014. 20th International Conference on the Theory and Application of Cryptology and Information Security. Proceedings.
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: Indistinguishability obfuscation differing-inputs obfuscation point function obfuscation multi-bit point function obfuscation auxiliary input obfuscation leakage resilient PKE
Divisions: Profile Areas
Profile Areas > Cybersecurity (CYSEC)
Event Title: 20th International Conference on the Theory and Application of Cryptology and Information Security
Event Location: Kaoshiung, Taiwan (R.O.C.)
Event Dates: December 7-11, 2014
Date Deposited: 21 Aug 2017 14:14
DOI: 10.1007/978-3-662-45608-8_8
Official URL: https://link.springer.com/chapter/10.1007/978-3-662-45608-8_...
Identification Number: TUD-CS-2014-1100
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)

View Item View Item