Efficient techniques for sharing a secret
View Patent ↗An n person secret sharing solution computes n unique keys to be distributed to the secret owners along with an exponentiated version of the secret. The custodian performs an exponent/modulo operation each time one of the keys is received from one of the secret owners. Alternatively, n+1 keys are created by the custodian, and the custodian retains one key after distributing the remaining n keys to the secret owners. After the custodian has received and processed the n keys from the secret owners, he performs an exponent/modulo operation using his own retained key. According to another aspect, a k out of n secret sharing solution involves computing and storing a database having an entry for each unique combination of k keys that could be returned from among the n keys. After k keys have been received, the custodian looks up in the database the entry corresponding to the particular unique combination of secret owners who returned keys. The custodian performs another exponent/modulo operation using the entry retrieved from the database in order to reconstruct the original secret. According to an embodiment, the custodian computes n+1 keys, distributes n of the keys to the secret owners, and keeps one of the keys for himself. The custodian retrieves his own key and performs a final exponent/modulo operation in order to reconstruct the original secret. According to another aspect, a k out of n secret sharing solution involves encrypting the original secret before applying any conventional k out of n secret sharing solution.
1. 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.
2. A method as in claim 1 , wherein receiving k secret owners values from the unique combination of k secret owners comprises:
receiving a first of the n secret owner pieces from one of the n secret owners; and
computing and storing S′=S ef mod N, where f represents the one of the numbers e 1 through e n contained in the first of the n secret owner pieces.
3. A method as in claim 2 , wherein receiving k secret owner values from the unique combination of k secret owners comprises:
receiving a second of the n secret owner pieces from another one of the n secret owners;
computing S′ q mod N, where q represents the one of the numbers e 1 through e n contained in the second of the n secret owner pieces; and replacing S′ with S′ q mod N.
4. A method as in claim 3 , wherein receiving k secret owner values from the unique combination of k secret owners comprises:
each time another of the secret owner pieces is received from another one of the n secret owners;
computing S′ q mod N, where q represents the one of the numbers e 1 through e n contained in the another of the n secret owner pieces; and replacing S′ with S′ q mod N.
5. A method as in claim 4 , further comprising the steps of:
after k secret owner pieces have been received,
retrieving from the database a value c from among the
(
n
k
)
values, wherein the value c corresponds to the k secret owner pieces of the unique combination of k secret owners that were received by the custodian;
computing S′ c mod N; and
replacing S′ with S′ c mod N.
6. 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, the method comprising the steps of:
choosing two large primes P and Q, such that PQ is greater than S where S is a number;
storing in the custodian computer 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 random numbers e and e′ that are 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 numbers d and d′ such that ed mod M is equal to one and such that e′d′ mod M is equal to one;
storing a database of
(
n
k
)
entries, wherein 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 ee′ ;
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 ee′ 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;
retrieving from the database the value c that is associated with the unique combination; and
determining the secret S using the value c and the k secret owner value.
7. A method as in claim 6 , wherein receiving k secret owner values from the unique combination of k secret owners comprises:
receiving a first of the n secret owner pieces from one of the n secret owners; and
computing and storing S′=S ee′f mod N, where f represents the one of the numbers e 1 through e n contained in the first of the n secret owner pieces.
8. A method as in claim 7 , wherein receiving k secret owner values from the unique combination of k secret owners comprises:
receiving a second of the n secret owner pieces from another one of the n secret owners;
computing S′ q mod N, where q represents the one of the numbers e 1 through e n contained in the second of the n secret owner pieces; and replacing S′ with S′ q mod N.
9. A method as in claim 8 , wherein receiving k secret owner values from the unique combination of k secret owners comprises:
each time another of the secret owner pieces is received from another one of the n secret owners;
computing S′ q mod N, where q represents the one of the numbers e 1 through e n contained in the another of the n secret owner pieces; and replacing S′ with S′ q mod N.
10. A method as in claim 9 , further comprising the steps of:
after k secret owner pieces have been received,
retrieving from the database the value c from among the
(
n
k
)
values, wherein the value c corresponds to the k secret owner pieces from the unique combination of k secret owner that were received by the custodian;
computing S′ c mod N;
replacing S′ with S′ c mod N;
computing S′ d′ mod N; and
replacing S′ with S′ d′ mod N.
11. A method performed by a custodian computing system, having memory, to share a secret among n secret owners such that any k of the n secret owners may reconstruct the secret, the method comprising the steps of:
encrypting the secret so as to generate an encrypted secret;
deleting from the custodian computer memory the secret; and
performing a forward k out of n secret sharing algorithm on the encrypted secret so as to generate n secret owner pieces;
storing in a database a plurality of entries associated with a plurality of unique combinations of k secret owners of the n secret owners, wherein a particular entry includes a value, c, that is a product of modulus M of d and 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 ;
distributing the n secret owner pieces to the n secret owners;
receiving k secret owner values from a unique combination of k secret owners;
retrieving from the database a value c that is associated with the unique combination;
performing a reverse k out of n secret sharing algorithm on the k secret owner pieces so as to recreate the encrypted secret using the value c; and
decrypting the encrypted secret so as to recreate the secret.
12. A method as in claim 11 , wherein the step of performing a forward k out of n secret sharing algorithm includes the steps of:
dividing the encrypted secret into k pieces; and
performing n polynomial evaluations at n points of a degree-k polynomial using the k pieces of the encrypted secret as polynomial coefficients;
wherein each of the k secret owner pieces includes a result of one of the n polynomial evaluations and a corresponding one of the n points.
13. A method as in claim 12 , wherein the step of performing a reverse k out of n secret sharing algorithm includes the steps of generating a system of k linear equations and solving the system of k linear equations for the k pieces of the encrypted secret.
14. A method as in claim 13 , further comprising the step of:
assembling the k pieces of the encrypted secret so as to recreate the encrypted secret.
15. A computer readable storage medium having embodied thereon computer readable program code suitable for programming a computer to perform a method performed by a custodian to share a secret S among n secret owners such that any k of the n secret owners may reconstruct the secret, the method comprising the steps of:
choosing two large primes P and Q, such that PQ is greater than S where S is a number;
computing and storing a product N=PQ;
computing and 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, wherein 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 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;
retrieving from the database one of the values c that is associated with the unique combination; and
determining the secret S using the value c and the k secret owner values.
16. A computer readable storage medium having embodied thereon computer readable program code suitable for programming a computer to perform a method performed by a custodian to share a secret S among n secret owners such that any k of the n secret owners may reconstruct the secret, the method comprising the steps of:
choosing two large primes P and Q, such that PQ is greater than S where S is a number;
storing 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 random numbers e and e′ that are 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 numbers d and d′ such that ed mod M is equal to one and such that e′d′ mod M is equal to one;
generating and storing a database of
(
n
k
)
values, where each value is the product of d and a unique k of the d i numbers for 1≦i≦n, wherein each value is associated with a unique combination of k secret owners of the n secret owners;
storing a database of
(
n
k
)
entries, wherein 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 ee′ ;
deleting 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 ee′ 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;
retrieving from the database one of the values c that is associated with the unique combination; and
determining the secret S using the value c and the k secret owner values.
17. A computer readable storage medium having embodied thereon computer readable program code suitable for programming a computer to perform a method performed by a custodian to share a secret among n secret owners such that any k of the n secret owners may reconstruct the secret, the method comprising the steps of:
encrypting the secret so as to generate an encrypted secret;
deleting the secret;
performing a forward k out of n secret sharing algorithm on the encrypted secret so as to generate n secret owner pieces;
storing in a database a plurality of entries associated with a plurality of unique combinations of k secret owners of the n secret owners, wherein a particular entry includes a value, c, that is a product of modulus M of d and 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 ;
distributing the n secret owner pieces to the n secret owners;
receiving k secret owner values from a unique combination of k secret owners;
retrieving from the database one of the values c that is associated with the unique combination;
performing a reverse k out of n secret sharing algorithm on the k secret owner pieces so as to recreate the encrypted secret using the value c; and
decrypting the encrypted secret so as to recreate the secret.
18. A computer comprising a processor and a computer readable storage medium coupled to the processor having embodied thereon processor readable program code suitable for programming a computer to perform a method performed by a custodian to share a secret S among n secret owners such that any k of the n secret owners may reconstruct the secret, the method comprising the steps of:
choosing two large primes P and Q, such that PQ is greater than S where S is a number;
storing a product N=PQ;
storing 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, wherein 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 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;
retrieving from the database one of the a values c that is associated with the unique combination; and
determining the secret S using the value c and the k secret owner values.
19. A computer comprising a processor and a computer readable storage medium coupled to the processor having embodied thereon processor readable program code suitable for programming the computer to perform a method performed by a custodian to share a secret S among n secret owners such that any k of the n secret owners may reconstruct the secret, the method comprising the steps of:
choosing two large primes P and Q, such that PQ is greater than S where S is a number;
storing 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 random numbers e and e′ that are 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 numbers d and d′ such that ed mod M is equal to one and such that e′d′ mod M is equal to one;
generating and storing a database of
(
n
k
)
values, where each value is the product of d and a unique k of the d i numbers for 1≦i≦n, wherein each value is associated with a unique combination of k secret owners of the n secret owners;
storing a database of
(
n
k
)
entries, wherein 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 ee′ ;
deleting P, Q, and M;
distributing n secret owner pieces to each of then secret owners, wherein each of the secret owner pieces includes S ee′ 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;
retrieving from the database one of the values c that is associated with the unique combination; and
determining the secret S using the value c and the k secret owner values.
20. A computer comprising a processor and a computer readable storage medium coupled to the processor having embodied thereon processor readable program code suitable for programming the computer to perform a method performed by a custodian to share a secret among n secret owner such that any k of the n secret owners may reconstruct the secret, the method comprising the steps of:
encrypting the secret so as to generate an encrypted secret;
deleting the secret;
performing a forward k out of n secret sharing algorithm on the encrypted secret so as to generate n secret owner pieces;
storing in a database a plurality of entries associated with a plurality of unique combinations of k secret owners of the n secret owners, wherein a particular entry includes a value, c, that is a product of modulus M of d and 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 ;
distributing the n secret owner pieces to the n secret owners;
receiving k secret owner values from a unique combination of k secret owners;
retrieving from the database one of the values c that is associated with the unique combination;
performing a reverse k out of n secret sharing algorithm on the k secret owner pieces so as to recreate the encrypted secret using the value c; and
decrypting the encrypted secret so as to recreate the secret.