Method and apparatus for implementing traceable electronic cash

• US 5,889,862 A
• Filed: 07/15/1996
• Issued: 03/30/1999
• Est. Priority Date: 07/17/1995
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Fujisaki, Eiichiro, Abe, Masayuki, Ohta, Kazuo, Fujioka, Atsushi
• Primary Examiner(s): HAYES, GAIL O
• Assistant Examiner(s): White, Carmen D.
• Application Number:
  US08/683,538
• Time in Patent Office: 988 Days
• Field of Search: 380/23, 380/24, 380/25, 705/39
• US Class Current: 705/69
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 20/10 specially adapted for electronic funds transfer [EFT] systems; specially adapted for home banking systems
• CPC Class Codes: G06Q 20/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: G06Q 20/4014 Identity check for transactions
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme
• CPC Class Codes: H04L 9/3257 using blind signatures

Abstract

In a method for implementing traceable electronic cash, a user US sends a bank BK a product N of prime numbers P and Q, a prime number L and his real name ID_U, and the bank BK generates a pseudonym I corresponding to the real name ID_U and keeps the correspondence between the real name ID_U and the pseudonym I secret. The bank BK uses a signature function Ω=D_eB (N,L,I) to attach a signature to information composed of the above-mentioned N, L and I and sends the user US the signed information Ω as information containing a license B. The user US generates authentication information X from the N and a random number R and sends the bank BK information Z obtained by performing blind signature preprocessing on information (X,B) with a function F_eC and has the information Z signed by the bank BK with a signature function D_eC (Z) to obtain electronic cash C. When the user US abuses the electronic cash C, the bank BK follows a court order to reveal the correspondence between the real name ID_U and pseudo name of the user US and trace the electronic cash spent.

Claims

1. A method for implementing traceable electronic cash, comprising the steps:

(1) wherein a user sends a first institution public information N corresponding to his real name ID_U and first secret information;

(2) wherein said first institution recognizes the identity of said user, then generates a pseudonym I of said user and keeps secret the correspondence between at least either one of said pseudonym I and said public information N and said real name ID_U ;

(3) wherein said first institution attaches a signature to said public information N and said pseudonym I and sends said signature and said pseudonym I to said user;

(4) wherein said user obtain a license B from said signature sent from said first institution and stores it together with said pseudonym I;

(5) wherein said user uses said first secret information to calculate second secret information S corresponding to said pseudonym I and said public information N and holds said second secret information S;

(6) wherein said user sends information containing at least a random number R and said license B and an amount of money A to a second institution to request it to issue electronic cash;

(7) wherein said second institution adds a signature to said received information containing said license B and sends it to said user as information containing electronic cash C;

(8) wherein said user checks said signed information from said second institution to see if said license B bears a signature to said public information N and said pseudonym I and if said electronic cash C is usable under said license B, thereafter making a payment to a third party through the use of said random number and said second secret information S;

(9) wherein said third party sends said second institution all information of communication with said user so as to seek a settlement concerning said electronic cash C; and

(10) wherein, when there is a likelihood of an attack, the correspondence between at least either one of said pseudonym I and said public information N and said real name ID_U kept secret by said first institution is retrieved and said pseudonym I and said public information N are revealed to preclude the possibility of said attack.

2. The method of claim 1, wherein said first secret information is composed of prime numbers P and Q that bear a relationship N=P×

Q;

wherein in said step (5) said second secret information S is calculated by the following equation with L as a prime number

space="preserve" listing-type="equation">S=I.sup.1/L mod N;

wherein in said step (6) said user;

(6-1) generates said random number R and calculates authentication information X from said public information N, said prime number L and said random number R by the following equation

space="preserve" listing-type="equation">X=R.sup.L mod N; and

(6-2) performs blind signature preprocessing Z=F_eC (X,B), represented by a function F_eC, for said authentication information A and said license B and sends said second institution the resulting information Z as information containing said license B, together with amount information A of said electronic cash C;

