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

Tuesday, November 7, 2017 - 4:00pm to 5:00pm
Light Refreshments at 3:45pm
Patil/Kiva G449
Omer Paneth

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.