OPTIMISTIC FAIR EXCHANGE PROTOCOLS

• US 20020049601A1
• Filed: 10/28/1998
• Published: 04/25/2002
• Est. Priority Date: 10/28/1998
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: ASOKAN, NADARAJAH, WAIDNER, MICHAEL, SHOUP, VICTOR
• Application Number:
  US09/181,442
• Publication Number:
  US 20020049601A1
• Time in Patent Office: Days
• US Class Current: 705/1
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 50/188 Electronic negotiation

Abstract

A method for the fair exchange of value items between two parties is presented in which a third party is only involved in exceptional situations. Each party sends initially in an exchange procedure, to the other party a permit which binds its value item in such a way that the receiving party can verify the fact that the value item is bound, but cannot yet extract the expected value item from the permit. If a party can accept a permit as correct, it then sends the actual value item to the other party. Thus, the exchange can be completed without involving the third party if no exceptional situation occurs.

For exceptional situations, subprotocols are provided by which a party, if not satisfied, can involve the third party and send to it the permit previously received. The third party can then obtain the value item from the permit and could deliver it to the requesting party. However, the subprotocls are so designed that in any case, the exchange procedure is completed, and either both parties have received the value item expected, or none of both received a value item from the other party. This exchange method operates reliably even in netweorks with arbitrary latency.

Claims

1. A method for the fair exchange of value items such as certified mail, electronic cash payment and receipt, or contract signatures, between two parties (A, B) in a network of arbitrary latency, according to a given protocol, in which method one party (A) receives the value item (item_B) of an other party (B) only if said other party also receives the value item (item_A) of said one party, and in which method a third party (T) is only involved in the exchange in exceptional situations;

providing an exchange protocol using permits each of which binds a representation of a value item such that;

a receiving party (A or B) can verify that the permit binds the representation of an expected value item but cannot obtain said expected value item from the permit, and

the third party (T), when receiving the permit and some additional information, can obtain the bound representation of the value item from the permit for delivery to one of the parties, without further cooperation of the two parties;

the protocol including steps for;

first sending a permit from each of the two parties to the other one for verification, and then

transmitting a representation of a value item from each party to the respective other party if the verification of a previously received permit was satisfactory for the transmitting party;

the protocol further providing;

at least one subprotocol (ABORT;

A-RESOLVE;

B-RESOLVE) for recovering from an exceptional situation;

a subprotocol being invoked by one (A or B) of the two parties for involving the third party (T), and including the transmission of a permit and additional information from said one party to the third party;

the execution of a subprotocol, without further cooperation from any of the two parties, either completing the exchange procedure so that finally each correctly behaving party received a representation of the value item it expected from the respective other party, or terminating the exchange procedure so that none of the parties received the value item it expected from the respective other party.

2. A method in accordance with claim 1, in which

any one of the two parties (A, B) can invoke a subprotocol when either the verification by said one party of a permit received from the respective other party is unsatisfactory, or when said one party decides to invoke a subprotocol in a particular situation predetermined by the protocol.

3. A method in accordance with claim 1, in which the following three subprotocols are provided:

a) a first subprotocol (ABORT) for requesting the termination of an ongoing exchange procedure by the party (A) which initiated the exchange procedure;

b) a second subprotocol (B-RESOLVE) for requesting, by the party (B) which responded to the initiated exchange procedure, the third party (T) to resolve an exceptional situation by completing the exchange procedure using a received permit; and

c) a third subprotocol (A-RESOLVE) for requesting, by the party (A) which initiated the exchange procedure, the third party (T) to resolve an exceptional situation by completing the exchange procedure using a received permit.

15. A method in accordance with claim 1 or claim 4, in which each permit is constructed by a party (A or B) according to a predetermined procedure (BIND) for binding the following items:

a) a representation of a value item (item_A) of the respective party (A);

b) a description of the expected value item (item_B) of the other party (B);

c) an authenticator (v) identifying the particular exchange procedure, initially generated by the party (A) which started the exchange operation; and

d) an identification of third the party (T) to be involved in an exceptional situation.

16. A method in accordance with claim 1 or claim 4, in which

