On the Anonymity of Fair Offline E-cash Systems.
M. Gaud and J. Traore

Fair off-line electronic cash (FOLC) schemes [5, 29] have been introduced for preventing misuse of anonymous payment systems by criminals. In these schemes, the anonymity of suspicious transactions can be revoked by a trusted authority. One of the most efficient FOLC system has been proposed by de Solages and Traoré [13] at Financial Cryptography'98. Unfortunately, in their scheme, the security for legitimate users (i.e., anonymity) is not clearly established (i.e., based on a standard assumption). At Asiacrypt'98, Frankel, Tsiounis and Yung [17] improved the security of [13] by proposing a fair cash scheme for which they prove anonymity under the Decision Diffie-Hellman (DDH) assumption. In this paper, we show that Frankel et al. failed to prove that their scheme satisfies the anonymity property. We focus here on this security problem and investigate the relationships between different notions of indistinguishability in the context of fair electronic cash. As a result, we prove under the DDH assumption, that a straightforward variant of [13], which is more simple and efficient than [17], is secure for users. This proof relies on the subsequent result of Handschuh, Tsiounis and Yung [19] showing equivalences between general decision and matching problems. Our proof is somewhat generic and can be used to prove that [17] is secure as well.