MPC and Secret Sharing in not Fully-Connected Network

Question

I have an interest in applications of MPC and Secret Sharing. My point of view is from fields of distributed computing and Game Theory.

I want to generalize some results to arbitrary network topologies. I couldn't find any results on MPC in not fully-connected networks.

Is anyone familiar with such works?

Answer 1

Secure computation over incomplete networks has been the subject of several works in the past. However, as far as I am aware of, none of these works uses the model of rational cryptography, where the agents are modeled in a game-theoretic way as rational players rather than computationally-bounded machines.

The most classical setting of secure computation considers security with aborts (adversaries may prevent the completion of the protocol, but they cannot compromise security or correctness of the computation), with computational security guarantees. In this setting, it is relatively easy to see that secure computation over an incomplete but strongly connected network can be reduced to secure computation over a complete point-to-point network. Indeed, assuming for simplicity that a public-key setup has been made, each party will simply compile the complete point-to-point MPC protocol as follows: each time a party $A$ must sends a message $m$ to a party $B$, she encrypts $m$ with the public key of $B$, signs it to guarantee integrity and authenticity, and sends the message to all parties she is connected to. Each time $A$ receives a message for which she is not the target receiver, she broadcasts it back to the parties she is connected to (unless she already broadcasted this message in the past, of course). This guarantees that, unless a cheating party prevents a message from passing (which is equivalent to aborting and preventing completion of the protocol), the correct message will eventually securely reach it's target receiver, hence one can implement an arbitrary MPC protocol this way. The same strategy can be used to execute a key exchange over an incomplete network, removing the need for a public key infrastructure in the first place (but one must still be able to authenticate himself).

Now, there are many questions that the above naive solution does not address: can we get something more efficient? Especially, what if we are willing to assume a bit more than just "the network is strongly connected"? Much more efficient protocols are likely to exist on some more specific types of graphs. What if we want unconditional security (with honest majority)? What if we want to hide the topology of the network? What if we want fairness, or guaranteed output delivery? What if the structure of the graph is not fixed before the protocol, but determined dynamically?

Not all of these questions have been considered. What has been looked at in the literature includes (see also additional references in the linked papers):

• Information-theoretic secure computation with private and reliable channels in an incomplete network was addressed in this paper.
• The more specific case of secure aggregation over incomplete networks was addressed here.
• This very cool recent paper addresses the challenging case of secure computation over an incomplete and dynamic network (whose connectivity is determined dynamically). I also suggest, for more references on MPC over incomplete network, that you look at their introduction; page 1 contains a bunch of references.
• This recent paper provides further insights regarding the characterization of information-theoretic secure computation over incomplete networks.
• Eventually, there has been a lot of work on topology hiding computation, where the goal is to securely compute a function over an incomplete graph, while at the same time hiding the topology of the graph. See e.g. 1, 2, 3, 4 and references therein.