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?

  • $\begingroup$ Even if you can't connect every node directly over the network, can't some nodes relay the protocol messages for the others? I believe there's a few MPC systems enabling asymmetric loads (offloading CPU work, etc), but I'm not sure if this applies to network traffic $\endgroup$
    – Natanael
    Jun 23 '19 at 19:16
  • $\begingroup$ In my model the parties are rational agents, they don't pass reliable information if it is not in their interest (measured by their utilities). I think, but absolutely not sure, that there are graphs where it's not obvious why agents will follow the protocol (at least without cryptographic assumptions (as signatures)). $\endgroup$
    – sosolo
    Jun 24 '19 at 7:29
  • $\begingroup$ This is a shameless plug, I suppose, but some work I did definitely has relevance to the situation that you are interested in. A game theoretic modeling of this scenario would be really interesting. If you are interested in collaborating, let me know. $\endgroup$
    – mikeazo
    Jun 24 '19 at 14:20

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.