Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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 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 at 13:05
    
But the protocol is certainly insecure. The requirement is Alice cannot see the value of $y$. –  Jan Leo Dec 4 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 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 at 13:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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