In a world of increasing threats from monopolies and oligarchies, people are increasingly looking for ways to protect their privacy. Isolating oneself from the world may be tempting, but there is a collective benefit to the processing of sensitive data. For example, hospitals use patient data to improve treatments, energy companies use power consumption data to predict grid usage, and governments can address inequality only if they measure it.

Privacy-enhancing technologies promise to close the apparent gap between privacy and utility. They provide a cryptographic solution by which statistics can be calculated without exposing individual inputs. In the world envisioned here, people gain the benefits of sharing data without exposing themselves to potential abuse.

Though solutions to societal problems are rarely if ever purely technical, this dissertation is concerned only with the technical. Specifically, with privacy-preserving summation, a protocol allowing users to learn the sum of their inputs without anyone learning the individual value of anyone else. While it may sound restrictive to focus only on summation, this is sufficient to achieve complex operations including principal component analysis, singular-value decomposition, and decision tree classifications.

In this dissertation, I provide novel methods for enforcing input and output validity in privacy-preserving summation, describe how running multiple summations in parallel leads to reconstruction attacks, and propose and evaluate countermeasures based on distributed short-cycle removal.

Validation of inputs and outputs is enforced through extensions, which can be added to any privacy-preserving summation scheme without sacrificing confidentiality. The first extension ensures that the individual pieces of data being summed over each fall within a specified numeric range. The second extension allows others to ensure that the sum published by the aggregator actually corresponds to the inputs.

Reconstruction attacks are an inherent risk when multiple summations run in sequence, regardless of the implementation of the summation protocol. When users obtain the sum A + B, one cannot learn either A or B due to the summation's privacy-preserving guarantees. However, if users subsequently also learn A + B + C, then anyone can infer C from the difference of the sums.

Understanding how and when reconstruction is possible is not trivial, especially as the numbers of variables and equations grows large. In this dissertation, I show that representing summations as a graph reveals that reconstruction coincides with the graph's cycles. In other words, removing cycles prevents reconstruction attacks. Therefore, I propose a decentralised protocol for removing short cycles. Finally, I evaluate the impact that restricting valid summation has on distributed averaging, and find that though the effect is largely negative, this can mostly be ameliorated through a subsequent greedy repair algorithm. ... Read more

The performance of distributed averaging depends heavily on the underlying topology. In various fields, including compressed sensing, multi-party computation, and abstract graph theory, graphs may be expected to be free of short cycles, i.e. to have high girth. Though extensive analyses and heuristics exist for optimising the performance of distributed averaging in general networks, these studies do not consider girth. As such, it is not clear what happens to convergence time when a graph is stretched to a higher girth.

In this work, we introduce the optimal graph stretching problem, wherein we are interested in finding the set of edges for a particular graph that ensures optimal convergence time under constraint of a minimal girth. We compare various methods for choosing which edges to remove, and use various convergence heuristics to speed up the searching process. We generate many graphs with varying parameters, stretch and optimise them, and measure the duration of distributed averaging. We find that stretching by itself significantly increases convergence time. This decrease can be counteracted with a subsequent repair phase, guided by a convergence time heuristic. Existing heuristics are capable, but may be suboptimal. ... Read more

Decentralised learning has recently gained traction as an alternative to federated learning in which both data and coordination are distributed over its users. To preserve the confidentiality of users' data, decentralised learning relies on differential privacy, multi-party computation, or a combination thereof. However, running multiple privacy-preserving summations in sequence may allow adversaries to perform reconstruction attacks. Unfortunately, current reconstruction countermeasures either cannot trivially be adapted to the distributed setting, or add excessive amounts of noise.

In this work, we first show that passive honest-but-curious adversaries can infer other users' private data after several privacy-preserving summations. For example, in subgraphs with 18 users, we show that only three passive honest-but-curious adversaries succeed at reconstructing private data 11.0% of the time, requiring an average of 8.8 summations per adversary. The success rate depends only on the adversaries' direct neighbourhood, and is independent of the size of the full network. We consider weak adversaries that do not control the graph topology, cannot exploit the inner workings of the summation protocol, and do not have auxiliary knowledge; and show that these adversaries can still infer private data.

We develop a mathematical understanding of how reconstruction relates to topology and propose the first topology-based decentralised defence against reconstruction attacks. Specifically, we show that reconstruction requires a number of adversaries linear in the length of the network's shortest cycle. Consequently, exact reconstruction attacks over privacy-preserving summations are impossible in acyclic networks.

Our work is a stepping stone for a formal theory of topology-based decentralised reconstruction defences. Such a theory would generalise our countermeasure beyond summation, define confidentiality in terms of entropy, and describe the interactions with (topology-aware) differential privacy. ... Read more

We consider the problem of publicly verifiable privacy-preserving data aggregation in the presence of a malicious aggregator colluding with malicious users. State-of-the-art solutions either split the aggregator into two parties under the assumption that they do not collude, or require many rounds of interactivity and have non-constant verification time. In this work, we propose mPVAS, the first publicly verifiable privacy-preserving data aggregation protocol that allows arbitrary collusion, without relying on trusted third parties during execution, where verification runs in constant time. We also show three extensions to mPVAS: mPVAS+, for improved communication complexity, mPVAS-IV, for the identification of malicious users, and mPVAS-UD, for graceful handling of reduced user availability without the need to redo the setup. We show that our schemes achieve the desired confidentiality, integrity, and authenticity. Finally, through both theoretical and experimental evaluations, we show that our schemes are feasible for real-world applications. ... Read more

Privacy-preserving data aggregation protocols have been researched widely, but usually cannot guarantee correctness of the aggregate if users are malicious. These protocols can be extended with zero-knowledge proofs and commitments to work in the malicious model, but this incurs a significant computational cost on the end users, making adoption of these protocols less likely.

We propose a privacy-preserving data aggregation protocol for calculating the sum of user inputs. Our protocol gives the aggregator confidence that all inputs are within a desired range. Instead of zero-knowledge proofs, our protocol relies on a probabilistic hypergraph-based detection algorithm with which the aggregator can quickly pinpoint malicious users. Furthermore, our protocol is robust to user dropouts and, apart from the setup phase, it is non-interactive. ... Read more