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)