To prove a protocol is secure in semi-honest model, we have to prove: the view o

Question

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.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.