Secret-key certificates - Patent Review 5606617

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to cryptographic techniques, and more particularly to methods and apparatus for implementing certificate schemes based on public-key cryptography.

2. Description of the Prior Art

Public-key certificates, usually plainly referred to as certificates, are an essential cryptographic tool for secure key management. The idea is to have a specially appointed party, commonly called the Certification Authority, certify the public keys of other parties in the system by digitally signing these public keys with its own secret key. By widely distributing the public key of the Certification Authority through a variety of media, one can be assured that it is genuine. Because a public-key certificate is a digital signature of the Certification Authority on a public key, certificates on public keys of other parties can be verified by anyone by using the public key of the Certification Authority. The net effect is that impersonation attacks, and similar other attacks, are prevented.

In practical applications, the certificate of the Certification Authority may, and perhaps should, certify additional information. Along with the public key, a certificate could validate such information as the name of the party associated with the public key, employer, telephone number, electronic mail address, and a list of access rights.

To facilitate practicality of the certificate issuing process, public keys can be recursively certified according to a hierarchical structure. For example, in an electronic cash system, the main bank can certify the public keys of all the local banks, the local banks in turn can certify public keys in POS terminals by using their certified keys, and the secret keys corresponding to the public keys in the POS terminals can be used to decrypt information that is sent by the host. The hierarchic certification process can be thought of as building a tree, each node containing a public key and a certificate on the public key. A certificate on a public key in a node is a digital signature on that public key, that has been computed by the party associated with the parent node by applying the secret key that corresponds to the public key of the parent node. Anyone can verify the validity of a public key be recursively descending (or ascending) the tree from the root node to the node associated with the public key that is being verified (or vice versa). A certification hierarchy that is often suggested is one that is implied by the life-time of the cryptographic keys: keys that are more susceptible to attacks are changed more frequently, and are certified by keys that have a longer life-time.

Public keys can be listed in so-called public-key directories, which can be made available on CD-ROM or other media. In order to encrypt a message intended for another party, one needs to merely look up the public key of that other party in the public-key directory, verify the validity of the certificate, and encrypt the message with the public key. It can then be sent to the other party. No interaction is needed between the two parties. In this way for instance encrypted electronic mail can be sent over a computer network.

Because the certificate mechanism obviates the need for the public-key directory to be secured, public keys need not necessarily be listed in a public-key directory. They may be sent (along with the certificate) on request, by the party associated with the public key itself, or by any other party that need not be trusted, such as a server in a computer network.

In cryptographic mechanisms for transfer of credentials, the Certification Authority at issuing time can issue a certificate on a public key of a user; the type of credential that is issued can, for instance, be denoted by the type of signature that the Certification Authority computes. This allows the user, when transferring the credential to a recipient, to make a digital signature on a message of the recipient (describing such information as the identity of the recipient and transaction details), by using the secret key corresponding to his certified public key. The certificate proves the validity of the credential to the recipient, whereas the signature made by the user proves that the user willingly transferred the credential to the recipient.

For privacy-protected transfer of credentials, the information that is issued by the Certification Authority should not be linkable to executions of the issuing protocol. Special techniques are known that enable the user to blind the issuing protocol while interacting with the Certificate Authority.

While important and useful, the public-key certificate technique also has a few problems associated with it. First of these relates to privacy. It is conceivable that providers for a variety of electronic systems available in the new future will require participants to meet certain criteria before certifying their public keys. These criteria may include social status, income, type of job, trustworthiness, and so on. Because a public-key certificate is a digital signature of the Certification Authority on the public key, pairs consisting of a public key and a corresponding public-key certificate reveal to anyone which parties are participating in a certain system, and which parties are not participating. This reveals which parties meet the criteria specified by the Certification Authority, and which parties may not meet them. Likewise, the genuineness of the additional information (employer, telephone number, access rights, and so on) that may have been certified along with the public key, is revealed. Consequently, public-key certificates allow anyone to extract profiles of other parties, by scanning for their appearances, or the lack thereof, in compiled lists of certified public keys (such as public-key directories). This problem is by no means removed by letting participants send their public keys only on request, instead of using a public-key directory.

