Method and system for providing translation certificates

• US 6,687,822 B1
• Filed: 06/11/1999
• Issued: 02/03/2004
• Est. Priority Date: 06/11/1999
• 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): Zand, Kambiz
• Application Number:
  US09/330,194
• Time in Patent Office: 1,698 Days
• Field of Search: 713/156, 713/158, 713/175
• US Class Current: 713/156
• 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 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]

Abstract

A method for providing publicly verifiable translation certificates comprising the steps of receiving an input encryption having a first secret key; outputting an output re-encryption of the input encryption, the output re-encryption having a second secret key; and generating a translation certificate that proves the input encryption and the output re-encryption are encryptions of an identical message, wherein the first secret key and the second secret key do not need to be, but are allowed to be, equal. This method and system for generating translation certificates in quorum controlled asymmetric proxy encryptions has uses, including but not limited to, Internet applications and specifically to E-mail systems. The scheme, which can use either an ElGamal encryption, 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 and produces a small, publicly verifiable translation certificate, that is independent of the number of prover servers involved in the re-encryption.

Claims

1. A method for providing publicly verifiable translation certificates comprising the steps of:

receiving an input encryption having a first secret key;

outputting an output re-encryption of said input encryption, said output re-encryption having a second secret key; and

generating a translation certificate that verifies said input encryption and said output re-encryption are encryptions of an identical message.

2. The method recited in claim 1, wherein said generating a translation certificate step further comprises the substeps of:

computing and outputting a first public key that corresponds to said first secret key; and

verifying said output re-encryption has a correct relationship with said first public key and so a second public key.

3. The method as recited in claim 2, wherein said verifying said output re-encryption step further comprises the substeps of:

selecting a first random value;

computing a pair of challenges from a partial decryption of said input encryption;

computing a first response responsive to said computed pair of challenges; and

outputting said partial decryption and said first response;

selecting a second random value;

computing a challenge from a partial re-encryption of said partial decryption;

computing a second response responsive to said computed challenge; and

outputting said partial re-encryption and said second response.

4. The method recited in claim 3, wherein said generating said translation certificate step comprises the substep of:

combining said first public key, said second public key, said partial decryption, said first response, said partial re-encryption, and said second response in a transcript.

5. The method recited in claim 4 further comprising the substep of:

verifying said translation certificate is correct.

6. The method recited in claim 5, wherein said verifying said translation certificate step further comprises the substeps of:

re-computing a new pair of challenges from said partial decryption;

accepting a verifying knowledge step as correct, if said re-computed new pair of challenges equals said computed pair of challenges;

re-computing a new challenge from said partial re-encryption;

accepting said comparing said output re-encryption step as correct, if said re-computed new challenge equals said computed challenge; and

outputting an acceptance if both said verifying knowledge step and said comparing said output re-encryption step are correct, otherwise outputting a rejection.

7. The method recited in claim 1, wherein said generating a translation certificate step further comprises the substeps of:

computing and outputting a first public key that corresponds to said first secret key;

verifying said output re-encryption has a correct relationship with said first public key and a second public key by each of a plurality of proxy servers; and

verifying honesty of all of said plurality of proxy servers.

8. The method as recited in claim 7, wherein said verifying said output re-encryption step further comprises the substeps of:

selecting a first random value for each of said plurality of proxy servers;

computing a pair of challenges from a partial decryption of said input encryption for each of said plurality of proxy servers;

computing a first response responsive to said computed pair of challenges for each of said plurality of proxy servers;

outputting said partial decryption and said first response for each of said plurality of proxy servers;

selecting a second random value for each of said plurality of proxy servers;

computing a challenge from a partial re-encryption of said partial decryption for each of said plurality of proxy servers;

computing a second response responsive to said computed challenge for each of said plurality of proxy servers; and

outputting said partial re-encryption and said second response for each of said plurality of proxy servers.

9. The method recited in claim 8, wherein said verifying honesty step further comprises the substeps of:

verifying said translation certificate; and

if said translation certificate is valid, accepting all of said plurality of proxy servers are honest; and

