Google Patentsopen access

Certificate-based encryption and public key infrastructure — Ntt Docomo, Inc. (US8074073B2)

ABSTRACT

Abstract

A digital message is sent from a sender to a recipient in a public-key based cryptosystem comprising an authorizer. The authorizer can be a single entity or comprise a hierarchical or distributed entity. In some embodiments, no key status queries or key escrow are needed. The recipient can decrypt the message only if the recipient possesses up-to-date authority from the authorizer. Other features are also provided.

Description

RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 10/521,741, filed Jan. 18, 2005, incorporated herein by reference (now U.S. Pat. No. 7,657,748, issued on Feb. 2, 2010), which is the U.S. national stage of PCT application PCT/US03/26834, filed Aug. 28, 2003, incorporated herein by reference, which claims the benefit of U.S. provisional patent applications Ser. No. 60/406,721, filed Aug. 28, 2002, and 60/412,221, filed Sep. 20, 2002, both which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

The present invention relates in general to cryptography and secure communication via computer networks or via other types of systems and devices, and more particularly to an improved method of implementation of public-key cryptography.

A user of a public-key cryptography based communication system communicates with another user by means of two different keys, a public key and a private key. A user's public key and private key form a public key/private key pair. A message sender communicates securely with a message recipient by encrypting a message using the recipient's public key. The sender then sends the message to the recipient who decrypts the message using the recipient's private key.

The security of messages sent to a user of a public-key based cryptography system depends on the security of the user's private key. Although the user's public key is freely available to other users, the user keeps its private key secret and known only to those privileged to receive messages sent to the user.

The implementation of public key cryptography requires an “infrastructure” to manage requirements such as key distribution and to certify for key validity. Before encrypting a message to a recipient, a message sender must have access to the recipient's public key. The sender must also confirm that this key is valid and not compromised.

In public-key cryptography systems, a trusted third party—the “certification authority” (CA) may perform functions such as key distribution and certification. Typically, the CA issues a “certificate” for each of its client users together with the CA's electronic signature to confirm the validity of the certificate. The certificate securely binds together several quantities. Usually, the certificate includes parameters such as the name of the client and the client's public key. Parameters such as the certificate's issue date and expiration date also may be included. By issuing a client's certificate, the CA attests that the associated public key is authentic and corresponds to the particular user for the validity period of the certificate.

Circumstances may require the revocation of a client's certificate before its intended expiration date. For example, revocation may be necessary if another party compromises the client's private key. Alternatively, the client may no longer be entitled to use the public key. If a certificate is revocable, then other users cannot rely on that certificate unless the CA distributes certification status information indicating that a certificate is currently valid. Such information must be up to date and distributed to all relying parties. Distributing such large amounts of information requires significant resources on the part of the CA and is a barrier to the widespread implementation of public-key cryptography.

The most well known—but inefficient—public-key infrastructure (PKI) proposal to address the key revocation issue is a certification revocation list (CRL). A CRL is a list of certificates revoked before their intended expiration date. The CA issues this list periodically together with its signature to confirm the validity of the CRL. Since the CA may revoke many certificates before their intended expiration date, the CRL may become very long, particularly if the CA has many clients. Each party requesting a certificate status check receives this list. Refinements to this approach require transmission of only those certificates revoked since the CA's last update. However, the transmission and infrastructure costs are still high.

An alternative proposal is the Online Certificate Status Protocol (OCSP). In this protocol, any user can query the CA as to the status of any client of the CA, including the validity of the client's public key. The CA responds to each query by generating a fresh signature on the certificate's current status. This proposal reduces transmission costs to a single signature per query. However, computation costs increase because a fresh signature is required in response to every query. Security also decreases because, if the CA is centralized, it becomes more vulnerable to denial-of-service (DoS) attacks.

A more promising protocol is the Micali “Novomodo” system. (S. Micali, Efficient Certificate Revocation, Proceedings of RSA Data Security Conference 1997; S. Micali, Novomodo: Scalable Certificate Validation and Simplified PKI Management, PKI Research Workshop, 2002.) The Novomodo system involves a CA, one or more directories to distribute certificate information, and the users. However, it achieves better efficiency than CRLs and OCSP, without sacrifices in security. The advantage of Novomodo over a CRL-based system is that a directory's response to a certificate status query is concise compared to a CRL protocol whereas the length of a CRL grows with the number of certificates revoked. Novomodo has several advantages over OCSP. First, the CA's computational load is much lower. Second, unlike the distributed components of an OCSP, the directories in Novomodo need not be trusted. Third, Novomodo is less susceptible to DoS attacks. Finally, although the directory-to-user communication costs of OCSP are low, Novomodo's are typically even lower. However, Novomodo still requires certification status queries.

Many refinements to protocols involving certificate status queries attempt to reduce PKI computation and transmission requirements and offer a variety of tradeoffs. However, there are several reasons for eliminating, or at least reducing, certificate status inquiries. First, such inquiries may come from any user and concern any client. Hence, every CA server in the system must be able to determine the certificate status for every client of the CA. Second, certificate status queries from the client multiply the query processing costs of the CA. If each of N clients queries the status of 10 other clients each day, the CA must process 10N queries. Third, nonclient queries are undesirable from a business model perspective. It is unclear, economically, how the CA should handle queries from non-clients. Finally, as mentioned above, if the CA must respond to queries from non-clients, it becomes more susceptible to DoS attacks.

Identity-based cryptosystems eliminate third-party queries. Identity-based cryptosystems are public key cryptosystems in which the public key of a user derives from the user's identity (name, address, email address, IP address, etc.). A trusted third party generates a user's private key using the user's identity and a master secret held by the trusted third party. In such a system, a first user can encrypt a message to the second user without obtaining explicit information other than the second user's identifying information and parameters of the second user's CA. The second user can decrypt the message only if that user has received an updated private key from its CA.

The concept of an identity-based cryptosystem was proposed in A. Shamir, Identity - Based Cryptosystems and Signatures Schemes , A DVANCES IN C RYPTOGRAPHY —C RYPTO '84, Lecture Notes in Computer Science 196 (1984), Springer, 47-53. However, practical identity-based encryption schemes have not been found until recently. For instance, identity-based schemes were proposed in C. Cocks, An Identity - Based Encryption Scheme Based on Quadratic Residues , available at h-t-t-p://www.cesg.gov.uk/technology/id-pkc/media/ciren.pdf; D. Boneh, M. Franklin, Identity Based Encryption from the Well Pairing , A DVANCES IN C RYPTOLOGY —C RYPTO 2001, Lecture Notes in Computer Science 2139 (2001), Springer, 213-229; and D. Boneh, M. Franklin, Identity Based Encryption from the Well Pairing (extended version), available at h-t-t-p://www.cs.stanford.edu/˜dabo/papers/ibe.pdf. Cocks' scheme is based on the “Quadratic Residuosity Problem,” and although encryption and decryption are reasonably fast (about the speed of RSA), there is significant message expansion (i.e., the bit-length of the ciphertext is many times the bit-length of the plaintext). The Boneh-Franklin scheme bases its security on the “Bilinear Diffie-Hellman Problem,” and it is quite fast and efficient when using Weil or Tate pairings on supersingular elliptic curves or abelian varieties.

Existing identity-based cryptosystems, however, have had only limited acceptance. One major reason for this is that these systems involve key escrow. The CA knows all secrets in the cryptosystem because it generates the private keys of all users. As a result, existing identity-based cryptosystems have been vulnerable to passive attacks in which the CA, or any other party that discovers the master secret can determine shared secret of the two users.

There is a need for an efficient scheme allowing a recipient user of a cryptosystem to decrypt a secret message from a message sender only when a trusted third party certifies that the recipient holds a valid private key. Ideally, such a scheme should not require that the message sender query another party, including the third party, as to the status of the recipient's private key. Neither should such a scheme have the disadvantage of third party key escrow.

