Method and apparatus for implementing electronic cash

• US 4,977,595 A
• Filed: 03/28/1990
• Issued: 12/11/1990
• Est. Priority Date: 04/03/1989
• Status: Expired due to Term

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Ohta, Kazuo, Okamoto, Tatsuaki
• Primary Examiner(s): Buczinski, Stephen C.
• Assistant Examiner(s): GREGORY, BERNARR E
• Application Number:
  US07/500,555
• Time in Patent Office: 258 Days
• Field of Search: 340/825.31, 340/825.34, 235/379, 235/381
• US Class Current: 705/69
• 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/0855 involving a third party
• CPC Class Codes: G06Q 20/29 characterised by micropayments
• CPC Class Codes: G06Q 20/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/3825 Use of electronic signatures
• 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/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/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3257 using blind signatures

Abstract

In an electronic cash implementing method, a user makes a bank apply a blind signature to user information Vi produced, by a one-way function, from secret information Si containing identification information, thereby obtaining signed user information. Further, the user makes the bank apply a blind signature to information containing authentication information Xi produced, by a one-way function, from random information Ri, thereby obtaining signed authentication information. The user uses an information group containing the signed user information, the signed authentication information, the user information and the authentication information, as electronic cash for payment to a shop. The shop verifies the validity of the signed user information and the signed authentication information, and produces and sends to the user an inquiry. In response to the inquiry the user produces a response Yi by using secret information and random information and sends it to the shop. Having verified the validity of the response the shop accepts the electronic cash.

Claims

1. An electronic cash implementing method in which a bank issues electronic cash to a user, said user pays a third party with said electronic cash, and said bank settles accounts with a party who finally possesses said used electronic cash, said method comprising the following steps:

wherein said user;

(a) generates user information based on secret information containing identification information of his own, through utilization of a first one-way function;

(b) obtains signed user information by having said bank apply blind signature to information containing said user information;

(c) generates authentication information based on random information through utilization of a second one-way function;

(d) obtains signed authentication information by having said bank apply blind signature to information containing said authentication information;

(e) sends, as said electronic cash issued by said bank, electronic cash information containing said user information, said signed user information, said authentication information and said signed authentication information to said third party;

wherein said third party;

(f) verifies the validity of said signed user information and said signed authentication information contained in said electronic information received from said user;

(g) if said validity is verified, generates and sends an inquiry to said user;

wherein said user;

(h) generates a response based on at least said secret information generated by himself and said inquiry received from said third party and sends said response to said third party;

wherein said third party;

(i) verifies the validity of said response through utilization of said user information and said authentication information contained in said electronic cash information received from said user and, if said response is valid, receives said electronic cash as valid one;

(j) sends said electronic cash information, said inquiry of said third party, and said response of said user to a fourth party, as required.

2. The electronic cash implementing method of claim 1 including a step wherein having when received, from a final party who possesses said used electronic cash, information containing said electronic cash information, said inquiry generated by said third party and said response generated by said user for settlement of accounts, said bank verifies the validity of said signed user information and said signed authentication information contained in said electronic cash information and the validity of said response to said user to said inquiry of said third party.

3. The electronic cash implementing method of claim 2, wherein the step for settlement of accounts includes a step wherein said bank:

detects invalid usage of said electronic cash by said user by checking whether or not a pair of pieces of information of the same values as the pair of said user information and said authentication information contained in said electronic cash exists in information stored in a memory of said bank; and

stores information containing said electronic cash information, said inquiry and said response in said memory.

4. The electronic cash implementing method of claim 2, wherein said user possesses said signed user information as a license issued by said bank;

in case of necessity, said user has said bank apply blind signature to information containing said authentication information and said license to obtain signed authentication information and uses said signed authentication information thus obtained, as an electronic coin issued by said bank;

when said user uses said electronic coin, he sends an information group containing at least said license, said electronic coin, said user information and said authentication information, as said electronic cash, to said third party; and

said third party and said bank verify the validity of said signed user information and said signed authentication information as the verification of the validity of said license and said electronic coin.

5. The electronic cash implementing method of claim 4, wherein said final party is said third party;

said fourth party is said bank; and

said inquiry generated by said third party contains identification information of said third party and time information.

6. The electronic cash implementing method of claim 4, wherein said third party has secret information and license of his own;

and wherein when having verified that said response from said user is valid, said third party sends said license of his own to said user, and said user signs said third party'"'"'s license and sends said signed license as a deed of transfer to said third party.

7. The electronic cash implementing method of claim 6, wherein said final party is said fourth party;

said fourth party receives from said third party at least said user'"'"'s license, said electronic coin, said user information, said authentication information and said response which have been presented by said user, and said third party'"'"'s license, said third party'"'"'s user information and said inquiry presented by said third party;

said fourth party;

verifies the validity of each of said user'"'"'s license and said electronic coin;

verifies the validity of said user'"'"'s response to said third party'"'"'s inquiry;

verifies the validity of said third party'"'"'s license;

generates an inquiry containing identification information of said fourth party himself and time information and sends said inquiry to said third party;

said third party;

generates a response based on said fourth party'"'"'s inquiry, said third party'"'"'s secret information and information generated based on said user'"'"'s authentication information and sends said response to said fourth party;

said fourth party;