descriptions of the value items (desc_A;

desc_B) expected by each of the two parties are exchanged between the parties prior to execution of the fair exchange protocol.

17. A method in accordance with claim 1 or claim 4, in which

the description (desc_A;

desc_B) of an expected value item (item_A;

item_B) which is a member of a first algebraic group (G₁) or which is converted to be represented by a member of a first algebraic group (G₁), is given as a member of another algebraic group (G₂) obtained by a homomorphic operation.

18. A method in accordance with claim 1 or claim 4, in which at least one of the permits is constructed by one of the two parties as a digital signature Sig_X under the signature key X of the respective party, binding at least the value item of said party (item_X), an authenticator (v) for the respective exchange operation, and an identifier for the third party (T) to be involved in exceptional situations.

19. A method in accordance with claim 1 or claim 4, in which at least one of the permits is constructed using a verifiable encryption protocol wherein:

a) a value item is represented as a selected member s of a first algebraic group G₁,

b) a description d of said selected member s, which description is a member of another algebraic group G₂ is generated by a homomorphic operation;

c) a permit is constructed by a proving party (P) by combining the selected member s with a bit string x which represents additional items (e.g. desc_V, v, T) required for execution of the exchange protocol, and encrypting the result using a predetermined encryption algorithm (VE);

d) the proving party (P) sends the resulting encryption as ciphertext c to the other, verifying party (V);

e) the receiving, verifying party (V) uses a verification algorithm (VV) corresponding to the predetermined encryption algorithm (VE), to obtain a verification ciphertext, using as input the description d previously obtained combined with said bit string x, so that the received ciphertext c corresponds to the locally generated verification ciphertext if the correct inputs were used by the prover and the verifier.

21. A method in accordance with claim 1 or claim 19, in which

coupons are used for the construction of verifiable encryption based permits, where each coupon is a security item which is independent of the value item for which a respective permit is constructed;

coupons are obtained prior to an actual exchange procedure in a pre-processing interaction between a proving party and the third party.

22. A method in accordance with claim 21, in which a proving party (P) wants to send to a verifying party (V) as permit (p) a verifiable encryption of a value item or secret s and an arbitrary string x;

and the verifying party already knows the description d=Θ

(s) of the value item or secret s of the proving party;

each coupon being prepared off-line in cooperation between the proving party (P) and the third party (T) executing following steps;

a) selecting a key pair (PK, SK) for a digital signature scheme, and a random element s′

as secret from an algebraic group G₁;

b) computing a description d′

=Θ

(s′

) which is an element of an algebraic group G₂ in a homomorphic operation;

c) generating, by the third party

a coupon (coup) including d′

, a random string t, s′

, and PK; and

a certificate (cert) by signing the coupon;

 

and sending the coupon, the certificate, the signing key SK and the secret s′

from the third party to said proving party;

 

so that the proving party (P) can use a coupon and the corresponding certificate and signature key and the secret s′

to generate a permit (p) binding the value item s for a value exchange operation, and

 

so that a verifying party (V) when receiving the permit (p) and the corresponding coupon and certificate and certain additional information can verify the permit.

23. A method in accordance with claim 22, in which

said coupon (coup) generated by the third party (T) has the form of <

d′

, E(t,s′

), PK>

wherein t is a random string selected by the third party, and E(t,s′

) is a ciphertext generated by a specified encryption system.

24. A method in accordance with claim 1 or claim 19, in which

verifiable encryption based permits are constructed without prior interaction between a proving party (P) and the third party (T), and

zero-knowledge proof procedures are used for the verifiable encryption and verification of permits.

25. A method in accordance with claim 22, in which a proving party, for sending a verifiable encryption of an item s to a verifying party, executes the following steps in the encryption procedure (VE):

choosing a stored coupon (coup) and following associated values;

s′

, SK, and certificate (cert);

computing s″

=s+s′

;

constructing the permit according to p=Sig_SK(E(t,s′

)|x) where Sig_SK indicates a digital signature with SK as the signature key; and

sending the permit p, the coupon (coup), the value s″

, and the associated certificate (cert) to the verifying party (V).

26. A method in accordance with claim 25, in which the verifying party (V) executes a verification procedure (VV) including following steps:

receiving the permit p, s″

, the coupon (coup) and its certificate (cert) from the proving party (P);

computing d″

=Θ

(s″

) and checking whether it is the same as d+d″

;

if not, signalling an error and quitting the procedure;

verifying, using T'"'"'s signature verification key, that the certificate (cert) is a valid signature by T on the coupon (coup); and

verifying, using PK, that the permit p is a valid signature on E(t,s′

)|x;

if any of these verifications fails, signalling an error and quitting the procedure;

if no error was signalled, storing s″

for use during recovery.

27. A method in accordance with claim 24, in which a proving party (P) wants to send to a verifying party (V) as permit (p) a verifiable encryption of a value item or secret s and an arbitrary string x, and the verifying party already knows the description d=Θ

(s) of the value item or secret s of the proving party;

the method including following steps executed by the proving party (P) for the encryption procedure (VE);

a) choosing a random element s′

of said group G₁ and computing d′

=Θ

(s′

);

b) computing s″

=s+s′

;

c) selecting a random string t and computing the permit p=E(t,s′

|x); and

d) sending the permit p and the description d′

to the verifying party (V).

28. A method in accordance with claim 27, including the following steps for the verification procedure (VV):

a) by the verifying party;

randomly choosing a binary variable as either 0 or 1, and sending the chosen value to the proving p

b) by the proving party;

b1) if b=0, then sending s′ and

t to the verifying party;

or

b2) if b=1, then sending s″

to the verifying party;

c) by the verifying party;

c1) if b=0, computing p′

=E(t, s′

|x) and checking whether p′

is the same as the received permit p;

if not, signalling an error and quitting the process;

or

c2) if b=1, checking whether Θ

(s″

)−

d is the same as d′

;

if not, signalling an error and quitting the process;

otherwise storing the received permit p as a valid permit, along with the corresponding s.

29. A method in accordance with claim 28, in which

the verifying procedure (VV) is repeated a predetermined number of times (N), and

one of the stored valid permits p is selected as the permit to be used by the verifying party in recovery subprotocols.

30. A method in accordance with claim 1 or claim 4, in which

common value items (electronic coins, digital signatures) are reduced to homomorphic inverses in suitable algebraic groups, prior to an exchange procedure.

4. A method for the fair exchange of value items such as certified mail, electronic cash payment and receipt, or contract signatures, between two parties (A, B) in a network of arbitrary latency, according to a given protocol, in which method one party (A) receives the value item (item_B) of an other party (B) only if said other party also receives the value item (item_A) of said one party, and in which method a third party (T) is only involved in the exchange in exceptional situations;

comprising the following steps for the exchange of a first value item (item_A) and a second value item (item_B) item between a first party (A) and a second party (B);

a) constructing by the first party (A), using a predetermined binding procedure, a first permit (perm_A) binding at least the first value item (item_A) and an authenticator (v); and

sending the first permit (perm_A) and the authenticator (v) to the second party;

b) verifying by the second party (B), using a predetermined verification procedure, the received first permit (perm_A), and

if the verification fails, halting its operation, or

if the verification succeeds, constructing a second permit (perm_B) binding at least the second value item (item_B) and the authenticator (v), and sending the second permit to the first party (A);

c) verifying, by the first party, the received second permit (perm_B), and

if the verification fails, invoking a first subprotocol (ABORT) for requesting a termination of the exchange procedure, or

if the verification succeeds, sending the first value item (item_A) to the second party;

d) verifying, by the second party, whether the received first value item matches its expectation (desc_A), and

if the verification fails, invoking a second subprotocol (B-RESOLVE) sending the received first permit (perm_A) to the third party (T) and requesting it to resolve the situation, or

if the verification succeeds, sending the second value item (item_B) to the first party and halting its operation;

e) verifying, by the first party, whether the received second value item matches its expectation (desc_B), and

if the verification fails, invoking a third subprotocol (A-RESOLVE) sending the received second permit (perm_B) to the third party and requesting it to resolve the situation, or

if the verification succeeds, halting its operation.

5. A method in accordance with claim 4, in which

