From: Robbie Gates <gates_r@maths.su.oz.au>
Date: Tue, 19 Dec 95 22:10:10 PST
To: Cypherpunks <cypherpunks@toad.com>
Subject: Bit Commitment Query
Message-ID: <30D7A993.3F54@maths.su.oz.au>
MIME-Version: 1.0
Content-Type: text/plain


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.