Method and system for micropayment transactions

• US 20040199475A1
• Filed: 06/01/2004
• Published: 10/07/2004
• Est. Priority Date: 04/27/2001
• Status: Abandoned Application

• Current Assignee: Heartland Payment Systems Incorporated (Global Payments Incorporated), Massachusetts Institute of Technology
• Original Assignee: Heartland Payment Systems Incorporated (Global Payments Incorporated)
• Inventors: Micali, Silvio, Rivest, Ronald L.
• Application Number:
  US10/476,128
• Publication Number:
  US 20040199475A1
• Time in Patent Office: Days
• US Class Current: 705/67
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: G06Q 20/027 involving a payment switch or gateway
• CPC Class Codes: G06Q 20/04 Payment circuits
• CPC Class Codes: G06Q 20/0425 the cheque being electronic only
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 20/29 characterised by micropayments
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: G06Q 20/382 insuring higher security of transaction
• CPC Class Codes: G06Q 20/3825 Use of electronic signatures

Abstract

A micropayment system and method is presented for a payor U to establish payment to payee M for a transaction T, which typically has a very low value T_v. The micropayment scheme minimizes the bank'"'"'s processing costs, while at the same time climinating the need for users and merchants to interact in order to determine whether a given micropayment should be selected for payment. In one embodiment, the micropayment scheme includes time constraints, which require that an electronic check C for the transaction T be presented to a bank B for payment within a predetermined time/date interval. In another embodiment, the micropayment scheme includes a selective deposit protocol, which guarantees that a user is never charged in excess of what he actually spends, even within a probabilistic framework. In another embodiment, the micropayment scheme includes a deferred selection protocol, which provides the bank with control and flexibility over the payment selection process.

Claims

1. A method of establishing payment for a transaction T, the method comprising:

A. a first party deriving from T a data string C related to T, and causing a second party to receive at least a portion of said data string C;

B. the second party associating with said at least a portion of C an item V, wherein V is substantially unpredictable by the first party;

C. the second party determining whether V satisfies a property P, and if so, the second party causing a third party to receive information I enabling the third party to verify whether V satisfies said property P;

D. the third party, upon receiving I, verifying whether V satisfies said property P; and

E. the third party causing a fourth party to receive an amount a, only if V satisfies said property P.

2. A method according to claim 1, wherein at least a portion of said data string C is authenticated.

3. A method according to claim 1,

wherein the step of the second party determining whether V satisfies a property P does not require an interaction between the second party and the first party.

4. A method according to claim 2, wherein said portion of said data string is authenticated by a fifth party on behalf of the first party.

5. A method according to claim 1, wherein the step of the first party deriving the data string C from T includes the step of the first party creating a digital signature for at least a portion of T, using a secret key of the first party.

6. A method according to claim 5, wherein said digital signature of said first party comprises at least one of:

(a) a deterministic signature;

(b) a randomized signature;

(c) an off-line signature;

(d) an on-line signature; and

(e) an identity-based signature.

7. A method according to claim 1, wherein the step of the second party associating the item V with C includes the step of the second party creating a digital signature for at least a portion of C, using a secret key of the second party.

8. A method according to claim 7, wherein said digital signature of said second party is a deterministic signature.

9. A method according to claim 1, wherein said data string C comprises at least one of:

a digital signature for at least a portion of said transaction T, wherein said digital signature is computed using a secret key of the first party;

a message authentication code, wherein said message authentication code value is computed using a secret key of the first party; and

iii) an electronic check.

10. A method according to claim 1, wherein said item V comprises at least one of:

a) a digital signature for C, wherein said digital signature is computed using a secret key of the second party; and

b) a message authentication code value, wherein said message authentication code value is computed using a secret key known to the second party.

11. A method according to claim 1, wherein the step of said second party causing said third party to receive said information I includes at least one of:

a) the second party sending I to the third party;

b) the second party asking a fifth party to send I to the third party; and

c) the second party posting I in a file, and said third party retrieving I from said file.

12. A method according to claim 1, further including the step of the second party checking, after receiving C, the authenticity and integrity of C.

13. A method according to claim 12, wherein the second party makes use of public verification information that is related to the first party, in order to check the authenticity and integrity of C.

14. A method according to claim 13, wherein said public verification information comprises the first party'"'"'s public key that corresponds to the first party'"'"'s secret key, in a public key digital signature scheme.

15. A method according to claim 13, wherein the step of the second party making use of said public verification information includes at least one of:

(a) the second party obtaining said public verification information from the first party;

(b) the second party obtaining said public verification information from information transmitted by the first party in association with said data string C;

(c) the second party obtaining said public verification information from a digital certificate; and

(d) the second party obtaining said public verification information from information about the first party that is publicly available.

16. A method according to claim 1, wherein the second party and the fourth party are identical.

17. A method according to claim 1, wherein said second party and said third party are identical.

18. A method according to claim 1, wherein V satisfies P only if:

F(V)<

s,

wherein F is function, and

wherein s is a constant.

19. A method according to claim 18, wherein 0<

s<

1.

20. A method according to claim 18, wherein F is a public function that takes arbitrary bit strings as input, and returns as output a number greater than 0 and less than 1.

21. A method according to claim 1, wherein said transaction T is characterized in part by a transaction value Tv.

22. A method according to claim 21, wherein said amount received by said fourth party is greater than Tv.

