Simultaneous electronic transactions

• US 5,666,420 A
• Filed: 11/18/1996
• Issued: 09/09/1997
• Est. Priority Date: 03/21/1995
• Status: Expired due to Term

• Current Assignee: Silvio Micali
• Original Assignee: Silvio Micali
• Inventors: Micali, Silvio
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/751,217
• Time in Patent Office: 295 Days
• Field of Search: 380/9, 380/30, 380/25
• US Class Current: 380/30
• CPC Class Codes: G06F 2211/008 Public Key, Asymmetric Key, Asymmetric Encryption
• CPC Class Codes: G06F 2211/009 Trust
• CPC Class Codes: G06Q 20/00 Payment architectures, schemes or protocols apparatus for performing or posting payment transactions G07F7/08, G07F19/00; electronic cash registers G07G1/12
• 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/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/3825 Use of electronic signatures
• CPC Class Codes: G06Q 20/388 using mutual authentication without cards, e.g. challenge-response
• CPC Class Codes: G06Q 20/389 Keeping log of transactions for guaranteeing non-repudiation of a transaction
• CPC Class Codes: G06Q 20/401 Transaction verification
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G06Q 50/188 Electronic negotiation
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 2463/102 applying security measure for e-commerce
• CPC Class Codes: H04L 51/23 Reliability checks, e.g. acknowledgments or fault reporting
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/085 : Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/321 : involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3247 : involving digital signatures

Abstract

A communication method between a first and second party, in the presence of a trusted party, that enables a transaction in which the second party receives a first value produced by the first party and unpredictable to the second party if and only if the first party receives a second value produced by the second party and unpredictable to the first party. The method includes two basic steps: exchanging a first set of communications between the first and second parties without participation of the trusted party to attempt completion of the transaction, and if the transaction is not completed using the first set of communications between the first and second parties, having the trusted party take action to complete the transaction.

Claims

1. An electronic communication method between a first and second party, in the presence of a trusted party, enabling an exchange of unpredictable values in which the second party receives a first value produced by the first party and unpredictable to the second party if and only if the first party receives a second value produced by the second party and unpredictable to the first party, wherein at least one of the parties uses an electronic device comprising the steps of:

exchanging a first set of communications between the first and second parties without participation of the trusted party to attempt completion of the exchange of unpredictable values wherein at least one of the communications is carried out electronically; and

if the exchange of unpredictable values is not completed using the first set of communications between the first and second parties, having the trusted party take action to complete the exchange.

2. The communication method as described in claim 1 wherein the first party'"'"'s value is a message and the second party'"'"'s value is a receipt, such that the exchange of unpredictable values is a certified transmission of the first party'"'"'s message.

3. The communication method as described in claim 1 wherein the first party can prove that some information it receives is the second value.

4. The communication method as described in claim 1 wherein the second party can prove that some information it receives is the first value.

5. The communication method as described in claim 1 wherein the first party can prove that some information it receives is the second value and the second party can prove that some information it receives is the first value.

6. The communication method as described in claim 1 wherein the first party'"'"'s value represents a commitment to a contract and the second party'"'"'s value represents a commitment to the contract, such that the exchange of unpredictable values closes a contract.

7. The communication method as described in claim 6 wherein the first party can prove that some information it receives is the second value and the second party can prove that some information it receives is the first value.

8. The communication method as described in claim 1 wherein at least one of the first and second parties and the trusted party can encrypt messages, and at least one of the first and second parties and the trusted party can decrypt messages.

9. The communication method as described in claim 8 wherein at least one communication of the first party includes a data string generated by a process including encrypting a second data string with an encryption key of the trusted party.

10. The communication method as described in claim 9 wherein the second data string includes a ciphertext generated with an encryption key of one of the parties.

11. The communication method as described in claim 9 wherein the second data string contains information identifying at least one of the parties.

12. The communication method as described in claim 8 wherein at least one communication of the second party includes a data string generated by a process that includes having the second party digitally sign a data string computed from information received from the first party in a prior communication, wherein the data string generated by the second party is the second party'"'"'s value.

13. The communication method as described in claim 8 wherein if the second party does not get the first value in the first set of communications, the second party sends the trusted party for further processing a data string that includes at least part of the data received from the first party.

14. The communication method as described in claim 13 wherein the further processing by the trusted party includes decrypting a ciphertext with a secret decryption key.

15. The communication method as described in claim 14 wherein the trusted party sends the first party information that enables the first party to compute the second value, and the trusted party sends the second party information that enables the second party to compute the first value.

