From: futplex@pseudonym.com (Futplex)
Date: Wed, 20 Dec 95 01:27:32 PST
To: cypherpunks@toad.com (Cypherpunks Mailing List)
Subject: Re: Bit Commitment Query
In-Reply-To: <30D7A993.3F54@maths.su.oz.au>
Message-ID: <199512200927.EAA27328@thor.cs.umass.edu>
MIME-Version: 1.0
Content-Type: text/plain


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)