4
$\begingroup$

Suppose this simple protocol with three parties: $X$ (with secret input $x$), $Y$ (with secret input $y$), and $Z$ (no input). Suppose that we are operating with elements from a finite field.

The goal is that after the execution of the protocol, $Z$ knows $x\cdot y$ but not $x$ nor $y$, and $X$ and $Y$ does not learn anything. This can be considered similar to output privacy in secure multiparty computation. It is clear why we need output privacy: if $X$ learns $x\cdot y$, he can compute $y$ (and viceversa).

An initial approach could be based in using blinding factors. $X$ gives $b\cdot x$ to $Y$ and $b$ to $Z$, for a randomly sampled $b$; next, $Y$ gives $(b\cdot x)\cdot y$ to $Z$; and finally, $Z$ removes $b$ to obtain $x\cdot y$. This solution assumes that all parties are honest.

Any other ideas or references on how to come up with better solutions? I'm sure that similar problems should have been already tackled by the SMC community.

$\endgroup$
  • $\begingroup$ This works with any multiplicative homomorphic encryption already. $Z$ generates a key (makes the public key known to the others), $X$ encrypts $x$ and sends it to Y, $Y$ encrypts $y$, uses the homomorphic property to get $enc(XY)$ and sends that to $Z$. $Z$ decrypts. $\endgroup$ – tylo Nov 10 '16 at 10:33
  • $\begingroup$ @tylo Interesting! Please add it as an answer so others can vote and comment :) $\endgroup$ – cygnusv Nov 10 '16 at 11:00
4
+50
$\begingroup$

First, I'll assume that parties' inputs come from a multiplicative group. If they're in a ring and you also want multiplication by zero, then things get harder. In that case, the protocol you describe is not secure even in the semi-honest case.

The protocol you describe is already secure in the malicious case. $X$ gives random $b$ to $Z$ and $bx$ to $Y$. $Y$ gives $(bx)y$ to $Z$, who computes $b^{-1}(bxy)$.

  • If $X$ is corrupt, he sends some $b$ to $Z$ and $c$ to $Y$. This achieves the same effect on the honest parties as running honestly with input $b^{-1} c$ in the ideal world, so it's simulatable / not an attack.

  • If $Y$ is corrupt, she gets $c = bx$ from $X$ and gives $d$ to $Z$. The message $c$ from $X$ is distributed uniformly, so this message is simulatable without knowing $X$'s input. Furthermore, $Y$'s behavior achieves the same effect on the honest parties as running honestly with input $d c^{-1}$, so it is simulatable / not an attack.

  • If $Z$ is corrupt, there's nothing he can do, since all he does is receive messages.

  • If $Z$ is corrupt and colludes with one of $\{X,Y\}$, then in the ideal world they can deduce the honest party's input in its entirety. So there is nothing to hide.

  • If $X$ and $Y$ collude, then $X$ sends $b$ to $Z$ and $Y$ sends $d$ to $Z$. This achieves the same effect on the honest party as them running honestly with inputs $1$ and $b^{-1} d$.

| improve this answer | |
$\endgroup$
2
$\begingroup$

Here is the link to recently published work for high throughput 3 party secure computation

The proposed protocol requires each party to transmit single bit for multiplication gate evaluation for boolean circuit.

For letting only Z know about the output, in the reconstruction phase each party send their share of output to Z, who can easily recompute the output.

For more details go through the entire paper.

| improve this answer | |
$\endgroup$
  • $\begingroup$ It seems that Section 2.3 is relevant, as it describes a multiplication gate for field elements. However, the input elements are given to the three parties with a secret sharing....I guess this is done externally? Anyway, this is not the setting I describe (correct me if I'm wrong). $X$ and $Y$ have their own private inputs, and ideally no external entities should be required. $\endgroup$ – cygnusv Nov 10 '16 at 10:19
  • $\begingroup$ In the initial phase X and Y can play the role of dealer and secret share their input in the desired way. $\endgroup$ – Shishir Nov 10 '16 at 11:49
2
$\begingroup$

This works with any multiplicative homomorphic encryption already, for example ElGamal encryption:

  • $Z$ generates a key, and sends the public key to the others
  • $X$ encrypts $x$ and sends it to $Y$
  • $Y$ encrypts $y$, and then uses the homomorphic property to get $enc(xy)$. And then sends this to $Z$.
  • $Z$ decrypts

$Z$ does not get anythign except $enc(xy)$. And the others can't learn anything, if the encryption scheme is IND-CPA.

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