Score:1

Question about Secure Multi-Party Computation

ro flag

I am doing research about Non-interactive Secure Multi-party Computation and encounter a dilemma that I am not quite sure if it is possible and wonder if there are better thoughts that could help.

Situation:

There are $n$ parties ($i \in [n]$) and a dealer. The dealer has a number $U$ and weights $w_i (i \in [n])$ and parties have their inputs $x_i$. Now the parties would like to calculate $U - \sum_{i \in [n]} w_i x_i$ under the limitation:

  1. only the parties know $x_i$
  2. only the dealer knows $w_i$
  3. only the dealer can send messages to parties but parties cannot send messages to the dealer.

I've been thinking of ways like FHE or Secret sharing that seem fine but actually are not.

  • Is there any other way that might work or any consideration that might help?
  • Or is there any way that we can prove that it is impossible to realize a protocol for this situation?

Edited:

As @poncho mentioned in the comment, it seems impossible if the parties cannot send messages to anybody. So I'd like to change the situation a little bit (an Evaluator is added) and hope there might be other thoughts:

Situation:

There are $n$ parties ($i \in [n]$), a dealer, and an evaluator. Dealers have a number $U$ and weights $w_i (i \in [n])$ and parties have their inputs $x_i$. Now the evaluator would like to calculate $U - \sum_{i \in [n]} w_i x_i$ under the limitation:

  1. only the parties know $x_i$
  2. only the dealer knows $w_i$
  3. Dealer can send messages to parties and evaluator. (single way)
  4. Parties can send messages to the evaluator (single way).
  5. The evaluator and parties may collude.

Under the new situation, is there any way that might be a helper under a fully robust secure model?

Great thanks to everyone that stops and takes a look.

poncho avatar
my flag
"parties cannot send message to the dealer"; who can the parties send messages to? If they literally cannot send messages to anybody, I don't see how this is a solvable problem if $n>1$
qingqingthe avatar
ro flag
To @poncho, yes, the parties cannot send messages to anyone. Well, thank you for the comment and I try to edit the situation (an Evaluator is added). Could you give any more thoughts on the new situation?
Score:0
my flag

is there any way that might be helper under fully robust secure model?

I do not believe so. By rule 5, the parties and the evaluator may collude, and hence we can treat them as a single party.

So, the situation becomes: Alice (the dealer in your scenario) has a secret X, Bob (the parties and the evaluator) has a secret Y; Alice sends a message M (or series of messages; since Bob does not respond, there is no real distinction) to Bob, and Bob computes F(X, Y).

Here's the problem with this situation: Bob can select a different secret Y', logically replay the message M, and then compute F(X, Y'), for as many values of Y' has Bob likes.

And, with the specific F you have in mind, a series of different Y' values will easily allow Bob to reconstruct the value $U$ and all the $w_i$ weights.

So, to make this a solvable problem, it sounds like you'll need to change the scenario somehow...

qingqingthe avatar
ro flag
Great thanks! What if the value $U$ can be known by Alice and Bob (or anyone), will the answer change? If not, to formally prove it is impossible under this situation, is it enough to demonstrate that under the abstracted situation you mentioned here, by replaying messages, the weights $w_i$ could be easily reconstructed?
poncho avatar
my flag
@qingqingthe: I believe it would be sufficient; it would give an attack method that would work against any method of implementing the MPC (given the limitations as stated)
qingqingthe avatar
ro flag
Thanks a lot! Have a nice day!!
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.