It therefore is an object of the present invention to provide an efficient protocol, not involving key status queries or key escrow, wherein a message recipient can decrypt a message from a message sender only if the recipient obtains authorization (e.g. up to date certification) from a third party. It is a further object of the present invention to provide such a protocol wherein the recipient's decryption ability is contingent upon authorization by several parties. Another object of the present invention is to provide such a protocol wherein the third party comprises a hierarchical authorization entity within the cryptosystem. It is yet another object of the present invention to provide an efficient method of providing a user with a private key having a short validity period. It is a further object of the invention to provide such a protocol that allows such communication in a system comprising a large number (e.g. millions) of users.

BRIEF SUMMARY OF THE PREFERRED EMBODIMENTS

The present invention provides methods for implementing a secure and practical certificate-based encryption scheme.

According to one aspect of the present invention, the method provides for encoding and decoding a digital message between a sender and a recipient in a public-key encryption scheme including the sender, the recipient and an authorizer. The method includes the steps of generating a recipient public key/recipient private key pair and a recipient encryption key. A key generation secret that is a secret of the authorizer is selected. A recipient decryption key is generated using at least the key generation secret and the recipient encryption key where a key formed from the recipient decryption key and a key formed from the recipient encryption key are a public key/private key pair.

The digital message is encrypted using at least the recipient public key and the recipient encryption key to create an encrypted digital message. The encrypted digital message is decrypted using at least the recipient private key and the recipient decryption key.

Another aspect of the present invention provides a method for sending a digital message between a sender and a recipient in a public-key encryption system including a plurality of authorizers, the plurality of authorizers including at least a root authorizer and a lower-level authorizer in a hierarchy between the root authorizer and the recipient. The method includes the steps of generating a recipient public key/private key pair and a recipient encryption key, where the recipient encryption key is generated using identity information of at least one of the recipient's ancestors.

A root key generation secret is selected and a root key generation parameter generated based on the root key generation secret. A recipient decryption key is then generated such that the recipient decryption key is related to the recipient encryption key, the root key generation secret and the associated root key generation parameter.

The digital message is encrypted using the recipient public key and a recipient encryption key to create an encrypted digital message, where a key formed from the recipient decryption key and a key formed from the recipient encryption key are a public key/private key pair. The encrypted digital message is decrypted using at least the recipient private key and the recipient decryption key.

Another aspect of the present invention provides a method of generating a decryption key for an entity in an encryption system including a plurality of authorizers, the plurality of authorizers including at least a root authorizer and lower-level authorizers in the hierarchy between the root authorizer and the entity. The method included the steps of generating a root key generation secret and a root key generation parameter based on the root key generation secret. A lower-level key generation secret for the lower-level authorizers is generated. A lower-level key generation parameter for lower-level authorizers is then generated using at least the lower-level key generation secret for its associated lower-level authorizer.

A decryption key generation schedule is established defining a validity period for a decryption key for the entity. The decryption key for the entity is generated such that the decryption key is related to at least the root key generation secret and one or more of the lower-level key generation secrets.

Another aspect of the present invention provides a method of sending a digital message between a sender and a recipient in a public-key encryption scheme including the sender, the recipient and a plurality of authorizers, where the recipient can decrypt the digital message only if it possesses authorization from the authorizers. The method includes the steps of generating a recipient public key/private key pair for the recipient and a secret key for each of the authorizers. A public key is generated for each of the authorizers using at least the secret key for its associated authorizer. A string of binary digits is signed with the secret key to generate a signature for each of the authorizers.

The digital message is encrypted to form a ciphertext using at least the recipient's public key, the public keys of the authorizers, and the strings of binary digits signed by the authorizers. The encrypted digital message is decrypted using at least the recipient's private key, and the signatures generated by the authorizers.

Another aspect of the present invention provides a method of sending a digital message between a sender and a recipient in a public key encryption scheme comprising the sender, the recipient and a plurality of authorizers including at least a root authorizer and lower-level authorizers in the hierarchy between the root authorizer and the recipient, where the recipient can decode the digital message only if it possesses authorization from the authorizers. The method includes the steps of generating a recipient public key/private key pair for the recipient and a secret key for the root authorizer and each of the lower level authorizers. A public key is generated for the root authorizer and each of the lower level authorizers using at least the secret key for the associated authorizer.

Documents, each containing the public key of each of the lower level authorizers, are certified to generate a signature, where the document containing the public key of each lower level authorizer is certified by the authorizer above it in the hierarchy. A document comprising the recipient public key and a parameter determining the validity of the recipient public key is certified by the authorizer immediately above the recipient in the hierarchy.

The digital message is encrypted to form a ciphertext using at least the recipient's public key, the public keys of the authorizers, and the documents. The encrypted digital message is decrypted using at least the recipient's private key and the signatures generated by the authorizers.

Another aspect of the present invention provides a method of encrypting and decrypting a digital message between a sender and a recipient in a public-key encryption scheme including the sender, the recipient and an authorizer. The method includes the steps of generating a recipient public key/recipi

RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 10/521,741, filed Jan. 18, 2005, incorporated herein by reference (now U.S. Pat. No. 7,657,748, issued on Feb. 2, 2010), which is the U.S. national stage of PCT application PCT/US03/26834, filed Aug. 28, 2003, incorporated herein by reference, which claims the benefit of U.S. provisional patent applications Ser. No. 60/406,721, filed Aug. 28, 2002, and 60/412,221, filed Sep. 20, 2002, both which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

The present invention relates in general to cryptography and secure communication via computer networks or via other types of systems and devices, and more particularly to an improved method of implementation of public-key cryptography.

A user of a public-key cryptography based communication system communicates with another user by means of two different keys, a public key and a private key. A user's public key and private key form a public key/private key pair. A message sender communicates securely with a message recipient by encrypting a message using the recipient's public key. The sender then sends the message to the recipient who decrypts the message using the recipient's private key.

The security of messages sent to a user of a public-key based cryptography system depends on the security of the user's private key. Although the user's public key is freely available to other users, the user keeps its private key secret and known only to those privileged to receive messages sent to the user.

The implementation of public key cryptography requires an “infrastructure” to manage requirements such as key distribution and to certify for key validity. Before encrypting a message to a recipient, a message sender must have access to the recipient's public key. The sender must also confirm that this key is valid and not compromised.

In public-key cryptography systems, a trusted third party—the “certification authority” (CA) may perform functions such as key distribution and certification. Typically, the CA issues a “certificate” for each of its client users together with the CA's electronic signature to confirm the validity of the certificate. The certificate securely binds together several quantities. Usually, the certificate includes parameters such as the name of the client and the client's public key. Parameters such as the certificate's issue date and expiration date also may be included. By issuing a client's certificate, the CA attests that the associated public key is authentic and corresponds to the particular user for the validity period of the certificate.

Circumstances may require the revocation of a client's certificate before its intended expiration date. For example, revocation may be necessary if another party compromises the client's private key. Alternatively, the client may no longer be entitled to use the public key. If a certificate is revocable, then other users cannot rely on that certificate unless the CA distributes certification status information indicating that a certificate is currently valid. Such information must be up to date and distributed to all relying parties. Distributing such large amounts of information requires significant resources on the part of the CA and is a barrier to the widespread implementation of public-key cryptography.

The most well known—but inefficient—public-key infrastructure (PKI) proposal to address the key revocation issue is a certification revocation list (CRL). A CRL is a list of certificates revoked before their intended expiration date. The CA issues this list periodically together with its signature to confirm the validity of the CRL. Since the CA may revoke many certificates before their intended expiration date, the CRL may become very long, particularly if the CA has many clients. Each party requesting a certificate status check receives this list. Refinements to this approach require transmission of only those certificates revoked since the CA's last update. However, the transmission and infrastructure costs are still high.

An alternative proposal is the Online Certificate Status Protocol (OCSP). In this protocol, any user can query the CA as to the status of any client of the CA, including the validity of the client's public key. The CA responds to each query by generating a fresh signature on the certificate's current status. This proposal reduces transmission costs to a single signature per query. However, computation costs increase because a fresh signature is required in response to every query. Security also decreases because, if the CA is centralized, it becomes more vulnerable to denial-of-service (DoS) attacks.

