Moni Naor: White-box vs. Black-box Search Problems: A Cryptographic Perspective
Moni Naor, Weizmann Institute of Science
Date: Tuesday, March 21, 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
Host: Vinod Vaikuntanathan
Contact: Deborah Goodwin, 617.324.7303, firstname.lastname@example.org
Speaker URL: None
TALK: Moni Naor: White-box vs. Black-box Search Problems: A Cryptographic Perspective
Abstract: Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how di?cult is it to ?nd the clique or independent set? If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to ?gure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? What if we are assured that the program is small without being given explicitly?
In this talk I will explore recent work on the complexity of search problems with guaranteed solution (the class TFNP) and the tight relationship with cryptographic assumptions and techniques.
Based on joint works with Pavel Hubacek, Ilan Komargodski and Eylon Yogev
Created by Deborah Goodwin at Friday, March 10, 2017 at 3:00 PM.