A second problem is that the publication of a public-key directory reveals a huge amount of digital signatures of the Certification Authority on known, or chosen, public keys. Although most of the known digital signature schemes are believed to be secure under known, or (adaptively) chosen, message attacks, only a few signature schemes are known that can be proven to be secure, assuming the existence of functions that are substantially unfeasible to invert. Unfortunately, these schemes are currently not practical for large-scale use. Since public-key directories typically will contain an enormous amount of entries, the Certification Authority will have to use an efficient signature scheme. This implies that the signatures in the public-key directory may be helpful in attempts to break the signature scheme of the Certification Authority; they can be used to mount known or (adaptively) chosen message attacks. Again, this problem is not removed by letting participants send their public keys only on request, instead of using a public-key directory.

A third problem is in blinding public-key certificate issuing protocols in mechanism for privacy-protected transfer of credentials (see, for instance, U.S. Pat. No. 4,759,063 to Chaum for a discussion of the technique of blinding in public-key cryptography). In many circumstances, the Certification Authority does not want the users to be able to blind to their hearts' contents, but would like to encode information in the issued information that cannot be changed by the blinding operations of the user. For instance, the mechanisms for transferring credentials under pseudonym, this encoded information can be uniquely associated with the user that the credential is issued to, thereby linking the pre-images of all the pseudonyms of each user. In this way, it can be ensured that users cannot use the credentials of other users, even if they cooperate. For credentials that may be shown only a limited number of times, such as coins in an electronic can system, it can be arranged that this encoded information is revealed if and only if the credential is shown a number of times exceeding a predetermined limit. This obviates the need for on-line verification of these credentials. For such purposes, an issuing protocol is needed in which the Certification Authority issues a secret key, a public key, and a public-key certificate, in such a way that the public key and the certificate can be perfectly blinded by the user, by a non-constant function of the secret key cannot. Such an issuing protocol is called a restrictive blind signature issuing protocol, and is described and claimed in patent application Ser. No. 08/203,231, filed Feb. 28, 1994, and is incorporated by reference herein. From the point of view of security, no satisfactory constructions of restrictive blind signature issuing protocols are known in which the certificate is a public-key certificate. This is a serious problem, since restrictive blind signature issuing protocols are of crucial importance for the construction of efficient and secure mechanisms for privacy-protected off-line transfer of credentials.

Patent application Ser. No. 08/203,231, filed Feb. 28, 1994, also describes and claims an inventive method for constructing restrictive blind signature issuing protocols where the issued certificate is not a digital signature on the public key (and hence not a public-key certificate). As is demonstrated in detail, the construction of efficient and secure restrictive blind signature issuing protocols becomes much easier by removing the need for the certificate to be a signature of the issuer on the public key. Most (more specifically, all but the last one described) of the exemplary restrictive blind signature issuing protocols described and claimed in patent application Ser. No. 08/203,231 are constructed by applying this inventive method.

While the inventive method described and claimed in patent application Ser. No. 08/203,231 overcomes the third problem associated with public-key certificates, it does not address the first two problems. This invention describes a generalized method that also overcomes the first two problems associated with public-key certificates.

OBJECTS OF THE INVENTION

Accordingly, it is an object of the present invention to allow anyone to generate pairs consisting of a public key and a corresponding certificate, while at the same time ensuring that it is unfeasible to generate, without knowledge of a special secret key that is held by a Certification Authority, triples consisting of a secret key, a matching public key, and a corresponding certificate, by providing for a new kind of certificates that will henceforth be called secret-key certificates.

Another object of the present invention is to prevent lists of certified public keys, such as public-key directories, from revealing the genuineness of privacy-related information, by using secret-key certificates instead of public-key certificates.

A further object of the present invention is to prevent lists of certified public keys, such as public-key directories, from revealing information that may be helpful in known or chosen message attacks on the signature scheme of the Certification Authority, by using secret-key certificates instead of public-key certificates.

