1
$\begingroup$

Most of general purpose multi-party computation protocols are highly interactive. Especially the ones with Shamir's secret scheme, as there is a degree reduction step in multiplication that needs the parties to interact with each other.

For example, say a client (trusted dealer) distributes the secret among several servers via secure channels, and the client also provides inputs to all the servers needed for secure function evaluation. Now the servers should evaluate a function on their own, they cannot talk to each other. At the end, the client receives all the partial results from different servers (via secure channels) and constructs the complete result locally.

There are non-interactive and robust threshold decryption protocols of RSA which are specialized multi party protocols. But are there any general-purpose non-interactive multi-party computation protocols? Or is it an open problem ?

Improve this question
$\endgroup$
12
  • $\begingroup$ What exactly do you mean by "non-interactive"? Obviously there will have to be some interaction. $\endgroup$
    – mikeazo
    Sep 9 '13 at 13:20
  • $\begingroup$ non-interactive means, the parties don't interact with each other. only the dealer gets all the partial results and collates them . if we use Shamir's scheme , the parties would need to interact for degree reduction while multiplication, for addition they need not ofcourse . $\endgroup$
    – sashank
    Sep 9 '13 at 14:32
  • $\begingroup$ Who is the dealer in an MPC protocol? $\endgroup$
    – mikeazo
    Sep 9 '13 at 17:01
  • $\begingroup$ the dealer is who distributed the shares to each server , say a client distributes the shares among servers , once the protocol of function evaluation is over, all the partial results are collated by client . in a non-interactive protocol servers should not talk to each other $\endgroup$
    – sashank
    Sep 9 '13 at 23:21
  • $\begingroup$ "the dealer is who distributed" what shares to each server? $\:$ You allude to secret sharing in your first paragraph and your tags and your comments, but neither of your questions mention it. $\:$ Is it the case that the dealer is still trusted after having dealt and that the parties have a confidential channel to that dealer? $\endgroup$
    – user991
    Sep 9 '13 at 23:38
5
$\begingroup$

It depends on what you mean by interaction.

Some protocols for secure multiparty computation, e.g. those based on Shamir secret sharings and the GMW protocol, require the servers to communicate a lot during the computation.

In other protocols, such as those based on Yao's garbled circuits (e.g. Fairplay MP), the interaction between servers is reduced in that the servers only need to communicate during a constant number of rounds, that is, a number of rounds that is independent of the size of the function they compute. But still, a lot of data traffic between the servers are needed during these rounds.

Some work has been done to further reduce the interaction required by secure multiparty computation. See for example this paper: Secure Computation on the Web: Computing without Simultaneous Interaction. This is in some sense non-interactive secure multiparty computation, but unfortunately the paper shows that it only works for a limited class of functions.

Improve this answer
$\endgroup$

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.