Keyed PV signatures

• US 9,088,419 B2
• Filed: 03/16/2012
• Issued: 07/21/2015
• Est. Priority Date: 03/18/2011
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Zaverucha, Gregory Marc, Vanstone, Scott Alexander
• Primary Examiner(s): CERVETTI, DAVID GARCIA
• Application Number:
  US13/422,941
• Publication Number:
  US 20120239930A1
• Time in Patent Office: 1,222 Days
• Field of Search: 713/168
• US Class Current: 1/1
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

A system and method enabling a recipient correspondent of a keyed PV signature to convert it to a signature with properties similar to a traditional signature (i.e., where the message is public and may be verified by anyone), removing the keyed aspect of the signature. The recipient correspondent may transfer the converted signature to a third party and provide the third party with a proof of knowledge such that the third party may be convinced that the originator of the signature signed the message.

Claims

1. A computer-implemented method of enabling a second correspondent device to prove to a third party the authenticity of a signed message received from a first correspondent device, the method comprising:

(a) obtaining the signed message at the second correspondent device comprising a confidential component;

(b) operating upon at least a portion of the signed message at the second correspondent device comprising the confidential component to generate a first value;

(c) generating a second value at the second correspondent device using the first value, a public value of the first correspondent device, and a private value of the second correspondent device;

(d) sending the second value by the second correspondent device to the third party, the third party coupled to the second correspondent device; and

(e) proving knowledge to the third party by the second correspondent of the private value of the second correspondent device by sending the second value for subsequent verification by the third party, the third party being configured to retrieve a decryption key from the second value to decrypt a portion of the signed message and accepting said portion as valid if decryption is successful.

2. The method according to claim 1 wherein the signed message further comprises one or more of:

a recoverable component, a visible component, or a combination thereof.

3. The method according to claim 2 wherein the recoverable component, the visible component, or both the recoverable component and the visible component are a predetermined string.

4. The method according to claim 2 wherein the signed message is generated according to an ECPVS scheme.

5. The method according to claim 1 wherein generating the second value comprises generating an intermediate value using the first value and the public value of the first correspondent device prior to using the private value of the second correspondent device.

6. The method according to claim 1 wherein proving knowledge to the third party comprises:

(a) computing a third value, and a fourth value using the first value and the public value of the first correspondent device;

(b) outputting a new signed message comprising the signed message, the second value, and a pair of proof of knowledge components comprising the third value and the fourth value, to enable the third party to verify the new signed message thereby verifying the authenticity of the signed message.

7. The method according to claim 6 wherein enabling the third party to verify the new signed message comprises:

(a) computing the first value;

(b) computing a fifth value using the first value and the public value of the first correspondent;

(c) computing representations of the third value and the fourth value using the proof of knowledge components and the fifth value;

(d) computing a representation of one of the pair of proof of knowledge components using the representations of the third value and the fourth value;

(e) comparing the representation of one of the pair of proof of knowledge components with a corresponding one of the pair of proof of knowledge components to verify the authenticity of the new signed message; and

(f) upon verifying the authenticity of the new signed message;

(i) computing a key using the second value; and

(ii) decrypting from the new signed message at least a portion of the signed message using the key.

8. The method according to claim 7 wherein at least the portion of the signed message has a characteristic enabling the third party to verify that it was generated by the first correspondent.

9. The method according to claim 8 wherein the characteristic is redundancy.

10. A device for proving to a third party the authenticity of a signed message received from a first correspondent, the device being associated with a second correspondent, the device comprising a processor configured for:

(a) obtaining the signed message at the device comprising a confidential component;

(b) operating upon at least a portion of the signed message comprising the confidential component to generate a first value;

(c) generating a second value using the first value, a public value of the first correspondent device, and a private value of the second correspondent device;

(d) sending the second value to the third party, the third party coupled to the second correspondent; and

(e) proving knowledge by the second correspondent to the third party of the private value of the second correspondent device by sending the second value for subsequent verification by the third party, the third party being configured to retrieve a decryption key from the second value to decrypt a portion of the signed message and accepting said portion as valid if decryption is successful.

11. The device according to claim 10 wherein the signed message further comprises one or more of:

a recoverable component, a visible component, or a combination thereof.

12. The device according to claim 11 wherein the recoverable component, the visible component, or both the recoverable component and the visible component are a predetermined string.

13. The device according to claim 11 wherein the signed message is generated according to an ECPVS scheme.

14. The device according to claim 10 wherein generating the second value comprises generating an intermediate value using the first value and the public value of the first correspondent device prior to using the private value of the second correspondent device.

15. The device according to claim 10 wherein proving knowledge to the third party comprises:

(a) computing a third value, and a fourth value using the first value and the public value of the first correspondent device;

(b) outputting a new signed message comprising the signed message, the second value, and a pair of proof of knowledge components comprising the third value and the fourth value, to enable the third party to verify the new signed message thereby verifying the authenticity of the signed message.

16. The device according to claim 15 wherein enabling the third party to verify the new signed message comprises enabling the third party to:

(a) compute the first value;

(b) compute a fifth value using the first value and the public value of the first correspondent;

(c) compute representations of the third value and the fourth value using the proof of knowledge components and the fifth value;

(d) compute a representation of one of the pair of proof of knowledge components using the representations of the third value and the fourth value;

(e) compare the representation of one of the pair of proof of knowledge components with a corresponding one of the pair of proof of knowledge components to verify the authenticity of the new signed message; and

(f) upon verifying the authenticity of the new signed message;

(i) compute a key using the second value; and

(ii) decrypt from the new signed message at least a portion of the signed message using the key.

17. The device according to claim 16 wherein at least the portion of the signed message has a characteristic enabling the third party to verify that it was generated by the first correspondent.

18. The device according to claim 17 wherein the characteristic is redundancy.

19. A non-transitory computer readable storage medium comprising computer executable instructions for enabling a second correspondent device to prove to a third party the authenticity of a signed message received from a first correspondent device said computer executable instructions comprising instructions for:

obtaining the signed message at the second correspondent device comprising a confidential component;

operating upon at least a portion of the signed message at the second correspondent device comprising the confidential component to generate a first value;

generating a second value at the second correspondent device using the first value, a public value of the first correspondent device, and a private value of the second correspondent device;

sending the second value by the second correspondent device to the third party, the third party coupled to the second correspondent device; and

proving knowledge to the third party by the second correspondent of the private value of the second correspondent device by sending the second value for subsequent verification by the third party, the third party being configured to retrieve a decryption key from the second value to decrypt a portion of the signed message and accepting said portion as valid if decryption is successful.