23. A method according to claim 20, wherein said transaction T is characterized in part by a transaction value Tv, and wherein said amount received by said fourth party is equal to (T_v* 1/s).

24. A method according to claim 1,

(a) wherein said item V comprises the digital signature of said second party relating to said data string C;

and

(b) wherein V satisfies said property P if F(V) is less than s, where F represents a public function that operates upon a bit string and returns as output a number between 0 and 1.

25. A method according to claim 1, wherein said data string C contains information on T, said information comprising at least one of:

a) the identity of the first party;

b) the time of the transaction; and

c) the date of the transaction.

26. A method for a user U to establish payment to a merchant M for a transaction T having a transaction value T_V, the method comprising:

A. the user establishing a public key and a corresponding secret key for a first digital signature scheme, and deriving from T a data string C=SIG_U(T) to create an electronic check containing C, wherein SIG_U(T) represents the digital signature of the user U for the transaction T in said first digital signature scheme;

B. the user causing the merchant to receive said data string C;

C. the merchant establishing a public key and a corresponding secret key for a second digital signature scheme, and associating with said data string C an item V=SIG_M(C), wherein SIG_M(C) represents the digital signature of the merchant M for said data string C in said second digital signature scheme;

D. the merchant computing the value F(V)=F(SIG_M(C)), where F represents a public function that operates on a bit string to output a number between 0 and 1;

E. the merchant comparing F(SIG_M(C)) with a constant s to determine whether F(V)<

s, and if so, causing a bank to obtain said public key of the merchant;

F. the bank using said public key of the merchant to verify that F(SIG_M(C))<

s; and

G. only if F(SIG_M(C))<

s, the bank causing the merchant to receive an amount A=[T_V*1/s];

wherein s is a constant greater than 0 and less than 1, and represents the probability that the electronic check be selected for presentation to the bank.

27. A system for establishing payment for a transaction T, the system comprising:

A. communications means for transmitting data between a first party, a second party, a third party, and a fourth party;

B. a first processing means operative by a first party for deriving, inputting, and storing a data string C related to T;

C. a second processing means operative by a second party and responsive to C, for associating an item V with at least a portion of C, and for determining whether V satisfies a property P;

wherein V is substantially unpredictable by the first party;

D. means, selectively operative by the second party when V satisfies P, for causing a third party to receive information I enabling the third party to verify whether V satisfies P; and

E. means, selectively operative by the third party when V satisfies P, for causing a fourth party to receive an amount A.

28. A method of establishing payment for a transaction T, the method comprising:

A. a first party receiving from a second party at least a portion of a data string C, wherein said data string C is related to T;

B. the first party associating with said at least a portion of C an item V, wherein V is substantially unpredictable by the second party; and

C. the first party determining whether V satisfies a property P, and only if so, the first party causing a third party to receive information I enabling the third party to verify whether V satisfies said property P, thereby enabling the third party to cause a fourth party to receive an amount A upon verification that V satisfies P.

29. A method of establishing payment for a transaction T, the method comprising:

A. a first party receiving from a second party information I enabling the first party to verify that an item V satisfies a property P;

wherein said item V is associated with at least a portion of a data string C derived from T by a third party, and

wherein V is substantially unpredictable by said third party;

B. the first party, upon receiving L verifying whether V satisfies said property P; and

C. the first party causing a fourth party to receive an amount A, only if V satisfies said property P.

30. A method of establishing payment for a transaction T characterized in part by a time t, the method comprising:

A. a first party deriving from T a data string C related to T, wherein C includes information IN regarding said time t;

B. the first party causing a second party to receive at least a portion of said data string C, wherein said at least a portion of C includes information IN;

C. the second party associating with said at least a portion of C an item V, wherein V is substantially unpredictable by the first party;

D. the second party determining whether V satisfies a property P, and if so, the second party at time t′

causing a third party to receive information IN and information I enabling the third party to verify whether V satisfies said property P;

E. the third party, upon receiving I, verifying whether V satisfies said property P; and

F. the third party causing a fourth party to receive an amount A, only if;

a) V satisfies said property P, and

b) |t′

−

t| is less than a predetermined time interval.

31. A method according to claim 30, wherein said predetermined time interval |t′

−

t| is n days, where n is a nonzero integer from about one to about seven.

32. A method according to claim 30, wherein said predetermined time interval |t′

−

t| is at least m hours, where m is a nonzero integer from about one to about twenty four.

33. A method according to claim 30, wherein the first party in step B causes the second party to receive said portion of C at a time t₁>

t,

and wherein the second party refuses to accept C as payment for T unless |t₁−

t| is less than a predetermined amount.

34. A method according to claim 30,

wherein said data string C comprises a digital signature for at least a portion of T, created using a secret key of the first party.

35. A method according to claim 30, wherein V satisfies P only if V matches at least a portion of C.

36. A method according to claim 30, wherein said property P depends on V but not on C.

37. A method according to claim 30, wherein V satisfies P only if:

F(V)<

s,

wherein F is a function, and

wherein s is a constant and 0<

s<

1.

38. A method according to claim 37, wherein the value F(V) of the function F is substantially unpredictable by the first party.

39. A method according to claim 37, wherein at least one of said function F and said constant s are specified in C.

40. A method according to claim 37, wherein F is one of:

(a) a fixed public function;

