GENERATING A SECURE SIGNATURE UTILIZING A PLURALITY OF KEY SHARES

• US 20140122891A1
• Filed: 01/06/2014
• Published: 05/01/2014
• Est. Priority Date: 04/01/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Resch, Jason K., Leggette, Wesley
• Granted Patent: US 9,894,151 B2
• Time in Patent Office: Days
• US Class Current: 713/176
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 67/1004 Server selection for load balancing
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467

Abstract

A method begins by a module to generate a secure signature on an item by selecting a first key representation index of a set of key representation indexes, wherein a first mathematical encoding of a private key generates a first plurality of key shares as a first key representation. The method continues with the module determining whether a first plurality of signature contributions have been received in response to a signature request for the item based on the first key representation index, wherein one of a first set of dispersed storage (DS) units executes a first mathematical signature function using one of the first plurality of key shares on the item to produce a signature contribution of the first plurality of signature contributions and when the first plurality of signature contributions have been received, generating the secure signature on the item from the first plurality of signature contributions.

Claims

1. A method for a device of a distributed storage network (DSN) to generate a secure signature on an item without a locally stored private key of the device, the method comprises:

selecting, by the device, a set of storage units of the DSN to perform the signature;

identifying, by the device and based on an association with the set of storage units, a key representation index for a key representation of the private key;

sending, by the device, a signature request, the key representation index, and an item to be signed to the set of storage units;

identifying, by each storage unit of the set of storage units, a key share of the key representation based on the key representation index;

generating, by each storage unit of the set of storage units, a signature contribution for the item to be signed using the key share; and

generating, by the device, a secure signature on the item based on the signature contributions of the set of storage units.

2. The method of claim 1, wherein the selecting the set of storage units further comprises at least one of:

selecting the set of the storage units based on reliability of the set of storage units; and

selecting the set of storage units based on performance of the set of storage units.

3. The method of claim 1, wherein the identifying the key representation index comprises:

selecting the key representation index from a plurality of key representation indexes, wherein the plurality of key representation indexes is for a plurality of key representations of the private key.

4. The method of claim 3 further comprises:

each of the plurality of key representations being a different mathematical encoding of the private key and including a plurality of key shares.

5. The method of claim 3 further comprises:

the pluralities of key shares of the plurality of key representations are stored in differing sets of storage units, wherein a storage unit is included in more than one set of the differing sets of storage units.

6. The method of claim 1, wherein the generating, by each storage unit of the set of storage units, a signature contribution comprises:

performing, by each storage unit of the set of storage units, a corresponding partial signature mathematical function to generate the signature contribution.

7. The method of claim 6, wherein the corresponding partial signature mathematical function comprises:

the signature contribution=(the item to be signed)^keyshare mod n, wherein n is a public modulus.

8. The method of claim 1 further comprises:

generating, by the device, the key representation by;

randomly generating one or more first values; and

generating a second value based on key share generating mathematical function of (x+y+z) mod Φ

(n)=d, where d is the private key, x and y correspond to the one or more first values, z corresponds to the second value, and Φ

(n) is an Euler'"'"'s totient function; and

sending the one or more first values and the second value to the set of storage units.

9. The method of claim 1 further comprises:

generating, by the device, the key representation by;

generating one or more third values;

generating a fourth value based on the one or more third values, the private key, and the key share generating mathematical function; and

sending the one or more third values and the fourth value to the set of storage units.

10. A computer readable storage medium comprises:

a first memory section storing operational instructions that, when executed by a computing device, causes the computing device to;

select a set of storage units of the DSN to perform a secure signature on an item without the computing device having a locally stored private key;

identify, based on an association with the set of storage units, a key representation index for a key representation of the private key;

send a signature request, the key representation index, and an item to be signed to the set of storage units;

a second memory section storing operational instructions that, when executed by a storage unit of the set of storage units, causes the storage unit to;

identify a key share of the key representation based on the key representation index;

generate a signature contribution for the item to be signed using the key share; and

a third memory section storing operational instructions that, when executed by the computing device, causes the computing device to;

generate a secure signature on the item based on the signature contributions of the set of storage units.

11. The computer readable storage medium of claim 10, wherein the first memory section further comprises operational instructions that, when executed by the computing device, causes the computing device to select the set of storage units further by at least one of:

selecting the set of the storage units based on reliability of the set of storage units; and

selecting the set of storage units based on performance of the set of storage units.

12. The computer readable storage medium of claim 10, wherein the first memory section further comprises operational instructions that, when executed by the computing device, causes the computing device to identify the key representation index by:

selecting the key representation index from a plurality of key representation indexes, wherein the plurality of key representation indexes is for a plurality of key representations of the private key.

13. The computer readable storage medium of claim 10 further comprises:

each of the plurality of key representations being a different mathematical encoding of the private key and including a plurality of key shares.

14. The computer readable storage medium of claim 10 further comprises:

the pluralities of key shares of the plurality of key representations are stored in differing sets of storage units, wherein a storage unit is included in more than one set of the differing sets of storage units.

15. The computer readable storage medium of claim 10, wherein the second memory section further comprises operational instructions that, when executed by the storage unit, causes the storage unit to generate the signature contribution by:

performing a corresponding partial signature mathematical function to generate the signature contribution.

16. The computer readable storage medium of claim 15, wherein the corresponding partial signature mathematical function comprises:

the signature contribution=(the item to be signed)^keyshare mod n, wherein n is a public modulus.

17. The computer readable storage medium of claim 10 further comprises:

a fourth memory section storing operational instructions that, when executed by the computing device, causes the computing device to generate the key representation by;

randomly generating one or more first values; and

generating a second value based on key share generating mathematical function of (x+y+z) mod Φ

(n)=d, where d is the private key, x and y correspond to the one or more first values, z corresponds to the second value, and Φ

(n) is an Euler'"'"'s totient function; and

sending the one or more first values and the second value to the set of storage units.

18. The computer readable storage medium of claim 10 further comprises:

a fourth memory section storing operational instructions that, when executed by the computing device, causes the computing device to generate the key representation by;

generating one or more third values;

generating a fourth value based on the one or more third values, the private key, and the key share generating mathematical function; and

sending the one or more third values and the fourth value to the set of storage units.