Efficient techniques for sharing a secret

A method performed by a custodian to share a secret S among n secret owners, the method comprising the steps of:

• choosing two large primes P and Q;
• computing a product N=PQ;
• computing a product M=(P−1)(Q−1);
• choosing n+1 random numbers q, through qn and d′ that are relatively prime to M;
• determining a number d such that a product of q1 through qn, d′, and d mod M equals one;
• computing s;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Sd and one of the numbers q1 through qn;
• and
• deleting the secret S, P, Q, M, q1 through qn, and d.

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;
• computing and storing a product N=PQ;
• computing and storing a product M=(P−1)(Q−1);
• choosing n random numbers e1 through en that are relatively prime to N;
• choosing another random number e that is relatively prime to N;
• choosing n numbers d1 through dn such that eidi mod M equals one for 1≦i≦n;
• choosing another number d such that ed mod M is equal to one;
• generating and storing a database of
• 9 [AutoLeftMatch] ( n k )
• values, where each value is the product of d and a unique k of the di numbers for 1≦i≦n;
• deleting P, Q, and M;
• computing Se;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Se and one of the numbers e1 through en;
• and
• deleting the secret S and e1 through en, e, d1 through dn, and d.

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;
• computing and storing a product N=PQ;
• computing and storing a product M=(P−1)(Q−1);
• choosing n random numbers e1 through e, that are relatively prime to N;
• choosing random numbers e and e′ that are relatively prime to N;
• choosing n numbers d1 through dn such that eidi 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
• 11 [AutoLeftMatch] ( n k )
• values, where each value is the product of d and a unique k of the di numbers for 1≦i≦n;
• deleting P, Q, and M;
• computing See′;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes See′ and one of the numbers e1 through en;
• and
• deleting the secret S and e1 through en, e, d1 through dn, and d.

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;
• and
• performing a forward k out of n secret sharing algorithm on the encrypted secret so as to generate n secret owner pieces.

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, the method comprising the steps of:

• choosing two large primes P and Q;
• computing a product N=PQ;
• computing a product M=(P−1)(Q−1);
• choosing n random numbers q1 through qn that are relatively prime to M;
• determining a number d such that a product of q1 through qn and d mod M equals one;
• computing Sd;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Sd and one of the numbers q1 through qn;
• and
• deleting the secret S, P, Q, M, q1 through qn, and d.

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, the method comprising the steps of:

• choosing two large primes P and Q;
• computing a product N=PQ;
• computing a product M=(P−1)(Q−1);
• choosing n+1 random numbers q1 through qn and d′ that are relatively prime to M;
• determining a number d such that a product of qn, through qn, d′, and d mod M equals one;
• computing Sd;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Sd and one of the numbers q1 through qn;
• and
• deleting the secret S, P, Q, M, q1 through qn, and d.

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;
• computing and storing a product N=PQ;
• computing and storing a product M=(P−1)(Q−1);
• choosing n random numbers e1 through en that are relatively prime to N;
• choosing another random number e that is relatively prime to N;
• choosing n numbers d, through d, such that eidi mod M equals one for 1≦i≦n;
• choosing another number d such that ed mod M is equal to one;
• generating and storing a database of
• 13 [AutoLeftMatch] ( n k )
• values, where each value is the product of d and a unique k of the di numbers for 1≦i≦n;
• deleting P, Q, and M;
• computing S;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Se and one of the numbers e1 through en;
• and
• deleting the secret S and e1 through en, e, d1 through dn, and d.

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;
• computing and storing a product N=PQ;
• computing and storing a product M=(P−1)(Q−1);
• choosing n random numbers e1 through en that are relatively prime to N;
• choosing random numbers e and e′ that are relatively prime to N;
• choosing n numbers d1 through dn such that eidi 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
• 14 [AutoLeftMatch] ( n k )
• values, where each value is the product of d and a unique k of the di numbers for 1≦i≦n;
• deleting P, Q, and M;
• computing See;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Se and one of the numbers e1 through en;
• and
• deleting the secret S and e1 through en, e, d1 through dn, and d.

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;
• and
• performing a forward k out of n secret sharing algorithm on the encrypted secret so as to generate n secret owner pieces.

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, the method comprising the steps of:

• choosing two large primes P and Q;
• computing a product N=PQ;
• computing a product M=(P−1)(Q−1);
• choosing n random numbers q, through qn that are relatively prime to M;
• determining a number d such that a product of q, through qn and d mod M equals one;
• computing Sd;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Sd and one of the numbers q1 through qn;
• and
• deleting the secret S, P, Q, M, q1 through qn, and d.

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, the method comprising the steps of:

• choosing two large primes P and Q;
• computing a product N=PQ;
• computing a product M=(P−1)(Q−1);
• choosing n+1 random numbers q1 through qn and d′ that are relatively prime to M;
• determining a number d such that a product of q1 through qn, d′, and d mod M equals one;
• computing Sd;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Sd and one of the numbers q1 through qn;
• and
• deleting the secret S, P, Q, M, q1 through qn, and d.

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;
• computing and storing a product N=PQ;
• computing and storing a product M=(P−1)(Q−1);
• choosing n random numbers e1 through en that are relatively prime to N;
• choosing another random number e that is relatively prime to N;
• choosing n numbers d1 through dn such that eidi mod M equals one for 1≦i≦n;
• choosing another number d such that ed mod M is equal to one;
• generating and storing a database of
• 15 [AutoLeftMatch] ( n k )
• values, where each value is the product of d and a unique k of the di numbers for 1≦i≦n;
• deleting P, Q, and M;
• computing Se;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes Se and one of the numbers e1 through en;
• and
• deleting the secret S and e1 through en, e, d1 through dn, and d.

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;
• computing and storing a product N=PQ;
• computing and storing a product M=(P−1)(Q−1);
• choosing n random numbers e1 through en that are relatively prime to N;
• choosing random numbers e and e′ that are relatively prime to N;
• choosing n numbers d1 through dn such that eidi 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
• 16 [AutoLeftMatch] ( n k )
• values, where each value is the product of d and a unique k of the di numbers for 1≦i≦n;
• deleting P, Q, and M;
• computing See′;
• distributing n secret owner pieces to each of the n secret owners, wherein each of the secret owner pieces includes See′ and one of the numbers e1 through en;
• and
• deleting the secret S and e1 through en, e, di through dn, and d.

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 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;
• and
• performing a forward k out of n secret sharing algorithm on the encrypted secret so as to generate n secret owner pieces.