[talks] D Xiao preFPO

[Melissa Lawson]

David Xiao will present his preFPO on Friday November 21 at 1PM in Room 402.
The members of his committee are; Boaz Barak, advisor; Avi Wigderson (IAS) and 
Russell Impagliazzo (IAS), readers; Sanjeev Arora and Rob Schapire, non-readers. 
Everyone is invited to attend his talk.  His abstract follows below.

New Connections Between Cryptography and Learning

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.

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.

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.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20081114/218fb781/attachment.html>