Aggregate signature schemes

• US 8,634,559 B2
• Filed: 05/01/2012
• Issued: 01/21/2014
• Est. Priority Date: 09/08/2006
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Brown, Daniel R., Vanstone, Scott A.
• Primary Examiner(s): Gergiso, Techane
• Application Number:
  US13/461,586
• Publication Number:
  US 20120213366A1
• Time in Patent Office: 630 Days
• Field of Search: 380/270, 340/12.51
• US Class Current: 380/270
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes

Abstract

An authenticated RFID system is provided that uses elliptic curve cryptography (ECC) to reduce the signature size and read/write times when compared to traditional public key implementations such as RSA. Either ECDSA or ECPVS can be used to reduce the signature size and ECPVS can be used to hide a portion of the RFID tag that contains sensitive product identifying information. As a result, smaller tags can be used or multiple signatures can be written at different stages in a manufacturing or supply chain. A key management system is used to distribute the verification keys and aggregate signature schemes are also provided for adding multiple signatures to the RFID tags, for example in a supply chain.

Claims

1. A computing device configured to generate an aggregate digital signature, said computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said computing device is configured to:

obtain a first signature, said first signature comprising;

a first signature component which has been generated by encrypting a first portion of data using a first encryption key; and

a second signature component, said second signature component having been generated from a first intermediate signature component and a first private key, said first intermediate signature component having been generated from said first signature component and a second portion of data;

generate a third signature component by encrypting one of said first and second signature components using a second encryption key in the same manner as said first signature component encrypts said first portion of data;

generate a second intermediate signature component from said third signature component and said second portion of data;

generate a fourth signature component from said second intermediate signature component and a second private key; and

output a second signature as said aggregate digital signature, said second signature comprising the other of said first and second signature components, and said third and fourth signature components.

2. The computing device of claim 1, wherein said first and second encryption keys are generated by applying a key derivation function to respective ephemeral public keys.

3. The computing device of claim 1 wherein said first and second intermediate components are generated by hashing a combination of a respective signature component and said second portion of data.

4. The computing device of claim 1 wherein said second and fourth signature components are generated using integer representations of respective intermediate components, respective long term private keys, and respective ephemeral private keys.

5. The computing device of claim 1 wherein said second signature is provided as an input in generating a third signature by repeating said method.

6. The computing device of claim 1 wherein said signature components are generated according to an elliptic curve Pinstov-Vanstone signature (ECPVS) cryptographic scheme.

7. A computing device configured to verify an aggregate digital signature, said computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said computing device is configured to:

obtain said aggregate digital signature, said aggregate digital signature comprising;

a first signature component which encrypts one of a pair of signature components from another signature, said one of said pair of signature components encrypting a first portion of data;

a second signature component having been generated from a first intermediate signature component and a first private key, said first intermediate signature component having been generated from said first signature component and a second portion of data; and

the other of said pair of signature components;

generate a first decryption key using said first signature component and said second portion of data and decrypting said first signature component to obtain a recovered signature component representative of said one of said pair of signature components;

use said recovered signature component, said second portion of data, and the other of said pair of signature components to generate a second decryption key and decrypting said recovered signature component to obtain a representation of said first portion of data; and

examine said representation of said first portion of data for a predetermined characteristic to verify said aggregate digital signature.

8. The computing device of claim 7 wherein said second decryption key is generated by computing a second intermediate signature component;

converting said second intermediate signature component to an integer representation;

using said integer representation and public data to generate an ephemeral public key; and

generating said second decryption key from said ephemeral public key.

9. The computing device of claim 8 wherein said second intermediate component is computed by hashing a value comprising said second portion of data.

10. The computing device of claim 7 wherein said predetermined characteristic is redundancy.

11. The computing device of claim 7 wherein said decryption keys are generated using a key derivation function.

12. A computing device configured to generate an aggregate digital signature using a plurality of signing stages, said computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said computing device is configured to:

obtain a first signature comprising an initial pair of signature components;

encrypt one of said initial pair of signature components in a second signature comprising a next set of signature components, said next set of signature components including the other of said initial pair of components and at least two new signature components; and

for subsequent signing stages, encrypt a previous signature component that in turn encrypts another previous signature component;

generate an additional new signature component;

wherein the number of signature components in said aggregate digital signature at each stage is one more than the total number of signing stages; and

wherein said initial pair of signature components comprises a first signature component and a second signature component, said first signature component is computed by encrypting a first portion of data using said first value, said first value being an encryption key derived from individual encryption keys generated by each of a plurality of signers; and

wherein said second signature component is computed by combining individual second components derived from said first signature component and a second portion of data.

13. A computing device configured to generate an aggregate digital signature, said computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said computing device is configured to:

generate a first signature component using a first value derived from a plurality of first individual values contributed by respective ones of a plurality of signers;

