Secret sharing system and storage medium

• US 6,810,122 B1
• Filed: 01/20/2000
• Issued: 10/26/2004
• Est. Priority Date: 07/23/1999
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sakurai, Kouichi, Miyazaki, Shingo
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): WU, ALLEN S
• Application Number:
  US09/488,006
• Time in Patent Office: 1,741 Days
• Field of Search: 380/42, 380/283, 380/30, 380/285, 380/286, 380/277, 705/71, 705/57, 705/80
• US Class Current: 380/30
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A secret sharing system and a storage medium where each of the n shareholders P1 to Pn holds a (n, n) share di (0≦i≦n), turns the share di into t(r+1) partial random numbers Sj of the (t, n) type, shares r+1 partial random numbers Sj to the respective shareholders P1 to Pn on the basis of a t-ary representation (value k at the t^j-th digit, 0≦k≦t−1, 0≦j≦r) of the identification number z of each of the shareholders Pi, and puts together the shared partial random numbers for each digit t^j in the t-ary representation to obtain r+1 shares d_j,k. Then, the user unit U selects t shareholders T_Z and transmits encrypted data C to the selected t shareholders T_Z. The t shareholders Tz perform an operation on the encrypted data C on the basis of the share d_j,k to obtain partial outputs X_Z and return the partial outputs X_Z to the user unit U. Then, the user unit U combines the t partial outputs X_Z to obtain the result of decryption.

Claims

1. A t-of-n secret sharing system which is applied to an RSA crypto system using a public, key and a secret key d, the secret sharing system including n shareholders connected to each other via a network and a user unit and, when partial final information about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create at least one of a result of decryption and a result of signature without computing said secret key d, wherein

each of said n shareholders comprises

means for creating said public key and said secret key d,

means for holding n-out-of-n partial information di (0≦

i≦

n) created based on the secret key d,

means for, if smallest integer equal to or larger than logarithm of n to a base t is r, turning said partial information di into t(r+1) partial random numbers of t-of-n type and sharing r+1 out of the t(r+1) partial random numbers to the respective shareholders based on a t-ary representation of value k at the t^j-th digit (0≦

k≦

t−

1, 0≦

j≦

r) of identification number of each of said shareholders,

means for putting together n(r+1) partial random numbers shared by said shareholders for each digit t^j in the t-ary representation and obtaining r+1 pieces of partial final information d_j,k,

means for performing an operation on the data to be processed received from said user unit on the basis of said partial final information d_j,k and returning the obtained partial output to said user unit, and

said user unit comprises

means for selecting said t shareholders and transmitting data to be processed to the selected t shareholders, and

means for combining the partial outputs received from said t shareholders and obtaining said result of decryption or said result of signature,

wherein the means for selecting said t shareholders further comprises;

means for providing t-ary representation of identification numbers of t shareholders,

means for determining whether or not a digit of the t-ary representation meets a condition that a value, calculated by a predetermined condition, in the t-ary representation, differs for each digit in the t-ary representation for the t-shareholders, and means for selecting t shareholders which meet the condition.

2. A t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system including n shareholders connected to each other via a network and a user unit and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of decryption without computing said secret key d, wherein

each of said n shareholders comprises

means for performing an operation on data C2=M^e (mod N) to be decrypted received from said user unit to produce a partial output Zj and returning the partial output Zj to said user unit by using the share about the secret key and the second public key, and

said user unit comprises

means for selecting t shareholders out of said n shareholders and transmitting said data C2 to be decrypted to the selected t shareholders,

means for combining the partial outputs Zj received from said t shareholders to obtain said result of decryption C1=M^{L{circumflex over ( )}2} (mod N) where {circumflex over ( )} represents power, and

means for performing an operation on the basis of said result of decryption C1, said data to be decrypted C2, and the following equations to determine a result of final decryption M by using the first and second public keys;

3. A t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system including n shareholders connected to each other via a network and a user unit and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of signature without computing said secret key d, wherein

each of said n shareholders comprises means for performing an operation on data S2=M to be signed received from said user unit to produce a partial output Zj and returning the partial output Zj to said user unit by using the share about the secret key and the second public key, and

said user unit comprises

means for selecting t shareholders out of said n shareholders and transmitting said data S2=M to be signed to the selected t shareholders,

means for combining the partial outputs Zj received from said t shareholders to obtain the result of signature S1=(M^d)^{L{circumflex over ( )}2} (mod N) where A represents power,