the execution of a subprotocol, without further cooperation from any of the two parties, either completes the exchange procedure so that finally each correctly behaving party received the value item it expected from the respective other party, or terminates the exchange procedure so that none of the parties received the value item it expected from the respective other party.

6. A method in accordance with claim 4, in which

any one of the two parties (A, B) can invoke a subprotocol when either the verification by said one party of a permit received from the respective other party is unsatisfactory, or when said one party decides to invoke a subprotocol in a particular situation predetermined by the protocol.

7. A method in accordance with claim 4, in which each of the constructed permits (p) binds the following items:

the value item (e.g. item_A) which the respective party (e.g. A) will provide;

a description of the value item (desc_B) which is expected from the other party (B);

the authenticator for the respective exchange procedure (v); and

the identifier for the third party (T).

8. A method in accordance with claim 4, in which

the first party (A) computes the authenticator (v) to be used according to v=f(r), using a predetermined one-way function f( ) and a random string r, so that r is a pre-image of v with respect to the function f( ).

9. A method in accordance witch claim 8, in which

for invoking the first subprotocol (ABORT) or the third subprotocol (A-RESOLVE), the first party sends to the third party (T), besides the permit, additional information related to the authenticator (v), so that the third party can identify the respective exchange procedure, and verify that the invoking party was in fact the initiator of the exchange.

10. A method in accordance with claim 4, in which a first subprotocol (ABORT) for requesting the termination of an ongoing exchange procedure is provided which includes the following steps:

a) sending, by the first party (A), an abort request to the third party (T) including the first permit (perm_A);

b) executing, by the third party, one of the following operations;

b1) sending to the first party a representation of the second value item (item_B) if it previously received and stored said representation of the second value item;

otherwise

b2) sending to the first party a message preventing an abort operation, if a respective entry [to prevent an abort] was previously entered into its storage;

otherwise

b3) sending to the first party a message that the exchange is aborted, and entering a respective entry into its storage.

11. A method in accordance with claim 8 and claim 10 in which

the first party includes in the abort request, besides the first permit, the pre-image r of the authenticator;

and

the third party computes f(r) and checks whether the result corresponds to the authenticator (v) included in the received first permit (perm_A), prior to executing one of the conditonal steps b1, b2, or b3.

12. A method in accordance with claim 4, in which a second subprotocol (B-RESOLVE) for requesting a resolving operation from an exceptional situation in an exchange procedure is provided which includes the following steps:

a) sending, by the second party (B), a resolve request to the third party (T) including the first permit (perm_A) and a representation of the second value item (item_B);

b) executing, by the third party, one of the following operations;

b1) extracting the authenticator (v) from the first permit (perm_A) for locating a respective_entry, and if it finds an entry in its storage that the exchange was aborted, sending a respective message to the second party;

otherwise

b2) checking whether the received representation of the second value item matches a description (desc_B) of an expected value item included in the first permit (perm_A) and, if the check fails, sending a message to the second party that the resolve request is invalid;

otherwise

b3) entering the received second value item (item_B) into its storage, and extracting the representation of the first value item (item_A) from the first permit (perm_A) and sending it to the second party.

13. A method in accordance with claim 4, in which a third subprotocol (A-RESOLVE) for requesting a resolving operation from an exceptional situation in an exchange procedure is provided which includes the following steps:

a) sending, by the first party (A), a resolve request to the third party (T) including the second permit (perm_B);

and

b) executing, by the third party, one of the following operations;

b1) sending to the first party a message that the exchange was aborted if it finds a respective entry in its storage;

otherwise

b2) extracting the representation of the second value item (item_B) from the second permit (perm_B) and sending it to the first party, and entering an entry into its storage that an abort operation is not allowed.

14. A method in accordance witch claim 8 and claim 13, in which

the first party includes in the resolve request, besides the second permit, the pre-image r of the authenticator;

and

the third party computes f(r) and checks whether the result corresponds to the authenticator (v) included in the received second permit (perm_B), prior to executing one of the conditonal steps b1 or b2.

20. A method in accordance with claim 19, in which

said bit string x is a combination of a description (desc_V) of the value item expected from the verifying party (V), the authenticator (v), and the identifier (T) of the third party.