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

Speaker: 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

Public: Yes

Location: Patil/Kiva G449

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL:

Speaker Photo:

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin at Tuesday, October 31, 2017 at 11:22 AM.