[Busec] CORRECT TITLE: Crypto Reading Group, Apr. 23rd, 9:00 -- 11:00am
huijial at gmail.com
Thu Apr 18 16:25:53 EDT 2013
Sorry for the wrong subject of the last email. Note that the next crypto
reading group is on *next Tuesday*.
On Thu, Apr 18, 2013 at 4:23 PM, Huijia Lin <huijial at gmail.com> wrote:
> Dear all:
> Next Tuesday, Nir Bitansky, from Tel Aviv University will tell us about "On
> the Impossibility of Approximate Obfuscation and Applications to
> Resettable Cryptography" (abstract below and full paper at *
> https://eprint.iacr.org/2012/729*). Please come and enjoy. Breakfast will
> be provided.
> Speaker: Nir Bitansky
> Venue: MIT, 32-D463 (Star)
> Time: Apr. 23rd, 9:00am --11:00am
> See you and have a nice day!
> On the Impossibility of Approximate Obfuscation
> and Applications to Resettable Cryptography
> The traditional notion of program obfuscation requires that an obfuscation
> P' of a program P computes the exact same function as P, but beyond that,
> the code of P' should not leak any information about P. This strong notion
> of virtual black-box security was shown by Barak et al. (CRYPTO 2001) to be
> impossible to achieve, for certain unobfuscatable function families. The
> same work raised the question of approximate obfuscation, where the
> obfuscated P' is only required to approximate P; that is, P' only agrees
> with P with high enough probability on some input distribution.
> We show that, assuming trapdoor permutations, there exist families of
> robust unobfuscatable functions for which even approximate obfuscation is
> impossible. Speciﬁcally, obfuscation is impossible even if the obfuscated
> P' is only required to agree with P with probability slightly more than
> 1/2, on a uniformly sampled input (below 1/2-agreement, the function
> obfuscated by P, is not uniquely deﬁned). Additionally, assuming only
> one-way functions, we rule out approximate obfuscation where P' may output
> \bot with probability close to 1 but otherwise must agree with P.
> We demonstrate the power of robust unobfuscatable functions by exhibiting
> new implications to resettable protocols. Concretely, we reduce the
> assumptions required for resettably-sound zero-knowledge to one-way
> functions, as well as reduce round-complexity. We also present a new
> simplified construction of a simultaneously-resettable zero-knowledge
> protocol, based on one-way functions, and any simultaneously-resettable
> witness-indistinguishable protocol. Finally, we construct a three-message
> simultaneously-resettable witness-indistinguishable argument of knowledge
> (with a non-black-box knowledge extractor). Our constructions use a new
> non-black-box simulation technique that is based on a special kind of
> “resettable slots”. These slots are useful for a non-black-box simulator,
> but not for a resetting prover.
> Joint work with Omer Paneth.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Busec