verifies the validity of said third party'"'"'s response through utilization of said third party'"'"'s user information, said fourth party'"'"'s inquiry and said user'"'"'s authentication information; and

sends to said bank information containing said electronic cash information, said third party'"'"'s inquiry, said user'"'"'s response, said third party'"'"'s license, said third party'"'"'s user information, said fourth party'"'"'s inquiry and said third party'"'"'s response.

8. The electronic cash implementing method of claim 7, wherein said step for the settlement of accounts includes a step wherein said bank verifies the validity of said third party'"'"'s response to said fourth party'"'"'s inquiry;

a step wherein said bank detects invalid usage of said electronic coin by said third party by checking whether or not an information group of the same values as an information group of said user'"'"'s authentication information and said third party'"'"'s user information exists in information stored in said memory of said bank; and

a step wherein said bank stores the information including said electronic cash information, said third party'"'"'s inquiry and said user'"'"'s response into said memory.

9. The electronic cash implementing method of claim 4, wherein said bank permits said electronic coin to be used a predetermined number K of times;

in response to said third party'"'"'s inquiry in a j-th (where 1≦

j≦

K) use of said electronic coin, said user generates said response based on said user'"'"'s secret information and information calculated from said user'"'"'s authentication information through utilization of a one-way function which varies using said value J as a parameter, and said user sends said response and said value j to said third party; and

said third party verifies the validity of said response through use of said inquiry, said user'"'"'s authentication information, said user'"'"'s information and said value j, and inserts said value j into said information to be provided to said fourth party.

10. The electronic cash implementing method of claim 9, further including a step wherein when having verified that said response from said user is valid, said third party sends license of his own to said user;

said user signs said third party'"'"'s license and sends said signed license as a deed of transfer to said third party; and

said third party verifies the validity of said deed of transfer.

11. The electronic cash implementing method of claim 9 or 10, further including a step wherein said bank receives also said value j from said final party and detects invalid usage of said electronic coin by said user by checking whether or not an information group of the same values as the information group of said user information, said authentication information and said value j exists in the information stored in said memory of said bank.

12. The electronic cash implementing method of claim 1, 2 or 4, wherein said step of making said bank apply blind signature to said information containing said user information, includes:

a step wherein said user processes said information containing said user information with a one-way blind signature preprocessing function using a randomizing random number as a variable and sends said randomized information as randomized user information to said bank;

a step wherein said bank signs a part of said randomized user information with a signature function and returns said signed information as signed-randomized user information to said user; and

a step wherein said user removes the influence of said randomizing random number from said signed-randomized user information with a blind signature postprocessing function to thereby obtain said signed user information.

13. The electronic cash implementing method of claim 12, further including:

a step wherein said user generates k pieces of said secret information, k being an integer equal to or greater than 2, and k pieces of each of said user information and said randomized user information corresponding to said k pieces of secret information, respectively; and

a step wherein having received said k pieces of randomized user information, said bank demands said user to present a predetermined number of groups of data containing said secret information and said randomizing random numbers used for the generation of those of said randomized user information selected by said bank, calculates said selected pieces of randomized user information from said group of data obtained from said user and verifies that the calculated results each coincide with the corresponding one of said randomized user information received from said user.

14. The electronic cash implementing method of claim 13, wherein said part of randomized user information is a predetermined second number of pieces of said randomized user information other than those used for said verification and said bank sends said predetermined second number of pieces of said signed randomized user information to said user.

15. The electronic cash implementing method of claim 4, wherein said step of obtaining said license, includes a step wherein:

said user;

generates k, k being an integer equal to or greater than 2, pieces of secret information Si, each containing said identification information, generates k pieces of said user information Vi from k pieces of said secret information Si by use of said first one-way function, generates k pieces of said randomized user information Wi by applying, as a variable, information Mi containing said user information to a one-way first blind signature preprocessing function, and sends said k pieces of randomized user information Wi to said bank;

said bank;

selects a predetermined number k₁, k₁ being smaller than k, of pieces of said randomized user information from said k pieces of randomized user information Wi received from said user, and demands said user to present specified number of sets of information containing said secret information used by said user for generating said selected randomized user information;

said user;

sends said specified k₁ sets of information to said bank;

said bank;

calculates k₁ pieces of corresponding randomized user information Wi from said sets of information received from said user, verifies that these calculated pieces of randomized user information Wi'"'"' respectively coincide with corresponding pieces of said randomized user information Wi selected by said bank, confirms that said identification information IDp of said user is contained in each of pieces of said secret information Si in said sets of information received from said user, and generates a predetermined number k₂ of pieces of signed-randomized user information Ω

_i by signing, with a first signature function, k₂ pieces of said randomized user information among said k pieces of randomized user information Wi received from said user, except said selected k₁ pieces of randomized user information, and sends said k₂ pieces of signed-randomized user information Ω

_i to said user; and

said user;

obtained k₂ pieces of said signed user information Bi by derandomizing with a first blind signature postprocessing function each of said k₂ pieces of said signed-randomized user information Ω

_i received from said bank; and

wherein said user uses said k₂ pieces of signed user information as said license issued by said bank.

16. The electronic cash implementing method of claim 15, further including a step of issuing said electronic coin, wherein

