Register to reply

Simultaneous disclosure

by Dragonfall
Tags: disclosure, simultaneous
Share this thread:
Dragonfall
#1
Dec15-12, 05:21 PM
Dragonfall's Avatar
P: 993
What is the name of the protocol that lets 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?
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
justsomeguy
#2
Dec15-12, 05:25 PM
P: 166
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
#3
Dec15-12, 05:28 PM
Dragonfall's Avatar
P: 993
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
#4
Dec15-12, 05:29 PM
P: 166
Simultaneous disclosure

OH.. that's different. Proving you know something is different from calculating it! That's called a zero-knowledge proof.
Dragonfall
#5
Dec15-12, 07:21 PM
Dragonfall's Avatar
P: 993
No it's not zero knowledge. I found it here http://ieeexplore.ieee.org/xpl/login...mber%3D4568055

But I can't access. Does anyone have a copy of that article?
justsomeguy
#6
Dec15-12, 07:43 PM
P: 166
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
#7
Dec15-12, 07:47 PM
P: 4,573
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
#8
Dec15-12, 07:53 PM
Dragonfall's Avatar
P: 993
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
#9
Dec15-12, 08:04 PM
P: 4,573
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
#10
Dec15-12, 08:17 PM
P: 166
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
#11
Dec16-12, 08:28 PM
Dragonfall's Avatar
P: 993
http://vvv.cs.ut.ee/~swen/courses/cr.../cleve1986.pdf

Bam, there it is
justsomeguy
#12
Dec16-12, 08:28 PM
P: 166
Thanks, reading! Will be back.
justsomeguy
#13
Dec16-12, 08:48 PM
P: 166
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
#14
Dec16-12, 10:46 PM
P: 4,573
Many thanks Dragonfall.
Dragonfall
#15
Dec18-12, 04:37 AM
Dragonfall's Avatar
P: 993
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.


Register to reply

Related Discussions
Disclosure project General Discussion 150
E.T. Disclosure 2010 General Discussion 10
Disclosure agreement at Employers Academic Guidance 11
The disclosure project General Discussion 3
Disclosure Project Conference General Discussion 7