Method and apparatus for implementing traceable electronic cash

Claim 3

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 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 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 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 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.

Claim 4

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.

Claim 7

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 Γ.sub.0 =<f.sub.Γ (C∥O∥N)>.sub.QR from said C, N, P and Q and generates Ω.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 1 . . . j q and calculates from said Γ 0 , Ω 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 1 , . . . ,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 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 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 (X/N)=-1 is satisfied, after which said third party calculates from said C and N f.sub.Γ (C∥O∥N), and calculates from said C, j 1 . . . j q and N Ω.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 1 . . . j t ) corresponding to the amount of money spent, said information N and said secret information P and Q to calculate Λ.sub.i =<f.sub.Λ (C∥j.sub.1 ∥ . . . ∥i∥N)>.sub.QR and uses said N, P, Q, Λ i and E i to calculate 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 (Y.sub.i /N)=(-1).sup.Ei and verifies said C, i, j 1 . . . j t , N and Y i to see whether they satisfy 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 1 . . . 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: <Z>.sub.QR =dzmod N such that dε{±1, ±2}, where dz mod N are quadratic residues; x.sup.1/2 mod N!.sub.1 =y' such that y' 2 =x mod N, (y'/N)=1 and 0<y'<N/2, where 1≦t, and x.sup.1/2 mod N!.sub.-1 =y" such that Y" 2 =x mod N, (y"/N)=-1 and 0<y"<N/2, where 1<t 0 .

Claim 8

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 Γ.sub.O =<f.sub.Γ (C∥O∥N)>.sub.QR from said C, N, P and Q and generates Ω.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 1 . . . j t and calculates from said Γ 0 , Ω 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 1 , . . . ,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 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 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 (X/N)=-1 is satisfied, after which said third party calculates from said C and N f.sub.Γ (C∥O∥N), and calculates from said C, j 1 . . . j q and N Ω.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 1 . . . j t ) corresponding to the amount of money spent, said information N and said secret information P and Q to calculate Λ.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 1 . . . j t , N and Y i to see whether they satisfy 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 1 . . . j t , E i and Y i as the amount of money corresponding to said node j 1 , . . . ,j t ; where symbols in the above are defined as follows: <Z>.sub.QR =dzmod N such that dε{±1, ±2}, where dz mod N are quadratic residues; x.sup.1/2.spsp.t mod N!.sub.1 =y' such that y' 2 .spsp.t =x mod N, (y'/N)=1 and 0<y'<N/2, where 1≦t, and x.sup.1/2.spsp.t mod N!.sub.1 =y" such that y" 2 .spsp.t =x mod N, (y"/N)=1 and 0<y"<N/2, where 1<t 0 .

Claim 9

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 n.sub.B =P×Q, e.sub.B ×d.sub.B .tbd.1(mod L) and L=LCM{(P-1),(Q-1)}, said signature attached by said first institution to said information (N,I) in said step (3) is carried out by the following calculation D.sub.eB (N,I)=(N,I).sup.dB mod n.sub.B and said verification of the validity of said license B for said information (N,I) in said step (7-3) succeeds when the following equation is satisfied: (N,I).tbd.B.sup.eB (mod n.sub.B).

Claim 10

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 n.sub.C =P×Q, e.sub.C ×d.sub.C .tbd.1(mod L) and L=LCM{(P-1),(Q-1)}, setting the function of said blind signature preprocessing F eC by said user in said step (5) as follows: Z=F.sub.eC (m)=r.sup.eC ×m mod n.sub.C, setting the function of said signature D eC by said second institution in said step (6) as follows: Θ=D.sub.eC (Z)=Z.sup.dC mod n.sub.C and setting the function of said blind signature postprocessing G eC by said user in said step (7) as follows: C=G.sub.eC (Θ)=Θ/r mod n.sub.C, said verification of the validity of said electronic cash C for said information (B,b) by said third party in said step (7-3) succeeds when the following equation is satisfied: (B,b).tbd.C.sup.eC (mod n.sub.C).

Claim 11

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

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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

Claim 20

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.

Claim 21

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.