Method and apparatus for simultaneous electronic exchange using a semi-trusted third party

• US 6,263,436 B1
• Filed: 12/17/1996
• Issued: 07/17/2001
• Est. Priority Date: 12/17/1996
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Franklin, Matthew Keith, Reiter, Michael Kendrick
• Primary Examiner(s): Hayes, Gail
• Assistant Examiner(s): Seal, James
• Application Number:
  US08/768,380
• Time in Patent Office: 1,673 Days
• Field of Search: 380/23, 380/24, 380/25, 380/30, 380/49, 380/21, 395/186, 395/187.01, 235/379, 705/75, 705/80, 705/69, 713/176, 713/170, 713/171, 713/169, 713/168, 713/167
• US Class Current: 713/167
• 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/04 Payment circuits
• CPC Class Codes: G06Q 20/12 specially adapted for electronic shopping systems
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A method and apparatus for fairly exchanging documents. A first document is shared between principal Y and third party Z. A second document is shared between principal X and third party Z. Z verifies that the sharing of the first and second documents has been performed correctly without Z understanding either document. If verified, Z sends its shares of the first and second documents to Y and X, respectively. X and Y verify that Z'"'"'s shares are authentic.

Claims

1. An apparatus for fairly exchanging documents over a network, comprising:

means for sharing a first document of a principal X between a principal Y and a third party Z;

means for sharing a second document of said principal Y between said principal X and said third party Z;

means for providing a one-way hash of said first document to said principal Y and said third party Z;

means for providing a one-way hash of said second document to said principal X and said third party Z;

means for verifying by Z that said sharing of said first and second documents has been performed correctly, without revealing said first or second document to Z, and without comparing shares of said first and second documents to each other;

means for sending Z'"'"'s shares of said first and second document to Y and X, respectively, once Z verifies said sharing has been performed correctly;

means for Y to verify Z'"'"'s share of said first document; and

means for X to verify Z'"'"'s share of said second document.

2. The apparatus described in claim 1, characterized in that said means for sharing use a 2-out-of-2 secret sharing scheme.

3. The apparatus described in claim 2, characterized in that said means for sharing use a one-way function f known to X, Y and Z.

4. The apparatus described in claim 3, characterized in that said means for sharing use a one-way hash h to X, Y and Z.

5. The apparatus described in claim 4, characterized in that said means for verifying use a checksum function F.

6. An apparatus for permitting simultaneous electronic transactions, comprising:

a first document held by a first principal;

a second document held by a second principal;

a one-way hash of said first document in possession of said second principal and a semi-trusted third party, and a one-way hash of said second document in possession of said first principal and said third party;

means for splitting said first document into section A and section B, and said second document into section C and section D;

means for exchanging said section A for said section C;

means for sending sections B and D to said third party;

means for said first and second principal to produce a checksum of section C and section A, respectively, and sending said checksums to said third party;

means for verifying by said third party that sections A and B comprise said first document, and that sections C and D comprise said second document;

means for sending said section B to said second principal and said section D to said first principal once said third party verifies said sharing has been performed correctly; and

means for authenticating by said first and second principals receipt of said second and first documents, respectively.

7. A method for fairly exchanging documents over a network, comprising:

sharing a first document of a principal X between a principal Y and a third party Z;

sharing a second document of said principal Y between said principal X and said third party Z;

providing a one-way hash of said first document to said principal Y and said third party Z;

providing a one-way hash of said second document to said principal X and said third party Z;

verifying by Z that said sharing of said first and second documents has been performed correctly, without revealing said first or second document to Z, and without comparing shares of said first and second documents to each other;

sending Z'"'"'s shares of said first and second document to Y and X, respectively, once Z verifies said sharing has been performed correctly;

verifying by Y that Z'"'"'s share of said first document is from said first document; and

verifying by X that Z'"'"'s share of said second document is from said second document.

8. The method described in claim 7, characterized in that said sharing is accomplished using a 2-out-of-2 secret sharing scheme.

9. The method described in claim 8, characterized in that said sharing is accomplished using a one-way function f known to X, Y and Z.

10. The method described in claim 9, characterized in that said sharing is accomplished using a one-way hash h to X, Y and Z.

11. The method described in claim 10, characterized in that said verifying is accomplished using a checksum function F.

12. A method for simultaneously exchanging a first document held by a first principal for a second document held by a second principal through a semi-trusted third party over a network, comprising the steps of:

providing a one-way hash of said first document to said second principal and said semi-trusted third party, and a one-way hash of said second document to said first principal and said third party;

splitting said first document into section A and section B, and said second document into section C and section D;

exchanging said section A for said section C;

providing sections B and D to said third party;

producing a checksum for section C and section A, and sending said checksums to said third party;

authenticating by said third party using said checksums that sections A and B comprise said first document, and that sections C and D comprise said second documents;

sending said section B to said second principal and said section D to said first principal once said documents match said checksums; and

authenticating by said first and second principals that they have correctly received said second and first documents, respectively.

13. A document exchange method, comprising:

splitting a first document into a first share A and a second share B;

sending said first share A to a principal Y;

sending said second share B to a third party Z;

receiving from the principle Y a first share C of a second document;

sending a checksum of said first share C to the third party Z;

receiving from the third party Z a second share D of said second document, and an indication that said first share A and said second share B comprise said first document, and said first share C and said second share D comprise said second document; and

assembling the second document from said first share C and said second share D.

14. A document exchange method, comprising:

receiving from a principle X a first share A of a first document;

receiving from a principle Y a first share C of a second document;

receiving from the principal X a checksum of a second share D of said second document after the principle Y sends said second share D to the principle X;

receiving from the principal Y a checksum of a second share B of said first document after the principle X sends said second share B to the principle Y;

verifying that said first share A and said second share B of said first document comprise said first document, and that said first share C and said second share D of said second document comprise said second document; and

sending said first share A to the principle Y and sending said first share C to the principle X, once said verifying has been performed correctly.