Topology-Hiding Computation for Networks with Unknown Delays

Rio LaVigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, and Daniel Tschudi

(Accepted at PKC 2020, June 1 – 4)

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. 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.

On the attached paper the authors 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 authors 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.

To get the full version of this scientific paper, click here.

Join Concordium in our different channels:

Twitter: https://twitter.com/ConcordiumNet

Telegram: https://t.me/concordium_official

Reddit: https://www.reddit.com/r/Concordium_Official

Developers Hub: https://development.concordium.com/tech

Gitter: https://gitter.im/concordium_official/community

Discord: https://discord.gg/xWmQ5tp

Learn more: https://concordium.com