Electronic cash implementing method with a surveillance institution, and user apparatus and surveillance institution apparatus for implementing the same
Abstract
A method for implementing an electronic cash system with a surveillance institution, in which a user sends a request for the issuance of electronic cash of a face value X to a bank together with user information U and a user signature verification key NU, and the bank stores a pair of information X and NU in a user database in correspondence with the user information U and sends the information pair to the surveillance institution, while at the same time the bank generates and sends a signature SB(X,NU) for the information (X,NU) to the user. The surveillance institution registers the information (X,NU) in a surveillance database in correspondence with the total amount of payments Y. The user sends to a shop the amount of payment y, the amount of money X, the signature verification key NU and the signature SB(X,NU), along with a signature SU(e,y) for challenge information e received from the shop. The shop verifies the signatures SB(X,NU) and SU(e,y) and, if they are valid, receives a payment with the electronic cash.
Term
Term ended
Projected expiry passed 13 May 2017, 9.4 years ago.
- Priority
- Filed
- Published
- Projected expiry
- Today
22 claims: 6 independent, 16 dependent
- 1An electronic cash implementing method for an electronic cash system which comprises a surveillance institution for keeping the issuance of electronic cash under its surveillance, a bank which issues electronic cash, a user who uses electronic cash, and a shop which receives a payment with electronic cash, said method comprising:step (1) wherein said user sends user information U and an amount of money X corresponding to a face value of electronic cash to said bank and requests it to withdraw said amount X from a bank account of said user;step (2) wherein said bank withdraws said amount X from said bank account of said user, generates a signature S B (X,N U ) of said bank for a user signature verification key N U and said amount X, sends the signature to said user, records management data n including information about said amount X and said signature verification key N U in a user database in correspondence with said user information U, and sends said management data n to said surveillance institution;step (3) wherein said surveillance institution registers said management data n in a surveillance database in correspondence with a total amount of payments Y;step (4) wherein said user pays an amount of money y to said shop, using information including a balance x, said amount X, said signature verification key N U and said signature S B (X,N U ) as electronic cash C of said face value X and said shop receives said electronic cash C after verifying its validity;step (5) wherein said shop sends to said surveillance institution, for the settlement of an account, whole data H of communication between said shop and said user, including information on said electronic cash C;and step (6) wherein said surveillance institution verifies validity of said electronic cash C contained in said communication data H and instructs said bank to transfer said amount of payment y to a bank account of said shop.
- 10An electronic cash implementing method for an electronic cash system which is composed of a surveillance institution which keeps the issuance of electronic cash under its surveillance, a bank which issues electronic cash, a user who uses electronic cash, and a shop which receives a payment with electronic cash, and wherein said surveillance institution makes public an encipher function E T and said bank makes public a bank signature verification key PK B , said method comprising:step (1) wherein said user sends user information U and an amount of money X corresponding to the face value of electronic cash to said bank and requests the bank to withdraw said amount of money X from a bank account of said user, while at the same time said user enciphers information including signature verification key N U and said face value X to produce enciphered information E T (X,n) and send it to said bank;step (2) wherein said bank withdraws said amount of money X from said bank account of said user and sends said amount of money X and said enciphered information E T (X,n) to said surveillance institution, while at the same time said bank records said user information U and said enciphered information E T (X,n) in a user database in correspondence with each other;step (3) wherein said surveillance institution deciphers said encipherd information E T to obtain signature verification key information and registers at least one of said signature verification key information and said enciphered information E T in a surveillance database in correspondence with a total amount of payments Y;step (4) wherein said user requests said bank to attach a blind signature to said management data n and said amount of money X, obtains a bank signature S B (n) of said bank for said amount of money X;step (5) wherein said user pays an amount of money y to said shop, using, as electronic cash C of said face value X, second information including said bank signature S B (n), a balance x, said face value X and said user signature verification key N U and said shop receives said electronic cash C after verifying its validity;step (6) wherein said shop sends to said surveillance institution, for the settlement of an account, whole data H of communication between said shop and said user, including information on said electronic cash C;and step (7) wherein said surveillance institution verifies the validity of said electronic cash C contained in said communication data H and instructs said bank to transfer said amount of payment y to a bank account of said shop.
- 19A user apparatus for implementing an electronic cash system which is composed of a surveillance institution which keeps the issuance of electronic cash under its surveillance, a bank which issues electronic cash, a user who uses electronic cash and a shop which receives a payment with electronic cash, said apparatus comprising:key generating means for generating user signature key SK U ;memory means for storing electronic cash C containing a bank signature S B (X,N U ) attached to an amount of money X and a signature verification key N U , a balance x, a face value X and a signature verification key N U , and said user signature key SK U ;signature generating means for attaching a signature to an amount of payment y and arbitrary challenge information e received from said shop by said signature key SK U to generate a signature S U (e,y);and balance updating means for subtracting said amount of payment y from said balance x to update the latter.
- 20A surveillance institution apparatus for implementing an electronic cash system which is composed of a surveillance institution which keeps the issuance of electronic cash under its surveillance, a bank which issues electronic cash, a user who uses electronic cash and a shop which receives a payment with electronic cash, said apparatus comprising:a surveillance database wherein management data n corresponding to each user possessing electronic cash issued thereto is registered in correspondence with a total amount of payments Y;a history database for storing history data H which contains electronic cash C including a balance x, a face value X, a signature verification key N U and a bank signature S B (X,N U ), and an amount of payment y all received from said shop;means for making a check to see if there has been registered in the surveillance database said management data n corresponding to said amount of money X and said verification key N U in said history data H and, if not, for deciding that the electronic cash paid to the shop is overspent electronic cash;adding means for adding said amount of payment y in said history data to said total amount of payments Y in the surveillance database when said management data n has been registered therein;compare means for comparing the result of addition Y+y with said face value X;and control means which: if the result of said comparison by said compare means is Y+yX , decides that electronic cash paid to said shop is overspent electronic cash, then eliminates said management data n and said amount of payments Y, and reports said eliminated management data n to said bank.
- 21A user apparatus for implementing an electronic cash system which is composed of a surveillance institution which keeps the issuance of electronic cash under its surveillance, a bank which issues electronic cash, a user who uses electronic cash and a shop which receives a payment with electronic cash, said apparatus comprising:key generating means for generating user signature key SK U ;encipher means for enciphering said amount of money X and said signature verification key N U by a public encipher key PK T of said surveillance institution to generate enciphered information E T (X,N U ) and for sending it to said bank;blind signature pre-processing means for pre-processing said signature verification key N U to produce pre-processed signature verification key F(N U ), said pre-processed signature verification key F(N U ) being sent to said bank;blind signature post-processing means for post-processing a blind signature Z(N U ) for said signature verification key received from said bank to obtain a signature S B (N U ) of said bank;memory means for storing electronic cash C containing a balance x, a face value X, said signature verification key N U and said bank signature S B (X,N U ), said user signature key SK U and said public encipher key PK T of said surveillance institution;signature generating means for attaching a signature to an amount of payment y and arbitrary challenge information e received from said shop by said signature key SK U to generate a signature S U (e,y);and balance updating means for subtracting said amount of payment y from said balance x to update the latter.
- 22A surveillance institution apparatus for implementing an electronic cash system which is composed of a surveillance institution which keeps the issuance of electronic cash under its surveillance, a bank which issues electronic cash, a user who uses electronic cash and a shop which receives a payment with electronic cash, and wherein said surveillance institution makes public an encipher function E T and said bank makes public a signature verification key PK B , said method comprising:a memory for storing a secret decipher key SK T for deciphering said public encipher function E T ;decipher means for deciphering, by using said secret decipher key SK T , enciphered information E T (n) for management data n containing a signature verification key N U to obtain said management data n;a surveillance database for registering therein said deciphered management data n and the total amount of payments Y corresponding thereto;a history database for storing history data H which contains electronic cash C including a balance x, a face value X, a signature verification key N U and a bank signature S B (X,N U ), and an amount of payment y all received from said shop;means for making a check to see if there has been registered in said surveillance database said management data n corresponding to said amount of money X and said verification key N U in said history data H and, if not, for deciding that the electronic cash paid to said shop is overspent electronic cash;adding means for adding said amount of payment y in said history data to said total amount of payments Y in said surveillance database when said management data n has been registered therein;compare means for comparing the result of said addition Y+y with said face value X;and control means which: if the result of said comparison by said compare means is Y+yX , decides that said electronic cash paid to said shop is overspent electronic cash, then eliminates said management data n and said total amount of payments Y, and reports said eliminated management data n to said bank.
Independent claims6
117 paragraphs in 5 sections, as filed
BACKGROUND OF THE INVENTION
0001The present invention relates to an electronic cash implementing method that permits divisional use of electronic cash through a telecommunication system or smart card, ensures user privacy and prevents abuses of electronic cash. The invention also pertains to a user apparatus and a surveillance institution apparatus for implementing the method.
0002In recent years there has been popularized an electronic funds transfer employing a telecommunication system. In general, a certificate convertible into money, such as a draft or check, has a symbolic function of its own (which guarantees its possessor to the rights stated thereon). When handled in the telecommunication system, the certificate is digitized data, which could easily be copied for repeated arbitrary or unfair conversion into money. This problem arises as well in the implementation of electronic cash such as a prepaid card, because it could also be copied for repeated arbitrary or unfair conversion into money or purchase of merchandise. On the other hand, the credit card is essentially free from the danger of such double usage, but instead it has a disadvantage that the whole history of customer's use of the card becomes known to a credit card issuing company (that is, user privacy is not preserved). As solution to these problems, there has been proposed a scheme that uses a card having a computational function and devises a way of data exchange between a card reader and the card for its conversion into money to thereby ensure user privacy and detects its double usage. This is disclosed in, for example, Chaum, Fiat and Naor, "Untraceable electronic Cash," Proc. Of CRYPTO '88.
0003With the Chaum et al. scheme, however, it is necessary, for preserving security to some extent (the probability of success in overspending is 1/2<sup>30</sup> or below, for instance), that three procedures of inquiry, response and verification in the processing of user's payment of electronic cash to a shop be repeated by the number of times (30 times, for example) corresponding to the security intended to provide--this significantly increases the volume of communication required. Another problem is indivisibility of electronic cash. The principle for divisional use of electronic cash proposed so far is based on mathematical logic that utilizes a hierarchial structure as disclosed in U.S. Patent No. 5,242,162, for instance. However, the actual implementation of this conventional scheme involves many procedures and large computational loads. The electronic cash implementing system is configured primarily on the assumption that the same financial institution both issues electronic cash and manages users' accounts, and consequently, the electronic cash issued by the financial institution returns thereto from the user via shops and banks. Hence, it is impossible to keep under surveillance the amount of electronic cash issued by each financial institution.
SUMMARY OF THE INVENTION
0004It is therefore an object of the present invention to provide an electronic cash implementing method which ensures user privacy and prevents abuses of electronic cash hut permits reduction of the amount of communication involved in payment processing and divisional use of electronic cash and makes it possible to keep under surveillance the amount of electronic cash issued by each financial institution.
0005Another object of the present invention is to provide a user apparatus and surveillance institution apparatus for implementing the above-mentioned electronic cash scheme.
0006The electronic cash implementing method according to the present invention comprises: <ul id="ul0001" list-style="none" compact="compact"><li>step (1) wherein a user sends user information U and an amount of money X corresponding to the face value of electronic cash to a bank and requests it to withdraw the amount X from the user's account;</li><li>step (2) wherein the bank withdraws the amount X from the user's account, then generates a bank's signature S<sub>B</sub> (X,N<sub>U</sub>) for a user signature verifying key N<sub>U</sub> and the amount X, then sends it to the user, then records management information n including information about the amount X and the signature verification key N<sub>U</sub> in a user database in correspondence with the user information U, and sends the management information n to a surveillance institution;</li><li>step (3) wherein the surveillance institution registers the management information n in a surveillance database in correspondence with a total amount of money used Y;</li><li>step (4) wherein the user pays an amount of money y to a shop, using information including a balance (an amount of money left over) x, the face value X, the signature verification key N<sub>U</sub> and the signature S<sub>B</sub>(X,N<sub>U</sub>) as electronic cash C of the face value X and the shop receives the electronic cash C after verifying its validity and;</li><li>step (5) wherein the shop receives the electronic cash C after verifying its validity and the shop sends to the surveillance institution, for the settlement of an account, whole data H of communication between the shop and the user, including information on the electronic cash C; and</li><li>step (6) wherein the surveillance institution verifies the validity of the electronic cash C included in the communication data H and instructs the bank to transfer the amount y to a shop's bank account.</li></ul>
0007The above method may be modified as follows:
0008In step (1) the user sends information E<sub>T</sub>(X,N<sub>U</sub>), obtained by enciphering a pair of information including the signature verification key N<sub>U</sub> and the amount X by an encipher function E<sub>T</sub> with the use of an encipher key PK<sub>T</sub> of the surveillance institution, to the bank and further to the surveillance institution and, further, the user subjects the signature verification key N<sub>U</sub> to blind signature pre-processing to obtain information F(N<sub>U</sub>) and send it to the bank. In step (2) the bank records the information E<sub>T</sub>(X,N<sub>U</sub>) in the database instead of recording therein the management information n in correspondence with the user information U and sends to the user a blind signature Z(N<sub>U</sub>) for the information F(N<sub>U</sub>) instead of sending thereto the signature attached directly to the information (X,N<sub>U</sub>). In step (4) the user uses, as part of electronic cash, a bank signature S<sub>B</sub>(N<sub>U</sub>) obtained by blind signature post-processing of the information F(N<sub>U</sub>).
0009The user apparatus according to the present invention comprises: <ul id="ul0002" list-style="none" compact="compact"><li>key generating means for generating a user signature key SK<sub>U</sub>;</li><li>memory means for storing electronic cash C containing a bank signature S<sub>B</sub>(X,N<sub>U</sub>) attached to an amount of money X and a signature verification key N<sub>U</sub>, a balance (the amount of money left over) x, the face value X and the signature verification key N<sub>U</sub>, and the user signature key SK<sub>U</sub>;</li><li>signature generating means for attaching a signature to an amount of payment y and arbitrary information e received from a shop by the signature key SK<sub>U</sub> to generate a signature S<sub>U</sub>(e,y); and</li><li>balance updating means for subtracting the amount of payment y from the balance x to update the latter.</li></ul>
0010In the above user apparatus, encipher means may be provided for enciphering information including the amount X and the signature verification key N<sub>U</sub> through the use of an encipher key of the surveillance institution, the enciphered information being sent to the bank, and blind signature pre-processing means and blind signature post-processing means may also be provided to obtain a blind signature Z(N<sub>U</sub>) of the bank for the signature verification key N<sub>U</sub>, from which a bank signature S<sub>B</sub>(N<sub>U</sub>) is obtained.
0011The surveillance institution apparatus according to the present invention comprises: <ul id="ul0003" list-style="none" compact="compact"><li>a surveillance database wherein management information n corresponding to a user possessing electronic cash issued thereto is registered in correspondence with the total amount of spent money Y;</li><li>a history database for storing history data H which contains electronic cash C including the balance (the amount of money left over) x, the face value X, the signature verification key N<sub>U</sub> and the signature S<sub>B</sub>(X,N<sub>U</sub>) of the bank and the amount of payment y all received from the shop;</li><li>means which makes a check to see if there are registered in the surveillance database the management information n corresponding to the amount X and the verification key N<sub>U</sub> in the history data H and, if not, decides that the electronic cash paid to the shop is overspent electronic cash;</li><li>add means for adding the amount of payment y in the history data to the corresponding total amount of spent money Y in the surveillance database when the management information n is registered therein;</li><li>compare means for comparing the result of addition Y+y with the face value X; and</li><li>control means which: if the result of comparison by the compare means is <maths id="math0001" num=""><math display="inline"><mrow><mtext>Y+y<X</mtext></mrow></math><img file="EP0807910A2_D0001.tif" /></maths>, updates the corresponding total amount of spent money Y in the surveillance database with the result of addition Y+y; if <maths id="math0002" num=""><math display="inline"><mrow><mtext>Y+y=X</mtext></mrow></math><img file="EP0807910A2_D0002.tif" /></maths>, eliminates the corresponding management information n and the total amount of spent money Y from the surveillance database; if <maths id="math0003" num=""><math display="inline"><mrow><mtext>Y+y>X</mtext></mrow></math><img file="EP0807910A2_D0003.tif" /></maths>, decides that the electronic cash paid to the shop is overspent electronic cash, then deletes the management information n and the total amount of spent money Y, and reports the deleted eliminated management information n to the bank.</li></ul>
0012In the above surveillance institution apparatus decipher means may be provided so that information (X,N<sub>U</sub>) obtained by deciphering the enciphered information E<sub>T</sub>(X,N<sub>U</sub>) from the user is registered in the surveillance database.
0013According to the present invention, an issuing institution (a bank) which issues electronic cash and an institution (a surveillance institution) which performs verification processing for settlement of accounts are independent of each other and the later under surveillance the amount of circulation of electronic cash issued from the bank. On the other hand, divisional use of electronic cash is made possible by performing payment processing with the use of the user signature key. That is, the user signature attached to the amount of payment can be presented as evidence of overspending if the user pays more than a certain amount of money.
BRIEF DESCRIPTION OF THE DRAWINGS
0014<ul id="ul0004" list-style="none" compact="compact"><li>Fig. 1 is a diagram schematically illustrating the system configuration to which the present invention is applied;</li><li>Fig. 2 is a block diagram functionally illustrating a method for issuing electronic cash in a first embodiment of the present invention;</li><li>Fig. 3 is a block diagram functionally illustrating a method for payment of electronic cash in the first embodiment of the present invention;</li><li>Fig. 4 is a block diagram functionally illustrating a method for settlement of accounts by electronic cash in the first embodiment of the present invention;</li><li>Fig. 5 is a block diagram illustrating the functional configuration of a user apparatus in the first embodiment of the present invention;</li><li>Fig. 6 is a block diagram illustrating the functional configuration of a surveillance institution apparatus in the first embodiment of the present invention;</li><li>Fig. 7 is a block diagram functionally illustrating a method for issuing electronic cash in a second embodiment of the present invention;</li><li>Fig. 8 is a block diagram functionally illustrating a method for payment of electronic cash in the second embodiment of the present invention;</li><li>Fig. 9 is a block diagram functionally illustrating a method for settlement of accounts by electronic cash in the second embodiment of the present invention;</li><li>Fig. 10 is a block diagram illustrating the functional configuration of a user apparatus in the second embodiment of the present invention; and</li><li>Fig. 11 is a block diagram illustrating the functional configuration of a surveillance institution apparatus in the second embodiment of the present invention.</li></ul>
DESCRIPTION OF THE PREFERRED EMBODIMENTS
0015In Fig. 1 there is schematically shown an example of the system configuration to which the method of the present invention is applied. In the system there are interconnected via communication lines or the like an apparatus 100 of a surveillance institution (information indicating the surveillance institution being identified by T) which monitors the issuance of electronic cash, apparatus 200 of banks (information indicating banks being identified by B) which issue electronic cash, an apparatus 300 of a user (information indicating the user being identified by U) who uses the issued electronic cash, and an apparatus 400 of a shop (information indicating the shop being identified by W) which receives electronic cash from the user. These apparatus may also be interconnected via a smart card or the like on which information can be recorded. As a digital signature scheme that is used in the embodiments of the present invention described below, it is possible to employ any of already established systems.
0016The electronic cash implementing method of the present invention will be described as being applied to the system configuration shown in Fig. 1.
First Embodiment
(1) Processing for Issuance of Electronic Cash
0017A description will be given first, with reference to Fig. 2, of how the user has a bank issue electronic cash.
0018The bank 200 generates in advance a pair of public and secret keys PK<sub>B</sub> and SK<sub>B</sub> for digital signature (see, for example, Bruce Schnier, "Applied Cryptography," John Wiley, 1994) and stores it in a memory 20M. The secret key SK<sub>B</sub> and a signature generating function S<sub>B</sub> for generating a digital signature by using it are kept secret. A signature verification function V<sub>B</sub> for verifying the digital signature and a public key for verification PK<sub>B</sub> that is used therefor are made public.
0019The user carries out the following steps to request the bank 200 to draw out the same amount of money X as the face value of issued electronic cash from his bank account (corresponding to user information U).
0020Step 1: The user 300 generates a signature generating key SK<sub>U</sub> and a signature verification key N<sub>U</sub> in a digital signature key generating part 301 and stores them in a memory 30M. Hence, the signature verification key N<sub>U</sub> corresponds to the user information U.
0021The user 300 sends to the bank 200 a message requesting it to withdraw the same amount of money X as the face value of electronic cash and the user information (user identification information or the number of his bank account), together with the signature verification key N<sub>U</sub>.
0022Step 2: The bank 200 checks the balance in the user's bank account, then subtracts the amount X from the user's balance, and records and a pair of X and N<sub>U</sub> as management data in correspondence with the user's name U in a user database 201. In this instance, the withdrawal requesting message attached with a digital signature of the user 300, if any, is also recorded.
0023Next, the bank 200 calculates its digital signature S<sub>B</sub>(X,N<sub>U</sub>) for the pair of X and N<sub>U</sub> in a signature generating part 202 using the signature function S<sub>B</sub> and sends the digital signature S<sub>B</sub>(X,N<sub>U</sub>) to the user 300 and the information (X,N<sub>U</sub>) to a surveillance institution 100.
0024Step 3: The user 300 stores in the memory 30M the bank's digital signature S<sub>B</sub>(X,N<sub>U</sub>) and the information x, X and N<sub>U</sub> as electronic cash <maths id="math0004" num=""><math display="inline"><mrow><msub><mrow><mtext>C={x,X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><msub><mrow><mtext>,S</mtext></mrow><mrow><mtext>B</mtext></mrow></msub><msub><mrow><mtext>(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)}</mtext></mrow></math><img file="EP0807910A2_D0004.tif" /></maths> of the face value X and the balance x. The initial value of the balance x is equal to the face value X.
0025Step 4: The surveillance institution 100 registers the information (X,N<sub>U</sub>) as management data in a surveillance database 101. In this case, the initial value of the sum total Y of past payments y of the electronic cash corresponding to the information (X,N<sub>U</sub>) is recorded as Y=0 in correspondence with the information (X,N<sub>U</sub>).
0026While in the above the signature verification key N<sub>U</sub> is generated by the user 300, it may be generated by a different institution such as the surveillance institution 100 or the bank 200, in which case the signature verification key N<sub>U</sub> is generated by the surveillance institution or the bank in response to the request for issuance of electronic cash, in advance, and is sent to the user 300.
(2) Payment with Electronic Cash
0027Next, a description will be given, with reference to Fig. 3, of how the user 300 pays the amount of money y (y≤x) to a shop 400 with the electronic cash C of the face value X and the balance x and containing the pair of the signature verification key N<sub>U</sub> of the user 300 and the signature S<sub>B</sub> (X,N<sub>U</sub>) issued from the bank 200.
0028Step 1: The user 300 displays on a display part 30D the balance x read out of the memory 30M and makes sure that the balance x is more than the amount of money y to be paid, and then sends the electronic cash <maths id="math0005" num=""><math display="inline"><mrow><msub><mrow><mtext>C={x,X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><msub><mrow><mtext>,S</mtext></mrow><mrow><mtext>B</mtext></mrow></msub><msub><mrow><mtext>(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)}</mtext></mrow></math><img file="EP0807910A2_D0005.tif" /></maths> to the shop 400.
0029Step 2: The shop 400 verifies the validity of the signature S<sub>B</sub>(X,N<sub>U</sub>) of the electronic cash issuer (the bank 200) by a signature verification part 401 using the signature verification key PS<sub>B</sub> read out of the memory 40M. If the signature is valid, the shop 400 generates inquiry information <maths id="math0006" num=""><math display="inline"><mrow><mtext>e=f(TIME,W)</mtext></mrow></math><img file="EP0807910A2_D0006.tif" /></maths> for verification from time TIME and information W corresponding to the shop 400 by a one-way function calculating part 402 using a one-way function f, and the shop 400 sends the information TIME, W and e to the user 300.
0030Step 3: The user 300 verifies the validity of the inquiry information <maths id="math0007" num=""><math display="inline"><mrow><mtext>e=f(TIME,W)</mtext></mrow></math><img file="EP0807910A2_D0007.tif" /></maths> by a one-way function calculating part 306 and a comparison part 307. If it is valid, the user 300 calculates by a signature generating part 305 a user's signature S<sub>U</sub>(e,y) for the information e sent thereto and the payment y (y≤x) and sends the information y and S<sub>U</sub>(e,y) to the shop 400.
0031Step 4: The shop 400 verifies the validity of the user signature S<sub>U</sub>(e,y) and the payment y by the signature verification part 404 using the inquiry information e and the signature verification key N<sub>U</sub> and verifies y≤x by a comparison part 403. If either of them is valid, the shop 400 approves the payment of the amount y of money concerned with electronic cash and sends the decision result OK to the user 300, and if at least one of them is invalid, the shop 400 sends the decision result NG declining the payment with electronic cash. Further, the shop 400 holds the communication data H={x,X,N<sub>U</sub>,S<sub>B</sub>(X,N<sub>U</sub>),TIME,W,e,y,S<sub>U</sub>(e,y)} between it and the user 300 in a shop data storage 40D for the subsequent settlement of accounts.
0032Incidentally, the shop 400 may verify the validity of the bank's signature S<sub>B</sub>(X,N<sub>U</sub>) after sending the data TIME, W and e to the user 300.
0033Step 5: When receiving the decision result OK from the shop 400, the user 300 updates, by a subtract part 302, the balance x in the memory 30M with x←x-y.
(3) Settlement of Accounts
0034Turning next to Fig. 4, a method for settlement of accounts between the shop 400 and the bank 200 will be described.
0035Step 1: In the first place, the shop 400 sends all communication data H={x,X,N<sub>U</sub>,S<sub>B</sub>(X,N<sub>U</sub>),TIME,W,e,y,S<sub>U</sub>(e,y)} between the shop it and the user 300 to the surveillance institution 100 via the bank 200 with which the shop 400 has an account (or directly).
0036Step 2: The control part 114 of the surveillance institution 100 makes a check to see if the pair (X,N<sub>U</sub>) of signature verification key N<sub>U</sub> of the user 300 and the face value X contained in the communication data H has been registered in the surveillance database 101. If it has been registered, the control part 114 performs the operations with an adding part 107 and a comparison part 103, as follows:
0037The sum total Y of payments recorded corresponding to the information (X,N<sub>U</sub>) is updated with Y+y→Y and a check is made again to see if the updated value Y is smaller than the face value X. Further, the control part 114 records the communication data H in a history database 108. It is preferable that the amount of data stored in the history database 108 be reduced by setting a term to each piece of history data H therein and eliminating therefrom the data when the term expires.
0038If the updated value Y is not in excess of the face value X, the control part 114 instructs the bank, which issued the electronic cash used, to transfer the amount of money y to the bank account specified by the shop 400. In this case, the bank with which the shop 400 has its account need not be the bank 200 that signed the information (X,N<sub>U</sub>) of the user 300. In addition, if <maths id="math0008" num=""><math display="inline"><mrow><mtext>Y+y=X</mtext></mrow></math><img file="EP0807910A2_D0008.tif" /></maths>, the control part 114 eliminates the information (X,N<sub>U</sub>) and corresponding Y from the surveillance database 101.
0039When the information (X,N<sub>U</sub>) has not been registered in the surveillance database 101, the surveillance institution 100 decides that the user 300 has overspent the electronic cash, and it performs processing for specifying the overspender. If <maths id="math0009" num=""><math display="inline"><mrow><mtext>Y+y>X</mtext></mrow></math><img file="EP0807910A2_D0009.tif" /></maths>, the control part 114 deletes the pair of information X and N<sub>U</sub> and the corresponding information Y from the surveillance database 101. Also in this case, the control part 114 decides that the user has overspent the electronic cash, and it carries out the overspender specifying processing.
0040Step 3: In the overspender specifying processing, prior to the elimination of the information (X,N<sub>U</sub>) from the database 101, the surveillance institution 100 retrieves from the history database 108 information (all communication data H concerning the overspent electronic cash) that is used as evidence of overspending and sends the information H to the bank 200 that issued the electronic cash. The bank 200 verifies the validity of the evidence of overspending by a signature verify part 203 using the user's signature verification key N<sub>U</sub> and, if it is valid, specifies the overspender 300 corresponding to the user information U by retrieving the user database 201 by using the information (X,N<sub>U</sub>) as a key word.
0041In the foregoing, the embodiment has been explained with the case where the user sends to the bank and further to the surveillance institution the information (X,N<sub>U</sub>) including signature verification key N<sub>U</sub> in an original form; however, in general, the information of signature verification key N<sub>U</sub> may be sent in any transformed form including original form. This arbitrary form will hereinafter be expressed by <maths id="math0010" num=""><math display="inline"><mrow><msub><mrow><mtext>n=f(N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0807910A2_D0010.tif" /></maths> and referred to as signature verification information. In the present invention, the user may send to the bank and further to the surveillance institution signature verification key information generally expressed by <maths id="math0011" num=""><math display="inline"><mrow><msub><mrow><mtext>n=f(N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0807910A2_D0011.tif" /></maths>. For example, the user may use a one-way function f to transform information including the signature verification key N<sub>U</sub> to <maths id="math0012" num=""><math display="inline"><mrow><mtext>n=f(NU)</mtext></mrow></math><img file="EP0807910A2_D0012.tif" /></maths> and send (X,n) to the bank 200 and further to the surveillance institution 100 so as to be stored in the databases 201 and 101, respectively, as management data.
0042In the above first embodiment, it is also possible to arrange such that the bank 200 generates compressed signature verification key information data <maths id="math0013" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0807910A2_D0013.tif" /></maths>, as a management data, using one-way hash function h, for instance, then stores the management data n in correspondence with the name U of the user 300 in the user database 201 In a similar manner, the surveillance institution 100 may produce compressed data <maths id="math0014" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0807910A2_D0014.tif" /></maths> and register it as the management data n in the surveillance database 101 in correspondence with the total sum of spent money Y. In such an instance, the surveillance institution 100 shown in Fig. 4 obtains the management data n by compressing the information (X,N<sub>U</sub>) in the communication data H from the shop 400 with the same one-way hash function h and retrieves the database 101 with the management number n for the same management number n, that is, to see if the information (X,N<sub>U</sub>) is registered.
0043The procedure for the user 300 to make a payment to an arbitrary shop with the balance x of the electronic cash used as described above is exactly the same as the above-described procedure for payment between the user 300 and the shop 400, and the procedure for settlement of accounts between the shop and the surveillance institution 100 is also exactly the same as described above.
0044According to the electronic cash implementing method of the present invention, since the amount X of electronic cash issued by every bank 200 is reported to the surveillance institution 100, it is possible for the institution 100 to keep under its surveillance the total amount of electronic cash issued by the respective banks and to keep track of the total amount of circulation of the electronic cash.
0045Moreover, since what is required for the payment with electronic cash is only to make sure that the amount of money y to be paid is smaller than the current balance x, the procedure for the division use of electronic cash is far simpler than the procedure disclosed in the afore-mentioned U.S. Patent No. 5,224,162 and the amount of communication therefor is also significantly small.
0046Another feature of the present invention resides in that the data (X,N<sub>U</sub>) registered in the surveillance database 101 for surveillance is erased when all the corresponding electronic cash is used up to the face value X. Hence, subsequent overspending of the electronic cash is found out at once since the data (X,N<sub>U</sub>) of the electronic cash sent from a shop to the surveillance institution 100 for settlement is already erased from the database 101.
0047What is characteristic of this method is that since the data (X,N<sub>U</sub>) registered in the database 101 for surveillance is erased at the time when all the electronic cash is spent or its overspending is discovered, the registered data (X,N<sub>U</sub>) held in the database 101 is only those effective at that point in time. Accordingly, if the total amount of electronic cash issued remains constant to some extent, the amount of registered data to be held in the surveillance database 101 remains substantially constant and does not accumulate. In contrast to this, according to the conventional electronic cash system, every bank needs to keep lists of overspent electronic cash and spent electronic cash (that has a possibility for overspending in future) under surveillance; hence, the amount of data held under surveillance accumulates with an increase in the amount of electronic cash issued.
0048Next, a description will be given of the functional configurations of the user apparatus 300 and the surveillance institution 100 that are characteristic of the above-described first embodiment.
0049Fig. 5 illustrates a functional block diagram of the user apparatus for performing the procedure of the user 300 in the first embodiment. The user apparatus has such a configuration that functional parts 300a and 300b for processing by the user 300 for issuance of electronic cash and for his use of electronic cash, respectively, share an input part 311, a control part 312 and a memory 30M. The functional part 300a is made up of the input part 311, the control part 312 for controlling operations of respective parts, a key generating part 301, a transmitting part 313, a receiving part 314 and the memory 30M. When supplied with a command, the user information U and the face value X from the input part 311, the control part 312 sends the user information U and the face value X via the transmitting part 313 to the bank 200(B) to request it to issue electronic cash, while at the same time the control part 312 controls the key generating part 301 to generate the verification key N<sub>U</sub> and the signature key SK<sub>U</sub>, which are stored in the memory 30M together with the face value X. Further, the key N<sub>U</sub> thus generated is sent to the bank 200.
0050When the receiving part 314 receives from the bank 200 the signature S<sub>B</sub>(X,N<sub>U</sub>) for the information (X,N<sub>U</sub>), the control part 312 stores it in the memory 30M.
0051The functional part 300b for using electronic cash is made up of the input part 311, the control part 312, the memory 30M, a display part 30D, a subtracting part 302, a signature generating part 305, a one-way function part 306, a compare/decide part 307, a transmitting part 315 and a receiving part 316. When the amount of payment to the shop 400 is input via the input part 311, the balance x is read out of the memory 30M and is displayed on the display part 30D to make sure that the balance x is more than the amount of payment. Next, the electronic cash C={x,X,N<sub>U</sub>,S<sub>B</sub>(X,N<sub>U</sub>)} of the face value X and the balance x is read out of the memory 30M and sent to the shop 400 via the transmitting part 315. Upon receiving via the receiving part 316 the inquiry information e, TIME and W sent from the shop 400 in response to the electronic cash C sent thereto, TIME and W are processed using a one-way function in the one-way function part 306 to obtain f(TIME,W), which is compared with the received information e in the compare/decide part 307 to determine if they match. If so, the signature S<sub>U</sub>(e,y) for the pair of information e and y is generated using the signature key SK<sub>U</sub> in the signature generating part 305 and the signature is sent to the shop 400 along with the amount of payment y. At the same time, the amount of payment y is subtracted from the balance x in the subtracting part 302 and the updated balance x is used to update the balance x stored in the memory 30M.
0052The surveillance institution 100 comprises, as depicted in Fig. 6, the surveillance database 101, the history database 108, the comparison part 103, a control part 114 for controlling them, a receiving part 112, a transmitting part 113 and a receiving part 115. When the information (X,N<sub>U</sub>) from the bank 200 is received in the receiving part 112, the control part 114 registers the information (X,N<sub>U</sub>) in the surveillance database 101 and records the initial value Y=0 of the total amount of electronic cash used.
0053Thereafter, when the communication history data H={x, X,N<sub>U</sub>,S<sub>B</sub>(X,N<sub>U</sub>),TIME,W,e,y,S<sub>U</sub>(e,y)} for the procedure of payment with the electronic cash C={x,X,N<sub>U</sub>,S<sub>B</sub>(X,N<sub>U</sub>)} is received from the shop 400 in the receiving part 115, the control part 114 retrieves the surveillance database 101 to see if the information (X,N<sub>U</sub>) in the received data has already been registered, and if not, the control part 114 decides that the payment with the electronic cash is improper and reports the information (X,N<sub>U</sub>) to the bank which issued the electronic cash. If the information (X,N<sub>U</sub>) has already been registered, the total amount of money used Y in the surveillance database 101, corresponding to the information (X,N<sub>U</sub>), and the amount of payment y in the data H are added together in the adding part 107. The result of this addition is compared in the comparison part 103 with the face value X in the data H. If the result of this comparison is <maths id="math0015" num=""><math display="inline"><mrow><mtext>Y+y>X</mtext></mrow></math><img file="EP0807910A2_D0015.tif" /></maths>, the control part 114 decides that the payment with the electronic cash is improper and erases the information (X,N<sub>U</sub>) and the corresponding face value X from the surveillance database 101 and, at the same time, sends the information (X,N<sub>U</sub>) via a transmitting part 113 to the bank that issued the electronic cash. If <maths id="math0016" num=""><math display="inline"><mrow><mtext>Y+y>X</mtext></mrow></math><img file="EP0807910A2_D0016.tif" /></maths>, the control part 114 decides that the use of the electronic cash is proper, then records the data H in the history database 108, and updates the corresponding total amount of money used Y in the surveillance database 108 with the result of addition in the adding part 107. When <maths id="math0017" num=""><math display="inline"><mrow><mtext>Y+y=X</mtext></mrow></math><img file="EP0807910A2_D0017.tif" /></maths>, it means that all the face value X of the electronic cash is spent, and consequently, the information (X,N<sub>U</sub>) and the corresponding amount of money Y are erased from the surveillance database 101.
0054In the above first embodiment, since a new signature verification key N<sub>U</sub> is generated every time the same user requests an issuance of electronic cash, a plurality of electronic cashes issued to the same user can be distinguished from each other even if the face values X of the electronic cashes are identical. In order to allow the same user to use the same key N<sub>U</sub> for a plurality of electronic cashes, a different variable number R may be generated for each electronic cash, and data (X,N<sub>U</sub>,R) may be used instead of (X,N<sub>U</sub>). That is, the bank 200 records, in the user database 201, data (X,N<sub>U</sub>,R) or <maths id="math0018" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>,R)</mtext></mrow></math><img file="EP0807910A2_D0018.tif" /></maths> in correspondence with user's name U. Furthermore, the surveillance institution 100 registers, in the surveillance database 101, data (X,N<sub>U</sub>,R) or <maths id="math0019" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>,R)</mtext></mrow></math><img file="EP0807910A2_D0019.tif" /></maths> instead of (X,N<sub>U</sub>). When using the electronic cash, the user sends the electronic cash C including data (X,N<sub>U</sub>,R) and SB(X,N<sub>U</sub>,R). When making a settlement on accounts, the surveillance institution checks if the data (X,N<sub>U</sub>,R) inluded in the data H or <maths id="math0020" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>,R)</mtext></mrow></math><img file="EP0807910A2_D0020.tif" /></maths> produced from (X,N<sub>U</sub>,R) has been registered in the surveillance database 101. Second Embodiment
0055In the embodiment described above with reference to Figs. 2, 3 and 4, since the user presents his signature verification key N<sub>U</sub> to the bank when requesting it to issue electronic cash, the bank knows the correspondence between the user information U and the data (X,N<sub>U</sub>). On the other hand, the shop, when paid with electronic cash, receives the data (X,N<sub>U</sub>) from the user. Then, in the event that the bank conspires with the shop, the former can get the information U of the user who spent the electronic cash at the latter. Thus, the embodiment described above with respect to Figs. 2, 3 and 4 does not ensure sufficient user privacy. Turning now to Figs. 7, 8 and 9, an embodiment improved in this respect will be described below.
0056According to this embodiment, in the processing for issuance of electronic cash, the user presents his data (X,N<sub>U</sub>) after enciphering it by an enciphering key PK<sub>I</sub> of the surveillance institution so as to prevent it from becoming known to the bank. Further, in the procedure for the bank to issue electronic cash the user attaches a blind signature to the electronic cash issued from the bank so that the user's signature verification key N<sub>U</sub> does not become known to the bank. This embodiment will be described in detail with reference to Figs. 7, 8 and 9.
(1) Processing for Issuance of Electronic Cash
0057A description will be given first, with reference to Fig. 7, of how the user has the bank issue electronic cash.
0058Let it be assumed that the surveillance institution 100 generates in advance a public key PK<sub>T</sub> and a secret key SK<sub>T</sub> of a public key cryptosystem and holds them in the memory 10M and that the bank 200 generates and holds a pair of public and secret keys PK<sub>B</sub> and SK<sub>B</sub> of the blind signature scheme corresponding to each face value X.
0059The surveillance institution 100 makes public encipher function E<sub>T</sub> for encipherment of the public key and the public key PK<sub>T</sub> but keeps in secrecy a secret key SK<sub>T</sub> for deciphering use that forms a counterpart to the public key PK<sub>T</sub> and a decipher function D<sub>T</sub> that uses the secret key SK<sub>T</sub>.
0060The bank 200 makes public the public key PK<sub>B</sub> for blind signature use and the signature verification function V<sub>B</sub> but keeps in secrecy the secret key SK<sub>B</sub> in a memory 20M for blind signature use and the signature generating function s<sub>B</sub> that uses the secret key SK<sub>B</sub>.
0061The user 300 goes through the following steps to take the procedure for requesting the bank 200 to withdraw the amount of money of the face value X of electronic cash from the user's bank account.
0062In the following, however, this embodiment will be explained with the case where the user uses the same key NU for each issuance of electronic cash. In this case, therefore, the aforementioned variable number (or random number) R is used together with data (X,N<sub>U</sub>) so that plural electronic cashes possessed by the same user can be distinguished from each other.
0063Step 1: the user 300 uses the digital signature key generating part 301 to generate the signature generating key SK<sub>U</sub> and the signature verification key N<sub>U</sub>, which are held in a memory 30M. Incidentally, in this embodiment the user 300 employs, as a variable number, a random number R generated by a random generating part 30R so as to increase security, but the random number R can be substituted with any other variable number.
0064Next, the user 300 uses the enciphering public key PK<sub>T</sub> of the surveillance institution 100 held in the memory 30M to calculate data E<sub>T</sub>(X,N<sub>U</sub>,R) in an encipher part 303 that calculates the encipher function E<sub>T</sub> made public, and the user 300 sends to the bank 200 a message requesting it to withdraw the amount of money X from the user's bank account, together with the data E<sub>T</sub>(X,N<sub>U</sub>,R). It is desirable that the message be authenticated with the digital signature of the user 300, for instance.
0065Step 2: The bank 200 checks the balance in the user's account, then reduces the amount X from the balance, and records the data E<sub>T</sub>(X,N<sub>U</sub>,R) as management data in correspondence with the user's name U in the user database 201. If a withdrawal request message added with the signature of the user 399 exists, it is also recorded. The bank 200 does not have the secret key SK<sub>T</sub> for deciphering the enciphered data E<sub>T</sub>(X,N<sub>U</sub>,R), and hence it cannot learn the data (X,N<sub>U</sub>,R).
0066Then the bank 200 sends data {X,E<sub>T</sub>(X,N<sub>U</sub>,R)} to the surveillance institution 100.
0067Step 3: The surveillance institution 100 uses a decipher part 102 of the decipher function D<sub>T</sub> using a secret key SK<sub>T</sub> to decipher the enciphered data E<sub>T</sub>(X,N<sub>U</sub>,R) into (X,N<sub>U</sub>,R). Next, the surveillance institution 100 makes a comparison, by the comparison part 103, between the amount of money X sent from the bank 200 and the X obtained by the decipherment to see if they are identical. If so, the surveillance institution 100 registers in the database 101 a set of data (X,N<sub>U</sub>,R) as management data and stores the initial value Y=0 of the total amount of spent money Y in correspondence with the management data.
0068Step 4: The user 300 generates data F(N<sub>U</sub>) by a blind signature generating part 304 through the use of the blind signature public key PK<sub>B</sub> of the bank corresponding to the face value X (this processing being called blind signature pre-processing) and sends the data F(N<sub>U</sub>) to the bank 200.
0069The bank 200 inputs the data F(N<sub>U</sub>) into the blind signature generating part 203, wherein the blind signature secret key SK<sub>B</sub> is used to generate a blind signature Z(N<sub>U</sub>), which is sent to the user 300.
0070The user 300 derives a bank's signature S<sub>B</sub>(N<sub>U</sub>) from the blind signature Z(N<sub>U</sub>) in a blind signature extracting part 308 by the blind signature public key PK<sub>B</sub> (this processing being called blind signature post-processing).
0071As for the implementation of the blind signature, a system using an RSA scheme is introduced in Chaum, Fiat and Naor, "Untraceable electronic Cash," Proc. Of CRYPTO '88 and a blind signature using a Schnorr scheme is set forth in T. Okamoto, "Probably Secure and Practical Identification Schemes and Corresponding Signature Schemes," Appendix B, Proc. Of CRYPTO '92<img file="EP0807910A2_D0021.tif" /> pp.31-53, 1993.
0072Then, the user 300 stores the data C={x,X,N<sub>U</sub>,R,S<sub>B</sub>(N<sub>U</sub>)} as electronic cash of the face value X and the balance x in the memory 30M. The initial value of the balance x in this case is equal to the face value X.
0073While in this second embodiment the user 300 generates the signature verification key N<sub>U</sub>, provision may be made to generate it by the surveillance institution 100, for instance. In such an instance, the user 300 creates an encipher key K<sub>U</sub> and sends data E<sub>T</sub>(K<sub>U</sub>) to the surveillance institution 100 via the bank 200. The surveillance institution 100 decipher the data E<sub>T</sub>(K<sub>U</sub>) to obtain an encipher key K, then enciphers the key NU by the key K into E<sub>K</sub>(N<sub>U</sub>), and sends it to the user 300 via the bank 200. The user 300 decipher the received data E<sub>K</sub>(N<sub>U</sub>) by the encipher key K to obtain the signature verification key N<sub>U</sub>.
(2) Payment with Electronic Cash
0074Turning next to Fig. 8, a description will be given of the case where the user 300 pays the amount of money y (y≤x) to the shop 400, using a pair of user signature verification key N<sub>U</sub> and bank signature S<sub>B</sub>(N<sub>U</sub>) as the electronic cash C of the face value X and the balance x (initial value <maths id="math0021" num=""><math display="inline"><mrow><mtext>x=X</mtext></mrow></math><img file="EP0807910A2_D0022.tif" /></maths>). It should be noted that in the blind signature scheme, it is possible to produce a unique pair of keys SK<sub>B</sub> and PK<sub>B</sub> in correspondence with each of a desired number of face values X. This means that the keys SK<sub>B</sub> and PK<sub>B</sub> to be used in the blind signature represent a face value X and, therefore, the signature S<sub>B</sub>(N<sub>U</sub>) contains information on both the signature key N<sub>U</sub> and the face value X.
0075Step 1: The user 300 displays on the display part 30D the balance x read out of the memory 30M to make sure that the balance x is more than the amount of money y which the user 300 is to use, and sends the electronic cash C={x.X, N<sub>U</sub>,R,S<sub>B</sub>(N<sub>U</sub>)} to the shop 400.
0076Step 2: the shop 400 verifies the validity of the signature S<sub>B</sub>(N<sub>U</sub>) of the electronic cash issuer (i.e. The bank 200) by the signature verification function V<sub>B</sub> in the signature verification part 401 using a public key PK<sub>B</sub> corresponding to the face value X. If the bank signature is valid, the shop 400 generates a challenge information <maths id="math0022" num=""><math display="inline"><mrow><mtext>e=f (TIME,W)</mtext></mrow></math><img file="EP0807910A2_D0023.tif" /></maths> for verification from any desired information such as the time TIME and the shop information W corresponding to the shop 400 by using the one-way function f in the one-way function calculating part 402 and the shop 400 sends data TIME, W and e to the user 300.
0077Step 3: The user 300 uses the one-way function calculating part 306 and the comparison part 307 to verify the validity of the challenge information <maths id="math0023" num=""><math display="inline"><mrow><mtext>e=f (TIME,W)</mtext></mrow></math><img file="EP0807910A2_D0024.tif" /></maths>. If the information is valid, the user 300 uses the signature generating part 305 to calculate the challenge information e sent thereto and the user signature S<sub>U</sub>(e,y) for the amount of payment y (y≤x) and sends the amount of payment y and the user signature S<sub>U</sub>(e,y) to the shop 400.
0078Step 4: The shop 400 uses the signature verification part 404 to verify the validity of the user signature S<sub>U</sub>(e,y) and the amount of payment y through utilization of the challenge information e and the signature verification key N<sub>U</sub> and verifies y≤x by the comparison part 403. If either of them is valid, the shop 400 approves the payment of the amount of money y with electronic cash and sends the decision result OK to the user 300. Further, the shop 400 holds the communication data H={x,X,N<sub>U</sub>,R,S<sub>B</sub>(N<sub>U</sub>),TIME,W,e, y,S<sub>U</sub>(e,y)} between it and the user 300 in a shop data storage part 40D for the subsequent settlement of accounts. If at least one of them is invalid, the shop 400 sends the decision result NG declining the payment with electronic cash.
0079Incidentally, the shop 400 may verify the validity of the bank's signature S<sub>B</sub>(N<sub>U</sub>) after sending the data TIME, W and e to the user 300.
0080Step 5: When receiving the decision result OK from the shop 400, the user 300 updates, by the subtract part 302, the balance x in the memory 30M with x←x-y.
(3) Settlement of Accounts
0081Referring now to Fig. 9, a method for settlement of accounts between the shop 400 and the bank 200 will be described.
0082Step 1: In the first place, the shop 400 sends all communication data H={x,X,N<sub>U</sub>,R,S<sub>B</sub>(N<sub>U</sub>),TIME,W,e,y,S<sub>U</sub>(e,y)} between the shop 400 and the user 300 to the surveillance institution 100 via the bank 200 together with the name of the bank with which the shop 400 settles accounts.
0083Step 2: The control part 114 of the surveillance institution 100 makes a check to see if the set (X,N<sub>U</sub>,R) composed of the face value X, the signature verification key N<sub>U</sub> of the user 300 and the random number R contained in the communication data H has been registered in the surveillance database 101. If it has been registered, the control part 114 performs the operations with the adding part 107 and the comparison part 103 as follows:
0084The sum total payments Y recorded corresponding to the data (X,N<sub>U</sub>,R) is updated with Y+y→Y and a check is made again to see if the updated value Y is smaller than the face value X. Further, the control part 114 records the communication data H in the history database 108.
0085If the updated value Y is not in excess of the face value X, the control part 114 instructs the bank 200, which issued the electronic cash used, to transfer the amount of money y to the bank account specified by the shop 400. In this case, the bank with which the shop 400 has its account need not necessarily be the bank 200 that attached the blind signature to the verification key N<sub>U</sub> of the user 300 (i.e. the bank that issued the electronic cash).
0086If <maths id="math0024" num=""><math display="inline"><mrow><mtext>Y+y=X</mtext></mrow></math><img file="EP0807910A2_D0025.tif" /></maths>, the control part 114 eliminates the data (X,N<sub>U</sub>,R) and the corresponding value Y from the surveillance database 101.
0087When the data (X,N<sub>U</sub>,R) has not been registered in the surveillance database 101, the surveillance institution 100 decides that the user 300 has overspent the electronic cash, and it performs processing for specifying the overspender. If <maths id="math0025" num=""><math display="inline"><mrow><mtext>Y+y>X</mtext></mrow></math><img file="EP0807910A2_D0026.tif" /></maths>, the control part 114 deletes the data (X,N<sub>U</sub>,R) and the corresponding data Y from the surveillance database 101. Also in this case, the control part 114 decides that the user has overspent the electronic cash, and it carries out the overspender specifying processing.
0088Step 3: In the overspender specifying processing, the information H that is used as evidence of overspending is retrieved from the history database 108 and data (X,N<sub>U</sub>,R) in the information H is enciphered by an enciphering part 116 with the public key PK<sub>T</sub> to reproduce enciphered data E<sub>T</sub> (X,N<sub>U</sub>,R), which is sent together with the information H as evidences to the bank 200 that issued the electronic cash. The bank 200 verifies the validity of the evidences S<sub>U</sub>(e,y), S<sub>B</sub>(N<sub>U</sub>) in the received information H by the signature verify part 203 using the user's signature verification key N<sub>U</sub> and the bank's public key PK<sub>B</sub> and, if they are valid, specifies the overspender 300 corresponding to the user information U by retrieving the user database 201 by using the data E<sub>T</sub>(X,N<sub>U</sub>,R) as a key word. Alternatively, an encipher part may be provided in the bank 200 instead of the encipher part 116 in the surveillance institution 100.
0089If the shop 400 wants to keep its real name W unknown to the surveillance institution 100, the real name W may be substituted with a pseudonym W' in the communication data H which the shop 400 sends to the surveillance institution 100. Since the shop 400 reports the correspondence between 400 and W' to the bank with which the shop 400 settles accounts, the bank judges that the request for payment into the bank account W', received from the surveillance institution 100, is a request for payment into the account of the shop 400.
0090In the above second embodiment, the surveillance institution 100 has been explained as to register the data (X,N<sub>U</sub>,R) obtained by deciphering the data E<sub>T</sub>(X,N<sub>U</sub>,R) received from the bank 200 (Fig. 7) and, when conducting the settlement of accounts, data in the surveillance database is checked if the data (X,N<sub>U</sub>,R) in the received communication data H has been registered and, furthermore, when specifying the overspender, the data (X,N<sub>U</sub>,R) in the data H is enciphered to produce E<sub>T</sub>(X,N<sub>U</sub>,R) to be sent to the bank 200. However, it is also possible to arrange such that when registering in the surveillance database, the enciphered data E<sub>T</sub>(X,N<sub>U</sub>,R) is registered instead of the deciphered data (X,N<sub>U</sub>,R) as indicated by a broken line in Fig. 7 and when conducting the settlement of accounts, data (X,N<sub>U</sub>,R) in the communication data H received from the shop 400 is enciphered to obtain E<sub>T</sub>(X,N<sub>U</sub>,R) which is used to find if the surveillance database 101 contains the same data E<sub>T</sub>(X,N<sub>U</sub>,R), and further when specifying the overspender, the data E<sub>T</sub> (X,N<sub>U</sub>,R) is sent together with H to the bank 200.
0091Next, a description will be given of the functional configurations of the user apparatus 300 and the surveillance institution 300 characteristic of the second embodiment described above.
0092Fig. 10 is a functional block diagram of the user apparatus for performing the procedure of the user 300 in the second embodiment. The user apparatus has such a configuration that functional parts 300a and 300b for processing by the user 300 for issuance of electronic cash and for his use of electronic cash, respectively, share the input part 311, the control part 312 and the memory 30M.
0093The functional part 300a is made up of the input part 311, the control part 312 for controlling operations of respective parts, the key generating part 301, the transmitting part 313, the receiving part 314 and the memory 30M. When supplied with a command, the user information U and the face value X from the input part 311, the control part 312 sends the user information U and the face value X via the transmitting part 313 to the bank 200 to request it to issue electronic cash, while at the same time the control part 312 controls the key generating part 301 to generate the verification key N<sub>U</sub> and the signature key SK<sub>U</sub>, which are stored in the memory 30M together with the face value X. Further, the control part 312 controls the encipher part 303 to encipher the data (X,N<sub>U</sub>,R) by the encipher public key PK<sub>T</sub> of the surveillance institution 100 to obtain E<sub>T</sub>(X,N<sub>U</sub>,R), which is sent to the bank 200. Besides, the control part 312 controls the blind signature pre-processing part 304 to pre-process the verification key N<sub>U</sub> by the public key PK<sub>B</sub> for the blind signature of the bank and sends the resulting data F(N<sub>U</sub>) to the bank 200.
0094When the receiving part 314 receives from the bank 200 the blind signature Z(N<sub>U</sub>) for the data F(N<sub>U</sub>), the control part 312 controls the blind signature post-processing part 308 to extract the bank's signature S<sub>B</sub>(N<sub>U</sub>) by the public key PK<sub>B</sub> for the bank's blind signature and stores it in the memory 30M.
0095The functional part 300b for using electronic cash is made up of the input part 311, the control part 312, the memory 30M, the display part 30D, the subtracting part 302, the signature generating part 305, the one-way function part 306, the compare/decide part 307, the transmitting part 315 and the receiving part 316. When the amount of payment to the shop 400 is input via the input part 311, the balance x is read out of the memory 30M and is displayed on the display part 30D to make sure that the balance x is more than the amount of payment. Next, the electronic cash C={x,X,N<sub>U</sub>,S<sub>B</sub>(N<sub>U</sub>)} of the face value X and the balance x is read out of the memory 30M and sent to the shop 400 via the transmitting part 315. Upon receiving via the receiving part 316 the challenge information e, TIME and W sent from the shop 400 in response to the electronic cash C sent thereto, TIME and W are processed using a one-way function in the one-way function part 306 to obtain f(TIME,W), which is compared with the received information e in the compare/decide part 307 to determine if they match. If so, the signature S<sub>U</sub>(e,y) for the pair of information e and y is generated using the signature key SK<sub>U</sub> in the signature generating part 305 and the signature thus generated is sent to the shop 400 along with the amount of payment y. At the same time, the amount of payment y is subtracted from the balance x in the subtracting part 302 and the updated balance x is used to update the balance x stored in the memory 30M.
0096The surveillance institution 100 comprises, as depicted in Fig. 11, the memory 10M, the surveillance database 101, the decipher part 102, the comparison part 103, the history database 108, the add part 107, the receiving part 112, the transmitting part 113, the receiving part 115 and the control part 114 for controlling the operations of the respective parts. When the data X and E<sub>T</sub>(X,N<sub>U</sub>,R) from the bank 200 is received in the receiving part 112, the decipher part 102 deciphers it by using the deciphering secret key SK<sub>T</sub> to obtain (X,N<sub>U</sub>,R). A check is made in the comparison part 103 to see if the thus obtained amount of money X matches the received one X. If they match, the pair of the key N<sub>U</sub> and the data (X,N<sub>U</sub>,R) and the initial value Y=0 of the corresponding total amount of money used are registered in the surveillance database 101.
0097Thereafter, when the communication history data H={x, X,N<sub>U</sub>,R,S<sub>B</sub>(N<sub>U</sub>),TIME,W,e,y,S<sub>U</sub>(e,y)} for the procedure of payment with the electronic cash C={x,X,N<sub>U</sub>,R,S<sub>B</sub>(N<sub>U</sub>)} is received from the shop 400 in the receiving part 115, the control part 114 retrieves the surveillance database 101 to see if (X,N<sub>U</sub>,R) in the received data has already been registered, and if not, the control part 114 decides that the payment with the electronic cash is improper and sends the data (X,N<sub>U</sub>,R) to the bank that issued the electronic cash. If the data (X,N<sub>U</sub>,R) has already been registered, the total amount of payments Y in the surveillance database 101, corresponding to the data (X,N<sub>U</sub>,R), and the amount of payment y in the data H are added together in the adding part 107.
0098The result of this addition is compared in the comparison part 103 with the face value X in the data H. If the result of this comparison is <maths id="math0026" num=""><math display="inline"><mrow><mtext>Y+y>X</mtext></mrow></math><img file="EP0807910A2_D0027.tif" /></maths>, the control part 114 decides that the payment with the electronic cash is improper and erases the data (X,N<sub>U</sub>,R) and the corresponding total amount of payments Y from the surveillance database 101 and, at the same time, sends the data (X,N<sub>U</sub>,R) to the bank that issued the electronic cash. If <maths id="math0027" num=""><math display="inline"><mrow><mtext>Y+y<X</mtext></mrow></math><img file="EP0807910A2_D0028.tif" /></maths>, the control part 114 decides that the use of the electronic cash is proper, then records the data H in the history database 108, and updates the corresponding total amount of payments Y in the surveillance database 108 with the result of addition in the adding part 107. When <maths id="math0028" num=""><math display="inline"><mrow><mtext>Y+y=X</mtext></mrow></math><img file="EP0807910A2_D0029.tif" /></maths>, it means that all the face value X of the electronic cash is spent, and consequently, the data (X,N<sub>U</sub>,R) and the corresponding total amount of payments Y are erased from the surveillance database 101.
0099In the above second embodiment, instead of sending E<sub>T</sub>(X,N<sub>U</sub>,R) to the bank and the surveillance institution, the user may first encipher (X,N<sub>U</sub>,R) by a hash function to obtain <maths id="math0029" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>,R)</mtext></mrow></math><img file="EP0807910A2_D0030.tif" /></maths>, then encipher the information n to obtain E<sub>T</sub>(n), which in turn is sent to the bank and further ot the surveillance institution. In this case, the bank records the information E<sub>T</sub>(n) as management datain the user database, and the surveillance institution registers the E<sub>T</sub>(n) or n as management data in the surveillance database. This modification may further be modified such that instead of obtaining <maths id="math0030" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>,R)</mtext></mrow></math><img file="EP0807910A2_D0031.tif" /></maths>, information (X,N<sub>U</sub>) may be compressed as <maths id="math0031" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(X,N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0807910A2_D0032.tif" /></maths> and information (n,R) may be enciphered to obtain E<sub>T</sub>(n,R), then E<sub>T</sub>(n,R) may be sent to the bank and the surveillance institution. In a further alternative, (N<sub>U</sub>,R) may be hashed or only NU may be hashed to obtain <maths id="math0032" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>,R)</mtext></mrow></math><img file="EP0807910A2_D0033.tif" /></maths> or <maths id="math0033" num=""><math display="inline"><mrow><msub><mrow><mtext>n=h(N</mtext></mrow><mrow><mtext>U</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP0807910A2_D0034.tif" /></maths>, then E<sub>T</sub>(X,n) may be sent to the bank and the surveillance institution.
0100In the second embodiment, if the same user's signature verification key N<sub>U</sub> is changed everytime the user requests for issuance of electronic cash, the variable number (e.g., random number) R may not be used. In the case of not using the random number R, the bank 200 records data (X,N<sub>U</sub>) in correspondence with the user's name U in the user database 201, and the surveillance institution 100 registers either (X,N<sub>U</sub>) or E<sub>T</sub>(X,N<sub>U</sub>).
0101Alternatively, a random number R may be used as in (X,N<sub>U</sub>,R) only for the purpose of higher security in communication from the user via the bank 200 to the surveillance institution 100. In the latter case, the random number R is not included in the electronic cash to be sent to a shop; therefore, in the issuance of electronic cash, the surveillance institution has to register both (X,N<sub>U</sub>) and E<sub>T</sub>(X,N<sub>U</sub>,R) in the surveillance database 101 in correspondence with each other so that in the tracing of overspender, E<sub>T</sub>(X,N<sub>U</sub>,R) can be extracted from the surveillance database 101 using the (X,N<sub>U</sub>) from the shop as a keyword.
0102Furthermore, in the latter case, the surveillance institution may register a pair of (X,N<sub>U</sub>) and R instead of a pair of (X,N<sub>U</sub>) and E<sub>T</sub>(X,N<sub>U</sub>,R), and when having found an overspender, the surveillance institution can produce E<sub>T</sub> (X,N<sub>U</sub>,R) using the detected (X,N<sub>U</sub>) and corresponding R.
EFFECT OF THE INVENTION
0103The first embodiment of the present invention has a defect that user privacy is not provided if the bank and the shop conspire, but has advantages that user privacy is preserved unless the bank does wrong and that overspending of electronic cash can be detected.
0104The second embodiment are, as is the case with the Chaum et al. system, advantageous in that user privacy can be provided even if the bank conspires with the shop and that overspending of electronic cash can be detected.
0105With either of the methods according to the present invention, the amount of communication in the payment processing can be made smaller than in the Chaum et al. system. Besides, the electronic cash is divisible and the electronic cash issuer and the financial institution (i.e., bank) that manages users' accounts can be separated hierarchically.
0106For example, according to the Chaum et al. scheme, when the probability of success in overspending in the payment with electronic cash is 1/2<sup>30</sup>, processing needs to be performed 30 times, so that if the output size of the one-way function is assumed to be 128 bits, an amount of communication of at least (3×128×39)=11520 bits is required.
0107According to the present invention, the sizes of the data y and e and the user signature S<sub>U</sub>(e,y) therefor become the amount of communication in the payment processing. The total of the sizes of the data y and e (and TIME,W) is a maximum of about 20 bits. Assuming that the size of the signature is 1023-bit, the total is 1200-bit at the maximum.
0108Thus, according to the present invention, the amount of communication that is needed for the payment processing can be reduced by approximately 1/10 that in the past.
0109Moreover, the electronic cash issued can be divided and used repeatedly until the total sum of payments reaches the face value.
0110Besides, financial institutions (banks) that issue electronic cash and an institution (the surveillance institution) that performs verification processing for settlement of accounts can be separated so that the amount of circulation of electronic cash issued by the former is kept under the surveillance of the latter. That is, the surveillance institution is capable of detecting the total sum of electronic cash issued by the banks and the total sum of electronic cash returned to them, and hence it can monitor the amount of electronic cash circulating at each point in time.
Contents5
54 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18 Sheet 19 Sheet 20 Sheet 21 Sheet 22 Sheet 23 Sheet 24 Sheet 25 Sheet 26 Sheet 27 Sheet 28 Sheet 29 Sheet 30 Sheet 31 Sheet 32 Sheet 33 Sheet 34 Sheet 35 Sheet 36 Sheet 37 Sheet 38 Sheet 39 Sheet 40 Sheet 41 Sheet 42 Sheet 43 Sheet 44 Sheet 45 Sheet 46 Sheet 47 Sheet 48 Sheet 49 Sheet 50 Sheet 51 Sheet 52 Sheet 53 Sheet 54
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| WO0101361A1 | Cited by | World Intellectual Property Organization (WIPO) | International search |
| EP0926637A3 | Cited by | European Patent Office (EPO) | Search report |
| WO0159725A1 | Cited by | World Intellectual Property Organization (WIPO) | International search |
| EP0926637A2 | Cited by | European Patent Office (EPO) | Search report |
| WO0036569A1 | Cited by | World Intellectual Property Organization (WIPO) | Applicant |
| US6539364B2 | Cited by | United States of America | Applicant |
| EP0772165A2 | Cites | European Patent Office (EPO) | Search report |
| US5455407A | Cites | United States of America | Search report |
| WO9641316A2 | Cites | World Intellectual Property Organization (WIPO) | Search report |
7 members in 4 offices; this record represents the family
Priority claims4
| Document | Office | Kind | Date |
|---|---|---|---|
| 12168896 | Japan | A | |
| 12168896 | Japan | – | |
| JP19960121688 | – | – | – |
| 12168896 | – | – | – |
Members7
| Document | Office | Kind | |
|---|---|---|---|
| EP0807910A2This record | European Patent Office (EPO) | A2 | |
| JPH1083426A | Japan | A | |
| US6003765A | United States of America | A | |
| EP0807910A3 | European Patent Office (EPO) | A3 | |
| JP3329438B2 | Japan | B2 | |
| EP0807910B1 | European Patent Office (EPO) | B1 | |
| DE69738743D1 | Germany | D1 |
26 legal events, as 4 offices reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | Office | |
|---|---|---|---|
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Application deemed withdrawn, or ip right lapsed, due to non-payment of renewal feeWithdrawnR119 | R119 | DE | |
| Gb: european patent ceased through non-payment of renewal feeCeasedGBPC | GBPC | EP | |
| Lapsed in a contracting state [announced via postgrant information from national office to epo]LapsedPG25 | PG25 | EP | |
| Notification of lapseLapsedST | ST | FR | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| Annual fee paid to national office [announced via postgrant information from national office to epo]GrantedPGFP | PGFP | EP | |
| No opposition filedOpposition26N | 26N | EP | |
| No opposition filed within time limitOppositionORIGINAL CODE: 0009261PLBE | PLBE | EP | |
| Information on the status of an ep patent application or granted ep patentGrantedSTATUS: NO OPPOSITION FILED WITHIN TIME LIMITSTAA | STAA | EP | |
| Corresponds to:REF | REF | EP | |
| Designated contracting statesAK | AK | EP | |
| European patent grantedGrantedFG4D | FG4D | GB | |
| (expected) grantORIGINAL CODE: 0009210GRAA | GRAA | EP | |
| Grant fee paidORIGINAL CODE: EPIDOSNIGR3GRAS | GRAS | EP | |
| Information provided on ipc code assigned before grantRIC1 | RIC1 | EP | |
| Despatch of communication of intention to grant a patentORIGINAL CODE: EPIDOSNIGR1GRAP | GRAP | EP | |
| First examination report despatched17Q | 17Q | EP | |
| First examination report despatched17Q | 17Q | EP | |
| Designated contracting statesAK | AK | EP | |
| Search report despatchedORIGINAL CODE: 0009013PUAL | PUAL | EP | |
| Request for examination filed17P | 17P | EP | |
| Designated contracting statesAK | AK | EP | |
| Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI | PUAI | EP |
Numbers
- Publication
- 0807910
- Publication, DOCDB
- 0807910
- Publication, EPODOC
- EP0807910
- Application
- 97107804
- Application, DOCDB
- 97107804
- Application, EPODOC
- EP19970107804
Titles3
- German
- Verfahren zum Einführen elektronischen Geldes mit einer Überwachungseinrichtung, Gebrauchervorrichtung und Überwachungseinrichtung zum Durchführen desselben
- English
- Electronic cash implementing method with a surveillance institution, and user apparatus and surveillance institution apparatus for implementing the same
- French
- Méthode de mise en oeuvre d'argent électronique avec un centre de surveillance, et dispositif de l'utilisateur et dispositif de centre de surveillance pour la mettre en oeuvre
Classification
- CPC, 10
- G07F7/1016
- G06Q20/06
- G06Q20/0855
- G06Q20/10
- G06Q20/3674
- G06Q20/3678
- G06Q20/3825
- G06Q30/04
- H04L9/3257
- H04L2209/56
- IPC, 2
- G06Q20 00
- G07F7 10
Designated states3
- Contracting states, 3
- Germany
- France
- United Kingdom