Method and system for quorum controlled asymmetric proxy encryption

• US 6,587,946 B1
• Filed: 12/29/1998
• Issued: 07/01/2003
• Est. Priority Date: 12/29/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Jakobsson, Markus Bjorn
• Primary Examiner(s): Barron, Gilberto
• Assistant Examiner(s): MEISLAHN, DOUGLAS J
• Application Number:
  US09/222,716
• Time in Patent Office: 1,645 Days
• Field of Search: 380/278, 380/282, 380/285, 380/286, 713/180, 713/170, 713/153
• US Class Current: 713/180
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 2209/76 Proxy, i.e. using intermediary entity to perform cryptographic operations network architectures or network communication protocols using hop-by-hop encryption H04L63/0464
• CPC Class Codes: H04L 51/00 User-to-user messaging in packet-switching networks, transmitted according to store-and-forward or real-time protocols, e.g. e-mail
• CPC Class Codes: H04L 63/02 for separating internal from external traffic, e.g. firewalls
• CPC Class Codes: H04L 63/04 for providing a confidential data exchange among entities communicating through data packet networks
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs

Abstract

A method of forwarding an encrypted message sent to a primary recipient having a secret key to at least one secondary recipient comprising the steps of sharing portions of the secret key among a predetermined threshold number of proxy servers greater than one, upon receipt of an encrypted message by the predetermined threshold number of proxy servers, each of the predetermined threshold number of proxy servers modifying the message by applying the key portion to the encrypted message, the result of the modification comprising a message secret to the predetermined threshold number of proxy servers but decryptable by at least one secondary recipient, and forwarding the resultant message to at least one secondary recipient. This method and system for quorum controlled asymmetric proxy encryption has uses ranging from efficient key distribution for pay-tv, to methods for distributively maintaining databases. The scheme, which can use either an ElGamal, or an ElGamal encryption based on Elliptic Curves or an ElGamal related encryption algorithm, leaks no information as long as there is no dishonest quorum of proxy servers.

Claims

1. A method of forwarding an encrypted message sent to a primary recipient having a secret key to at least one secondary recipient comprising the steps of

sharing portions of said secret key among a plurality of proxy servers,

upon receipt of an encrypted message by said plurality of proxy servers, each of said plurality of proxy servers modifying said encrypted message by applying said key portion to said encrypted message, the result of said modifications comprising a message secret to said plurality of proxy servers but decryptable by said at least one secondary recipient,

forwarding said resultant encrypted message to said at least one secondary recipient, and

a first one of said plurality of proxy servers modifying said encrypted message followed by a second one of said plurality of proxy servers modifying said encrypted message and verifying said first one of said plurality of proxy servers'"'"' modification of said encrypted message.

2. A method of forwarding an encrypted message according to claim 1 wherein the number of members in said plurality of proxy servers is equal to a predetermined threshold number that is specified by said primary recipient.

3. A method of forwarding an encrypted message according to claim 1 wherein said encrypted message is encrypted according to an ElGamal encryption algorithm.

4. A method of forwarding an encrypted message according to claim 1 wherein said encrypted message is encrypted according to an ElGamal encryption based on at least one of Elliptic Curves or an ElGamal related encryption.

5. A method of forwarding an encrypted message according to claim 1 further comprising the step of

verifying a modification of said encrypted message by one of said plurality of proxy servers.

6. A method of forwarding an encrypted message as recited in claim 5 further comprising the steps of

all said plurality of proxy servers verifying a modification of said encrypted message, and

signing their respective modification.

7. A method of forwarding an encrypted message as recited in claim 1 wherein said step of modifying said encrypted message by applying a key portion comprises the substeps of encrypting and decrypting said encrypted message.

8. A method of forwarding an encrypted message as recited in claim 7 wherein said substeps of encryption and decryption of said encrypted message comprise partially decrypting and then encrypting said partially decrypted encrypted message occur in the order of decryption followed by encryption.

9. A method of forwarding an encrypted message as recited in claim 7 wherein said substeps of encryption and decryption of said encrypted message comprise partially encrypting and then decrypting said partially encrypted encrypted message occur in the order of encryption followed by decryption.

10. A method of forwarding an encrypted message as recited in claim 7 wherein said substeps of encryption and decryption of said encrypted message by said plurality of proxy servers occurs in parallel.

11. A method of forwarding an encrypted message as recited in claim 7 wherein said substeps of encryption and decryption of said encrypted message by said plurality of proxy servers occurs serially.

12. A method of forwarding an encrypted message as recited in claim 1 wherein the number of members in said plurality of proxy servers is determined by said primary recipient and comprises a quorum of a predetermined total number of proxy servers.

13. A method of forwarding an encrypted message as recited in claim 1 wherein said plurality of proxy servers modifications of said encrypted message may occur in any order of said plurality of proxy servers.

14. A method of forwarding an encrypted message as recited in claim 1 wherein said shared portion of said secret key is shared among said plurality of proxy servers using proactive secret sharing methods to protect against a mobile attacker who can corrupt any non-quorum of servers for any time period.

15. A method of forwarding an encrypted message as recited in claim 1 wherein said encrypted message comprises data identifying said primary recipient.

16. A method of forwarding an encrypted message as recited in claim 15 wherein said data identifying said primary recipient is received encrypted by a key accessible to each of said plurality of proxy servers.

