Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1998-12-22
2002-10-29
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
Public key
C380S286000
Reexamination Certificate
active
06473508
ABSTRACT:
BACKGROUND—FIELD OF INVENTION
The field of this invention is cryptography. This invention relates to digital signature schemes, and in particular to schemes that are compatible with any escrowed encryption system. The scheme introduces a public key/private key system in which the public key is auto-certifiable and is effective only as a digital signature verification key, and is not effective at performing unescrowed encryptions of data. Furthermore, the private signing key in the system is not escrowed. If the public key is ever used to encrypt data then that data is auto-recoverable by trusted authorities. The invention relates to cryptosystems implemented in software, but is also applicable to cryptosystems implemented in hardware. In particular the invention can be employed as the signature and authentication component in conjunction with escrowed encryption schemes.
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. In the same paper by Diffie and Hellman the notion of a digital signature scheme was also proposed. A digital signature scheme allows a user to digitally “sign” a message using the private key known only to the user, to prove that the message comes from the user. To sign a message M, the user computes a signature using the private key D. The signature can then be verified using the public key E. A PKC and digital signature scheme 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).
Since the present invention discloses a method for generating, publishing, and employing public key systems based upond a digital signature algorithm which is based on the problem of computing discrete logarithms, we will cite relevant prior art dealing with discrete log based signature schemes. The first space efficient digital signature scheme based on discrete logarithms is the Digital Signature Algorithm (U.S. Pat. No. 5,231,668). DSA gets its security from the difficulty of computing discrete logs modulo the prime p, where p is at least 512 bits in size. It also gets its security from the difficulty of computing discrete logs in a cyclic subgroup of order q, where q is a 160 bit prime divisor of p−1. DSA is novel in that the signatures that it outputs are 320 bits in length. Nyberg and Rueppel disclosed a set of ElGamal based variants that provide for message recovery (K. Nyberg, R. Rueppel, “Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem, Eurocrypt '94, pages 182-193, 1994). The message recovery feature allows the message to be recovered from the signature itself, hence the message need not be sent along with the signature. Another important feature of digital signature schemes is blindability (D. Chaum, “Blind Signatures for Untraceable Payments”, CRYPTO '82, pages 199-203). A scheme is blindable if it is possible for Alice to obtain a Bob's signature on a message of her choice such that Bob remains oblivious as to what he is signing and what the resulting signature is. In (D. Chaum, T. Pedersen, “Wallet Databases with Observers”, CRYPTO '92, pages 89-105) a blindable scheme based on ElGamal is disclosed. A good overview of digital signature security is described in (S. Goldwasser, S. Micali, R. Rivest, “A digital Signature Scheme Secure Against Adaptive Chosen Message Attacks”, SIAM J. Comput., vol. 17, n. 2, pages 281-308, 1988).
In the U.S. Patent Document entitled “Auto-Escrowable and Auto-Certifiable Cryptosystems” (by Young and Yung), a public key cryptosystem was disclosed that has 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 draws many of its ideas from the Auto-Escrowable and Auto-Certifiable key escrow solution but concentrates on signature keys that have the feature that encryptions using the public verification key are auto-recoverable. Other methods for conducting key escrow are U.S. Pat. Nos. 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-Escrowable 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, see also U.S. Pat. No. 5,647,000 to Leighton), 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 multi-round protocol in order to generate public/private key pairs. Other key escrow systems with similar inneficiencies are by De Santis et al., Walker and Winston (TIS), and the IBM SecureWay document. 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 provides for session level key recoverability, and makes no provision for preventing users from encrypting messages prior to using the Binding ElGamal system. Hence, it permits conspiring criminals to conduct untappable communications. Both Binding ElGamal and the Auto-Escrowable and Auto-Certifiable Cryptosystems solutions employ the use of non-interactive zero-knowledge proofs. More specificly, 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). 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 encumbersome solution as well. Such solutions are described in the TIS patent (U.S. Pat. Nos. 5,557,346, 5,557,7
Young Adam Lucas
Yung Marcel Mordechay
Hayes Gail
Schweitzer Cornman Gross & Bondell LLP
Song Ho S.
LandOfFree
Auto-recoverable auto-certifiable cryptosystems with... 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 auto-certifiable cryptosystems with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Auto-recoverable auto-certifiable cryptosystems with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2957892