16. The communication method as described in claim 15 wherein the trusted party also verifies identity information of at least one of the parties and does not learn the first value.

17. The communication method as described in claim 1 wherein the trusted party takes no action to complete the transaction after a specified time.

18. The communication method as described in claim 17 wherein the specified time is included within the first set of communications.

19. The communication method as described in claim 17 wherein the specified time is determined by the time at which certain communications occur.

20. A method by which first and second parties and a trusted party effect a certified mail transaction, each of the parties having matching public and secret keys of a public key encryption scheme, and wherein the first party desires to send a message to the second party and obtain a message receipt to thereby complete the certified mail transaction, comprising the steps of:

(a) having the first party generate and send to the second party a data string including an encryption, with the trusted party'"'"'s public key, of information that prevents the second party from obtaining the first party'"'"'s message without the first party obtaining the message receipt;

(b) upon receipt by the second party of the data string, having the second party generate and send to the first party the message receipt;

(c) upon receipt by the first party of the message receipt, having the first party send to the second party information that enables the second party to retrieve the message;

(d) having the second party attempt to verify whether the message was received; and

(e) if the message was not received, having the second party send information to the trusted party for further processing, wherein the information includes the data string.

21. The method as described in claim 20 further including the step of:

(f) having the trusted party, using the information received from the second party, (i) decrypt some information it receives from the second party using the secret key of its public key encryption scheme to thereby generate a version of the message understandable to the second party, and (ii) to verify that information is obtained that identifies at least the first party as a genuine sender of the message.

22. The method as described in claim 21 further including the unordered steps of:

(g) having the trusted party send the first party, as the message receipt, information that includes data generated by the second party; and

(h) having the trusted party send the second party information from which the second party can retrieve the message.

23. The method as described in claim 20 wherein at least one of the first and second parties and the trusted party includes a physically secure device.

24. The communication method as described in claim 20 wherein further processing by the trusted party does not occur after a specified time.

25. The communication method as described in claim 24 wherein the specified time is determined by at least one communication between the first and second parties.

26. The communication method as described in claim 24 wherein the specified time is determined by the time at which certain communications occur.

53. The method as described in claim 21 further including the unordered steps of:

having the trusted party send the first party information vouching that the trusted party has transmitted to the second party a version of the message understandable by the second party; and

having the trusted party send the second party information from which the second party can retrieve the message.

55. The method as described in claim 20 wherein the message receipt can be used to prove the content of the message.

57. The method as described in claim 21 wherein the trusted party also verifies that information is obtained that identifies the second party as a genuine recipient of the message.

27. An electronic communication method between a first and second party, in the presence of a plurality of trustees, enabling an exchange of unpredictable values in which the second party receives a first value produced by the first party and unpredictable to the second party if and only if the first party receives a second value produced by the second party and unpredictable to the first party, comprising the steps of:

exchanging a first set of communications between the first and second parties without participation of any of the trustees to attempt completion of the exchange of unpredictable values, wherein at least one of the parties uses an electronic device and at least one of the first set of communications is carried out electronically; and

if the exchange of unpredictable values is not completed using the first set of communications between the first and second parties, having a given number of the trustees take action to complete the exchange.

28. The communication method as described in claim 27 wherein the plurality of trustees hold shares of a given secret key.

29. The communication method as described in claim 27 wherein at least one of the first and second parties and at least some of the trustees can encrypt messages, and at least one of the first and second parties and at least some of the trustees can decrypt messages.

30. The communication method as described in claim 27 wherein at least one communication of the second party is a data string generated by a process that includes having the second party digitally sign a data string computed from information received from the first party in a prior communication, wherein the data string generated by the second party comprises the second party'"'"'s value.

31. The communication method as described in claim 30 wherein if the second party does not get the first value in the first set of communications, the second party causes at least some of the trustees to receive a data string that includes at least part of the data received from the first party.

32. The communication method as described in claim 27 wherein the trustees take no action to complete the exchange after a specified time.

33. The communication method as described in claim 32 wherein the specified time is determined by the first set of communications.

34. The communication method as described in claim 32 wherein the specified time is determined by the time at which certain communications occur.

35. In a communications network wherein first and second parties desire to effect an exchange of unpredictable values in a manner that is overseen by a trusted party of the network, each of the first and second parties having a value that cannot be predicted by the other of the first and second parties, and wherein the exchange of unpredictable values is complete when the first party receives the value generated by the second party and the second party receives the value generated by the first party, a communication method comprising the steps of:

exchanging a first set of communications between the first and second parties without participation of the trusted party to attempt completion of the exchange of unpredictable values, wherein at least one of the parties uses an electronic device and at least one of the first set of communications is carried out electronically; and

