[CSDM] Nir Bitansky's IAS talks tomorrow, Monday.

[Avi Wigderson]

Hi,

Due to the snow storm Tuesday,  Nir Bitansky will give both his Mon & 
Tue talks tomorrow, on Monday,
the first as usual at 11:15, and the 2nd, 2-hr talk at 2pm.

Here is the detailed information. Note again that the talks are in the 
West Building seminar room
(the afternoon talk may move if necessary.)

1  On the cryptographic hardness of finding a Nash equilibrium (Monday, 
11:15 - 12:15)
    Nir Bitansky

The computational complexity of finding Nash Equilibria in games has 
received much attention over the past two decades due to its theoretical 
and philosophical significance. This talk will be centered around the 
connection between this problem and cryptography. Mostly, I will discuss 
a result proving that finding Nash equilibrium is hard, assuming the 
existence of a cryptographic notion called indistinguishability 
obfuscation. This is done by demonstrating that this cryptographic 
notion gives rise to a hard computational problem in the complexity 
class PPAD, for which finding Nash equilibrium is known to be complete.

Indeed, in recent years indistinguishability obfuscation has turned out 
to have surprisingly strong implications in cryptography and beyond. I 
will give the high-level picture as to where we stand in our efforts of 
constructing such obfuscators and basing them on solid hardness 
assumptions. In a companion talk on Tuesday, I will discuss one specific 
line of work that reduces indistinguishability obfuscation to simple 
assumptions on 5-linear maps, coming closer to well-studied 
cryptographic objects such as bilinear-map groups.

The talk is based on joint work with Paneth and Rosen. No prior 
knowledge in cryptography is required.

http://www.math.ias.edu/seminars/abstract?event=104314



2  Indistinguishability obfuscation from 5-linear maps: a reduction from 
flying pigs to jumping pigs (Monday, 2-4 pm)
    Nir Bitansky

Indistinguishability obfuscation has turned out to be an outstanding 
notion with strong implications not only to cryptography, but also other 
areas such as complexity theory, and differential privacy. Nevertheless, 
our understanding of how to construct indistinguishability obfuscators 
is still at its infancy. The first candidates, suggested only several 
years ago, were based on quite complex assumptions on little-studied 
multilinear maps. Since then, and especially in light of various attacks 
on current multilinear maps, there has been an ongoing effort aimed at 
basing indistinguishability obfuscation on simpler building blocks and 
better-studied computational assumptions.

This talk will overview one such line of works. I will first describe a 
reduction from indistinguishability obfuscation to a simpler and 
longer-studied object called functional encryption. I will then describe 
the main ideas behind recent constructions of such functional encryption 
from simple assumptions on 5-linear-map groups, coming closer to 
well-studied cryptographic objects such as bilinear-map groups.

We will cover the relevant definitions and techniques, often focusing on 
simplified instances of the above transformations. I will not assume any 
prior knowledge in cryptography.

http://www.math.ias.edu/seminars/abstract?event=104574