Network management in a world of secrets.

The Internet is by definition a network of networks. No-one operates, or controls more than a small slice of the overall Internet. A large number of network providers manage their own, independent networks, and these then interconnect to create the world-spanning artefact we call the Internet. These Internet Service Providers (ISPs) are highly heterogeneous – they vary widely in scale, technology, objective, and management policies. However, they have some general features in common, and in particular they all engage in some kind of network management. Network management consists of a variety of tasks and activities, including performance analysis, detection of network anomalies or fraud, traffic engineering, and capacity planning. Some of the activities we wish to conduct as part of these tasks are apparently not possible without co-operation. However, these companies also compete, and much of the information that they would need to share to co-operate is secret! For the last 40 years a field of cryptology has been growing, named Secure Multiparty Computation (SMC). It offers protocols for multiple parties to compute functions without revealing their respective inputs to each other. These techniques have come a long way from the earliest theoretical ideas, now offering practical solutions for wide-ranging problems including electronic voting, auctions, or data mining. Despite the maturity of this exciting work on SMC, there remains relatively little research in the context of network management. In this thesis, we apply concepts of SMC to problems within network management. Importantly, SMC techniques generate significant overheads because they use cryptographic primitives to enable secure computation. With this in mind, the first half of this thesis we attempt to improve the practicability of SMC. Specifically, we show a new implementation of Yao’s two-party secure function evaluation protocol with significantly better performance than previous implementations. Its low memory footprint enables the evaluation of bigger circuits with less memory. We then demonstrate a secure scaling protocol which enables two parties to convert real-numbered privacy-preserving problems into the integer domain by scaling, as almost all techniques for SMC support only integer inputs and operations. Our approach does not limit the choice of SMC techniques for the privacy-preserving problem, nor does it introduce additional overheads compared with previous solutions. The core of our protocol is a novel algorithm for privacy-preserving random number generation. In the second half of the thesis, we present two examples of how to apply SMC to network management. First we present a distance-vector routing protocol that allows routers to compute the shortest paths without learning the distances of any paths. Whereas previous solutions relied on trusted third parties for route computation, we maintain the distributed nature of a routing protocol. The basic components of the protocol can easily be extended to implement other types of path metrics. The second example is a protocol for privacy-preserving fraud detection. It enables telecommunication providers to co-operate in detecting subscription fraud without violating protection laws for phone records. We present several protocols for call-signature based subscription fraud detection with different levels of privacy, enabling providers to mine each others fraudster databases. In all cases we present implementations, and we use these to show that SMC-based protocols are practical and may be highly beneficial to network operators.Thesis (Ph.D.) -- University of Adelaide, School of Mathematical Sciences, 201