if the exchange of unpredictable values is not completed using the first set of communications between the first and second parties, having the trusted party take action to complete the exchange.

36. In the communications network as described in claim 35 wherein at least one of the first and second parties is a computer.

37. In the communications network as described in claim 35 wherein the trusted party is a computer.

38. In the communications network as described in claim 35 wherein at least one of the first and second parties is a secure device.

39. An electronic communication method between a first and second party enabling an exchange of unpredictable values in which the second party receives a first value produced by the first party and unpredictable to the second party if and only if the first party receives a second value produced by the second party and unpredictable to the first party, comprising the steps of:

in a first set of communications between the first and second party wherein at least one of the first set of communications is carried out electronically, having the first party generate an encryption of a string from which the second party can compute the first value, wherein the encryption is decryptable with a secret key known to the third party; and

if the exchange of unpredictable values is not completed using the first set of communications, having the third party take action to complete the exchange, wherein the action includes decrypting the string from which the second party can compute the first value.

40. The method as described in claim 39 wherein the string also includes information that is selected from the group consisting of information specifying the first party, information specifying the second party, and information specifying the first and second parties.

41. The method as described in claim 39 wherein the key of the third party is held by a plurality of trustees.

42. The method as described in claim 39 wherein the first party comprises a plurality of entities.

43. The method as described in claim 39 wherein the second party comprises a plurality of entities.

44. The communication method as described in claim 39 wherein at least one of the parties takes no action to complete the exchange after a specified time.

45. The communication method as described in claim 44 wherein the specified time is specified by at least one of the parties.

46. The communication method as described in claim 44 wherein the specified time is determined by the time at which certain communications are received.

47. A communication method between a first and second party, in the presence of an invisible third party, enabling an exchange of unpredictable values, wherein at least one of the parties uses an electronic device, comprising the steps of:

having the first party generate an encryption of a message for the second party, wherein the encryption is decryptable with a secret key known to the third party; and

exchanging a first set of communications between the first and second parties without participation of the third party to attempt completion of the exchange of unpredictable values, wherein and at least one of the first set of communications is carried out electronically;

wherein the first party decrypts the encryption decryptable by the secret key known to the third party when the exchange of unpredictable values is completed without participation of the third party.

48. A communication method between a first and second party, in the presence of an invisible party, enabling a given transaction, wherein at least one party uses an electronic device, comprising the steps of:

exchanging a first set of communications between the first and second parties without participation of the invisible party to attempt completion of the given transaction, wherein at least one of the first set of communications includes a string encrypted in a manner decryptable by a secret key known to the invisible party; and

if the transaction is not completed using the first set of communications between the first and second parties, having the invisible party take action to complete the transaction, wherein the action taken by the invisible party includes decrypting the encrypted string using the secret key.

49. A method by which first and second parties and a trusted party effect a certified mail transaction, each of the parties having secret keys, and wherein the first party desires to send a message to the second party and obtain a message receipt to thereby complete the certified mail transaction, comprising the steps of:

(a) having the first party generate and send to the second party a data string including an encryption, decryptable with a secret key known to the trusted party, of information that prevents the second party from obtaining the first party'"'"'s message without the first party obtaining the message receipt;

(b) upon receipt by the second party of the data string, having the second party generate and send to the first party the message receipt;

(c) upon receipt by the first party of the message receipt, having the first party send to the second party information that enables the second party to retrieve the message;

(d) having the second party attempt to verify whether the message was received; and

(e) if the message was not received, having the second party send information to the trusted party for further processing, wherein the information includes the data string.

50. The method as described in claim 49 further including the step of:

(f) having the trusted party, using the information received from the second party, (i) decrypt some information it receives from the second party using a secret key to thereby generate a version of the message understandable to the second party, and (ii) verify that information is obtained that identifies at least the first party as a genuine sender of the message.

51. The method as described in claim 50 further including the unordered steps of:

(g) having the trusted party send the first party, as the message receipt, information that includes data generated by the second party; and

(h) having the trusted party send the second party information from which the second party can retrieve the message.

52. The method as described in claim 50 further including the unordered steps of:

having the trusted party send the first party information vouching that the trusted party has transmitted to the second party a version of the message understandable by the second party; and

having the trusted party send the second party information from which the second party can retrieve the message.

56. The method as described in claim 50 wherein the trusted party also verifies that information is obtained that identifies the second party as a genuine recipient of the message.

54. The method as described in 49 wherein the message receipt can be used to prove the content of the message.