Electronic cash implementing method using a trustee

• US 5,901,229 A
• Filed: 11/04/1996
• Issued: 05/04/1999
• Est. Priority Date: 11/06/1995
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Okamoto, Tatsuaki, Fujisaki, Eiichiro, Ohta, Kazuo
• Primary Examiner(s): CAIN, DAVID C
• Application Number:
  US08/744,856
• Time in Patent Office: 911 Days
• Field of Search: 380/30, 380/28, 380/23, 380/24, 380/25
• US Class Current: 380/30
• 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/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: G06Q 20/403 Solvency checks
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• 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 an electronic cash implementing method using a trustee, a user registers his identification information ID_U and anonymous public key N with the trustee and receives a license (B,I). The user processes the license (B,I) by a public key corresponding to the amount to be issued and sends the processed information to a bank to have it attach a blind signature to the information so that the user obtain electronic cash C from the blind signature. The user transmits to a shop the information B,I,C,N and a digital signature that assures the divisional use of the electronic cash. The shop verifies the validity of the information B and C and accepts it as cash and sends a history H of communication with the user to the bank and receives a payment therefrom. The bank places all received communication histories under its supervision and makes a check to see if the amount x spent by the electronic cash C is in excess of its face value X, and if so, informs the trustee of the information N contained in the communication history. The trustee uses the information ID_U thus received to specify the corresponding user identification information ID_U.

Claims

1. An electronic cash implementing method for an electronic cash system which contains a trustee and a bank, said method comprising steps:

(1) wherein a user transmits his user identification information and an anonymous public key to said trustee;

(2) wherein said trustee stores the correspondence of said user identification information and said anonymous public key as a correspondence table in secrecy and generates and transmits a digital signature B of said trustee corresponding to said anonymous public key to said user;

(3) wherein said user stores said digital signature B of said trustee as a license, shows said license and a face value X to said bank and requests said bank to issue electronic cash C of said face value X; and

(4) wherein said bank issues to said user, by a blind signature, said electronic cash C associated with said license and corresponding to said face value X.

2. The method of claim 1, further comprising steps:

(5) wherein said user shows said anonymous public key, said license and said electronic cash to a shop and uses said anonymous public key to generate a payment signature S assuring the payment of the amount of money spent and provides said signature to said shop; and

(6) wherein said shop delivers payment history information H to said bank to settle therewith an account and obtain an amount of money corresponding to said amount spent.

3. The method of claim 2, further comprising a step wherein said bank makes a check to see if the total amount paid by said electronic cash is smaller than said face value X, and if so, extracts at least said anonymous public key of a history of all payments by said electronic cash and transmits it to said trustee.

4. The method of claim 1 or 2, further comprising a step wherein, wshen receiving an official order or permission of a third party, said bank and said trustee each retrieve one of identification information and anonymous public key of a user specified by said third party from said communication history placed under the supervision of said bank and said correspondence table held under the supervision of said trustee and inform said third party of said retrieved identification information and anonymous public key.

5. The method of claim 1, further comprising the steps:

(5) wherein a first user as said user shows said license and electronic cash C of said first user to a second user; and

(6) wherein said first user uses his anonymous public key N₁ to generate a transferring signature which assures the transferring of a divided amount x smaller than said face value X and providing said transferring signature to said second user.

6. The method of claim 5, further comprising a step wherein said second user shows to a shop a history of sa4d electronic cash at the time of transferring and said license of said second user and uses an anonymous public key N₂ of said second user to generate a signature assuring the payment of an amount y smaller than said divided amount and provides it to said shop to make the payment thereto.

7. The method of claim 1, wherein said digital signature in said step (2) is generated by a digital signature method based on an RSA scheme, and said blind signature in said step (4) is generated by a blind signature method based on said RSA scheme.

8. The method of claim 2, wherein said payment signature in said step (5) is generated by a digital signature method based on an RSA scheme.

9. The method of claim 5, wherein said transferring signature in said step (6) is generated by a digital signature method based on an RSA scheme.

10. The method of claim 1, wherein said digital signature in said step (2) is generated by a digital signature method based on an RSA scheme and said blind signature in said step (4) is generated by a blind signature method based on zero-knowledge interactive proof.

11. The method of claim 2, wherein said payment signature in said step (5) is generated by a digital signature method based on an ESIGN scheme.

