cut & choose

-----BEGIN PGP SIGNED MESSAGE-----

In Applied Cryptography, Schneier describes digital cash protocols that
depend on the cut and choose method:  Alice prepares 100 anonymous money
orders for $100, sends them all to the bank, which opens all the envelopes
except one picked at random.  If the 99 envelopes checked have money
orders for $100, then the bank is confident that the one they sign blindly
will be for $100 as well. 

Chaum's system uses different keys for different denominations.  Alice 
only sends one envelope, and the bank uses its $100 key to sign it.

I don't understand why anyone would use the cut and choose protocol over 
denominated keys.  Chaum's method seems a lot cleaner to me and more 
secure.  It obviously uses less bandwidth.  What am I missing here?

==
Alex Strasheim | finger astrashe@nyx.cs.du.edu
alex@omaha.com | for my PGP 2.6.1. public key

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBLudoHxEpP7+baaPtAQFIiwQAsCc/TYI/cgJyGf6AtykBGgu+qJJ+peM6
/IYXnUzrIeFLx54nRjsUOUFYJs6Uu3vu6s2BRbd2/YIJVaY6/kP4HO0zuMhqFn2z
4eddRverUeH59IZgZ+4Va4/rgfn5hRdNSOgNinIyk0aRsa8ulR+cmJdUYqggHgd5
w2dxkAtDSGM=
=fzJT
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----

Alex Strasheim <alex@omaha.com> writes:

>I don't understand why anyone would use the cut and choose protocol over 
>denominated keys.  Chaum's method seems a lot cleaner to me and more 
>secure.  It obviously uses less bandwidth.  What am I missing here?

Schneier's examples are meant to be instructional in nature rather than
practical, showing how it would be done with paper envelopes and such.
The only example he has which is cryptographic is the "off-line" version
where Alice's identity is encoded in the cash in such a way that it is
revealed if she double-spends.  Chaum's off-line protocol also relies on
cut and choose for this (Chaum, Fiat, Naor, Crypto 88).  That is the
major improvement in Brands' scheme, that you don't have to use cut and
choose for his off-line cash system.

Hal

-----BEGIN PGP SIGNATURE-----
Version: 2.6

iQBVAwUBLuiNKxnMLJtOy9MBAQH1HgH/SycFuvD/vud4ZHUU8b8WDV+KgsfoyxbT
4Immhq478EcLhbLPrjriinyue17lc4fChQDPhm7Wg/i3w9rkaQQwGg==
=hyg3
-----END PGP SIGNATURE-----

> From: Alex Strasheim <alex@omaha.com>
> 
> In Applied Cryptography, Schneier describes digital cash protocols that
> depend on the cut and choose method [...] Chaum's system uses different
> keys for different denominations. [...]
> 
> I don't understand why anyone would use the cut and choose protocol over 
> denominated keys.  Chaum's method seems a lot cleaner to me and more 
> secure.  It obviously uses less bandwidth.  What am I missing here?

Cut and choose is necessary for several protocols.  It is necessary for
cash protocols that do not use blinding, it is necessary for the cash
protocols that include identification, and in general it is necessary for
any protocol where the signer does not know the contents of what they are
signing _and_ the contents need to be formed in a particular fashion.

Denominated keys requires the user (the one accepting the packet and
verifying it) to keep track of more information, such as which keys
correspond to which denominations.  In cut and choose the end user only
needs to know one key and the other information is carried in the packet
itself.  There is a cost in each system, it is just a question of who bears
the cost and what abilities the cost gives the system...

jim