Keyed PV Signatures

• US 20120239930A1
• Filed: 03/16/2012
• Published: 09/20/2012
• Est. Priority Date: 03/18/2011
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited), Research In Motion Limited (Blackberry Limited)
• Inventors: VANSTONE, Scott Alexander, ZAVERUCHA, Gregory Marc
• Granted Patent: US 9,088,419 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• 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 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 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; and

(e) proving knowledge to the third party of the private value.

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 further comprising the third party obtaining the second value, generating a key using the second value, and using the key to decrypt at least a portion of the signed message.

7. 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.

8. The method according to claim 7 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.

9. The method according to claim 8 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.

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

11. 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 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; and

(e) proving knowledge to the third party of the private value.

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

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

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

14. The device according to claim 12 wherein the signed message is generated according to an ECPVS scheme.

15. The device according to claim 11 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.

16. The device according to claim 11 wherein sending the second value to the third party enables the third party to generate a key using the second value and use the key to decrypt at least a portion of the signed message.

17. The device according to claim 11 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.

18. The device according to claim 17 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.

19. The device according to claim 18 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.

20. The device according to claim 19 wherein the characteristic is redundancy.