
#1
Dec1512, 05:21 PM

P: 994

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?




#2
Dec1512, 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.




#3
Dec1512, 05:28 PM

P: 994

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. 



#4
Dec1512, 05:29 PM

P: 166

Simultaneous disclosure
OH.. that's different. Proving you know something is different from calculating it! That's called a zeroknowledge proof.




#5
Dec1512, 07:21 PM

P: 994

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? 



#6
Dec1512, 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. diffiehellman 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. 



#7
Dec1512, 07:47 PM

P: 4,570

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. 



#8
Dec1512, 07:53 PM

P: 994

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.




#9
Dec1512, 08:04 PM

P: 4,570

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.




#10
Dec1512, 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).




#11
Dec1612, 08:28 PM

P: 994




#12
Dec1612, 08:28 PM

P: 166

Thanks, reading! Will be back.




#13
Dec1612, 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. 



#14
Dec1612, 10:46 PM

P: 4,570

Many thanks Dragonfall.




#15
Dec1812, 04:37 AM

P: 994

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 