A more promising protocol is the Micali “Novomodo” system. (S. Micali, Efficient Certificate Revocation, Proceedings of RSA Data Security Conference 1997; S. Micali, Novomodo: Scalable Certificate Validation and Simplified PKI Management, PKI Research Workshop, 2002.) The Novomodo system involves a CA, one or more directories to distribute certificate information, and the users. However, it achieves better efficiency than CRLs and OCSP, without sacrifices in security. The advantage of Novomodo over a CRL-based system is that a directory's response to a certificate status query is concise compared to a CRL protocol whereas the length of a CRL grows with the number of certificates revoked. Novomodo has several advantages over OCSP. First, the CA's computational load is much lower. Second, unlike the distributed components of an OCSP, the directories in Novomodo need not be trusted. Third, Novomodo is less susceptible to DoS attacks. Finally, although the directory-to-user communication costs of OCSP are low, Novomodo's are typically even lower. However, Novomodo still requires certification status queries.

Many refinements to protocols involving certificate status queries attempt to reduce PKI computation and transmission requirements and offer a variety of tradeoffs. However, there are several reasons for eliminating, or at least reducing, certificate status inquiries. First, such inquiries may come from any user and concern any client. Hence, every CA server in the system must be able to determine the certificate status for every client of the CA. Second, certificate status queries from the client multiply the query processing costs of the CA. If each of N clients queries the status of 10 other clients each day, the CA must process 10N queries. Third, nonclient queries are undesirable from a business model perspective. It is unclear, economically, how the CA should handle queries from non-clients. Finally, as mentioned above, if the CA must respond to queries from non-clients, it becomes more susceptible to DoS attacks.

Identity-based cryptosystems eliminate third-party queries. Identity-based cryptosystems are public key cryptosystems in which the public key of a user derives from the user's identity (name, address, email address, IP address, etc.). A trusted third party generates a user's private key using the user's identity and a master secret held by the trusted third party. In such a system, a first user can encrypt a message to the second user without obtaining explicit information other than the second user's identifying information and parameters of the second user's CA. The second user can decrypt the message only if that user has received an updated private key from its CA.

The concept of an identity-based cryptosystem was proposed in A. Shamir, Identity - Based Cryptosystems and Signatures Schemes , A DVANCES IN C RYPTOGRAPHY —C RYPTO '84, Lecture Notes in Computer Science 196 (1984), Springer, 47-53. However, practical identity-based encryption schemes have not been found until recently. For instance, identity-based schemes were proposed in C. Cocks, An Identity - Based Encryption Scheme Based on Quadratic Residues , available at h-t-t-p://www.cesg.gov.uk/technology/id-pkc/media/ciren.pdf; D. Boneh, M. Franklin, Identity Based Encryption from the Well Pairing , A DVANCES IN C RYPTOLOGY —C RYPTO 2001, Lecture Notes in Computer Science 2139 (2001), Springer, 213-229; and D. Boneh, M. Franklin, Identity Based Encryption from the Well Pairing (extended version), available at h-t-t-p://www.cs.stanford.edu/˜dabo/papers/ibe.pdf. Cocks' scheme is based on the “Quadratic Residuosity Problem,” and although encryption and decryption are reasonably fast (about the speed of RSA), there is significant message expansion (i.e., the bit-length of the ciphertext is many times the bit-length of the plaintext). The Boneh-Franklin scheme bases its security on the “Bilinear Diffie-Hellman Problem,” and it is quite fast and efficient when using Weil or Tate pairings on supersingular elliptic curves or abelian varieties.

Existing identity-based cryptosystems, however, have had only limited acceptance. One major reason for this is that these systems involve key escrow. The CA knows all secrets in the cryptosystem because it generates the private keys of all users. As a result, existing identity-based cryptosystems have been vulnerable to passive attacks in which the CA, or any other party that discovers the master secret can determine shared secret of the two users.

There is a need for an efficient scheme allowing a recipient user of a cryptosystem to decrypt a secret message from a message sender only when a trusted third party certifies that the recipient holds a valid private key. Ideally, such a scheme should not require that the message sender query another party, including the third party, as to the status of the recipient's private key. Neither should such a scheme have the disadvantage of third party key escrow.

It therefore is an object of the present invention to provide an efficient protocol, not involving key status queries or key escrow, wherein a message recipient can decrypt a message from a message sender only if the recipient obtains authorization (e.g. up to date certification) from a third party. It is a further object of the present invention to provide such a protocol wherein the recipient's decryption ability is contingent upon authorization by several parties. Another object of the present invention is to provide such a protocol wherein the third party comprises a hierarchical authorization entity within the cryptosystem. It is yet another object of the present invention to provide an efficient method of providing a user with a private key having a short validity period. It is a further object of the invention to provide such a protocol that allows such communication in a system comprising a large number (e.g. millions) of users.

BRIEF SUMMARY OF THE PREFERRED EMBODIMENTS

The present invention provides methods for implementing a secure and practical certificate-based encryption scheme.

According to one aspect of the present invention, the method provides for encoding and decoding a digital message between a sender and a recipient in a public-key encryption scheme including the sender, the recipient and an authorizer. The method includes the steps of generating a recipient public key/recipient private key pair and a recipient encryption key. A key generation secret that is a secret of the authorizer is selected. A recipient decryption key is generated using at least the key generation secret and the recipient encryption key where a key formed from the recipient decryption key and a key formed from the recipient encryption key are a public key/private key pair.

The digital message is encrypted using at least the recipient public key and the recipient encryption key to create an encrypted digital message. The encrypted digital message is decrypted using at least the recipient private key and the recipient decryption key.

Another aspect of the present invention provides a method for sending a digital message between a sender and a recipient in a public-key encryption system including a plurality of authorizers, the plurality of authorizers including at least a root authorizer and a lower-level authorizer in a hierarchy between the root authorizer and the recipient. The method includes the steps of generating a recipient public key/private key pair and a recipient encryption key, where the recipient encryption key is generated using identity information of at least one of the recipient's ancestors.

A root key generation secret is selected and a root key generation parameter generated based on the root key generation secret. A recipient decryption key is then generated such that the recipient decryption key is related to the recipient encryption key, the root key generation secret and the associated root key generation parameter.

The digital message is encrypted using the recipient public key and a recipient encryption key to create an encrypted digital message, where a key formed from the recipient decryption key and a key formed from the recipient encryption key are a public key/private key pair. The encrypted digital message is decrypted using at least the recipient private key and the recipient decryption key.

Another aspect of the present invention provides a method of generating a decryption key for an entity in an encryption system including a plurality of authorizers, the plurality of authorizers including at least a root authorizer and lower-level authorizers in the hierarchy between the root authorizer and the entity. The method included the steps of generating a root key generation secret and a root key generation parameter based on the root key generation secret. A lower-level key generation secret for the lower-level authorizers is generated. A lower-level key generation parameter for lower-level authorizers is then generated using at least the lower-level key generation secret for its associated lower-level authorizer.

A decryption key generation schedule is established defining a validity period for a decryption key for the entity. The decryption key for the entity is generated such that the decryption key is related to at least the root key generation secret and one or more of the lower-level key generation secrets.

Another aspect of the present invention provides a method of sending a digital message between a sender and a recipient in a public-key encryption scheme including the sender, the recipient and a plurality of authorizers, where the recipient can decrypt the digital message only if it possesses authorization from the authorizers. The method includes the steps of generating a recipient public key/private key pair for the recipient and a secret key for each of the authorizers. A public key is generated for each of the authorizers using at least the secret key for its associated authorizer. A string of binary digits is signed with the secret key to generate a signature for each of the authorizers.

The digital message is encrypted to form a ciphertext using at least the recipient's public key, the public keys of the authorizers, and the strings of binary digits signed by the authorizers. The encrypted digital message is decrypted using at least the recipient's private key, and the signatures generated by the authorizers.

