Abstract:
The present invention discloses a software-based commercial key escrow system (KES) for the PKI environment that enables an entity such as the court to monitor communications of users suspected of unlawful activities while protecting the privacy of law-abiding users.  
     The present invention provides a key escrow system providing a PKI-roaming service and the perfect forward secrecy to the key management agent (KMA).

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates generally to the cryptosystems and more particularly to a forward-secure commercial key escrow system that is interoperable with the PKI (Public Key Infrastructure) environment. More specifically, the present invention relates to a forward-secure commercial key escrow system that enables a given entity to monitor communications of users suspected of unlawful activities while protecting the privacy of law-abiding users.  
         DESCRIPTION OF THE RELATED ART  
         [0002]    A rapid growth of digital communication over internet have resulted in the development of information technology, Network security and particularly cryptographic technology. Cryptographic technology is widely used to ensure the privacy and authentication of messages communicated over insecure channels such as internet.  
           [0003]    Cryptography can be used to protect the confidentiality of information by limiting access to the plain text data.  
           [0004]    It has many advantages of using cryptography in electronic commerce and contracts over the internet for privacy and user authentication. But, the following problems may arise from the encryption key management.  
           [0005]    First of all, a genuine user himself might not be able to access his information due to the loss or the damage of the decryption key.  
           [0006]    Secondly, from the aspect of a company, there is a latent threat that can be caused by the misuse of the cryptosystem. For example, a rogue employee may encrypt the critical information of a company and then request money for releasing the decryption key.  
           [0007]    Finally, from the aspect of a government, it sometimes happens that the government needs to have the right of an access to a key or plaintext with legal reasons such as the criminal investigation. Actually, the suspect can disturb the legal investigation by encrypting the information that has a relation to the crime.  
           [0008]    The problems of the user&#39;s aspect can be solved if a commercial KES that provides services such as key-backup is used.  
           [0009]    Furthermore, the second issue from the aspect of a company or a government can be solved if a mandatory KES is employed as a security policy.  
           [0010]    Many countermeasures such as lawful restriction for the usage of a cryptosystem with a hidden trapdoor have been studied to prevent the cryptographic side effects. Among them the KES is a typical solution.  
           [0011]    In general, the key escrow system can be defined as a cryptosystem that allows an authorized person to retrieve the decryption key under the pre-determined condition.  
           [0012]    Here, the predetermined condition means user&#39;s request for the description key when a desirable KES (Key Escrow System) satisfy the opposite features between protecting user&#39;s privacy and guaranteeing law enforcement. But practically, it is not an easy task to fulfill these requirements at the same time.  
           [0013]    As a prior art in the field of the key escrow system for the PKI environment, the KES technologies from Netscape, VeriSign, and Entrust have been disclosed. They are very popular PKI-based key escrow system. The detailed descriptions of the above-mentioned company&#39;s KES technology will be provided in the following in order to understand the shortcomings of the prior art.  
           [0014]    First of all, let us summarize the meaning of the terminology used in the conventional KES. The user is defined as an entity using PKI-based commercial key escrow system. The registration authority, which is abbreviated as RA, is a server that registers or vouch for the identity of users to a CA that then issues certificates.  
           [0015]    The certification authority, which is called as CA in short, is a server that manages certificates for encryption and authentication.  
           [0016]    The key management agent (KMA), is a trusted server coordinating the key recovery agents (KRA). The KRA is a server or an administrator to provide a key recovery information to a KMA.  
           [0017]    [0017]FIG. 1A is a schematic diagram illustrating the workflow of the Netscape&#39;s certificate management system (CMS) for a commercial key escrow system as a prior art. The detailed description of the Netscape&#39;s CMS can be found in the Netscape certificate management system administrator&#39;s guide version 4.1 (http://docs.iplanet.com/docs/manuals/cms/41/adm_guid e/contents.html).  
           [0018]    Referring to FIG. 1A, the user  10  generates an encryption key pair (S A , P A ). Further, the user encrypts a private key (S A ) with the public key (P KMA ) of the KMA, which is called as data recovery manager by Netscape, and sends the encrypted key E P     KMA    (S A ) as well as the user&#39;s public key (P A ) to the RA  11  (step S 100 ).  
           [0019]    Thereafter, the RA forwards the user&#39;s encrypted key E P     KMA   (S A ) together with the user&#39;s public key (P A ) to the KMA  13  for requesting the key escrow (step S 101 ).  
           [0020]    Now, the KMA  13  decrypts the encrypted key E P     KMA    (S A ) with the KMA&#39;s private transport key (S KMA ), and checks that the user&#39;s private key (S A ) corresponds to the user&#39;s public key P A .  
           [0021]    Then the KMA encrypts the user&#39;s private key S A  with the KMA&#39;s storage key (P′ KMA ) and stores the encrypted key in its internal database  17  (step S 102  ).  
           [0022]    Once user&#39;s private key has been successfully stored, the KMA digitally signs a token confirming that the key has been successfully stored.  
           [0023]    The KMA&#39;s private key for storage is reserved in a software or hardware token and is protected by a PIN code.  
           [0024]    The KMA  13  splits the PIN into n pieces with (m, n)-secret sharing scheme and then stores them encrypted with the passwords of n KRAs  14 ,  15 ,  17 , respectively.  
           [0025]    Referring to FIG. 1A again, the KMA  13  sends a digitally signed token with the KMA&#39;s private transport key to the RA  11 . The signed token means that the escrow of the user&#39;s private key (S A ) has been successfully completed (step S 104  ).  
           [0026]    Thereafter, the RA  11  verifies the signed token and sends the certificate request to the CA  12  (step S 105 ). The CA  12  issues and returns the encryption certificate to RA  11  (step S 106 ), which is forwarded to the user  10  (step S 107 ).  
           [0027]    [0027]FIG. 1B is a schematic diagram illustrating the key recovery process from the Netscape&#39;s CMS. Referring to FIG. 1B, when the user  10  requests that KMA recover his or her private key, KMA subjects the request to its policy checks (step S 120 ).  
           [0028]    If the request passes all the policy rules, the KMA  13  sends a confirmation messages to n KRAs  14 ,  16  (step S 121 ).  
           [0029]    After verifying the confirmation, the KRAs then send their individual identifiers and passwords PSWD 1 , PSWD 2 , . . . , PSWD n  to the KMA  13  (step S 122 ). After the verification process of checking if the required number of KRAs send their passwords, the KMA constructs the PIN for accessing the private key repository with the passwords of KRAs.  
           [0030]    The KMA  13  retrieves the user&#39;s encrypted private key from its key repository and decrypts it with the private component of the storage key pair. Finally, the KMA securely sends the recovered private key to the user  10  (step S 123 ).  
           [0031]    [0031]FIG. 2A is a schematic diagram illustrating the key escrow process of the VeriSign&#39;s Key Management Service product. More detailed information can be referred in a document “Onsite key management service administrator&#39;s guide (http://www.verisign.com)” 
           [0032]    The feature of the VeriSign&#39;s key escrow system is that both the private key and the KMA  13  generate user&#39;s encryption key pair, which is called a key manager in the literature.  
           [0033]    Referring to FIG. 2A, once the user  10  requests the certificate for encryption (step S 130 ), the RA  11  forwards the request to the KMA  13  (step S 131 ). The KMA  13  generates an encryption key pair as well as a unique triple DES key for the user.  
           [0034]    Thereafter, the KRR (Key Recovery Record) and the KRB (Key Recovery Block) are constructed as follows.  
           [0035]    Preferably, the KRR is constructed from the relation KRR=E k (PRI), and the KRB from the relation KRB=Ε P     KRA    (K) where k is a triple DES Key, and PRI is the private key of the user while P KRA  is the public key of the KRA  14 . A KRB is the symmetric key encrypted using KRA&#39;s public key(triple DES key).  
           [0036]    Additionally, the KMA  13  stores the created KRR and KRB in the database  17  together with the user&#39;s identifier and then the triple DES key is destroyed. Moreover, the KMA  13  sends the certificate request of the user to the CA  12  (step S 133 ).  
           [0037]    Consequently, the CA  12  sends the encryption certificate to the KMA  13  (step S 134 ). Thereafter, the KMA  13  sends the private key for encryption and the certificate to the user  10  securely(step S 135 ). Then, the KMA  13  destroys the private key of the user.  
           [0038]    [0038]FIG. 2B is a schematic diagram illustrating the key recovery process of VeriSign&#39;s KMS product. Referring to FIG. 2B, when the user  10  requests that the KMA  13  recover his or her private key, the KMA  13  retrieves the KRB of the user from the database (step S 141 ). Optionally, an organization may use two PINs (called “Emergency Recovery Codes”) , and thereby the level of security is enhanced from the requirement of the existence of a couple of KMA&#39;s administrators.  
           [0039]    The retrieved KRB and the request for key recovery are transmitted to the KRA  14  (step S 142 ). The KRA verifies if the KRB is valid and matches with two PINs. The KRA  14  then decrypts the KRB to recover the embedded triple-DES Key to decrypt the encrypted private key.  
           [0040]    The KRA  14  returns the decrypted triple DES key to the KMA  12  (step S 143 ). Thereafter, the KMA  13  decrypts the KRR (the encrypted private key) with the received triple DES key to recover the user&#39;s private key and then sends it to the user (step S 144 ).  
           [0041]    [0041]FIG. 3A is a schematic diagram illustrating the key escrow system of Entrust Corporation. The Entrust&#39;s key escrow system (KES) is described at “Administering Entrust/PKI 5.0 on UNIX” 
           [0042]    Referring to FIG. 3A, the user sends a request for the encryption certificate to the RA  11  (step S 150 ). The RA  11  then forwards the request to the CA  12  (step S 151 ).  
           [0043]    Now, the CA  12  generates the user&#39;s key pair upon the request. Furthermore, the CA  12  is responsible for the issuance of the encryption certificate.  
           [0044]    The user  10 &#39;s encryption key pair and the certificate are encrypted either with CAST-128 or with 3-DES, which are to be stored in the database  17  (step S 152 ). In the meanwhile, the CA  12  forwards the user&#39;s private key and certificate to the user  10  via the RA  11  (step S 153 , S 154 ).  
           [0045]    [0045]FIG. 3B is a schematic diagram illustrating the key escrow process of Entrust&#39;s KES. Referring to FIG. 3B, the user requests the key recovery to the RA  11  (step S 160 ), and then the RA  11  forwards the request to the CA  12  (step S 161 ).  
           [0046]    The CA  12  retrieves the encrypted private key of the user from the database  17  and decrypts the user&#39;s encrypted private key (step S 162 ).  
           [0047]    For the recovery of the encrypted private key at the step of S 162 , the passwords of the operating managers are needed and the number of operating managers participating in the recovery process of the escrowed key can be suitably chosen in accordance with the security policy.  
           [0048]    Finally, the CA  12  forwards the decrypted private key to the user through the RA (step S 163 , S 164 ).  
           [0049]    As far as the user&#39;s privacy is concerned, the traditional commercial key escrow system proposed by either VeriSign or Entrust, however, have shortcomings in common. Namely, the user&#39;s private key for encryption is inevitably exposed to a third party at the initial step of generating a key in accordance with the prior art.  
           [0050]    This is because anyone among the group of the user, the KMA, and the CA is capable of generating the user&#39;s key pair (including user&#39;s private key) according to the prior art.  
           [0051]    Additionally, traditional KES (key escrow system) disclosed by VeriSign and/or Entrust is not practically applicable because the user&#39;s private key is not securely managed. For instance, the security of the user&#39;s private key relies on the KMA and/or the CA in case when either the KMA or the CA generates the user&#39;s private key.  
           [0052]    Additionally, the KES disclosed by Netscape Corporation still has the similar problem because the KMA encrypts the user&#39;s private key with the KMA&#39;s transport key in order to verify the correspondence between the escrowed private key and the public key, which means that the user&#39;s private key is inevitably exposed to the KMA that is a third party.  
           [0053]    Furthermore, the user&#39;s escrowed private key is encrypted with the key of the central server (for instance, the storage key of the KMA for Netscape, and CAST-128 or 3-DES key of the CA for Entrust) and stored in the database.  
           [0054]    Even in the case of compromising the central server&#39;s long-term private key, there still exists a problem such as the reduction of the security of the user&#39;s escrowed private key.  
           [0055]    Since KMA as a central server employs the CRS (Certificate Request Syntax) protocol in an effort to securely transmit the decrypted 3-DES key from KRM, KMA has overhead for using the CRS protocol.  
           [0056]    In addition, the traditional commercial key escrow system still has the problem in a sense that the database is vulnerable to the concentrated attack. This is because the key is kept in a single database despite the fault tolerance due to the periodic back-ups.  
         SUMMARY OF THE INVENTION  
         [0057]    In view of the above-mentioned problems, there is a need in the art for a key escrow system, which is not subject to these limitations.  
           [0058]    Accordingly, it is an object of the present invention to provide a practical key escrow system that is interoperable with PKI (Public Key Infrastructure).  
           [0059]    It is another object of the present invention to provide a key escrow system supporting a PKI-roaming service in addition to the key-backup service. Here, a PKI-roaming service means that the user moving in the wireless Internet environments is able to enjoy mobile PKI-service through downloading the private key with password, which is entered anywhere at client terminal.  
           [0060]    It is still another object of the present invention to provide a key escrow system supporting a lawful access to the user&#39;s private key. In other words, it is an object of the present invention provide a key escrow system that does not allow a third party such as the KMA or the KRA, for instance, to have an access to the user&#39;s private key for encryption without the lawful permissions like the user&#39;s recovery request or the order from the court.  
           [0061]    Yet it is another object of the present invention to present a key escrow system that provides the perfect forward secrecy and the practical utility. Here, a server with perfect forward secrecy implies the one that does not reduce the security of the user&#39;s escrowed key despite making compromise with its long-term private key.  
           [0062]    Practically, the server&#39;s feature of the perfect forward secrecy is a very important factor because much more information regarding the encryption key is concentrated on the central managing server.  
           [0063]    It is also another object of the present invention to present a key escrow system that provides the blindness of the KMA or the KRA, which means that the user&#39;s private key for encryption is invisible either to the KMA or to the KRA during the key recovery process.  
           [0064]    It is still another object of the present invention to provide the key escrow system with the fault-tolerant database of the KMA.  
           [0065]    It is further another object of the present invention to provide a key escrow system that is possibly implemented in software. The aspect of implementation in software is important because the commercial key escrow system has to be economical even with high quality. Thus software implementation would be better for further use in e-commerce.  
           [0066]    In general, a high-performance key escrow system is built with a hardware providing a tamperproof. However, the present invention has a feature in a sense that the escrow system is implemented in software in order to satisfy the requirement both for the cost and for the utility in electronic commerce.  
           [0067]    Yet it is another object of the present invention to present a key escrow system providing a privacy of the user even in the case when applicable to mandatory KES. In other words, the present invention insures the user&#39;s privacy as much as possible.  
           [0068]    It is further another object of the present invention to present a key escrow system that enhances the credibility of the user and prevents the possible attack to a single KRA. The present invention provides a new system with a feature that authorization to the key recovery should be distributed over several servers.  
           [0069]    Yet another object of the present invention is to provide a key escrow system preventing the large-scale wiretapping.  
           [0070]    It is suggested as a solution to enable the legal individual to wiretap only the selected users, and to prohibit illegal massive wiretapping computationally. In accordance with a broad aspect of the present invention, provided is a software-based key escrow system for the PKI environment that is beneficial to both the user and the authority.  
           [0071]    As a result, it becomes possible to protect the user&#39;s privacy even with the extendibility to the PKI-roaming service and the practical utility in the commercial electronic applications.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0072]    Further features of the present invention will become apparent from a description of the fabrication process in conjunction with the accompanying drawings of the preferred embodiment of the invention, which, however, should not be taken to be limitative to the invention, but are for explanation and understanding only.  
         [0073]    In the drawings:  
         [0074]    [0074]FIG. 1A is a schematic diagram illustrating the key escrow process of the Netscape Corporation as a prior art.  
         [0075]    [0075]FIG. 1B is a schematic diagram illustrating the key recovery process of the Netscape Corporation as a prior art.  
         [0076]    [0076]FIG. 2A is a schematic diagram illustrating the key escrow process of VeriSign Corporation as a prior art.  
         [0077]    [0077]FIG. 2B is a schematic diagram illustrating the key recovery process of Verisign Corporation as a prior art.  
         [0078]    [0078]FIG. 3A is a schematic diagram illustrating the key escrow process of Entrust Corporation as a prior art.  
         [0079]    [0079]FIG. 3B is a schematic diagram illustrating the key recovery process of Entrust Corporation as a prior art.  
         [0080]    [0080]FIG. 4A is a schematic diagram illustrating the key escrow process of a first embodiment in accordance with the present invention, an RSA (n, n)-commercial KES.  
         [0081]    [0081]FIG. 4B is a schematic diagram illustrating the key recovery process of a first embodiment in accordance with the present invention, an RSA (n, n)-commercial KES.  
         [0082]    [0082]FIG. 5 is a schematic diagram illustrating the key escrow and recovery processes of a second embodiment in accordance with the present invention, an RSA (n, n)-mandatory KES.  
         [0083]    [0083]FIG. 6 is a schematic diagram illustrating the key escrow and recovery processes of a third embodiment in accordance with the present invention, an RSA (n, n)-mandatory KES.  
         [0084]    [0084]FIG. 7A is a schematic diagram illustrating the key escrow process of a fourth embodiment in accordance with the present invention, a Diffie-Hellman (n, n)-commercial KES.  
         [0085]    [0085]FIG. 7B is a schematic diagram illustrating the key recovery process of fourth embodiment in accordance with the present invention, a Diffie-Hellman (n, n)-commercial KES.  
         [0086]    [0086]FIG. 8 is a schematic diagram illustrating the key escrow and recovery process of a fifth embodiment in accordance with the present invention, a Diffie-Hellman (n, n)-mandatory KES.  
         [0087]    [0087]FIG. 9 is a schematic diagram illustrating the key escrow and recovery processes of a sixth embodiment in accordance with the present invention, a Diffie-Hellman (n, n)-mandatory KES.  
         [0088]    [0088]FIG. 10A and FIG. 10B are a schematic diagram illustrating the key escrow and recovery processes of a seventh embodiment in accordance with the present invention, a Diffie-Hellman (t, n)-commercial KES.  
         [0089]    [0089]FIG. 11 is a schematic diagram illustrating the key escrow and recovery processes of an eighth embodiment in accordance with the present invention, a Diffie-Hellman (t, n)-mandatory KES.  
         [0090]    [0090]FIG. 12 is a schematic diagram illustrating the key escrow and recovery processes of a ninth embodiment in accordance with the present invention, a Diffie-Hellman (t, n)-mandatory KES. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0091]    The present invention will be explained in detail with reference to the accompanying drawings.  
         [0092]    Shown in FIG. 4A and FIG. 4B are the schematic representations of the key escrow and recovery process of a first embodiment in accordance with the present invention, an RSA (n, n)-commercial KES, respectively.  
         [0093]    For the understanding of the features of the present invention, let us explain the notations used in the following context  
         [0094]    PWD: user&#39;s password, which is supposed to be memorized, for the PKI-roaming service  
         [0095]    VER: user&#39;s password verifier that is registered in the KMA.  
         [0096]    KRB: user&#39;s key recovery block.  
         [0097]    (e 1 , N i ): the public key of the KRA i  for encryption (N 1 &lt;N 2 &lt; . . . &lt;N 1 &lt; . . . &lt;N n )  
         [0098]    d 1 : the private key of the KRA 1  for decryption.  
         [0099]    Referring to FIG. 4A, the user  10  generates a pair of private/public keys (PRI, PUB) for encryption. The KRB (key recovery block) is constructed by the user and then forwarded to the RA  11  along with the PUB (step S 201 ).  
         [0100]    The present invention has a feature that the user himself encrypts PRI with PWD. In other words, the operation of C=E PWD (PRI) is performed by the user. 
           KRB =( . . . (( C   e     1     modN   1 ) e     2     modN   2 ) . . . ) e     n     modN   n   (1) 
         [0101]    Referring to FIG. 4A again, the RA  11  sends the KRB and PUB to the KMA  13  (step S 202 ). In the meanwhile, the KMA divides the key recovery block into l shares (KRB 1 , KRB 2 , . . . , KRB l ) with (m, l)-SS (m&lt;l) and stores each share with the user&#39;s identifier in the associate l databases  23  (DB 1 , DB 2 , . . . , DB l ) , correspondingly.  
         [0102]    Preferably, the KRB is then destroyed as long as the divided shares are stored in each database in an appropriate manner. Thereafter, the KMA  13  sends the notice permitting the issuance of encryption certificate to the RA  11  (step S 203 ).  
         [0103]    The RA  11  then exhibits the permission for the issuance to the CA  12  and requests an encryption certificate for the public key of the user  10  (step S 204 ).  
         [0104]    Accordingly, the CA  12  issues encryption certificate (step S 205 ) and sends it to the RA  11  (step S 206 ). Further, the CA  12  opens an encryption certificate in the directory server  19 . Finally, the RA  11  forwards the encryption certificate to the user  10  (step S 207 ).  
         [0105]    [0105]FIG. 4B is a schematic diagram illustrating the key recovery process of a first embodiment in accordance with the present invention, an RSA (n, n)-commercial KES. Referring to FIG. 4B, the user  10  sends a request for the recovery of the private key for encryption to the KMA  13  (step S 210 ).  
         [0106]    After completing the step of identifying the user  10 , the KMA  13  retrieves m key recovery blocks (KRB 1 , KRB 2 , . . . , KRB m ) out of l KRB 1  and reconstructs KRB through the (m, l)-SS. As a preferred embodiment in accordance with the present invention, the encrypted private key E PWD (PRI) is recovered by the KMA  13  through the following steps.  
         [0107]    The KMA  13  randomly chooses a blind factor r (0&lt;r&lt;N 1 ) and calculates KRB′ from the relationship of 
           KRB′=KRB ·( . . . ( r   e     1     modN   1 ) e     2     modN   2 ) . . . ) e     n     modN   n . 
         [0108]    Now, the KMA  13  sends the KRB′ along with the request for the key recovery to the n-th key recovery server KRA n  (step S 211 ). In a reverse order from the n-th KRA to the first KRA (KRA n , KRA n−1 , . . . , KRA 1 ) , each KRA i  decrypts the received message with its own private key (step S 212  through to S 216 ). 
           KRA   n   :KRB′   (n) =( KRB′ ) d     n     modN   n   (2) 
           KRA   n−1   :KRB′   (n−1 )=( KRB′   (n) ) d     n−1     modN   n−1   (3) 
         [0109]    [0109]                 KRA   n     :     KRB     (   n   )     ′       =         (     KRB   ′     )       d   n          mod                   N   n               (   2   )                     KRA     n   -   1       :     KRB     (     n   -   1     )     ′       =         (     KRB     (   n   )     ′     )       d     n   -   1            mod                   N     n   -   1                
                   ⋮           (   3   )                   KRA   2     :     KRB     (   2   )     ′       =         (     KRB     (   3   )     ′     )       d   2          mod                   N   2               (   4   )                   KRA   1     :     KRB     (   1   )     ′       =           (     KRB     (   2   )     ′     )       d   1          mod                   N   1            
                =           E     P                 W                 D            (     P                 R                 I     )       ·   r                   mod                   N   1                 (   5   )                                 
         [0110]    The KRA 1  sends the KRB′ (1) =E PWD (PRI)·r modN 1  to the KMA. Finally, the KMA  13  recovers C=E PWD (PRI)=KRB′ (1) /r modN 1 .  
         [0111]    More preferably, the KMA  13  that has the password verifier (VER) of the user  10  sends C=E PWD (PRI) to the user in a secure fashion such as the password-based private key downloading protocol (step S 217 ).  
         [0112]    [0112]FIG. 5 is a schematic representation illustrating the key escrow process of a second embodiment in accordance with the present invention, an RSA (n, n)-mandatory KES. For a mandatory KES of a second embodiment in accordance with the present invention, the RA has to check if the escrowed private key of the user for encryption has a correspondence to the public key of the user.  
         [0113]    The second embodiment of the present invention discloses a technique that protects the privacy of the user simultaneously with checking capability of the validity of the key recovery block from the user.  
         [0114]    Referring to FIG. 5, the user  10  generates a total of s passwords PWD j  (j=1, . . . , s) and registers the s password verifiers VER j  corresponding to each password to the KMA  13  (step S 221 ).  
         [0115]    Now, the user generates s pairs of private/public keys for encryption (PRI J , PUB j ) In other words, the user  10  generates a set of s private keys (PRI 1 , PRI 2 , . . . , PRI S ) and a set of public keys (PUB 1 , PUB 2 , . . . PUB S ). Thereafter the set of s private keys PRI j  is encrypted with a set of password PWD j  of the user (j=1, . . . , s).  
         [0116]    In other words, C J =E PWD     J   (PRI J ) (j=1, . . . , s) is calculated. In this case, the encrypting step with PWD can be skipped preferably during the process of constructing the KRB when applicable to the key escrow system for the urgent wiretapping.  
         [0117]    Now, the user constructs s key recovery blocks with a relationship of KRB J =( . . . ((C j   e     1    modN 1 ) e     2   modN 2 ) . . . ) e     n   modN n  and sends them along with the public keys PUB j  (j=1, . . . , s) to the RA  11  (step S 222 ).  
         [0118]    The RA  11  that has received the KRB j  (j=1, . . . , s) and PUB J  (j=1, . . . , s) sends a random number of k 1≦k≦s to the user (step S 223 ).  
         [0119]    The user  10  opens (s−1) KRB except KRB k  to RA  11 . In other words, the password PWD J  and PRI j  ∀j≈k, 1≦k≦s are sent to the RA  11  (step S 224 ).  
         [0120]    As a preferred embodiment in accordance with the present invention, the number s controls the strength of the security. More preferably, this scheme can be designed in such a way as a non-interactive KES with a hash function.  
         [0121]    Further, the RA  11  that has received (s−1) KRB j  except KRA k  examines the validity of PRI J  and PUB j  with the following equation. 
           KRB   J   ? ( . . . (( C   j   e     1     modN   1 ) e     2     modN   2 ) . . . ) e     n     mod N   n   (6) 
         [0122]    where ∀j≈k, 1≧j≧s.  
         [0123]    Once the validity of the one-to-one correspondence between the PRI j , PUB j , and KRB j  ∀j≈k, 1≧j≧s is checked, it is considered that it is still valid even when j=k. Then, the RA  11  sends the KRB=KRB k , and PUB=PUB k  to the KMA  13  (step S 225 ). The remaining steps S 226  through to S 230  are identical to the processes of the first embodiment.  
         [0124]    [0124]FIG. 6 is a schematic diagram illustrating the key escrowing process of a third embodiment in accordance with the present invention, an RAS (n, n)-mandatory KES.  
         [0125]    The third embodiment discloses a key escrow system wherein the private/public keys of the user are generated by the KMA  13 , and encrypted with PWD of the user for transmitting to the user.  
         [0126]    The third embodiment can be employed for the practical, safe, and robust key escrow system against shadow attack.  
         [0127]    Referring to FIG. 6, the user  10  sends a request for encryption certificate to the RA  11  (step S 231 ). Then the request is forwarded to the KMA  13  (step S 232 ) through the RA  11 .  
         [0128]    In the meanwhile, the KMA  13  constructs a pair of the user&#39;s private/public keys (PRI, PUB) for encryption. The KRB is constructed and stored in the database as illustrated in the following description.  
         [0129]    First of all, the KMA  13  encrypts the user&#39;s private key PRI with password PWD. In other words, the operation of C=E PWD (PRI) is performed, followed by a step of destroying the PRI. Now, the KRB is calculated with the following equation. 
           KRB =( . . . (( C   e     1     modN   1 ) e     2     modN   2 ) . . . ) e     n     modN   n   (7) 
         [0130]    Additionally, the KMA  13  divides the KRB into l shares with (m, l)-SS (m&lt;l) and stores each share (KRB 1 , KRB 2 , . . . , KRB l ) along with the user&#39;s identifier in the l databases, DB 1    21 , DB 2    22 , . . . , DB l    23 , respectively.  
         [0131]    AS a preferred embodiment, the KRB is destroyed, after storing KRB 1  in the database. The KMA  13  sends the notice permitting the issuance of encryption certificate along with (C, PUB) to the RA  11  (step S 233 ).  
         [0132]    The RA  11  then presents the permission to the CA  12  for the issuance and requests a encryption certificate for the public key PUB of the user  10  for encryption (step S 234 ).  
         [0133]    Accordingly, the CA  12  issues the encryption certificate (step S 235 ) and sends it to the RA  11  (step S 236 ). Further, the CA  12  open an encryption certificate in the directory server  19 .  
         [0134]    Finally, the RA  11  forwards the certificate to the user  10  (step S 237 ). The escrowed private key of the user in the mandatory KES can be recovered through the process illustrated in FIG. 4B, and the KMA should mount a dictionary attack to recover the private key PRI of the user for encryption.  
         [0135]    Now, let us review the features of the present invention with comparison to the prior art by referring to the following table.  
                                                               TABLE 1                           Comparison of features invention       and prior art                Netscape   Verisign   Entrust               (Prior   (Prior   (Prior               Art)   Art)   Art)   Invention                        Commer-   Lawful   Poor   Poor   Poor   Excellent       cial   Access       KES   Utility and   Poor   Poor   Poor   Excellent           Perfect           forward           secrecy           Blindness   Poor   Poor   Poor   Excellent           Fault   Good   Good   Good   Excellent           Tolerance of           storage unit           Feasibility   Excellent   Excellent   Excellent   Excellent           with           software           Value-Added   N/A   PKI-   PKI-   PKI-           service       roaming   roaming   roaming                   service   service   service       Mandatory   Division of   Good   Good   Good   Excellent       KES   authority           depending           for key           on           recovery           Security                       Policy)           Large-scale   Poor   Poor   Poor   Excellent           wiretapping                  
 
         [0136]    The present invention has a unique feature of lawful access because the private key of the user for encryption is encrypted with password PWD that is privately kept only to the user and then encrypted with the KRA&#39;s public key in a successive manner for transmittance.  
         [0137]    Moreover, since the second embodiment in accordance with the present invention, an RSA (n, n)-mandatory KES, preferably employs the cut &amp; choose method for checking the validity of the escrowed private key of the user, a lawful access is guaranteed due to the fact that the secret KRB that has not been made open to a third party is sent to the KMA.  
         [0138]    In the meanwhile, the prior art disclosed by VeriSign and Entrust corporations has a limitation in that the private key of the user can be exposed either to the KMA or to the CA during the generating and escrowing phase, not the recovering phase, because the KMA or the CA itself generates the private key of the user.  
         [0139]    Furthermore, the prior art even from Netscape Corporation discloses a key escrow system wherein the private key of the user is encrypted with a key for transport of the KMA in order to examine the correspondence between the private key and the public key.  
         [0140]    Therefore, it may happen that the private key of the user is exposed to the KMA during the generating and escrowing phase rather than the recovering phase.  
         [0141]    Referring to the Table 1, the present invention has an overwhelming feature in terms of the utility and perfect forward secrecy. For instance, the prior art disclosed from Netscape and Entrust has a shortcoming in a sense that the escrowed key of the user is encrypted with the key of the server (i.e., DRM&#39;s storage key in Netscape and CA&#39;s CAST-128 key or triple DES key in Entrust) and once the private key of the server is made open to the public, the private key of the user for encryption will be in danger.  
         [0142]    Moreover, the prior art disclosed from VeriSign Corporation still has a limitation because the key for the CRS protocol, which is employed for the encryption of the transmitted message, should kept in a secure fashion in order for the KMA to forward the decrypted 3-DES key to the KRA.  
         [0143]    In the meanwhile, the present invention provides a technique that makes it possible to guarantee a perfect forward secrecy because it is not necessary for the KMA to administrate the extra private and public keys.  
         [0144]    Moreover, it is not possible for the KMA to figure out the private key of the user either during the key generation and escrowing phase or during the key recovering phase since the private key of the user is encrypted with the user&#39;s own password that the KMA doesn&#39;t know.  
         [0145]    Furthermore, the blind decoding algorithm in accordance with the present invention does not allow any KRA to find out the information of the user&#39;s private key during the recovering step of the key.  
         [0146]    The key escrow system in accordance with the present invention has further a feature of fault tolerance of the storage unit.  
         [0147]    The periodic back-ups of the database in the prior art disclosed by Netscape, VeriSign, and Entrust still does not provide a fault tolerance since a single unit of database is vulnerable to the hacker&#39;s attack.  
         [0148]    To the contrary, the KMA in accordance with the present invention divides the KRB into a number of shares and each piece of KRB is separately stored in the multiple units of database.  
         [0149]    Therefore, it becomes possible to decrease the chance of being attacked by a hacker for the preferred embodiments in accordance with the present invention.  
         [0150]    More preferably, the proactive secure algorithm allows the security of the KES in accordance with the present invention to be enhanced.  
         [0151]    For the reader&#39;s reference, the proactive secure algorithm can be referred in a paper titled “How to withstand mobile virus attacks,” by R. Ostrovski and M. Young, pp. 51-61, 10th ACM symposium proceeding, 1991.  
         [0152]    In addition, the present invention has a feature of flexibility for implementation both in software and in hardware. The present invention also provides enough flexibility regardless of the platform when compared to the prior art like Clipper.  
         [0153]    The technology for the Clipper is described in a paper titled with, “Escrow encryption Standard (EES),” FIBS PUB (federal information processing standards publication) published by NIST, 1994.  
         [0154]    Referring to Table 1 again, the present invention has a feature of providing a PKI-roaming service due to the fact that the recovered key C=E PWD (PRI) is supposed to be transmitted to the user in a secure manner through the password-based private key downloading protocol.  
         [0155]    Additionally, the key escrow system in accordance with the present invention, unlike the prior art such as the VeriSign&#39;s system, prevents the KRA from abusing its authorized power since the authorization for the key recovery is shared by many KRAs.  
         [0156]    Furthermore, the present invention has a feature of preventing a large-scale wiretapping since the KMA recovers the private key of the user through the dictionary attack as in the partial KES.  
         [0157]    More preferably, the speed of the recovery process of the key can be enhanced through employing the technique disclosed in the U.S. patent application Ser. No. 76/193,977 (High-speed RSA public key cryptographic method).  
         [0158]    In general, the sender and the receiver make an agreement on their session key by Diffie-Hellman key exchange protocol. Once the user&#39;s long-term private key is disclosed, all the communications are insecure.  
         [0159]    Therefore, the limitation of the period of the wiretapping becomes an important issue for the recovery of the key.  
         [0160]    One approach to resolve the above-mentioned problem is to employ a protocol of distributing the session key suggested by A. K. Lenstra. Detailed description about the protocol of distributing the session key can be found in a literature “A key escrow system with warrant bounds,” pp. 197-207 of a book titled with “Advances in cryptology-crypto 95 published by Springer-Verlag, 1995”.  
         [0161]    Now, the followings are the description about additional embodiments in accordance with the present invention, a Diffie-Hellman KES.  
         [0162]    First of all, let us explain the notations used in the following context.  
         [0163]    PWD: the user&#39;s password for PKI-roaming service, which is supposed to be memorized.  
         [0164]    p: prime, P=qw+1, where q is a large prime and w is a smooth composite.  
         [0165]    q: a generator of G q , where G q  is the unique subgroup of Z p * of order q.  
         [0166]    (X 1 , Y i ) the KRA 1 &#39;s pair of encryption key, where y i =g X     1   modp.  
         [0167]    [0167]FIG. 7A is a schematic representation illustrating the generating and escrowing process of the key of a fourth embodiment in accordance with the present invention, a Diffie-Hellman (n, n)-commercial KES.  
         [0168]    Referring to FIG. 7A, the user  10  generates a pair of private/public keys (PRI, PUB) and transmits the KRB along with the PUB to the RA  11  (step S 410 ).  
         [0169]    Here, the user encrypts his private key PRI with his own password PWD. In other words, the user generates C with a relation of C=E PWD (PRI).  
         [0170]    Thereafter, the user selects a random number z from the range 0&lt;z&lt;q. Moreover, the KRB is constructed from the following equation. 
           KRB =( C   1   , C   2 )=( g   z   modP, C· ( y   1   ·y   2   · . . . ·y   n ) z   modP   (8) 
         [0171]    In the meanwhile, the RA  11  transmits the KRB and PUB to the KMA  13  (step S 411 ). Additionally, the KMA divides the KRB into l share (KRB 1 , KRB 2 , . . . , KRB l ) with (m,l)-ss (m&lt;l) and stores each share with the user&#39;s identifier in each database (DB 1    21 , DB 2    22 , . . . , DB l    23 ). After completing the storage, the KRB is destroyed.  
         [0172]    The KMA  13  then sends the notice permitting the issuance of encryption certificate along with (C, PUB) to the RA  11  (step S 412 ).  
         [0173]    The RA  11  then presents the permission to the CA  12  for the issuance and requests a certificate for the user&#39;s public key PUB (step S 413 ).  
         [0174]    Accordingly, the CA  12  issues encryption certificate and open an encryption certificate in the directory server  19 .  
         [0175]    The CA  12  sends the certificate to the RA  11  (step S 414 ). Finally, the RA  11  forwards the certificate to the user  10  (step S 237 ).  
         [0176]    [0176]FIG. 7B is a schematic diagram illustrating the recovering process of the key of a fourth embodiment in accordance with the present invention, a Diffie-Hellman (n, n)-commercial KES.  
         [0177]    Referring to FIG. 7B, the user  10  sends a request for the recovery of the private key for encryption to the KMA  13  (step S 550 ).  
         [0178]    After completing the step of identifying the user  10 , the KMA  13  retrieves m key recovery blocks (KRB 1 , KRB 2 , . . . , KRB m ) out of l KRB i  and reconstructs the KRB through the (m, l)-SS (m&lt;l).  
         [0179]    As a preferred embodiment in accordance with the present invention, the encrypted private key E PWD (PRI) is recovered by the KMA  13  through the following steps.  
         [0180]    The KMA  13  randomly chooses a blind factor r (0&lt;r&lt;P−1) and calculates C 1 ′ from the relation of C 1 ′=C 1   r modp.  
         [0181]    Thereafter, the KMA  13  sends the calculated C 1 ′ along with a request for the recovery of the private key to the key recovery agents (KRA 1 , KRA 2 , KRA n ) .  
         [0182]    In addition, each KRA i  calculates C 1 ″ (1) =(C 1 ′) x     −   modP and then sends C 1 ″ (i)  to the KMA  13  (i=1, . . . , n).  
         [0183]    The KMA  13  recovers the key C=E PWD (PRI) by calculating C 2 /(C 1 ″ (1) ·C 1 ″ (2) · . . . ·C 1 ″ (n) ) 1/r modP. Finally, the KMA  13 , which has a password verifier of the user  10 , sends the recovered private key C=E PWD (PRI) to the user in a secure fashion such as the password-based private key downloading protocol.  
         [0184]    [0184]FIG. 8 is a schematic diagram illustrating the generating and escrowing process of a fifth embodiment in accordance with the present invention, a Diffie-Hellman (n, n)-mandatory KES.  
         [0185]    For a mandatory KES of a fifth embodiment in accordance with the present invention, the RA performs an additional step of checking the validity of the escrowed KRB.  
         [0186]    Referring to FIG. 8, the user  10  generates a total of s passwords PWD j  (j=1, . . . , s) and registers the s password verifiers VER j  corresponding to each password to the KMA  13  (step S 510 ).  
         [0187]    Now, the user generates a total of s pairs of private/public keys for encryption (PRI j , PUB j ). In other words, a set of s private keys (PRI 1 , PRI 2 , . . . , PRI S ) and a set of s public keys (PUB 1 , PUB 2 , . . . , PUB s ) are generated by the user  10 .  
         [0188]    Thereafter, a set of KRB j  (j=1, . . . , s) is constructed and sent to the RA  11  along with PUB j  (j=1, . . . , s). The private key PRI j  is encrypted with the password PWD j  of the user himself  10 . In other words, C J =E PWD     j    (PRI (j=1, . . . , s) is calculated.  
         [0189]    Preferably, in the key escrow system that needs the urgent wiretapping, the encrypting step with PWD can be skipped during the generating step of the KRB. Additionally, a total of s random numbers z 1  are chosen in a range of 0&lt;z i &lt;q (j=1, . . . , s) and the KRB j  (j=1, . . . , s) is calculated from the following equation.  
                       KRB   j     =     (       C     1      j       ,     C     2   3         )                 =     (         g     z   j          mod                 P     ,         C   j     ·       (       y   1     ·     y   2     ·   …   ·     y   n       )       z   3            mod                 P                             (   9   )                               
 
         [0190]    In the meanwhile, the RA  11  chooses k randomly in a range of 1≦k≦s and sends k to the user (step S 512 ). Preferably, the security level of the system can be varied with s.  
         [0191]    Referring to FIG. 8 again, the user  10  open (s−1) KRB j  except the KRB k  to RA  11  (step S 513 ). In other words, the password PWD j , PRI j  and z j  ∀j≈k, 1≦j≦s are sent to the RA  11 . Further, the RA  11 , which has received (s−1) KRB s  except the KRB k , examines the validity and the correspondence of PRI j , PUB J , and KRB J  with the following equation. 
           KRB   J   ? (g z     J     modP, C   J ·( y   1   ·y   2 · . . . ·y n ) z     J     modP   (10) 
         [0192]    As a preferred embodiment in accordance with the present invention, the number S controls the strength of the security. More preferably, this scheme can be designed in such a way as a non-interactive KES with a hash function. Now the RA  11  sends KRB=KRB k  and PUB=PUB k  to the KMA  13  (step S 514 ). The remaining steps S 515  through to S 518  are identical to the processes of the fourth embodiment.  
         [0193]    The Sixth embodiment can be employed for the practical, safe, and robust key escrow system against shadow attack.  
         [0194]    [0194]FIG. 9 is a schematic diagram illustrating the generating and escrowing process of a sixth embodiment in accordance with the present invention, a (n, n)-mandatory KES based on Diffie-Hellman.  
         [0195]    Referring to FIG. 9, the user  10  sends a request for an encryption certificate to the RA  11  (step S 630 ). The RA  11  forwards the request to the KMA  13  (step S 631 ). The KMA  13  generates a pair of private/public keys (PRI, PUB), and constructs the KRB to store in a distributed database  21 ,  22 ,  23  (step S 632 ).  
         [0196]    The KMA  13  encrypts the user&#39;s private key PRI with user&#39;s password PWD. In other words, C=E PWD (PRI) is calculated. In this case, it is assumed that the password of the user  10  PWD has been pre-registered at the KMA  13 .  
         [0197]    Thereafter, a random number z is selected in the range of 0&lt;z&lt;q. The KRB is constructed from the following equation. 
           KRB= ( C   1   , C   2 )=( g   z   modP, C· ( y   1   ·y   2   · . . . ·y   n ) z   modp   (11) 
         [0198]    Now, the KMA  13  divides the KRB into l shares (KRB 1 , KRB 2 , . . . , KRB l ) with (m, l)-SS (m&lt;l), and stores each share in the associated database (DB 1 , DB 2 , . . . , DB l ) of l, correspondingly, with the identifier of the user. After storing KRB 1  in the database, the KRB is destroyed.  
         [0199]    The KMA  13  then sends the permission to issue the encryption certificate along with (C, PUB) to the RA  11  (step S 633 ). The RA  11  then presents the permission to the CA  12  and requests a certificate for the public key of the user  10 , PUB (step S 634 ).  
         [0200]    Accordingly, the CA  12  issues the certificate of encryption and makes it public at a directory server  19  (step S 635 ). The CA  12  sends the certificate to the RA  11  (step S 636 ). Finally, the RA  11  forwards the certificate to the user  10  (step S 637 ).  
         [0201]    For the fifth embodiment of this invention, the escrowed key can be recovered with the process depicted in FIG. 7B. In this case, the KMA can recover the private key of the user, PRI, by mounting a dictionary attack on the password of the user.  
         [0202]    For the sixth embodiment of the present invention, the escrowed key can also be recovered with the process in FIG. 7B. In this case, the KMA can recover the private key of the user, PRI, by using the password available to the KMA.  
         [0203]    Now, the following is a detailed description of another embodiment of this invention, (t, n)-commercial KES based on Diffie-Hellman (t&lt;n). The unique feature of the preferred Diffie-Hellman (t, n)-commercial embodiment in accordance with the present invention is that t KRAs out of n are enough for the recovery of the escrowed key.  
         [0204]    x 1 : a private key of KRA 1  for 1≦i≦n.  
         [0205]    y: a public key of the group of KRAs.  
         [0206]    P: a prime, P=qw+1, where q is a large prime and w is a smooth composite.  
         [0207]    g: a generator of G q , where G q  is the unique subgroup of Z p   *  of order q.  
         [0208]    Each KRA i =1, . . . , n chooses r 1 ε R z q  and makes y 1 =g r     1   modP public. Each KRA i  selects a random polynomial f 1 ε R z q [χ] of degree (t−1) such that f 1 (0)=r 1 . Let f i (x)=r i +a 1,i ·x+a 1,2 ·x 2 + . . . +a 1,t−1 ·x t−1 modq, where a i,1 , a 1,2 , . . . , a 1,t−1 ε R z q . Then the KRA 1  computes f 1 (j)modq ∀j≈i, 1≦j≦n and sends it to the KRA j  securely.  
         [0209]    Thereafter, each KRA 1  computes, g a     1,1   modP, g a     1,2   modP and makes them public. Using received f j (i) ∀j≈i, 1≦j≦n , each KRA j  verifies if g f     J     (1)   ? y j ·(g a     J,1   ) i     1   · . . . ·(g a     J,t−1   ) J     t−1   modP Vj≈i, 1≦j≦n.  
         [0210]    Let us define H as the set {KRA 1 |KRA i  is an honest KRA satisfying the previous step.} Each KRA i  computes its private key  
         X   i     =       ∑     j   ∈   H              f   j          (   i   )                               
 
         [0211]    (i) and keeps it secure. The KRAs compute and publish their group public key  
       y   =       ∏     j   ∈   H              y   j     .                             
 
         [0212]    [0212]FIG. 10 is a schematic representation illustrating key generation, escrow process, and key recovery process of a seventh embodiment in accordance with the present invention, a (t, n)-commercial KES based on Diffie-Hellman.  
         [0213]    Referring to FIG. 10A, the user  10  generates a pair of private/public keys (PRI, PUB), and sends the KRB along with the PUB to the RA  11  (step S 710 ). The user  10  encrypts his private key, PRI, with his own password, PWD.  
         [0214]    Thereafter, a random number z in the range of 0&lt;z&lt;q is selected. In addition, the key recovery block is computed from the following equation.  
                       K                 R                 B     =     (       C   1     ,     C   2       )                 =     (         g   z        mod                 P     ,       C   ·     y   z          mod                 P       )                         (   12   )                               
 
         [0215]    In the meanwhile, the RA  11  sends the key recovery block, KRB, and the public key, PUB, to the KMA  13  (step S 711 ). The KMA  13  divides the KRB into l shares (KRB 1 , KRB 2 , . . . , KRB l ) with(m, l)-SS (m&lt;l), and stores each share with user&#39;s identifier in each database (DB 1 , DB 2 , . . . , DB l )  
         [0216]    After the completion of the storage, the KRB is destroyed. The KMA  13  then sends a permission to issue the certificate of the encryption (step S 712 ). The RA  11  then presents the permission to the CA  12  and requests a certificate for user&#39;s public key, PUB (step S 713 ).  
         [0217]    Accordingly, the CA  12  issues the certificate of encryption and makes it public at a directory server  19 . The CA  12  sends the certificate to the RA  11  (step S 714 ). Finally, the RA  11  forwards the certificate to the user  10  (step S 715 ).  
         [0218]    Referring to FIG. 10B, the user  10  sends a request for the key recovery to the KMA  13  (step S 850 ). After identifying the user  10 , the KMA  13  retrieves m key recovery blocks (KRB 1 , KRB 2 , . . . , KRB m ) out of l key recovery blocks and reconstructs the KRB through the (m, l)-SS (m&lt;l).  
         [0219]    As a preferred embodiment in accordance with this invention, the encrypted private key E PWD (PRI) can be recovered by the KMA  13  through the following steps. The KMA  13  randomly chooses a blind factor r (0&lt;r&lt;P−1) and calculates c 1 ′ from the relation of C 1 ′=C 1   r modP.  
         [0220]    Thereafter, the KMA  13  sends the calculated C 1 ′ along with a request for the key recovery to the key recovery agents (KRA 1 , KRA 2 , . . . , KRA n ).  
         [0221]    In addition, each of t key recovery agents calculates C 1 ″ (i     j     ) =(C 1 ′) x     lj    modP and then sends (C 1 ″ (i     J     ) , i J ) to the KMA  13  (1≧ i     1   &lt; . . . &lt;i i     j   &lt; . . . &lt; i     t   ≧n) The KMA  13  receives t (C 1 ″ (1) , i) pairs from the KRAs of t, and recovers the encrypted private key C=E PWD (PRI) by calculating  
         C   2     /       ∏   i              (     C   1     ″     (   i   )         )               r     -   1                ∏     j   ≠   i            z   /     (     j   -   i     )                mod                   P   .                               
 
         [0222]    modP.  
         [0223]    Finally, the KMA  13 , which has a password verifier of the user  10 , sends the recovered c=E PWD (PRI) to the user in a secure fashion using “password-based private key downloading protocol”.  
         [0224]    Now, when we want to apply the (t, n)-commercial KES based on Diffie-Hellman to a mandatory KES having a protection against a large-scale wiretapping, the RA performs an additional step of checking the validity of the escrowed key recovery block.  
         [0225]    In this case, cut &amp; choose method as in the previous second embodiment can be preferably employed.  
         [0226]    [0226]FIG. 11 is a schematic diagram illustrating the key generation and escrow process of an eighth embodiment in accordance with this invention, (t, n)-mandatory KES based on Diffie-Hellman.  
         [0227]    Referring to FIG. 11, the user  10  generates a total of s passwords PWD j  (j=1, . . . , s) and registers the s password verifiers VER j  (j=1, . . . , s) corresponding to each password to the KMA  13  (step S 910 ). Now, the user generates a total of s pairs of private/public keys for encryption (PR j , PUB j ).  
         [0228]    Thereafter, a set of KRB j  (j=1, . . . , s) is constructed and sent to the RA  11  along with PUB j  (j=1, . . . , s).  
         [0229]    The private key PRI j  is encrypted with the password PWD j  of the user  10 . In other words, C J =E PWD     J   (PRI j ) (j=1, . . . , s) is calculated. Preferably, in the key escrow system that needs the urgent wiretapping, the encrypting step with PWD can be skipped in the generating step of the KRB.  
         [0230]    Additionally, a total of s random number z j  are chosen in the range of 0&lt;z J &lt;q (j=1, . . . , s) and the KRB j (j=1, . . . , s) is calculated from the following equation. 
           KRB   J =( C   1J   , C   2j )=( g   z     J     modP, C   J ·( y ) z     J     modP   (13) 
         [0231]    In the meanwhile, the RA  11  randomly chooses k in the range of 1≦k≦s and sends k to the user (step S 912 ). Preferably, the security level of this system depends on the size of s.  
         [0232]    Referring to FIG. 11 again, the user  10  opens (s−1) KRB j  except the KRB k  to the RA  11  (step S 913 ).  
         [0233]    In other words, the PWD j , PRI j , and for ∀j≈k and 1≦j≦s are sent to the RA  11 . Further, the RA  11 , which has received (s−1) key recovery blocks except the KRB k , examines the validity of the KRB j  and the correspondence of PRI j  and PUB j  for ∀j≈k, 1≦j≦s.  
         [0234]    As a preferred embodiment in accordance with this invention, this scheme can be designed in such a way as a non-interactive one with a hash function.  
         [0235]    Now the RA  11  sends KRB=KRB k  and PUB=PUB k  to the KMA  13  (step S 914 ). The remaining steps S 915  through to S 919  are identical to the processes of the fourth embodiment.  
         [0236]    As a preferred embodiment for robust and practical (n, n)-mandatory KES based on Diffie-Hellman that is secure against the shadow public key attack, a sixth embodiment is disclosed wherein the private/public key of the user is generated and encrypted by the KMA and then sent to the user.  
         [0237]    [0237]FIG. 12 is a schematic diagram illustrating the key generation and escrow process of a ninth embodiment in accordance with the present invention, (t, n)-mandatory KES based on Diffie-Hellman.  
         [0238]    Referring to FIG. 12, the user  10  sends a request for the certificate of encryption to the RA  11  (step S 1210 ). Then the RA  11  forwards the request to the KMA  13  (step S 1211 ).  
         [0239]    The KMA generates a pair of private/public keys (PRI, PUB) for the user, and constructs the KRB as illustrated in the following description.  
         [0240]    The KMA  13  encrypts the private key of the user PRI with user&#39;s password PWD. In other words, C=E PWD (PRI) is calculated. In this case, it is assumed that the password of the user PWD has already been registered in the KMA  13 . Thereafter, the KMA  13  selects a random number z in the range of 0&lt;z&lt;q.  
         [0241]    Moreover, the KMA  13  constructs the KRB from the following equation. 
           KRB= ( C   1   , C   2 )=( g   z   modP, C·y   z   modp   (14) 
         [0242]    Additionally, the KMA divides the KRB into l shares (KRB 1 , KRB 2 , . . . , KRB l ) with (m, l)-SS (m&lt;l) and stores each share with user&#39;s identifier in each database (DB 1    21 , DB 2    22 , . . . , DB l    23 ). After, completing the storage, the KRB is destroyed.  
         [0243]    The KMA  13  then sends a permission to issue the certificate of encryption along with (C, PUB) to the RA  11  (step S 1212 ). The RA  11  then presents the permission to the CA  12  and requests a certificate for the public key of the user  10 , PUB (step S 1213 ).  
         [0244]    Accordingly, the CA  12  issues the certificate of encryption and makes it public at a directory server  19 . The CA  12  sends the certificate to the RA  11  (step S 1214 ). Finally, the RA  11  forwards the certificate and C to the user  10  (step S 1215 ).  
         [0245]    For the eighth embodiment of this invention, the escrowed key can be recovered with the process illustrated in FIG. 10B. More preferably, the private key of the user, PRI, can be recovered by mounting a dictionary attack on the password of the user.  
         [0246]    For the ninth embodiment of this invention, the escrowed key can also be recovered with the process illustrated in FIG. 10B. More preferably, the private key of the user, PRI, can be recovered with user&#39;s password that has been available with the KMA.  
         [0247]    Although the present invention has been illustrated and described with respect to exemplary embodiments thereof, it should be understood by those skilled in the art that various other changes, omissions and additions may be made therein and thereto, without departing from the spirit and scope of the present invention.  
         [0248]    It should be appreciated by those skilled in the art that the specific embodiments disclosed above may be readily utilized as a basis for modifying or designing other techniques and processes for carrying out the same purposes of the present invention.  
         [0249]    It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.