On the (Im)Plausibility of Constant-Round Public-Coin Straight-Line-Simulatable Zero-Knowledge Proofs
In 2001, a breakthrough result by Barak [FOCS 2001] showed how to achieve public-coin Zero-Knowledge (ZK) arguments in constant rounds, a feature known to be impossible using black-box simulation. In this approach, the simulator makes use of the code of the malicious verifier in computing the prover messages (albeit without understanding it), and does not rewind the malicious verifier - and it is hence called a straight-line simulator. Since then, however, the authors have witnessed little progress on the basic question whether Barak's technique can be extended to ZK proof systems. In this paper, they make progress on this front, by providing strong evidence that such an extension is far from likely.