Another aspect of the present invention provides a method of sending a digital message between a sender and a recipient in a public key encryption scheme comprising the sender, the recipient and a plurality of authorizers including at least a root authorizer and lower-level authorizers in the hierarchy between the root authorizer and the recipient, where the recipient can decode the digital message only if it possesses authorization from the authorizers. The method includes the steps of generating a recipient public key/private key pair for the recipient and a secret key for the root authorizer and each of the lower level authorizers. A public key is generated for the root authorizer and each of the lower level authorizers using at least the secret key for the associated authorizer.

Documents, each containing the public key of each of the lower level authorizers, are certified to generate a signature, where the document containing the public key of each lower level authorizer is certified by the authorizer above it in the hierarchy. A document comprising the recipient public key and a parameter determining the validity of the recipient public key is certified by the authorizer immediately above the recipient in the hierarchy.

The digital message is encrypted to form a ciphertext using at least the recipient's public key, the public keys of the authorizers, and the documents. The encrypted digital message is decrypted using at least the recipient's private key and the signatures generated by the authorizers.

Another aspect of the present invention provides a method of encrypting and decrypting a digital message between a sender and a recipient in a public-key encryption scheme including the sender, the recipient and an authorizer. The method includes the steps of generating a recipient public key/recipient private key pair and selecting a key generation secret known to the authorizer. A recipient decryption key associated with time period i is generated, where this key is related to the key generation secret and where recipient decryption keys associated with time periods earlier than i, but not those associated with time periods later than i, can be generated from the recipient decryption key associated with time period i.

The digital message is encrypted to form a ciphertext using the recipient public key, the time period parameter associated with time period i or a time period parameter associated with an earlier time period, and a recipient encryption key to create an encoded digital message. The encrypted digital message is decrypted using at least the recipient private key and the recipient decryption key associated with time period i.

Another aspect of the present invention provides a method of sending a digital message between a sender and a recipient in a public-key encryption scheme including the sender, a plurality of clients including the recipient, and an authorizer, where the digital message is encrypted by the sender and decrypted by the recipient when the recipient is authorized to do so by the authorizer. The method includes the steps of generating a recipient public key/recipient private key pair and a unique binary string associating the recipient with a leaf node in a B-tree. A unique binary string associated with each ancestor node of the recipient leaf node and an encryption key for the recipient leaf node and for each of the ancestor nodes for the recipient leaf node are also generated, as is a master secret known to the authorizer. The encryption key for each node is associated with at least the binary string associated with that node.

A recipient decryption key associated with an ancestor node of the recipient leaf node is generated, where the ancestor node is not an ancestor of a leaf node associated with a client not authorized by the authorizer. The recipient decryption key is associated with at least the binary string associated with that node and the master secret. The recipient decryption key associated with an ancestor node of the recipient leaf node forms a private key/public key pair with the encryption key associated with the ancestor node of the recipient leaf node.

The sender encrypts the digital message to create an encrypted digital message using at least the recipient public key, and the encryption keys associated with the recipient leaf node and ancestor nodes of the recipient leaf node. The recipient decrypts the encrypted digital message using at least the recipient private key and the recipient decryption key associated with an ancestor node of the recipient leaf node.

BRIEF DESCRIPTION OF THE DRAWINGS

The subsequent description of the preferred embodiments of the present invention refers to the attached drawings, wherein:

FIG. 1 shows a flow diagram illustrating the steps performed by a message recipient according to one embodiment of the invention;

FIG. 2 shows a flow diagram illustrating the steps performed by an authorizer according to one embodiment of the invention;

FIG. 3 shows a flow diagram illustrating the steps performed by a message sender according to one embodiment of the invention;

FIG. 4 shows a flow diagram illustrating a Hierarchical Certificate-Based Encryption scheme according to another embodiment of the invention;

FIG. 5 shows a flow diagram illustrating another Hierarchical Certificate-Based Encryption scheme according to an embodiment of the invention;

FIG. 6 shows a block diagram illustrating a typical hierarchical structure in which the method of FIG. 5 may be performed;

FIG. 7 shows a flow diagram illustrating a method of encoding and decoding a digital message M communicated between a sender y and a recipient z according to another embodiment of the invention;

FIG. 8 shows a flow diagram illustrating a method of encoding and decoding a digital message M;

FIG. 9 shows a flow diagram illustrating a method of encoding and decoding a digital message M communicated between a sender y and a recipient z according to another embodiment of the invention.

FIG. 10 shows a diagram illustrating a High-Granularity Encryption Scheme.

FIG. 11 shows a flow diagram illustrating a broadcast encryption scheme using a binary tree.

FIG. 12 shows a block diagram illustrating broadcast encryption scheme using the cover concept.

DESCRIPTION OF THE EMBODIMENTS

The methods of the invention provide efficient protocols allowing a sender in a cryptosystem to communicate a secret message to a recipient only when a trusted third party (the “authorizer”) certifies that the recipient should receive the message.

In the protocols described below, the names “sender” and “recipient” represent two users of a cryptosystem. Such a cryptosystem may include many users other than the sender and recipient. Specifically, the sender represents a first user who wishes to communicate a secret message to a second user, represented by the recipient. The message may contain any type of digital information, including session keys used with symmetric cryptography algorithms to secure message traffic.

The term “Certification Authority (CA)” represents the entity responsible for managing the public-key infrastructure of the cryptosystem. The major functions of the CA may include the generation and distribution of digital certificates as well as public keys. The CA may be a single entity or may consist of a distributed or hierarchical structure of entities.

The term “authorizer” represents a third party trusted by a message sender using the cryptosystem to certify that a message recipient has authority to receive a message encrypted to a message recipient. The authorizer may be a single entity or may consist of a distributed or hierarchical structure of entities. In many systems, the authorizer and the CA will be the same entity. However, this will not always be so. The message recipient's ability to decrypt a message can be contingent on authorization from any specified entity or entities.

The term “certificate” represents an identifier used by individual users of the cryptosystem to identify and authenticate themselves to other users. A certificate has certain attributes that enable users to trust the information contained in the certificate. Typically, a certificate consists of a digital signature on a document containing information such as the identity of the certificate owner, the public key of the certificate owner, the identity of the CA, an issue date, an expiration date, a serial number, and a parameter allowing users to verify that the certificate is genuine and valid. To verify the certificate, the verifier must know the document signed. This information is often sent with the certificate

The term “public-key cryptosystem” represents a cryptosystem wherein a sender sends an encrypted message to a recipient. The sender encrypts the message using the recipient's public key. The recipient decrypts the encrypted message using the recipient's private key. Such a public key and private key form a “public key/private key pair”. It is computationally infeasible to determine the recipient's private key from knowledge of the recipient's public key. Examples of public-key cryptosystems are the RSA Cryptosystem, in which the security of the private key is related to the difficulty of factoring large integers, and the EIGamal Cryptosystem, in which the security of the private key is related to the discrete logarithm problem. The term “form a public key/private key pair” will be understood by those skilled in the art to include a situation where the definitions of the public and private keys are redefined but the overall ability of the keys to encrypt and decrypt messages in maintained.

The terms “tree” and “B-tree” represent data structures that maintain an ordered set of data. A B-tree consists of “nodes”, “leafs”, and pointers connecting the nodes and leafs together. A “root node” defines the base, or first level, of the B-tree. A pointer connects the root node to each of a second level of nodes. The second level nodes are the child nodes of the root node. The root node is the parent node of the second level nodes. Further pointers may connect each of the second level nodes to their own child nodes and so on. “Leaf” nodes are the highest level of nodes of the B-tree. The leaf nodes are the child nodes of the next to highest level nodes and have no children of their own. Those nodes connecting a node to the root node, including the root node itself, are termed the ancestor nodes of this node.

The term “binary tree” represents a B-tree in which every node, except the leaf nodes, has at most two children.

The term “2-3 tree” represents a B-tree in every interior node has two or three children.

The term “Merkle tree” represents a B-tree whose nodes store values, some of which computed by means of a one-way function H, for example, a one-way hash function, in a specified manner. A leaf node can store any value, but each internal node should store a value that is the one-way function of the concatenation of the values in its children. For example, if an internal node has a two children, one storing the value U and the other storing a value V, then this node stores the value H(UV)).

Certificate-Based Encryption