said user generates k₂ pieces of said random information Ri, generates from said k₂ pieces of random information k₂ pieces of said authentication information Xi by use of said second one-way function, generates said randomized authentication information Z by applying, as a variable, information m containing k₂ pieces of said license Bi and k₂ pieces of said authentication information Xi to a one-way second blind signature preprocessing function, and sends said randomized authentication information Z to said bank;

said bank;

generates said signed-randomized authentication information Θ

by signing with a second signature function said randomized authentication information Z received from said user, and sends said signed-randomized authentication information Θ

to said user; and

said user;

obtains, as said electronic coin C, said signed authentication information by derandomizing said signed-randomized authentication information Θ

with a second blind signature postprocessing function.

17. The electronic cash implementing method of claim 16, further including a step wherein:

said user;

generates k prime numbers Li, k pairs of secret prime numbers Pi and Qi and k prime-number products Ni=Pi×

Qi, calculates k pieces of said user information Vi from k pieces of said secret information Si by said first one-way function expressed by the following equation;

Vi=Si^Li mod Ni,

where i=1, . . . , k.

18. The electronic cash implementing method of claim 17, further including a step wherein, supposing said k₂ items i=1, . . . , k₂,

said user:

generates k₂ pieces of said authentication information Xi by said second one-way function expressed by the following equation;

Xi=Ri^Li mod Ni,

wherein i=1, . . . , k₂.

19. The electronic cash implementing method of claim 18, wherein said final party is said third party and said fourth party is said bank, and further including a step wherein:

said user;

when using said electronic coin C, furnishes said third party with said electronic cash information containing said electronic coin C, k₂ pieces of said license Bi, k₂ pieces of said user information Vi and k₂ pieces of said authentication information xi, along with k₂ said prime numbers Li and k₂ pieces of said information Ni;

said third party;

generates said inquiry qi, furnishes said user with said inquiry qi, and calculates k₂ pieces of inquiry information Ei by an inquiry function Ei=f(qi);

said user;

generates inquiry information Ei from said inquiry qi by said inquiry function, generates k₂ pieces of said response Yi from said inquiry information Ei, said secret information Si and said random information Ri by the following equation;

space="preserve" listing-type="equation">Yi=Ri.Si.sup.Ei mod Ni,

wherein i=1, . . . , k₂,

and furnishes said third party with said response Yi; and

said third party;

verifies the valdity of said response Yi by checking it to ensure that a verification equation expressed by the following equation;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂, holds, by use of said inquiry information Ei generated by himself and said user information Vi and said authentication information Xi received from said user, and regards said electronic coin C as valid.

20. The electronic cash implementing method of claim 19, further including a step wherein:

said third party;

furnishes, for settlement of said electronic coin, said bank with information containing said electronic cash information {Vi, Xi, Bi, C}, said prime-number products Ni, said prime numbers Li, said inquiry qi and said response Yi;

said bank;

verifies the validity of said response Yi to said inquiry qi by checking that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂.

21. The electronic cash implementing method of claim 20, further including a step wherein said bank checks whether or not a pair of information of the same values as a pair of said user information and said authentication information {Vi, Xi} received from said fourth party exists in said memory of said bank;

if such a pair of information does not exist, said bank stores in said memory the information received from said fourth party; and

if such a pair of information exists, said bank reads out the corresponding inquiry qi'"'"' and response Yi'"'"' from said memory, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"' solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

calculates secret information Si by the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and detects from said calculated secret information Si identification information of said user who invalidly used said electronic coin.

22. The electronic cash implementing method of claim 18, wherein said final party is said fourth party, and further including a step wherein:

said user;

when sending said electronic coin to said third party, furnishes said third party with information containing said electronic cash information {Vi, Xi, Bi, C}, said prime-number products Ni and said prime numbers Li;

said third party;

generates k₂ pieces of said inquiry ε

_i and sends them to said user;

said user;

generates k₂ pieces of response Yi from said inquiry ε

_i, said random information Ri and said secret information Si by the following equation;

space="preserve" listing-type="equation">Yi=Ri.Si.sup.ε

.sbsp.i mod Ni,

where i=1, . . . , k₂,

and sends said k₂ pieces of response Yi to said third party;

said third party;

verifies the validity of said response by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

and furnishes said user with k₂ pieces of license Bi of said third party;

said user;

generates a deed of transfer T by applying a signature, with use of the prime-number Ni of said user, to said k₂ pieces of license Bi and sends said deed of transfer T to said third party.

23. The electronic cash implementing method of claim 22, further including a step wherein:

said third party;

when using said electronic coin, furnishes said fourth party with the information Ni, Li, said electronic cash information {Vi, X, Bi, C}, said deed of transfer T, said third party'"'"'s inquiry ε

_i, said user'"'"'s response Yi, said third party'"'"'s license Bi, and said third party'"'"'s prime-number products Ni, prime numbers Li and user information Vi used for generating said third party'"'"'s license Bi;

said fourth party;

verifies the validity of said response Yi of said user by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

generates an inquiry qi, sends said inquiry qi to said third party, and calculates inquiry information Ei from an inquiry function Ei=f(qi);

said third party calculates inquiry information Ei from said inquiry qi received from said fourth party by said inquiry function Ei=f(qi), generates a response Yi from the following equations;

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

=Xi.sup.1/Li mod Ni,

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.Si.sup.Ei mod Ni,

where i=1, . . . , k₂