and means for performing an operation on the basis of said result of signature S1=(M^d)^e, said data to be signed S2=(M^d)^{L{circumflex over ( )}2}, and the following equations to determine the result of final signature M^d by using the first and second public keys;

4. A of-n secret sharing system which is applied to an RSA crypto system using a public key and a secret key d and the secret sharing system including n shareholders connected to each other via a network and, when partial final information about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create at least one of a result of decryption and a result of signature without computing said secret key d, wherein

each of said n shareholders comprises

means for creating said public key and said secret key d,

means for holding n-out-of-n partial information di (0≦

i≦

n) created based on the secret key d,

means for, if the smallest integer equal to or larger than the logarithm of n to the base t is r, turning said partial information di into t(r+1) partial random numbers of t-of-n type and sharing r+1 out of the t(r+1) partial random numbers to other shareholders on the basis of a t-ary representation of value k at the t^j-th digit (0≦

k≦

t−

1, 0≦

j≦

r) of identification number of each of said shareholders,

means for putting together n(r+1) partial random numbers shared by said other shareholders for each digit t^j in the t-ary representation and obtaining r+1 pieces of partial final information d_j,k,

means for performing an operation on the data to be processed, on the basis of said partial final information d_j,k, and outputting the obtained partial output,

means for selecting said t shareholders and transmitting the data to be

processed to the selected t shareholders, and means for combining the partial outputs from said t shareholders to obtain at least either said result of decryption or said result of signature,

wherein the means for selecting said t shareholders further comprises;

means for providing t-ary representation of identification numbers of t shareholders,

means for determining whether or not a digit of the t-ary representation meets condition that value, calculated by predetermined condition, in the t-ary representation differs for each digit in the t-ary representation for the t-shareholders, and

means for selecting t shareholders which meet the condition.

5. A shareholder which is used in a t-of n secret sharing system which is applied to an RSA crypto system using a public key and a secret key d and the secret sharing system including n shareholders connected to each other via a network and, when partial final information about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create at least one of a result of decryption and a result of signature without computing said secret key d, comprising:

means for providing a t-ary representation of identification numbers of t shareholders;

means for determining whether or not a digit of the t-ary representation meets a condition that a value, calculated by a predetermined condition, in the t-ary representation differs for each digit in the t-ary representation for the t-shareholders;

means for selecting t shareholders which meet the condition;

means for creating said public key and said secret key d,

means for holding n-out-of-n partial information di (0≦

i≦

n) created based on the secret key d,

means for, if the smallest integer equal to or larger than the logarithm of n to the base t is r, turning said partial information di into t(r+1) partial random numbers of the t-of-n type and sharing r+1 out of the t(r+1) partial random numbers to the respective shareholders on the basis of a t-ary representation of value k at the t^j-th digit (0≦

k≦

t−

1, 0≦

j≦

r) of the identification number of each of said shareholders,

means for putting together n(r+1) partial random numbers shared by said other shareholders for each digit t^j in the t-ary representation and obtaining r+1 pieces of partial final information d_j,k, and

means for performing an operation on the data to be processed, on the basis of said partial final information d_j,k, and outputting the obtained partial output.

6. A t-of-n secret sharing method which is applied to an RSA crypto system using a public key and a secret key d and the secret sharing system including n shareholders connected to each other via a network and, when partial final information about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create at least one of a result of decryption and a result of signature without computing said secret key d, said secret sharing method comprising the steps of:

providing a t-ary representation of identification numbers of t shareholders;

determining whether or not a digit of the t-ary representation meets a condition that a value, calculated by predetermined condition, in the t-ary representation differs for each digit in the t-ary representation for the t-shareholders;

selecting t shareholders which meet the condition;

causing each of said n shareholders to create said public key and said secret key d;

causing each of said n shareholders to hold n-out-of-n partial information di (0≦

i≦

n) created based on the secret key d,

causing each of said n shareholders to turn said partial information di into t(r+1) partial random numbers of the t-of-n type, if the smallest integer equal to or larger than the logarithm of n to the base t is r, and share r+1 out of the t(r+1) partial random numbers to other shareholders based on a t-ary representation of value k at the t^j-th digit (0≦

k≦

t−

1, 0≦

j≦

r) of the identification number of each of said shareholders,

causing each of said n shareholders to put together n(r+1) partial random numbers shared by said other shareholders for each digit t^j in the t-ary representation and obtaining r+1 pieces of partial final information d_j,k, and

and causing the t shareholders selected from said n shareholders to perform an operation on the data to be processed, on the basis of said partial final information d_j,k and output the obtained partial output.

