System and method for transferring the right to decode messages in a symmetric encoding scheme6859533Abstract Methods for transferring among key holders in encoding and cryptographic systems the right to decode and decrypt messages in a way that does not explicitly reveal decoding and decrypting keys used and the original messages. Such methods are more secure and more efficient than typical re-encoding and re-encryption schemes, and are useful in developing such applications as document distribution and long-term file protection. Claims What is claimed is: Description FIELD OF THE INVENTION
TABLE 1
Scheme Key Space "K" Operation "."
X B.sub.n .sym.(XOR)
M Z.sub.n * .times.(mod n)
S Z.sub.n +(mod n)
P II.sub.n .degree.(composition)
A Z.sub.n * .times. Z.sub.n *(defined above)
When the key space K of an encoding scheme (X, K, E, D) is a group with some operation ".multidot.", the encoding and decoding transformations may be uniquely determined by the keys. This happens when the key space K is isomorphic, as a group, to the transformation groups E={E.sub.k.vertline.k.epsilon.K} and D={D.sub.k.vertline.k.epsilon.K} formed by the encoding and decoding transformations on the message space X; that is, for any k, k'.epsilon.K, D.sub.k =(E.sub.k).sup.-1 =E.sub.k.sub..sup.-1 and E.sub.k.smallcircle.E.sub.k' =E.sub.k.multidot.k' and E.sub.k =(D.sub.k).sup.-1 =D.sub.k.sub..sup.-1 and D.sub.k.smallcircle.D.sub.k' =D.sub.kk', where .smallcircle. is the composition operator of the transformations, which is defined as, for example, E.sub.k.smallcircle.E.sub.k' (x)=E.sub.k' (E.sub.k (x)) for all x.epsilon.X. It can be easily checked that all the schemes given in Table 1 above are key-determined. Key-determined encoding schemes permit a systematic way to transfer the right to decode messages from one key holder to another. With the isomorphism between the key space and the transformation groups, the composition of the decoding transformation with one key k and the encoding transformation with another key k' can then be viewed as the encoding transformation determined by the composed key k.sup.-1.multidot.k. Let (X, K, E, D) be a key-determined encoding scheme. Suppose y=E.sub.k (x) is the encoded version of the message x.epsilon.X with the key k.epsilon.K. The right to decode the encoded message of x can be transferred from the key holder of k to the key holder of k' in the two-step algorithm shown in FIG. 3. First, generate a transfer key t=k.sup.-1.multidot.k (step 310). Then encode the message with the transfer key t according to y'=E.sub.t (y) (step 312). The algorithm is correct thanks to the property of the key space being isomorphic to the encoding and decoding transformation groups. The correctness can be verified as follows: ##EQU3## The generality of the algorithm makes it immediate to derive the transference steps for the example schemes set forth above. Referring again to FIG. 3, for the XOR Scheme X over B.sub.n, to convert y=E.sub.k (x) to y'=E.sub.k' (x), first generate a transfer key t=k.sym.k'(step 310). Then encode the message with the transfer key t according to y'=y.sym.t (step 312). For the Multiplicative Scheme M over Z*.sub.n, to convert y=E.sub.a (x) to y'=E.sub.a' (x), first generate a transfer key t=a'a.sup.-1 (mod n) (step 310). Then encode the message with the transfer key t according to y'=ty (mod n) (step 312). For the Shift Scheme S over Z.sub.n, to convert y=E.sub.b (x) to y'=E.sub.b' (x), first generate a transfer key t=b'-b (mod n) (step 310). Then encode the message with the transfer key t according to y'=y.sym.t (mod n) (step 312). For the Substitution Scheme P over .PI..sub.n, to convert y=E.sub.p (x) to y'=E.sub.p' (x), first generate a transfer key t=p.sup.-1.smallcircle.p'(step 310). Then encode the message with the transfer key t according to y'=t(y). (step 312). As will be described below, it is also possible to transfer the right to decode in product schemes of not only key-determined encoding but also commuting schemes. In order to define commuting schemes, it is necessary to characterize encoding schemes that are essentially equivalent. Suppose that S=(X, K, E, D) and S'=(X, K', E', D) are two encoding schemes with the same message space X. S is said to be equivalent to S', denoted by S.ident.S', if there is a bijective (one-to-one and onto) mapping h: K.fwdarw.K' such that for each message x.epsilon.X and for each key k.epsilon.K, E.sub.k (x)=E'.sub.h(k) (x) and D.sub.k (x)=D'.sub.h(k) (x). Clearly, the scheme equivalence relation .ident. is an equivalence relation; that is, it satisfies that, for any encoding schemes S, S', S", the following hold: (i) S.ident.S; (ii) S.ident.S' implies S'.ident.S; and (iii) S.ident.S' and S'.ident.S" imply S.ident.S". Thus, equivalent encoding schemes form an equivalence class in that each scheme in the class provides no more and no less functionality than any others in the class. The scheme equivalence relation allows one to characterize encoding schemes in several ways. An encoding scheme S is said to be idempotent if S.sup.2.ident.S. Many of the encoding schemes are idempotent, including the XOR, multiplicative, shift, substitution, and affine schemes. If a scheme S is idempotent, then there is no point in using the product scheme S.sup.2, as it requires an extra key but provides no more functionality. Another characterization on encoding schemes using the scheme equivalence relation .ident. is that of commuting schemes. Two encoding schemes S and S' are said to commute if S.times.S'.ident.S'.times.S. Trivially, any scheme commutes with itself. A not-so-trivial example is that of the multiplicative scheme M and the shift scheme S. To see that they commute, i.e., M.times.S.ident.S.times.M, one can compare the equations E.sub.b (E.sub.a (x))=ax+b(mod n) and E.sub.a (E.sub.b (x))=ax+ab(mod n); and find out that the mapping h:K.sub.s.times.K.sub.M.fwdarw.K.sub.M.times.K.sub.s defined by h(b,a)=(a,a.sup.-1 b(mod n)) makes the product S.times.M isomorphic to the product M.times.S. Product schemes of key-determined and commuting encoding schemes enjoy a systematic way of transferring the right to decode messages. Let S.sub.1.times.S.sub.2 be the product scheme of two key-determined and commuting encoding schemes. Suppose that h=(h.sub.1,h.sub.2):K.sub.2.times.K.sub.1.fwdarw.K.sub.1.times.K.sub.2 is the mapping that makes S.sub.2.times.S.sub.1 isomorphic to S.sub.1.times.S.sub.2, where h.sub.1 :K.sub.2.times.K.sub.1.fwdarw.K.sub.1 and h.sub.2 : K.sub.2.times.K.sub.1 K.sub.2. First, observe that the product scheme is also key-determined; the product key space K.sub.1.times.K.sub.2 is a group with respect to the operation * defined by (k.sub.1,k.sub.2)*(k'.sub.1,k.sub.2 ')=(k.sub.1.multidot.h.sub.1 (k.sub.2,k.sub.1 '),h.sub.2 (k.sub.2,k'.sub.1).multidot.k.sub.2 '). This is because ##EQU4## Now, the right to decode the encoded message of x can be transferred from the key holder of k to the key holder of another key k' in the two-step algorithm shown in FIG. 3. First, generate a transfer key t=(h.sub.1 (k.sub.2.sup.-1, k.sub.1.sup.-1.multidot.k'.sub.1), h.sub.2 (k.sub.2.sup.-1,k.sub.1.sup.-1.multidot.k').multidot.k.sub.2 ') (step 310). Then encode the message with the transfer key t according to y'=E.sub.t (y) (step 312). The correctness of the transference algorithm is verified by the following equality: ##EQU5## where the last entity can be readily decoded using the key k'=(k'.sub.1,k'.sub.2). The method is best illustrated with the following example, applying the affine cipher A over Z.sub.n. Since A=M.times.S, and M and S are key-determined, commuting schemes, the method described above applies to the affine scheme. As seen before, it is the mapping h(b, a)=(a, ab) that makes S.times.M isomorphic to M.times.S. Thus, h.sub.1 (b, a)=a and h.sub.2 (a, b)=ab (mod n). The transfer key t from (a, b) to (a', b') can be derived as ##EQU6## Then, to decode y using a second key (a', b'), first generate a transfer key t=(a'a.sup.-1 (mod n),-a'a.sup.-1 b+b'(mod n)){character pullout} (t.sub.1,t.sub.2)(step 310). Then encode the message using the transfer key t according to y'=t.sub.1 y+t.sub.2 (mod n) (step 312). The methods presented herein for transferring the right to decode messages are transitive. This means that two sequential transfers from Alice to Bob and then from Bob to Carol are equivalent to a direct transfer from Alice to Carol. It is important to note that, in each of the example schemes, a transfer key is also a key of the scheme. Accordingly, two transfer keys used in the two sequential transfers can be combined to form a transfer key for the direct transfer. Take the affine scheme as an example. Let k=(a, b), k'=(a', b'), and k"=(a", b") be the keys for Alice, Bob, and Carol, respectively. Then the transfer keys are t=(a'a.sup.-1,-a"a.sup.-1 b+b") from Alice to Bob, t'=(a"a'.sup.-1,-a"a'.sup.-1 b'+b") from Bob to Carol, and t"=(a"a.sup.-1,-a"a.sup.-1 b+b") from Alice to Carol. It is straightforward to verify that the composition of t and t' as keys in the affine scheme yields t": ##EQU7## In other words, the composition of sequential transfers of the right to decode messages is memory-less; all the intermediate transfers will not be reflected in the overall transfer. It should be noted also that, for the schemes X, M, and S, the transfer key generation step is equivalent to "decoding" k' with k. Thus, the computation needed in the transfer is the same as the one used in the decoding-and-re-encoding method for these schemes. One may think that the new method shows no improvement in this efficiency regard, but it has been found that the transfer key is message-independent and hence needs to be computed only once. When the number of messages m involved in the transfer increases, this feature will cut the computation required by the re-encoding method by half. Moreover, the transfer key t does not leak any useful information on the keys k and k', and a transfer performed according to the methods set forth herein will not reveal the message x. These properties make the proposed method appealing when the security of the message x and the decoding keys k and k' is an issue during a transfer. A typical system configuration capable of carrying out the methods described with reference to FIG. 3 (and described in further detail below) is shown in FIG. 4. There are three relevant parties in most proxy encryption applications. An Encryptor 410, a Grantor A 412, and a Grantee B 414. As will be recognized, the encryption, decryption, and other processing operations performed in the invention are facilitated by a processor (416, 418, 420) under each party's control. Each processor is equipped with memory (422, 424, 426) for data storage and a communication interface (428, 430, 432), capable of sending and receiving messages. Proxy Encryption Schemes The rest of the disclosure, directed to more formal proxy encryption schemes, rather than encoding schemes, is organized as follows. First, a generic proxy encryption scheme is described and characterized according to several criteria. The several following paragraphs fix set forth notation that will be used throughout the disclosure and recall the ElGamal public-key encryption scheme. For the purpose of comparison, this disclosure then lists two existing proxy encryption schemes and examines their properties in comparison to the present invention. Details on the two new proxy encryption schemes are then introduced, together with their security and performance analysis. Applications of these new schemes to massive document distribution and file protection are given thereafter. As indicated in the introduction, the goal of proxy encryption is to delegate the decryption right from one to another in secure and efficient ways. For the discussion that follows, it is convenient to define the roles of parties that may be involved in proxy encryption. Two most important roles are those of grantor and grantee. A grantor is an original key holder of encrypted messages who wants to delegate the decryption right to someone else. A grantee is a key holder designated to perform decryption on behalf of a grantor and thus act as grantor's decryption proxy. In the motivating example in the introduction, Alice is the grantor while Bob is the grantee. Other roles may include an encryptor who is an one that originally encrypts messages for the grantor, and a facilitator who may help to perform some message processing tasks, such as transforming messages encrypted for the grantor into messages encrypted for the grantee. Certainly, it is not necessary that all these roles are played by different parties. For example, a party may play roles of the grantor and facilitator, as in the Mambo and Okamoto schemes discussed below. With these roles in place, a proxy encryption scheme is just a description of how a grantee, possibly with some aid from a facilitator, delegates a grantee the right to decrypt messages originally generated by an encryptor for the grantee. A proxy encryption scheme may consist of four generic steps: message encryption, proxy key generation, proxy transformation and message decryption. These steps will be described in further detail below, with reference to FIG. 5. 1. Message encryption E: The encryptor generates an encrypted message using grantor's encryption key and delivers it to the grantor (step 510). 2. Proxy generation .pi.: To delegate the decryption right to the grantee, the grantor generates a proxy key .pi. as a commitment token that allows the grantee to decrypt the message encrypted for the grantor (step 512). 3. Proxy transformation .PI.: When necessary, the facilitator performs a proxy transformation .PI., possibly using the proxy key it, to convert the message encrypted for the grantor to a message encrypted for the grantee (step 514). 4. Message decryption D: Upon receiving the transformed message and possibly the proxy key .pi., the grantee decrypts the message (step 516). Accordingly, it should be observed that the generic scheme above covers the two straightforward solutions to proxy encryption mentioned in the introduction. The re-encryption scheme is a special case where the grantor (Alice) is also the facilitator who actually decrypts the message and then encrypts for the grantee (Bob), and the proxy a can be considered as a collection of grantor's decryption key and grantee's encryption key, which is used only by the grantor and not by the grantee. The scheme of passing grantor's decryption key to the grantee is another special case of the generic scheme, where the proxy key is the decryption key and the proxy transformation is the identity transformation. However, not all schemes that can be derived from the generic one above are qualified as proxy encryption schemes. Intuitively, a proxy encryption scheme has to satisfy some basic requirements, namely delegation, security, transitivity and performance, as described below. Delegation. To ensure that, at the end of the message decryption step, the grantee is able to recover the original message correctly, the following equation must hold for any message m: D(.PI.(E(m,e.sub.A),.pi.),d.sub.B,.pi.)=m, where E(m,e) is an encryption function of message m under encryption key e, D(c,d,.pi.) is a corresponding decryption function of encrypted message c under decryption key d and possibly proxy key .pi., .PI.(c,r) is the proxy function that converts encrypted message c according to proxy key .pi., and e.sub.A, e.sub.B, d.sub.A, and d.sub.B are the encryption and decryption keys of the grantor A and grantee B, respectively. In addition to the correctness above, the functionality of delegation should be guaranteed. In one form, this means that, after the proxy key is issued and the proxy transformation is completed, the message decryption step should require no private information from the grantor, and it should be carried out solely by the grantee. In another form, this is equivalent to undeniability of the delegation from the grantor; that is, once the proxy key is created and proxy transformation is performed, the grantor should not be able to deny the delegation, without seeking other means such as preventing the grantee from obtaining the proxy key and receiving the transformed message. As a consequence of this functionality, the grantor's decryption key can be destroyed with grantee's decryption key and possibly the proxy key maintaining the ability to decrypt the message. (This is useful in the file protection application later in Section 6.) Security. In essence, a proxy encryption scheme is also an encryption scheme at least from the grantee's point of view. The introduction of proxy keys and transformations must in no way compromise security and privacy of the encryption. Thus, it should be at least computationally hard for any unauthorized third party to recover the original message and decryption keys of the grantor and grantee from publicly available information. Moreover, forging valid proxy keys by any untrusted party should be very hard. It must be clear, though, that generating the proxy key .pi. requires knowledge of at least the decryption key of the grantor; otherwise the underlying encryption system is not secure. Transitivity. Naturally, the proxy relationship should be transitive. After the grantor delegates the decryption right, the grantee should be able to act as a new grantor to delegate the right further to another grantee, by just following the same scheme. Moreover, it should be possible for someone, say the first grantor, to delegate the right directly to a new grantee by combining all intermediate proxy keys into one proxy key and composing all consecutive proxy transformations into one transformation. Performance. As the re-encryption scheme is an intuitive, straightforward solution to proxy encryption and it satisfies the above delegation, security and transitivity requirements, any practically useful proxy encryption scheme should have no degradation in computational performance when compared with the re-encryption scheme. Proxy encryption schemes may vary according to their application requirements. They can be categorized according to many aspects. Obvious ones include whether they are public-key or private-key based, and whether their security measures are perfect in the information theoretical sense or rely on intractability of some computational problems. The following aspects ones are related to the proxy key and transformation. Confidentiality. While secrecy of messages and decryption keys has to be enforced, secrecy of proxy keys and proxy transformations may not be a mandatory requirement. A scheme is called public if proxy keys it generates may be published without compromising its security and proxy transformations applied in untrusted environments; otherwise, the scheme is private. In a private scheme, when a proxy key is transferred from the grantor to the facilitator and grantee, care must be taken to protect the proxy key from disclosure. As a result, the proxy transformation which uses the proxy key must be performed in private as well. Commutativity. In terms of messages, the grantee must be unconditionally trusted by the grantor, since proxy encryption by definition allows the former to decrypt on behalf of the latter. However, the trust model may be different for their private information. A proxy encryption scheme is commutative if the grantor and grantee have to trust each other with regard to their private keys; otherwise, it is non-commutative. A commutative example is that the proxy key is such created that either one of the grantor and grantee can obtain other's decryption key from it. Whenever this is the case, the proxy encryption mechanism may be simplified to a key exchange protocol that allows the grantee to use grantor's decryption key to decrypt the encrypted messages directly. Generality. In many cases, the grantor wants to restrict the scope of the delegated decryption right. Often intended restrictions include that the proxy key may only be used by a designated grantee, that the proxy key may only be applicable to a specific message, or that the proxy transformation may only be applied by a specific facilitator. For example, when a proxy encryption scheme is used in some applications like key escrow, it would be ideal that proxy keys are independent of messages they will apply to. But for occasional delegation such as securely specifying inheritance in someone's will, it may be highly desirable that a proxy key can only be restricted to a designated party (e.g., a grandchild), applicable to a specific message (e.g., some portion of the will) and possibly used in the proxy transformation by a particular party (an attorney). Degenerateness. When used in the extreme situation where the grantor and grantee are a same person with a same decryption key, a proxy encryption scheme should reduce to a regular encryption scheme, without introducing any complications (such as non-trivial proxy keys and transformations, and the requirement of an extra facilitator). As will be shown below, the Mambo and Okamoto schemes are private and non-commutative. Proxy keys in their schemes can be either message-independent or dependent but are not restricted to designated grantees. The Blaze and Strauss scheme is just opposite: it is public but commutative, and its proxy keys are message-independent but uniquely associated with designated grantees. In comparison, the schemes according to the invention set forth herein are public and non-commutative, and their proxy keys are message-dependent and restricted to designated grantees. Proxy Encryption Using the ElGamal Cryptosystem As the proxy encryption schemes discussed below in this disclosure will all be based on discrete logarithms in multiplicative groups, a formal setting which is common to all these encryption schemes is hereby adopted. The notation used herein recalls the ElGamal encryption scheme. Encryption schemes based on discrete logarithms are particularly advantageous because of their technical advantages over RSA-type schemes and their natural generalizations to many finite groups such as elliptic curve groups over finite fields. As set forth above, for any natural number n, let Z.sub.n ={0, 1, . . . , n-1} denote the ring of integers modulo n, and let Z*.sub.n ={m.epsilon.Z.sub.n.vertline.gcd(m,n)=1} denote the multiplicative group of Z.sub.n. Note that, when n is a prime, Z*.sub.n ={1, . . . , n-1}. For a modulo n and a number a that is relatively prime to n, let a.sup.-1 denote the multiplicative inverse of a modulo n; that is, a.sup.-1 is the element that satisfies aa.sup.- 5 1(mod n). An element a of Z*.sub.p is said to be of order m if the number of its powers modulo n is m. A generator g of Z*.sub.n, if it exists, is an element of order .vertline.Z*.sub.n.vertline.(the size of Z*.sub.n); in this case, Z*.sub.n is a cyclic group. When n is a prime, every element of Z*.sub.n except 1 is a generator of Z*.sub.n. Let Z*.sub.n be a cyclic group with a generator g. The discrete logarithm of an element x to the base g, denoted as log.sub.g x, is the unique integer a, 0.ltoreq.a.ltoreq.n-1, such that x=g.sup.a (mod n). The discrete logarithm problem is that, given a prime p, a generator g of Z*.sub.p, and an element x.epsilon.Z*.sub.p, find the integer a, 0.ltoreq.a.ltoreq.p-2,such that g.sup.a.ident.x(mod p). A very closely related problem is the Diffie-Hellman problem: given a prime p, a generator g of Z*.sub.p, and elements g.sup.a (mod p) and g.sup.b (mod p), find g.sup.ab (mod p). The discrete-logarithm problem is at least as hard as the Diffie-Hellman problem, because any solution to the former problem can be used to solve the latter problem. The ElGamal encryption scheme shown in FIG. 6 is a part of a discrete-logarithm based, public-key cryptosystem proposed by ElGamal for both encryption and digital signature. See T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithm," IEEE Trans. on Information Theory, Vol. 31, pp. 465-472 (1985). Referring now to FIG. 6 in detail, the ElGamal scheme is set up (step 610) by establishing two public parameters p and g, where p is a prime (typically 512 bits in length), such that p-1 has a large (typically 160 bit) prime factor q (e.g., p=2q+1) and g is a generator in Z*.sup.p. A private key for a user is set (step 612) by uniformly choosing a random number a.epsilon.Z*.sub.p-1. Its related public key is calculated (step 614) as a=g.sup.a (mod p). The user publishes a and keeps a secret. To encrypt a message m to be sent to user A with public key a, a random number k.epsilon.Z*.sub.p-1, is uniformly chosen (step 616), and a pair of numbers (r,s), together representing the encrypted message to be sent to A, is calculated (step 618) as follows: r=g.sup.k (mod p) and s=m.alpha..sup.k (mod p). To decrypt the message (r,s), the recipient A recovers the message m (step 620) by calculating m=s(r.sup.a)-(mod p) Note that the selection of the public parameters is intended to establish equation g.sup.p-1 (mod p).ident.1 (Fermat's little theorem). These parameters should be authentically known to all users. They can be chosen, say, by some trusted authority. Also, the way that private key a is chosen ensures that the inverse a.sup.-1 of a modulo p-1 exists and is unique. Unlike the RSA public-key encryption scheme, the ElGamal scheme is non-deterministic, since the encrypted message also depends on the random number k. Indeed, it is similar in nature to the Diffie-Hellman key exchange protocol; the key established between the sender and receiver for encrypting and decrypting the message m is g.sup.ak (mod p) from r=g.sup.k (mod p) (part of the encrypted message) and .alpha.=g.sup.a (mod p) (the public key of A). Nevertheless, the security of the ElGamal encryption scheme relies on the intractability of the discrete logarithm problem and the Diffie-Hellman problem. To date, practice in seeking optimal algorithms for the discrete logarithm problem has not found any efficient (polynomial-time) solution. It is similar to the situation for the integer factorization problem upon which security of the RSA scheme is based. Moreover, it has also been shown that, for some primes p, solving the discrete logarithm problem is at least as hard as solving the factorization problem of a same size. This implies that for those ps, the ElGamal scheme is at least as secure as the RSA scheme. Very recently, several proxy encryption schemes have been proposed. All these schemes follow the generic proxy encryption scheme in delegating the decryption right: the encryptor sends an encrypted message to the grantor A, who then delegates the decryption right to grantee B by creating the proxy key, and after the proxy transformation is completed the grantee B finally decrypts the message. Two representative and known proxy encryption schemes are presented below: one from Mambo and Okamoto and the other from Blaze and Strauss, both of which are variations on the ElGamal scheme. Since they have the same scheme setup as the ElGamal scheme, the setup (see steps 610-614 of FIG. 6 above) is omitted from the presentation. Mambo and Okamoto have proposed three proxy encryption schemes: two are based on the ElGamal scheme and the other is based on the RSA scheme. The one shown in FIG. 6 and described below is ElGamal-based and shares its basic features with the other two schemes. Referring now to FIG. 7, given a message m that needs to be sent to a grantor A with public key a, the message m is encrypted by uniformly choosing a random number k.epsilon.Z*.sub.p-1 (step 710) and calculating a pair of numbers (r,s) representing the encrypted message (step 712) as follows: r=g.sup.k (mod p) and s=m.alpha..sup.k (mod p). To delegate the decryption right to a grantee B, the grantor A creates a proxy key .pi. by uniformly choosing a random number a'.epsilon.Z*.sub.p-1 (step 714) and calculating .pi.=aa'(mod(p-1)) (step 716). Then, A delivers the proxy key .pi. to B (step 718) in a secure manner (e.g., by encrypting it with B's public key) and keeps the value of a' private. To allow B to decrypt the message, A calculates r'=r.sup.a.sup..sup.-1 (mod p), where a'.sup.-1 is the multiplicative inverse of a' modulo p-1 (step 720). The pair (r', s) is the transformed, encrypted message to be sent to B. Upon receiving the transformed message (r', s) and the proxy key .pi., B decrypts the message m (step 722) by calculating m=s(r'.sup..pi.).sup.-1 (mod p). This proxy encryption scheme uses the encryption and decryption components of the ElGamal scheme, except B's private key is replaced by the proxy key .pi.. It is correct because, when using .pi. to decrypt the transformed message (r', s), the following holds: s((r').sup..pi.).sup.-1 (mod p)=s(r.sup.aa'a'.sup..sup.-1 ).sup.-1 (mod p)=mg.sup.ka (g.sup.ka).sup.-1 (mod p)=m. The security of this scheme is evaluated in two aspects. The complexity for anyone, including the grantee B, to discover grantor A's private key a based on all the available information is as same as the one for solving the discrete logarithm problem. The difficulty for anyone, even with the proxy key, to impersonate A to transform the encrypted message (i.e., to generate (r', s)) is the same as the one for solving the Diffie-Hellman problem. This scheme has several very appealing features. First, its security implies that it is hard for B to recover A's private key. In this sense, there is no need for A to trust B, and hence the scheme is non-commutative. Second, the proxy key .pi. generated is message-independent. B can use it to decrypt all the messages transformed by A. Third, this scheme satisfies the transitivity requirement. Upon receiving both the proxy key ir and the transformed message (r', s), the delegated user B can further delegate the proxy to another user C, by treating .pi. as the private key a and (r', s) as (r, s) and repeating the proxy generation and transformation. Fourth, the scheme requires less computational efforts than the re-encryption scheme. However, implementing proxy encryption in the manner of this scheme has several shortcomings. First, the proxy key contains no information about the delegated grantee B; it is solely derived from grantor A's private key. Moreover, the message decryption performed by B does not need B's private decryption key either. Consequently, the message can be recovered by anyone that gets hold of the proxy key and encrypted message, not necessarily B. Thus, B can ask anyone to decrypt the message by directly passing the proxy information. In many cases, this is not desirable; A should be able to specify the key holder who is to act on A's behalf. Second, the proxy key .pi. has to be a secret between A and B and needs to be transmitted from A to B in a secure manner. As a result of .pi. containing no information of B and (r', s) being possibly communicated in public, revealing .pi. is essentially equal to disclosing the message. Third, the proxy transformation has to be conducted by A. The value a' used in the transformation is a secret to A and it is vital to preventing B from knowing A's decryption key a. In short, the scheme is non-commutative and message-independent, but private and unable to specify the designated grantee. Blaze and Strauss have described another public-key proxy encryption scheme. As can be seen in FIG. 8, the scheme is similar in structure to ElGamal encryption, but with the parameters used differently and the inverse of the secret used to recover the message. Turning now to FIG. 8 in more detail, given a message m that needs to be sent to a grantor A with public key .alpha., the message m is encrypted by uniformly choosing a random number k.epsilon.Z*.sub.p-1 (step 810) and calculating a pair of numbers (r, s) representing the encrypted message (step 812) as follows: r=mg.sup.k (mod p) and s=.alpha..sup.k (mod p). To delegate the decryption right to a grantee B, the grantor A creates a proxy key .pi. by obtaining B's private decryption key b (step 814) and computing .pi.=a.sup.-1 b(mod(p-1)) (step 816), where a.sup.-1 is the inverse of the private key a of A modulo p-1. The proxy key ir can be made public. To use the proxy key .pi. to convert a message (r, s) encrypted for A to a message encrypted for B, the facilitator (not necessarily A, since the proxy key .pi. is public) computes s'=s.sup..pi. (mod p) (step 818). The pair (r, s') represents the transformed encrypted message, which can then be transmitted to B. To decrypt the transformed message, B computes m=r(s'.sup.b.sup..sup.-1 ).sup.-1 (mod p) (step 820), where b is B's private key and b.sup.-1 is the inverse of b modulo p-1. The scheme is correct, since in the message decryption s'.sup.b.sup..sup.-1 =g.sup.k (mod p) and m=r(g.sup.k).sup.-1 (mod p). The scheme is secure in that the message m and secret keys a and b cannot be recovered from the encrypted messages and public keys. Moreover, publishing the proxy key compromises neither the message m nor the secret keys a and b. More precisely, the problem of recovering m from the public information (.alpha., .beta., r, s, .pi., s') is as hard as the Diffie-Hellman problem. In contrast to the previous scheme, the last security feature makes it unnecessary to keep the proxy key .pi. private. Thus, the grantor A can publicly send .pi. to whoever (facilitator) is to perform the proxy transformation, or can simply publish it. Moreover, the scheme does not require any secret from A in order to carry out the proxy transformation, and consequently it allows anyone, trusted or not, to perform the transformation and hence eliminates the necessity of A's, as well as B's, presence in the transformation. Also unlike the previous scheme, there is no difference to the user B between decrypting a regular encrypted message and decrypting a proxy transformed message. This elegant feature allows the user B to treat all incoming encrypted messages uniformly. In fact, it is possible for an untrusted facilitator or server to perform the proxy transformation and then forward the message to the user B. In spite of these desirable features, this scheme is commutative; the involved key holders A and B must trust one another bilaterally. B can learn A's secret key a (by multiplying the proxy key by b.sup.-1). In addition, the proxy key is also message-independent, as it is in the previous scheme, which delegates B the right to decrypt all messages encrypted for A's private, key a. Accordingly, this scheme is public and message-independent but commutative. Two proxy encryption schemes according to the invention are presented herein, and then analyzed in regard to their security, commutativity and performance. Like the private proxy scheme, they are non-commutative, and at the same time, they support public proxy keys and transformations in the fashion the commutative proxy scheme does. However, they differ from the private and commutative schemes in that they are message dependent. Moreover, their overall performance is better than the ElGamal-based re-encryption scheme. Again, these schemes share the same scheme setup of the ElGamal scheme, and they assume that a grantor A delegates the decryption right to a grantee B. To understand how to adapt the ElGamal scheme into a proxy encryption scheme, it is helpful to examine some details of the ElGamal scheme. It should be noted that the r component of the encrypted message m is independent of the recipient A's private key a and public key a. As s=m.alpha..sup.k (mod p)=mg.sup.ka (mod p), a is only used in the s component, and a is implicitly embedded in s's exponent. Thus, it is sufficient for the proxy transformation to convert the message encrypted for A into the message encrypted for B by removing A's private key a from s and replacing it with B's private key b. In order to prevent B from obtaining A's private key a, the function to generate the proxy key must be somehow "one-way." Indeed, this can be achieved with aid of the random number k as follows: .pi.=g.sup.k(b-a) (mod p) Consequently, the proxy transformation that completes the message conversion should look like the following: s'=s.pi.(mod p)=mg.sup.ka g.sup.k(b-a) (mod p)=mg.sup.kb (mod p). The above discussion leads to the scheme in FIG. 9. It turns out that the proxy key and transformation satisfy the security requirement and provide desired being-public and non-commutativity features. Referring now to FIG. 9, given a message m that needs to be sent to a grantor A with public key a, the message m is encrypted by uniformly choosing a random number k.epsilon.Z*.sub.p-1 (step 910) and calculating a pair of numbers (r, s) representing the encrypted message (step 912) as follows: r=g.sup.k (mod p) and s=m.alpha..sup.k (mod p). To delegate the decryption right to a grantee B, grantor A creates a proxy key .pi. by obtaining B's authentic decryption key b (step 914) and calculating .pi.=r.sup.b-a (mod p) (step 916). The message is transformed from (r, s) to (r, s') by calculating s'=s.pi.(mod p) (step 918). The message m is then decrypted by B from (r, s') by computing m=s'(r.sup.b).sup.-1 (mod p) (step 920). Clearly, this scheme uses the message encryption and decryption steps of the ElGamal scheme. It is correct as the message m can be recovered from s'(r.sup.b).sup.-1 (mod p)=s.pi.(r.sup.b).sup.-1 (mod p)=mg.sup.ak g.sup.k(b-a) (g.sup.kb).sup.-1)(mod p)=m. A nice feature of this scheme is that, not only do regular and proxy encrypted messages appear no different to the grantee B, but also the scheme coincides with the ElGamal scheme when A and B are the same user with the same key; in this case, the proxy value .pi. is equal to 1 and the proxy transformation is the identity transformation. It is easy to see that the scheme is transitive. Upon receiving the proxy transformed message, the grantee B can act like the grantor A to further delegate the decryption right to, say, another grantee C by repeating the proxy generation step with the keys b and c in place of a and b. Also like the commutative scheme, the proxy generation step requires both A's and B's private keys in order to generate the proxy key .pi.. As an alternative, this step can be carried out by anyone that is trusted by both A and B. As noted above, A's private key is definitely needed, as otherwise anyone can issue a proxy key to recover the message and the underlying encryption scheme is not secure. To establish and communicate B's private key b, many key-exchange protocols such as the Diffie-Hellman key exchange may be used. As shown in further detail below, in some practical applications the requirement of the key b either is not a problem or can be relaxed. But unlike the private and commutative schemes, this scheme does not make it easy for the grantee B to decrypt messages encrypted for A other than the intended one. Clearly, the proxy key .pi. contains a piece of information that is specific to the encrypted message m, namely, the random number k. In this sense, the proxy scheme is message-dependent. Moreover, the scheme is non-commutative in the sense that it is hard for B to discover A's private key a. This fact, together with the performance of the scheme will be established after presenting the next scheme. Note that, in the previous scheme, the proxy transformation only changes the s component of the encrypted message. Since s is the part that actually carries the information about the message m, the scheme may not be efficient when m is a very long message. For example, the proxy key generated would be as long as the message and the effort spent in the proxy transformation would be linear with regard to the length of the entire message. The scheme presented in FIG. 10 tends to improve this situation. It uses the message encryption step of the commutative scheme in which the message m is shifted from s to r. Its proxy key and transformation now have no direct dependence on the message m. As shown in FIG. 10, given a message m that needs to be sent to a grantor A with public key a, the message m is encrypted by uniformly choosing a random number k.epsilon.Z*.sub.p-1 (step 1010) and calculating a pair of numbers (r, s) representing the encrypted message (step 1012) as follows: r=mg.sup.k (mod p) and s=.alpha..sup.k (mod p). To delegate the decryption right to a grantee B, grantor A creates a proxy key .pi. by obtaining B's authentic decryption key b (step 1014) and calculating .pi.=(s.sup.a.sup..sup.-1 ).sup.b-a (mod p) (step 1016), where a is the inverse of a.sup.-1 modulo p-1. The message is transformed from (r, s) to (r, s') by calculating s'=s.pi.(mod p) (step 1018). The message m is then decrypted by B from (r, s') by computing m=r(s'b.sup.-1).sup.-1 (mod p) (step 1020), where b.sup.-1 is the inverse of b modulo p-1. This scheme is correct since ##EQU8## Other properties of this scheme can be verified in the same way as the previous scheme. Due to their similarity in nature, only the first of the two new schemes is analyzed in this section in regard to its security and non-commutativity. An almost same discussion can be carried out for the second scheme. In addition, though the first scheme (as well as the second scheme) is transitive and its security may involve more than two key holders, the analysis to be given only considers the two-key-holder case; the general case is also similar. For presentation clarity, the phrase "(mod p)" will be omitted in this subsection; its occurrence should be clear from context. Recall that, other than the scheme parameters (p, g), the public information available from the scheme includes .pi.=g.sup.a, .beta.=g.sup.b, r=g.sup.k, s=mg.sup.ak, .pi.=g.sup.k(b-a), s'=mg.sup.bk. For the reasons set forth below, the scheme is computationally secure. It is hard to recover the message m and secret keys a and b from the public information, provided that the Diffie-Hellman and discrete-logarithm problems are hard to solve. Since the proxy key is part of the public information, this implies publishing it compromises neither the message nor the secret keys. A consequence of this is that it is also hard for anyone to forge a valid proxy key in a systematic manner. Beyond that, the scheme is shown to be non-commutative in the sense that even with B's private key, it is still hard to recover A's private key. If the proxy key is indeed generated by a third party trusted by both A and B, this fact implies that it is not necessary for B to trust A either. This is a significant improvement over the commutative scheme. Moreover, as stated above, the proxy encryption schemes of the invention are more efficient than re-encrypting a message. Below, in Table 2, is the performance of the two proxy encryption schemes according to the invention described herein compared with the re-encryption scheme using the ElGamal algorithm, in terms of the amount of computation they require. In Table 2, the numbers of multiplication operations, exponentiation operations, and inversions, all performed modulo p, are listed for these schemes.
TABLE 2
First Scheme Second Scheme
Re-Encryption (FIG. 9) (FIG. 10)
Operations mult. exp. inv. mult. exp. inv. mult. exp. inv.
Encryption 1 (.times.2) 2 (.times.2) 0 (.times.2) 1 2 0
1 2 0
Proxy Key Gen. 0 1 0 0/1 2/1 1/0
Transformation 1 0 0 1 0 0
Decryption 1 (.times.2) 1 (.times.2) 1 (.times.2) 1 1 1
1 1 2/1
Total 4 6 2 3 4 1 3/4 5/4 3/1
Note that the total number of operations for re-encryption using the ElGamal scheme is twice the number of operations for a single ElGamal encryption and decryption, since the message must first be encrypted, then decrypted, then re-encrypted, then re-decrypted. Moreover, the computation in the second scheme can be optimized by (i) pre-computing the inverses a.sup.-1 and b.sup.-1 in the scheme setup step and (ii) multiplying the two exponential components (modulo (p-1)) in the proxy generation step instead of using two exponentiations. The second set of numbers under the second scheme result from this optimization. Overall, the inventive proxy encryption schemes presented herein have better performance than the simple, ElGamal-based re-encryption scheme. Applications Public and non-commutative proxy encryption schemes provide a key mechanism for implementing a wide range of applications. Massive document distribution and file protection are two key motivations for this disclosure. These applications correspond to two typical situations for proxy encryption. The former is related to the case where the grantor is the one who encrypts the message at the first place, while the latter is to self-delegation in which the grantor and grantee are the same key holder but with different keys. Again, note that a document refers to any digital file whose content could text, graphics, audio, video, executable or even multi-media. Usually, a document is large in size, even after compression. Because public-key algorithms tend to be very slow when compared with conventional private-key algorithms such as DES, IDEA and RC4, and private-key algorithms require establishing secret keys to begin with, the most practical approach to massive and secure distribution of documents over networks is to combine the private-key and public-key encryption mechanisms. Typically, an efficient private-key algorithm is used to encrypt the document by using a randomly generated key, called the session key, and the public key for each document recipient is used to encrypt this session key. Recipients use their private keys to recover the secret session key and then use it to decrypt the document. Indeed, the above document distribution approach has the proxy encryption flavor; the owner encrypts the document first using a private-key scheme and then grants the decryption right, upon request, to its recipients via a public-key scheme. It turns out that, either one of the two new proxy encryption schemes can be used to combine the best features of the approach into a single, normal encryption scheme. Take the second scheme set forth above (FIG. 10), for example. Two observations are in order. First, the component r of the encrypted message can be generated using any private-key encryption scheme with K=g.sup.k (mod p) as the secret session key. Accordingly, the message m can be recovered in the message decryption step by its corresponding private-key decryption using the secret session key K'=s'b.sup.-1 (mod p)=K. In fact, the secret-key encryption scheme used in the scheme is r=E.sub.K (m)=mK(mod p) for encryption and m=D.sub.K' (r)=rK'.sup.-1 (mod p) for decryption. Another simple example is the encryption scheme based on bit-wise XOR (E)). In this case, the computation of r and m can be replaced by r=E.sub.K (m)=m.sym.K and m=D.sub.K (r)=r.sym.K. Certainly, more sophisticated private-key encryption schemes such as DES and triple-DES can be employed if stronger security is needed. The second observation is that, if the grantor A is the one who encrypts the message m, then A can keep the random number k private and use B's public key .beta.=g.sup.b (mod p), instead of B's private key b, to generate the proxy key: .pi.=(.beta..alpha..sup.-1).sup.k (mod p), where .alpha. is A's public key. This eliminates the requirement for B's private key b (or key exchange between A and B), and implies that B does not have to trust A, either. These two observations-lead to the document distribution scheme shown in FIG. 11, which is based on the second proxy encryption scheme according to the invention set forth above (and in connection with FIG. 10). In the scheme, a private-key encryption scheme is used to encrypt the message just once for all recipients, while a less expedient proxy-key portion is used to encrypt a small amount of information--the session key--customized once for each recipient. A beneficial feature of this scheme is that the encrypted document can be stored in a publicly accessible repository, and the proxy transformation can be performed by the document owner A, the recipient B, or the repository where the document is physically stored, depending upon the needs of real document management and distribution systems. Referring now to FIG. 11, the scheme is set up the same way as a standard ElGamal scheme (see FIG. 6, described above). In addition, a symmetric, private-key encryption scheme is selected (step 1110). Its encryption function is m.vertline..fwdarw.E.sub.K (m) and decryption function is r.vertline..fwdarw.D.sub.K (r), where K is some private key. To encrypt a document m, owner A first chooses a uniformly random number k.epsilon.Z*.sub.p-1 (step 1112) and calculates a session key K=g.sup.k (mod p) (step 1114). The encrypted document (r, s) is then calculated as follows: r=E.sub.K (m) and s=K.sup.a (mod p). (step 1116), where a is A's private key. A keeps the pair (s, k) private. Upon request from a recipient B for the encrypted document (r, s), A first obtains B's authentic public key .beta. (step 1118) and retrieves k from the pair (s, k) (step 1120). A then computes .pi..sub.B =.beta..sup.k s.sup.-1 (mod p) (step 1122), where s.sup.-1 is the inverse of s modulo p, as the proxy key for B. The document is then transformed by computing s'=s.pi..sub.B (mod p) (step 1124); the pair (r, s') represents the transformed document customized for B. To decrypt the customized document (r, s') and retrieve the original document m, B first recovers the session key by calculating K=s'.sup.b.sup..sup.-1 (mod p) (step 1126), where b.sup.-1 is the inverse of b modulo p-1. Then the document itself is decrypted by calculating m=D.sub.K (r) (step 1128). As described above, an adaptation of the present invention is also applicable to a file protection application. Usually, file protection in insecure systems such as laptops and networked hardware involves long-term encryption of files. Thus, encryption keys used for file encryption have much longer lifetimes than their communication counterparts. While a user's primary, long-term, secret key may be the fundamental representation of a network identity of the user, there is a danger that it might get compromised if it is used for many files over a long period of time. If the primary key is lost or stolen, not only are contents of the files encrypted with it disclosed, but also the user loses personal information based on the key such as credit card account, social security number, and so on. Therefore, it is often preferable to use an on-line method in which a new decryption key is derived from the primary key every time a file needs to be encrypted and gets updated on a regular basis. With the proxy encryption schemes set forth herein, new decryption keys can be generated and constantly updated through self-delegation to keep them fresh. Once a new key is created and a corresponding proxy key generated, the old secret key can be destroyed, with the new key and proxy key maintaining the ability to decrypt the file. FIG. 12 shows a file protection scheme that uses a smart card to store and update decryption keys. It is again based on the second proxy encryption scheme presented herein, as illustrated in FIG. 10. As shown in FIG. 12, to encrypt a file m, a processor embedded in a smart card chooses a random number k.epsilon.Z*.sub.p-1 (step 121(0) and computes r=mg.sup.k (mod p) and s=(g.sup.k).sup.a (mod p) (step 1212), where a is the smart card's private key. The pair (r, s) represents the file m in encrypted form. Whenever necessary or desired, for example every few weeks or after a predetermined number of document accesses, the smart card generates another uniform random number a'.epsilon.Z*.sub.p-1 (step 1214) and computes s'=(s.sup.a.sup..sup.-1 ).sup.a' (mod p) (step 1216), where a.sup.-1 is the multiplicative inverse of a modulo p-1. The encrypted file (r, s) is then replaced with (r, s') (step 1218), and the decryption key a is replaced with a new decryption key a' (step 1220). These steps 1214-1220 can be repeated as many times as desired. To recover the original file m from its encrypted version (r, s), the processor on the smart card uses the latest decryption key a to compute m=rs.sup.a.sup..sup.-1 (mod p) (step 1222). Note that the file encryption step can start with any secret key it generates, not necessarily the smart card's private key. To keep encrypted files fresh by updating encryption data with a piece of smart-card-generated information helps to maintain single useful copies of protected files. This, in some sense, provides copy protection as well. Moreover, the non-commutativity of the scheme renders previous copies of the files useless, as the corresponding secret information stored in the smart card has been changed (and preferably destroyed). Proxy Encryption Using the Cramer-Shoup Cryptosystem Although the foregoing examples and algorithms all employ various adaptations of the ElGamal cryptosystem, it should be noted that other cryptosystems can also be adapted by a scheme according to the invention. For example, the Cramer-Shoup public-key cryptosystem is a recently proposed cryptosystem that is the first practical public-key system to be provably immune to the adaptive chosen ciphertext attack. See R. Cramer and V. Shoup, "A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack," Proceedings of CRYPTO 98, Springer Verlag LNCS, vol. 1462, pp. 13-25 (1998). The adaptive chosen ciphertext attack assumes that the attacker can obtain decryptions of any chosen ciphertexts other than the target ciphertext. For example, if the target ciphertext for which the plaintext is wanted is c, then the attacker is assumed to have access to a "decryption oracle" which will decrypt any ciphertext except c, including for example c+1, 4c, etc. RSA and ElGamal fall easily to this kind of attack. A different, but equivalent, notion of security against active attacks is called non-malleability; however, known non-malleable systems are not practical. Set forth below in FIG. 13 is a description of a hash-free version of the Cramer-Shoup cryptosystem, the security of which is based strictly on the Diffie-Hellman decision problem for an arbitrary group. Thereafter, how to delegate the right to decrypt in a Cramer-Shoup scheme will be illustrated in two different situations. Referring initially to FIG. 13, the system is set up by choosing G as a group of prime order q, where q is large (step 1310). The system assumes that cleartext messages are (or can be encoded as) elements of G, and ciphertext messages are elements of G.sup.4 =G.times.G.times.G.times.G; that is, a ciphertext message is four times as long as its corresponding plaintext message. A good example of the group G is the subgroup of order q in the multiplicative set Z*.sub.p for some large prime p=2q+1. In this case, a message m from the set {1, . . . , q} can be "encoded" by squaring it modulo p, resulting in an element in G, and the message m can be recovered from its encoding by computing the unique square root of its encoding modulo p, in the set {1, . . . , q}. A key is generated as follows. First, random elements g.sub.1,g.sub.2 .epsilon.G are chosen (step 1312), and random elements x.sub.1,x.sub.2,y.sub.11,y.sub.12,y.sub.21,y.sub.22,y.sub.31,y.sub.32, z.epsilon.Z.sub.q are chosen (step 1314). Next, the group elements c=g.sub.1.sup.x.sup..sub.1 g.sub.2.sup.x.sup..sub.2 , d.sub.1 =g.sub.1.sup.y.sup..sub.11 g.sub.2.sup.y.sup..sub.12 , d.sub.2 =g.sub.1.sup.y.sup..sup.21 g.sub.2.sup.y.sup..sub.22 , d.sub.3 =g.sub.1.sup.y.sup..sub.31 g.sub.2.sup.y.sup..sub.32 , and h=g.sub.1.sup.z are computed (step 1316). The public key is then calculated to be (g.sub.1,g.sub.2,c,d.sub.1,d.sub.2,d.sub.3,h) (step 1318) and the private key is calculated to be (x.sub.1,x.sub.2,y.sub.11,y.sub.12,y.sub.21,y.sub.22,y.sub.31,y.sub.32,z) (step 1320). Given a message m.epsilon.G, the encryption method begins by choosing r.epsilon.Z.sub.q at random (step 1322). Then the ciphertext (u.sub.1,u.sub.2,e,v) is calculated as follows (step 1324): u.sub.1 =g.sub.1.sup.r, u.sub.2 =g.sub.2.sup.r, e=h.sup.r m, and v=c.sup.r d.sub.1.sup.u.sup..sub.1 .sup.r d.sub.2.sup.u.sup..sub.2 .sup.r d.sub.3.sup.er. Given the ciphertext (u.sub.1,u.sub.2,e,v), the corresponding decryption algorithm first tests if v=u.sub.1.sup.x.sup..sub.1 .sup.+u.sup..sub.1 .sup.y.sup..sub.11 .sup.+u.sup..sub.2 .sup.y.sup..sub.21 .sup.+ey.sup..sub.31 u.sub.2.sup.x.sup..sub.2 .sup.+u.sup..sub.1 .sup.y.sup..sub.12 .sup.+u.sup..sub.2 .sup.y.sup..sub.22 .sup.+ey.sup..sub.32 (step 1326). If not, the decryption effort is rejected (step 1328). Otherwise, the message m is calculated as m=e/u.sub.1.sup.z (step 1330). The correctness of a cryptosystem can be verified by checking that the decryption of an encryption of a message yields the message. In this case, since u.sub.1 =g.sub.1.sup.r and u.sub.2 =g.sub.2.sup.r, one has u.sub.1.sup.x.sup..sub.1 u.sub.2.sup.x.sup..sub.2 =g.sub.1.sup.rx.sup..sub.1 g.sub.2.sup.rx.sup..sub.2 =c.sup.r. Likewise, u.sub.1.sup.x.sup..sub.1 .sup.+u.sup..sub.1 .sup.y.sup..sub.11 .sup.+u.sup..sub.2 .sup.y.sup..sub.21 .sup.+ey.sup..sub.31 u.sub.2.sup.x.sup..sub.2 .sup.+u.sup..sub.1 .sup.y.sup..sub.12 .sup.+u.sup..sub.2 .sup.y.sup..sub.22 .sup.+ey.sup..sub.32 =c.sup.r d.sup.u.sup..sub.1 .sup.r d.sub.2.sup.u.sup..sub.2 .sup.r d.sub.3.sup.er u.sub.1.sup.z =h.sup.r. Therefore, for the valid ciphertext, the test performed in the decryption algorithm will pass. The security of this cryptosystem relies upon the difficulty in solving the Diffie-Hellman decision problem. An algorithm that solves the Diffie-Hellman decision problem is a statistical test that can effectively distinguish the following two distributions: (a) random quadruples (g.sub.1,g.sub.2,u.sub.1,u.sub.2).epsilon.G.sup.4, and (b) random quadruples (g.sub.1,g.sub.2,u.sub.1,u.sub.2).epsilon.G.sup.4,where g.sub.1, g.sub.2 are random and u.sub.1 =g.sub.1.sup.r and u.sub.2 =g.sub.2.sup.r for some random r.epsilon.Z.sub.q. Related to the Diffie-Hellman decision problem are the Diffie-Hellman problem (given g, g.sup.x, and g.sup.y, compute g.sup.xy), and the discrete logarithm problem (given g and g.sup.x, compute x). Within polynomial time, the Diffie-Hellman decision problem can be reduced to the Diffie-Hellman problem which in turn can be reduced to the discrete logarithm problem. It is this relationship between the three problems that leads to the possibility of delegating the right to decrypt for the Cramer-Shoup system. Assume that someone wants to delegate the right to decrypt from a delegator (Alice, A) to a delegatee (Bob, B). Suppose that Alice has the public key (g.sub.1,g.sub.2,c,d.sub.1,d.sub.2,d.sub.3,h) and the private key (x.sub.1,x.sub.2,y.sub.11,y.sub.12,y.sub.21,y.sub.22,y.sub.31,y.sub.32,z), and that Bob has the public key (g'.sub.1,g'.sub.2,c',d'.sub.1, d'.sub.2,d'.sub.3,h') and the private key (x'.sub.1,x'.sub.2,y'.sub.11,y'.sub.12,y'.sub.21,y'.sub.22,y'.sub.31,y'. sub.32,z') Recall, that for a given plaintext message m.epsilon.G, the ciphertext message for delegator A is M=(u.sub.1,u.sub.2,e,v), where u.sub.1 =g.sub.1.sup.r, u.sub.2 =g.sub.2.sup.r, e=h.sup.r m, and v=c.sup.r d.sub.1.sup.u.sup..sub.1 .sup.r d.sub.2.sup.u.sup..sub.2 .sup.r d.sub.3.sup.er. Similarly, if the message m is directly encrypted for the delegatee B, the ciphertext message is M'=(u'.sub.1,u'.sub.2,e',v'), where u'.sub.1 =g'.sub.1.sup.r', u'.sub.2 =g'.sub.2.sup.r', e'=h'.sup.r' m, and v'=c'.sup.r' d'.sub.1.sup.u'.sup..sub.1 .sup.r' d'.sub.2.sup.u'.sup..sub.2 .sup.r' d'.sub.3.sup.e'r', where r' is also a random number from Z.sub.q. Note further that v=(cd.sub.1.sup.u.sup..sub.1 d.sub.2.sup.u.sup..sub.2 d.sub.3.sup.e).sup.r and v'=(c'd'.sub.1.sup.u.sup..sub.1 d'.sub.2.sup.u.sup..sub.2 d'.sub.3.sup.e').sup.r'. Based on the ideas set forth above, to delegate the right to decrypt from A to B involves generating a transfer key .pi., using that transfer key to transform M into M'. In the following, it is assumed that the components g'.sub.1, g'.sub.2 of B's public key are identical to the components g.sub.1,g.sub.2 of A's public key (analogously to the ElGamal system parameters described above). Also, it is assumed that the random number r' is the same as r. Under these two assumptions, elements u'.sub.1,u'.sub.2 of B's ciphertext message are the same as elements u.sub.1,u.sub.2 of A's ciphertext message. Referring now to FIG. 14, the system is set up by choosing G as a group of prime order q, where q is large (step 1410). Then, as above, key is generated as follows. First, random elements g.sub.1,g.sub.2.epsilon.G are chosen (step 1412), and random elements x.sub.1,x.sub.2,y.sub.11,y.sub.12,y.sub.21,y.sub.22,y.sub.31,y.sub. 32,z.epsilon.Z.sub.q are chosen (step 1414). Next, the group elements c=g.sub.1.sup.x.sup..sub.1 g.sub.2.sup.x.sup..sub.2 , d.sub.1 =g.sub.1.sup.y.sup..sub.11 g.sub.2.sup.y.sup..sub.12 , d.sub.2 =g.sub.1.sup.y.sup..sub.21 g.sub.2.sup.y.sup..sub.22 , d.sub.3 =g.sub.1.sup.y.sup..sub.31 g.sub.2.sup.y.sup..sub.32 , h=g.sub.1.sup.z are computed (step 1416). The public key is then calculated to be (g.sub.1,g.sub.2,c,d.sub.1,d.sub.2,d.sub.3,h) (step 1418) and the private key is calculated to be (x.sub.1,x.sub.2,y.sub.11,y.sub.12,y.sub.11,y.sub.22,y.sub.31,y.sub.32,z) (step 1420). Given a message m.epsilon.G, the encryption method begins by choosing r.epsilon.Z.sub.q at random (step 1422). Then the ciphertext (u.sub.1,u.sub.2,e,v) is calculated as follows (step 1424): u.sub.1 =g.sub.1.sup.r, u.sub.2 =g.sub.2.sup.r, e=h.sup.r m, and v=c.sup.r d.sub.1.sup.u.sup..sub.1 .sup.r d.sub.2.sup.u.sup..sub.2 .sup.r d.sub.3.sup.er. If B's private key is available for generating the transfer key ir, that key is obtained (step 1426) and then .pi. can be calculated (step 1428) as follows: .pi.(.epsilon.,.theta.,.delta..sub.1,.delta..sub.2.delta..sub.3) where .epsilon.=e'/e=g.sub.1.sup.(z'-z)r =u.sub.1.sup.z'-z .theta.=c'.sup.r /c.sup.r =g.sub.1.sup.x'.sup..sub.1 .sup.-x.sup..sub.1 .sup.)r g.sub.2.sup.(x'.sup..sub.2 .sup.-x.sup..sub.2 .sup.)r =u.sub.1.sup.x'.sup..sub.1 .sup.-x.sup..sub.1 u.sub.2.sup.x'.sup..sub.2 .sup.-x.sup..sub.2 .delta..sub.1 =d'.sub.1.sup.r /d.sub.1.sup.r =u.sub.1.sup.y'.sup..sub.11 .sup.y.sup..sub.11 u.sub.2.sup.y'.sup..sub.12 .sup.-y.sub.12 .delta..sub.2 =d'.sub.2.sup.r /d'.sub.2.sup.r =u.sub.1.sup.y'.sup..sub.21 .sup.-y.sup..sub.21 u.sub.2.sup.y'.sup..sub.22 .sup.-y.sup..sub.22 .delta..sub.1 =d'.sub.3.sup..epsilon.r /d.sub.3.sup..epsilon.r u.sub.1.sup.y'.sup..sub.31 .sup..epsilon.-y.sup..sub.31 u.sub.2.sup.y'.sup..sub.32 .sup..epsilon.-y.sup..sub.32 The ciphertext transformation is then u'.sub.1 =u.sub.1, u'.sub.2 =u.sub.2, e'=e.epsilon., and v'v.theta..delta..sub.1.sup.u.sup..sub.1 .delta..sub.2.sup.u.sup..sub.2 .delta..sub.3.sup.e. This transforms the ciphertext (u.sub.1, u.sub.2,e,v) into (u.sub.1,u.sub.2,e',v') (step 1430). The recipient/delegatee is then able to decrypt the transformed cyphertext (u.sub.1,u.sub.2,e',v'). As above, the decryption algorithm first tests if v'=u'.sub.1.sup.x'.sup..sub.1 .sup.+u'.sup..sub.1 .sup.y'.sup..sub.11 .sup.+u'.sup..sub.2 .sup.y'.sup..sub.21 .sup.+e'y'.sup..sub.31 u'.sub.2.sup.x'.sup..sub.2 .sup.+u'.sup..sub.1 .sup.y'.sup..sub.12 .sup.+u'.sup..sub.2 .sup.y'.sup..sub.22 .sup.+e'y'.sup..sub.32 (step 1432). If not, the decryption effort is rejected (step 1434). Otherwise, the message m is calculated as m=e'/u'.sub.1.sup.z' (step 1436). In the case where only the public key of the delegatee B can be used for delegating the right to decrypt the message from the delegator A to B, one needs to save and use the random number r used initially in encrypting the message for A. This may be a problem where the party to generate the transfer key is not A, and may not be a problem if the party is, in fact, A. In any case, if it is available, the transfer key .pi. can be generated using B's public key as follows: .pi.=(.epsilon.,.theta.,.delta..sub.1,.delta..sub.2,.delta..sub.3) where .epsilon.=e'/e=(g.sub.1.sup.z' /g.sub.1.sup.z).sup.r =(h'/h).sup.r .theta.=c'.sup.r /c.sup.r =(c'/c).sup.r .delta..sub.1 =d'.sub.1.sup.r /d.sub.1.sup.r =(d'.sub.1 /d.sub.1).sup.r .delta..sub.2 =d'.sub.2.sup.r /d.sub.2.sup.r =(d'.sub.2 /d.sub.2).sup.r .delta..sub.1 =d'.sub.3.sup..epsilon.r /d.sub.3.sup..epsilon.r =(d'.sub.3.sup..epsilon. /d.sub.3).sup.r The proxy transformation is then u'.sub.1 =u.sub.1, u'.sub.2 =u.sub.2, e'=e.epsilon., and v'=v.theta..delta..sub.1.sup.u.sup..sub.1 .delta..sub.2.sup.u.sup..sub.2 .delta..sub.3.sup.e. It is straightforward to verify, in either case, that the delegates B can use his own private key to decrypt the ciphertext (u'.sub.1,u'.sub.2,e',v') transformed by the methods set forth above. Since the mechanisms used herein on the Cramer-Shoup cryptosystem are the same as those used above on ElGamal-like cryptosystems, they are public and non-=commutative, assuming the Diffie-Hellman problem and the discrete logarithm problem t are difficult to solve. As described above, through enhancing common public-key encryption schemes with the proxy encryption capability, it becomes possible to support flexible designated decryption. This disclosure has presented two public and non-commutative proxy encryption schemes, which have inherited the merits of the existing schemes and discarded their shortcomings. The new schemes have been shown to have direct applications to massive document distribution and file protection. The basic idea of these new schemes has also been applied to cryptosystems of other types such as the Cramer-Shoup cryptosystem, enhancing them into proxy encryption schemes. While the various aspects of the present invention have been described with reference to several aspects and their embodiments, those embodiments are offered by way of example, not by way of limitation. The foregoing detailed description of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and obviously many modifications and variations are possible in light of the above teaching. The described embodiments were chosen in order to best explain the principles of the invention and its practical applications to thereby enable others skilled in the art to best utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. Those skilled in the art will be enabled by this disclosure will be enabled by this disclosure to make various obvious additions or modifications to the embodiments described herein; those additions and modifications are deemed to lie within the scope of the present invention. It is intended that the scope of the invention be defined by the claims appended hereto.
|
Same subclass Same class Consider this |
||||||||||