and sends said response Yi to said fourth party; and

said fourth party;

verifies the validity of said response Yi of said third party by checking it, through use of said user'"'"'s authentication information Xi, to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂.

24. The electronic cash implementing method of claim 23, further including a step wherein:

said fourth party;

for settlement of said electronic coin, furnishes said bank with said electronic cash information {Vi, Xi, Bi, C}, pieces of the information Ni, Li and Yi of said user, said deed of transfer T, the information {Ni, Vi, Li, Bi, ε

_i, Yi} of said third party and said inquiry qi of said fourth party;

said bank;

verifies the validity of said response Yi of said user and said response Yi of said third party by checking them to ensure that the following equations hold;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni).

25. The electronic cash implementing method of claim 24, further including a step wherein said bank checks whether or not a pair of information of the same values as a pair of said user information and said authentication information {Vi, Xi} received from said fourth party exists in said memory of said bank;

if such a pair of information does not exist, said bank stores in said memory the information received from said fourth party; and

if such a pair of information exists, said bank reads out the corresponding inquiry qi'"'"' and response Yi'"'"' from said memory, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

calculates secret information Si from the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and detects from said calculated secret information Si the identification information of said user who invalidly used said electronic coin C.

26. The electronic cash implementing method of claim 24 or 25, further including a step wherein said bank checks whether or not a pair of information of the same values as a pair {Vi, Xi} of said user information Vi of said third party and said authentication information Xi of said user received from said fourth party, is stored in said memory of said bank;

if such a pair of information is not found, said bank stores in said memory the information received from said fourth party; and

if such a pair of information is found, said bank reads out the corresponding inquiry qi'"'"' of said fourth party and the response Yi'"'"' thereto of said third party from said memory, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

calculates secret information Si from the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and detects from said calculated secret information Si the identification information of said third party who invalidly used said electronic coin C.

27. The electronic cash implementing method of claim 18, wherein said bank allows said electronic coin to be used a predetermined number K of times, said final party is said third party and said fourth party is said bank, and further including a step wherein:

said user;

furnishes said third party with said electronic cash information {Vi, X, Bi, C} and information {Ni, Li} at the time of a j-th use of said electronic coin by said user, where 1≦

j≦

K;

said third party;

generates k₂ pieces of said inquiry qi, sends said inquiry qi to said user, and calculates inquiry information Ei by an inquiry function Ei=f(qi);

said user;

calculates said inquiry information Ei from said inquiry qi by said inquiry function Ei=f(qi), generates said response Yi from the following equations;

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

.sub.i.sup.<

j>

=f.sub.j (Xi).sup.1/Li mod Ni,

where i=1, . . . , k₂,

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.sup.<

j>

.Si.sup.Ei mod Ni,

sends said response Yi to said third party, where f_j (Xi) is a function of Xi which varies with j as a parameter; and

said third party;

verifies the validity of said response Yi by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.f.sub.j (Xi).Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂.

28. The electronic cash implementing method of claim 27, further including a step wherein, when having received information containing said electronic cash information {Vi, Xi, Bi, C}, the information {Ni, Li, Yi, j} of said user and the inquiry qi of said third party, from said final party for settlement of said electronic coin, said bank calculates inquiry information Ei by said inquiry function Ei=f(qi), and checks whether or not a set of information of the same values as a set of said user information Vi, said authentication information Xi and said j is stored in said memory of said bank;

and if such a set of information is found, said bank reads out the corresponding inquiry qi'"'"' of said third party and the corresponding response Yi of said user from said memory, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

where i=1, . . . , k₂,

calculates secret information Si from the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

where i-1, . . . , k₂,

and obtains from said calculated secret information Si the identification information IDp of said user who invalidly used said electronic coin.

29. The electronic cash implementing method of claim 18, wherein said bank allows said electronic coin to be used a predetermined number K of times, and further including a step wherein:

said user;

furnishes said third party with said electronic cash information {Vi, Xi, Bi, C} and information {Ni, Li} at the time of a j-th use of said electronic coin by said user, where 1≦

j≦

k;

said third party generates said inquiry ε

_i and sends it to said user;

said user;

generates said response Yi by the following equations with use of said inquiry ε

_i ;

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

.sub.i <

j>

=f.sub.j (Xi).sup.1/Li mod Ni,

where i=1, . . . , k₂,

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.sup.<

j>

.Si.sup.ε

.sbsp.i mod Ni,

and sends said response Yi to said third party, together with j, where f_j (Xi) is a function of Xi which varies with j as a parameter;

said third party;

verifies the validity of said response Yi by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.f.sub.j (Xi).Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

and furnishes said user with a license Bi, where i=1, . . . , k₂, which said third party has;

said user;

generates a deed of transfer T by applying a signature, with use of a prime-number product Ni of said user, to said license Bi of said third party and sends said deed of transfer T to said third party.

30. The electronic cash implementing method of claim 29, wherein said final party is said fourth party, and further including a step wherein:

said third party;

when using said electronic coin C, furnishes said fourth party with said electronic cash information {Vi, Xi, Bi, C} information {Ni, Li, T, Yi, j} of said user and information {Ni, Li, Bi, ε

_i } of said third party;

said fourth party;

verifies the validity of said response Yi of said user by checking it to ensure that the following equation hold;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

