Interesting paper I had not heard of, but was recently referred to... http://www.cwi.nl/~brands/cash.html Electronic Cash System Based On The Representation Problem Stefan Brands CWI P.O. Box 4079, 1009 AB Amsterdam The Netherlands e-mail: brands@cwi.nl Abstract: We present a new on-line electronic cash system based on a problem, called the representation problem, of which little use has been made in literature thus far. Our system is the first to be based entirely on discrete logarithms. Using the representation problem as a basic concept, some techniques are introduced that enable us to construct protocols for withdrawal and payment that do not use the cut and choose methodology of earlier systems. As a consequence, our cash system is much more efficient in both computation and communication complexity than previously proposed systems. Another important aspect of our system concerns its provability . Contrary to previously proposed systems, its correctness can be mathematically proven to a very great extent. Specifically , if we make one plausible assumption concerning a single hash-function, the ability to break the system seems to imply that one can break the Diffie-Hellman problem. Our system offers a number of extensions that are hard to achieve in previously known systems. In our opinion the most interesting of these is that the entire cash system (including all the extensions) can be incorporated straight forwardly in a setting based on wallets with observers, which has the important advantage that double- spending can be prevented in the \014rst place, rather than detecting the identity of a double-spender after the fact. In particular, it can be incorporated even under the most stringent requirements conceivable about the privacy of the user, which seems to b e impossible to do with previously proposed systems. Another benefit of our system is that framing attempts by a bank have negligible probability of success (independent of computing power) by a simple mechanism from within the system, which is something that p previous solutions lack entirely . Furthermore, the basic cash system can be extended to checks, multi-show cash and divisibility , while retaining its computational efficiency. Although in this paper we only make use of the representation problem in groups of prime order, similar intractable problems hold in RSA-groups (with computational equivalence to facto ring and computing RSA- roots). We discuss how one can use these problems to construct an efficient cash system with security related to factoring or computation of RSA-roots, in an analogous way to the discrete log based system. Finally , we discuss a decision problem (the decision variant of the Diffie-Hellman problem) that is strongly related to undeniable signatures, which to our knowledge has never been stated in literature and of which we do not know whether it is in BPP. A p roof of its status would be of interest to discrete log based cryptography in general. Using the representation problem, we show in the appendix how to batch the confirmation protocol of undeniable signatures such that polynomially many undeniable signatures can be verified in four moves. AMS Subject Classification (1991) : 94A60 CR Subject Classification (1991) : D.4.6 Keywords and Phrases : Cryptography , Electronic Cash, Representation Problem _______________________ Regards, It is not because things are difficult that we do not dare; it is because we do not dare that they are difficult. -Seneca Joseph Reagle http://rpcp.mit.edu/~reagle/home.html reagle@mit.edu E0 D5 B2 05 B6 12 DA 65 BE 4D E3 C1 6A 66 25 4E