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.