Aaron Johnson, United States Naval Research Laboratory (NRL)

Abstract

Tor is a widely popular tool for online privacy. Despite its focus on privacy, Tor benefits from some transparency about the operation of its network. Measurements of Tor help direct its developers, inform its users, and guide policymakers. Existing approaches to making these measurements, including Tor’s current techniques, are limited in the types of measurements that can be made.

We present a system that uses secure multiparty computation protocols to give Tor full power to compute any function of its relays’ observations while keeping the observations themselves private. We show how it scales to Tor’s thousands of relays, tolerates network churn, and provides security depending only on Tor’s core trust assumptions.

We demonstrate how to use our system to compute two broadly-applicable statistics: the median of relay inputs and the cardinality of set union across relays. We implement our protocols and experimentally test their performance in networks like Tor using the Shadow simulator. Our experiment show that, when processing the inputs of 7,000 relays, the system can compute from 36 to 151 median computations per day and from 134 to 533 set union cardinalities per day, depending on the trust assumptions of the network. Thus, the system enables large numbers of complex analytics to be securely computed over the Tor network.