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