[Busec] CORRECT TITLE: Crypto Reading Group, Apr. 23rd, 9:00 -- 11:00am

Huijia Lin 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*.

Rachel

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!
> Rachel
>
> ==============================================
> 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. Specifically, 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 defined). 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...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20130418/90d44692/attachment.html>


More information about the Busec mailing list