3 ms·

Bit commitment is a core concept in crypto -- this is also a piss-poor commitment protocol. After I flip the coin and say tails you can claim to have "won" and

by evgen 17y ago

Bit commitment is a core concept in crypto -- this is also a piss-poor commitment protocol. After I flip the coin and say tails you can claim to have "won" and when I dispute the result you just pull out a sentence that has TAIL at the front and claim that this is what you sent to me. How can either party prove the claim? If you build a good bit commitment scheme you can get by with a very small number of message exchanges and still have both parties accept the results. Start with the wikipedia entry for bit commitment, read Blum's coin flipping over the telephone paper and work your way up to zero knowledge protocols...

RiderOfGiraffes 17y ago
I appreciate you taking the time to reply, but I'm not sure I understand you. You seem to be claiming that what I've outlined has a flaw, but I don't understand your objection. I don't just pull out any sentence with (for example) "tail" at the front, I have to find one that has the hash I sent you. Could you expand a little further as to why the scheme I've described doesn't work? Thanks.
- devicenull 17y ago
  How does that verify anything? You still flipped the coin, then wrote the sentence. The two do not have to be related (say you flip the coin and get heads, then write tails, what happens then?).
  - RiderOfGiraffes 17y ago
    Er, yes, but they call. It doesn't matter if I choose whatever I like, then send the hash. The other person then has a free choice, and they are right or wrong. The coin is effectively irrelevant. Imagine we're together and I pretend to toss the coin. I decide what I want it to be, place it as that, and then hold it in my hand. Provided I'm not allowed to change my mind, this is just as fair as actually tossing the coin because you are free to call and are right or wrong with equal probability. The point about the real coin is that it prevents me from changing my mind. The point about the hash is it prevents me from changing my mind. In effect, the hash is the coin. I am free to decide heads or tails as I wish - I just need to be prevented from changing my mind after you call.
    - dgreensp 17y ago
      Sounds like it works to me, except that the lack of the actual coin flip introduces an interesting psychological element -- it's kind of like rock-paper-scissors. Two people say "heads" or "tails", and person A wins if they are the same, else B. You can be thinking things like "he usually says 'heads', but maybe he'll try to psyche me out..."
      - RiderOfGiraffes 17y ago
        That's why person A should actually flip the coin. People are really bad at choosing "randomly."
- evgen 17y ago
  I think we have a difference in threat models. It sounds like you are dealing with a non-adversarial model in which neither party has much of an incentive to cheat. If this is the case then your system works fine. If either party gains much by cheating then your system is insufficient to solve the problem.
  - RiderOfGiraffes 17y ago
    You might be right, but I don't understand how either party could cheat. Let's assume that the hash is computationally secure, so that it's effectively impossible to compute a file to match a given hash. SHA-256 seems to me to meet that assumption. I decide whether I want heads or tails, and create a file that starts with my choice, then has random padding. I compute the hash and send it to you. You now tell me openly your call. I believe you have no way to compute from my hash what I've chosen, so to you, my choice is hidden. Whether you guess right is effectively random. Now I reveal the file from which the hash was computed. Again, I can't compute a different file with the same hash, so I'm forced to reveal the choice I made. If you were right we both know it. If you were wrong we both know it. Can you explain how it's possible for either of us to cheat? I appreciate your time - thanks.

by evgen 17y ago

RiderOfGiraffes 17y ago

I appreciate you taking the time to reply, but I'm not sure I understand you. You seem to be claiming that what I've outlined has a flaw, but I don't understand your objection. I don't just pull out any sentence with (for example) "tail" at the front, I have to find one that has the hash I sent you. Could you expand a little further as to why the scheme I've described doesn't work? Thanks.

devicenull 17y ago
How does that verify anything? You still flipped the coin, then wrote the sentence. The two do not have to be related (say you flip the coin and get heads, then write tails, what happens then?).
- RiderOfGiraffes 17y ago
  Er, yes, but they call. It doesn't matter if I choose whatever I like, then send the hash. The other person then has a free choice, and they are right or wrong. The coin is effectively irrelevant. Imagine we're together and I pretend to toss the coin. I decide what I want it to be, place it as that, and then hold it in my hand. Provided I'm not allowed to change my mind, this is just as fair as actually tossing the coin because you are free to call and are right or wrong with equal probability. The point about the real coin is that it prevents me from changing my mind. The point about the hash is it prevents me from changing my mind. In effect, the hash is the coin. I am free to decide heads or tails as I wish - I just need to be prevented from changing my mind after you call.
  - dgreensp 17y ago
    Sounds like it works to me, except that the lack of the actual coin flip introduces an interesting psychological element -- it's kind of like rock-paper-scissors. Two people say "heads" or "tails", and person A wins if they are the same, else B. You can be thinking things like "he usually says 'heads', but maybe he'll try to psyche me out..."
    - RiderOfGiraffes 17y ago
      That's why person A should actually flip the coin. People are really bad at choosing "randomly."
evgen 17y ago
I think we have a difference in threat models. It sounds like you are dealing with a non-adversarial model in which neither party has much of an incentive to cheat. If this is the case then your system works fine. If either party gains much by cheating then your system is insufficient to solve the problem.
- RiderOfGiraffes 17y ago
  You might be right, but I don't understand how either party could cheat. Let's assume that the hash is computationally secure, so that it's effectively impossible to compute a file to match a given hash. SHA-256 seems to me to meet that assumption. I decide whether I want heads or tails, and create a file that starts with my choice, then has random padding. I compute the hash and send it to you. You now tell me openly your call. I believe you have no way to compute from my hash what I've chosen, so to you, my choice is hidden. Whether you guess right is effectively random. Now I reveal the file from which the hash was computed. Again, I can't compute a different file with the same hash, so I'm forced to reveal the choice I made. If you were right we both know it. If you were wrong we both know it. Can you explain how it's possible for either of us to cheat? I appreciate your time - thanks.