7. The t-of-n secret sharing method according to claim 6, further comprising:

the step of combining the partial outputs from the t shareholders selected from said n shareholders and obtaining at least either said result of decryption or said result of signature.

8. A t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system including n shareholders connected to each other via a network and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of decryption without computing said secret key d by using first and second public keys, wherein

each of said n shareholders comprises

means for outputting a partial output Zj obtained by performing an operation on data C2=M^e (mod N) to be decrypted, said partial output Zj being computed using the following equations by using the share about the secret key and the second public key;

${\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}=\underset{l\in <br><br>\mathrm{\Lambda <br><br>}<br><br>\backslash <br><br>\left\{j\right\}}{\prod <br><br>}<br><br>\frac{l}{l-j}$${\mathrm{\sigma <br><br>}}_j=s_j·<br><br>L^2·<br><br>{\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}$$Z_j=C^{{\mathrm{\sigma <br><br>}}_j}<br><br>\left(\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>N\right).$

9. The t-of-n secret sharing system according to claim 8, further comprising:

means for selecting t shareholders out of said n shareholders and transmitting said data C2 to be decrypted to the selected t shareholders;

means for combining the partial outputs Zj received from said t shareholders to obtain the result of decryption C1=M^{dL{circumflex over ( )}2} (mod N) where {circumflex over ( )} represents power; and

means for performing an operation on the basis of said result of decryption C1, said data to be processed C2, and the following equations to determine the result of final decryption M;

11. The t-of-n secret sharing system according to claim 8, further comprising:

means for selecting t shareholders out of said n shareholders and transmitting said data S2 to be signed to the selected t shareholders;

means for combining the partial outputs Zk received from said t shareholders to obtain a result of signature S1=M^{dL{circumflex over ( )}2} (mod N) where {circumflex over ( )} represents power; and

means for performing an operation on the basis of said result of signature S1, said data to be processed S2, and the following equations to determine the result of final signature M^d;

10. A t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system including n shareholders connected to each other via a network and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of signature without computing said secret key d by using first and second public keys, wherein

each of said n shareholders comprises

means for outputting a partial output Zj obtained by performing an operation on data S2=M to be signed;

decrypted, said partial output Zj being computed using the following equations by using the share about the secret key and the second public key;

${\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}=\underset{l\in <br><br>\mathrm{\Lambda <br><br>}<br><br>\backslash <br><br>\left\{j\right\}}{\prod <br><br>}<br><br>\frac{l}{l-j}$${\mathrm{\sigma <br><br>}}_j=s_j·<br><br>L^2·<br><br>{\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}$$Z_j=C^{{\mathrm{\sigma <br><br>}}_j}<br><br>\left(\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>N\right).$

12. A t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and which includes n shareholders connected to each other via a network and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of decryption without computing said secret key d said secret sharing method comprising the steps of;

causing the t shareholders selected from said n shareholder to output partial outputs Zj obtained by performing an operation on data C2=M^e (mod N) to be decrypted by using the share of the secret key and the second public key;

combining the partial outputs Zj received from said t shareholders to obtain said result of decryption C1=M^{L{circumflex over ( )}2} (mod N) where {circumflex over ( )} represents power, and

performing an operation on the basis of said result of decryption C1, said data to be processed C2, and the following equations to determine the result of final decryption M by using the first and second public keys;

13. A t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and which includes n shareholders connected to each other via a network and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of signature without computing said secret key d said secret sharing method comprising the steps of;

causing the t shareholders selected from said n shareholder to output partial outputs Zj obtained by performing an operation on data S2=M to be signed by using the share of the secret key and the second public key;

combining the partial outputs Zj received from said t shareholders to obtain said result of signature S1=M^{dL{circumflex over ( )}2} (mod N) where {circumflex over ( )} represents power, and

performing an operation on the basis of said result of signature S1, said data to be signed S2=(M^d)^{L{circumflex over ( )}2}, and the following equations to determine the result of final signature M^d by using the first and second public keys;

14. A computer-readable information recording medium used in a t-of-n secret sharing system which is applied to an RSA crypto system using a public key and a secret key d and the secret sharing system includes n shareholders connected to each other via a network and, when partial final information about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create at least one of a result of decryption and a result of signature without computing said secret key d, said information recording medium comprising:

means for causing said shareholders to provide a t-ary representation of identification numbers of t shareholders;

means for causing said shareholder to determine whether or not a digit of the t-ary representation meets a condition that a value, calculated by a predetermined condition, in the t-ary representation differs for each digit in the t-ary representation for the t-shareholders;