generates an inquiry qi, sends said inquiry qi to said third party, and calculates inquiry information Ei from an inquiry information Ei=f(qi);

said third party;

calculates said inquiry function Ei from said inquiry qi by said inquiry function Ei=f(qi), generates a response Yi by the following equations;

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

.sub.i.sup.<

j>

=f.sub.j (Xi).sup.1/Li mod Ni,

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.sup.<

j>

.Si.sup.Ei mod Ni,

where i=1, . . . , k₂,

and sends said response Yi to said fourth party; and

said fourth party;

verifies the validity of said response Yi of said third party by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.f.sub.j (Xi).Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂.

31. The electronic cash implementing method of claim 4, wherein said step of making said bank apply said blind signature to said information containing said user information, includes a step wherein:

said user;

generates k, k being an integer equal to or greater than 2, pieces of said secret information Si each containing said identification information, generates k pieces of said user information Vi from said k pieces of secret information Si by use of said first one-way function, generates k pieces of said randomized under information Wi randomized by applying, as a variable, information Mi containing each of said k pieces of user information Vi to a one-way first blind signature preprocessing function, and sends said k pieces of randomized user information Wi;

said bank;

when having received said k pieces of randomized user information Wi, selects therefrom a predetermined first number k₁ of pieces of said randomized user information, k₁ being smaller than k, specifies sets of information each containing said secret information Si used by said user for generating said randomized user information, and demands said user to present said specified sets of information;

said user;

furnishes said bank with said k₁ sets of information specified by said bank;

said bank;

calculates, from said sets of information received from said user, k₁ corresponding pieces of randomized user information Wi'"'"', verifies that said calculated randomized user information Wi'"'"' coincides with the corresponding pieces of said selected randomized user information Wi, respectively, confirms that said identification information IDp of said user is contained in all the pieces of said secret information in said sets of information received from said user, generates signed-randomized user information Ω

by signing, with a first signature function, multiplex randomized user information obtained from a predetermined number k₂ of pieces of said randomized user information among said k pieces of randomized user information received from said user, except said selected k₁ pieces of randomized user information, sends said signed-randomized user information Ω

to said user; and

said user;

derandomizes said signed-randomized user information Ω

, received from said bank, with a first blind signature postprocessing function to obtain said signed user information B;

wherein said user uses said signed user information B as said license issued by said bank.

32. The electronic cash implementing method of claim 31, wherein said step of issuing said electronic coin, including a step wherein:

said user;

generates k₂ pieces of said random information Ri, generates therefrom k₂ pieces of said authentication information Xi by a second one-way function, generates said randomized authentication information Z by applying information m containing said k₂ pieces of said authentication information Xi and said license B, as a variable, to a one-way second blind signature preprocessing function, and sends said randomized authentication information Z to said bank;

said bank;

generates said signed randomized authentication information Θ

by signing said randomized authentication information Z with a second signature function, and sends said signed-randomized authentication information Θ

to said user; and

said user;

derandomizes said signed-randomized authentication information Θ

with a second blind signature postprocessing function to obtain said signed authentication information as said electronic coin C.

33. The electronic cash implementing method of claim 31, further including a step wherein:

said user;

generates k prime members Li, k pairs of secret prime numbers Pi and Qi and k prime-number products Ni=Pi×

Qi, calculates k pieces of said user information Vi from k pieces of said secret information Si by said first one-way function expressed by the following equation;

space="preserve" listing-type="equation">Vi=Si.sup.Li mod Ni,

where i=1, . . . , k.

34. The electronic cash implementing method of claim 33, further including a step wherein, letting said k₂ items i be 1, . . . , k₂,

said user:

generates k₂ pieces of said authentication information Xi by using said second one-way function expressed by the following equation;

space="preserve" listing-type="equation">Xi=Ri.sup.Li mod Ni,

where i=1, . . . , k₂.

35. The electronic cash implementing method of claim 34, wherein said final party is said third party and said fourth party is said bank, and further including a step wherein:

said user;

when using said electronic coin, furnishes said third party with said electronic cash information containing said electronic coin C, said license B, k₂ pieces of said user information Vi and k₂ pieces of said authentication information Xi, k₂ said prime numbers Li and k₂ said prime-number products Ni;

said third party;

generates said inquiry qi, sends said inquiry qi to said user, and calculates k₂ pieces of inquiry information Ei from an inquiry function Ei=f(qi),

said user;

generates inquiry information Ei from said inquiry qi by said inquiry function, generates k₂ pieces of said response from said inquiry information Ei, said secret information Si and said secret random information Ri by the following equation

space="preserve" listing-type="equation">Yi=Ri.Si.sup.Ei mod Ni,

where i=1, . . . , k₂, and sends said k₂ pieces of response to said third party; and

said third party;

verifies the validity of said response Yi by checking them to ensure that the following equation

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂ holds, by use of said inquiry information Ei formed by himself, said user information Vi and said authentication information Xi received from said user, and authenticates said electronic coin as valid.

36. The electronic cash implementing method of claim 35, further including a step wherein:

said third party;

for the settlement of said electronic coin, furnishes said bank with information containing said electronic cash information (Vi, Xi, B, C), said prime-number products Ni, said prime numbers Li, said inquiry qi and said response Yi;

said bank;

verifies the validity of said response Yi to said inquiry qi by checking that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂.

