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.