Troubleshooting network outages is a complex and time-consuming process. Network administrators are typically overwhelmed with large volumes of monitoring data, like SMTP and NetFlow measurements, from which it is very hard to separate between actionable and non-actionable events. In addition, they can only debug network problems using very basic tools, like ping and traceroute. In this context, intelligent correlation of measurements from different Internet locations is essential for analyzing the root cause of outages. However, correlating measurements across domains raises privacy concerns and hence is largely avoided. A possible solution to the privacy barrier is secure multi-party computation (MPC), that is, a set of cryptographic methods that enable a number of parties to aggregate private data without revealing sensitive information. In this article, we propose a distributed mechanism based on MPC for privacy-preserving correlation of NetFlow measurements from multiple ISPs, which helps in the diagnosis of network outages. We first outline an MPC protocol that can be used to analyze the scope (local, global, or semi-global) and severity of network outages across multiple ISPs. Then we use NetFlow data from a medium-sized ISP to evaluate the performance of our protocol. Our findings indicate that correlating data from several dozens of ISPs is feasible in near real time, with a delay of just a few seconds. This demonstrates the scalability and potential for real-world deployment of MPC-based schemes. Finally, as a case study we demonstrate how our scheme helped analyze, from multiple domains, the impact that Hurricane Sandy had on Internet connectivity in terms of scope and severity.