Secret sharing system and storage medium

[0002] This invention relates to a secret sharing system and a storage medium for a crypto system based on the problem of factorization into prime factors, and more particularly to a crypto system and a storage device which shares a secret key secretly to n shareholders and enable t of the n shareholders to perform shared decryption and signature without computing the secret key.

[0003] One known crypto system based on the problem of factorization into prime factors is a secret sharing scheme called a threshold scheme in the field of secret sharing using, for example, an RSA crypto system. The threshold scheme has a secret information recovery characteristic with a threshold of t as a boundary line. The secret information recovery characteristic is such that, when secret information is shared into n share, the secret information is recovered completely from t out of the n share but cannot be recovered at all from t−1 share (where 1<t<n).

[0004] One known secret sharing scheme of this type is a (t, n) secret sharing scheme where the concept of the threshold scheme has been introduced into the RSA crypto system and a secret key has been shared secretly in the (t, n) type (Y. Frankel, P. Gemmell, P. D.

[0005] MacKenzie and M. Yung, “Optimal-resilience proactive public-key cryptosystems,” 38^thAnnual Symposium on Foundations of Computer Science, pp. 384-393, 1997, which is hereinafter referred to as reference [FGMY97]), and T. Okamoto, “Threshold key-recovery systems for RSA,” Security Protocols, LNCS 1361, pp. 191-200, 1997, which is hereinafter referred as reference [Oka97]).

[0006] Reference [FGMY97] has described a method of enabling any t shareholders to perform decryption and signature without computing a secret key d in an environment where dealers (distributors) exist. That is, it is a method of enabling a secret key d capable of decryption and signature to be created from any t share even if shareholders do not know prime factors of composite number N.

