Data processing: financial – business practice – management – or co – Business processing using cryptography – Secure transaction
Reexamination Certificate
1998-11-18
2002-09-03
Kemper, Melanie A. (Department: 2165)
Data processing: financial, business practice, management, or co
Business processing using cryptography
Secure transaction
C705S074000
Reexamination Certificate
active
06446052
ABSTRACT:
TECHNICAL FIELD
This invention relates to the field of electronic commerce transaction systems and, more particularly, to the tracing of anonymous digital cash.
BACKGROUND INFORMATION
Digital cash, also known informally as e-cash, is a form of digital currency. Cash is represented by electronic (digital) coins. As with ordinary coins, each digital coin has a fixed denomination. Coins are “issued” by a coin issuer, also referred to as a bank. Using cryptography, a bank signs a coin to certify the coin's authenticity.
In some electronic cash systems, such as the ECASH system commercially available from DIGICASH of Palo Alto, Calif., a user authenticates herself in a secure manner to a bank. The user then withdraws coins, which are numbers (or sets of numbers) that represent money, from the bank. The bank deducts funds corresponding to the withdrawn coins from her account. To spend a coin with a merchant, the user simply transmits the coin to the merchant. To prevent double spending of a coin, the merchant verifies on-line with the bank that the coin has not already been spent. An explanation of the DIGICASH protocols can be found in B. Schoenmakers, “Basic Security of the ecash™ Payment System,” which appears in Computer Security and Industrial Cryptography: State of the Art and Evolution, ESAT Course 1997, edited by Bart Preenel et al.
One type of cryptography used in electronic cash systems is public/private key cryptography. One commercially available public/private key technology is RSA encryption technology, available from RSA Data Security, Inc. of San Mateo, Calif. To provide a simplified overview, an RSA signature is based on the difficulty of computing roots, for example cube roots, modulo a large modulus N with unknown factorization. A signer knows the factorization of the modulus N and so the signer is the only entity able to compute f
1
(x) mod N, for a given (x), where f is a one-way collision-free hash function, and f
1
(x) mod N represents the n
th
root of f(x) modulo (N). In the implementation of digital cash, a user who presents a merchant with the valid pair (x, f
1
(x) mod N), where n and N are publicly known numbers chosen by the bank, effectively demonstrates that the coin (x) has been authorized (or signed) by the bank, because only the bank can determine (f
1
(x) mod N) from x. To distinguish among different denominations in this scheme, the bank can use different public exponents. For example, (x, f
1/3
(x) mod N) might indicate a $0.50 coin, while (x, f
1/17
(x) mod N) might indicate a $1 coin.
Digital coins have been implemented that are both secure (in the bank's interest) and afford a heightened assurance of consumer privacy by providing anonymity to users with respect to both merchants and banks. Informally, a digital cash scheme is referred to as unconditionally blind or anonymous if the bank that issues a coin is unable to determine, either at the time of withdrawal or later upon examining circulating or deposited coins, which coin was withdrawn by which user. The user can withdraw money from the bank in such a scheme, spend it at a merchant, and be confident that when the merchant deposits the money at the bank, the bank will not be able to recognize the money as the same cash given to the user.
There are several variants of anonymous digital cash, not all of which have been implemented commercially. In a commercially available, on-line version implemented by DIGICASH, a coin consists of an RSA signature by the bank on the hash of a message (x). In this blinded protocol, the bank signs coin (x) by calculating (f
1
(x) mod N) without knowing what (x) is. At the time the coin is submitted to the bank for signature, the coin (x) is “hidden” from the bank by a blinding factor, which the user “multiplies in” and combines with (x) before transmission to the bank and “divides out” after the bank has signed.
Referring to
FIG. 1
, the bank publishes a public modulus N=pq, for which it alone knows the factorization (pq), and chooses a public exponent, which for this example is the exponent
3
(i.e. cube root). A user chooses random numbers (x) and (r), where (x) is the number to be used in the coin, and (r) is a blinding factor and (X)&egr;
r
Z
N
and (r)&egr;
r
Z
N
, meaning that (x) and {circle around (R)} are integers between (0) and (N−1) inclusive. The user calculates f(x) mod N, and multiplies the result by the blinding factor (r
3
). The user sends (r
3
f(x) mod N) to the bank. The bank determines the cube root mod N, which only the bank can do because the bank knows the factors (pq) of (N). The bank never knows (x), however, because it receives f(x) multiplied by the blinding factor (r
3
). The bank then returns (r f
1/3
(x) mod N) to the user. The user extracts f
1/3
(x) from the quantity (r f
1/3
(x) mod N) it receives from the bank by dividing by (r). The user then can provide a merchant with the “signed” coin (x, f
1/3
(x)). The merchant can verify that the bank has signed the coin (x, f
1/3
(x)) by calculating f(x) mod N from x, and comparing it to the cube of (f
1/3
(x)) modulo (N). This protocol is unconditionally blind, because the blindness does not rely on computational assumptions or statistical arguments.
A weaker notion of blindness can be described informally in terms of a lack of statistical correlation between the view of the signer at the time of signing and the set of produced signatures. A more formal definition of computational blindness may be described in terms of the following experiment. The user produces two messages m
0
and m
1
of length polynomial in k
1
. The user sets a bit (b) uniformly at random. In two arbitrarily interleaved (and presumed blind) digital signature protocols, she presents the documents m
0
and m
1
to the bank in an order specified by (b), i.e., in the order {m
b
, m
1−b
}. In this interaction, she obtains from the bank signatures s(m
0
) and s(m
1
) on the two messages. The user presents the message/signature pairs (m
0
, s(m
0
)) and (m
1
, s(m
1
)) to the bank. The bank then attempts to guess the bit b. If no polynomial-time algorithm exists which enables the bank do so with probability 1/2+1/poly (over its own coin-flips and those of the user), then we say that the digital signature scheme is blind or secure with respect to anonymity.
Researchers have observed that unconditional anonymity in payment systems might be exploited to facilitate crimes like blackmail and money laundering. This observation spurred research into the idea of making anonymity in payment systems conditional, and, in particular, revocable by a third party. This notion is referred to as a trustee-based coin tracing. A National Security Agency report has since declared the availability of tracing in e-cash systems vital to the security interests of the United States. The importance of traceability in e-cash systems has motivated the proposal of various trustee-based coin tracing schemes.
One trustee-based tracing scheme is based on a blind Schnorr-like signature scheme and involves use of interactive proofs between trustees and the bank. Another trustee-based tracing scheme is based on blind RSA signatures, but make use of a cut-and-choose protocol, resulting in a scheme that is flexible but has rather large coin sizes and computational requirements.
Another scheme makes use of a blind signature based on that of Chaum and Pedersen. In this scheme, the user requests a pseudonym and registration information from a trustee. The user presents this registration information to the bank, and also incorporates it into the coins she withdraws.
Another scheme introduces the notion of “challenge semantics,” enabling flexible determination of coin value, so that coins can be invalidated, for example in case of a bank robbery. This scheme is capable of addressing stronger attack models than many others and a wider range of commercial settings. It is also adaptable to use with any underlying digital signature scheme. On the other hand, this scheme requires on-line participation of
Kemper Melanie A.
RSA Security Inc.
Testa Hurwitz & Thibeault LLP
LandOfFree
Digital coin tracing using trustee tokens does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital coin tracing using trustee tokens, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital coin tracing using trustee tokens will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896795