(b) a public function that takes arbitrary bit strings as input and returns as output a number greater than 0 and less than 1.

41. A method according to claim 30, wherein V comprises a digital signature for C, computed using a secret key of the second party, and denoted as SIG_M(C).

42. A method according to claim 30, further comprising, after the step of the fourth party receiving the amount A, the step of the third party causing the first party to receive a free subscription to one or more transactions TS_i (i=1, . . . , n) provided by the second party, if for all i (i=1, . . . n), said transactions TS_i are characterized in part by a time ts_i, and |ts_i−

t| is less than a predetermined amount.

43. A method according to claim 30,

wherein said item V comprises a digital signature for at least one of:

a) date information relating to T and contained in C;

b) a serial number contained in C;

c) a string included in C;

d) a random string part of C; and

e) a quantity dependent on C;

and wherein V is computed using a secret key of the second party, and can be denoted as SIG_M.

44. A method according to claim 30, wherein said item V comprises a digital signature of G(C), where G represents at least one of a function and an algorithm.

45. A method according to claim 44, wherein V satisfies P only if

F(V)=F(SIG_M(G(C)))<

s;

wherein F represents a function;

wherein s represents a constant and 0<

s<

1; and

wherein the value F(V) is substantially unpredictable by the first party.

46. A method according to claim 44, wherein G(C) is specified within at least one of T and C.

47. A method according to claim 44, wherein G(C) includes at least one of:

(a) a substring of T;

(b) information F regarding said time t of the transaction T;

(c) information regarding the date on which the transaction T took place; and

(d) a string W selected by the first party.

48. A method according to claim 47, wherein said string W is unique to T, and is selected at random.

49. A method according to claim 47, wherein V=SIG_M(G(C)) is adapted to be computed by the second party before receiving said at least a portion of C.

50. A method according to claim 44, wherein said property P is satisfied if at least some bits of V=SIG_M(G(C)) match at least some bits of C.

51. A method according to claim 44, wherein said property P is satisfied if a selected m-bit string in V=SIG_M(G(C)) matches a selected m-bit string in C, wherein m is a predetermined positive integer.

52. A method according to claim 51, wherein m is about 10.

53. A method of establishing payment for a transaction T, the method comprising:

A. a first party deriving from T a data string C related to T, and causing a second party to receive at least a portion of said data string C;

B. the second party determining whether a property P holds between said at least a portion of C and a quantity Q depending on C, wherein Q is substantially unpredictable by the first party, and if so, the second party causing a third party to receive information I enabling the third party to verify that said property P is satisfied;

C. the third party, upon receiving I, verifying whether said property P is satisfied; and

D. only upon verifying that said property P holds between said at least a portion of C and Q, the third party causing a fourth party to receive an amount A.

54. A method according to claim 53, wherein said quantity Q can be represented as G(C), and wherein G is at least one of a function and an algorithm.

55. A method according to claim 54, wherein G(C) includes information on at least one of:

a) the time t at which the transaction T took place, and

b) the date d on which the transaction T took place.

56. A method according to claim 55, wherein said property P holds only if at least some bits of C equal at least some bits of SIG_M(G(C)), where SIG_M(G(C)) denotes the digital signature for G(C), created using a secret key of the second party.

57. A method of establishing payment for a transaction T characterized in part by a time t, the method comprising:

A. a first party deriving from T a data string C related to T;

B. a second party deriving a sequence of values VL_i associated with a sequence of times t_i (i=1, . . . , n), wherein for at least one integer m greater than 1 and less than n, |t−

t_m| is less than a predetermined amount;

C. the first party causing the second party to receive at least a portion of said data string C, wherein said portion includes information regarding the time t of said transaction T;

D. the second party determining whether a property P holds between said portion of C, and one of said value VL_m associated with t_m, and a quantity Q depending on VL_m;

E. if P holds, the second party causing a third party to receive information I enabling the third party to verify that said property P is satisfied;

F. the third party, upon receiving I, verifying whether Q satisfies P; and

G. the third party causing a fourth party to receive an amount A, only if Q satisfies said property P.

58. A method according to claim 57, wherein said quantity Q is given by:

Q=F(SIG_M(V_m)), where F represents a function, and where SIG_M(V_m) represents a digital signature of V_m, created using a secret key of the second party.

59. A method of establishing payment for a transaction T characterized in part by a transaction t, the method comprising:

A. a first party deriving from T a data string C related to T, wherein C includes information regarding t;

B. a second party deriving a sequence of values V_i associated with a sequence of time units t_i (i=1, . . . , n);

wherein each pair of adjacent time units t_i+1 and t_i defines a time interval Δ

t_i=t_i+1−

t_i; and

wherein for at least an integer m greater than 1 and less than n, said time t is within the time interval Δ

t_m;

C. at the beginning of said time interval Δ

t_m, the second party deriving a value Q_m associated with V_m, wherein Q_m is substantially unpredictable by the first party;

D. during said time interval Δ

t_m;

a) the first party causing the second party to receive at least a portion of C;

b) the second party determining whether a property P holds between said portion of C and Q_m, and if so, the second party causing a third party to receive information I enabling the third party to verify that said property P is satisfied;

E. the third party, upon receiving I, verifying whether Q satisfies P; and

F. the third party causing a fourth party to receive an amount A, only if Q satisfies said property P.