The present invention describes “certificate-based encryption (CBE)” schemes where the ability of a message recipient user of a cryptosystem to decrypt a secret message from a message sender is contingent on the authorization of one or more trusted authorizers. The message recipient needs at least two keys to decrypt a message. One of these keys is a signature by one or more authorizers on one or more documents. The CBE protocols of the invention include a public-key encryption scheme and an adapted Identity-Based Encryption (IBE) scheme. Such protocols allow for CBE schemes including large numbers of users (e.g. millions of users) without destroying the algebraic structure necessary for CBE. In the protocols described below, a sender communicates an encrypted message to a recipient.

In the public-key encryption scheme, an entity, e.g. the recipient, generates a public key/private key pair (PK B , SK B ) for the recipient. The recipient's public key is available to other users of the cryptosystem, including the sender. The other users can use this key to encrypt messages sent to the recipient. The recipient keeps the recipient private key secret and uses this key to decrypt messages encrypted with the recipient's public key.

A CBE protocol may incorporate any IBE scheme. An IBE scheme uses a trusted third party called a Private Key Generator (PKG). To set up, the PKG generates a master secret s, and publishes certain system parameters params that include a public key that masks s. The PKG may have many clients. Each client has some ID, which is simply a string that identifies it—e.g., the client's email address. The main algorithms in an IBE scheme are Private Key Generation, Encryption, and Decryption.

In the Private Key Generation algorithm, the PKG uses s, params and ID to compute a private key d ID corresponding to a given ID string. The message sender then uses the Encryption algorithm to compute the ciphertext C for the message M, using params, ID, and M. The message recipient used params, d ID , and C to recover M.

In an IBE scheme adapted to implement a CBE scheme, the authorizer generates a recipient “decryption key” using a key generation secret that is a secret of the authorizer. The decryption key forms a public key/private pair with a recipient “encryption” key. In one embodiment, the recipient decryption key is a signature on the recipient encryption key generated using the key generation secret. The message sender encrypts a digital message using the recipient public key and the recipient encryption key to create an encrypted digital message. The recipient decrypts the encrypted digital message using the recipient private key and the recipient decryption key. Since the sender encrypts the message using both the recipient public key and the recipient encryption key, the recipient needs both the recipient private key and recipient decryption key to decrypt the encrypted message. Because both keys are required, the recipient decryption key need not be kept secret. For example, since the recipient decryption key is in fact a signature by one or more authorizers, the decryption can be treated as a signature; it can be used as verifiable proof that the recipient has received appropriate authorization.

In general, the encryption key can correspond to a document D and the decryption key to the signature s D , the authorizer's signature on the document D using s, the authorizer's key-generation secret. If the decryption key, and hence the encryption key, are updated using a schedule known to the message sender, the sender can encrypt a message that the recipient can decrypt only when the recipient receives a decryption key corresponding to the encryption key used to encrypt the message.

The above scheme reduces the infrastructure overhead on the cryptosystem by avoiding the need for the sender to query to ensure that the recipient's private key is not compromised. The sender merely must know encryption key and the schedule on which the authorizer issues a new decryption key to the recipient. Without an up-to-date decryption key, an attacker knowing the recipient's private key cannot decrypt messages intended for the recipient. Thus, the CBE scheme allows the recipient's authorization to decrypt messages to be revoked if, for example, the recipient's private key is compromised. In such a situation, the authorizer stops issuing decryption keys to the recipient.

The scheme offers the additional advantage that it does not require the transmission of decryption keys to the recipient over a secure channel. Because decryption is not possible without the recipient's private key and the decryption key, the recipient need not keep the decryption key secret.

Because the authorizer knows the decryption key, it can decrypt messages encrypted by the encryption key. However, the sender avoids key escrow by doubly encrypting messages to the recipient using both the recipient's public key and encryption key. The authorizer cannot decrypt the message because it does not know the recipient's private key.

Although the encryption key can correspond to any document D, in many situations this document comprises parameters such as the recipient's identifying information (PK IDB ), including the recipient's public key (PK B ), and a parameter depending on the schedule by which the authorizer issues new decryption keys.

In a CBE scheme, the recipient's encryption key, the recipient's public key, and a parameter describing the schedule by which the authorizer issues new decryption keys are distributed to users of the cryptosystem, including the sender. The recipient can perform this function. Alternatively, a trusted third party, for example the CA or the authorizer, may perform the distribution.

Validity Period and Revocation

If the sender encrypts a message to the recipient using an encryption key that is valid for the current year, the recipient may use the corresponding decryption key for decryption during the current year. After this period, the recipient must obtain a new key from the authorizer. Likewise, if the sender encrypts a message using an encryption key that is valid for the current day, the recipient must obtain a new decryption key every day. Using this approach, a system may be created in which key revocation is automatic after any particular desired time-period. Similarly, the structure of the encryption may be such that the recipient can decrypt a message from a sender only at a pre-determined future time.

Other parameters, such as the recipient's security level, may also be included in the encryption key. If the sender encrypts a message using both a time parameter and a security level parameter, the recipient can decrypt the message only if the recipient has an up-to-date decryption key that specifies the required security level parameter. If the recipient's security level changes, the recipient will not be able to decrypt the sender's message.

A Pairing-Based CBE Scheme

A CBE scheme may incorporate any IBE scheme. Examples of such schemes are those based on Weil or Tate pairings associated with elliptic curves or abelian varieties. One embodiment of a CBE scheme of the present invention is described below. This embodiment uses the Boneh-Franklin IBE scheme and an identity-based encryption key comprising parameters such as the recipient's identifying information (PK IDB ), including the recipient's public key (PK B ), and a parameter depending on the schedule by which the authorizer issues new decryption keys. This embodiment is efficient and is provably secure (in the random oracle model) against adaptive chosen ciphertext attack.

Referring to the accompanying drawings, FIG. 1 shows a flow diagram illustrating the steps taken by a message recipient during a setup phase. This setup phase occurs before the recipient decrypts an encrypted message. In block 101 , the recipient generates a public key/private key pair using a public-key cryptography protocol. In block 102 , the recipient generates identifying information. In block 103 , the recipient communicates identifying information, including the recipient's public key, to other users, including the message sender, and the authorizer.

FIG. 2 shows a flow diagram illustrating the steps taken by the authorizer during parameter setup and recipient certification. As used in the CBE scheme, the Boneh-Franklin IBE scheme generally includes four randomized algorithms: setup, certification, encryption, and decryption. Here, the authorizer is the equivalent of the Private Key Generator (PKG) in the conventional IBE scheme.

During setup, the authorizer uses a BDH parameter generator and a security parameter k to generate groups

1 and

2 of some prime order q and an admissible pairing ê:

1 ×

1 →

2 . The pairing is defined as being admissible if it is bilinear: ê(aQ, bR)=ê(Q, R) ab for all Q, R∈

1 and all a, b∈

; non-degenerate: the mapping does not send all pairs in

1 ×

1 to the identity in

2 ; and computable: there is an efficient algorithm to compute ê(Q, R) for any Q, R∈

1 .

The Boneh-Franklin IBE scheme based on pairings, such as, for instance, the Weil or Tate pairings associated with elliptic curves or abelian varieties. The methods base their security on the Bilinear Diffie-Hellman problem. Here, the first group

1 preferably is a group of points on an elliptic curve or abelian variety, and the group law on

1 may be written additively. The second group

2 preferably is a multiplicative subgroup of a finite field, and the group law on

2 may be written multiplicatively. However, other types of groups may be used as

1 and

2 consistent with the present invention.

The Bilinear Diffie-Hellman problem is that of finding ê(P, P) abc if P, aP, bP, and cP are known, but a, b, and c are not known. Solving the Diffie-Hellman problem in

1 solves the Bilinear Diffie-Hellman problem because ê(P, P) abc =ê(abP, cP). Similarly, solving the Diffie-Hellman problem in

2 solves the Bilinear Diffie-Hellman problem because, if g=ê(P, P), then g abc =(g ab ) c where g ab =ê(aP, bP) and g c =ê(P, cP). For instance, suppose E is a supersingular elliptic curve or abelian variety over a finite field F; suppose P∈E(F) is a point of order l (relatively prime to the characteristic of F); and suppose ê is the Weil pairing on the l-torsion on E. Let