12. The method of claim 7, wherein:

in said step (1), said user;

generates two large prime numbers P and Q;

uses said prime numbers to calculate a composite number N=P×

Q as said anonymous public key;

makes the following modular inverse calculation

space="preserve" listing-type="equation">d=e.sup.-1 mod LCM(P-1,Q-1)

from said prime numbers P and Q and a key e common to all users, LCM(a,b) representing a least common multiple;

stores d and N in a memory; and

transmits N to a trustee;

in step (2), said trustee;

keeps the correspondence of said user and said N as said correspondence table in secrecy;

generates information I on the term of validity or the like;

generates, by one-way function g-calculation and modular exponential calculation, said digital signature expressed by the following equation

space="preserve" listing-type="equation">B=g(N∥

I).sup.d.sbsp.W mod n.sub.B

through use of a secret key (d_B,n_B) for signature of said trustee; and

transmits said signature B and said information I to said user;

in step (3), said user;

stores information (B,I,N) from said trustee as said license in a memory;

generates and stores a random value b in said memory;

calculates a one-way function g(B∥

b) from said random value b and said license (B,I,N) read out of said memory;

calculates the following equation

space="preserve" listing-type="equation">Z=g(B∥

b)r.sup.e.sbsp.C mod n.sub.C

through use of public information (e_C,n_C) of said bank corresponding to said face value; and

transmits said information Z to said bank, together with said amount information of said electronic cash; and

in said step (4), said bank;

calculates the following equation

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

=Z.sup.d.sbsp.C mod n.sub.C

through use of said Z received from said user and a secret key (d_C,n_C) corresponding to said face value of said electronic cash; and

transmits said information Θ

to said user; and

said user calculates the following equation

space="preserve" listing-type="equation">C=Θ

/r mod n.sub.C

through the use of said information Θ

received from said bank and said public key (e_C,n_C), thereby obtaining said electronic cash C of said specified face value.

13. The method of claim 8, wherein said step (5) comprises the steps:

(5-1) wherein said user sends information {I,N,B,b,C} to said shop;

(5-2) wherein said shop;

verifies the validity of said digital signature B for information (I,N) by checking whether said B satisfies

space="preserve" listing-type="equation">B.sup.e.sbsp.B .tbd.g(N∥

I)(mod n.sub.B)

through use of a public key (e_B,n_B) for signature of said trustee;

verifies the validity of said electronic cash C for information (B,b) by checking whether said C satisfies the following equation

space="preserve" listing-type="equation">C.sup.e.sbsp.C =g(B∥

b)(mod n.sub.C)

through the use of said public key (e_C,n_C) of said bank;

when either verification fails, halts subsequent processing;

when either verification succeeds, generates a random value E'"'"' and sends it to said user together with identification information ID_V and a time stamp T; and