60. A method according to claim 59, wherein step C takes place before step B, and wherein said property P is satisfied only if at least some bits of Q match at least some bits of C.

61. A method according to claim 59, wherein Q_i is given by Q_i=F(SIG_M(V_i)), where F represents a function and where SIG_M(Vi) represents a digital signature of V_i, created using a secret key of the second party.

62. A method according to claim 59, wherein for all i=1, . . . , n, the time interval Δ

t_i=|t_i+1−

t_i| is a predetermined time interval.

63. A method according to claim 62, wherein said predetermined constant is one day.

64. A method of establishing payment for a transaction T characterized in part by a time t, the method comprising:

A. a first party deriving from T a data string C related to T, wherein C includes information F regarding t;

B. a second party deriving a sequence of values x_i (i=0, 1, . . . , n) associated with a sequence of time values t_i (i=0, 1, . . . , n), and making x₀ public;

wherein x_i=H(x_i+1) for i=0, 1, . . . , n−

1, where H is a one-way hash function;

wherein each pair of adjacent time values t_i+1 and t_i defines a time interval Δ

t_i=t_i+1−

t_i; and

wherein for at least an integer m greater than 1 and less than n, said time t is the time interval Δ

t_m;

C. during said time interval Δ

t_m, the first party causing the second party to receive at least a portion of C, wherein said portion includes F;

D. during said time interval Δ

t_m, the second party determining whether a property P holds between Q_m and said portion of C, and if so, the second party causing a third party to receive information I enabling the third party to verify that said property P is satisfied;

E. the third party, upon receiving I, verifying whether Q_m satisfies P; and

F. the third party causing a fourth party to receive an amount A, only if Q satisfies said property P.

65. A method according to claim 64, wherein the step of the second party making x₀ public comprises at least one of:

a) placing x₀ in a public file; and

b) digitally signing x₀ using a secret key of the second party, and placing the corresponding public key in a public directory;

66. A method according to claim 64, wherein said time interval Δ

t_i=t_i+1−

t_i is a predetermined constant for all i=1, . . . , n.

67. A system for establishing payment for a transaction T characterized in part by a time t, the system comprising:

A. communications means for transmitting data between a first party, a second party, a third party, and a fourth party;

B. a first processing means operative by a first party for deriving, inputting, and storing a data string C related to T, wherein C contains information F regarding the time t;

C. a second processing means operative by a second party and responsive to C, for associating an item V with at least a portion of C, and for determining whether V satisfies a property P;

wherein V is substantially unpredictable by the first party;

D. means, selectively operative by the second party when V satisfies P, for causing a third party to receive F, and information I enabling the third party to verify;

a) whether V satisfies P; and

b) wherein |t′

−

t| is less than a predetermined amount;

E. means, selectively operative by the third party when V satisfies P, and |t′

−

t| is less than a predetermined amount, for causing a fourth party to receive an amount A.

68. A method of establishing payment for a transaction T characterized in part by a time t, the method comprising:

A. a first party receiving from a second party at time t′

information I enabling the first party to verify that an item V satisfies a property P;

wherein said item V is associated with at least a portion of a data string C that is derived from T by a third party and that includes information regarding t; and

wherein V is substantially unpredictable by said third party;

B. the first party, upon receiving L verifying whether V satisfies said property P; and

C. the first party causing a fourth party to receive an amount A, only if;

a) V satisfies said property P; and

b) |t′

−

t| is less than a predetermined amount.

69. A method of establishing payment for a transaction T characterized in part by a time t, the method comprising:

A. a first party receiving from a second party at least a portion of a data string C, wherein said data string C is related to T, and wherein said portion of C includes information on t;

B. the first party associating with said at least a portion of C an item V, wherein V is substantially unpredictable by the second party; and

C. the first party determining whether V satisfies a property P, and if so, the first party at a time t′

causing a third party to receive information I enabling the third party to verify whether V satisfies said property P, thereby enabling the third party to cause a fourth party to receive an amount A, provided that

a) V satisfies P; and

b) |t′

−

t| is less than a predetermined amount.

70. A method of establishing payment for a plurality of n transactions T₁, T₂, . . . T_i, . . . T_n, wherein an index i, between 1 and n, can be associated with each T_i, and wherein each transaction T_i is characterized in part by a transaction value TV_i, the method comprising:

A. a first party using a probabilistic payment scheme to generate a check C_i for each transaction T_i and causing a second party to receive said C_i, wherein C_i includes an indication of the index i;

B. the second party selecting the checks C_j (1≦

j≦

n) that are payable in a manner that prevents the first party from predicting in advance which checks C_j will be selected to be payable;

C. the second party causing a third party to receive information I_j enabling the third party to verify that a selected check C_j is payable;

D. the third party, in response to receipt of I_j, verifying that a selected check C_j is payable; and

E. only if C_j is payable, a fifth party causing a fourth party to receive a credit amount CR_j, and causing the first party to be debited by a debit amount D_j so that, for all index j between 1 and n, and for any selection of payable checks, D=D₁+D₂+ . . . +D_j is no greater than TV_agg=TV₁+TV₂+ . . . +TV_j.

71. A method according to claim 70, wherein each debit amount Dj is determined at least in part by one of TV_j and C_j, for all index j between 1 and n.

72. A method according to claim 70, wherein each debit amount D_j depends on said index j associated with T_j.

