Generating a secure signature utilizing a plurality of key shares

Patent metadata

Field	Value
Publication number	US-9894151-B2
Application number	US-201414147982-A
Country	US
Kind code	B2
Filing date	Jan 6, 2014
Priority date	Apr 1, 2011
Publication date	Feb 13, 2018
Grant date	Feb 13, 2018

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.

First claim

What is claimed is:

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 c

Assignees

• Cleversafe Inc
• IBM

Inventors

• Dhuse Greg
• Resch Jason K
• Leggette Wesley

Classifications

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H04L9/3247

  involving digital signatures · CPC title

• H04L67/1004 Primary

  Server selection for load balancing · CPC title

• H04L67/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 title

• H04L67/2847

  Electricity · mapped topic