Multi-bit point functions are a strengthening of point functions, where on $\alpha$, the point function returns a string $\beta$ instead of $1$. Multi-bit point functions with auxiliary input (MB-AIPO) have been constructed by Canetti and Bitansky (Crypto 2010) and have been used by Matsuda and Hanaoka (TCC 2014) to construct CCA-secure public-key encryption schemes and by and 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 means of attacking a large class of assumptions from the Universal Computational Extractor framework (Bellare et al; 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 prove that this weak version of MB-AIPO 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.Category / Keywords: foundations / indistinguishability obfuscation, differing-inputs obfuscation, point function obfuscation, multi-bit point function obfuscation, auxiliary input obfuscation, leakage resilient PKE Date: received 31 May 2014, last revised 2 Jun 2014 Contact author: arno mittelbach at cased de Available format(s): PDF | BibTeX Citation Version: 20140602:071211 (All versions of this report) Discussion forum: Show discussion | Start new discussion