Fair cryptosystems and methods of use

Abstract

A method, using a public-key cryptosystem, for enabling a predetermined entity to monitor communications of users . .suspected of unlawful activities while protecting the privacy of law-abiding users.!., wherein each user is assigned a pair of matching secret and public keys. According to the method, each user's secret key is broken into shares. Then, each user provides a plurality of "trustees" pieces of information. The pieces of information provided to each trustee enable that trustee to verify that such information includes a "share" of a secret key of some given public key. Each trustee can verify that the pieces of information provided include a share of the secret key without interaction with any other trustee or by sending messages to the user. Upon a predetermined request or condition, e.g., a court order authorizing the entity to monitor the communications of a user . .suspected of unlawful activity.!., the trustees reveal to the entity the shares of the secret key of such user. This enables the entity to reconstruct the secret key and monitor the . .suspect.!. user's communications.

What is claimed is: 
     
       1. A method, using a public-key cryptosystem, for enabling a predetermined entity to monitor communications of users suspected of unlawful activities while protecting the privacy of law-abiding users, wherein each user is assigned a pair of matching secret and public keys, comprising the steps of: breaking each user's secret key into shares;   providing trustees pieces of information enabling the trustees to verify that the pieces of information include shares of a secret key of some given public key; and   upon a predetermined request, having the trustees reveal the shares of the secret key of a user suspected of unlawful activity to enable the entity to attempt reconstruction of the secret key for monitoring communications to the suspect user.   
     
     
       2. The method as described in claim 1 wherein the predetermined entity is a government agency and the predetermined request is a court order. 
     
     
       3. The method as described in claim 1 wherein the identity of the suspect user is known to the trustees. 
     
     
       4. The method as described in claim 1 wherein the identity of the suspect user is unknown to the trustees. 
     
     
       5. The method as described in claim 1 further including the step of: characterizing the suspect user's activities as unlawful if the entity is unable to monitor the suspect user's communications.   
     
     
       6. The method as described in claim 1 wherein less than all of the shares of the suspect user's secret key are required to be revealed in order to reconstruct the secret key. 
     
     
       7. The method as described in claim 1 wherein the shares are revealed to the entity upon the predetermined request. 
     
     
       8. The method as described in claim 1 wherein a given minority of trustees are unable to reconstruct the secret key. 
     
     
       9. The method as described in claim 1 wherein each trustee can verify that the pieces of information provided include a share of the secret key without interaction with any other trustee. 
     
     
       10. A method, using a public-key cryptosystem, for enabling a predetermined entity to monitor communications of users suspected of unlawful activities while protecting the privacy of law-abiding users, wherein each user is assigned a pair of matching secret and public keys, comprising the steps of: breaking each user's secret key into shares;   providing trustees pieces of information that include shares of a secret key of some give public key.Iadd., trustees being distinct from the predetermined entity,.Iaddend.; and   upon a predetermined request, having the trustees reveal the shares of the secret key of auser suspected of unlawful activity to enable the entity to reconstruct the secret key and monitor communications to the suspect user.   
     
     
       11. A method, using a public-key cryptosystem . .into a cryptosystem.!., for enabling a predetermined entity to monitor communications of users suspected of unlawful activities while protecting the privacy of law-abiding users, comprising the step.Iadd.s .Iaddend.of: . .verifying.!. .Iadd.verifiably .Iaddend.secret sharing each user's secret key with a plurality of trustees so that each trustee can verify that the share received is part of a secret key of some public key.Iadd.; and   upon a predetermined request, having at least some of the trustees reveal the shares of the secret key of a user to enable the entity to reconstruct the secret key and monitor communications to the user.Iaddend..   
     
     
       12. The method as described in claim 11 further including the step of: characterizing the suspect user's activities as unlawful if the entity is unable to monitor the suspect user's communications.   
     
     
       13. The method as described in claim 11 wherein a given minority of trustees are unable to reconstruct the secret key. 
     
     
       14. The method as described in claim 11 wherein each trustee can verify that the pieces of information provided include a share of the secret key without interaction with any other trustee. 
     
     
       15. A method, using a cryptosystem, for enabling a predetermined entity to monitor communications of users suspected of unlawful activities while protecting the privacy of law-abiding users, wherein a group of users has a secret key, comprising the steps of: breaking the secret key into shares;   providing trustees pieces of information that include shares of the secret key.Iadd., trustees being distinct from the predetermined entity.Iaddend.; and   upon a predetermined request, having the trustees reveal the shares of the secret key of a user suspected of unlawful activity to enable the entity to reconstruct the secret key and monitor communications to the suspect user.   
     
     
       16. The method as described in claim 15 further including the step of: characterizing the suspect user's activities as unlawful if the entity is unable to monitor the suspect user's communications.   
     
     
       17. The method as described in claim 15 wherein a given minority of trustees are unable to reconstruct the secret key. 
     
     
       18. The method as described in claim 15 wherein each trustee can verify that the pieces of information provided include a share of the secret key without interaction with any other trustee. .Iadd.19. A method, using a public-key cryptosystem, for enabling a predetermined entity to monitor communications of users, wherein each user is assigned a pair of matching secret and public keys, comprising the steps of: breaking each user's secret key into shares;   providing trustees pieces of information enabling the trustees to verify that the pieces of information include shares of a secret key of some given public key; and   upon a predetermined request, having the trustees reveal the shares of the secret key of a user to enable the entity to attempt reconstruction of the   
     
     
        secret key for monitoring communications to the user..Iaddend..Iadd.20. The method of claim 19, for monitoring communications of certain users while protecting the privacy of other users..Iaddend..Iadd.21. A method, using a public-key cryptosystem, for enabling a predetermined entity to monitor communication of users, wherein each user is assigned a pair of matching secret and public keys, comprising the steps of: breaking each user's secret key into shares;   providing trustees pieces of information that include shares of a secret key of some given public key, trustees being distinct from the predetermined entity; and   upon a predetermined request, having the trustees reveal the shares of the secret key of a user to enable the entity to reconstruct the secret key and monitor communications to the user..Iaddend..Iadd.22. The method of claim 21, for monitoring communications of certain users while protecting   
     
     
        the privacy of other users..Iaddend..Iadd.23.  A method, using a public-key cryptosystem, for enabling a predetermined entity to monitor communications of users, comprising the steps of: verifiably secret sharing each user's secret key with a plurality of trustees so that each trustee can verify that the share received is part of a secret key of some public key; and   upon a predetermined request, having at least some of the trustees reveal the shares of the secret key of a user to enable the entity to reconstruct the secret key and monitor communications to the user..Iaddend..Iadd.24. The method of claim 23, for monitoring communications of certain users while protecting the privacy of other users..Iaddend..Iadd.25. A method, using a cryptosystem, for enabling a predetermined entity to monitor communications of users, wherein a group of users has a secret key, comprising the steps of:   breaking the secret key into shares;   providing trustees pieces of information that include shares of the secret key, trustees being distinct from the predetermined entity; and   upon a predetermined request, having the trustees reveal the shares of the secret key of a user to enable the entity to reconstruct the secret key   
     
     
        and monitor communications to the user..Iaddend..Iadd.26.  The method of claim 23, for monitoring communications of certain users while protecting the privacy of other users..Iaddend.