73. A method according to claim 72, wherein each debit amount D_j also depends on at least one of a previous debit amount D_k (1≦

k<

j≦

n), and a previous index l (1≦

l<

j≦

n)for which a debited amount D_l was debited.

74. A method according to claim 70, further comprising the step of said fifth party causing an indication of the index j to be stored, for each check C_j selected for payment.

75. A method according to claim 74, wherein each debit amount D_j of a payable check C_j depends on the latest stored index k of any previous checks found to be payable.

76. A method according to claim 70, wherein the step of the second party causing the third party to receive the information I_j includes at least one of:

a) the second party sending I_j to the third party;

b) the second party asking a fifth party to send I_j to the third party; and

c) the second party posting I_j in a file, and said third party retrieving I_j from said file.

77. A method of establishing payment for a plurality of n transactions T₁, T₂, . . . T_i, . . . T_n, wherein an index i, between 1 and n, can be associated with each T_i, and wherein each transaction T_i is characterized in part by a transaction value TV_i, the method comprising:

A. a first party deriving from each transaction T_i a data string C_i related to T_i, and causing a second party to receive said data string C_i;

B. the second party associating with each data string C_i an item V_i, wherein V_i is substantially unpredictable by the first party;

C. the second party determining whether V_i satisfies a property P_i, and if so, the second party causing a third party to receive information I_i enabling the third party to verify whether V_i satisfies said property P_i;

D. the third party, in response to receipt of I_i, verifying whether V_i satisfies said property P_i; and

E. only if V_i satisfies said property P_i, a fifth party causing a fourth party to receive a credit amount CR_i, and causing the first party to be debited by a debit amount D_i;

wherein said debit amount D_i is less than or equal to said credit amount CR_i.

78. A method according to claim 77, wherein D₁+D₂+ . . . +D_i is less than or equal to TV₁+TV₂+ . . . +TV_i, for all index i between 1 and n.

79. A method according to claim 77, wherein each debit amount D_i is determined at least in part by one of TV_i and C_i, for all index i between 1 and n.

80. A method according to claim 77, wherein each data string C_i contains an indication of said index i associated with T_i.

81. A method according to claim 80, wherein each debit amount D_i depends on said index i associated with T_i.

82. A method according to claim 81, wherein each debit amount D_i also depends on at least one of a previous debit amount D_j, and a previous index k for which a debited amount D_k was debited.

83. A method according to claim 82, wherein D₁+D₂+ . . . +D_i is less than or equal to TV₁ +TV₂+ . . . +TV_i, for all index i between 1 and n.

84. A method according to claim 77, further comprising the step of said fifth party causing information SN_i to be stored for each data string C_i whenever V_i satisfies P_i.

85. A method according to claim 84, wherein SN_i is a progressive serial number representative of an order of said data string C_i relative to the other data strings

C₁ . . . C_i−

1 and C_i+1 . . . Cn in an ordered succession of data strings derived by said first party.

86. A method according to claim 84, wherein each debit amount D_i is determined using SN_i.

87. A method according to claim 84, wherein D₁+D₂+ . . . +D_i is less than or equal to TV₁+TV₂+ . . . +TV_i, for all index i between 1 and n.

88. A method according to claim 84, wherein each debit amount D_i is determined using SN_i.

89. A method of paying for a plurality of equal-valued transactions T₁, T₂, . . . T_i, . . . T_n, each having a value TV, the method comprising:

A. a first party deriving from each transaction T_i a data string C_i related to T_i, and causing a second party to receive said data string C_i;

wherein each data string C_i comprises a progressive serial number S_i, said serial number S_i being sequentially ordered starting from 1 and being representative of a position of C_i relative to other data strings in an ordered succession of data strings C_j (j=1, . . . , n);

B. the second party associating with C_i an item V_i, wherein V_i is substantially unpredictable by the first party;

C. the second party determining whether a property P_i holds between C_i and V_i, and if so, the second party causing a third party to receive information Ii enabling the third party to verify whether V_i satisfies P_i;

D. the third party verifying whether V_i satisfies P_i; and

only if V_i satisfies P_i;

a) a fifth party determining the value of S_max, wherein S_max represents the largest of any serial number S_k contained in C_k for which;

i) 1 k<

n;

ii) C_k is received by second party before receiving C_i;

iii) the third party has verified that V_k satisfies P_k; and

iv) said first party has been debited by a nonzero amount D_k;

b) said fifth party causing a fourth party to receive a credit amount CR; and

c) said fifth party causing the first party to be debited by a debit amount D_i, where D_i is given by;

(S_i−

S_max)*TV.

90. A method according to claim 89, wherein V_i satisfies P_i only if:

F(V_i)<

s,

wherein s is a number, and F is a function that operates on a bit string and returns a number.

91. A method according to claim 90, wherein said credit amount CR received by said fourth party is proportional to TV and to 1/s.

92. A method according to claim 90, wherein F is a function that operates on a bit string to output a number between 0 and 1, and wherein s is a number between 0 and 1.

93. A method for a user U to establish payment to a merchant M for a plurality of transactions T_i (i=1, . . . , n) having transaction values TV_i (i=1, . . . , n), the method comprising:

A. the user U establishing a public key and a corresponding secret key for a first digital signature scheme, and deriving from each T_i a data string C_i=SIG_U(T_i) and creating an electronic check CH_i that contains C_i and a serial number S_i;

