<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.6000.16735" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=668403920-14112008><FONT face=Arial
color=#0000ff size=2>David Xiao will present his preFPO on Friday November 21 at
1PM in Room 402.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=668403920-14112008><FONT face=Arial
color=#0000ff size=2>The members of his committee are; Boaz Barak, advisor; Avi
Wigderson (IAS) and </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=668403920-14112008><FONT face=Arial
color=#0000ff size=2>Russell Impagliazzo (IAS), readers; Sanjeev Arora and Rob
Schapire, non-readers. </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=668403920-14112008><FONT face=Arial
color=#0000ff size=2>Everyone is invited to attend his talk. His abstract
follows below.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><FONT face=Arial color=#0000ff size=2></FONT><BR>New
Connections Between Cryptography and Learning<BR><BR>Cryptography and learning
are intuitively inverse tasks: the first deals with obscuring information while
the second aims to extract hidden information. Not surprisingly, many
relationships were discovered early on between the two: a secure encryption
system implies that learning how to decipher encrypted messages is hard, while
on the other hand extremely powerful learning algorithms can potentially be used
to break the security of cryptographic protocols.<BR><BR>In this thesis, we
deepen the understanding of the relationship between the complexity of these two
tasks and use their relationship to inform the design of secure cryptographic
protocols. In our first set of results, we investigate under what
assumptions learning can be proven to be hard for polynomial-time
algorithms. First we show that the assumption ZK != BPP (and in particular
the worst-case hardness of problems such as Graph Isomorphism and Quadratic
Residuosity) suffices to imply that learning is hard. We then show that on
the other hand the weaker assumption P != NP is unlikely to imply that learning
is hard via standard proof techniques.<BR><BR>In our second result, we study
secure fault localization in Internet routing. In this problem, a sending
router and a receiving router wish to discover if there are any adversaries
along the path between them causing faults, i.e. that are dropping or modifying
packets. We build a formal model of security for this problem and show
that in order to achieve security, the intermediate routers must share keys and
perform cryptographic operations. This suggests that this security goal
inherently requires expensive computation at all nodes in the network, not just
the sender and receiver. Our result follows from applying a specific
learning algorithm to breaking protocols that do not satisfy the requirements of
keys and/or cryptographic operations at each intermediate
router.<BR></DIV><BR></BODY></HTML>