if said translation certificate is not valid, replacing each of said plurality of proxy servers whose partial decryption and said partial re-encryption are not both verified as correct.

10. The method recited in claim 8, wherein said comparing said output re-encryption step and said verifying honesty step are performed in parallel by each of said plurality of proxy servers, and said generating said translation certificate step further comprises the substep of:

combining said first public key, said second public key, said partial decryptions, said first response, said partial re-encryption, and said second response in a transcript.

11. The method recited in claim 8, wherein said comparing said output re-encryption step and said verifying honesty step are performed in serial by each of said plurality of proxy servers, and said generating said translation certificate step comprises the substep of:

combining said first public key, said second public key, said partial decryptions, said first response, said partial re-encryption, and said second response in a transcript.

12. The method recited in claim 10 further comprising the substep of:

verifying said translation certificate is correct.

13. The method recited in claim 12, wherein said verifying said translation certificate step further comprises the substeps of:

re-computing a new pair of challenges from said partial decryption;

accepting a proving knowledge step as correct, if said re-computed new pair of challenges equals said computed pair of challenges;

re-computing a new challenge from said partial re-encryption;

accepting said proving said output re-encryption step as correct, if said re-computed new challenge equals said computed challenge; and

outputting an acceptance if both said proving knowledge step and said proving said output re-encryption step are correct, otherwise outputting a rejection.

14. The method recited in claim 11 further comprising the substep of:

verifying said translation certificate is correct.

15. The method recited in claim 14, wherein said verifying said translation certificate step further comprises the substeps of:

re-computing a new pair of challenges from said partial decryption;

accepting a proving knowledge step as correct, if said re-computed new pair of challenges equals said computed pair of challenges;

re-computing a new challenge from said partial re-encryption;

accepting said proving said output re-encryption step as correct, if said re-computed new challenge equals said computed challenge; and

outputting an acceptance if both said proving knowledge step and said proving said output re-encryption step are correct, otherwise outputting a rejection.

16. A computer-readable medium having computer executable instructions for performing the steps comprising:

receiving an input encryption having a first secret key;

outputting an output re-encryption of said input encryption, said output re-encryption having a second secret key; and

generating a translation certificate that verifies said input encryption and said output re-encryption are encryptions of an identical message.

17. The computer-readable medium of claim 16, wherein said generating a translation certificate step further comprises the substeps of:

computing and outputting a first public key that corresponds to said first secret key; and

verifying said output re-encryption has a correct relationship with said first public key and a second public key.

18. The computer-readable medium of claim 17, wherein said verifying said output re-encryption step further comprises the substeps of:

selecting a first random value;

computing a pair of challenges from a partial decryption of said input encryption;

computing a first response responsive to said computed pair of challenges; and

outputting said partial decryption and said first response;

selecting a second random value;

computing a challenge from a partial re-encryption of said partial decryption;

computing a second response responsive to said computed challenge; and

outputting said partial re-encryption and said second response.

19. The computer-readable medium of claim 18, wherein said generating said translation certificate step comprises the substep of:

combining said first public key, said second public key, said partial decryption, said first response, said partial re-encryption, and said second response in a transcript.

20. The computer-readable medium of claim 19, having further computer executable instructions for performing the substep comprising:

verifying said translation certificate is correct.

21. The computer-readable medium of claim 20, wherein said verifying said translation certificate step further comprises the substeps of:

re-computing a new pair of challenges from said partial decryption;

accepting a verifying knowledge step as correct, if said re-computed new pair of challenges equals said computed pair of challenges;

re-computing a new challenge from said partial re-encryption;

accepting said comparing said output re-encryption step as correct, if said re-computed new challenge equals said computed challenge; and

outputting an acceptance if both said verifying knowledge step and said comparing said output re-encryption step are correct, otherwise outputting a rejection.

22. The computer-readable medium of claim 16, wherein said generating a translation certificate step further comprises the substeps of:

computing and outputting a first public key that corresponds to said first secret key;

verifying said output re-encryption has a correct relationship with said first public key and a second public key by each of a plurality of proxy servers; and