37. The electronic cash implementing method of claim 36, furthr including a step wherein said bank checks whether or not a set of information of the same values as a set of said user information and said authentication information {Vi, Xi} received from said fourth party exists in said memory of said bank;

if such a pair of information is found, said bank stores in said memory said information received from said fourth party; and

if such a pair of information is found, said bank reads out of said memory the corresponding inquiry qi'"'"' and response Yi'"'"', calculates an inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

calculates secret information Si by the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and obtains from said calculated secret information Si the identification information IDp of said user who invalidly used said electronic coin.

38. The electronic cash implementing method of claim 34, wherein said final party is said fourth party, and further including a step wherein:

said user;

when transferring said electronic coin to said third party, furnishes said third party with information containing said electronic cash information {Vi, Xi, B, C}, said prime-number products Ni and said prime numbers Li;

said third party;

generates k₂ pieces of said inquiry ε

_i and sends it to said user;

said user;

generates k₂ pieces of response Yi by the following equation

space="preserve" listing-type="equation">Yi=Ri.Si.sup.ε

.sbsp. mod Ni,

where i=1, . . . , k₂,

by use of said secret random information Ri and said secret information Si, and sends said response Yi to said third party;

said third party;

verifies the validity of said response by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

and furnishes said user with a license B which said third party has;

said user;

generates a deed of transfer T by applying a signature, with use of the prime-number Ni of said user, to said license B of said third party, and sends said deed of transfer T to said third party.

39. The electronic cash implementing method of claim 38, further including a step wherein:

said third party;

when using said electronic coin, furnishes said fourth party with the information Ni, Li, said electronic cash information {Vi, Xi, B, C}, said deed of transfer T, said third party'"'"'s inquiry ε

_i, said user'"'"'s response Yi, said third party'"'"'s license B and said third party'"'"'s prime-number products Ni, prime numbers Li and user information Vi used for generating said third party'"'"'s license B;

said fourth party;

verifies the validity of said response Yi of said user by checking it to ensure that the following equation hold;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Yi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

generates an inquiry qi, sends said inquiry qi to said third party, and calculates inquiry information Ei by an inquiry function Ei=f(qi);

said third party;

calculates inquiry information Ei from said inquiry qi from said fourth party by said inquiry function Ei=f(qi), generates a response Yi by the following equations

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

.sub.i =Xi.sup.1/Li mod Ni, and

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.Si.sup.Ei mod Ni,

where i=1, . . . , k₂

and sends said response Yi to said fourth party; and

said fourth party verifies the validity of said response Yi of said third party by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂,

by use of said authentication information Xi of said user.

40. The electronic cash implementing method of claim 39, further including a step wherein:

said fourth party;

for settlement of said electronic coin, furnishes said bank with said electronic cash information {Vi, X, B, C}, said pieces of information Ni, Li and Yi of said user, said deed of transfer T, said information {Ni, Vi, Li, B, ε

_i, Y} of said third party and said inquiry qi of said fourth party; and

said bank;

verifies the validity of said response Yi of said user and said response Yi of said third party by checking them to ensure that the following equations hold;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂, and

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.ε

.sbsp.i (mod Ni).

41. The electronic cash implementing method of claim 40, further including a step wherein said bank checks whether or not a pair of information of the same values as a pair of said user information and said authentication information {Vi, Xi} received from said fourth party exists in said memory of said bank;

if such a pair of information is not found, said bank stores in said memory said information received from said fourth party; and

if such a pair of information is found, reads out of said memory an inquiry qi'"'"' and a response Yi'"'"' corresponding thereto, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

calculates secret information Si by the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and obtains from said calculated secret information Si the identification information IDp of said user who invalidly used said electronic coin C.

42. The electronic cash implementing method of claim 40 or 41, further including a step wherein said bank checks whether or not a pair of information of the same values as a pair {Vi, Xi} of said user information Vi of said third party and said authentication information Xi of said user received from said fourth party is stored in said memory of said bank;

if such a pair of information is not found, said bank stores in said memory said information received from said fourth party; and

is such a pair of information is found, said bank reads out of said memory the corresponding inquiry qi'"'"' of said fourth party and a response Yi'"'"' thereto of said third party, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

calculates secret information Si from the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and obtains from said calculated secret information Si the identification information of said third party who invalidly used said electronic coin C.

43. The electronic cash implementing method of claim 34, wherein said bank allows said electronic coin to be used a predetermined number K of times, said final party is said third party and said fourth party is said bank, and further including a step wherein:

said user;

at the time of a j-th use of said electronic coin, furnishes said third party with said electronic cash information {Vi, X, B, C} and information {Ni, Li}, where 1≦

j≦

k;

said third party;

generates k₂ pieces of said inquiry qi, sends said inquiry qi to said user, and calculates inquiry information Ei by an inquiry function Ei=f(qi);

said user;

calculates inquiry information Ei from said inquiry qi by said inquiry function Ei=f(qi), generates said response Yi from the following equations;

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

.sub.i.sup.<

j>

=f.sub.j (Xi).sup.1/Li mod Ni,

where i=1, . . . , k₂, and

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.sup.<

j>

.Si.sup.Ei mod Ni,

sends said response Yi to said third party, together with j, where f_j (Xi) is a function of Xi and varies with j as a parameter; and

