[Busec] [busec] Omer Paneth (Wed 9.45am)

Sharon Goldberg goldbe at cs.bu.edu
Mon Feb 29 09:51:59 EST 2016


***The Tuesday seminar with Alberto Dianotti from CAIDA has been CANCELLED
due to speaker illness.****

Hi everyone,

Join us for the BUsec seminar on Wednesday at 9:45am. Our own Omer Paneth
will present his PhD proposal on the cryptographic hardness of finding Nash
Equilibria.   Followed by lunch in the lab.

After this week, we'll take a few weeks off, and then come back on March 23
with a series of exciting network security talks from Cristina Nita-Rotaru
(NEU), Zakir Durumeric (UMich), Matt Green (JHU) and Bryan Ford (EPFL).

- Sharon

BUsec Calendar:  http://www.bu.edu/cs/busec/
BUsec Mailing list: http://cs-mailman.bu.edu/mailman/listinfo/busec

The busec seminar gratefully acknowledges the support of BU's Center for
Reliable Information Systems and Cyber Security (RISCS).

******
Title: On the Cryptographic Hardness of Finding a Nash Equilibrium
[Thesis Proposal]
Speaker: Omer Paneth (BU)
Room: MCS148 at 111 Cummington St, Boston MA 02215
Time: Wednesday March 2, 2015, 9:45AM


We prove that finding a Nash equilibrium of a game is hard, assuming the
existence of indistinguishability obfuscation and injective one-way
functions with sub-exponential hardness. We do so by showing how these
cryptographic primitives give rise to a hard computational problem that
lies in the complexity class PPAD, for which finding Nash equilibrium is
known to be complete.

Previous proposals for basing PPAD-hardness on program obfuscation
considered a strong "virtual black-box" notion that is subject to severe
limitations and is unlikely to be realizable for the programs in question.
In contrast, for indistinguishability obfuscation no such limitations are
known, and recently, several candidate constructions of
indistinguishability obfuscation were suggested based on different hardness
assumptions on multilinear maps.

Our result provides further evidence of the intractability of finding a
Nash equilibrium, one that is extrinsic to the evidence presented so far.

Joint work with Nir Bitansky and Alon Rosen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20160229/80df9f96/attachment.html>


More information about the Busec mailing list