Generating a secure signature utilizing a plurality of key shares

• US 8,627,091 B2
• Filed: 03/06/2012
• Issued: 01/07/2014
• Est. Priority Date: 04/01/2011
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Resch, Jason K., Leggette, Wesley
• Primary Examiner(s): Nalven, Andrew L
• Assistant Examiner(s): MALINOWSKI, WALTER J
• Application Number:
  US13/413,232
• Publication Number:
  US 20120254619A1
• Time in Patent Office: 672 Days
• Field of Search: None
• 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 a first key representation index of a set of key representation indexes,

wherein the first key representation index includes information regarding a first key representation of a set of key representations,

wherein a first mathematical encoding of the private key generates a first plurality of key shares as the first key representation, which is stored in a first set of dispersed storage (DS) units of the DSN, and a second mathematical encoding of the private key generates a second plurality of key shares as a second key representation of the set of key representations, which is stored in a second set of dispersed storage (DS) units of the DSN;

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 the first set of 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, wherein;

the first mathematical encoding includes;

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 first set of DS units;

the second mathematical encoding includes;

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 second set of DS units; and

after generating the set of key representations, destroying the private key.

2. The method of claim 1 further comprises:

when the first plurality of signature contributions have not been received;

generating second signature requests for the item based on a second key representation index of the set of key representation indexes;

sending the second signature requests to the second set of DS units;

determining whether a second plurality of signature contributions have been received from the second set of DS units; and

when the second plurality of signature contributions have been received, generating the secure signature on the item from the second plurality of signature contributions.

3. The method of claim 1, wherein the generating the secure signature on the item comprises:

multiplying the first plurality of signature contributions to produce a multiplication result; and

performing a modulus function on the multiplication result to produce the secure signature.

4. The method of claim 1, wherein the signature request comprises:

a set of signature requests, wherein each signature request of the set of signature requests includes one or more of a first key representation identifier (ID), a signature payload, a hash of the signature payload, a DS unit ID, and a public modulus value.

5. The method of claim 1, wherein the item comprises one or more of:

a data element that includes one or more of registry information, key information, encryption algorithm information, a device certificate, a user certificate, and a system element identifier, and a DSN access request; and

a hash of the data element.

6. The method of claim 1 further comprises:

determining whether the secure signature is valid; and

when the secure signature is not valid;

generating second signature requests for the item based on a second key representation index of the set of key representation indexes;

sending the second signature requests to the second set of DS units;

determining whether a second plurality of signature contributions have been received from the second set of DS units; and

when the second plurality of signature contributions have been received, generating the secure signature on the item from the second plurality of signature contributions.

7. The method of claim 1, wherein the selecting the first key representation index comprises:

selecting the first key representation index based on one or more of;

DS unit status indicators of the first and second sets of DS units, DS unit performance level indicators of the first and second sets of DS units, DS unit retrieval history indicators of the first and second sets of DS units, a security indicator, a query, a command, a key share storage table lookup, and a message.

8. A module to enable 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 module comprises:

a first module operable to select a first key representation index of a set of key representation indexes,

wherein the first key representation index includes information regarding a first key representation of a set of key representations,

wherein a first mathematical encoding of the private key generates a first plurality of key shares as the first key representation, which is stored in a first set of dispersed storage (DS) units of the DSN, and a second mathematical encoding of the private key generates a second plurality of key shares as a second key representation of the set of key representations, which is stored in a second set of dispersed storage (DS) units of the DSN;

a second module operable to determine 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 the first set of 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, a third module operable to generate the secure signature on the item from the first plurality of signature contributions,

wherein;

the first mathematical encoding includes;

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 first set of DS units;

the second mathematical encoding includes;

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 second set of DS units; and

after generating the set of key representations, destroying the private key.

9. The module of claim 8 further comprises:

when the first plurality of signature contributions have not been received;

the second module is further operable to;

generate second signature requests for the item based on a second key representation index of the set of key representation indexes;

send the second signature requests to the second set of DS units;

determine whether a second plurality of signature contributions have been received from the second set of DS units; and

when the second plurality of signature contributions have been received, the third module is further operable to generate the secure signature on the item from the second plurality of signature contributions.

10. The module of claim 8, wherein the third module functions to generate the secure signature on the item by:

multiplying the first plurality of signature contributions to produce a multiplication result; and

performing a modulus function on the multiplication result to produce the secure signature.

11. The module of claim 8, wherein the signature request comprises:

a set of signature requests, wherein each signature request of the set of signature requests includes one or more of a first key representation identifier (ID), a signature payload, a hash of the signature payload, a DS unit ID, and a public modulus value.

12. The module of claim 8, wherein the item comprises one or more of:

a data element that includes one or more of registry information, key information, encryption algorithm information, a device certificate, a user certificate, and a system element identifier, and a DSN access request; and

a hash of the data element.

13. The module of claim 8 further comprises:

a fifth module operable to determine whether the secure signature is valid; and

when the secure signature is not valid;

the second module further operable to;

generate second signature requests for the item based on a second key representation index of the set of key representation indexes;

send the second signature requests to the second set of DS units;

determine whether a second plurality of signature contributions have been received from the second set of DS units; and

when the second plurality of signature contributions have been received, the third module further operable to generate the secure signature on the item from the second plurality of signature contributions.

14. The module of claim 8, wherein the first module functions to select the first key representation index by:

selecting the first key representation index based on one or more of;

DS unit status indicators of the first and second sets of DS units, DS unit performance level indicators of the first and second sets of DS units, DS unit retrieval history indicators of the first and second sets of DS units, a security indicator, a query, a command, a key share storage table lookup, and a message.