said third party;

verifies the validity of said response Yi by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.f.sub.j (Xi).Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂.

44. The electronic cash implementing method of claim 43, further including a step wherein, when having received from said final party, for settlement of said electronic coin, information containing said electronic cash information {Vi, Xi, B, C}, the informatiion {Ni, Li, Yi, j} of said user and said third party'"'"'s inquiry qi, said bank calculates inquiry information Ei by said inquiry function Ei=f(qi);

sand bank checks whether or not a set of information of the same values as a set {Vi, Xi, j} of said user information Vi, said authentication information Xi and said j is stored in said memory of said bank;

if such a set of information is found, said bank reads out of said memory the corresponding inquiry qi'"'"' of said third party and the response Yi thereto of said user, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

where i=1, . . . , k₂,

calculates secret information Si from the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and obtains from said calculated secret information Si the identification information IDp of said user who invalidly used said electronic coin.

45. The electronic cash implementing method of claim 34, wherein said bank allows said electronic coin to be used a predetermined number K of times, and further including a step wherein:

said user;

at the time of j-th (where 1≦

j≦

K) use of said electronic coin, furnishes said third party with said electronic cash information {Vi, Xi, B, C} and information {Ni, Li}, where 1≦

j≦

K;

said third party;

generates and sends said inquiry ε

_i to said user;

said user;

generates said response Yi by the following equations;

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

.sub.i.sup.<

j>

=f.sub.j (Xi).sup.1/Li mod Ni,

where i=1, . . . , k₂, and

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.sup.<

j>

.Si.sup.ε

.sbsp.i mod Ni

and sends said response Yi to said third party, together with j, where f_j (Xi) is a function of Xi which varies with j as a parameter;

said third party;

verifies the validity of said response Yi by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.f.sub.j (Xi).Vi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

and sends to said user the license B that said third party has;

said user generates a deed of transfer T by applying a signature, with use of a prime-number product Ni, to said license B of said third party, and sends said deed of transfer T to said third party.

46. The electronic cash implementing method of claim 45, wherein said final party is said fourth party, and further including a step wherein:

said third party;

when using said electronic coin, furnishes said fourth party with said electronic cash information {Vi, Xi, B, C}, information {Ni, Li, T, Yi, j} of said user and information {Ni, Li, B, ε

_i } of said third party;

said fourth party;

verifies the validity of said user'"'"'s response Yi by checking it to ensure that the following equation hold;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Yi.sup.ε

.sbsp.i (mod Ni),

where i=1, . . . , k₂,

generates an inquiry qi, sends said inquiry qi to said third party, and calculates inquiry information Ei by an inquiry function Ei=f(qi);

said third party;

calculates inquiry information Ei from said inquiry qi from said fourth party by said inquiry function Ei=f(qi), generates a response Yi by the following equations;

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

.sub.i.sup.<

j>

=Xi.sup.1/Li mod Ni, and

space="preserve" listing-type="equation">Yi=Ψ

.sub.i.sup.<

j>

.Si.sup.Ei mod Ni,

where i=1, . . . , k₂

and sends said response Yi to said fourth party; and

said fourth party;

verifies the validity of said response Yi by checking it to ensure that the following equation holds;

space="preserve" listing-type="equation">Yi.sup.Li .tbd.Xi.Vi.sup.Ei (mod Ni),

where i=1, . . . , k₂.

47. The electronic cash implementing method of claim 1, wherein said step of making said bank apply said blind signature to said information containing said user information and said step of making said bank apply said blind signature to said information containing said authentication information, include

a step wherein:

said user;

generates k, k being an integer equal to or greater than 2, pieces of said secret information Si each containing said identification information IDp, generates k pieces of said random number information Ri, generates k pieces of said user information Vi and k pieces of said authentication information Xi on the basis of said k pieces of secret information Si and said k pieces of random information Ri by use of said first and second one-way functions, generates k pieces of said randomized user information Wi each randomized by applying each of said k pieces of user information Vi as a variable to said one-way first blind signature preprocessing function, generates k pieces of said randomized authentication information Zi each randomized by applying each of said k pieces of authentication information Xi as a variable to said one-way second blind signature preprocessing function, and sends said k pieces of randomized user information Wi and said k pieces of randomized authentication information Zi to said bank;

said bank;

selects a predetermined first number k₁ of pieces of said randomized user information and k pieces of said randomized authentication information from said k pieces of randomized user information and said k pieces of randomized authentication information, respectively, where k₁ is smaller than k, specifies k₁ information groups each containing said secret information Si and said random information Ri used for generating said randomized user information Wi and said randomized authentication information Zi selected by said bank, and demands said user to present said specified k₁ information groups;

said user;

sends to said bank said k₁ information groups specified by said bank;

said bank;

calculates said k₁ randomized user information Wi and said k₁ randomized authentication information Zi on the basis of said information groups received from said user, verifies that the k₁ pieces of randomized user information Wi'"'"' thus calculated and the k₁ pieces of randomized authentication information Zi'"'"' thus calculated respectively coincide with said selected k₁ pieces of randomized user information Wi and said selected k₁ pieces of randomized authentication information Zi, confirms that said identification information IDp of said user is contained in all pieces of said secret information Si in said information groups received from said user, generates a predetermined number k₂ of pieces of signed-randomized user information Ω

