Omer Paneth: On the round Complexity of Zero-Knowledge Protocols and Compressing Collisions

Abstract: The round complexity of zero-knowledge protocols is a long-standing open question in the theory of cryptography. Its study over the past three decades has revealed connections to other fundamental concepts such as non-black-box reductions and succinct proof systems.

In the first part of the talk, I will survey the history of the question. In the second part, I will present a new result that resolves the question under a new hardness assumption. Roughly, the assumption asserts the existence of shrinking hash functions such that no polynomial-time algorithm, with advice of size k, can output much more than k colliding inputs. I will motivate this assumption and discuss additional applications.

Based on joint works with Nir Bitansky, Zvika Brakerski, Yael Kalai and Vinod Vaikuntanathan.