System and method for processing a shared secret

• US 20040117649A1
• Filed: 10/16/2003
• Published: 06/17/2004
• Est. Priority Date: 04/27/2001
• Status: Active Grant

• Current Assignee: Verizon Ireland Ltd. (Verizon Communications Inc.)
• Original Assignee: Verizon Ireland Ltd. (Verizon Communications Inc.)
• Inventors: Whyte, William
• Granted Patent: US 8,718,283 B2
• Time in Patent Office: Days
• US Class Current: 713/200
• 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

Abstract

A method of constructing shares in a secret is disclosed. The method operates in a network comprising a number of computing devices, each arranged to securely store at least one share in the secret k for which n shares are required to reconstruct the secret and to which access to a number m of the shares can be reliably provided at any given time. The method comprises the steps of: determining n shares for an n-of-n secret sharing sheme, each share comprising a value y; storing at least some of the shares in the computing devices such that at least m of the n shares are reliably accessible; determining the shared secret k according to the shares y; determining a further (n-m) shares consistent with the shared secret k and the shares y; and storing the additional shares in a reliably accessible location.

Claims

1. In a network comprising a number of computing devices, each arranged to securely store at least one share in a secret k for which n shares are required to reconstruct the secret and to which access to a number m of said shares can be reliably provided at any given time, a method of constructing shares in a secret comprising the steps of:

determining n shares for an n-of-n secret sharing scheme, each share comprising a value y;

storing at least some of said shares in said computing devices such that at least m of said n shares are reliably accessible;

determining the shared secret k according to said shares y;

characterised by m being less than n and by the steps of;

determining a further (n-m) shares consistent with the shared secret k and the shares y; and

storing the additional shares in a reliably accessible location.

8. A computer program product for constructing a secret, said computer program product being arranged to perform the steps of claim 1.

10. A method as claimed in claim 1 wherein the step of determining n shares comprises:

determining n possibly arbitrary numbers w, said values y being calculated from said numbers w.

2. In a network comprising a number of computing devices, each arranged to securely store at least one share in a secret k for which n shares are required to reconstruct the secret and to which access to a number m of said shares can be reliably provided at any given time, a method of reconstructing said secret comprising the steps of:

securely obtaining m shares from one or more secret share holders including at least one of said computing devices;

characterised by m being less than n and by the steps of;

obtaining (n-m) shares from a reliably accessible location; and

constructing the shared secret k according to said obtained shares.

3. In a network comprising a number of computing devices, each arranged to securely store at least one share in a secret k for which n shares are required to reconstruct the secret and to which access to a number m of said shares can be reliably provided at any given time, a method of updating said secret comprising the steps of:

reconstructing said secret k according to the steps of claim 2;

deducing from the obtained shares the values of the shares for the unobtained n-m shares of the secret;

determining for each location from which a share was securely obtained a new share value y′

;

determining a new shared secret k′

according the new share values y′ and

the unobtained share values;

storing at least some of said new shares in said computing devices such that at least m of said new shares and said unobtained shares are reliably accessible;

generating additional (n-m) shares which are consistent with the new share values and the unobtained share values; and

storing the additional shares in a reliably accessible location.

4. A method according to claim 3 wherein said step of determining for each location from which a share was securely obtained a new share value y′

comprises;

generating said new shares y′ and

transmitting at least one new share y′

securely to one of the computing devices; and

requesting confirmation that they have been received.

5. A method according to claim 3 wherein said step of determining for each location from which a share was securely obtained a new share value y′

comprises;

requesting each location from which a share was securely obtained to generate and securely return a new share y′

.

9. A computer program product for re-constructing a secret, said computer program product being arranged to perform the steps of claim 2.

6. Apparatus for constructing shares in a secret and operable within a network comprising a number of computing devices, each arranged to securely store at least one share in a secret k for which n shares are required to reconstruct the secret and to which access to a number m of said shares can be reliably provided at any given time, comprising:

means for determining n shares for an n-of-n secret sharing scheme, each share comprising a value y;

means for causing at least some of said shares to be stored in said computing devices such that at least m of said n shares are reliably accessible;

means for determining the shared secret k according to said shares y;

characterised by m being less than n and by;

means for determining a further (n-m) shares consistent with the shared secret k and the shares y; and

means for causing the additional shares to be stored in a reliably accessible location.

7. Apparatus for reconstructing a secret and operable in a network comprising a number of computing devices, each arranged to securely store at least one share in a secret k for which n shares are required to reconstruct the secret and to which access to a number m of said shares can be reliably provided at any given time, comprising:

means for securely obtaining m shares from one or more secret share holders including at least one of said computing devices;

characterised by m being less than n and by;

means for obtaining (n-m) shares from a reliably accessible location; and

means for constructing the shared secret k according to said obtained shares.