Bit Commitment Query
I am confused about bit commitment via one way hashing as described in Schneier (1st ed, p 73) h is a one way hash function. This description from Schneier, except that variables are changed so i don't need subscripts: 1. Alice has a bit b she wants to commit to. She picks random bit strings R and S, and sends Bob h(R,S,b),R 2. To verify commitment, she tells Bob S and b so he can verify the hash. What i don't get is Schneier's claim: ``If Alice didn't send Bob R, then she could change the value of S and then the value of the bit. The fact that Bob already knows R prevents her from doing this.'' Can someone explain exactly how Alice cheats if Bob doesn't know R. I can't see how she can alter R and S and b at all without being able to produce hash collisions. In essence, why doesn't the following work: 1. Alice has a bit b. She picks a random bit string R and sends Bob h(R,b) 2. To verify, she tells Bob R and b. Assuming Bob knows b is a single bit, how does Alice cheat without needing to produce hash collisions for h. thanks in advance for any help, - robbie -- ---------------------------------------------------------------------- robbie gates | it's not a religion, it's just a technique. apprentice algebraist | it's just a way of making you speak. pgp key available | - "destination", the church.
robbie gates, apprentice algebraist writes:
In essence, why doesn't the following work:
1. Alice has a bit b. She picks a random bit string R and sends Bob h(R,b)
2. To verify, she tells Bob R and b.
Assuming Bob knows b is a single bit, how does Alice cheat without needing to produce hash collisions for h.
Hmmm. I can't see anything wrong with your reasoning, and I too am puzzled by Schneier's comment about Alice needing to send R_1 to Bob initially. I hope someone else will give a more authoritative answer. Your question prompted me to study the other bit commitment protocols in _AC_ a bit more closely (pun not intended). Schneier observes that the b.c. with hash function protocol you cited has an advantage over the b.c. protocol with symmetric encryption he describes (v.1,pg.72). Namely, the hashing b.c. protocol only needs one-way communication after the protocol negotiation. It seems to me that the encryption b.c. protocol he gives can easily be modified to require only one-way communication (Alice-->Bob). The modified protocol goes like this: [0] Alice has a bit b, and generates a secret key K and a random string R. [1] Alice --- E_K(R, b), R --> Bob [2] Alice wants to reveal her committed bit. [3] Alice --- K --> Bob [4] Bob computes D_K(E_K(R, b)) = (R, b) and checks the value of b (or cries foul if R has the wrong value) This can't possibly be a new idea, but I don't know the literature well enough to give a reference. Of course, the other possibility is that this protocol is broken. :} If E is a good encryption algorithm, it should be hard for Alice to find K_2 s.t. D_K_2(E_K(R, b)) = (R, 1-b), even though she gets to choose R. Comments ? Why might we prefer to use the encryption b.c. protocol in Schneier to something like the above ? -Futplex <futplex@pseudonym.com> R.I.P. Brian Jones (apprentice cryptographer)
participants (2)
-
futplexï¼ pseudonym.com -
Robbie Gates