wherein SIG_U(T_i) represents the digital signature of the user U_i for the transaction T_i in said first digital signature scheme;

wherein S_i is a progressive serial number representative of an order of said data string C_i relative to the other data strings in an ordered succession of data strings C_j (j=1, . . . , n) derived by said first party;

B. the user U causing the merchant M to receive said electronic check CH_i containing C_i and S_i;

C. the merchant M establishing a public key and a corresponding secret key for a second digital signature scheme, and associating with said data string C_i an item V_i=SIG_M(C_i), wherein SIG_M(C_i) represents the digital signature of the merchant M for said data string Ci in said second digital signature scheme;

D. the merchant M computing the value F(V_i)=F(SIG_M(C_i)), where F represents a public function that operates on a bit string to output a number between 0 and 1;

E. the merchant M comparing F(SIG_M(C_i)) with a constant s (0<

s<

1) to determine whether F(V_i)<

s, and if so, causing a bank to obtain said public key of the merchant M;

F. the bank using the merchant'"'"'s public key to verify that F(SIG_M(C_i))<

s; and

G. only if F(SIG_M(C_i))<

s,

a) a fifth party determining the value of S_max, wherein S_max represents the largest serial number S_j contained in any CH_j in said ordered succession upon which payment was made;

b) said fifth party causing a fourth party to receive a credit amount CR; and

c) said fifth party causing the first party to be debited by a debit amount D_i.

94. A method according to claim 93, wherein each transaction T_i (i=1, . . . , n) is equal-valued so that TV_i=TV for all i=1, . . . , n, and wherein D_i is given by:

D_i=(S_i−

S_max)*TV;

and wherein CR is given by;

CR=TV*(1/s).

95. A system for establishing payment for a plurality of n transactions T₁, T₂, . . . , T_i, . . . , T_n, wherein an index i, between 1 and n, can be associated with each T_i, and wherein each transaction Ti is characterized in part by a transaction value TV_i, the system comprising:

A. communications means for transmitting data between a first party, a second party, a third party, and a fourth party;

B. a first processing means operative by a first party for deriving, inputting, and storing a data string Ci (i less than or equal to n and greater than or equal to

     1),

wherein Ci is related to a transaction Ti, and

wherein Ci includes a progressive serial number Si representative of the position of the check Ci relative to other checks in an ordered succession of checks Cj (j=1, . . . , n);

C. a second processing means operative by a second party and responsive to Ci, for associating an item Vi with at least a portion of Ci, and for determining whether Vi satisfies a property Pi,

wherein Vi is substantially unpredictable by the first party; and

wherein said second processing means are selectively operative by the second party, when Vi satisfies Pi, for causing a third party to receive information Ii enabling the third party to verify whether Vi satisfies Pi; and

D. means, selectively operative by the third party when Vi satisfies Pi, for determining the value of S_max, for causing a fourth party to receive an amount CRi, and for causing the first party to be debited by an amount Di, wherein for all index i between 1 and n, D₁+D₂+ . . . +D_i is no greater than TV_i+TV₂+ . . . +TV_i.

96. A method of establishing payment for a plurality of n transactions T₁, T₂, . . . , T_i, . . . , T_n, wherein an index i, between 1 and n, can be associated with each T_i, and wherein each transaction T_i is characterized in part by a transaction value TV_i, the method comprising:

A. a first party receiving from a second party at least a portion of a data string Ci for each Ti, wherein each data string Ci is generated from Ti using a probabilistic payment scheme, and wherein each Ci includes an indication of the index i;

B. the first party selecting the checks Cj (j less than or equal to n and greater than or equal to

     1) that are payable in a manner that prevents the first party from predicting in advance which checks Cj will be selected as payable;

C. for each selected check Cj, the first party causing a third party to receive information Ij enabling the third party to verify that the selected check Cj is indeed payable, thereby enabling the third party, upon verification that Cj is payable, to cause a fourth party to receive a credit amount CRj and the second party to be debited by a debit amount Dj so that, for all index j between 1 and n, and for any selection of payable checks Cj, D=D₁+D₂+ . . . D_j is no greater than TV_agg=TV₁+TV₂+ . . . +TV_j.

97. A method of establishing payment for a plurality of n transactions T₁, T₂, . . . , T_i, . . . , T_n, wherein an index i, between 1 and n, can be associated with each T_i, and wherein each transaction T_i is characterized in part by a transaction value TV_i and can be represented by a corresponding data string C_i, the method comprising:

A. a first party receiving from a second party information I_j enabling the first party to verify that a check C_j is payable;

wherein said check C_j is selected by the second party from a plurality of checks C_i (i=1, . . . , n) derived by a third party from a corresponding one of said plurality of transactions T_i (i=1, . . . , n); and

wherein the selection of said check C_j is substantially unpredictable by said third party;

B. the first party, upon receiving I_j, verifying whether C_j is indeed payable; and

C. the first party causing a fourth party to receive a credit amount CR_i, and causing the third party to be debited by a debit amount D_i,

98. A method of establishing payment for a plurality of n transactions T₁, T₂, . . . T_i, . . . T_n, wherein each transaction T_i is characterized in part by a transaction value TV_i that is a multiple of a unit value UV, the method comprising:

