Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Security kernel or utility
Reexamination Certificate
1997-05-28
2001-03-13
Peeso, Thomas R. (Department: 2767)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Security kernel or utility
C713S155000, C713S168000
Reexamination Certificate
active
06202150
ABSTRACT:
BACKGROUND
1. Field of Invention
The field of this invention is cryptography. This invention relates to cryptosystems, and in particular to the escrowing and recovering of cryptographic keys and data encrypted under cryptographic keys. The escrow and recovery process assures that authorized entities like law-enforcement bodies, government bodies, users, and organizations, can when allowed or required, read encrypted data. The invention relates to cryptosystems implemented in software, but is also applicable to cryptosystems implemented in hardware.
2. Description of Prior Art
Public Key Cryptosystems (PKC's) allow secure communications between two parties who have never met before. The notion of a PKC was put forth in (W. Diffie, M. Hellman, “New directions in cryptography”, IEEE Transactions on Information Theory, 22, pages 644-654, 1976). This communication can take place over an insecure channel. In a PKC, each user possesses a public key E and a private key D. E is made publicly available by a key distribution center, also called certification authority (CA), after the registration authority verifies the authenticity of the user (its identification, etc.). The registration authority is part of the certification authority. D is kept private by the user. E is used to encrypt messages, and only D can be used to decrypt messages. It is computationally impossible to derive D from E. To use a PKC, party A obtains party B's public key E from the key distribution center. Party A encrypts a message with E and sends the result to party B. B recovers the message by decrypting with D. The key distribution center is trusted by both parties to give correct public keys upon request. A PKC based on the difficulty of computing discrete logarithms was published in (T. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”, CRYPTO '84, pages 10-18, Springer-Verlag, 1985).
PKC's are highly convenient in terms of use, and permit users to conduct private communications over insecure channels. They may be used to initiate symmetric key systems like DES (Data Encryption Standard). PKC's have a drawback, however. Criminals can use PKC's in the course of criminal activity, since no provision is made to supply law enforcement with the necessary decryption keys and untappable criminal communications may result. It is therefore desirable to permit private communications exclusively to law abiding citizens. A general solution to this problem is to have each user submit a representation of his or her private key to trusted escrow authorities, or trustees. The shares are taken out of escrow in the event of a court authorized wire tap. Alternatively, key escrow provides a way to recover lost private keys in an organization, or keys of a file system.
Let us review some of the key escrow systems and show that all require more than a PKC alone. U.S. Pat. Nos. 5,276,737, and 5,315,658 to Micali (1994) disclose a Fair Public Key Cryptosystem (FPKC) (see also, S. Micali, “Fair Public-Key Cryptosystems”, CRYPTO '92, pages 113-138, Springer-Verlag, 1992) which satisfies the needs of law abiding citizens and law enforcement (and is based on P. Feldman, 28th annual FOCS). Micali's preferred embodiment discloses how to convert the Diffie-Hellman PKC, and the RSA PKC into Fair PKC's. In the preferred embodiment of the Fair Diffie-Hellman PKC, each user submits five shares to five central trustees (also known as “trusted third parties”) to register a public key. This solution is therefore not very scalable, since it requires the use of a small number of trusted authorities, and is thus very centralized. In the present invention, the user constructs a key pair such that the private key is provably escrowed automatically. Hence, no trusted third parties are needed whatsoever. The escrowed information can be sent to one of a multitude of decentralized certification authorities (CA's). In Micali's scheme each trustee verifies their respective shares. Provided the share is valid, the share is stored in a database. Each trustee then signs the values that were received and gives them to a key management center. The five authorities have the burden of securing and managing five private databases of shares. In the present embodiment, the key information is verified by a CA. Provided it has the correct form, the key is signed, and placed immediately in the database of public keys. There need only be one private database. Since only the CA is needed to manage user keys in the current embodiment, the least amount of communication overhead that is possible is achieved. In the Fair PKC's, only the trustees can verify that a key is escrowed properly. Verification is required since without it a user can easily generate keys which are not recoverable. In the current invention, everyone can verify this. This is particularly useful if, for example, a citizen suspects that a CA is failing to insure that its keys are properly escrowed.
It has been shown that the Fair RSA PKC does not meet certain needs of law enforcement (J. Kilian, F. Leighton, “Fair Cryptosystems Revisited”, CRYPTO '95, pages 208-221, Springer-Verlag, 1995), since a shadow public key cryptosystem can be embedded within it. A shadow public key system is a system that can be embedded in a key escrow system that permits conspiring users to conduct untappable communications.
The flaw in the RSA FPKC lies in the fact that it is assumed that criminals will use the same secret keys that were provided to the escrow authorities. The shadow cryptosystems make use of what is known in the art as subliminal channels that exist in the public keys of the PKC's. These channels are used to display the public keys of the shadow PKC. The Kilian and Leighton paper discloses how to convert PKC's into Fail-safe Key Escrow (FKE) systems. Specifically, they disclose how to construct FKE systems for discrete-log based PKC's like Diffie-Hellman and DSS. In their expensive protocol, the user and the trusted authorities engage in a protocol to generate the user's public and private keys. In so doing, the authorities are convinced that no subliminal information is contained in the resulting public key. The user is also convinced that the keys are escrowed properly. This system is similar to the Fair Diffie-Hellman PKC, except for the added overhead of this protocol. It is thus subject to the same inefficiencies as the Fair Diffie-Hellman PKC. In the present invention, the user chooses his or her own keys independently. With respect to the threat of shadow PKC's, the present invention relies on the fact that there is no known way to inconspicuously embed a significant number of bits within a modular exponentiation in a finite field. Hence, the exploitation of shadow cryptosystems in discrete-log PKC's seems remote.
DeSantis et al. teach an escrow system where trustees are able to open only messages in session rather than opening the key of the party suspected of criminal activity. This refines the notion of Fair Cryptosystems. Other technologies that teach how to open the session key of users rather than their permanent public key is by Walker and Winston (TIS) and the IBM SecureWay document. These key recovery technologies require that users be aware of and use the keys of the set of trustees at any session initiation. These technologies may be overburdening each and every user since they require new protocol extensions which are used in every communication session and further require users to store many keys beyond what is needed for a PKI.
A “Fraud-Detectable Alternative to Key-Escrow Proposals” based on ElGamal has been described in (E. Verheul, H. van Tilborg, “Binding ElGamal: A Fraud-Detectable Alternative to Key-Escrow Proposals”, Eurocrypt '97, pages 119-133, Springer-Verlag, 1997). This system allows users to send encrypted information along with a short proof that the encrypted information can be recovered by a set of trustees. So, this system has the adva
Young Adam Lucas
Yung Marcel Mordechay
Peeso Thomas R.
Schweitzer Cornman Gross & Bondell LLP
LandOfFree
Auto-escrowable and auto-certifiable cryptosystems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Auto-escrowable and auto-certifiable cryptosystems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Auto-escrowable and auto-certifiable cryptosystems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2501070