Barak: „How to Go Beyond the Black-Box Simulation Barrier“

17.10.2018, 10:00 – 11:30

17.10.2018 10:00-11:30

Speaker: Felix Rohrbach, TU Darmstadt, Cryptoplexity Group | Location: Mornewegstraße 32 (S4|14), Room 5.3.01, Darmstadt

Organizer: Felix Günther, Christian Janson


This talk is the first one in the seminar series „Reading the Crypto Classics“ for the winter term 2018/2019. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper Barak: „How to Go Beyond the Black-Box Simulation Barrier“ (FOCS 2001), with the following abstract:

„The simulation paradigm is central to cryptography. A simulator is an algorithm that tries to simulate the interaction of the adversary with an honest party, without knowing the private input of this honest party. Almost all known simulators use the adversary's algorithm as a black-box. We present the first constructions of non-black-box simulators. Using these new non-black-box techniques, we obtain several results that were previously proven to be impossible to obtain using black-box simulators. Specifically, assuming the existence of collision resistent hash functions, we construct a new zero-knowledge argument system for NP that satisfies the following properties: 1. This system has a constant number of rounds with negligible soundness error. 2. It remains zero knowledge even when composed concurrently n times, where n is the security parameter. Simultaneously obtaining 1 and 2 has been recently proven to be impossible to achieve using black-box simulators. 3. It is an Arthur-Merlin (public coins) protocol. Simultaneously obtaining 1 and 3 was known to be impossible to achieve with a black-box simulator. 4. It has a simulator that runs in strict polynomial time, rather than in expected polynomial time. All previously known constant-round, negligible-error zero-knowledge arguments utilized expected polynomial-time simulators.“