1 be the group generated by P, and let

2 be the group of l-th roots of unity in the algebraic closure of F. If f is an automorphism of E such that f(P)∉

1 , then defining ê:

1 ×

1 →

2 by ê(Q, R)=e(Q, f(R)) gives a function ê that satisfies the two conditions set forth above. Further, this ê is non-degenerate. For instance, if ê(aP, bP)=ê(P, cP), then abP=cP.

In blocks 201 and 202 of FIG. 2 , the authorizer selects a key generation secret and establishes system parameters by choosing an arbitrary generator P∈

1 , picking a random s c ∈

/q

<img id="CUSTOM-CHARACTER-00028" he="3.13mm" wi="2.46mm" file="US08074073-20111206-P00004.TIF" alt="Figure US08074073-20111206-P00004" img-content="character" img-format="tif" orientation="portrait" inline

CLAIMS

Claims ( 99 )

1. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message is encrypted by the sender and decrypted by the recipient, the method comprising encrypting, by at least one machine in a set of one or more machines, the digital message M using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption with a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated by the authorizer using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein the recipient encryption key RENC and the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

2. A system configured to perform the method of claim 1 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

3. The method of claim 1 , wherein the recipient decryption key RDEC is generated by the authorizer according to a schedule known to the sender.

4. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 3 .

5. A system configured to perform the method of claim 3 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

6. The method of claim 3 , wherein the recipient encryption key RENC is generated using at least information comprising the schedule.

7. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 6 .

8. A system configured to perform the method of claim 6 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

9. The method of claim 1 , wherein the recipient private key RPRIV and the recipient public key RPUB are generated using at least one system parameter issued by the authorizer.

10. The method of claim 1 , wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s c P B , wherein:

s c is the key generation secret of the authorizer; and

P B is the recipient encryption key RENC and is equal to H 1 (Inf B ), wherein Inf B is an element of a first cyclic group

1 of elements, wherein P B is an element of a second cyclic group

2 of elements, and H 1 is a predefined function (“first function H 1 ”), wherein the first and second cyclic groups

1 and

2 and the function H 1 are system parameters made available to the sender, and also available to the sender are system parameters comprising:

a generator P of the first cyclic group

1 ;

a key generation parameter Q=S C P;

a second function H 2 capable of generating a second string of binary digits from an element of the second cyclic group

2 .

11. The method of claim 10 , wherein both the first group

1 and the second group

2 are of the same prime order q.

12. The method of claim 11 wherein:

s C is an element of the cyclic group

/q

.

13. The method of claim 10 wherein the first cyclic group

1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group

2 is a multiplicative subgroup of a finite field.

14. The method of claim 10 wherein the system parameters available to the sender further comprise a function ê which is a bilinear, non-degenerate, and efficiently computable pairing which maps

1 ×

1 into

2 .

15. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 10 .

16. A system configured to perform the method of claim 10 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

17. The method of claim 10 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

18. The method of claim 1 , wherein the recipient encryption key RENC is generated from a document and the recipient decryption key RDEC is the authorizer&#39;s signature on the document.

19. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 18 .

20. A system configured to perform the method of claim 18 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

21. The method of claim 1 wherein the method further comprises the recipient performing, by at least one machine in the set of the one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV;

decrypting the encrypted digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

22. The method of claim 1 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating the recipient decryption key RDEC and sending the recipient decryption key to the recipient.

23. The method of claim 22 wherein the method further comprises the recipient performing, by at least one machine in the set of the one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV;

decrypting the encrypted digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

24. A system configured to perform the method of claim 23 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

25. The method of claim 1 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC by the authorizer and/or the recipient and/or the sender.

26. A non-transitory computer-readable medium comprising a computer-readable computer program operable to cause a computer to perform the method of claim 1 .

27. The method of claim 1 wherein the recipient private key RPRIV is generated by the recipient and is unknown to the authorizer.

28. A method for operating a public-key encryption scheme which provides for sending a digital message between a sender and a recipient with participation of a plurality of authorizers, the plurality of authorizers including a root authorizer and n lower-level authorizers in a hierarchy between the root authorizer and the recipient, wherein n≧1, the method comprising encrypting, by at least one machine in a set of one or more machines, the digital message using a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption with a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient encryption key RENC and the recipient decryption key RDEC are a public key/private key pair 1;

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 2, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient encryption key RENC is generated using identity information of at least one of the recipient&#39;s ancestors;

the recipient decryption key RDEC is generated by one of the authorizers such that the recipient decryption key RDEC is related to the recipient encryption key RENC, a root key generation secret and an associated root key generation parameter, wherein the root key generation parameter is generated based on the root key generation secret, and the root key generation secret is a secret of the root authorizer;

wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

29. The method of claim 28 , wherein the recipient decryption key RDEC is generated according to a schedule known to the sender.

30. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 29 .

31. A system configured to perform the method of claim 29 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

a plurality of computer systems each comprising one or more processors and memory, acting as said authorizers.

32. The method of claim 28 , wherein the recipient private key RPRIV and the recipient public key RPUB are generated using system parameters issued by one or more of the authorizers.

33. The method of claim 28 , wherein the recipient decryption key RDEC is related to the root key generation secret and the associated root key generation parameter.

34. The method of claim 33 wherein the method further comprises generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC by one of the authorizers.

35. The method of claim 28 , wherein the plurality of authorizers further includes at least in lower-level authorizers in the hierarchy between the root authorizer and the sender, wherein in m≧1, and wherein l of the m authorizers in the hierarchy are common ancestors to both the sender and the recipient, wherein authorizer l is the lowest common ancestor authorizer between the sender and the recipient, and wherein l≧1, and wherein:

a lower-level key generation secret is selected for each of the m lower-level authorizers in the hierarchy between the root authorizer and the sender; and

a sender decryption key SDEC is generated such that the sender decryption key SDEC is related to at least the root key generation secret and one or more of the m lower-level key generation secrets associated with the in lower-level authorizers in the hierarchy between the root authorizer and the sender;

wherein the message is encrypted using at least the sender decryption key SDEC and one or more of the lower-level key generation parameters associated with the (m−l+1) authorizers between the root authorizer and the sender that are at or below the level of the lowest common ancestor authorizer l , but not using any of the lower-level key generation parameters that are associated with the (l−1) authorizers above the lowest common ancestor authorizer l ; and

wherein the encrypted digital message is decryptable using at least the recipient decryption key RDEC and one or more of the lower-level key generation parameters associated with the (n−l+1) authorizers between the root authorizer and the sender that are at or below the level of the lowest common ancestor authorizer l , but not using any of the lower-level key generation parameters that are associated with the (l−1) authorizers that above the lowest common ancestor authorizer l .

36. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 35 .

37. A system configured to perform the method of claim 35 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

a plurality of computer systems each comprising one or more processors and memory, acting as said authorizers.

38. The method of claim 28 wherein the method further comprises the root authorizer performing, by at least one machine in the set of the one or more machines, operations of:

selecting the root key generation secret that is a secret of the root authorizer; and

generating the root key generation parameter based on the root key generation secret.

39. The method of claim 28 wherein the method further comprises generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC by one of the authorizers.

40. The method of claim 38 wherein further comprising the recipient performing, by at least one machine in the set of the one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV; and

decrypting the encrypted digital message to recover the digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

41. The method of claim 28 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

42. A non-transitory computer-readable medium comprising a computer-readable computer program operable to cause a computer to perform the method of claim 28 .

43. A method for operating a public-key encryption scheme which provides for sending a digital message between a sender and a recipient with participation of a plurality of authorizers, the plurality of authorizers including a root authorizer and n lower-level authorizers in a hierarchy between the root authorizer and the recipient, wherein n≧1, the method comprising encrypting, by at least one machine in a set of one or more machines, the digital message using a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption with a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient encryption key RENC and the recipient decryption key RDEC are a public key/private key pair 1;

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 2, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient encryption key RENC is generated using identity information of at least one of the recipient&#39;s ancestors;

