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.

In this paper at the bottom of pg. 1235 and beginning of pg. 1236 it says:

An MPC protocol is said to be secure, if for every real world leakage adversary A there exists an ideal world simulator S, such that the output of all the parties (including the adversary) in the real world, is computationally indistinguishable from the output of all the parties (including the simulator) in the ideal world.

Why do the outputs have to be indistinguishable? Why not the inputs? The paper talks about a "secret state". Is the secrete state different from input/output ?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Suppose you have a black box with some buttons and some lights. When you push the buttons, the lights go on and off. You wonder what's inside, but you cannot open the box. The only way to figure out what's inside is by pushing buttons and observing the lights.

Now suppose you have two black boxes. You wonder if they are the same on the inside. Again, you cannot open the boxes, so you cannot decide by inspection. You are reduced to pushing buttons, observing lights and comparing. If a sequence of button pushes usually causes a light on one box to turn on, while the corresponding light on the other box usually stays off, you know the insides are different (probably).

Note that if you have two exactly identical black boxes and push the buttons in exactly the same way on both boxes, their lights may still behave differently. That's because inside the box, there is a source of randomness, and each box may produce different randomness.

Now suppose the insides of the black boxes really are different, but if you press the buttons in the same way, the lights always seem to go on and off in the same fashion. For you, the black boxes are effectively identical, because you now have no way of distinguishing one box from another.

If you push different buttons on the two black boxes, they will probably respond in different ways. But that doesn't allow you to distinguish them.

That was easy. The tricky part is the interpretation.

Protocol input and adversarial tampering correspond to button pushing. Flashing lights correspond to protocol output and whatever the adversary can observe during protocol runs.

On the inside of the first black box, we have the real protocol's honest users and whatever infrastructure they use.

In the second box, we have two things. One thing (often called the ideal functionality) gathers up the honest users' inputs and computes the outputs in the required way. The second thing (the simulator) gets certain information about the inputs and outputs (the specified allowed leakage) from the first thing. It simulates observations for the adversary to enjoy.

Now we observe two things about the second box:

  • It will always do the computation correctly.
  • The adversarial observations are computed using only the allowed leakage, so nothing more than the allowed leakage will leak.

If the first box cannot be distinguished from the second box, it follows logically that this must also apply to the first box. Which means that we have established that our protocol is secure.

share|improve this answer
    
if I understand your example correctly you are saying the buttons are the inputs and the lights are the outputs. You are basically saying the adversary controls the inputs of both black boxes (one of them is ideal black box and the other is real black box). So when the adversary pushes buttons and messes with the inputs he/she still can't tell the differences between real and ideal black box. Thus they won't be able to crack the code and get to the secret state inside the black box? –  user1068636 Nov 15 '13 at 4:30
    
I've updated the answer. Note that in the literature, you will find many variations on this general idea. –  K.G. Nov 15 '13 at 9:31

I think your first question is answered by K.G., so I'll tackle the other two

Why not the inputs? The paper talks about a "secret state". Is the secret state different from input/output?

Often the inputs of the corrupted parties assumed to be known, but not those of the honest parties.

As far as the secret state, a quote from the abstract might help:

We construct a multiparty computation (MPC) protocol that is secure even if a malicious adversary...can leak information about the secret state of each honest party.

So there is some secret state for each honest party. What exactly is included in that secret state is probably application specific, though probably includes the honest parties' inputs and portions of either the garbled circuit, intermediate values, secret shares, etc.

share|improve this answer
    
So I think what I"m hearing you and K.G. say is as long as the outputs are indistinguishable in the real/ideal worlds then their MPC protocol is secure with continual leakage on the secret state. And you're saying the secret state may or may not contain the inputs - but it's irrelevant. –  user1068636 Nov 15 '13 at 4:36
    
Likely the secret state of each party includes that party's input. –  mikeazo Nov 15 '13 at 13:22
    
The reason indistinuguishibility implies security is that the ideal world is secure by definition. –  mikeazo Nov 15 '13 at 13:22
    
I'd say that the description of the ideal world often is our security definition. But not always. –  K.G. Nov 17 '13 at 10:21

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.