verifying honesty of all of said plurality of proxy servers.

23. The computer-readable medium of claim 22, wherein said verifying said output re-encryption step further comprises the substeps of:

selecting a first random value for each of said plurality of proxy servers;

computing a pair of challenges from a partial decryption of said input encryption for each of said plurality of proxy servers;

computing a first response responsive to said computed pair of challenges for each of said plurality of proxy servers;

outputting said partial decryption and said first response for each of said plurality of proxy servers;

selecting a second random value for each of said plurality of proxy servers;

computing a challenge from a partial re-encryption of said partial decryption for each of said plurality of proxy servers;

computing a second response responsive to said computed challenge for each of said plurality of proxy servers; and

outputting said partial re-encryption and said second response for each of said plurality of proxy servers.

24. The computer-readable medium of claim 23, wherein said verifying honesty step further comprises the substeps of:

verifying said translation certificate; and

if said translation certificate is valid, accepting all of said plurality of proxy servers are honest; and

if said translation certificate is not valid, replacing each of said plurality of proxy servers whose partial decryption and said partial re-encryption are not both verified as correct.

25. The computer-readable medium of claim 23, wherein said comparing said output re-encryption step and said verifying honesty step are performed in parallel by each of said plurality of proxy servers, and said generating said translation certificate step further comprises the substep of:

combining said first public key, said second public key, said partial decryptions, said first response, said partial re-encryption, and said second response in a transcript.

26. The computer-readable medium of claim 23, wherein said comparing said output re-encryption step and said verifying honesty step are performed in serial by each of said plurality of proxy servers, and said generating said translation certificate step comprises the substep of:

combining said first public key, said second public key, said partial decryptions, said first response, said partial re-encryption, and said second response in a transcript.

27. The computer-readable medium of claim 25 further comprising the substep of:

verifying said translation certificate is correct.

28. The computer-readable medium of claim 27, wherein said verifying said translation certificate step further comprises the substeps of:

re-computing a new pair of challenges from said partial decryption;

accepting a proving knowledge step as correct, if said re-computed new pair of challenges equals said computed pair of challenges;

re-computing a new challenge from said partial re-encryption;

accepting said proving said output re-encryption step as correct, if said re-computed new challenge equals said computed challenge; and

outputting an acceptance if both said proving knowledge step and said proving said output re-encryption step are correct, otherwise outputting a rejection.

29. The computer-readable medium of claim 26, further comprising the substep of:

verifying said translation certificate is correct.

30. The computer-readable medium of claim 29, wherein said verifying said translation certificate step further comprises the substeps of:

re-computing a new pair of challenges from said partial decryption;

accepting a proving knowledge step as correct, if said re-computed new pair of challenges equals said computed pair of challenges;

re-computing a new challenge from said partial re-encryption;

accepting said proving said output re-encryption step as correct, if said re-computed new challenge equals said computed challenge; and

outputting an acceptance if both said proving knowledge step and said proving said output re-encryption step are correct, otherwise outputting a rejection.

31. A method for electronically providing publicly verifiable translation certificates comprising the steps of:

receiving an input encryption from a primary recipient by a plurality of proxy servers;

generating an output re-encryption of said input encryption by said plurality of proxy servers, said output re-encryption having a second secret key;

generating a translation certificate that proves said input encryption and said output re-encryption are encryptions of an identical message; and

transmitting said output re-encryption and said translation certificate to at least one secondary recipient.

32. The method of claim 31, wherein said plurality of proxy servers is equal to one, said creating said output re-encryption step comprises the substep of:

combining a second secret key with a partial re-encryption of a partial decryption of said input encryption to create said output re-encryption.

33. The method of claim 31, wherein said plurality of proxy servers is greater than one, said creating said output re-encryption step comprises the substeps of:

combining each of said plurality of proxy servers partial re-encryptions of each of said plurality of proxy servers own partial decryptions of said input encryption into a combined partial re-encryption; and

combining a second secret key with said combined partial re-encryption to create said output re-encryption.