the recipient decryption key RDEC is generated such that the recipient decryption key RDEC is related to the recipient encryption key RENC, a root key generation secret and an associated root key generation parameter, wherein the root key generation parameter is generated based on the root key generation secret, and the root key generation secret is a secret of the root authorizer;

wherein the method further comprises the recipient performing, by at least one machine in the set of the one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV; and

decrypting the encrypted digital message to recover the digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC;

wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

44. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message M is encrypted by the sender using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message and is decrypted by the recipient, the method comprising decrypting, by at least one machine in a set of one or more machines, the encrypted digital message using at least a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated by the authorizer using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein the recipient encryption key RENC and the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

45. The method of claim 44 , wherein the recipient decryption key RDEC is generated by the authorizer according to a schedule known to the sender.

46. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 45 .

47. A system configured to perform the method of claim 45 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

a plurality of computer systems each comprising one or more processors and memory, acting as said authorizers.

48. The method of claim 45 , wherein the recipient encryption key RENC is generated using at least information comprising the schedule.

49. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 48 .

50. A system configured to perform the method of claim 48 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

a plurality of computer systems each comprising one or more processors and memory, acting as said authorizers.

51. The method of claim 44 , wherein the recipient private key RPRIV and the recipient public key RPUB are generated using at least one system parameter issued by the authorizer.

52. The method of claim 44 , wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s c P B , wherein:

s c is the key generation secret of the authorizer; and

P B is the recipient encryption key RENC and is equal to H 1 (Inf B ), wherein Inf B is an element of a first cyclic group

1 of elements, wherein P B is an element of a second cyclic group

2 of elements, and H 1 is a predefined function (“first function H 1 ”), wherein the first and second cyclic groups

1 and

2 and the function H 1 are system parameters made available to the sender, and also available to the sender are system parameters comprising:

a generator P of the first cyclic group

1 ;

a key generation parameter Q=s C P;

a second function H 2 capable of generating a second string of binary digits from an element of the second cyclic group

2 .

53. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 52 .

54. A system configured to perform the method of claim 52 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

a plurality of computer systems each comprising one or more processors and memory, acting as said authorizers.

55. The method of claim 52 , wherein both the first group

1 and the second group

2 are of the same prime order q.

56. The method of claim 52 wherein the first cyclic group

1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group

2 is a multiplicative subgroup of a finite field.

57. The method of claim 56 wherein:

s C is an element of the cyclic group

/q

.

58. The method of claim 52 wherein the system parameters available to the sender further comprise a function ê which is a bilinear, non-degenerate, and efficiently computable pairing which maps

1 ×

1 into

2 .

59. The method of claim 44 , wherein the recipient encryption key RENC is generated from a document and the recipient decryption key RDEC is the authorizer&#39;s signature on the document.

60. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 59 .

61. A system configured to perform the method of claim 59 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

a plurality of computer systems each comprising one or more processors and memory, acting as said authorizers.

62. The method of claim 44 further comprising the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

63. A non-transitory computer-readable medium comprising a computer-readable computer program operable to cause a computer to perform the method of claim 44 .

64. The method of claim 44 wherein the recipient private key RPRIV is generated by the recipient and is unknown to the authorizer.

65. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message is encrypted by the sender using at least a recipient public key RPUB and a recipient encryption key RENC, wherein the recipient public key RPUB and a recipient private key RPRIV form a recipient public key/recipient private key pair, wherein the recipient private key RPRIV is a secret of the recipient, and the digital message is decrypted by the recipient using at least the recipient private key RPRIV and a recipient decryption key RDEC, the method comprising the authorizer performing, by at least one machine in a set of one or more machines, operations of:

selecting a key generation secret that is a secret of the authorizer;

generating the recipient decryption key RDEC using at least the key generation secret of the authorizer and the recipient encryption key RENC, wherein the recipient encryption key RENC and the recipient decryption key RDEC are a public key/private key pair;

sending the recipient decryption key RDEC to the recipient;

wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

66. The method of claim 65 , wherein the recipient decryption key RDEC is generated by the authorizer according to a schedule known to the sender.

67. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 66 .

68. A system configured to perform the method of claim 66 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

69. The method of claim 66 , wherein the recipient encryption key RENC is generated using at least information comprising the schedule.

70. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 69 .

71. A system configured to perform the method of claim 69 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

72. The method of claim 65 , wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s c P B , wherein:

s c is the key generation secret of the authorizer; and

P B is the recipient encryption key RENC and is equal to H 1 (Inf B ), wherein Inf B is an element of a first cyclic group

1 of elements, wherein P B is an element of a second cyclic group

2 of elements, and H 1 is a predefined function (“first function H 1 ”), wherein the first and second cyclic groups

1 and

2 and the function H 1 are system parameters made available to the sender, and also available to the sender are system parameters comprising:

a generator P of the first cyclic group

1 ;

a key generation parameter Q=s C P;

a second function H 2 capable of generating a second string of binary digits from an element of the second cyclic group

2 .

73. The method of claim 72 , wherein both the first group

1 and the second group

2 are of the same prime order q.

74. The method of claim 73 wherein:

s c is an element of the cyclic group

/q

.

75. The method of claim 72 wherein the first cyclic group

1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group

2 is a multiplicative subgroup of a finite field.

76. The method of claim 72 wherein the system parameters available to the sender further comprise a function ê which is a bilinear, non-degenerate, and efficiently computable pairing which maps

1 ×

1 into

2 .

77. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 72 .

78. A system configured to perform the method of claim 72 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

79. The method of claim 65 , wherein the recipient encryption key RENC is generated from a document and the recipient decryption key RDEC is the authorizer&#39;s signature on the document.

80. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 79 .

81. A system configured to perform the method of claim 79 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

at least one computer system comprising one or more processors and memory, acting as said recipient.

82. A non-transitory computer-readable medium comprising a computer-readable computer program operable to cause a computer to perform the method of claim 65 .

83. The method of claim 65 wherein the recipient private key RPRIV is unknown to the authorizer.

84. A method for operating a public-key encryption scheme which provides for sending a digital message between a sender and a recipient with participation of a plurality of authorizers, the plurality of authorizers including a root authorizer and n lower-level authorizers in a hierarchy between the root authorizer and the recipient, wherein n≧1, wherein the digital message is encrypted by the sender using a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption by the recipient using a recipient private key RPRIV and a recipient decryption key RDEC,

the method comprising performing, by at least one machine in a set of one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV which are a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

obtaining an encrypted digital message formed by encryption of the digital message with the recipient public key RPUB and the recipient encryption key RENC, wherein the recipient encryption key RENC and the recipient decryption key RDEC are a public key/ private key pair 2; and

decrypting the encrypted digital message to recover the digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC;

wherein the recipient encryption key RENC is generated using identity information of at least one of the recipient&#39;s ancestors;

wherein the recipient decryption key RDEC is generated by one of the authorizers such that the recipient decryption key RDEC is related to the recipient encryption key RENC, a root key generation secret and an associated root key generation parameter, wherein the root key generation parameter is generated based on the root key generation secret, and the root key generation secret is a secret of the root authorizer;

wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

85. The method of claim 84 , wherein the recipient decryption key RDEC is generated according to a schedule known to the sender.

86. non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 85 . RDEC.

87. A system configured to perform the method of claim 85 , the system comprising:

at least one computer system comprising one or more processors and memory, for acting as said authorizer;

at least one computer system comprising one or more processors and memory, for acting as said sender; and

a plurality of computer systems each comprising one or more processors and memory, acting as said authorizers.

88. The method of claim 84 , wherein the recipient private key RPRIV and the recipient public key RPUB are generated using system parameters issued by one or more of the authorizers.

89. The method of claim 84 , wherein the recipient decryption key RDEC is related to the root key generation secret and the associated root key generation parameter.