Yet another object of the present invention is to describe techniques to construct secret-key certificates, and issuing protocols therefor, from a class of well-known digital signature schemes, (see, Fiat, A. and Shamir, A., "How to prove yourself: practical solutions to identification and signature problems," Crypto '86, Springer-Verlay (1987), pp. 186-194).

A still further object of the present invention is to construct efficient and secure restrictive blind secret-key certificate issuing protocols, by letting the Certification Authority issue triples consisting of a secret key, a matching public key, and a corresponding secret-key certificate, such that the public key and the certificate can be perfectly blinded by the receiving party, but at least part of the secret key cannot be blinded.

An even further object of the present invention is to implement hierarchical certification by recursively using secret-key certificates instead of public-key certificates.

Still another object of the present invention is to allow efficient, economical, and practical apparatus and methods fulfilling the other objects of the invention.

Other features, objects, and advantages of this invention will be appreciated when the description and appended claims are read in conjunction with the figures.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a representative combination block and functional diagram of an exemplary secret-key certificate system in accordance with the teachings of the present invention.

FIG. 2 shows a flowchart of a secret-key certificate issuing protocol for a first preferred embodiment in accordance with the teachings of the present invention.

FIG. 3 shows a flow chart of a secret-key certificate issuing protocol, such that the Certification Authority does not need to know the secret key of the recipient, for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 4 shows a flowchart of a secret-key certificate issuing protocol, such that the subliminal channel in the secret-key certificate is prevented, for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 5 shows a flowchart of a secret-key certificate issuing protocol, such that the recipient fully blinds the issued information, for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 6 shows a first flowchart of a restrictive blind secret-key certificate issuing protocol for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 7 shows a second flowchart of a restrictive blind secret-key certificate issuing protocol for the first preferred embodiment in accordance with the teachings of the present invention.

FIG. 8 shows a flowchart of a secret-key certificate issuing protocol for a second preferred embodiment in accordance with the teachings of the present invention.

FIG. 9 shows a flowchart of a secret-key certificate issuing protocol, such that the Certification Authority does not need to known the secret key of the recipient, for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 10 shows a flowchart of a secret-key certificate issuing protocol, such that the subliminal channel in the secret-key certificate is prevented, for the second preferred embodiment in accordance with the teachings of the present invention.

FIG. 11 shows a flowchart of a secret-key certificate issuing protocol, such that the recipient fully blinds the issued information, for the second preferred embodiment in accordance with the teachings of the present information.

FIG. 12 shows a flowchart of a restrictive blind secret-key certificate issuing protocol for the second preferred embodiment in accordance with the teachings of the present invention.

SUMMARY OF THE INVENTION

In accordance with these and other objects of this invention, a brief summary of the invention is presented. Some simplifications and omissions may be made in the following summary, which is intended to highlight and introduce some aspects of the present invention, but not to limit its scope. Detailed descriptions of preferred exemplary embodiments adequate to allow those of ordinary skill in the art to make and use this invention will be provided later.

In essence, the primary purpose of a public-key certificate is to certify the tasks that a participant in a cryptographic system can successfully perform with respect to his public key, rather than the public key itself. Consider the three most well-known public-key cryptographic tasks in a cryptographic system: digital signing, identification, and encryption. The intended purpose of a certificate is to certify that the tasks of digital signing, proving knowledge of a secret key that corresponds to a public key, and decrypting a message that is encrypted with a public key, are performed using a secret key the usage of which has been permitted by the Certification Authority. In other words, it is the secret key that must be certified, not necessarily the public key.

Informally, a secret-key certificate is a digital signature of the Certification Authority on a secret key, such that it is not a digital signature on the public key that matches the secret key. More precisely, triples consisting of a secret key, a matching public key, and a corresponding secret-key certificate can be feasibly generated only by the Certification Authority, but pairs consisting of a public key and a corresponding secret-key certificate can be feasibly generated by anyone.

The following illustration may help to appreciate how such a condition can be met. Consider the task of generating a pair (s, h.noteq.1), such that h is equal to g.sup.s, where g is a randomly chosen generator of a group in which multiplication is simple but no feasible algorithms for computing discrete logarithms are known. As will be obvious to those of ordinary skill in the art, this is a simple task; unless, in addition, one must also know a number t such that h is equal to g.sub.1.sup.t, where g.sub.1 is another randomly chosen generator of the group, that has been fixed in advance.

In a public-key directory, parties are listed together with their public keys and corresponding certificates. If the certificates are secret-key certificates, then the information in the directory does not reveal discriminating information about legitimate participation, as each of the entries could have been generated by anyone (if the directory is, or has been at a certain point in time, open for public writing). If additional information is included as well, such as telephone numbers, postal address, and access rights, than this may be bogus information as well. To ensure that users will be unable to tell whether entries in a public-key directory have been certified by the Certification Authority or not, the manufacturer of a public-key directory on, say, a CD-ROM, can gather the entries in the Directory by letting the parties associated with the public keys submit their own public keys and associated secret-key certificates, as they wish them to appear on the CD-ROM.

For the same reason, the information listed in the directory cannot be of much help in attaching the signature scheme of the Certification Authority. In particular, it can be of no help whatsoever if pairs consisting of a public key and a corresponding secret-key certificate can be generated, without cooperation of the Certification Authority, with a probability distribution that is indistinguishable from the probability distribution that applies when the certificate issuing protocol is performed with the Certification Authority.

An attacker whose keys have not been certified by the KAC would need to known the secret keys of legitimate participants in the system in order to have any advantage in breaking the signature scheme of the Certification Authority over trying to break it from scratch. Revealing one's secret key brings along a great deal of trust in that it will not be misused, and so in practice the consequence of using secret-key certificates instead of public-key certificates is that known or chosen message attacks to break the signature scheme of the KAC will be much harder to mount.

Secure public-key cryptographic schemes, such as schemes for the aforementioned tasks of proving knowledge of a secret key corresponding to a public key, signing a message with a secret key corresponding to a public key, and decrypting a message encrypted with a public key, are only feasible to perform if one actually knows the secret key corresponding to the public key. Hence, the fact that a user can successfully perform such a task attests to the fact that he knows the secret key corresponding to his public key, and this in turn proves that the certificate must have been issued by the Certification Authority.

The following illustrations are helpful to appreciate the use of secret-key certificates:

1. Suppose that a first party wants to transfer an encrypted message to a second party. From the public-key directory, the first party retrieves the public key of the second party, and a corresponding secret-key certificate, which supposedly has been issued by the Certification Authority. The first party encrypts its message using the public key of the second party, and transfers it to the second part. Although the first party does not know whether the information listed in the public-key directory is genuine or not, it is ensured that if the second party can decrypt and retrieve the original message, then the Certification Authority computed the string listed in the public-key directory. Obviously, a proper response of the second party to the first party will allow the first party to distinguish between the two cases.

2. Suppose that the second party digitally signs a message for the first party. Given the message, the digital signature of the second party, and the information listed with the second party in the public-key directory, the first party is able to verify not only that the digital signature is genuine, but it is also ensured that it was indeed made with a certified key. Of course, if this signature is to have any legal significance, then anyone should be able to verify these two facts.

3. Suppose that the second party wishes to obtain a secret-key certificate, issued by the first part. To this end, the first party issues, by applying its secret key, a secret-key certificate on a public key of the second party. Not only can the second party verify the validity of the secret-key certificate issued by the first party, by using the public key of the first party, but if the verification holds, it also is ensured that the secret-key certificate on the public key of the first party has been issued by the Certification Authority. In general, recursive application of secret-key certificates allows hierarchical certification trees to be formed that offer the same security as hierarchical certification trees formed from public-key certificates.

An example of a secret-key certificate and a corresponding issuing protocol will now be described. As is common in the art, for any integer, l, the symbol denotes the set of integers {0, . . . , l-1}, for which addition and multiplication are defined modulo l. Let G.sub.q denote a group of prime order, q, for which no feasible algorithms are known to compute discrete logarithms, and let be a one-way hash-function that maps its arguments to .sub.2.sup.t, where t is an appropriately large security parameter. The secret key of the Certification Authority is a number x.sub.0 in .sub.q, and the corresponding public key is (g, h.sub.0), where h.sub.0 denotes g.sup.x.sub.0, and both g and h.sub.0 are in G.sub.q. The parties, whose keys are to be certified, use the same key set-up as the Certification Authority: the secret key of a party is a number x in .sub.q, and the corresponding public key is h=g.sup.x. a secret-key certificate on h is a pair (c, r), where c is in .sub.2t and r is in G.sub.q, such that c is equal to (h,g.sup.r (h.sub.0 h).sup.-c,I). Here, I is an, optionally included, string consisting of additional information about the party associated with the public key.

As will be clear to those of ordinary skill in the art, the certificate of the Certification Authority in effect is a Schnorr signature (see; Schnorr, C., "Efficient Signature Generation by Smart Cards,"Journal of Cryptology, Vol. 4, No. 3, (1991), pp. 161-174) on g.sup.x, made with secret key x.sub.0 +x mod q. Anyone can feasibly generate pairs h,(c,r) such that the verification relation holds, by taking h equal to h.sub.0.sup.-1 g.sup.s for an arbitrary s in .sub.q, and a equal to g.sup.t for an arbitrary t in .sub.q ; the pair (c,sc +t mod q), with c=(h,a,I), then matches h. However, the ability to feasibly generate such pairs together with the secret key log.sub.g h would enable one to forge Schnorr signatures.

To issue a secret-key certificate, the Certification Authority can proceed as follows. It generates at random a number w in .sub.q, and computes a=g.sup.w. It then computes c=(h,a,I) and r=c(X.sub.0 +x)+w mod q, and transfers (c,r) to . As will be demonstrated in the detailed description, the issuing protocol can be modified such that the need for the Certification Authority to known the secret key can be prevented. Moreover, a variety of blinding capabilities for can be incorporated into the issuing protocol.

In sum, the present invention describes certificate techniques based on public-key cryptography, that solve problems related to the well-known cryptographic technique of public-key certificates.

DETAILED DESCRIPTION OF THE INVENTION

While it is believed that the notation of FIGS. 2 to 12 would be clear to those of ordinary skill in the art, it is first reviewed here for definiteness.

A variety of secret-key certificates issuing protocols is described by flowcharts. The actions performed by the parties participating in these protocols are grouped together into flowchart boxes. The party performing the actions described in a flowchart box is indicated by the column that the box is in. The columns are labeled by a symbol denoting the type of party. The term"party" is used to indicate an entity with control over at least the secrecy of some information, usually at least one key. It is anticipated that a plurality of people may each known all or part of some key, and that they might collectively be thought of as a party. In other cases, a key may be substantially unknown to people, and reside in some physical device, and the device itself or those who control it from time to time, may be regarded as parties. Thus the parties denoted by single boxes or collections of boxes might sometimes be regarded as agents who perform a step or a collection of steps in a protocol. They might also be regarded as means for performing those steps, and might be comprised of any suitable configuration of digital logic circuitry. For example, any box or collection of boxes from the figures could be realized by hard-wired and dedicated combinatorial logic, or by some sort of suitably programmed machine, a microprocessor for instance, such as are well-known in the art, just as long as it is able to perform the storage, input/output and transformational steps (possibly apart from the random source functions) described by the corresponding box or boxes.

As is common in the art, for any integer, l, the symbol .sub.l denotes the set of numbers {0, . . . , l-1}. Addition and multiplication of elements in .sub.l are defined module l. Similarly, the symbol .sub.i denotes the set of number in {0, . . . l-1} that are co-prime to l. Multiplication of elements in .sub.i is defined modulo l. As is well-known in the art, .sub.l is called a ring of integers modulo l, and .sub.i is called a multiplicative group of integers modulo l.

The symbol ".rarw." denotes assignment, meaning that the variable or symbol on its left-hand side is assigned the value on its right-hand side to. The assignments do not necessarily imply that storage space must actually be reserved; they may indicate intermediate values manipulated in volatile memory.

Another operation is a test for equality, which is indicated by the symbol. As is common in the art, the protocol halts in the case the equality does not hold.

The symbol .epsilon..sub.R indicates that the number, or each of the numbers, on its left-hand side is chosen from the set on its right-hand side according to a uniform probability distribution, and independent of anything else. In practice, pseudo-random techniques may be used, and the deviation from the uniform distribution may be significant without resulting in an appreciable loss in security and/or privacy. Such techniques are well-known in the art.

Another action is denoted by the word "Send," followed by a colon and one or more numbers. This indicates that these numbers are sent by the party performing the actions described in the box to the other party participating in the protocol. The directed connections between the boxes indicate the order in which the actions that are grouped in the boxes are performed.

Apparatus for Secret-Key Certificates Systems

A precise description of the apparatus for a secure secret-key certificate system will now be given. The apparatus comprises the following five means:

1. First key generation means that, on being given as input at least a security parameter, outputs a secret key and a matching public key, to be used by the Certification Authority for certifying keys of parties that wish to participate in the cryptographic system.

As will be clear to those of ordinary skill in the art, the binary length of the output is polynominally (preferably linearly) related to the security parameter.

The first key generation means is of a probabilistic nature, meaning that the key pair is generated in a substantially random manner. Preferably, the randomization process is based on the output of some physical source of randomness, possibly combined with the output of a cryptographically strong pseudo-random number generator taking, for instance, the bitwise exclusive-or of the two outputs.

2. Second key generation means that, on being given as input at least a security parameter, outputs a key pair consisting of a secret key and a matching public key, to be used by a party that wishes to participate in the cryptographic system.

As with the first key generation means, the output is the result of a suitable randomization process. The means may be operated by the party itself, by the Certification Authority, or by the both of them. The first and second key generation means may, but need not, be equivalent.

3. Certificate verification means that, on being given as input the public key of the Certification Authority and a pair consisting of a public key and a presumed secret-key certificate, outputs a response that is to be interpreted as "yes" or "no."

Usually, the verification relation will be deterministic, but this need not be the case; the certificate verification means may be of probabilistic nature, performing a great many random trials in order to decide whether the presumed certificate is a secret-key certificate on the public key.

The certificate verification means outputs "yes" if and only if the presumed certificate is a secret-key certificate on the public key. In other words, the certificate verification means defines what a secret-key certificate on a public key is.

4. Certificate issuing means that, on being given as input the secret key of the Certification Authority and a pair consisting of a secret key and a matching public key of a party that requires a certificate, outputs a digital signature on the secret key, such that the certificate verification means, on being given as input the public key of the Certification Authority and a pair consisting of the public key and the issued digital signature, outputs "yes" (and so the output of the certificate issuing means is a secret-key certificate on the public key).

The certificate issuing means may, but need not, be of a probabilistic nature.

Obviously, it will usually suffice to take only the secret key of the Certification Authority and the secret key of the party as input, since the public key can usually be computed from the secret key.

As will be appreciated, the certificate issuing means can be such that the party, whose keys are to be certified, can keep secret from the Certification Authority its secret key. In that case, the certificate issuing means itself comprises means controlled by the party, means controlled by the Certification Authority, and suitable interface means for allowing communication therebetween. The means controlled by the party takes as input the secret key of the party (and possibly also the public key of the party), and the means controlled by the Certification Authority takes as input the secret key of the Certification Authority (and possibly also the public key of the party). The final output is the result of processing by the means controlled by the party and the means controlled by the Certification Authority, where appropriate intermediate results may be communicated through the interface means. The precise actions to be performed by the means that the certificate issuing means comprises, must be described by a cryptographic protocol, henceforth called a secret-key certificate issuing protocol.

Yet another variation is that the Certification Authority can compute the secret keys corresponding to any public key of a party that requires a secret-key certificate, because it knows additional trap-door information.

These and other variations will be appreciated by studying the exemplary embodiments. For example, the certificate issuing process may be blinded by the means controlled by the party, according to a variety of criteria that will be described in the text.

5. Certificate simulating means that, on being given as input the public key of the Certification Authority, outputs a pair consisting of a public key and a matching certificate.

The public key that is output is such that it could have been output by the second key generation means (as part of the pair that it outputs). "Matching" indicates that the certificate verification means, on being given as input the public key of the Certification Authority and the output of the certificate simulating means, outputs "yes." The certificate simulating means is of a probabilistic nature, and the probability distribution of its output should be substantially indistinguishable from the probability distribution that applies when the public key is generated by the second key generation means and the certificate is generated by the certificate issuing means.

As will be clear to those of ordinary sk