The cost of successful tag forgery can be enormous, since if an adversary could forge tags, he or she could manufacture counterfeit coins at will. In order to minimize the possibility of successful tag forgery, we suggest the following:
A coin can have various states. For example, spent or not; anonymous or not; split, and if so how; etc. These are marked in the database.
The issuer will expect from a coin purchaser requesting coins, or a change maker wanting change, a specification of exactly what kinds of coins are being requested. The specification takes the form of a list of denominations, and for each denomination, the number of coins of that denomination that is desired. The simplest thing is to just ask for one coin of a certain denomination, for example a single coin of $0.80. But one could ask for, say, ,meaning I want 2 coins of value $2.50 each, one coin of value $1.25, and 3 coins of value $2. The total value of the list is the total dollar value, $12.25 in the example just given. The choice of specification is decided by a combination of the user's needs and the software (purse).
The cryptographic primitives used in the protocols of Section 3 are summarized in Figure 2. All the parties have public keys. The issuer has a cache of identities and their corresponding public keys, so that the certification authority is not needed in transactions with the issuer. (But it may be needed for other transactions.)
The encryption function must provide, besides secrecy, some form of ``message integrity.'' Decryption of a ciphertext results either in a plaintext message, or in a flag indicating non-validity. Formally, the property we require of the encryption scheme is plaintext awareness [5,2]. Roughly speaking, this means that correct decryption convinces the decryptor that the transmitter ``knows'' the plaintext that was encrypted. This is the strongest known type of security, and in particular it is shown in  that it implies non-malleability (it is not possible to modify a ciphertext in such a way that the resulting plaintext is meaningfully related to the original one, as formalized in ) and security against chosen-ciphertext attacks. A simple, efficient scheme to achieve such encryption using RSA is OAEP . A Diffie-Hellman based solution can be found in . (Note that the RSA PKCS #1 encryption standard can be broken under chosen ciphertext attacks , and is thus not suitable for our purposes.)
However we stress that plaintext-aware encryption does not provide authentication in the manner of a signature, i.e., it does not provide non-repudiation. But it prevents an adversary from tampering with a ciphertext.
Also note that the encryption function is randomized: , invoked upon message m will use, to compute its output, some randomizer, so that each encryption is different from previous ones.
Finally, the notation denotes bitwise XOR.