[0007] On the other hand, in an environment where no dealer exists, one known secret sharing scheme is a (n, n) secret sharing scheme, not a threshold scheme. In the (n, n) secret sharing scheme, all the shareholders create a key where nobody knows the secret(D. Boneh and M. Franklin, “Efficient generation of shared RSA keys,” Advances in Cryptology-CRYPTO '97, LNCS 1294, pp. 425-439, 1997, which is hereinafter referred to as reference [BF97]).

[0008] In the scheme of reference [BF97], when a key is generated, (n, n) secret sharing is performed simultaneously. In addition, by combining the partial outputs from all the shareholders using the held share, the ciphertext can be decrypted without computing the secret key d.

[0009] In reference [BF97], a method of constructing (2, n) secret sharing (n≧3) from (2, 2) secret sharing has been described as shown in the following algorithm.

[0010] To simplify explanation, it is assumed that a user knows a secret key d and the user performs (2, n) secret sharing of the secret key d. It is also assumed that the number of secret sharing polynomials expressing combinations of share is r+1 where r=┌log n┘ for the total number of shareholders P being n (in the present specification, ┌┘ means that the smallest integer equal to or larger than the value in the parentheses).

[0011] To perform the (2, 2) secret sharing r+1 times, the user creates r+1 independent polynomials d=d_0,0+d_0,1=d_1,0+d_1,1= . . . =d_r,0+d_r,1separately.

[0012] Next, it is assumed that the identification number of each shareholder in a total of n shareholders is z (z∈[0, n]) and a binary representation of identification number z is z(2)=β_rβ_r−1. . . β₀. The user takes all the 0-th to n-th shareholders P₀to P_ninto account and sends r+1 share {d_r, β_r, d_r−1, β_r−1, . . . , d₀, β₀} to the z-th shareholder P_Z.

[0013] As a result, a set of shares corresponding to a binary representation of identification number z is sent to all the shareholders P₀to P_n.

[0014] When the number of an shareholder is set uniquely after the set has been sent, any two shareholders Pi, Pj (i≠j) can recover the secret key d (d_i,0+d_i,1=d) from the shares (d_i,0, d_i,1) in the same digit differing in bit β at number z(2) of the r+1 share of (2, 2).

[0015] Next, related techniques for expanding the type of secret sharing as the method of constructing the (2, n) secret sharing from the (2, 2) one will be explained.

[0016] One of the techniques of this type is a (t, 1^m) secret sharing scheme using the (t, 1) type (S. R. Blackburm, M. Burmester, Y. Desmedt and P. R. Wild, “Efficient multiplicative sharing schemes,” Advances in Cryptology-EURO-CRYPT '96, pp. 107-118, 1996, which is hereinafter referred to as reference [BBDW96]). The scheme of reference [BBDW96] is related to 1 that satisfies the following equation (1) for a positive integer m. $\begin{array}{cc}\begin{array}{c}1\ge \left(\begin{array}{c}t\\ 2\end{array}\right)\left(m-1\right)\\ \mathrm{if}b=\left(\begin{array}{c}t\\ 2\end{array}\right)\left(m-1\right)\end{array}& \left(1\right)\end{array}$

[0017] then

[0018] t=2 b≧1→≧1

[0019] t=3 b≧3→1 ≧3

[0020] t=4 b≧6→1≧6

[0021] When t≧4, then t<1. Specifically, when t≧4, it is impossible to construct a (t, n) secret sharing scheme using the (t, t) type.

[0022] For this reason, a (3, 3²) secret sharing scheme using the (3, 3) type in reference [BBDW96] will be explained hereinafter. Let m=2, 1=3, and t=3, and calculate b using equation (2). $\begin{array}{cc}b=\left(\begin{array}{c}t\\ 2\end{array}\right)\left(m-1\right)=3& \left(2\right)\end{array}$

[0023] First, (3, 3) secret sharing is performed b+1=4 times and four independent polynomials for the secret key d using equations (3) are formulated:

[0024] d=d0,0+d0,1+d0,2 (fist time)=d1,0+d1,1+d1,2 (second time)=d2,0+d2,1+d2,2 (third time)=d3,0+d3,1+d3,2 (fourth time)  (3)

[0025] In addition, let f(x)=a₀+a₁X (mod 3).

[0026] In reference [BBDW96], if a set of the final shareholders (in this case, 3²shareholders) is P′, f(X) is expressed by equation (4) (the first line on page 113, “d” in the equation is replaced with “m”, in the present specification). $\begin{array}{cc}f\left(x\right)=\sum _{i=0}^{d-1}{a}_i{X}^i\in P^{\prime }& \left(4\right)\end{array}$

[0027] Equation (4), however, is mistaken for the following equation (5). $\begin{array}{cc}f\left(x\right)=\sum _{i=0}^{d-1}{a}_i{X}^i\left(\mathrm{mod}l\right)& \left(5\right)\end{array}$

[0028] where a₀, a₁∈F3 and f()=a₁.

[0029] f1(x)=0 (mod 3)

[0030] f2(x)=1 (mod 3)

[0031] f3(x)=2 (mod 3)

[0032] f4(x)=0+X(mod 3)

[0033] f5(x)=1+X(mod 3)

[0034] f6(x)=2+X(mod 3)

[0035] f7(x)=0+2X(mod 3)

[0036] f8(x)=1+2X(mod 3)

[0037] f9(x)=2+2X(mod 3)

[0038] Each shareholder fj has (d₀,f_j(), d₁,f_j(0), d₂,f_j(1), d₃,f_j(2)). FIG. 1 concretely shows the sets of shares held in the individual shareholders. FIG. 2 shows combinations of shareholders and relevant share.

[0039] As shown in FIG. 1, for example when shareholders f1, f4, and f8 (second row) perform shared decryption, they extract the share corresponding to X=. Each of them can compute the output corresponding to the secret key d by doing calculations using (d_0,0, d_0,1, d_0,2).

[0040] In FIG. 2, a combination with one of the alphabetic characters a to l means that there are three types of computation routes for the output corresponding to the secret key d in the same combination in each shareholder (in FIG. 2, “d” is merely an alphabetic character, not the secret key d). For example, in the combination (f1, f2, f3) with character b, it is possible to collect three shares to recover the secret key d using any of X=0, 1, and 2.

[0041] In connection with the (n, n) secret sharing scheme in reference [BF97], there is a scheme that has introduced the concept of threshold scheme (Y. Frankel, P. D. MacKenzie and M. Yung, “Robust efficient shared RSA-key generation,” Proceedings of the thirtieth annual ACM symposium on theory of computing, pp. 663-672, 1998, which is hereinafter referred to as [FMY98]).

[0042] In the scheme of reference [FMY98], a (t, n) key generation and sharing scheme based on the (n, n) secret sharing in reference [BF97] has been described. Specifically, (n, n) key generation is performed and then the sum of polynomials for the secret key d is obtained. Then, each shareholder Pi becomes a dealer for share di and performs Sum-to-Poly conversion (conversion of sum into polynomials). At this time, each shareholder Pi combines the pieces of shared information for the partial information dj from all the shareholder Pj and finally performs secret sharing of the secret key d, thereby realizing the (t, n) secret sharing of the secret key d.

[0043] As a result, in the scheme of reference [FMY98], any t shareholders P out of a total of n shareholders can compute the RSA secret key d and therefore recover the key.

[0044] The above-described secret sharing systems, however, have the following problems.

[0045] In the scheme of reference [BBDW96], since it is impossible to construct (t, l^m) secret sharing when n>3²for t=3 and when t≧4, a method of constructing (2, n) secret sharing has not been generalized.

[0046] In the scheme of reference [FMY98], the secret key d has not been computed and a problem has arisen in performing signature or decryption using the secret key d. For example, it is assumed that there is a ciphertext C=M^e(mod N) encrypted using the public key (e, N). When any t shareholders (let a set of these shareholders be Λ) decrypt the ciphertext C, each shareholder Pj must calculate Lagrange's interpolation coefficient λ_j,Λ as shown in equation (6) and determine each partial output from the interpolation coefficient λ_j,Λ. $\begin{array}{cc}{\lambda }_{j,\Lambda }=\prod _{l\in \Lambda \backslash \left\{j\right\}}\frac{l}{l-j}\left(\mathrm{mod}\phi \left(N\right)\right)& \left(6\right)\end{array}$

[0047] However, since none of the shareholders know primary factors of composite number N (=pq), they cannot compute the multiplicative inverse elements of 1−j with the order φ (N) of the width as modulus and therefore cannot compute Lagrange's interpolation coefficient λ_j,Λ. Consequently, they cannot perform shared decryption to recover the plaintext by combining partial outputs as shown in equation (7). $\begin{array}{cc}\prod _{j\in \Lambda }{C}^{s_j·{\lambda }_{j,\Lambda }}=C^d=M\left(\mathrm{mod}N\right)& \left(7\right)\end{array}$

[0048] It is, accordingly, an object of the present invention to provide a (t, n) secret sharing system and a storage medium which enable any t out of n shareholders to perform shared decryption and signature without computing a secret key in an environment where no dealer exists.

[0049] According to a first aspect of the present invention, there is provided a (t, n) secret sharing system which is used for a crypto system based on the problem of factorization into prime factors and, when partial final information about a secret key is shared to n shareholders and any of the n shareholders cannot calculate the secret key from its own partial final information, enables any t shareholders out of the n shareholders to create the result of decryption and the result of signature without computing the secret key.

[0050] According to a second aspect of the present invention, there is provided a (t, n) secret sharing system which is applied to an RSA crypto system using a public key and a secret key d and which includes n shareholders connected to each other via a network and a user unit and, when partial final information about the secret key d is shared to n shareholders, enables any t shareholders out of the n shareholders to create at least either the result of decryption or the result of signature without computing the secret key d, wherein each of the n shareholders comprises means for creating the public key and the secret key d, means for holding a piece of (n, n) share di (0≦i≦n) created on the basis of 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 the share di into t(r+1) partial random numbers of the (t, 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 (value k at the t^j-th digit, 0≦k≦t−1, 0≦j≦r) of the identification number of each of the shareholders, means for putting together n(r+1) partial random numbers shared by the shareholders for each digit t^jin 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 the user unit on the basis of the partial final information d_j,kand returning the obtained partial output to the user unit, and the user unit comprises means for selecting the t shareholders and transmitting data to be processed to the selected t shareholders, and means for combining the partial outputs received from the t shareholders and obtaining the result of decryption or the result of signature.

[0051] According to a third aspect of the present invention, there is provided a (t, n) secret sharing system which is applied to an RSA crypto system (the greatest common divisor of e and L²is 1 and modulus N is common) using a first public key (e, N), a secret key d, and a second public key (L², N) and which includes n shareholders connected to each other via a network and a user unit and, when share sj about the secret key d is shared to n shareholders, enables any t shareholders out of the n shareholders to create the result of decryption without computing the secret key d, wherein each of the n shareholders comprises means for performing an operation on data C2 (=M^e(mod N)) to be decrypted received from the user unit to produce a partial output Zj and returning the partial output Zj to the user unit, and the user unit comprises means for selecting t shareholders out of the n shareholders and transmitting the data C2 to be decrypted to the selected t shareholders, means for combining the partial outputs Zj received from the t shareholders to obtain the 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 the result of decryption C1, the data to be decrypted C2, and the following equations to determine the result of final decryption M:

[0052] a1=(L²)⁻¹(mod e)

[0053] a2=(a1L²−1)/e

[0054] M=C₁^a1(C₂^a2)⁻¹(mod N)

[0055] According to a fourth aspect of the present invention, there is provided a (t, n) secret sharing system which is applied to an RSA crypto system (the greatest common divisor of e and L²is 1, modulus N is common, and L=(n−1)!) using a first public key (e, N), a secret key d, and a second public key (L², N) and which includes n shareholders connected to each other via a network and a user unit and, when share sj about the secret key d is shared to n shareholders, enables any t shareholders out of the n shareholders to create the result of signature without computing the secret key d, wherein each of the n shareholders comprises means for performing an operation on data S2 (=M) to be signed received from the user unit to produce a partial output Zj and returning the partial output Zj to the user unit, and the user unit comprises means for selecting t shareholders out of the n shareholders and transmitting the data S2 (=M) to be signed to the selected t shareholders, means for combining the partial outputs Zj received from the t shareholders to obtain the 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 the result of signature S1 (=(M^d)^e), the data to be signed S2 (=(M^d)^{L{circumflex over ( )}2}), and the following equations to determine the result of final signature M^d:

[0056] a1=(L²)⁻¹(mod e)

[0057] a2=(a1L²−1)/e

[0058] M^d=S₁^a1(S₂^a2)⁻¹(mod N)

[0059] With the configurations according to the first and second aspects of the present invention, each of the n shareholders creates the public key and the secret key d and holds a piece of (n, n) share di (0≦i≦n) created on the basis of the secret key d. If the smallest integer equal to or larger than the logarithm of n to the base t is r, each of the n shareholders turns the share di into t(r+1) partial random numbers of the (t, n) type, shares r+1 out of the t(r+1) partial random numbers to the respective shareholders 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 of each of the shareholders, and puts together n(r+1) partial random numbers shared by the shareholders for each digit t^jin the t-ary representation to obtain r+1 pieces of partial final information d_j,k.

[0060] Then, the user unit selects the t shareholders and transmits data to be processed to the selected t shareholders. The t shareholders perform an operation on the data to be processed received from the user unit on the basis of the partial final information d_j,kand returns the obtained partial outputs to the user unit. Then, the user unit combines the partial outputs received from the t shareholders to obtain the result of decryption or the result of signature.

[0061] As described above, any t shareholders out of the n shareholders can perform shared decryption or signature without computing the secret key in an environment where there is no dealer. In addition, high processing efficiency can be realized without using Lagrange's interpolation.

[0062] Furthermore, with the configuration according to the third aspect of the present invention, in an RSA crypto system (the greatest common divisor of e and L²is 1 and modulus N is common) using a first public key (e, N), a secret key d, and a second public key (L², N), when share sj about the secret key d is shared to n shareholders, a user unit selects t from the n shareholders and transmits data to be decrypted C2 to the selected t shareholders. Each of the t shareholders performs an operation on data C2 (=M^e(mod N)) to be decrypted received from the user unit to produce a partial output Zj and returns the partial output Zj to the user unit. The user unit combines the partial outputs Zj received from the t shareholders to obtain the result of decryption C1 (=M^{L{circumflex over ( )}2}(mod N)) and performs an operation on the basis of the result of decryption C1, the data to be decrypted C2, and the specific equations (a1=(L²)⁻¹(mod e), a2=(a1L²−1)/e, M=C₁^a1(C₂^a2)⁻¹(mod N)) to determine the result of final decryption M.

[0063] As described above, any t shareholders out of the n shareholders can perform shared decryption without computing the secret key in an environment where there is no dealer. In addition, high processing efficiency can be realized on the basis of Lagrange's interpolation using a public key under specific conditions.

[0064] Still furthermore, with the configuration according to the fourth aspect of the present invention, data to be signed S2 (=M) is used in place of data C2 to be decrypted and the result of signature S1 (=M^{dL{circumflex over ( )}2}(mod N) where {circumflex over ( )} represents power) is used in place of the result of decryption C1. Instead of means for determining the result of final description M, an operation is performed on the basis of the result of signature S1 (=(M^d)^e), the data to be signed S2 (=(M^d)^{L{circumflex over ( )}2}), and specific equations (a1=(L²)⁻¹(mod e), a2=(a1L²−1)/e, M^d=S₁^a1(S₂^a2)−1 (mod N)) to determine the result of final signature M^d.

[0065] As a result, the signature process can realize a similar operation to that of the third aspect.

[0066] Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.

[0067] The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate presently preferred embodiments of the invention, and together with the general description given above and the detailed description of the preferred embodiments given below, serve to explain the principles of the invention.

[0068] FIG. 1 is a table listing sets of shares held in each shareholder in a conventional scheme;

[0069] FIG. 2 is a table listing combinations of shareholders and relevant shares in the conventional scheme;

[0070] FIG. 3 schematically shows a secret sharing system according to a first embodiment of the present invention;

[0071] FIG. 4 is a block diagram showing the hardware configuration of each shareholder and a user unit in the first embodiment;

[0072] FIG. 5 is a flowchart to help explain the operation of secret sharing in the first embodiment;

[0073] FIG. 6 is a flowchart to help explain the operation of decryption in the first embodiment;

[0074] FIG. 7 is a flowchart to help explain the operation of signature in the first embodiment;

[0075] FIG. 8 is a table listing pieces of information held in each shareholder to help explain a decipherable example in the first embodiment;

[0076] FIG. 9 is a table listing pieces of information held in each shareholder to help explain an indecipherable example in the first embodiment;

[0077] FIG. 10 is a flowchart to help explain the operation of decryption in a second embodiment of the present invention;

[0078] FIG. 11 is a flowchart to help explain the operation of signature in the second embodiment;

[0079] FIG. 12 is a flowchart to help explain the operation of a modification of signature in the second embodiment; and

[0080] FIG. 13 is a table to help evaluate the scheme of the present invention in relation to the conventional scheme.

[0081] Referring to the accompanying drawings, embodiments of the present invention will be explained. A first embodiment of the present invention realizes high processing efficiency without using Lagrange's interpolation. A second embodiment of the present invention realizes high reliability on the basis of Lagrange's interpolation using a public key under specific conditions. Both the first and second embodiments are a (t, n) secret sharing system which enables shared decryption and signature using a non-dealer-model threshold scheme.

[0082] The first embodiment of the present invention is a (t, n) secret sharing system obtained by generalizing the method of constructing a (2, n) secret sharing system from a (2, 2) one in reference [BF97].

[0083] Specifically, the first embodiment is a (t, n) secret sharing system where, when each shareholder Pi holds (n, n) share di about a secret key d, all the shareholders P1 to Pn shares di in the form of (t, n) partial random-number information, and each of the shareholders P1 to Pn puts together pieces of the partial random-number information for each digit to create partial information d_j,k.

[0084] FIG. 3 schematically shows the configuration of a secret sharing system according to the first embodiment. In the secret sharing system, n shareholders P1 to Pn each composed of computer systems and a user unit U are connected to each other via a network 1.

[0085] Since the shareholders P1 to Pn have the same configuration, an arbitrary shareholder Pi (where 1≦i≦n) will be explained as a representative example.

[0086] Shareholder Pi has the function of generating a public key (e, N) and a secret key d, the function of turning the secret key d into (2, n) share on the basis of the scheme of [BF97] and sharing r+1 pieces of the share to the shareholders P1 to Pn, the function of holding one piece of (n, n) share di on the basis of the shared r+1 shares, the function of turning into the share di into (t, n) partial random numbers and sharing r+1 of the partial random numbers to the shareholders P1 to Pn on the basis of a t-ary representation of the identification number for the shareholder, the function of putting together n(r+1) pieces of partial random numbers shared from the shareholders P1 to Pn for each digit tj in the t-ary representation and obtaining r+1 partial information d_j,k, and the function of returning to the user unit U the partial output X_Zobtained by decrypting the ciphertext C received from the user unit U.

[0087] When t shareholders out of the shareholders Pi are selected, T is used in place of P in representation. For example, when shareholder P_Zis selected, it is represented as shareholder T_Z.

[0088] The user unit U has the function of selecting t shareholders out of n shareholders P1 to Pn, the function of transmitting a ciphertext C encrypted using the public key (e, N), and the function of creating a plaintext M by combining the partial outputs X_Zreceived from the shareholders T_Z.

[0089] The following is explanation of a concrete hardware configuration of the shareholders P1 to Pn and user unit U. The shareholder Pi and user unit U are a computer system in which a CPU 11, a controller 12, a memory 13, a communication device 14, a display 15, a keyboard 16, and a printer 17 are connected to each other via a bus 18 as shown in FIG. 14.

[0090] In the hardware configuration, the memory 13 includes both of a main memory (e.g., RAM) and a secondary memory (e.g., hard disk). The function the shareholder Pi is to execute is realized using the programs loaded into the main memory and the control of the CPU 11 running according to the programs. Specifically, each of the shareholders P1 to Pn and user unit U has a different software configuration to carry out the above-described functions. The details of the functions composed of hardware and software combinations will be described in explaining the operations below.

[0091] Since the shareholders P1 to Pn have only to be hardware devices for processing the data received from the user device U and returning the result to the user device U, for example, the display 15, keyboard 16, and printer 17 may be eliminated, if necessary. Similarly, in the user unit U, for example, the printer 17 may be eliminated.

[0092] The operation of the secret sharing system constructed as described above will be explained. ((t, n) secret sharing)

[0093] When the shareholders P1 to Pn generate a public key (e, N) and a secret key d, they turn the secret key d into (2, n) shares on the basis of the scheme of reference [BF97] and share r+1 out of the shares to the shareholders P1 to Pn.

[0094] The shareholders P1 to Pn secretly share different prime factors of composite number N and the secret key d in the (n, n) type on the basis of the r+1 shares in the scheme of [BF97].

[0095] Specifically, the shareholders Pi (1≦i≦n) hold shares fulfilling the following equation (8) as shown in FIG. 5 (ST1).

[0096] d=d1+d2+ . . . +dn  (8)

[0097] Next, all the shareholders Pi function as dealers for their own shares. Specifically, all the shareholders Pi generate (t, n) partial random-number information Sj,l (1≦j≦r, 0≦1≦t−2) indicting their own shares di as shown in equation (9) (ST2) where r=┌log_tn┘. $\begin{array}{cc}{S}_{j,t-1}^{\left(i\right)}=d_i-\sum _{l=0}^{t-2}{S}_{j,l}& \left(9\right)\end{array}$

[0098] The process of generating pieces of the partial random-number information S_j,lis equivalent to the act for all the shareholders Pi to create r+1 independent polynomials representing their own shares di as shown below: $\begin{array}{c}di=S_{0,0}+S_{0,1}+\dots +S_{0,t-2}+S_{0,t-1}\\ =S_{1,0}+S_{1,1}+\dots +S_{1,t-2}+S_{1,t-1}\\ =\dots \\ =S_{j,0}+S_{j,1}+\dots +S_{j,t-2}+S_{j,t-1}\\ =\dots \\ =S_{r,0}+S_{r,1}+\dots +S_{r,t-2}+S_{r,t-1}\end{array}$

[0099] Next, if an identification number is z, all the shareholders Pi share pieces of the partial random-number information S_i,lamong shareholders Pz (1≦z≦n) as shown in step ST3 to step ST4 below.

[0100] Specifically, the identification number z of shareholder Pz is converted into t-ary number as shown in equation (10):

[0101] z=β_r,zt^r+β_r−1,zt^r−1+ . . . +β_j,zt^j+ . . . +β_0,z  (10

[0102] For the sake of simplicity, equation (10) is represented as equation (11):

[0103] z(t)=β_r,zβ_r−1,z. . . β_j,z. . . β_0,z  (11)

[0104] where t-ary value β_r,z∈{0, . . . , t−1}

[0105] Each shareholder Pi transmits set S including r+1 pieces of the partial random-number information shown below to shareholder Pz on the basis of t-ary value β for each digit t^jin z(t) (ST4). $S_{r,\beta r,z^{\prime }}^{\left(i\right)}{S}_{r-1,\beta r-1,z^{\prime }}^{\left(i\right)}\dots ,S_{0,\mathrm{\beta 0},z}^{\left(i\right)})$

[0106] Each shareholder Pz calculates partial information d_j,kby summing the pieces of the partial random-number information S_j,lfor each digit j as shown in the following equation (12) on the basis of the set S obtained from all the shareholders Pi including itself, where k∈{β_r,zβ_r−1,z. . . β_0,z}, 0≦j≦r (ST5). $\begin{array}{cc}{d}_{j,k}=\sum _{i=1}^n{S}_{j,k}^{\left(i\right)}=S_{j,k}^{\left(1\right)}+S_{j,k}^{\left(2\right)}+\dots +S_{j,k}^{\left(n\right)}& \left(12\right)\end{array}$

[0107] Each shareholder Pz holds r+1 partial information d_j,kcorresponding to digit j (ST6). The partial information d_j,kis a subset of the secret key d.

[0108] The relationship between the secret key d and the partial secret key d_j,kis as shown in equation (13):

[0109] d=d_0,0+d_0,1+ . . . +d_0,t−1(t⁰-th digit)=d_1,0+d_1,1+ . . . +d_1,t−1(t¹-th digit)=( . . . )=d_r,0+d_r,1+ . . . +d_r,t−1(t^r-th digit)  (13)

[0110] For example, the information that the shareholder z=20 in (3, 27) secret sharing is as follows:

[0111] r=┌log₃27┘=3

[0112] 20=20=0×3³+2×3²+0×3¹+2×3⁰

[0113] 20 (3)=0202 (ternary representation)

[0114] Therefore, shareholder P₂₀holds the shares (d_3,0, d_2,2, d_1,0, d_0,2) corresponding to a ternary representation (0202) of the identification number z among all the shareholders shown in equation (14):

[0115] d=d_3,0+d_3,1+d_3,2(3³-th digit)=d_2,0+d_2,1+d_2,2(3²-th digit)=d_1,0+d_1,1+d_1,2(3¹-th digit)=d_0,0+d_0,1+d_0,2(3⁰-th digit)  (14)

[0116] (Shared Decryption)

[0117] Being requested by the user device U to perform decryption, t shareholders T_Z(let this set be Λ) out of n shareholders P1 to Pn perform shared decryption of data C=M^e(mod N) encrypted with the public key (e, N) of the user device U, as shown in step ST11 to step ST16 in FIG. 6.

[0118] Specifically, the user unit U converts the identification number z of each of the t shareholders T_Zinto t-ary representation as shown in equation (15) (ST11):

[0119] z(t)=β_r,zβ_r−1,z. . . β_0,z  (15)

[0120] Thereafter, the user unit U judges whether or not there is digit t^jmeeting the condition that value β in the t-ary representation differs (β_j,a≠β_j,b) for each digit t^j(0≦j≦r) in the t-ary representation for the t shareholders Ta, Tb∈Λ (a≠b) (ST12).

[0121] When there is no digit t^jmeeting the condition, shared decryption using the set Λ is impossible. Thus, some of the shareholders T_Zin the set Λ are replaced with others and the processes are executed again, starting from step ST11.

[0122] If there is a digit t^jfulfilling the condition at step ST2, the user unit U transmits the encrypted data C to each shareholder T_Z(ST14).

[0123] Each shareholder T_Z(ST14) decrypts the encrypted data C on the basis of the partial information d_j,k(k=β_j,z) corresponding to the t^j-th digit and returns the obtained partial output X_Z(=C^dj,k(mod N)) to the user unit U (ST15).

[0124] The user unit combines the t partial outputs X_Z(z∈Λ) received from the t shareholders T_Z(z∈Λ) as shown in equation (16) and recovers a plaintext M (ST16). $\begin{array}{cc}\begin{array}{c}\sum _{z\in \Lambda }=c^{d_{j,1}}{c}^{d_{j,2}}{\mathrm{\dots c}}^{d_{j,t}}\\ ={\left(M^e\right)}^{d_{j,1}+d_{j,2}+\dots +d_{j,t}}\\ ={\left(M^e\right)}^d\\ =M^{\left(\mathrm{mod}N\right)}\end{array}& \left(16\right)\end{array}$

[0125] The above operations are carried out when the plaintext M is subjected to shared decryption by sending the encrypted data C (=M^e(mod N)) to the t shareholders T_Z. The present invention is not limited to this. For instance, in the first embodiment, when data to be signed M is transmitted to the t shareholders T_Zin place of the encrypted data C (ST14a), a signature M^d(mod N) may be obtained by combining the aforementioned partial outputs X_Zas shown in FIG. 7 (ST16a).

[0126] As described above, with the first embodiment, each of the n shareholders P1 to Pn generates a public key and a secret key d and holds a piece of (n, n) shares di (0≦i≦n) created on the basis of the secret key d. If the smallest integer equal to or larger than the logarithm of t to the base t log_tn is r, the share di is turned into t(r+1) partial random numbers Sj of the (t, n) type. On the basis of the t-ary representation (value k at t^j-th digit, 0≦k≦t−1, 0≦j≦r) of the identification number z of each shareholder Pi, r+1 out of the t(r+1) random numbers Sj are shared to the shareholders P1 to Pn. The shared n(r+1) partial random numbers are put together for each t^j-th digit in the t-ary representation, thereby obtaining r+1 partial information d_j,k.

[0127] Then, the user unit U selects t shareholders T_Zand transmits the encrypted data C (or data to be signed). The t shareholders T_Zcompute the encrypted data C (or data to be signed) on the basis of the partial information d_j,kand return the obtained partial outputs X_Zto the user unit U. The user unit U then combines t partial outputs X_Zand obtains the result of decryption (or signature).

[0128] As described above, any t out of n shareholders can perform shared decryption and signature without computing the secret key in an environment where there is no dealer. In addition, in shared decryption, the trouble of computing Lagrange's interpolation coefficient can be omitted, which realizes high processing efficiency.

[0129] Furthermore, with the first embodiment, the input to the ciphertext can be held beforehand in the form of a table and the processing efficiency of calculations is improved more than the scheme of reference [FMY98] because Lagrange's interpolation coefficient need not be computed.

[0130] Moreover, in the first embodiment, when the Lagrange's interpolation coefficients corresponding to all the combinations are held in table form, the amount of information held can be reduced more than the scheme of reference [FMY98].

[0131] For example, in the scheme of reference [FMY98], shared decryption is performed using a threshold scheme on the basis of Lagrange's interpolation. In this case, the secret key d is not a mere sum of the shares the shareholders P1 to Pn have. Each shareholder Pj must compute the Lagrange's interpolation coefficient λ_j,Λ and combine them. Therefore, when the interpolation coefficients λ_j,Λ b are calculated beforehand and held in table form, it is necessary to calculate n^Ct interpolation coefficients λ_j,Λ corresponding to all the combinations of one share and all the participating shareholders T_Zand hold the results.

[0132] On the other hand, in the first embodiment, the share corresponding to the combinations of shareholders are selected from ┌log_tn┘+1 shares. Thus, the number of shares held is ┌log_tn┘+1, resulting in a smaller amount of information.

[0133] With the scheme of the first embodiment, shared decryption of the ciphertext might be impossible when a combination of t shareholders is bad. Supplementary explanation will be given using (3, 27) secret sharing as an example. It is assumed that the following r+1 polynomials hold for the secret key d: $\begin{array}{c}d=d_{3,0}+d_{3,1}+d_{3,2}\left(3^3\text{-th digit}\right)\\ =d_{2,0}+d_{2,1}+d_{2,2}\left(3^2\text{-th digit}\right)\\ =d_{1,0}+d_{1,1}+d_{1,2}\left(3^1\text{-th digit}\right)\\ =d_{0,0}+d_{0,1}+d_{0,2}\left(3^0\text{-th digit}\right)\end{array}$

[0134] First, a case where shared decryption is possible will be described. When, of 27 shareholders, shareholders P₂₀, P₂₃, and P₂₆intervene in a shared decryption protocol, decryption operation C^d=M^ed=M is successful. Here, the ternary representations of the shareholders P₂₀, P₂₃, and P₂₆are P₂₀=0202, P₂₃=0212, and P₂₆=0222. The pieces of the information held are as shown in FIG. 8. For the 3¹-th digit, decryption can be performed using d because of d=d_1,0+d_1,1+d_1,2as shown in equation (17): $\begin{array}{cc}\begin{array}{c}{C}^{\mathrm{d1},0}·C^{\mathrm{d1},1}·C^{\mathrm{d1},2}=M^{\mathrm{ed}}\\ =M\left(\mathrm{mod}N\right)\end{array}& \left(17\right)\end{array}$

[0135] The shareholders P₂₀, P₂₃, and P₁₁using P11 in place of P₂₃fail to perform decryption. Specifically, ternary representations of the shareholders are as follows: P₂₀=0202, P₂₃=0212, and P₁₁=0102. The pieces of information held are as shown in FIG. 9.

[0136] In this case, none of the digits j have three partial information (d_j,0+d_j,1+d_j,2) constituting the secret key d. Any shares overlap (collide) with each other in two or more shareholders. The overlap of pieces of the information held might make shared decryption impossible.

[0137] In this case, another t shareholders must be selected newly.

[0138] When the total number of shareholders n is large and t or more shareholders can be selected relatively freely from the n shareholders, the (t, n) secret sharing in the first embodiment is suitable. Specifically, when decryption is impossible because the total number of shareholders n is large, t shareholders P have only to be restructured to try shared decryption protocol again.

[0139] Conversely, when total number of shareholders n is small and there is no room for shareholders P to be selected, a method of creating a relational equation corresponding to all the combinations is suitable. For example, in connection with the ElGamal crypto system, the technique for any t out of n shareholders to be able to decrypt the ciphertext encrypted using a group key has been proposed (T. P. Pedersen, “A threshold cryptosystem without a trusted party,” Advances in Cryptology-Eurocrypt '91, LNCS 547, pp. 522-526, 1991, which is hereinafter referred to as reference [Ped91b]). Specifically, for any t shareholders to perform shared decryption and recover the key as in the method shown in reference [Ped91b], _nC_tindependent relational equations related to the secret key d have only to be created. To explain more concretely, the method is to perform shared decryption using the relevant relational equation as shown in equation (18) in the case of a certain combination (Λ):

[0140] d=d_1,Λ+d_2,Λ+ . . . +d_t,Λ  (18)

[0141] In the method of reference [Ped91b], however, the number of relational equations becomes enormous in proportion to the total number of shareholders n, although there is no possibility of collision. Therefore, it is desirable that independent polynomials should be suppressed to a minimum in the range where there is little possibility of collision.

[0142] Because each scheme has both advantages and disadvantages, it is desirable that whether the scheme of the first embodiment (the reorganizing scheme), the scheme of using relational equations in the scheme of the first embodiment, or the scheme of a second embodiment of the present invention (a scheme using interpolation) is used should be determined on the basis of such conditions as the total number of shareholders n, the processing efficiency, the environment where shareholders are used, or whether decryption is permitted to be impossible.

[0143] Before explanation of a second embodiment of the present invention, an RSA common modulus protocol failure on which the second embodiment is based will be described.

[0144] It is assumed that, in an RSA crypto system, a single message M is encrypted under the condition that a common modulus N and different public exponents e1 and e2 are used and this encryption produces two different ciphertexts C1 and C2. In this case, even when prime factors of a composite number N are unknown, a message M can be recovered from the two ciphertexts C1 and C2 (G. J. Simmons, “A ‘weak’ privacy protocol using the RSA cryptoalgorithm,” Cryptologia, vol. 7, pp. 180-182, 1983, which is hereinafter referred to as reference [Sim83]).

[0145] In the scheme of reference [Sim83], the aforementioned two ciphertexts C₁, C₂are obtained using the following equations (19) and (20):

[0146] C₁=M^e1(mod N)  (19)

[0147] C₂=M^e2(mod N)  (20)

[0148] When the greatest common divisor of the different public exponents e1, e2 is gcd (e1, e2)=1, the message M can be recovered from the two ciphertexts C₁, C₂by carrying out the following steps STc1 to STc3 (D. R. Stinson, “CRYPTOGRAPHY: Theory and Practice,” CRC Press, Inc. Boca Raton, Fla., U.S.A., 1995, which is hereinafter referred as reference [Sti95]):

[0149] (Step STc1) a1=e1⁻¹(mod e2)

[0150] (Step STc2) a2=(a1e1−1)/e2

[0151] (Step Stc3) M=C₁^a1(C₂^a2)⁻¹  (mod N)

[0152] The above processes (STc1 to STc3) are expressed as follows:

[0153] Common (e1, e2)→M

[0154] As described above, in the RSA crypto system, when the specific conditions are fulfilled, there is a protocol that enables the message M to be recovered. The protocol is called an RSA common modulus protocol failure.

[0155] Now, a secret sharing system according to the second embodiment of the present invention will be explained. The second embodiment relates to a (t, n) secret sharing system which creates a public key under the condition that the RSA common modulus protocol in reference [Sim83] or [Sti95] or the like is applicable and which shares sj about the secret key d by the scheme of reference [FMY98].

[0156] The condition that the RSA common modulus protocol is applicable is equivalent to fulfilling all the following items (a) to (c):

[0157] (a) The message M is the same.

[0158] (b) Modulus N is common.

[0159] (c) The greatest common divisor of the different public exponents (e1, e2) is gcd (e1, e2)=1.

[0160] In the explanation below, the public exponents (e1, e2) are expressed as (L², e). In addition, L, which is an element of the public exponent L², may be L=(n−1)! in place of L=n!.

[0161] The user unit and shareholders are the same as those in FIGS. 3 and 4 in hardware configuration, but differ in function from the first embodiment. The following explanation centers on the differences.

[0162] The shareholders P1 to Pn will be explained using an arbitrary shareholder Pi (1≦i≦n) as a representative.

[0163] The shareholder Pi has the function of creating share (pj, qj) to modulus N on the basis of the scheme of reference [FMY98], the function of sharing those shares pj, qj to the shareholders P1 to Pn, the function of creating a public key (e, N) on the basis of (pj, qj) of each shareholder Pj, the function of obtaining (t, n) share sj from a secret key d, the function of holding the share (pj, qj) and sj, and the function of returning to the user unit U the partial output Zj obtained by decrypting the ciphertext C (=C₂=M^e(mod N)) received from the user.

[0164] The user unit U has the function of selecting t shareholders T_Zout of n shareholders, the function of transmitting the ciphertext C₂(=M^e(mod N)) encrypted using the public key (e, N) to the t shareholders T_Z, the function of combining the partial outputs Zj received from the shareholders T_Zto create a ciphertext C₁(=M^L2(mod N)), and the function of calculating a message M from the two ciphertexts (M^L2, M^e) using the aforementioned RSA common modulus protocol Common (L², e)→M.

[0165] The operation of the secret sharing system constructed as described above will be explained. ((t, n) secret sharing)

[0166] Each of the shareholders turns the secret key d into (t, n) share on the basis of the scheme of reference [FMY98] and shares the corresponding pieces of the share sj to n shareholders P1 to Pn.

[0167] Specifically, each shareholder Pj creates and transmits component elements (pj, qj) to modulus N. Each shareholder Pj judges whether the composite N=(p1+p2+ . . . +pn) (q1+q2+ . . . +qn) received from another shareholder Pj is the product of different prime numbers. If the composite is the product of two different prime numbers, the shareholder Pj judges that the composite is valid and proceeds to the next step.

[0168] Each shareholder Pj creates a public key (e, N) on the basis of (pj, qj) and computes partial information dj about the secret key d that each shareholder Pj should hold (which completes the (n, n) secret sharing), where

[0169] d=d1+d2+ . . . +dj+ . . . +dn

[0170] Next, each shareholder Pj converts the (n, n) type sharing method of a secret key d into the (t, n) type sharing method of the secret key d using Sum-to-Poly techniques (which completes the (t, n) secret sharing).

[0171] At this time, for t−1 random numbers {b1, . . . , b_t−1}∈Z, a polynomial as shown in equation (21) is determined:

[0172] f(x)=d+b1x+b2x²+ . . . +b_t−1x^t−1  (21)

[0173] The equation is a polynomial of degree k−1 using y-intercept as the secret key d and determined uniquely from k coordinate points (j, f(j)) by Lagrange's interpolation. From k−1 coordinate points, however, the equation is not determined uniquely and permits any y-intercept, which prevents the secret key d from being computed.

[0174] Each shareholder Pj uses its own identification number j (1≦j≦n) of each of the shareholders P1 to Pn as an independent variable x, substitutes it into the above polynomial f(x), computes f(j), and obtains share sj (=f(j)) indicating the y coordinate on f(x) for each Pj.

[0175] Each shareholder Pj holds the obtained (t, n) share sj and the share (pj, qj) about prime factors of modulus N. The (n, n) partial information dj is also held but not used in the second embodiment.

[0176] Being requested by the user device U to perform decryption, t shareholders T_Z(let this set be Λ) out of n shareholders perform shared decryption of data C=M^e(mod N) encrypted with the public key (e, N) of the user device U, as shown in step ST21 to step ST24 in FIG. 10. It is assumed that L=n! and the greatest common divisor gcd (e, L²)=1.

[0177] Specifically, the user unit U transmits ciphertext C (M^e(mod N)) to t shareholders Tj (∈Λ) (ST21).

[0178] Each shareholder Tj calculates share Zj using its own share sj and returns the obtained partial output Zj to the user unit U as shown in equations (22) to (24) (ST22): $\begin{array}{cc}{\lambda }_{j,\Lambda }=\prod _{l\in \Lambda \backslash \left\{j\right\}}\frac{l}{l-j}& \left(22\right)\\ {\sigma }_j=s_j·L^2·{\lambda }_{j,\Lambda }& \left(23\right)\\ Z_j=C^{{\sigma }_j}\left(\mathrm{mod}N\right)& \left(24\right)\end{array}$

[0179] The user unit U combines the partial outputs Zj received from the t shareholders Tj and computes ciphertext M^L2(mod N) as shown in equation (25) (ST23): $\begin{array}{cc}\prod _{j\in \Lambda }{Z}_j={\left(M^e\right)}^{L^2·{\sum }_{j\in \Lambda }\left(s_j·{\lambda }_{j,\Lambda }\right)}=M^{L^2}\left(\mathrm{mod}N\right)& \left(25\right)\end{array}$

[0180] The user unit U computes a message M from the original ciphertext M^eand the ciphertext M^L2, or two different ciphertexts (M^L2, Me), using the above-described RSA common modulus protocol failure Common (L², e)→M (ST24). The correlation between the second embodiment and the aforementioned protocol is as follows: (M^L2, M^e)=(C₁, C₂) and (L², e)=(e1, e2). The RSA common modulus protocol failure has soundness as shown in equation (26):

[0181] C1^a1(C2^a2)⁻¹=M^L2a1−ea2=M(mod N)  (26)

[0182] (Shared Signature)

[0183] The user unit U may cause t shareholders T_Zto perform shared signature instead of shared decryption.

[0184] In this case, the user unit U uses data S1 (=M) to be signed in place of ciphertext C to be decrypted and the result of signature S2 (=(M^d)^{L{circumflex over ( )}2}(mod N) where {circumflex over ( )} represents power) in place of the ciphertext M^L2obtained by decryption (ST23a).

[0185] Then, the user unit U computes signature M_dfrom (C₁, C₂)=(M^{dL{circumflex over ( )}2}, M)=((M^d)^{L{circumflex over ( )}2}, (M^d)^e) on the basis of the following RSA common modulus protocol failure (ST24a):

[0186] a1=(L²)⁻¹(mod e)

[0187] a2=(a1L²−1)/e

[0188] M=C₁^a1(C₂^a2)⁻¹(mod N)

[0189] The RSA common modulus protocol failure has soundness as shown in equation (27): $\begin{array}{cc}\begin{array}{c}{{\mathrm{C1}}^{1a}\left({\mathrm{C2}}^{\mathrm{a2}}\right)}^{-1}=M^{d\left(\mathrm{L2a1}-\mathrm{ea2}\right)}\\ =M^d\left(\mathrm{mod}N\right)\end{array}& \left(27\right)\end{array}$

[0190] (Modification of Shared Signature)

[0191] The above-described shared signature may be modified as shown in FIG. 12. Specifically, after step ST23a, the user unit U transmits a set of data to be signed S1 and signature result S2 to a signature authentication device at the other party (not shown) (ST25a).

[0192] The signature authentication device calculates first comparison data D1 (=M^e(mod N)) from data to be signed S1 and first public key (e, N) and then second comparison data D2 (=M^{L{circumflex over ( )}2}(mod N)) from signature result S2 and second public key (e, N) (ST26a).

[0193] Thereafter, the signature authentication device does calculations and determines an output M on the basis of the first and second comparison data D1, D2 and the following equations (28) to (30) (ST27a):

[0194] a1=(L²)⁻¹(mod e)  (28)

[0195] a2=(a1L²−1)/e  (29)

[0196] M=D₁^a1(D₂^a2)⁻¹(mod N) (30)

[0197] If the output M coincides with the data to be signed S1, the signature authentication device judges that the signature of the user unit U is valid (ST28a).

[0198] As described above, with the second embodiment, when share sj about the secret key d have been shared to n shareholders P1 to Pn in an RSA crypto system under the condition that an RSA common modulus protocol failure is applicable, the user unit U selects t shareholders T_Zand transmits encrypted data C1. Each of the t shareholders T_Zreturns the partial output Zj obtained by performing an operation on the encrypted data C1 (=M^e(mod N)) to the user unit U. The user unit U combines t partial outputs Zj to produce the result of decryption C2 (=ML{circumflex over ( )}2 (mod N)) and executes a computing process on the basis of the result of decryption C2, the data to be processed C1, and the RSA common modulus protocol failure to determine the result of final decryption M.

[0199] Therefore, any t out of n shareholders can perform shared decryption without computing the secret key in an environment where there is no dealer. In addition, high reliability can be realized on the basis of Lagrange's interpolation using a public key under specific conditions.

[0200] Furthermore, with the data to be signed C2 (=M) in place of the data to be decrypted C2 and the result of signature S1 (=(M^d)^{L{circumflex over ( )}2}(mod N) where {circumflex over ( )} represents power) in place of the result of decryption C1, a signature M^dis determined by performing an operation using the RSA common modulus protocol failure.

[0201] In this way, shared signature is realized as is shared decryption.

[0202] Specifically, with the second embodiment, creating a public key under specific conditions enables the decrypting and encrypting processes to be executed reliably, regardless of a combination of t shareholders.

[0203] The scheme of the second embodiment that realizes the above-described functions using a non-dealer model will be compared with the scheme of reference [FGMY97] that realizes the functions (the shared decryption/shared signature in the (t, n) type) using a dealer model.

[0204] Like the scheme of reference [FGMY97], the scheme of the second embodiment is based on the following Euclidean formula (30) using α and β as coefficients:

[0205] eα+L²β=1

[0206] where gcd(e, L²)=1

[0207] where coefficients (α, β)=(−a2, a1) in the scheme of the second embodiment, and coefficients (α, β)=(P, s/H) in the scheme of reference [FGMY97].

[0208] In the second embodiment, since M is computed from the combined output using Euclidean algorithm after the partial outputs Zj have been combined in decryption, the processing efficiency is lower than that of the scheme of reference [FGMY97] by the value corresponding to the process of computing M. (In the scheme of reference [FGMY97], since a dealer creates a Euclidean formula at the time of key sharing, the partial outputs of the shareholders are combined in decryption. The combined output is message M.)

[0209] In the scheme of reference [FGMY97], however, a dealer who knows Euler's function of N φ(N) is needed and L²k fulfilling d≡P+L²k (mod φ(N)) is shared secretly to shareholders, which share the function. When having lost the secret key d and prime factors p and q, the dealer cannot recover the secret key d from the shareholders. The reason is that, even if L²k is recovered, the secret key d cannot be calculated from L²k because modulus φ(N) is lost. P+L²k congruent to d using modulusφ(N) can be computed.

[0210] Specifically, in the scheme of reference [FGMY97], shared signature and shared decryption are performed in an environment where there is a dealer, but the dealer cannot recover the key d. In the scheme of reference [FGMY97], to recover the key, it is necessary to use another scheme, such as the scheme disclosed in a reference about a dealer model (T. P. Pedersen, “Shared provers with applications to undeniable signatures,” Advances in Cryptology-Eurocrypt '91, LNCS 547, pp. 221-238, 1991, which is hereinafter referred to as reference [Ped91a]) or reference [Oka97]. When the positions of the conventional scheme and the scheme of the present invention in the shared RSA crypto system are considered, they are classified as shown in FIG. 13.

[0211] On the other hand, the scheme of the present invention can realize shared signature and shared decryption by combining with the scheme of reference [Ped91a] in an environment where there is a dealer and by combining with the scheme of reference [FMY98] in an environment where there is no dealer.

[0212] In the first and second embodiments, the case where there is no dealer has been explained. Hereinafter, modifications 1 and 2 applied to an environment where there is no dealer will be explained briefly. Modification 1 is related to a case where the first embodiment is applied to a dealer model. In modification 1, a user unit U serving as a dealer creates all the partial secret keys d_j,kfulfilling equation (13) and allocates them to the shareholders. With modification 1, because the complex processes from step ST1 to step St4 described above are eliminated, the efficiency is improved so much more.

[0213] Modification 2 is related to a case where the second embodiment is combined with reference [Ped91a]. This combination achieves the same function as that of the combination of the second embodiment with reference [FMY98].

[0214] Specifically, as far as (t, n) secret sharing is concerned, the present invention can be realized, regardless of whether there is a dealer. The invention is not limited to the above-described embodiments. For instance, the invention may be realized by suitably using a function group concerning a case where any t of n birds are put in different birdhouses (K. Kurosawa and D. Stinson, Personal communication, June 1996 Referred in Desmedt's paper. (Y. Desmedt, “Some recent research aspects of threshold cryptography,” Information Security, LNCS 1396, pp. 158-173, 1997)).

[0215] As long as the storage medium in the present invention is a computer-readable storage medium and can store programs, it may take any storage form, such as a magnetic disk, a floppy disk, a hard disk, an optical disk (e.g., CD-ROM, CD-R, or DVD), a magneto-optical disk (e.g., MO), or a semiconductor memory.

[0216] An operating system (OS) running on a computer under the control of the programs loaded into the computer from a storage medium, or middleware (MW), such as database management software or network software, may execute part of the processes to realize the embodiments.

[0217] The storage medium in the present invention is not limited to a medium independent of the computer and includes a storage medium into which the programs transmitted via a LAN or the Internet are downloaded and stored or temporarily stored.

[0218] The number of storage mediums is not restricted to one. The storage medium in the invention further includes plural storage mediums used to execute the processes in the embodiments. The configuration of each medium may take any form.

[0219] The computer in the present invention may be composed of a single personal computer or a system consisting of plural devices connected in network form and execute each process in the embodiments on the basis of the programs stored on a storage medium.

[0220] Furthermore, the computer in the invention is not limited to a personal computer and includes an arithmetic processing unit and a microcomputer classified into information processing equipment. The apparatuses and devices capable of realizing the functions of the present invention using programs are generally called a computer in the invention.

[0221] Moreover, the present invention is not restricted to the RSA crypto system and may be applied to a crypto system other than the RSA crypto system, as long as it is a crypto system based on the problem of factorization into prime factors.

[0222] The present invention may be practiced or embodied in still other ways without departing from the spirit or essential characteristic thereof.

[0223] As described above, with the present invention, it is possible to provide a (t, n) secret sharing system and a storage medium which enable any t out of n shareholders to perform shared decryption and shared signature without computing a secret key in an environment where there in no dealer.

[0224] Additional advantages and modifications will readily occur to those skilled in the art. Therefore, the invention in its broader aspects is not limited to the specific details and representative embodiments shown and described herein. Accordingly, various modifications may be made without departing from the spirit or scope of the general inventive concept as defined by the appended claims and their equivalents.