wherein in said step (7) said second institution attaches a blind signature Θ

=D_eC (Z), represented by a function D_eC, to said information Z by using a secret key corresponding to said amount A of said electronic cash C and sends said user the resulting information Θ

as information containing said electronic cash C;

wherein in said step (8);

said user performs blind signature postprocessing C=G_eC (Θ

), represented by a function G_eC, for said signature Θ

to obtain said electronic cash C;

said third party checks the validity of said license B for information (N,I) and the validity of said electronic cash S for information (X,B) and, if they are proved valid, said third party sends said user a inquiry Eε

Z_L ={0,1, . . . ,-1};

said user calculates a response Y from said second secret information S, said information (N,R) and said inquiry E by the following equation

space="preserve" listing-type="equation">Y=R·

S.sup.E mod N

and sends said response Y to said third party; and

said third party calculates Y^L and X·

I^E (mod N) and makes a verification to see if the following equation is satisfied

space="preserve" listing-type="equation">Y.sup.L .tbd.X·

I.sup.E (mod N)

and if said verification succeeds, said third party accepts said electronic cash C as cash of said amount information A.

3. The method of claim 1, wherein a plurality of departments of said first institution use different pairs of sequentially corresponding pieces of association information α

to manage the correspondence between said real name ID_U of said user and at least one of said pseudonym I and said public information N so that the correspondence between at least one of said pseudonym I and said public information N and said real name is made available through said association information α

only when said plurality of departments cooperate.

9. The method of claim 1, 3, or 4, wherein said first and second institutions each form part of the same bank.

10. The method of claim 1, 3, or 4, wherein said first institution is a trustee and said second institution is a bank different from said trustee.

11. The method of claim 1 or 4, wherein a plurality of departments of said first institution use different pairs of sequentially corresponding pieces of association information α

to manage the correspondence between said real name ID_U of said user and at least one of said pseudonym I and said public information N so that the correspondence between at least one of said pseudonym I and said public information N and said real name is made available through said association information α

only when said plurality of departments cooperate.

12. The method of claim 3, wherein said plurality of departments of said first institution are a plurality of trustees and said second institution is a bank different from said plurality of trustees.

4. A method for implementing traceable electronic cash, comprising the steps:

(1) wherein a user sends a first institution public information N corresponding to his real name ID_U and secret information;

(2) wherein said first institution recognizes the identity of said user, then generates a pseudonym I of said user and keeps secret the correspondence between at least either one of said pseudonym I and said public information N and said real name ID_U ;

(3) wherein said first institution attaches a signature to said public information N and said pseudonym I and sends said signature and said pseudonym I to said user;

(4) wherein said user obtains a license B from said signature sent from said first institution and stores it together with said pseudonym I;

(5) wherein said user sends a second institution information containing at least a random number b and said license B and an amount of money A to request said second institution to issue electronic cash;

(6) wherein said second institution attaches a signature to said information containing said license B from said user and sends said user said signed information as information containing electronic cash C;

(7) wherein said user checks said signed information from said second institution to see if said license B bears a signature to said public information N and said pseudonym I and if said electronic cash C is usable under said license B, thereafter making a payment to a third party through the use of said random number b and said secret information;

(8) wherein said third party sends said second institution all information of communication with said user so as to seek a settlement concerning said electronic cash C; and

(9) wherein, when there is a likelihood of an attack, the correspondence between at least either one of said pseudonym I and said public information N and said real name ID_U kept secret by said first institution is retrieved and said pseudonym I and said public information N are revealed to preclude the possibility of said attack.

5. The method of claim 4, wherein said secret information is composed of prime numbers P and Q that bear a relationship N=P×

Q;

wherein in said step (5) said user calculates a one-way function g(B∥

b) from said random number R and said license B, then performs blind signature preprocessing Z=F_eC (g(B∥

b)) for said one-way function g(B∥

b) and sends said second institution the resulting information Z as information containing said electronic cash C, together with said amount information A;

