Aggregate signature schemes

• US 8,185,744 B2
• Filed: 09/10/2007
• Issued: 05/22/2012
• 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:
  US11/852,819
• Publication Number:
  US 20080069347A1
• Time in Patent Office: 1,716 Days
• Field of Search: 713/180, 340/12.51, 340/13.26
• US Class Current: 713/180
• 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 method for generating an aggregate digital signature, said method comprising:

obtaining, by a computing device, 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;

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

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

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

3. The method according to 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 method according to 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 method according to claim 1 wherein said second signature is provided as an input in generating a third signature by repeating said method.

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

7. A method for verifying an aggregate digital signature, said method comprising:

obtaining, by a computing device, 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;

 

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

 

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

8. The method according to 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 method according to claim 8 wherein said second intermediate component is computed by hashing a value comprising said second portion of data.

10. The method according to claim 7 wherein said predetermined characteristic is redundancy.

11. The method according to claim 7 wherein said decryption keys are generated using a key derivation function.

12. A method for generating an aggregate digital signature using a plurality of signing stages said method comprising:

obtaining, by a computing device, 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;

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

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

13. A method for generating an aggregate digital signature, said method comprising:

generating, by a computing device, 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;

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

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

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

15. The method according to 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 method according to claim 13 wherein said individual second components are each derived from respective private values of respective ones of said plurality of signers.

17. The method according to 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 method according to claim 17 wherein said first individual values are computed using respective ephemeral private keys generated by said plurality of corresponding signers.

19. The method according to claim 17 wherein said second signature component is computed using a representation of a message being signed.

20. A method for verifying an aggregate digital signature, said method comprising:

obtaining, by a computing device, 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;

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

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

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