A. a first party deriving from each transaction T_i a data string C_i corresponding to T_i, and causing a second party to receive C_i;

wherein each data string C_i includes information on said integer index i and said value TV_i of T_i in the form of a vector (S_i, S_i+v_i−

1);

wherein for all i between 1 and n, S_i is a progressive serial number that is sequentially ordered and that is representative of a position of C_i relative to other data strings in an ordered succession of data strings C_j(j=1, . . . , n); and

wherein v_i is an integer depending on i and indicative of the value TV_i of T_i, and is given by v_i=TV_i/(UV);

B. the second party selecting the checks C_j (1≦

j≦

n) that are payable in a manner that prevents the first party from predicting in advance which checks C_j will be selected to be payable;

C. the second party causing a third party to receive information I_j enabling the third party to verify that a selected check C_j is payable;

D. the third party, in response to receipt of I_j, verifying that a selected check C_j is payable; and

E. only if C_j is payable;

a) a fifth party determining the value of S_max,

wherein max is an integer such that 1≦

max<

i≦

n, and v_max=TV_max/(UV); and

wherein S_max represents the largest of any serial number S_k (1≦

k<

n) contained in C_k for which;

i) C_k is received by the second party before receiving C_i; and

ii) the third party has verified that V_k satisfies P_k; and

iii) said first party was debited by a non-zero amount D_k, and

b), said fifth party causing a fourth party to receive a credit amount CR; and

c) said fifth party causing the first party to be debited by a debit amount D_i, where D_i is given by;

(S_i+v_i−

1−

S_max)*UV.

99. A method of establishing payment for a plurality of n transactions T₁, T₂, . . . , T_i, . . . T_n, wherein an index i between 1 and n is associated with each T_i, and wherein each transaction T_i is characterized in part by a transaction value TV_i that is an integral multiple of a unit value UV, the method comprising:

A. a first party deriving from each transaction T_i a data string C_i corresponding to T_i and causing a second party to receive C_i;

wherein each data string C_i includes information on said integer index i and said value TV_i of T_i in the form of a vector (S_i, S_i+v_i−

1);

wherein for all i between 1 and n, Si is a progressive serial number that is sequentially ordered and that is representative of a position of C_i relative to other data strings in an ordered succession of data strings C_j(j=1, . . . , n); and

wherein v_i is an integer depending on i and indicative of the value TV_i of T_i, and is given by v_i=TV_i/(UV);

B. the second party associating with C_i an item V_i, wherein V_i is substantially unpredictable by the first party;

C. the second party determining whether a property P_i holds between C_i and V_i, and if so, the second party causing a third party to receive information I_i enabling the third party to verify whether V_i satisfies P_i;

D. the third party verifying whether V_i satisfies P_i; and

only if V_i satisfies P_i;

a) a fifth party determining the value of S_max,

wherein max is an integer such that 1≦

max<

i≦

n, and v_max=TV_max/(UV); and

wherein S_max represents the largest of any serial number S_k (1≦

k<

n) contained in C_k for which;

i) C_k is received by the second party before receiving C_i; and

ii) the third party has verified that V_k satisfies P_k; and

iii) said first party was debited by a non-zero amount D_k, and

b) said fifth party causing a fourth party to receive a credit amount CR; and

c) said fifth party causing the first party to be debited by a debit amount D_i, where D_i is given by;

(S_i+v_i−

1−

S_max)*UV.

100. A method of establishing payment for a plurality of n transactions T_i (i=1, . . . , n), each transaction T_i having a value TV_i, the method comprising:

a. a first party deriving from each T_i a data string C_i related to T_i, and causing a second party to receive said data string C_i;

b. the second party uniquely associating groups of said data strings C_i (i=1, . . . , n) into m lists L^k, where k=1, . . . , m;

wherein each list L^k includes data strings C^k₁, . . . , C^kl_k, and

wherein Σ

^m_k=1l_k=n;

c. the second party committing to L^k (k=1, . . . , m), by computing a commitment CM^k for each L^k, and causing a third party to receive CM^k (k=1, . . . , m);

d. the third party, in response to receipt of CM^k (k=1, . . . , m), selecting one or more integer indices i₁, i₂, . . . i_r, and causing the second party to receive said indices i₁, i₂, . . . i_r, wherein 1≦

i_r≦

m;

e. in response to receipt of said indices i₁, i₂, . . . i_r, the second party de-committing CMⁱ¹, CMⁱ² . . . CM^ir, thereby revealing Lⁱ¹, . . . , L^ir to the third party; and

f. a fifth party causing a fourth party to receive a credit amount CR, and causing the first party to be debited by a debit amount D.

101. A method according to claim 100, wherein said commitment CM^k for L^k is a hash value H(L^k), and wherein H is a one-way hash function.

102. A method according to claim 100, wherein each data string C_i includes one or more bits that represent said transaction value TV_i.

103. A method according to claim 102, further comprising the step, after step (b), of the second party associating with each list L^k a corresponding value V^k, wherein V^k represents the aggregate value of all the data strings C^k₁, . . . , C^kl_k in list L^k,

wherein V^k is given by

V^k=TV^k₁+ . . . +TV^kl_k.

104. A method according to claim 103, further comprising the step, after step (c), of the second party computing a commitment CV for the list of values (V¹, . . . , V^m),