calculates therefor E=h(ID_V ∥

T∥

E'"'"') through the use of a one-way function h;

(5-3) said user calculates the following equation

space="preserve" listing-type="equation">S=g(x∥

h(ID.sub.V ∥

T∥

E'"'"')).sup.d mod N

as a payment signature for the amount spent x of said electronic cash C and sid information received from said shop through the use of a secret key (d,N) of said user; and

sends said payment signature S and said information x to said shop; and

said step (6) comprises the steps;

(6-1) said shop makes a check to see if said amount spent x is smaller than said face value X of said electronic cash C;

when said check does not pass, halts subsequent processing; and

when said check passes, verifies the validity of said payment signature S by checking whether said S satisfies the following equation

space="preserve" listing-type="equation">S.sup.e .tbd.g(x∥

E)(mod N); and

(6-2) when this verification succeeds, said shop regards the payment of the amount corresponding to said amount x as being valid and receives it from said user.

14. The method of claim 9, wherein:

said step (5) comprises the steps;

(5-1) said first user sends said license (B₁,I₁,N₁) and said electronic cash (b,C) to said second user;

(5-2) said second user;

verifies the validity of a signature B1 for said (I₁,N₁) by checking whether said B1 satisfies the following equation

space="preserve" listing-type="equation">B.sup.e.sbsp.B .tbd.g(N.sub.1 ∥

I.sub.1)(mod n.sub.B);

verifies the validity of said electronic cash C for said (B₁,b) by checking whether said C satisfies the following equation

space="preserve" listing-type="equation">C.sup.e.sbsp.C .tbd.g(B.sub.1 ∥

b)(mod n.sub.C);

when either one of these checks does not pass, halts subsequent processing; and

when both checks pass, generates a random value E₂ '"'"' and sends it to said first user together with a signature B₂ for said second user, and calculates E=h(B₂ ∥

T∥

E₂ '"'"'); and

said step (6) comprises the steps;

(6-1) said first user calculates a signature S₁ for said amount x to be divided from said electronic cash C by the following equation

space="preserve" listing-type="equation">S.sub.1 =g(x∥

h(B.sub.2 ∥

T∥

E.sub.2 '"'"')).sup.d.sbsp.1 mod N.sub.1 ; and

sends said signature S₁ and said amount x to said second user; and

(6-2) said second user makes a check to see if said amount x is smaller than the maximum amount X of said electronic cash C;

when this check does not pass, halts subsequent processing;

when said check passes, verifies the validity of said signature S₁ by checking whether said S₁ satisfies the following equation

space="preserve" listing-type="equation">S.sub.1.sup.e.sbsp.1 .tbd.g(x∥

E)(mod N.sub.1); and

when this check passes, said second user regards the transferring of the amount worth said amount x from said first user as being valid and receives it.

15. The method of claim 14, further comprising the steps:

(7) said second user sends to a shop said second license (B₂,I₂,N₂) and a history H₁ (I₁,B₁,N₁,B₁,b,C,x,T,E₂ '"'"',S₁) of communications conducted with said first user when electronic cash was transferred;

(8) said shop;

verifies the validity of said signature B₂ of said second user for (I₂,N₂) by checking whether said B₂ satisfies the following equation

space="preserve" listing-type="equation">B.sub.2.sup.e.sbsp.B .tbd.g(N.sub.2 ∥

I.sub.2) (mod n.sub.B);

and verifies the validity of said communication history H₁ ;

when either one of these checks does not pass, halts subsequent processing;

when said checks both pass, generates a random value E'"'"' and sends it to said second user together with identification information ID_V '"'"' and a time stamp T'"'"' and calculates

space="preserve" listing-type="equation">E.sub.V =H(ID.sub.V ∥

T'"'"'∥

E.sub.V '"'"');

(9) said second user;

generates a signature S₂ for an amount y to be divided from said transferred amount x for spending, by the following equation

space="preserve" listing-type="equation">S.sub.2 =g(y∥

h(ID.sub.V ∥

T'"'"'∥

E.sub.V '"'"')).sup.d.sbsp.2 mod N.sub.2

and sends said signature S₂ and said amount x to said shop;

(10) said shop;

makes a check to see if said amount y is smaller than the amount x to be divided from said electronic cash C for transferring;

when this verification fails, halts subsequent processing;

when said verification succeeds, verifies the validity of said signature S₂ by checking whether said S₂ satisfies the following equation

space="preserve" listing-type="equation">S.sub.2.sup.e.sbsp.2 .tbd.g(y∥

E.sub.V)(mod N.sub.2);

when this verification succeeds, regards the payment of the amount worth y and receives it from said second user.

16. The method of claim 10, wherein:

in said step (1), said user;

generates two large prime numbers P and Q;

uses said prime numbers to calculate a composite number N=P² ×

Q as said anonymous public key;

stores d and N in a memory; and

transmits N to a trustee;

in step (2), said trustee;

keeps the correspondence of said user and said N as said correspondence table in secrecy;

generates information I on the term of validity or the like;

calculates the following equation

space="preserve" listing-type="equation">B.tbd.g(N∥

I).sup.d.sbsp.B mod n.sub.B

through use of a secret key (d_B,n_B) for signature of said trustee; and

transmits said B and said information I to said user;

in said step (3), said user;

(3-1) stores information (B,I,N) from said trustee as a license in a memory;

(3-2) said bank responds to a request of said user for withdrawal of said electronic cash to generate a random value r, calculates the following equation

space="preserve" listing-type="equation">a'"'"'=r.sup.L.sbsp.C mod n.sub.C

and transmits it to said user;

(3-3) said user generates random value r'"'"' and b, calculates the following equation

space="preserve" listing-type="equation">a=a'"'"'r'"'"'.sup.L.sbsp.C hc.sup.b mod n.sub.C

and stores it in a memory, calculates the following equation

space="preserve" listing-type="equation">c=g(B∥

a)mod n.sub.C

and stores it in a memory, and calculates the following equation

space="preserve" listing-type="equation">c'"'"'=c+b mod L.sub.C

and transmits it to said bank;

in said step (4), said bank;

(4-1) calculates the following equation

space="preserve" listing-type="equation">y'"'"'=rx.sub.C.sup.C mod n.sub.C

through the use of a public key (h_C, L_C,n_C) corresponding to the face value of said electronic cash and a secret key x_C, transmits it to said user, and at the same time, withdraws the amount concerned from the account of said user, or receives said amount from said user by some other means; and

(4-2) said user calculates d which satisfies the following equation

space="preserve" listing-type="equation">c'"'"'=c+b+dL

and calculates the following equation

space="preserve" listing-type="equation">y=y'"'"'r'"'"'h.sup.-d mod n.sub.C

and stores it in a memory together with a and c in the form of electronic cash C=(a,c,y).

17. The method of claim 11, wherein:

said step (5) comprises the steps;

(5-1) said user sends I, N, B, C to said shop;

(5-2) said shop verifies the validity of a signature B for (I,N) by checking whether said B satisfies the following equation

space="preserve" listing-type="equation">B.sup.e.sbsp.B .tbd.g(N∥

I)(mod n.sub.B)

through the use of a public key (e_B,n_B) for signature of said trustee and verifies the validity of said electronic cash for said signature B by checking whether said C satisfies the following equation

space="preserve" listing-type="equation">y.sup.L.sbsp.C .tbd.ah.sup.C (mod n.sub.C)

space="preserve" listing-type="equation">c=g(B∥

a)

when this verification fails, halts subsequent processing;

when this verification succeeds, said shop generates a random value E'"'"' and sends it to said user together with identification information ID_V and a time stamp T and calculates E=h(ID_V ∥

T∥

E'"'"') by using a one-way function h; and

(5-3) said user;

determines that he spends an amount x in said electronic cash C, calculates the following equation

space="preserve" listing-type="equation">m=x∥

h(ID.sub.V ∥

T∥

E'"'"')

and generates an ESIGN signature S by the following equation

space="preserve" listing-type="equation">S=E.sub.SIG (m,p,q)

through the use of a secret key (p,q) of said user and sends said amount x and said signature S to said shop; and

said step (6) comprises the steps;

(6-1) said shop makes a check to see if said amount x is smaller than the maximum amount x of said electronic cash C;

when this check fails, halts subsequent processing;

when the check passes, verifies the validity of said ESIGN signature S by the following equation

space="preserve" listing-type="equation">E.sub.VER (m,S,N)=OK/NG

through the use of said pieces of information m, S and N; and

when this verification succeeds, said shop regards the payment of an amount worth said x as being valid and receives it from said user.

18. The method of claim 17, further comprising the steps:

(7) said shop presents to said bank a history H of communication conducted with said user for the spending of said electronic cash;

(8) said bank verifies the validity of said communication history H and, when this verification succeeds, stores the history H and pays an amount concerned into an account of said shop, or pays said amount to said shop by some other means;

(9) said bank places said history H under its supervision to prevent said electronic cash C from being spent in excess of the maximum amount X and, if said cash C is spent in excess of the maximum amount X, presents a history of all payments by said electronic cash C as evidence of an attack; and

(10) said trustee finds out said user'"'"'s name from said correspondence table on the basis of said N contained in said communication history H and identifies the attacker.

19. The method of claim 1, wherein said trustee is composed of a plurality of institutions, and said step (2) is a step of storing the correspondence of said user identification information ID_U and said anonymous public key N as information distibuted among said plurality of institutions.

20. The method of claim 19, wherein in said step (2), said plurality of institutions store the correspondence of said user identification information ID_U and said anonymous public key N in a sequentially corresponding manner by different pairs of sequentially associated pieces of information so that only when said plurality of institutions cooperate, the correspondence of said anonymous public key N and said identification information ID_U can be detected from said associated pieces of information.

21. The method of claim 20, wherein said plurality of institutions are t institutions 40T₁ to 40T_t, and said step (1) comprises the steps:

(1-1) wherein said user generates keys k₁ to k_t in a one-to-one correspondence with said t institutions 40T₁ to 40T_t when said user registers said anonymous public key N with said t institutions;

(1-2) wherein said user uses a public key cryptography function E_i of each institution 40T_i to recursively calculate φ

=E_i (k_i ∥

φ

_i-1) for 1≦

i≦

1 to ultimately obtain φ

_t, φ

₀ being the identification information ID_U of said user; and

(1-3) wherein said user recursively calculates Φ

₁ =E₁ o . . . oE_t (N∥

φ

_t), where E_i oE_j (x) represents E_i (E_j (x)), said Φ

₁ being transmitted to said first institution 40T₁ ; and

said step (2) comprises the steps;

(2-1) said first institution uses a public key decryption function D₁ to calculate Φ

₁ =D₁ (Φ

₁) and transmits it to said second institution 40T₂, and for i=1, . . . t-1, said each institution 40T_i uses the public key decryption function D_i to calculate Φ

_i+1 =D_i (Φ

_i) and transmits it to said institution 40T_i+1 so that said institution 40T_t ultimately obtain Φ

_t ;

(2-2) said institution 40T_t uses said public key decryption function D_t to calculate (N∥

φ

_t)=D_t (Φ

_t) from Φ

_t and (k_t ∥

φ

_t-1)=D_t (φ

_t) from φ

_t and finally obtains (N,φ

_t-1,k_t);

(2-3) said institution 40T_t generates a digital signature for said anonymous public key N, encrypts said digital signature B into Ψ

_t =ε

_kt (B), using k_t as a secret key, stores N, B and φ

_t in a memory and transmits (φ

_t-1,φ

_t) to said institution 40T_t-1 ;

(2-4) wherein said institution 40T_i calculates (k_i ∥

φ

_i-1)=D_i (φ

_i) from φ

_i, encrypts Ψ

_i+1 into Ψ

_i =e_ki (Ψ

_i+1) by using k_i as a secret key, then stores a pair of associated pieces of information (Ψ

_i, Ψ

_i+1) and transmits (φ

_i-1, Ψ

_i) to said institution 40T_i-1, this sequence of operations being repeated for i=t-1,t-2, . . . , t so that said institution 40T_t ultimately obtains (φ

₁, Ψ

₂);

(2-5) wherein said institution 40T₁ calculates (k₁ ∥

I D_U)=D₁ (φ

₁) from φ

_i, identifies said user on the basis of said identification information ID_U, calculates Ψ

₁ =ε

_k1 (Ψ

₂) from k₁ and Ψ

₂, stores ID_U, Ψ

₂ and Ψ

₁ in a memory 40M₁ and transmits Ψ

₁ to said user; and

(2-6) wherein said user obtains said digital signature B from said trustee by the following equation

space="preserve" listing-type="equation">B=δ

.sub.kt o . . . oδ

.sub.k1 (Φ

.sub.1)=g(N).sup.d.sbsp.T mod n.sub.T

through the use of decryptors for (k₁, . . . , k_t) and ε

.

22. The method of claim 1, wherein said trustee is composed of t independent institutions 40T₁ to 40T_t, t being an integer equal to or greater than 2, and which further comprises the step wherein, when getting electronic cash issued by said bank, said user generates a random value λ

corresponding to said electronic cash C and t-1 random values λ

₁, . . . , λ

_t-1 and calculates E₁ (λ

(1)), . . . , E_t (λ

(t)) for said t institutions by using public key encryptors E₁, . . . , E_t, where λ

(x)=λ

+λ

x+ . . . +λ

_t-1 x^t-1 mod r, said E₁ (λ

(1)), . . . , E_t (λ

(t)) being transmitted to each of said t institutions.

23. The method of claim 22, further comprising the step where, when receiving an official request or permission from a third party, said t institutions cooperates to decrypt said random values λ

and write them into a database.

24. The method of claim 23, wherein said random value decryption processing comprises processing by which said t institutions respectively extract pieces of secret information λ

(1), . . . , λ

(t) from said E₁ (λ

(1)), . . . , E_t (λ

(t)) by the corresponding public keys and calculate, from said pieces of secret information and a parameter r, λ

₁, . . . , λ

_t-1 which satisfy the following equation

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

(x)=λ

+λ

.sub.1 x+ . . . +λ

.sub.t-1 x.sup.t-1 mod r.