Can Simultaneous Disclosure Ensure Equal Output in Joint Computation?

[Dragonfall]

What is the name of the protocol that let's two parties to simultaneously get an output of a joint computation (within epsilon of certainty of each other)? That is, they don't simultaneously get it, each party gets a little bit at a time, but no party gets more than a fraction of a bit more than the other?

 

[justsomeguy]

Is this a quantum computing question? I know of similar schemes in cryptography but there is nothing quite like what you describe that I can remember.

 

[Dragonfall]

No it's entirely classical. I remember learning about it but I don't know what it's called.

One special case of this is that two parties supposedly have the same string S. They want to show each other than they have the same one, but not disclose more than necessary if the other party is cheating. They could disclose one bit at a time, but that gives one party an advantage of 1 bit. It's possible to reduce that to epsilon bit, but I don't remember how.

 

[justsomeguy]

OH.. that's different. Proving you know something is different from calculating it! That's called a zero-knowledge proof.

 

[Dragonfall]

No it's not zero knowledge. I found it here http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4568055&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D4568055

But I can't access. Does anyone have a copy of that article?

 

[justsomeguy]

In the applied crypto book (2nd ed, p90) there's a public key scheme for fairly flipping a coin without either party being able to cheat, but one party will know the outcome before the other. Is that part terribly important to your goal?

There are a few others but they all generalize to the same thing; e.g. diffie-hellman key exchange. I have to imagine that the IEEE paper relates to one of these (or was proven weak) considering the relative age of the paper vs. available crypto materials like AC.

 

[chiro]

Hey DragonFall.

Have you considered looking for resources on group signatures?

It sounds like a situation where you could construct an error correcting code for the function and combine it with cryptography to tell if someone has cheated or is telling the truth.

 

[Dragonfall]

I need it to not be based on any complexity assumptions. There was a negative result by somebody which may have said that what I want is impossible, but I can't find it.

 

[chiro]

If you find it can you please let me know as well: I'm very interested in this result if you do happen to get it.

 

[justsomeguy]

I am interested as well. I'm not aware of any methods that can be used right now in a practical sense that require full disclosure by both parties before either can know the results. At some point, either (or both) parties will be in need of only one more piece of data (otherwise there is no point at which more data does not need to be sent) to determine the coin toss, and at that point, there does not seem to be a way of preventing one party from sending early (same as the other side withholding).

 

[Dragonfall]

http://vvv.cs.ut.ee/~swen/courses/crypto-ii/2008/cleve1986.pdf

Bam, there it is

 

[justsomeguy]

Thanks, reading! Will be back.

 

[justsomeguy]

Well, the paper is interesting (and short! That's rare in crypto.) but doesn't sound like quite what you asked for. How do you propose to use this to share a piece of information of arbitrary length without one potentially getting a 1 bit advantage in knowledge?

There's always the opportunity for one to cheat and not reveal in the final round, e.g. in round 2 of the 2 round example diagram on page 2. There is nothing compelling B to send information to A in step B2 before calculating b.

 

[chiro]

Many thanks Dragonfall.

 

[Dragonfall]

Yes, the paper says what I ask for is impossible without additional assumptions. The trick is to make it so that you have a random variable that's slightly skewed towards the bit that it actually reflects. Then each round you sample the RV, increasing your confidence. If that's small enough then each party only has negligible advantage.