means for causing said shareholders to select t shareholders which meet the condition;

means for causing said shareholders to create said public key and said secret key d,

means for causing said shareholders to hold n-out-of-n partial information di (0≦

i≦

n) created based on the secret key d,

means for, if the smallest integer equal to or larger than the logarithm of n to the base t is r, causing said shareholders to turn said partial information di into t(r+1) partial random numbers of the t-of-n type and sharing r+1 out of the t(r+1) partial random numbers to other shareholders based on a t-ary representation of value k at the t^j-th digit (0≦

k≦

t−

1, 0≦

j≦

r) of the identification number of each of said shareholders,

means for causing said shareholders to put together n(r+1) partial random numbers shared by said other shareholders for each digit t^j in the t-ary representation and obtaining r+1 pieces of partial final information d_j,k, and

means for causing said shareholders to perform an operation on the data to be processed, on a basis of said partial final information d_j,k, and outputting the obtained partial output.

15. A computer-readable information recording medium used in a t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system includes n shareholders connected to each other via a network and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of decryption without computing said secret key d by using first and second public keys, said information recording medium comprising;

means for outputting a partial output Zj obtained by performing an operation on data C2=M^e (mod N) to be decrypted, said partial output Zj being computed using the following equations by using the share about the secret key and the second public key;

${\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}=\underset{l\in <br><br>\mathrm{\Lambda <br><br>}<br><br>\backslash <br><br>\left\{j\right\}}{\prod <br><br>}<br><br>\frac{l}{l-j}$${\mathrm{\sigma <br><br>}}_j=s_j·<br><br>L^2·<br><br>{\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}$$Z_j=C^{{\mathrm{\sigma <br><br>}}_j}<br><br>\left(\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>N\right).$

16. A computer readable information recording medium used in a t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system includes n shareholders connected to each other via a network and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of signature without computing said secret key d by using first and second public keys said information recording medium comprising;

means for causing said shareholders to output partial outputs Zj obtained by performing an operation on data S2=M to be signed, said partial output Zj being computed using the following equations by using the share about the secret key and the second public key;

${\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}=\underset{l\in <br><br>\mathrm{\Lambda <br><br>}<br><br>\backslash <br><br>\left\{j\right\}}{\prod <br><br>}<br><br>\frac{l}{l-j}$${\mathrm{\sigma <br><br>}}_j=s_j·<br><br>L^2·<br><br>{\mathrm{\lambda <br><br>}}_{j,\mathrm{\Lambda <br><br>}}$$Z_j=C^{{\mathrm{\sigma <br><br>}}_j}<br><br>\left(\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>N\right).$

17. A computer-readable information recording medium used in a t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system includes n shareholders connected to each other via a network and a user unit and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of decryption without computing said secret key d, said information recording medium comprising;

means for causing said user unit to select t shareholders out of said n shareholders and transmit data C2 to be decrypted to the selected t shareholders

means for causing said user unit to combine partial outputs Zj received from said t shareholders to obtain said result of decryption C1=M^{L{circumflex over ( )}2} (mod N) where {circumflex over ( )} represents power, said partial outputs being obtained by performing an operation on the data C2=M^e (mod N) to be decrypted by using the share of the secret key and the second public key; and

and means for causing said user unit to perform an operation on the basis of said result of decryption C1, said data to be processed C2, and the following equations to determine the result of final decryption M by using the first and second keys

18. A computer-readable information recording medium used in a t-of-n secret sharing system which is applied to an RSA crypto system wherein a greatest common divisor of e and L² is 1, modulus N is common, and L=(n−

1)!, using a first public key e-of-N, a secret key d, and a second public key L²-of-N and the secret sharing system includes n shareholders connected to each other via a network and a user unit and, when share sj about said secret key d is shared to n shareholders, enables any t shareholders out of said n shareholders to create a result of signature without computing said secret key d, said information recording medium comprising;

means for causing said user unit to select t shareholders out of said n shareholders and transmit data S2=M to be signed to the selected t shareholders

means for causing said user unit to combine partial outputs Zj received from said t shareholders to obtain said result of signature S1=M^{dL{circumflex over ( )}2} (mod N) where {circumflex over ( )} represents power, said partial output Z_j being obtained by performing an operation on the data S2=M to be signed by using the share of the secret key and the second public key; and

means for causing said user unit to perform an operation on the basis of said result of signature S1=(M^d)^e, said data to be signed S2=(M^d)^{L{circumflex over ( )}2}, and the following equations to determine the result of final signature M^d by using the first and second public keys;