17. A method of forwarding an encrypted message as recited in claim 16 further comprising the step of

decrypting the identity of said primary recipient by at least one of said plurality of proxy servers via said accessible key.

18. A method of forwarding an encrypted message as recited in claim 1 further comprising the step of

decrypting said resultant secret encrypted message by said secondary recipient via a secret key of said secondary recipient.

19. An apparatus for forwarding an encrypted message sent to a primary recipient having a secret key to at least one secondary recipient comprising

a means for sharing portions of said secret key among a plurality of proxy servers,

a means for each of said plurality of proxy servers to modify said encrypted message by applying said key portion to said encrypted message, the result of said modifications comprising a message secret to said plurality of proxy servers but decryptable by said at least one secondary recipient, and

a means for forwarding said resultant encrypted message to said at least one secondary recipient,

wherein a first one of said plurality of proxy servers modifies said encrypted message followed by a second one of said plurality of proxy servers modifying said encrypted message and verifying said first one of said plurality of proxy servers'"'"' modification of said encrypted message.

20. The apparatus as recited in claim 19 wherein the means for forwarding said resultant encrypted message comprises an E-mail communication system.

21. The apparatus as recited in claim 19 wherein said plurality of proxy servers comprising a quorum of a predetermined total number of proxy servers.

22. A communication system for forwarding an encrypted message sent to a primary recipient having a secret key to at least one secondary recipient, said communication system comprising

a first memory for said primary recipient for receiving and sending said encrypted messages,

a plurality of second memories, wherein each of said second memories is associated with one of said at least one secondary recipient for receiving and sending said encrypted messages,

a plurality of proxy servers for administering said communication system,

a quorum of proxy servers selected from said plurality of proxy servers for forwarding said encrypted message sent to said first memory of said primary recipient to each of said plurality of second memories of said at least one secondary recipient, and

a means for sending and receiving said encrypted messages between said first memory of said primary recipient to each of said plurality of second memories of said at least one secondary recipient,

wherein a first one of said quorum of proxy servers modifies said encrypted message followed by a second one of said quorum of proxy servers modifying said encrypted message and verifying said first one of said quorum of proxy servers'"'"' modification of said encrypted message.

23. The communication system as recited in claim 22 wherein the number of members in said quorum of proxy servers is determined by said primary recipient.

24. The communication system as recited in claim 22 wherein the means for sending and receiving said encrypted messages comprises an E-main communication system.

25. A computer-readable medium having computer-executable instructions for performing the step comprising

forwarding an encrypted message sent to a primary recipient having a secret key in a form decryptable by at least one secondary recipient wherein said forwarding step comprises the substeps of

(a) outputting portions of said secret key to a plurality of proxy servers,

(b) receiving said encrypted message by said plurality of proxy servers,

(c) applying each said key portion to modify said encrypted message, the result of said modifications comprising an encrypted message secret to said plurality of proxy servers but decryptable by said at least one secondary recipient, and

(d) forwarding said resultant encrypted message to said at least one secondary recipient,

wherein a first one of said plurality of proxy servers modifies said encrypted message followed by a second one of said plurality of proxy servers modifying said encrypted message and verifying said first one of said plurality of proxy servers'"'"' modification of said encrypted message.

26. A computer-readable medium having computer-executable instructions as recited in claim 25 wherein the number of members in said plurality of proxy servers is determined by said primary recipient and comprises a quorum of a predetermined total number of proxy servers.

27. A computer-readable medium having computer-executable instructions for performing the step comprising

forwarding an encrypted message sent to a primary recipient having a secret key in a form decryptable by at least one secondary recipient wherein said forwarding step comprises the substeps of

(a) outputting portions of said secret key from a communication system to a plurality of proxy servers,

(b) sending said encrypted message from said communication system to said plurality of proxy servers,

(c) receiving a resultant encrypted message in said communication system from said plurality of proxy servers, and

(d) forwarding said resultant encrypted message from said communication system to said at least one secondary recipient,

wherein a first one of said plurality of proxy servers modifies said encrypted message followed by a second one of said plurality of proxy servers modifying said encrypted message and verifying said first one of said plurality of proxy servers'"'"' modification of said encrypted message.

28. A computer-readable medium having computer-executable instructions as recited in claim 27 wherein the number of members in said plurality of proxy servers is determined by said primary recipient and comprises a quorum of a predetermined total number of proxy servers.

29. A computer-readable medium having computer-executable instruction for performing the steps comprising

(a) receiving portions of a secret key form a communication system by a plurality of proxy servers,

(b) receiving an encrypted message from said communication system by said plurality of proxy servers,

(c) applying each said key portion to modify said encrypted message, the result of said modifications comprising an encrypted message secret to said plurality of proxy servers but decryptable by said at least one secondary recipient, and

(d) sending said resultant encrypted message to said communication system from said plurality of proxy servers,

wherein a first one of said plurality of proxy servers modifies said encrypted message followed by a second one of said plurality of proxy servers modifying said encrypted message and verifying said first one of said plurality of proxy servers'"'"' modification of said encrypted message.

30. A computer-readable medium having computer-executable instructions as recited in claim 29 wherein the number of members in said plurality of proxy servers is determined by said primary recipient and comprises a quorum of a predetermined total number of proxy servers.