wherein in said step (6) said second institution uses a secret key corresponding to said amount A of said electronic cash C to calculate a signature Θ

=D_eC (Z) and sends it to said user;

wherein in said step (7) said user performs blind signature postprocessing C=G_eC (Θ

) for said received signature Θ

to obtain said electronic cash of said amount A; and

wherein the procedure for the payment to said third party comprises the steps;

(7-1) wherein said user calculates

space="preserve" listing-type="equation">Γ

.sub.0 =<

f.sub.Γ

(C∥

O∥

N)>

.sub.QR

from said C, N, P and Q and generates

space="preserve" listing-type="equation">Ω

.sub.j.sbsb.1 .sub.. . . j.sbsb.q =<

f.sub.Ω

(C∥

j.sub.1 ∥

. . . ∥

j.sub.q ∥

N)>

.sub.1

where q=1, . . . ,t, from said electronic cash C and said node j₁ . . . j_q and calculates from said Γ

₀, Ω

_j.sbsb.1.sub.. . . j.sbsb.q (where q=1, . . . ,t),

N, P and Q, a radical root of a node value corresponding to the amount spent ##EQU4## (7-2) wherein said user sends I, N, X_j1 . . . jt, B, b, c and j₁, . . . ,j_t to said third party;

(7-3) wherein said third party verifies the validity of said license B for information (I,N) by checking said license B to see if it satisfies

space="preserve" listing-type="equation">V.sub.eB ((N,I),B)=OK

and verifies the validity of said electronic cash C for information (B,b) by checking said electronic cash to see if it satisfies

space="preserve" listing-type="equation">V.sub.eC (g(B∥

b),C)=OK

and, when said license B and said electronic cash C are valid, letting (a/b) represent a Jacobi symbol, said third party makes a check to see if

space="preserve" listing-type="equation">(X/N)=-1

is satisfied, after which said third party calculates from said C and N

space="preserve" listing-type="equation">f.sub.Γ

(C∥

O∥

N),

and calculates from said C, j₁ . . . j_q and N

space="preserve" listing-type="equation">Ω

.sub.j.sbsb.1 .sub.. . . j.sbsb.q =<

f.sub.Ω

(C∥

j.sub.1 ∥

. . . ∥

j.sub.q ∥

N)>

.sub.1,

where q=1, . . . ,t, and, further, uses said f.sub.Γ

(C∥

O∥

N), Ω

_j1 . . . jq (q=1, . . . t) and N to make a check to see if said X satisfies the following relation ##EQU5## where d represents the value of either one of ±

1 and ±

2;

(7-4) wherein when all of said verifications succeed, said third party generates an inquiry E_i ε

{0,1},where i=1, . . . K'"'"' and sends it to said user;

(7-5) wherein said user uses said electronic cash C, said node value (1, j₁ . . . j_t) corresponding to the amount of money spent, said information N and said secret information P and Q to calculate

space="preserve" listing-type="equation">Λ

.sub.i =<

f.sub.Λ

(C∥

j.sub.1 ∥

. . . ∥

i∥

N)>

.sub.QR

and uses said N, P, Q, Λ

_i and E_i to calculate

space="preserve" listing-type="equation">Y.sub.i = Λ

.sub.i.sup.1/2 mod N!.sub.(-1).spsb.E.sub.1

and sends it to said third party;

(7-6) wherein said third party makes a check to see if said information Y_i satisfies

space="preserve" listing-type="equation">(Y.sub.i /N)=(-1).sup.Ei

and verifies said C, i, j₁ . . . j_t, N and Y_i to see whether they satisfy

space="preserve" listing-type="equation">Y.sub.i.sup.2 .tbd.d'"'"'f.sub.Λ

(C∥

j.sub.1 ∥

. . . ∥

j.sub.t i∥

N)(mod N)

