Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Security kernel or utility
Reexamination Certificate
1996-12-17
2001-07-17
Hayes, Gail (Department: 2131)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Security kernel or utility
C713S168000
Reexamination Certificate
active
06263436
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates generally to electronic commerce and transactions. More particularly, the invention relates to techniques for enabling users to engage in fair or simultaneous electronic transactions using a semi-trusted third party, and in the case of fraudulent behavior by a user, prevent the disclosure of any electronic information until the exchange, and authentication of information is complete.
Recently there has been a proliferation of information networks such as computer, telephone, cable, energy and others. The presence of these networks has tremendously improved the efficiency and convenience of many transactions (i.e., exchanges) while lowering associated costs. Yet more recently, digital signatures and public-key encryption have added much needed security to these electronic transactions. This functionality makes electronic communication channels articularly suitable for financial transactions, i.e., electronic commerce.
A problem endemic to electronic transactions is the need for simultaneity. The term “simultaneity” as used herein means an electronic transaction that is structured to guarantee certain actions will take place if and only if certain other actions take place. In the case of payment protocols, simultaneity can ensure that a customer receives a document from a vendor if and only if the vendor receives payment from the customer. Similarly, simultaneity can ensure that a certified electronic mail is delivered to its destination if and only if proof of that delivery is given to its sender.
The absence of simultaneity in electronic transactions severely limits electronic commerce. This can be illustrated using certified electronic mail as an example. A certified mail transaction typically includes a sender, e.g., Tracey, who wishes to deliver a given message to an intended recipient, e.g., Alex. Tracey could try to get a receipt from Alex of an electronic message m by sending m to Alex in clear text form, i.e., unencrypted. If message m was something as important as Tracey's electronic signature for an electronic payment, a dishonest Alex might be motivated to discontinue the conversation once he receives m. Alex could therefore deprive Tracey of any proof of delivery. Conversely, Alex may find unacceptable the idea of sending a blank receipt to Tracey prior to receiving m.
The simultaneity problem does not disappear by simply adding a few more rounds of communication. For example, it is possible for Tracey to send Alex an encryption of m, for which Alex would return his digital signature of this ciphertext as an “intermediate” receipt. Tracey would then send him the decryption key, for which Alex would send a final receipt.
This transaction does not guarantee simultaneity as well. It simply adds one more layer of complexity which merely delays the point where Alex may engage in dishonest behavior. Alex may refuse to send Tracey any receipt after receiving Tracey's decryption key. Alex's signature of the encrypted message would not constitute a valid receipt since there is no proof that Tracey sent Alex her key.
Various cryptographic approaches exist in the literature that attempt to solve similar problems, but they are not satisfactory in many respects. Some of these methods applicable to multi-party scenarios propose use of verifiable secret sharing, or multi-party protocols for making simultaneous some specific transactions between parties. These methods, however, require a plurality of parties. Furthermore, a majority of these party members must be honest. This greatly increases the complexity of the transaction. Furthermore, these methods require several rounds of transmission, which greatly increases overhead. Thus, these techniques are generally impractical. Moreover, these techniques are incapable of ensuring simultaneity for two party transactions.
Sophisticated cryptographic transactions between two parties have been developed. These cryptographic transactions, however, do not guarantee simultaneity. As illustrated with our certified electronic mail example, these techniques merely delay the point at which dishonest behavior can occur.
There have been several specific attempts made at providing simultaneity for two-party transactions. These attempts, however, use assumptions or methods that are unsatisfactory in various ways. For example, an article by M. Blum titled “How to exchange (secret) keys,”
ACM Transactions on Computer Systems,
vol. 1, No. 2, May 1983, pp. 175-193, describes transactions that include contract signing and certified mail. These techniques, however, are very complex and require a large number of rounds of communication.
The method of Luby et al. given in a paper titled “How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin,” 1983, allows two parties to exchange the decryption of two given ciphertexts in a special way. Both parties leak information to each other such that the probability that one party will guess correctly the clear text of the other is slowly increased towards 100%. This method, however, does not guarantee simultaneity since one party could quit the protocol with a slight advantage.
The most recent attempts for achieving simultaneity for two party transactions involve the use of one or more external entities. These external entities are often referred to as “centers”, “servers” or “trustees.” Examples of the use of external entities to achieve fair exchange is outlined in a paper by S. Ketchpal titled “Transaction protection for information buyers and sellers,”
Proceedings of the Dartmouth Institute for Advanced Graduate Studies '
95, 1995. These external entities are referred to as “fully-trusted” third parties since they are assumed to be honest. The techniques using fully-trusted third parties, however, quickly break down in the presence of dishonest behavior in the case of human third parties, or equipment malfunction or tampering in the case of electronic third parties. Moreover, these techniques are incapable of determining whether the third party is operating in the proper manner.
SUMMARY OF THE INVENTION
In view of the foregoing, there exists a substantial need in the art for simultaneous electronic transactions (SET), otherwise known as “fair exchange.” More particularly, there exists a substantial need in the art for a “fair exchange protocol” which allows two parties to exchange electronic content if and only if certain actions take place, thereby preventing either party, or a third party, to gain an advantage by quitting prematurely or otherwise engaging in fraudulent activity.
The invention permits two principal parties (“principals”) to fairly exchange electronic information or content (“documents”) through a semi-trusted third party over information networks such as computer, telephone, cable, energy and others (“networks”). A semi-trusted third party is distinguished from a fully-trusted third party in that either principal may detect when the semi-trusted third party misbehaves on its own, but not if it conspires with a principal.
The invention gives both principals the ability to control transmission of their document to the other principal. The invention also allows each principal and the third party to determine whether there is any faulty, dishonest or incorrect behavior, e.g., the wrong document is being sent or the requested document is being withheld. In addition, the invention prevents both principals from gaining access to any portion of the other's document unless each have received and authenticated the other's complete document. The third party never gains access to either document under any circumstances.
The invention accomplishes this using an apparatus and 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. The invention provides a one-way hash of the first document to the second principal and semi-trusted third party, and a one-way hash of the second
Franklin Matthew Keith
Reiter Michael Kendrick
AT&T Corp.
Hayes Gail
Kenyon & Kenyon
Seal James
LandOfFree
Method and apparatus for simultaneous electronic exchange... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for simultaneous electronic exchange..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for simultaneous electronic exchange... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2566459