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)