Generating a secure signature utilizing a plurality of key shares

• US 9,894,151 B2
• Filed: 01/06/2014
• Issued: 02/13/2018
• Est. Priority Date: 04/01/2011
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg, Resch, Jason K., Leggette, Wesley
• Primary Examiner(s): Pham, Luu
• Assistant Examiner(s): MALINOWSKI, WALTER J
• Application Number:
  US14/147,982
• Publication Number:
  US 20140122891A1
• Time in Patent Office: 1,499 Days
• Field of Search: 713176, 713171, 380278
• 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:

generating a first key representation of a private key 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 are one or more integers corresponding to the one or more first values, z is an integer corresponding to the second value, and Φ

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

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

selecting, by the device, a set of storage units of the DSN to perform the secure signature, wherein differing sets of storage units of the DSN store a plurality of key representations of the private key, including the first key representation and the second key representation;

identifying, by the device and based on an association with the set of storage units, a key representation index corresponding to a key representation of the plurality of key representations stored in the selected set of storage units, wherein a mathematical encoding is performed on the private key to produce a plurality of key shares, and wherein the plurality of key shares is referenced by the key representation index;

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 corresponding one of the plurality of key shares 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 corresponding one of the plurality of key shares; 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 of the DSN further comprises at least one of:

selecting the set of 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 corresponds to the 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 different plurality of key shares.

5. The method of claim 4 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 on the item using the corresponding one of the plurality of key shares 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, wherein generating a first key representation of the private key further includes:

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

9. The method of claim 1, wherein generating a second key representation of the private key further includes:

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

10. A non-transitory 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 a distributed storage network (DSN) to perform a secure signature on an item, wherein differing sets of storage units of the DSN store a plurality of key representations of a private key associated with the computing device, the plurality of key representations including at least a first key representation and a second key representation;

identify, based on an association with the set of storage units, a key representation index corresponding to a key representation of the plurality of key representations stored in the selected set of storage units, wherein a mathematical encoding is performed on the private key to produce a plurality of key shares, and wherein the plurality of key shares is referenced by the key representation index;

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 corresponding one of the plurality of key shares based on the key representation index;

generate a signature contribution for the item to be signed using the corresponding one of the plurality of key shares;

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

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

generate the first 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 are one or more integers corresponding to the one or more first values, z is an integer corresponding to the second value, and Φ

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

generate the second key representation by;

generating one or more third values; and

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

11. The non-transitory 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 of the DSN further by at least one of:

selecting the set of 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 non-transitory 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 corresponds to the plurality of key representations of the private key.

13. The non-transitory computer readable storage medium of claim 12 further comprises:

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

14. The non-transitory computer readable storage medium of claim 13 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 non-transitory 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 on the item using the corresponding one of the plurality of key shares to generate the signature contribution.

16. The non-transitory 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 non-transitory computer readable storage medium of claim 10, wherein the fourth memory section further comprises operational instructions that, when executed by the computing device, causes the computing device to send the one or more first values and the second value to the set of storage units.

18. The non-transitory computer readable storage medium of claim 10, wherein the fourth memory section further comprises operational instructions that, when executed by the computing device, causes the computing device to send the one or more third values and the fourth value to the set of storage units.