Omer Paneth: On the round Complexity of Zero-Knowledge Protocols and Compressing Collisions
Omer Paneth, MIT
Date: Tuesday, November 07, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Location: Patil/Kiva G449
Event Type: Seminar
Host: Vinod Vaikuntanathan
Contact: Deborah Goodwin, 617.324.7303, firstname.lastname@example.org
TALK: 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.
Created by Deborah Goodwin at Tuesday, October 31, 2017 at 11:22 AM.