_i by signing, with a first signature function, k₂ pieces of randomized user information among said k pieces of randomized user information Wi received from said user, except said selected k₁ pieces of randomized user information, sends said k₂ pieces of signed-randomized user information Ω

_i to said user, generates k₂ pieces of signed-randomized authentication information Θ

_i by signing, with a second signature function, k₂ pieces of randomized authentication information among said k pieces of randomized authentication information Zi received from said user, except said selected k₁ pieces of randomized authentication information, and sends said k₂ pieces of signed-randomized authentication information Θ

_i to said user; and

said user;

derandomizes said k₂ pieces of signed-randomized user information Ω

_i and said k₂ pieces of signed-randomized authentication information Θ

_i with first and second blind signature postprocessing functions, respectively, to obtain k₂ pieces of said signed user information Bvi and k₂ pieces of said signed authentication information Bxi;

wherein processing related to said signed user information and said signed authentication information in the use of said electronic cash is performed for said second number k₂ of pieces of signed user information and said second number k₂ of pieces of signed authentication information.

48. The electronic cash implementing method of claim 47, wherein

said user:

generates k prime numbers Li, k pairs of secret prime numbers Pi and Qi, and k prime-number products Pi×

Qi=Ni, calculates said user information Vi and said authentication information Xi from said secret information Si and said random information Ri by use of said first and second one-way functions respectively expressed by the following equations;

Vi=Si^Li mod Ni

Xi=Ri^Li mod Ni

where i=1, . . . , k.

49. The electronic cash implementing method of claim 48, wherein said final party is said third party and said fourth party is said bank, and further including a step wherein when using said electronic cash with respect to said third party, said user sends k₂ sets of information {Vi, Bvi, Xi, Bxi} as electronic cash information to said third party, together with said prime-number product Ni and said prime number Li;

said third party produces k₂ pieces of said inquiry qi and sends them to said user, and for said k₂ items i, calculates inquiry information Ei by use of an inquiry function Ei=f(qi);

said user calculates k₂ pieces of inquiry information Ei from said inquiry by use of said inquiry function Ei=f(qi), and generates and sends to said third party k₂ responses expressed by the following equation;

Yi=Ri.Si^Ei mod Ni;

and said third party verifies the validity of said response Yi by checking it to ensure that the following verification equation for all of k₂ items i, by use of said response Yi;

Yi^Li .tbd.Xi.Vi^Ei (mod Ni).

50. The electronic cash implementing method of claim 49, further including a step wherein said third party sends to said bank said electronic cash information {Bi, Bvi, Xi, Bxi}, said inquiry qi, said response Yi and said information Li and Ni for all of the k₂ items i for settlement of said electronic cash;

said bank verifies the validity of said response Yi to said inquiry (IDv, t, γ

_i) by checking whether or not the following verification equation holds for all of the k₂ items i;

Yi^Li .tbd.Xi.Vi^Ei (mod Ni).

51. The electronic cash implementing method of claim 50, further including a step wherein said bank checks whether or not a pair of information of the same values as a pair of said user information and said authentication information {Vi, Xi} received from said third party exists in said memory of said bank;

if such pair of information does not exist, said bank stores in said memory the information received from said third party; and

if such pair of information exists, said bank reads out the corresponding inquiry qi'"'"' and response Yi'"'"' from said memory, calculates inquiry information Ei'"'"'=f(qi'"'"') from said read-out inquiry qi'"'"', solves, by the Euclid'"'"'s algorithm, integers α and

β

which satisfy the following equation;

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

.Li+β

(Ei-Ei'"'"')=1,

calculates secret information Si by the following equation;

space="preserve" listing-type="equation">Vi.sup.α

.(Yi/Yi'"'"').sup.β

mod Ni=Si,

and detects from said calculated secret information Si identification information IDp of said user who invalidly used said electronic cash.

52. An electronic cash implementing user system in which a bank issues electronic cash to a user and the user pays to a third party with said electronic cash, comprising:

secret information generating means for generating secret information containing identification information;

user information generating means whereby user information is produced, by use of a first one-way function, from said secret information provided from said secret information generating means;

first blind signature preprocessing means whereby information containing said user information provided from said user information generating means is subjected to one-way blind signature preprocessing to produce randomized user information;

first blind signature postprocessing means whereby signed randomized user information produced by signing said randomized user information by said bank is derandomized to obtain signed user information;

secret random information generating means for generating secret random information;

authentication information generating means whereby authentication information is produced, by use of a second one-way function, from said secret random information provided from said secret random information generating means;

second blind signature preprocessing means whereby said authentication information provided from said authentication information generating means is subjected to one-way blind signature preprocessing to obtain randomized authentication information;

second blind signature postprocessing means whereby signed authentication information produced by signing said randomized authentication information by said bank is derandomized to obtain signed authentication information; and

response generating means whereby a response is produced by use of said secret random information in response to an inquiry from said third party.

53. The user system of claim 52, wherein said second blind signature preprocessing means includes concatenating means for concatenating said authentication information and said signed user information into a concatenated message, and a one-way preprocessing function operator for randomizing said concatenated message with a random number to produce said randomized user inormation.

54. The user system of claim 53, further including a one-way signature function operator whereby said user attaches a signature to signed user information of said third party provided therefrom.