# Why is proving “parties' views are simulatable” enough in semi-honest model?

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.

• "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?"? $\;\;\;\;$ – user991 Dec 4 '14 at 9:23
• I have modified the question. – Jan Leo Dec 4 '14 at 9:33
• Proving that "parties' views are simulatable" is enough in the semi-honest model because Alice can distinguish $y$ from $y'$. $\;$ – user991 Dec 4 '14 at 9:49
• Why? Alice doesn't know the value of $y$. – Jan Leo Dec 4 '14 at 9:59
• honest-Alice "doesn't know the value of $y$", but adversary-Alice chooses the value of $y$. $\hspace{1.11 in}$ – user991 Dec 4 '14 at 10:02

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 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. – Jan Leo Dec 4 '14 at 12:03
• 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')$. – Guut Boy Dec 4 '14 at 13:05
• But the protocol is certainly insecure. The requirement is Alice cannot see the value of $y$. – Jan Leo Dec 4 '14 at 13:38
• 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. – Guut Boy Dec 4 '14 at 13:47
• 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). – Guut Boy Dec 4 '14 at 13:49