wherein said commitment CV commits the second party to (V¹, . . . , V_m),

wherein CV is a hash value H(V¹, . . . , V^m);

and

wherein H is a one-way hash function, so that by de-committing CV, the second party reveals (V¹, . . . , V^m) to the third party.

105. A method according to claim 100, wherein said credit amount CR received by the fourth party is given by:

V=V¹+ . . . +V^k+ . . . V^m=Σ

^m_k=1V^k.

106. A method according to claim 100, wherein said debit amount D is given by:

D=Vⁱ¹+Vⁱ²+ . . . +V^ir multiplied by a scale factor.

107. A method according to claim 106, wherein said scale factor is m/r.

108. A method according to claim 100, wherein said each data string C_i includes information representative of an integer SN_i, wherein SN_i is a progressive serial number sequentially ordered starting from 1, and wherein said serial number SN_i is representative of the order in time of said transaction T_i with respect to other transactions T₁, . . . , T_i−

1 and T_i+1, . . . T_n in said plurality of n transactions T_i (i=1, . . . , n).

109. A method according to claim 100, wherein the step of the first party deriving said data string C_i from T_i includes the step of the first party creating a digital signature for at least a portion of T_i, using a secret key of the first party.

110. A method according to claim 100, wherein at least a portion of C_i is authenticated.

111. A method according to claim 100, wherein C_i comprises at least one of:

a) a digital signature for at least a portion of T;

b) a message authentication code; and

c) an electronic check.

112. A method according to claim 100, wherein said fifth party and said third party are identical.

113. A method according to claim 100, wherein said second party, said third party, and said fifth party are identical.

114. A method according to claim 100, wherein said second party and said third party are identical.

115. A method of establishing payment for a plurality of n transactions T₁, . . . , T_i, . . . , T_n, each transaction T_i having a value TV_i, the method comprising:

A. for each T_i, a first party receiving from a second party a data string C_i derived from T_i;

B. the first party uniquely associating groups of said data strings C_i (i=1, . . . , n) into m lists L^k, where k=1, . . . , m;

wherein each list L^k includes data strings C^k₁, . . . , C^kl_k, and

wherein Σ

^m_k=1l_k=n;

C. the first party committing to L^k (k=1, . . . , m), by computing a commitment CM^k for each L^k, and causing a third party to receive CM^k (k=1, . . . , m), thereby enabling the third party to select one or more integer indices i₁, i₂, . . . i_r, wherein 1≦

i_r≦

m;

D. upon receipt of said indices i₁, i₂, . . . i_r, the first party de-committing CMⁱ¹, CMⁱ² . . . CM^ir, thereby revealing Lⁱ¹, . . . , L^ir to the third party and enabling the third party to cause a fourth party to receive a credit amount CR, and the second party to be debited by a debit amount D.

116. A method of establishing payment for a plurality of n transactions T₁, . . . , T_i, . . . , T_n, wherein each transaction T_i has a value TV_i and can be represented by a corresponding data string C_i derived from T_i, and wherein groups of said data strings C_i (i=1, . . . , n) can be uniquely associated into m lists L^k (k=1, . . . , m), each list L^k includes data strings C^k₁, . . . , C^kl_k (Σ

^m_k=1l_k=n), the method comprising;

A. a first party receiving from a second party a commitment CM^k for each of the m lists L_k (k=1, . . . , m);

B. the first party, upon receiving CM^k (k=1, . . . , m), selecting one or more integer indices i₁, i₂, . . . i_r, wherein 1≦

i_r≦

m, and causing the second party to receive said indices i₁, i₂, . . . i_r, thereby enabling the second party to de-commit CMⁱ¹, Cⁱ² . . . CM^ir so as to revealing Lⁱ¹, . . . , L^ir to the first party;

C. the first party causing a third party to receive a credit amount CR, and a fourth party to be debited by a debit amount D.

117. A system for establishing payment for a plurality of n transactions T₁, T₂, . . . , T_i, . . . , T_n, each T_i having a value TV_i, the system comprising:

A. communications means for transmitting data between a first party, a second party, a third party, and a fourth party;

B. a first processing means operative by a first party for deriving, inputting, and storing a data string C_i (1≦

i≦

n) for each T_i;

C. a second processing means operative by a second party and responsive to receipt of C_i (i=1, . . . n), for uniquely associating groups of said data strings C_i (i=1, . . . , n) into m lists L^k (k=1, . . . , m), and for inputting and storing said lists L^k(k=1, . . . , m);

wherein each list L^k includes data strings C^k₁, . . . , C^kl_k, and

wherein ρ

^m_k=1l_k=n;

said second processing means being further operative by the second party for computing a commitment CM^k for each L^k, and for inputting and storing said commitments CM^k (k=1, . . . , m);

D. a third processing means, operative by the third party upon receipt of said commitments CM^k, for selecting one or more integer indices i₁, i₂, . . . , i_r, and for causing the second party to receive said indices i₁, i₂, . . . , i_r,

wherein 1≦

i_r≦

m for all r;

E. a fourth processing means, operative by the second party upon receipt of said indices i₁, i₂, . . . , i_r, for de-committing CM, thereby revealing to the third party; and

F. means, operative by the third party upon revelation of Lⁱ¹, . . . , L^ir, for causing the first party to be debited by a debit amount D and for causing a, fourth party to receive a credit amount CR.