1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "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$ $\endgroup$
    – poncho
    Commented Feb 9, 2023 at 9:32
  • $\begingroup$ 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? $\endgroup$ Commented Feb 9, 2023 at 9:48

1 Answer 1

0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Commented Feb 9, 2023 at 10:52
  • $\begingroup$ @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) $\endgroup$
    – poncho
    Commented Feb 9, 2023 at 10:58
  • $\begingroup$ Thanks a lot! Have a nice day!! $\endgroup$ Commented Feb 9, 2023 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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