generate a second signature component using a second value derived from a plurality of second individual values contributed by respective ones of said plurality of signers;

output said aggregate digital signature having said first and second signature components; and

wherein said first signature component is computed by encrypting a first portion of data using said first value, said first value being an encryption key derived from individual encryption keys generated by each of said plurality of signers; and

wherein said second signature component is computed by combining individual second components derived from said first signature component and a second portion of data.

14. The computing device of claim 13 wherein said individual encryption keys are derived from respective ephemeral keys derived by respective ones of said plurality of signers.

15. The computing device of claim 13 wherein said individual second components are each derived from an intermediate signature component computed by hashing a combination of said first signature component and said second portion of data.

16. The computing device of claim 13 wherein said individual second components are each derived from respective private values of respective ones of said plurality of signers.

17. The computing device of claim 13, wherein said first signature component is computed as a function of said first value, said first value being a combination of said first individual values;

and wherein said second signature component is computed using said second value and said first signature component, wherein said second value is a combined private key computed by combining private values from respective ones of said plurality of signers.

18. The computing device of claim 17 wherein said first individual values are computed using respective ephemeral private keys generated by said plurality of corresponding signers.

19. The computing device of claim 17 wherein said second signature component is computed using a representation of a message being signed.

20. A computing device configured to verify an aggregate digital signature, said computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said computing device is configured to:

obtain said aggregate digital signature having a first signature component generated using a first value derived from a plurality of first individual values contributed by respective ones of a plurality of signers, and a second signature component generated using a second value derived from a plurality of second individual values contributed by respective ones of said plurality of signers;

combine individual public values of respective ones of said plurality of signers to generate a combined public key;

use said combined public key in at least one step in a signature verification process; and

wherein said first signature component has been computed by encrypting a first portion of data using said first value, said first value being an encryption key derived from individual encryption keys generated by respective ones of said plurality of signers; and

wherein said second signature component has been computed by combining individual second components derived from said first signature component and a second portion of data.

21. The computing device of claim 20 wherein said combined public key is used in generating a representation of an ephemeral public key for generating a decryption key for decrypting said first portion of data from said first signature component.

22. The computing device of claim 21 wherein said representation of said ephemeral public key is computed using said second signature component and an integer representation of an intermediate signature component derived from said first signature component and said second portion of data.

23. The computing device of claim 20, wherein said first signature component has been computed as a function of said first value, said first value being a combination of said first individual values;

and wherein said second signature component has been computed using said second value and said first signature component, wherein said second value is a combined private key computed by combining private values from respective ones of said plurality of signers.

24. A non-transitory computer readable medium comprising instructions for generating an aggregate digital signature, said instructions executable by a computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said instructions comprise:

obtaining a first signature, said first signature comprising;

a first signature component which has been generated by encrypting a first portion of data using a first encryption key; and

a second signature component, said second signature component having been generated from a first intermediate signature component and a first private key, said first intermediate signature component having been generated from said first signature component and a second portion of data;

generating a third signature component by encrypting one of said first and second signature components using a second encryption key in the same manner as said first signature component encrypts said first portion of data;

generating a second intermediate signature component from said third signature component and said second portion of data;

generating a fourth signature component from said second intermediate signature component and a second private key; and

outputting a second signature as said aggregate digital signature, said second signature comprising the other of said first and second signature components, and said third and fourth signature components.

25. The non-transitory computer readable medium of claim 24, wherein said first and second encryption keys are generated by applying a key derivation function to respective ephemeral public keys.

26. The non-transitory computer readable medium of claim 24 wherein said first and second intermediate components are generated by hashing a combination of a respective signature component and said second portion of data.

27. The non-transitory computer readable medium of claim 24 wherein said second and fourth signature components are generated using integer representations of respective intermediate components, respective long term private keys, and respective ephemeral private keys.

28. The non-transitory computer readable medium of claim 24 wherein said second signature is provided as an input in generating a third signature by repeating said method.

29. The non-transitory computer readable medium of claim 24 wherein said signature components are generated according to an elliptic curve Pinstov-Vanstone signature (ECPVS) cryptographic scheme.

30. A non-transitory computer readable medium comprising instructions for verifying an aggregate digital signature, said instructions executable by a computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said instructions comprise:

obtaining said aggregate digital signature, said aggregate digital signature comprising;

a first signature component which encrypts one of a pair of signature components from another signature, said one of said pair of signature components encrypting a first portion of data;

a second signature component having been generated from a first intermediate signature component and a first private key, said first intermediate signature component having been generated from said first signature component and a second portion of data; and

the other of said pair of signature components;

generating a first decryption key using said first signature component and said second portion of data and decrypting said first signature component to obtain a recovered signature component representative of said one of said pair of signature components;