where d'"'"'=±

1 or ±

2;

and, when said verification succeeds, said third party accepts said I, N, X, B, b, C, j₁ . . . j_t, E_i and Y_i as the amount of money corresponding to said node j_i1 . . . ,j_t ;

where symbols in the above are defined as follows;

space="preserve" listing-type="equation"><

Z>

.sub.QR =dzmod N

such that dε

{±

1, ±

2}, where dz mod N are quadratic residues;

space="preserve" listing-type="equation"> x.sup.1/2 mod N!.sub.1 =y'"'"'

such that y'"'"'² =x mod N, (y'"'"'/N)=1 and 0<

y'"'"'<

N/2, where 1≦

t, and

space="preserve" listing-type="equation"> x.sup.1/2 mod N!.sub.-1 =y"

such that Y"² =x mod N, (y"/N)=-1 and 0<

y"<

N/2, where 1<

t₀.

6. The method of claim 4, wherein said secret information is composed of prime numbers P and Q that bear a relationship N=P×

Q;

wherein in said step (5) said user calculates a one-way function g(B∥

b) from said random number R and said license B, then performs blind signature preprocessing Z=F_eC (g(B∥

b)) for said one-way function g(B∥

b) and sends said second institution the resulting information Z as information containing said electronic cash C, together with said amount information A;

wherein in said step (6) said second institution uses a secret key corresponding to said amount A of said electronic cash C to calculate a signature Θ

=D_eC (Z) and sends it to said user;

wherein in said step (7) said user performs blind signature postprocessing C=G_eC (Θ

) for said received signature Θ

to obtain said electronic cash of said amount A; and

wherein the procedure for the payment to said third party comprises the steps;

(7-1) wherein said user calculates

space="preserve" listing-type="equation">Γ

.sub.O =<

f.sub.Γ

(C∥

O∥

N)>

.sub.QR

from said C, N, P and Q and generates

space="preserve" listing-type="equation">Ω

.sub.j.sbsb.1 .sub.. . . j.sbsb.q =<

f.sub.Ω

(C∥

j.sub.1 ∥

. . . ∥

j.sub.q ∥

N)>

.sub.1,

from said electronic cash C and the node j₁ . . . j_t and calculates from said Γ

₀, Ω

_j1 . . . jq, N, P and Q, a radical root of a node value corresponding to the amount spent ##EQU6## where q=1, . . . ,t;

(7-2) wherein said user sends said I, N, X_j1 . . . jt, B, b, c and j₁, . . . ,j_t to said third party;

(7-3) wherein said third party verifies the validity of said license B for information (I,N) by checking said license B to see if it satisfies

space="preserve" listing-type="equation">V.sub.eB ((N,I),B)=OK

and verifies the validity of said electronic cash C for information (B,b) by checking said electronic cash to see if it satisfies

space="preserve" listing-type="equation">V.sub.eC (g(B∥

b),C)=OK

and, when said license B and said electronic cash C are valid, letting (a/b) represent a Jacobi symbol, said third party makes a check to see if

space="preserve" listing-type="equation">(X/N)=-1

is satisfied, after which said third party calculates from said C and N

space="preserve" listing-type="equation">f.sub.Γ

(C∥

O∥

N),

and calculates from said C, j₁ . . . j_q and N

space="preserve" listing-type="equation">Ω

.sub.j.sbsb.1 .sub.. . . j.sbsb.q =<

f.sub.Ω

(C∥

j.sub.1 ∥

. . . ∥

j.sub.q ∥

N)>

.sub.1,

where q=1, . . . ,t, and, further, uses f.sub.Γ

(C∥

O∥

N), Ω

_j1 . . . jq

(q=1, . . . ,t) and N to make a check to see if said X satisfies the following relation ##EQU7## where d represents the value of either one of ±

1 and ±

2;

(7-4) wherein when all of said verifications succeed, said third party generates an inquiry Eε

