Patent ID: 7167565

Claim:
A method performed by a custodian computing system, having memory, to share a secret S among n secret owners such that any k of the n secret owners may reconstruct the secret S, the method comprising the steps of: choosing two large primes P and Q, such that PQ is greater than S when S is a number; storing in the custodian computer system memory a product N=PQ; storing a product M=(P−1)(Q−1); choosing n random numbers e 1 through e n that are relatively prime to N; choosing another random number e that is relatively prime to N; choosing n numbers d 1 through d n such that e i d i mod M equals one for 1≦i≦n; choosing another number d such that ed mod M is equal to one; storing a database of ( n k ) entries, where each entry is associated with a unique combination of the ( n k ) possible combinations of the k secret owners, and wherein a particular entry includes a value, c, that is the product of modulus M of d and the d i values for i indices that correspond to the particular secret owners present in the unique combination for that particular entry, wherein c corresponds to modulus M of the product kd i ; computing S e ; deleting from the custodian computer memory P, Q, and M; distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes S e and one of the numbers e 1 through e n ; deleting the secret S and e 1 through e n , e, d 1 through d n , and d; receiving k secret owner values from a unique combination of k secret owners; determining the value c that is associated with the unique combination; and determining the secret S using the value c retrieved from the database entry corresponding to the k secret owners whose secret owner pieces have been received and S e mod N.