using said recovered signature component, said second portion of data, and the other of said pair of signature components to generate a second decryption key and decrypting said recovered signature component to obtain a representation of said first portion of data; and

examining said representation of said first portion of data for a predetermined characteristic to verify said aggregate digital signature.

31. The non-transitory computer readable medium of claim 30 wherein said second decryption key is generated by computing a second intermediate signature component;

converting said second intermediate signature component to an integer representation;

using said integer representation and public data to generate an ephemeral public key; and

generating said second decryption key from said ephemeral public key.

32. The non-transitory computer readable medium of claim 31 wherein said second intermediate component is computed by hashing a value comprising said second portion of data.

33. The non-transitory computer readable medium of claim 30 wherein said predetermined characteristic is redundancy.

34. The non-transitory computer readable medium of claim 30 wherein said decryption keys are generated using a key derivation function.

35. A non-transitory computer readable medium comprising instructions for generating an aggregate digital signature using a plurality of signing stages, said instructions executable by a computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said instructions comprise:

obtaining a first signature comprising an initial pair of signature components;

encrypting one of said initial pair of signature components in a second signature comprising a next set of signature components, said next set of signature components including the other of said initial pair of components and at least two new signature components; and

for subsequent signing stages, encrypting a previous signature component that in turn encrypts another previous signature component;

generating an additional new signature component;

wherein the number of signature components in said aggregate digital signature at each stage is one more than the total number of signing stages; and

wherein said initial pair of signature components comprises a first signature component and a second signature component, said first signature component is computed by encrypting a first portion of data using said first value, said first value being an encryption key derived from individual encryption keys generated by each of a plurality of signers; and

wherein said second signature component is computed by combining individual second components derived from said first signature component and a second portion of data.

36. A non-transitory computer readable medium comprising instructions for generating an aggregate digital signature, said instructions executable by a computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said instructions comprise:

generating a first signature component using a first value derived from a plurality of first individual values contributed by respective ones of a plurality of signers;

generating a second signature component using a second value derived from a plurality of second individual values contributed by respective ones of said plurality of signers;

outputting said aggregate digital signature having said first and second signature components; and

wherein said first signature component is computed by encrypting a first portion of data using said first value, said first value being an encryption key derived from individual encryption keys generated by each of said plurality of signers; and

wherein said second signature component is computed by combining individual second components derived from said first signature component and a second portion of data.

37. The non-transitory computer readable medium of claim 36 wherein said individual encryption keys are derived from respective ephemeral keys derived by respective ones of said plurality of signers.

38. The non-transitory computer readable medium of claim 36 wherein said individual second components are each derived from an intermediate signature component computed by hashing a combination of said first signature component and said second portion of data.

39. The non-transitory computer readable medium of claim 36 wherein said individual second components are each derived from respective private values of respective ones of said plurality of signers.

40. The non-transitory computer readable medium of claim 36, wherein said first signature component is computed as a function of said first value, said first value being a combination of said first individual values;

and wherein said second signature component is computed using said second value and said first signature component, wherein said second value is a combined private key computed by combining private values from respective ones of said plurality of signers.

41. The non-transitory computer readable medium 40 wherein said first individual values are computed using respective ephemeral private keys generated by said plurality of corresponding signers.

42. The non-transitory computer readable medium 40 wherein said second signature component is computed using a representation of a message being signed.

43. A non-transitory computer readable medium comprising instructions verifying an aggregate digital signature, said instructions executable by a computing device in communication with a radio frequency identification (RFID) device, said RFID device configured to at least one of read and write an RFID tag, and wherein said instructions comprise:

obtaining said aggregate digital signature having a first signature component generated using a first value derived from a plurality of first individual values contributed by respective ones of a plurality of signers, and a second signature component generated using a second value derived from a plurality of second individual values contributed by respective ones of said plurality of signers;

combining individual public values of respective ones of said plurality of signers to generate a combined public key;

using said combined public key in at least one step in a signature verification process; and

wherein said first signature component has been computed by encrypting a first portion of data using said first value, said first value being an encryption key derived from individual encryption keys generated by respective ones of said plurality of signers; and

wherein said second signature component has been computed by combining individual second components derived from said first signature component and a second portion of data.

44. The non-transitory computer readable medium of claim 43 wherein said combined public key is used in generating a representation of an ephemeral public key for generating a decryption key for decrypting said first portion of data from said first signature component.

45. The non-transitory computer readable medium of claim 44 wherein said representation of said ephemeral public key is computed using said second signature component and an integer representation of an intermediate signature component derived from said first signature component and said second portion of data.

46. The non-transitory computer readable medium of claim 43, wherein said first signature component has been computed as a function of said first value, said first value being a combination of said first individual values;

and wherein said second signature component has been computed using said second value and said first signature component, wherein said second value is a combined private key computed by combining private values from respective ones of said plurality of signers.