Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1997-09-17
2002-05-14
Elmore, Reba I. (Department: 2187)
Cryptography
Particular algorithmic function encoding
C380S030000, C380S044000, C713S156000, C713S180000
Reexamination Certificate
active
06389136
ABSTRACT:
BACKGROUND—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 or in hardware. In particular, the invention relates to the generation of user public keys based on composite numbers and on the hardness of number factoring, and relates to implementing a hierarchical key escrow system.
BACKGROUND—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).
The current invention relates to key escrow systems. Prior methods for conducting key escrow are U.S. Pat. No. 5,276,737, and 5,315,658 which are due to Micali (1994). In these patents Micali discloses a Fair Public Key Cryptosystem (FPKC) which is based on the work of P. Feldman (28th annual FOCS). The FPKC solution is not as efficient in terms of use as Auto-Recoverable and Auto-Certifiable Cryptosystems. Furthermore, 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. Kilian and Leighton disclose a Fail-safe Key Escrow system. This system has the drawback that it requires users to engage in a costly multi-round protocol in order to generate public/private key pairs. Other key escrow systems with similar inefficiencies are by De Santis et al., Walker and Winston (TIS), and the IBM SecureWay document. These solutions propose session-level escrow which requires changes in communication protocols. 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, called Binding ElGamal, provides for session level key recoverability, and makes no provision for preventing users from encrypting messages using the provided unescrowed public key infrastructure prior to using the Binding ElGamal system. Hence, it permits conspiring criminals to conduct untappable communications. Binding ElGamal also imposes a large amount of communication overhead per communications session. An overview of key escrow schemes appears in (D. Denning, D. Branstad, “A Taxonomy for Key Escrow Encryption Systems,”Communications of the ACM, v. 39, n. 3, 1996). In (N. Jefferies, C. Mitchell, M. Walker, “A Proposed Architecture for Trusted Third Party Services”, Cryptography: Policy and Algorithms, LNCS 1029, Springer, 1996) and (R. Anderson, “The GCHQ Protocol and Its Problems”, Eurocrypt '97, pages 134-148, Springer-Verlag, 1997) a trusted third party approach to escrow is described where the trusted third parties of the participating users are involved in every session key establishment stage, and hence provides for another cumbersome solution as well.
In the pending U.S. Pat. Nos. 08/864,839, 08/878,189, and “Auto-Recoverable And Auto-Certifiable Cryptosystems with Fast Key Generation” filed Aug. 29, 1997 (by Young and Yung), Auto-Recoverable and Auto-Certifiable public key cryptosystems were disclosed that have the following properties. Users of the system can generate a public/private key pair and a certificate of recoverability. This certificate of recoverability can be used to both recover the private key by the escrow authorities, and verify that the private key is recoverable. The present invention is a new Auto-Recoverable and Auto-Certifiable key escrow solution. The main restriction of the prior Auto- Recoverable and Auto-Certifiable cryptosystems that were proposed is that it is not possible to generate user public and private keys that are based on the difficulty of factoring. Such cryptosystems based on a multiple of two large prime numbers, for example, are popular. Inn particular the RSA system by Rivest et. al (Rivest 1983) is very popular. The previous Auto-Recoverable and Auto-Certifiable systems based users'keys on the hardness of the problem of computing discrete logarithms. Indeed, it could be the case that computing discrete logs is not as hard as is currently believed, but that factoring is hard. Thus for this reason, there is a significant advantage to an Auto-Recoverable and Auto-Certifiable cryptosystem based on the difficulty of factoring, as in the present invention. The present invention discloses an Auto-Recoverable and Auto-Certifiable cryptosystem in which the public key of the escrow authorities and the public keys of the users are based on the hardness of factoring composites. In another embodiment the escrow authorities keys are based on the discrete log problem.
The present invention also introduces a new notion, the notion of a key escrow hierarchy which is a method with new functionality. We disclose a method for implementing a key escrow hierarchy that takes the form of a tree. This tree has the property that any node has the ability to recover the communications of nodes of the subtree for which it is the root. Thus, the root node of the entire tree is able to recover the communications of all users of the system. Such a system is ideal for implementing national and multinational Public Key Infrastructures (PKI). For instance, a national PKI for the U.S. could be implemented as a depth-3 tree. The federal government could be the root. The state governments could be the middle nodes, and the residents of each state could be the leaves. This would allow the federal government to decrypt all communications, and would restrict the state governments to only be able to decrypt the communications of the states own residents.
Both Binding ElGamal and the Auto-Recoverable and Auto-Certifiable Cryptosystems solutions employ the use of non-interactive proofs. More specifically, they employ the Fiat Shamir heuristic which is disclosed in (A. Fiat, A. Shamir, “How to Prove Yourself: Practical Solutions to Identification and Signature Problems”, CRYPTO '86, pages 186-194, Springer-Verlag, 1987). It is known in the art how to replace non-interactive proofs by interactive proofs. The variant of proofs introduced by our mechanism is a proof that combines a zero-knowledge methodology with explicit encryption of values to a third party.
SUMMARY OF THE I
Young Adam Lucas
Yung Marcel Mordechay
Elmore Reba I.
Schweitzer Cornman Gross & Bondell LLP
LandOfFree
Auto-Recoverable and Auto-certifiable cryptosystems with RSA... 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-Recoverable and Auto-certifiable cryptosystems with RSA..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Auto-Recoverable and Auto-certifiable cryptosystems with RSA... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2888026