Z_U ={0,1, . . . ,u-1} and sends it to said user;

(7-5) wherein said user uses said electronic cash C, said node value (1, j₁ . . . j_t) corresponding to the amount of money spent, said information N and said secret information P and Q to calculate

space="preserve" listing-type="equation">Λ

.sub.j.sbsb.1 .sub.. . . j.sbsb.t =<

f.sub.Λ

(C∥

j.sub.1 ∥

. . . ∥

j.sub.t ∥

N)>

.sub.QR

and uses said N, P, Q, Λ

_i and E_i to calculate ##EQU8## and sends it to said third party;

(7-6) wherein said third party makes a check to see if said information Y_j1 . . . jt satisfies ##EQU9## and verifies said C, i, j₁ . . . j_t, N and Y_i to see whether they satisfy

space="preserve" listing-type="equation">Y.sub.j.sbsb.1.sup.2.spsp.U .sub.. . . j.sbsb.t .tbd.d'"'"'f.sub.Λ

(C∥

j.sub.1 ∥

. . . ∥

j.sub.t ∥

N)(mod N)

where d'"'"'=±

1 or ±

2;

and, when said verification succeeds, said third party accepts said I, N, X, B, b, C, j₁ . . . j_t, E_i and Y_i as the amount of money corresponding to said node j₁, . . . ,j_t ;

where symbols in the above are defined as follows;

space="preserve" listing-type="equation"><

Z>

.sub.QR =dzmod N

such that dε

{±

1, ±

2}, where dz mod N are quadratic residues;

space="preserve" listing-type="equation"> x.sup.1/2.spsp.t mod N!.sub.1 =y'"'"'

such that y'"'"'².spsp.t =x mod N, (y'"'"'/N)=1 and 0<

y'"'"'<

N/2, where 1≦

t, and

space="preserve" listing-type="equation"> x.sup.1/2.spsp.t mod N!.sub.1 =y"

such that y"².spsp.t =x mod N, (y"/N)=1 and 0<

y"<

N/2, where 1<

t₀.

7. The method of claim 5 or 6, wherein letting (e_B,n_B) represent a public key of an RSA scheme used by said first institution and setting

8. The method of claim 5 or 6, wherein letting (e_C,n_C) represent a public key of an RSA scheme used by said first institution, setting

13. An institution apparatus which issues a license and electronic cash in accordance with a method for implementing traceable electronic cash, said apparatus comprising:

pseudonym generating means which receives from a user public information N and information containing the user'"'"'s real name ID_U and generates a pseudonym I corresponding to said real name ID_U ;

correspondence storage means which holds a table representing a correspondence between said real name ID_U and at least one of said pseudonym I and said public information N;

license signing means which uses a secret key for a license to sign, with a first signing function D_eB, information containing said public information and said pseudonym I and sends said user the signed information as information containing a license B; and

electronic cash signing means which signs, with a second signing function D_eC, said information received from said user and containing said license B and sends said user said signed information as electronic cash information.

14. The apparatus of claim 13, further comprising first and second institutions, said first institution including said pseudonym generating means and said correspondence storage means and said license signing means and said second institution including said electronic cash signing means.

15. The apparatus of claim 14, wherein said first institution includes a plurality of departments, said plurality of departments respectively have association memories for storing tables representing the correspondence between said real name ID_U of said user and at least one of said pseudonym I and said public information N by the use of sequentially corresponding pieces of association information α

so that the correspondence between at least one of said pseudonym I and said public information N and said real name ID_U becomes available through said pieces of association information α

only when said plurality of departments cooperate with each other.

16. The apparatus of claim 14 or 15, wherein said first and second institutions each form part of the same bank.

17. The apparatus of claim 14 or 15, wherein said first institution is a trustee and said second institution is a bank different from said trustee.

18. The apparatus of claim 15, wherein said plurality of departments of said first institution are a plurality of trustees and said second institution is a bank different from said plurality of trustees.