TU Darmstadt / ULB / TUbiblio

Indistinguishability Obfuscation versus Multi-Bit Point Obfuscation with Auxiliary Input

Brzuska, Christina ; Mittelbach, Arno
Hrsg.: Sarkar, Palash ; Iwata, Tetsu (2014)
Indistinguishability Obfuscation versus Multi-Bit Point Obfuscation with Auxiliary Input.
In: Advances in Cryptology – ASIACRYPT 2014. 20th International Conference on the Theory and Application of Cryptology and Information Security. Proceedings.
doi: 10.1007/978-3-662-45608-8_8
Buchkapitel, Bibliographie

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

Typ des Eintrags: Buchkapitel
Erschienen: 2014
Herausgeber: Sarkar, Palash ; Iwata, Tetsu
Autor(en): Brzuska, Christina ; Mittelbach, Arno
Art des Eintrags: Bibliographie
Titel: Indistinguishability Obfuscation versus Multi-Bit Point Obfuscation with Auxiliary Input
Sprache: Englisch
Publikationsjahr: Dezember 2014
Ort: Berlin, Heidelberg
Verlag: Springer
(Heft-)Nummer: 8874
Buchtitel: Advances in Cryptology – ASIACRYPT 2014. 20th International Conference on the Theory and Application of Cryptology and Information Security. Proceedings.
Reihe: Lecture Notes in Computer Science
Band einer Reihe: 2
DOI: 10.1007/978-3-662-45608-8_8
URL / URN: https://link.springer.com/chapter/10.1007/978-3-662-45608-8_...
Kurzbeschreibung (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.

Freie Schlagworte: Indistinguishability obfuscation differing-inputs obfuscation point function obfuscation multi-bit point function obfuscation auxiliary input obfuscation leakage resilient PKE
ID-Nummer: TUD-CS-2014-1100
Fachbereich(e)/-gebiet(e): Profilbereiche
Profilbereiche > Cybersicherheit (CYSEC)
Hinterlegungsdatum: 21 Aug 2017 14:14
Letzte Änderung: 08 Mai 2024 11:27
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