1
$\begingroup$

To prove a protocol is secure in semi-honest model, we have to prove: the view of each party, on each possible pair of inputs, can be efficiently simulated based solely on its own input and and output.

So let's consider this example, Alice holds $x$ and Bob holds $y$, they wants to compute $f(x, y)$ without revealing their inputs. I constructs a protocol which is insecure: Bob simply sends $y$ to Alice, and Alice outputs $f(x,y)$.

But it seems it can be proved according to the definition of semi-honext model. Let's assume Bob is honest, we construct a simulator for Alice. The simulator feeds Bob with a random $y'$, Alice cannot distinguish $y$ and $y'$. So Alice's view can be simulatable. But the protocol is of course not secure.

$\endgroup$
  • $\begingroup$ "about the proof in semi-honest model" is not a question. $\:$ Do you mean "What is wrong with my proof about a protocol in the semi-honest model?"? $\;\;\;\;$ $\endgroup$ – user991 Dec 4 '14 at 9:23
  • $\begingroup$ I have modified the question. $\endgroup$ – Jan Leo Dec 4 '14 at 9:33
  • $\begingroup$ Proving that "parties' views are simulatable" is enough in the semi-honest model because Alice can distinguish $y$ from $y'$. $\;$ $\endgroup$ – user991 Dec 4 '14 at 9:49
  • $\begingroup$ Why? Alice doesn't know the value of $y$. $\endgroup$ – Jan Leo Dec 4 '14 at 9:59
  • $\begingroup$ honest-Alice "doesn't know the value of $y$", but adversary-Alice chooses the value of $y$. $\hspace{1.11 in}$ $\endgroup$ – user991 Dec 4 '14 at 10:02
1
$\begingroup$

I am having a hard time understanding your argument why you think this could be simulated. However, here is an explanation of why it could not.

Assume Bob is honest and has input $y$, now we have to simulate the view of Alice. As the simulator, as you state, we only get the input and output of Alice. I.e, we only know $x$ and $f(x,y)$. We only need to simulate the one message in Alices view, i.e., the first message where Bob sends $y$ to Alice. Since we do not know $y$ the best we can do is to randomly guess at some $y'$. Now the probability that $y' \neq y$ is going to be high, so the simulation is going to be clearly distinguishable from the view of Alice.

What might be confusing you is that, when we do the simulation we do not know the inputs of the honest parties. But when we try to distinguish the real view from the simulation we know all the inputs.

$\endgroup$
  • $\begingroup$ What if $y$ is a random bit selected by Bob. Then the simulator randomly selects a value $y'$. So Alice's real view is $(x, y, f(x,y))$ and her simulated view is $(x, y', f(x,y')$. They are indistinguishable to Alice. $\endgroup$ – Jan Leo Dec 4 '14 at 12:03
  • $\begingroup$ The distinguisher knows all the inputs and the outputs of the honest parties. As you phrased the problem above it seems Bob does not have an output. If you let $x$ be picked at random by the functionality then Bob also has no input. In that case, yes the protocol is secure. The simulator just picks a random $y'$ and sends it to Alice and Alice outputs $f(x, y')$. It would be different if Bob is also supposed to output $f(x,y)$. In that case the simulator would have to sample a $y'$ so that $f(x,y) = f(x, y')$. $\endgroup$ – Guut Boy Dec 4 '14 at 13:05
  • $\begingroup$ But the protocol is certainly insecure. The requirement is Alice cannot see the value of $y$. $\endgroup$ – Jan Leo Dec 4 '14 at 13:38
  • $\begingroup$ It is a little hard to say, because you have not explicitly defined your ideal functionality. But if the functionality is: Take input $x$ from Alice, pick random $y$ and output $f(x,y)$ to Alice (which seems to be what you are implying). Then the protocol is trivially secure, in fact Alice could just pick $y$ randomly herself, Bob does no longer need to be involved. $\endgroup$ – Guut Boy Dec 4 '14 at 13:47
  • 1
    $\begingroup$ On the other hand if the random bit $y$ is an input to Bob. Then the distinguisher knows this bit, and since the simulator does not, the simulated and real views can be easily distinguished (as discussed in the answer). $\endgroup$ – Guut Boy Dec 4 '14 at 13:49

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.