Trustee Tokens: Simple and Practical Anonymous Digital Coin Tracing

We introduce a trustee-based tracing mechanism for anony- mous digital cash that is simple, efficient, and provably secure relative to its underlying cryptographic primitives. In contrast to previous schemes, ours may be built on top of a real-world anonymous cash system, such as the DigiCashTM system, with minimal modification to the underlying protocols. In addition, our scheme involves no change to the structure of the coins. On the other hand, our scheme requires user interaction with a trustee, while many other such systems do not. This interaction occurs infrequently, however, and is efficient both in terms of computation and storage requirements. Our scheme also achieves more limited security guarantees in the presence of malicious trustees than many other sys- tems do. While this is a disadvantage, it represents a tradeoff enabling us to achieve the high level of practicality of our system.