90. The method of claim 84 , wherein the plurality of authorizers further includes at least m lower-level authorizers in the hierarchy between the root authorizer and the sender, wherein m≧1, and wherein l of the in authorizers in the hierarchy are common ancestors to both the sender and the recipient, wherein authorizer l is the lowest common ancestor authorizer between the sender and the recipient, and wherein l≧1, and wherein:

a lower-level key generation secret is selected for each of the m lower-level authorizers in the hierarchy between the root authorizer and the sender; and

a sender decryption key SDEC is generated such that the sender decryption key SDEC is related to at least the root key generation secret and one or more of the m lower-level key generation secrets associated with the m lower-level authorizers in the hierarchy between the root authorizer and the sender;

wherein the message is encrypted using at least the sender decryption key SDEC and one or more of the lower-level key generation parameters associated with the (m−l+1) authorizers between the root authorizer and the sender that are at or below the level of the lowest common ancestor authorizer l , but not using any of the lower-level key generation parameters that are associated with the (l−1) authorizers above the lowest common ancestor authorizer l ; and

wherein the encrypted digital message is decryptable using at least the recipient decryption key RDEC and one or more of the lower-level key generation parameters associated with the (n−l+1) authorizers between the root authorizer and the sender that are at or below the level of the lowest common ancestor authorizer l , but not using any of the lower-level key generation parameters that are associated with the (l−1) authorizers that above the lowest common ancestor authorizer l .

91. A non-transitory computer-readable medium comprising a computer-readable program operable to cause a computer to perform the method of claim 90 .

92. The method of claim 84 further comprising generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC by one of the authorizers.

93. A non-transitory computer-readable medium comprising a computer-readable computer program operable to cause a computer to perform the method of claim 84 .

94. A method for operating a public-key encryption scheme which provides for sending a digital message between a sender and a recipient with participation of a plurality of authorizers, the plurality of authorizers including a root authorizer and n lower-level authorizers in a hierarchy between the root authorizer and the recipient, wherein n≧1, wherein the digital message is encrypted by the sender using a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption by the recipient using a recipient private key RPRIV and a recipient decryption key RDEC,

the method comprising one of the authorizers generating, by at least one machine in a set of one or more machines, the recipient decryption key RDEC such that the recipient decryption key RDEC is related to the recipient encryption key RENC, a root key generation secret and an associated root key generation parameter, wherein the root key generation parameter is generated based on the root key generation secret, and the root key generation secret is a secret of the root authorizer;

wherein the recipient encryption key RENC is generated using identity information of at least one of the recipient&#39;s ancestors;

wherein the recipient encryption key RENC and the recipient decryption key RDEC are a public key/private key pair 1;

wherein the recipient public key RPUB and the recipient private key RPRIV are a public key/private key pair 2, wherein the recipient private key RPRIV is a secret of the recipient;

wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

95. The method of claim 94 , wherein the recipient decryption key RDEC is generated according to a schedule known to the sender.

96. The method of claim 94 , wherein the recipient private key RPRIV and the recipient public key RPUB are generated using system parameters issued by one or more of the authorizers.

97. The method of claim 94 , wherein the recipient decryption key RDEC is related to the root key generation secret and the associated root key generation parameter.

98. The method of claim 94 , wherein the plurality of authorizers further includes at least m lower-level authorizers in the hierarchy between the root authorizer and the sender, wherein m≧1, and wherein l of the m authorizers in the hierarchy are common ancestors to both the sender and the recipient, wherein authorizer l is the lowest common ancestor authorizer between the sender and the recipient, and wherein l≧1, and wherein:

a lower-level key generation secret is selected for each of the m lower-level authorizers in the hierarchy between the root authorizer and the sender; and

a sender decryption key SDEC is generated such that the sender decryption key SDEC is related to at least the root key generation secret and one or more of the m lower-level key generation secrets associated with the m lower-level authorizers in the hierarchy between the root authorizer and the sender;

wherein the message is encrypted using at least the sender decryption key SDEC and one or more of the lower-level key generation parameters associated with the (m−l+1) authorizers between the root authorizer and the sender that are at or below the level of the lowest common ancestor authorizer l , but not using any of the lower-level key generation parameters that are associated with the (l−1) authorizers above the lowest common ancestor authorize l , and

wherein the encrypted digital message is decryptable using at least the recipient decryption key RDEC and one or more of the lower-level key generation parameters associated with the (n−l+1) authorizers between the root authorizer and the sender that are at or below the level of the lowest common ancestor authorizer l , but not using any of the lower-level key generation parameters that are associated with the (l−1) authorizers that above the lowest common ancestor authorizer l .

99. A non-transitory computer-readable medium comprising a computer-readable computer program operable to cause a computer to perform the method of claim 94 .

US12/552,720

2002-08-28

2009-09-02

Certificate-based encryption and public key infrastructure

Expired - Fee Related

US8074073B2

( en )

Priority Applications (1)

Application Number

Priority Date

Filing Date

Title

US12/552,720

US8074073B2

( en )

2002-08-28

2009-09-02

Certificate-based encryption and public key infrastructure

Applications Claiming Priority (5)

Application Number

Priority Date

Filing Date

Title

US40672102P

2002-08-28

2002-08-28

US41222102P

2002-09-20

2002-09-20

US10/521,741

US7657748B2

( en )

2002-08-28

2003-08-28

Certificate-based encryption and public key infrastructure

PCT/US2003/026834

WO2004021638A1

( en )

2002-08-28

2003-08-28

Certificate-based encryption and public key infrastructure

US12/552,720

US8074073B2

( en )

2002-08-28

2009-09-02

Certificate-based encryption and public key infrastructure

Related Parent Applications (3)

Application Number

Title

Priority Date

Filing Date

US10521741

Continuation

2003-08-28

US10/521,741

Continuation

US7657748B2

( en )

2002-08-28

2003-08-28

Certificate-based encryption and public key infrastructure

PCT/US2003/026834

Continuation

WO2004021638A1

( en )

2002-08-28

2003-08-28

Certificate-based encryption and public key infrastructure

Publications (2)

Publication Number

Publication Date

US20100082986A1

US20100082986A1 ( en )

2010-04-01

US8074073B2

true

US8074073B2 ( en )

2011-12-06

Family

ID=31981427

Family Applications (4)

Application Number

Title

Priority Date

Filing Date

US10/521,741

Expired - Fee Related

US7657748B2

( en )

2002-08-28

2003-08-28

Certificate-based encryption and public key infrastructure

US12/245,472

Expired - Fee Related

US7751558B2

( en )

2002-08-28

2008-10-03

Certificate-based encryption and public key infrastructure

US12/245,475

Expired - Fee Related

US7796751B2

( en )

2002-08-28

2008-10-03

Certificate-based encryption and public key infrastructure

US12/552,720

Expired - Fee Related

US8074073B2

( en )

2002-08-28

2009-09-02

Certificate-based encryption and public key infrastructure

Family Applications Before (3)

Application Number

Title

Priority Date

Filing Date

US10/521,741

Expired - Fee Related

US7657748B2

( en )

2002-08-28

2003-08-28

Certificate-based encryption and public key infrastructure

US12/245,472

Expired - Fee Related

US7751558B2

( en )

2002-08-28

2008-10-03

Certificate-based encryption and public key infrastructure

US12/245,475

Expired - Fee Related

US7796751B2

( en )

2002-08-28

2008-10-03

Certificate-based encryption and public key infrastructure

Country Status (6)

Country

Link

US

( 4 )

US7657748B2

( en )

EP

( 1 )

EP1540875A4

( en )

Related documents

• Virtual reality system using multiple force arrays for a solver — DeepMotion, Inc. (US10657696B2)#653961
• Augmented reality system with spatialized audio tied to user manipulated … — Magic Leap, Inc. (US11231770B2)#653963
• High-efficiency fuel cell system with carbon dioxide capture assembly and … — Fuelcell Energy, Inc. (US10170782B2)#653965
• Integrated electrochemical cell power generation and electrolysis systems — Czero, Inc. (US20250087711A1)#653966
• Generating augmented reality experiences utilizing physical objects to … — Meta Platforms Technologies, Llc (US20260037214A1)#653960