Techniques for validating and sharing secrets

• US 8,170,216 B2
• Filed: 06/18/2008
• Issued: 05/01/2012
• Est. Priority Date: 06/18/2008
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Vishnu, Vardhan Itta, Puthali, H. B.
• Primary Examiner(s): Laforgia, Christian
• Assistant Examiner(s): WANG, HARRIS C
• Application Number:
  US12/141,286
• Publication Number:
  US 20100005302A1
• Time in Patent Office: 1,413 Days
• Field of Search: 380/286
• US Class Current: 380/286
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

Techniques for validating and sharing secrets are presented. A secret is divided into a plurality of parts. Each part is represented by a unique value. Each value is distributed to a unique user that shares in the secret. The secret is recreated when each user presents each user'"'"'s unique value. Each unique value is then used to recreate its corresponding part of the key and when all parts are present and validated, the secret is reproduced.

Claims

1. A machine-implemented method residing in a non-transitory computer-readable medium and for execution on a processing device, comprising:

deciding, by the processing device, to divide a secret among a first total number of users;

separating, by the processing device, the secret into shares, each share a different piece of the secret and a total number of the shares generated is equal to the first total number, separating further includes;

generating a share set of pairwise co-prime numbers, one share set pairwise co-prime number per share and per user;

producing an intermediate value for each share as a remainder that is obtained when the secret is divided by that share'"'"'s pairwise co-prime number; and

retaining each intermediate value for subsequent independent validation of each share;

producing an intermediate value for each share as a remainder that is obtained when the secret is divided by that share'"'"'s pairwise co-prime number; and

retaining each intermediate value for subsequent independent validation of each share;

calculating, on the processing device and for each share, a single value that permits each share to be independently validated from remaining shares and that permits each share to be re-assembled with the remaining shares to reform the secret, the calculating further includes;

processing a Chinese Remainder Theorem (CRT) algorithm for each share and that share'"'"'s intermediate value and that share'"'"'s pairwise co-prime number;

producing a single CRT value for each share in response to processing the CRT algorithm; and

representing the CRT value as the single value that is delivered to each user and processing the CRT algorithm further includes;

generating a first equation via the CRT algorithm that produces as a first remainder the intermediate value when the CRT value is divided by a pre-established pairwise co-prime number;

generating a second equation via the CRT algorithm that produces as a second remainder a particular share'"'"'s pairwise co-prime number when the CRT value is divided by another pre-established pairwise co-prime number; and

generating a third equation via the CRT algorithm that produces as a third remainder a control value when the CRT value is divided by a control pairwise co-prime number; and

delivering, by the processing device, each single value for each share to a particular one of the users, wherein the users share the secret via each user'"'"'s single value.

2. The method of claim 1, wherein deciding further includes evaluating policy to determine when to divide the secret.

3. The method of claim 1, wherein calculating further includes subsequently validating a particular share from a particular user when that particular user presents a particular single value, and using the particular single value to process the first equation and the second equation to obtain a particular intermediate value and a particular share'"'"'s pairwise co-prime number and then dividing the secret by the particular share'"'"'s pairwise co-prime number and comparing a resulting remainder against the particular intermediate value.

4. The method of claim 3 further comprising, invalidating the particular share when the resulting remainder does not equal the particular intermediate value, and wherein when the resulting remainder does equal the particular intermediate value delivering the secret to a requestor when each of the remaining shares of the secret are presented and similarly validated.

5. A machine-implemented system, comprising:

a key dividing service implemented in a non-transitory computer-readable storage medium as instructions that process on a machine; and

a key validation service implemented in a non-transitory computer-readable storage medium as instructions that process on the machine or a different machine of a network;

wherein the key dividing service splits a shared key into shares, each share corresponds to a particular user and a total number of shares is equal to a total number of the users, and wherein the key dividing service supplies a unique value to each of the users to represent each user'"'"'s share, and wherein the key validation service validates each unique value and reconstructs each share from each unique value and the key validation service reproduces the shared key when each share is successfully reconstructed and validated, wherein the key dividing service processes a Chinese Remainder Theorem (CRT) algorithm to produce each unique value for each user, and wherein the CRT algorithm produces three equations for each unique value, a first equation provides a particular share of the shared key, a second equation provides a pairwise co-prime that when used as a divisor to the shared key produces the particular share, and a third equation provides a control value that validates each unique value to ensure no changes have occurred.

6. The system of claim 5, wherein the key validation service processes a Chinese Remainder Theorem (CRT) algorithm to validate each unique value and to reconstruct each share of the shared key.

7. The system of claim 5, wherein the key validation service is unable to reconstruct the shared key when less than the total number of shares are received for processing.

8. The system of claim 5, wherein the shared secret is completely reconstructed by the key validation service for each unique value but is not supplied to a requestor unless the total number of unique values are received representing the total number of shares and is not supplied to the requestor unless each share is validated via each unique value.