AGGREGATE SIGNATURE SCHEMES

• US 20080069347A1
• Filed: 09/10/2007
• Published: 03/20/2008
• 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, Vanstone, Scott
• Granted Patent: US 8,185,744 B2
• Time in Patent Office: Days
• US Class Current: 380/45
• 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 comprising generating a first signature component by encrypting a first portion of data using a first encryption key;

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

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

generating a third signature component by encrypting one of said first and second signature components using a second encryption key;

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 the other of said first and second signature components and said third and fourth signature components as said digital signature.

2. The method according to claim 1 comprising generating said first and second encryption keys 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 first and second signature components are generated by a first signing entity to produce a first representation of said digital signature;

and said third and fourth signature components are generated from said first representation by a second signing entity to produce a second representation of said digital signature.

6. The method according to claim 1 wherein said signature components are generated according to an ECPVS cryptographic scheme.

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

obtaining said digital signature, said digital signature having a first signature component encrypting at least one other signature component using respective encryption keys, a first of which encrypts a first portion of data, and having at least one secondary signature component, each being generated from either said first signature component or a respective one of said at least one other signature component and a respective private key;

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

using said recovered signature component to recover additional signature components corresponding to said at least one other signature component by generating one or more subsequent decryption keys;

recovering from said first of said at least one other signature components, 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 digital signature.

8. The method according to claim 7 wherein said decryption keys are generated by computing respective intermediate values from said first signature component or said at least one other signature component and said second portion of data;

converting said intermediate values to integer representations;

using said integer representations and public data to generate respective ephemeral public keys; and

generating said decryption keys from said ephemeral public keys.

9. The method according to claim 8 wherein said intermediate components are computed by hashing a respective signature component and 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 at a plurality of signing stages comprising generating an initial pair of signature components;

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

for subsequent signing stages, encrypting a previous signature component that in turn encrypts another previous signature component and generating an additional new signature component;

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

13. A method for generating an aggregate digital signature comprising generating a first signature component using a first value derived from first individual values contributed by each of a plurality of signers;

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

outputting said digital signature having said first and second signature components.

14. The method according to claim 13, said first signature component being 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 said plurality of signers;

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

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

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

17. The method according to claim 14 wherein said individual second components are each derived from respective private values of said plurality of signers.

18. The method according to claim 13, said first signature component being computed as a function of said first value, said first value being a combination of said first individual values;

and said second signature component being 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 each of said plurality of signers.

19. The method according to claim 18 wherein said first individual values are computed using respective ephemeral private keys generated by said plurality of signers.

20. The method according to claim 18 wherein said second signature is computed using a representation of a message being signed.

21. A method for verifying an aggregate digital signature comprising obtaining said digital signature having a first signature component generated using a first value derived from first individual values contributed by each of a plurality of signers and a second signature component generated using a second value derived from second individual values contributed by each said plurality of signers;

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

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

22. The method according to claim 21, said first signature component having 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 each said plurality of signers;

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

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

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

25. The method according to claim 21, said first signature component having been computed as a function of said first value, said first value being a combination of said first individual values;

and said second signature component having 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 each of said plurality of signers.