Mis-representation of Identities in E-Cash Schemes
		and how to Prevent it

	Agnes Chan (Northeastern University, Boston, MA),
	Yair Frankel (Sandia Nat. Labs, Albuquerque, NM),
	Phil MacKenzie (Boise State University, Boise, Idaho.
	Research performed while at Sandia Nat. Labs, ABQ, NM),
	Yiannis Tsiounis (Northeastern University, Boston, MA)


In Crypto '93, S. Brands presented a very efficient off-line
electronic cash scheme based on the representation problem in groups
of prime order. In Crypto '95 a very efficient off-line divisible
e-cash scheme based on factoring Williams integers was presented by
T. Okamoto.  We demonstrate one efficient attack on Okamoto's scheme
and two on Brands' scheme which allow users to mis-represent their
identities and double-spend in an undetectable manner, hence defeating
the most essential security aspect of the schemes. The attack on
Brands' scheme (which we suspect, given his previous related results,
was an inadvertent omission) is also applicable to T. Eng and
T. Okamoto's divisible e-cash scheme (presented in Eurocrypt '94)
which uses Brands' protocols as a building block.

We present an efficient modular fix which is applicable to any use of
the Brands' idea, and we discuss how to counteract the attack on
Okamoto's scheme.  Hence the original results remain significant
contributions to electronic cash.