Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simultaneous disclosure

  1. Dec 15, 2012 #1
    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. jcsd
  3. Dec 15, 2012 #2
    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.
     
  4. Dec 15, 2012 #3
    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.
     
  5. Dec 15, 2012 #4
    OH.. that's different. Proving you know something is different from calculating it! That's called a zero-knowledge proof.
     
  6. Dec 15, 2012 #5
  7. Dec 15, 2012 #6
    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.
     
  8. Dec 15, 2012 #7

    chiro

    User Avatar
    Science Advisor

    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.
     
  9. Dec 15, 2012 #8
    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.
     
  10. Dec 15, 2012 #9

    chiro

    User Avatar
    Science Advisor

    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.
     
  11. Dec 15, 2012 #10
    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).
     
  12. Dec 16, 2012 #11
  13. Dec 16, 2012 #12
    Thanks, reading! Will be back.
     
  14. Dec 16, 2012 #13
    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.
     
  15. Dec 16, 2012 #14

    chiro

    User Avatar
    Science Advisor

    Many thanks Dragonfall.
     
  16. Dec 18, 2012 #15
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Simultaneous disclosure
Loading...