Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: From the Impossibility of Obfuscation to a New Non-Black-Box Technique
event speaker icon
Nir Bitansky (Tel-Aviv University)
event date icon
Wednesday, 21.11.2012, 12:30
event location icon
Taub 201
The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak’s techniques were subsequently extended and have given rise to various powerful applications. We present the first non-black-box simulation technique that does not rely on Barak’s technique. Our technique is based on essentially different tools: it does not invoke universal arguments, nor does it rely on collision-resistant hashing. Instead, the main ingredient we use is the impossibility result for general program obfuscation of Barak et al. (CRYPTO 2001).

Using our technique, we construct a new resettably sound zero-knowledge (rsZK) protocol. rsZK protocols remain sound even against cheating provers that can repeatedly reset the verifier to its initial state and random tape. Indeed, for such protocols black-box simulation is impossible. Our rsZK protocol is based solely on semi-honest oblivious transfer and does not rely on collision-resistant hashing; in addition, our protocol does not use PCP machinery. In the converse direction, we show a generic transformation from any rsZK protocol to a family of functions that cannot be obfuscated.

Joint work with Omer Paneth.