Electronic payment device using balanced binary tree and the...

Details Electronic payment device using balanced binary tree and the... Electronic payment device using balanced binary tree and the...

1999-06-25

2003-04-08

Millin, Vincent (Department: 3624)

Data processing: financial, business practice, management, or co

Automated electrical financial or business practice or...

Finance

C705S050000, C705S075000, C713S177000

Reexamination Certificate

active

06546376

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to an electronic payment system in electronic commerce of network, and especially to a system using a balanced binary tree structure to calculate. The network used includes an Internet, a telephone network, a dedicated network, a cable TV network, etc.
BACKGROUND OF THE INVENTION
The basic structure of an electronic payment system
10
is illustrated in
FIG. 1. A
subscribe computer
1
and a merchant computer
2
perform data communication for completing a transaction through an Internet
3
(or other network). In general, the action of transferring account or verification for security is performed through an electronic payment service center
4
(for example, banks). In
FIG. 2
, the subscribe computer
1
purchases the total unit n by paying an amount of money to the electronic payment service center
4
and is awarded with an authority. Then, the total unit n is operated by a one-way function h to obtain a contrast data M. If the user desires to consume, the subscribe computer
1
firstly subtracts the unit spent, and uses the current unit k to calculate a value X
k
representing current consumption state to the amount of money. These datum (M and X
k
) is sent to the merchant computer
2
through the Internet
3
. In a reprocessing procedure P, the merchant computer
2
calculates a second value X′
k
using identical one-way function h. In the conventional operating process of the subscribe computer
1
with respect to the values M and X
k
a payment chain of one-way hash function shown in
FIG. 3
is used, which has the relation of a one-way function X
n−1
=h(X
n
). It means that the value X
n
is substituted into a one-way hash function h to operate as a one-dimension function or obtaining the next value X
n−1
. As shown in this figure, in the subscribe computer
1
, starting from substituting the initial value of a random number X
n
into an one-way hash function h to perform n times for deriving a contrast data M or to perform n−k times for deriving X
k
. Then, in the reprocessing procedure P of the merchant computer
2
, by the same one-way hash function h, X
k
is operated to generate X′
k
and then the value X′
k
is contrasted with data M. If X′
k
=M, it identifies this transaction is successful, thus the merchant computer
2
provides services or merchandises to the subscriber and requests a transferring account to the electronic payment service center
4
, thus storing current X
k
as a contrast value M for being used in next consumption.
Since the one-way hash function is irreversible, any X
k
only operates in a forward direction (the leftward direction in FIG.
3
). Therefore, for each consumption (with different k value, and value k is increased monotonically to value n), the subscribe computer
1
calculates from X
n
to X
k
for n−k times. For example, assuming one unit of money is consumed each time, thus, n−1 times of function operation are necessary to calculate from X
n
to X
1
. In the next consumption, from X
n
to X
2
similarly, n−2 times of operation are necessary. In further next consumption, from X
n
to X
3
, n−3 times of operation is necessary. And for X
n−1
, only one time of operation from X
n
is necessary. Thus, in the conventional calculation, totally, (n−1)+(n−2)+ . . . +1 times of functional operation are performed, and then this total value is divided by n to obtain an average of (n−1)/2 times for each consumption. For such a large amount of operations, the subscribe computer
1
with a finite ability of hardware (for example, an IC card) is insufficient. Therefore, the operation efficiency becomes low. The larger the unit of purchase, the lower the operation efficiency. Thus, the prior art only can be used in an electronic payment system with a smaller amount of money.
SUMMARY OF THE INVENTION
Accordingly, the primary object of the present invention is to provide an electronic payment device using an balanced binary tree for improving the calculating efficiency of an electronic payment system.
Another object of the present invention is to provide an electronic payment device using an balanced binary tree for reducing the operation times of an electronic payment system.
Another object of the present invention is to provide an electronic payment device using an balanced binary tree with a modularized design.
In order to attain the aforementioned objects, in the electronic payment system of the present invention, an operation device is installed in the subscribe computer for calculating a first data X
k
representing current consumption states, or a plurality of root values R
q
, in order that for each root value R
q
, a contrast value M
q
can be obtained from a third one-way function h. The operation device includes a data providing device for providing datum including the total unit n of the amount of money that user purchases, a first one-way function h
0
, a second one-way function h
1
, and the current unit k of the money after current consumption. The first one-way function h
0
and the second one-way function h
1
are different functions. Besides, a microprocessor is used to calculate the position value j of the current unit k, where j=n−k+1; and to pick up every binary code of the position value j from d
m−1
to d
0
sequentially, where j=(d
m
d
m−1
. . . d
1
d
0
)
2
, where each binary code d
i
=0 or 1, and i=m,m−1, . . . 1,0; and to calculate the first data X
k
of the current unit k of the amount of money, according to the value of the binary code d
m−1
d
m−2
. . . d
1
d
0
of the position value j being a 0 or 1 by formula X
k
=h
d0
(. . . (h
dm−2
(h
dm−1
(X
n
)))), where h
d
1
(. . . ), i=m−1,m−2, . . . ,1,0, it represents that if binary code d
i
=0, then the first one-way function h
0
(. . . ) serves as an operating function, and if the binary code d
i
=1, then the second one-way function h
1
(. . . ) serves as an operating function. After the first data X
k
is calculated, the X
k
and the contrast values M
q
are sent to the merchant computer through a network. Then, the merchant computer performs a reprocess procedure to the first data X
k
to form as a second data X′
k
, and checks whether the respective contrast value M
q
is equal to the second data X′
k
, so as to determine whether this translation is successful.
The data providing device of the present invention is a storing device (such as ROM, hard disk, etc), or an input device (such as a modem) reading data from a network.
It is suggested that the first one-way function h
0
and the second one-way function h
1
of the present invention are one-way Hash functions, for example, a MD-5 algorithm, a RIPE-MD algorithm, a SHA-1 algorithm, a MDC2 algorithm, a MDC4 algorithm, etc. It is preferred that the first and second one-way functions h
0
, h
1
are RIPE-MD algorithm, SHA-1 algorithm, respectively. They have the advantages of short data length and preferred reliability.
In the present invention, the operating device can be installed and operated step by step within a subscribe computer, or be modularized as a chip installed in the subscribe/merchant computer. The subscribe computer can be made as an IC card itself (such as a Smart IC card) contained such device. Of course, it can be used in a reprocessing procedure of the merchant computer for reducing operation times and improving the operating efficiency.


REFERENCES:
patent: 5432852 (1995-07-01), Leighton et al.
patent: 5963648 (1999-10-01), Rosen
patent: 5974141 (1999-10-01), Saito
patent: 5983208 (1999-11-01), Haller et al.
patent: 0932109 (1999-01-01), None
Johnson et al; Reexamining B-trees:free-at-empty is better than merge-at-half, Dr. Dobb's Journal, v17, n1, p44(3), Jan 199.*
Tashek, John; Indexing schemes chip away at lenghty query time, PC week, v13, n13 p95(1), Apr. 1996.

Affiliated with

Also associated with

Rating

Electronic payment device using balanced binary tree and the... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Electronic payment device using balanced binary tree and the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Electronic payment device using balanced binary tree and the... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3101007