Graph-Based Reconstruction in Summation Sequences

Abstract

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.