Privacy Laws, GDPR and impact on Topology Hiding Computation

[ataraxiaceleste]

In the wake of GDPR and other privacy laws, companies need ways to process data in a way such that the trust is distributed among several parties. This is super important for preservation of privacy as well as being compliant with the laws.

Topology-Hiding Computation (THC) allows a set of parties to securely compute a function over an incomplete network without revealing information on the network topology. Since its introduction in TCC’15 by Moran et al., the research on THC has focused on reducing the communication complexity, allowing larger graph classes, and tolerating stronger corruption types.

All of these results consider a fully synchronous model with a known upper bound on the maximal delay of all communication channels.

Unfortunately, in any realistic setting this bound has to be extremely large, which makes all fully synchronous protocols inefficient. In the literature on multi- party computation, this is solved by considering the fully asynchronous model.

However, THC is unachievable in this model (and even hard to define), leaving even the definition of a meaningful model as an open problem.

Researchers from Concordium, MIT, IDC Herzilya and ETH Zurich introduce a meaningful model of unknown and random communication delays for which THC is both definable and achievable.

The probability distributions of the delays can be arbitrary for each channel, but one needs to make the (necessary) assumption that the delays are independent.

The existing fully-synchronous THC protocols do not work in this setting and would, in particular, leak information about the topology.

Second, in the model with trusted stateless hardware boxes introduced at Eurocrypt’18 by Ball et al., the researchers present a THC protocol that works for any graph class.

Third, they explore what is achievable in the standard model without trusted hardware and present a THC protocol for specific graph types (cycles and trees) secure under the DDH assumption.

The speed of all protocols scales with the actual (unknown) delay times, in contrast to all previously known THC protocols whose speed is determined by the assumed upper bound on the network delay.

A fundamental solution to this problem is to introduce a meaningful model to secure multiparty computation.