Patent Publication Number: US-9894056-B2

Title: Segmented secret-key storage system, segment storage apparatus, segmented secret-key storage method

Description:
TECHNICAL FIELD 
     The present invention relates to a segmented secret-key storage system, a segment storage apparatus, and a segmented secret-key storage method for securely storing a secret key for use in encryption or authentication. 
     BACKGROUND ART 
     Storing a secret key for use in encryption or authentication is an important matter. In modern encryption, preventing secret key leaks is a prerequisite to security. Tamper-resistant hardware for storing keys has been studied to prevent secret keys from leaking, and products such as a trusted platform module (TPM) and a hardware security module (HSM) have been put to practical use. 
     Another method of preventing secret information from being divulged because of leakage of a secret key is to update the secret key. That type of technique has already been known, as disclosed in Patent literature 1. 
     PRIOR ART LITERATURE 
     Patent Literature 
     Patent literature 1: Japanese Patent Application Laid Open No. 2012-150287 
     SUMMARY OF THE INVENTION 
     Problems to be Solved by the Invention 
     Hardware such as a TPM and an HSM is, however, slow and often does not have sufficient capacity to store a large number of keys. The method of updating secret keys periodically or under a predetermined condition has the risk of leaking secret information from when a secret key has leaked until when that secret key is updated. 
     In view of these problems, it is an object of the present invention to reduce the risk of leaking secret information caused by leakage of a secret key. 
     A first segmented secret-key storage system according to the present invention includes an encryption apparatus which uses a public key PK to encrypt plaintext M and outputs ciphertext C; N segment storage apparatuses which record one of secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK corresponding to the public key PK; and a combining device which obtains the plaintext M corresponding to the ciphertext C. It is first assumed that the relationship 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )                   
is satisfied, where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Dec(C, SK) is a symbol representing decryption of the ciphertext C with the secret key SK, g(sk 1 , . . . , sk N ) is a function of sk 1 , . . . , sk N , and f(m 1 , . . . , m N ) is a function of m 1 , . . . , m N . In the first segmented secret-key storage system, each of the segment storage apparatuses includes a decryption unit and a secret-key segment changing unit. The decryption unit uses the secret-key segment sk n  recorded in the segment storage apparatus to obtain a plaintext segment m n  given by m n =Dec(C, sk n ) and sends the plaintext segment m n  to the combining device. The secret-key segment changing unit obtains a set of secret-key segments (sk 1 ′, . . . , sk N ′) which satisfies
 
                         Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   (     C   ,     g   (     sk   1     ’     ,   …   ⁢           ,     sk   N       ’       )     )                     =       ⁢     f   ⁡     (     Dec   (     C   ,     sk   1       ’     )         ,   …   ⁢           ,     Dec   (     C   ,     sk   N       ’       )     )               
and which differs from (sk 1 , . . . , sk N ) and changes the secret-key segment sk n  recorded in the segment storage apparatus to sk n ′. The combining device obtains the plaintext M given by M=f(m 1 , . . . , m N ).
 
     A second segmented secret-key storage system according to the present invention includes an encryption apparatus which uses a public key PK to encrypt plaintext M and outputs ciphertext C, and N segment storage apparatuses which record one of secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK corresponding to the public key PK. It is first assumed that the relationships
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
are satisfied, where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Dec(C, SK) is a symbol representing decryption of the ciphertext C with the secret key SK, g(sk 1 , . . . , sk N ) is a function of sk 1 , . . . , sk N , and f(Dec(C, sk n ), m n+1 ) is a function of Dec(C, sk n ) and m n+1 . The segment storage apparatus which records the secret-key segment sk N  includes a decryption unit which uses the secret-key segment sk N  to obtain a plaintext segment m N  given by m N =Dec(C, sk N ) and sends the plaintext segment m N  to the segment storage apparatus which records the secret-key segment sk n−1 . The segment storage apparatus which records the secret-key segment sk n  (N is not less than 3, and n is 2 to N−1) includes a decryption unit which uses a plaintext segment m n+1  obtained from the segment storage apparatus which records the secret-key segment sk n+1  and the secret-key segment sk n  to obtain a plaintext segment m n  given by m n =f(Dec(C, sk n ), m n+1 ) and sends the plaintext segment m n  to the segment storage apparatus which records the secret-key segment sk n−1 . The segment storage apparatus which records the secret-key segment sk 1  includes a decryption unit which uses a plaintext segment m 2  obtained from the segment storage apparatus which records the secret-key segment sk 2  and the secret-key segment sk 1  to obtain the plaintext M given by M=f(Dec(C, sk 1 ), m 2 ). Each of the segment storage apparatuses further includes a secret-key segment changing unit which obtains a set of secret-key segments (sk 1 ′, . . . , sk N ′) which satisfies
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   ′, . . . ,sk   N ′))
 
 m   N   =Dec ( C,sk   N ′)
 
 m   n   =f ( Dec ( C,sk   n ′), m   n+1 )
 
 M=m   1  
 
and which differs from (sk 1 , . . . , sk N ) and changes the secret-key segment sk n  recorded in the segment storage apparatus to sk n ′.
 
     A third segmented secret-key storage system according to the present invention includes N segment storage apparatuses which record one of secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK, and a combining device which obtains a signature Σ for plaintext M. It is first assumed that the relationship 
                     Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   ⁡     (     M   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   1       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N       )         )                   
is satisfied, where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Sig(M, SK) is a symbol representing generation of the signature Σ with the secret key SK, g(sk 1 , sk N ) is a function of sk 1 , . . . , sk N , and f(σ 1 , . . . , σ N ) is a function of σ 1 , . . . , σ N . Each of the segment storage apparatuses includes a generation unit and a secret-key segment changing unit. The generation unit uses the secret-key segment sk n  recorded in the segment storage apparatus to obtain a signature segment σ n  given by σ n =Sig(M, sk n ) and sends the signature segment σ n  to the combining device. The secret-key segment changing unit obtains a set of secret-key segments (sk 1 ′, . . . , sk N ′) which satisfies
 
                         Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   (     M   ,     g   (     sk   1     ’     ,   …   ⁢           ,     sk   N       ’       )     )                     =       ⁢     f   ⁡     (     Sig   (     M   ,     sk   1       ’     )         ,   …   ⁢           ,     Sig   (     M   ,     sk   N       ’       )     )               
and which differs from (sk 1 , . . . , sk N ) and changes the secret-key segment sk n  recorded in the segment storage apparatus to sk n ′. The combining device obtains the signature Σ given by Σ=f(σ 1 , . . . , σ N ).
 
     A fourth segmented secret-key storage system according to the present invention includes N segment storage apparatuses which record one of secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK, and generates a signature for plaintext M. It is first assumed that the relationships
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   , . . . ,sk   N ))
 
σ N   =Sig ( M,sk   N )
 
σ n   =f ( Sig ( M,sk   n ),σ n+1  
 
Σ=σ 1  
 
are satisfied, where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Sig(M, SK) is a symbol representing generation of a signature Σ with the secret key SK, g(sk 1 , . . . , sk N ) is a function of sk 1 , . . . , sk N , and f(Sig(M, sk n ), σ n+1 ) is a function of Sig(M, sk n ) and σ n+1 . The segment storage apparatus which records the secret-key segment sk N  includes a generation unit which uses the secret-key segment sk N  to obtain a signature segment σ N  given by σ N =Sig(M, sk N ) and sends the signature segment σ N  to the segment storage apparatus which records the secret-key segment sk n−1 . The segment storage apparatus which records the secret-key segment sk n  (N is not less than 3 and n is 2 to N−1) includes a generation unit which uses a signature segment σ n+1  obtained from the segment storage apparatus which records the secret-key segment sk n+1  and the secret-key segment sk n  to obtain a signature segment σ n  given by σ n =f(Sig(M, sk n ), σ n+1 ) and sends the signature segment σ n  to the segment storage apparatus which records the secret-key segment sk n−1 . The segment storage apparatus which records the secret-key segment sk 1  includes a generation unit which uses a signature segment σ 2  obtained from the segment storage apparatus which records the secret-key segment sk 2  and the secret-key segment sk 1  to obtain the signature Σ given by Σ=f(Sig(M, sk 1 ), σ 2 ). Each of the segment storage apparatuses further includes a secret-key segment changing unit which obtains a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   ′, . . . ,sk   N ′))
 
σ N   =Sig ( M,sk   N ′)
 
σ n   =f ( Sig ( M,sk   n ′),σ n+1 )
 
Σ=σ 1  
 
and that differs from (sk 1 , . . . , sk N ) and changes the secret-key segment sk n  recorded in the segment storage apparatus to sk n ′.
 
     Effects of the Invention 
     According to a segmented secret-key storage system of the present invention, the secret key SK will not be revealed unless the secret-key segments are stolen from all the segment storage apparatuses in an interval between changes made to the secret-key segments. Accordingly, the risk of leakage can be greatly reduced in comparison with the risk of leakage of the secret key from a single apparatus. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a view showing an example of the functional configuration of a segmented secret-key storage system according to a first embodiment. 
         FIG. 2  is a view showing a processing flow of decrypting ciphertext to plaintext in the segmented secret-key storage system in the first embodiment. 
         FIG. 3  is a view showing a first example of a processing flow of changing secret-key segments in the present invention. 
         FIG. 4  is a view showing a second example of a processing flow of changing secret-key segments in the present invention. 
         FIG. 5  is a view showing a third example of a processing flow of changing secret-key segments in the present invention. 
         FIG. 6  is a view showing an example of the functional configuration of a segmented secret-key storage system according to a second embodiment. 
         FIG. 7  is a view showing a processing flow of decrypting ciphertext to plaintext in the segmented secret-key storage system in the second embodiment. 
         FIG. 8  is a view showing an example of the functional configuration of a segmented secret-key storage system according to a third embodiment. 
         FIG. 9  is a view showing a processing flow of generating a signature in the segmented secret-key storage system in the third embodiment. 
         FIG. 10  is a view showing an example of the functional configuration of a segmented secret-key storage system according to a fourth embodiment. 
         FIG. 11  is a view showing a processing flow of generating a signature in the segmented secret-key storage system in the fourth embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     Now, embodiments of the present invention will be described in detail. Components having identical functions will be denoted by the same reference numbers, and a duplicate description of those components will be avoided. 
     First Embodiment 
       FIG. 1  shows an example of the functional configuration of a segmented secret-key storage system in a first embodiment.  FIG. 2  shows a processing flow of decrypting ciphertext to plaintext, and  FIGS. 3 to 5  show examples of a processing flow of changing secret-key segments. The segmented secret-key storage system in the first embodiment includes an encryption apparatus  600 , N segment storage apparatuses  100   1 , . . . ,  100   N , and a combining device  130 , which are connected by a network  900 . The encryption apparatus  600  uses a public key PK to encrypt plaintext M and outputs ciphertext C. The segment storage apparatus  100   n  records a secret-key segment sk n  among secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK corresponding to the public key PK. The combining device  130  obtains plaintext M corresponding to the ciphertext C. In  FIG. 1 , the combining device  130  is represented by a dotted box and is shown in different places. The combining device  130  may be a single independent apparatus or may be disposed in any segment storage apparatus  100   n . A plurality of apparatuses may include the combining device  130 , and the combining device  130  to be used may be selected in each decryption processing flow. 
     Suppose here that the relationship 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )                   
holds, where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Dec(C, SK) is a symbol representing decryption of the ciphertext C with the secret key SK, g(sk 1 , . . . , sk N ) is a function of sk 1 , . . . , sk N , f(m 1 , . . . , m N ) is a function of m 1 , . . . , m N , and ^ is a symbol representing a power.
 
     Each segment storage apparatus  100   n  includes a decryption unit  110   n , a secret-key segment changing unit  120   n , and a recording unit  190   n . The recording unit  190   n  records the secret-key segment sk n . The decryption unit  110   n  uses the secret-key segment sk n  to obtain a plaintext segment m n  given by m n =Dec(C, sk n ) and sends the plaintext segment m n  to the combining device  130  (S 110   n ). The combining device  130  obtains the plaintext M given by M=f(m 1 , . . . , m N ) (S 130 ). 
     The secret-key segment changing unit  120   n  obtains, periodically or under a predetermined condition, a set of secret-key segments (sk 1 ′, . . . , sk N ′) which satisfies 
                         Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   (     C   ,     g   (     sk   1     ’     ,   …   ⁢           ,     sk   N       ’       )     )                     =       ⁢     f   ⁡     (     Dec   (     C   ,     sk   1       ’     )         ,   …   ⁢           ,     Dec   (     C   ,     sk   N       ’       )     )               
and which differs from (sk 1 , . . . , sk N ), and updates the secret-key segment sk n  recorded in the recording unit  190   n  to sk n ′ (S 120   n ). The predetermined condition can be when decryption has been carried out a given number of times, for example, and can be specified as desired. For example, if functions g and f are defined to satisfy
 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1   ′     ,   …   ⁢           ,     sk   N   ′       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1   ′       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N   ′       )         )                   
when the relationship
 
 SK=sk   1   + . . . +sk   N  
 
holds, the secret-key segment changing unit  120   n  should obtain a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N   ′=sk   1   + . . . +sk   N  
 
Alternatively, if functions g and f are defined to satisfy
 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1   ′     ,   …   ⁢           ,     sk   N   ′       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1   ′       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N   ′       )         )                   
when the relationship
 
 SK=sk   1   + . . . +sk   N  mod  q  
 
holds, the secret-key segment changing unit  120   n  should obtain a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N ′ mod  q=sk   1   + . . . +sk   N  mod  q  
 
     In the processing flow of changing the secret-key segments as shown in  FIG. 3 , α n  is a change part to be applied to the secret-key segment in the segment storage apparatus  100   n , and the segment storage apparatuses  100   1  to  100   N  obtain α 1  to α N  that satisfy
 
α 1 + . . . +α N =0
 
or
 
α 1 + . . . +α N  mod  q= 0
 
and the segment storage apparatus  100   n  obtains α n  (S 121 ). Then, the secret-key segment changing unit  120   n  changes the secret-key segment according to
 
 sk   n   ′=sk   n +α n  
 
     (S 122   n ). 
     In the processing flow of changing the secret-key segments shown in  FIG. 4 , two segment storage apparatuses  100   i  and  100   j  are selected, where i and j are integers between 1 and N, both inclusive, and i≠j. When N=2, i=1 and j=2, or i=2 and j=1. The segment storage apparatuses  100   i  and  100   j  record the same change part α (S 121   ij ). The secret-key segment changing unit  120   i  of the segment storage apparatus  100   i  changes the secret-key segment according to
 
 sk   1   ′=sk   1 +α
 
and the secret-key segment changing unit  120   j  of the segment storage apparatus  100   j  changes the secret-key segment according to
 
 sk   j   ′=sk   j −α
 
     (S 122   ij ). It is checked whether all the segment storage apparatuses have been selected, and it is determined whether to repeat the steps (S 124 ). Through the repetition of the steps, all the secret-key segments are changed. In this way of recording the same value α in two segment storage apparatuses and using α to change the secret-key segments sk i  and sk j  to sk 1 ′ and sk j ′, respectively, an authentication key exchange protocol can be used in the step of recording the same value α (S 121   ij ). With the authentication key exchange protocol, α is defined by using random numbers generated by both the segment storage apparatus  100   i  and the segment storage apparatus  100   j , and neither segment storage apparatus can define α arbitrarily. Consequently, security can be improved. 
     The processing flow of changing the secret-key segments shown in  FIG. 5  is the processing flow in the case where N=2. In that case, there is no need to select the segment storage apparatuses, and the segment storage apparatuses  100   1  and  100   2  record the same change part α (S 121 ). The secret-key segment changing unit  120   1  of the segment storage apparatus  100   1  changes the secret-key segment according to
 
 sk   1   ′=sk   1 +α
 
and the secret-key segment changing unit  120   2  of the segment storage apparatus  100   2  changes the secret-key segment according to
 
 sk   2   ′=sk   2 −α
 
(S 122 ). Here, in the step of recording the same value α (S 121 ), the authentication key exchange protocol can be used.
 
     According to the segmented secret-key storage system in the first embodiment, the secret key SK is not revealed unless the secret-key segments are stolen from all the segment storage apparatuses in an interval between changes made to the secret-key segments. Accordingly, the risk of leakage can be greatly reduced in comparison with the risk of leakage of the secret key from a single apparatus. 
     An existing single decryption apparatus that records the secret key SK can migrate to the segment storage apparatus  100   N  in the first embodiment through the following procedure: Add the secret-key segment changing unit  120   N  to the existing decryption apparatus; and connect the segment storage apparatuses  100   1  to  100   N-1  in which the recording units  190   1  to  190   N-1  record sk 1 = . . . =sk N-1 =0, to the network  900 . This configuration sets the initial state to sk n =SK and sk 1 = . . . =sk N-1 =0. Then, when the secret key is segmented by changing the first set of secret-key segments (sk 1 , . . . , sk N ), the segmented secret-key storage system in the first embodiment can be configured. It is thus easy to migrate to the segmented secret-key storage system in the first embodiment from the existing system. 
     Examples of Applicable Encryption Methods 
     When the segmented secret-key storage system in the first embodiment is implemented, the relationship 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )                   
must hold. Encryption methods that satisfy the relationship will be indicated below. Other encryption methods are also applicable so long as the relationship is satisfied.
 
     (1) RSA Encryption 
     In RSA encryption, plaintext M and ciphertext C satisfy the relationships
 
 C=M^e  mod  q  
 
 M=Dec ( C,d )= C^d  mod  q  
 
where q is the composite (product) of two large prime numbers, {q, e} is the public key PK, and d is the secret key SK. If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  
 
 f ( Dec ( C,sk   1 ), . . . , Dec ( C,sk   N ))= Dec ( C,sk   1 )× . . . × Dec ( C,sk   N )mod  q  
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 d=SK=sk   1   + . . . +sk   N  
 
then
 
               f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )       =         C   ^     (       sk   1     +   …   +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q     =   M           
because
 
 Dec ( C,sk   n )= C^sk   n  mod  q  
 
Therefore,
 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )                   
holds.
 
     (2) ElGamal Encryption 
     In ElGamal encryption, when the public key PK is {g, h}, the secret key SK is x, and r is a random number (h=g^x; x and r are integers between 0 and q−1, both inclusive; q is the order of a cyclic group G; g is the generator of the cyclic group G), plaintext M and ciphertext C, which are elements of the cyclic group G, satisfy these relationships
 
 C={C   1   ,C   2   }={g^r,Mh^r} 
 
 M=Dec ( C,x )= C   2 /( C   1   ^x )
 
If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  mod  q  
 
 f ( Dec ( C,sk   1 ), . . . , Dec ( C,sk   N ))= Dec ( C,sk   1 )× . . . × Dec ( C,sk   N )/( C   2 ^( N− 1))
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 x=SK=sk   1   + . . . +sk   N  mod  q  
 
then
 
               f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )       =           C   2     /     (       C   1     ^     sk   1       )       ×   …   ×         C   2     /     (       C   1     ^     sk   N       )       /     (       C   2     ^     (     N   -   1     )       )         =         C   2     /     (       C   1     ^     (       sk   1     +   …   +     sk   N       )       )       =   M             
because
 
 Dec ( C,sk   n )= C   2 /( C   1   ^sk   n )
 
Therefore,
 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )                   
holds.
 
     (3) Elliptic Curve ElGamal Encryption 
     In elliptic curve ElGamal encryption, when the public key PK is {G, H}, the secret key SK is x, and r is a random number (H=xG; x is an integer between 1 and q−1, both inclusive; r is an integer between 0 and q−1, both inclusive, q is the order of a base point G on the elliptic curve), plaintext M and ciphertext C satisfy these relationships
 
 C={C   1   ,C   2   }={rG,M+rH} 
 
 M=Dec ( C,x )= C   2   −xC   1  
 
If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  mod  q  
 
 f ( Dec ( C,sk   1 ), . . . , Dec ( C,sk   N ))= Dec ( C,sk   1 )+ . . . + Dec ( C,sk   N )−( N− 1) C   2  
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 x=SK=sk   1   + . . . +sk   N  mod  q  
 
then
 
               f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )       =         C   2     -       sk   1     ⁢     C   1       +   …   +     C   2     -       sk   N     ⁢     C   1       -       (     N   -   1     )     ⁢     C   2         =         C   2     -       (       sk   1     +   …   +     sk   N       )     ⁢     C   1         =   M             
because
 
 Dec ( C,sk )= C   2   −Sk   n   C   1  
 
Therefore,
 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )                   
holds.
 
     (4) ID-Based Encryption 
     In ID-based encryption, when the public key PK is {P ID , P, Q}, the secret key SK is S ID , and r is a random number (S ID =sP ID ; Q=sP; P ID  is a point on an elliptic curve of order q transformed from ID by using a hash function; P is the generator of a subgroup on the elliptic curve; s is the master secret key; e(,) represents pairing on the elliptic curve), plaintext M and ciphertext C satisfy the relationships
 
 C={C   1   ,C   2   }={rP,M×e ( P   ID   ,rQ )}
 
 M=Dec ( C,S   ID )= C   2   ×e ( S   ID   ,C   1 ) −1  
 
If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  mod  q  
 
 f ( Dec ( C,sk   1 ), Dec ( C,sk   N ))= Dec ( C,sk   1 )× . . . × Dec ( C,sk   N )/( C   2 ^( N− 1))
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 S   ID   =SK=sk   1   + . . . +sk   N  mod  q  
 
then
 
               f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )       =         C   2     ×       e   ⁡     (       sk   1     ,     C   1       )         -   1       ×   …   ×     C   2     ×         e   ⁡     (       sk   N     ,     C   1       )         -   1       /     (       C   2     ^     (     N   -   1     )       )         =         C   2     ×       e   ⁡     (         sk   1     +   …   +     sk   N       ,     C   1       )         -   1         =   M             
because
 
 Dec ( C,sk   n )= C   2   ×e ( sk   n   ,C   1 ) −1  
 
Therefore,
 
                     Dec   ⁡     (     C   ,   SK     )       =       ⁢     Dec   ⁡     (     C   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   1       )       ,   …   ⁢           ,     Dec   ⁡     (     C   ,     sk   N       )         )                   
holds.
 
     Second Embodiment 
       FIG. 6  shows an example of the functional configuration of a segmented secret-key storage system in a second embodiment, and  FIG. 7  shows a processing flow of decrypting ciphertext to plaintext. Examples of a processing flow of changing secret-key segments are as shown in  FIGS. 3 to 5 . The segmented secret-key storage system in the second embodiment includes an encryption apparatus  600  and N segment storage apparatuses  200   1 , . . . ,  200   N , which are connected by a network  900 . The encryption apparatus  600  uses a public key PK to encrypt plaintext M and outputs ciphertext C. The segment storage apparatus  200   n  records a secret-key segment sk n  among secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK corresponding to the public key PK. 
     Suppose here that the relationships
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
hold, where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Dec(C, SK) is a symbol representing decryption of ciphertext C with the secret key SK, g(sk 1 , . . . , sk N ) is a function of sk 1 , . . . , sk N , f(Dec(C, sk n ), m n+1 ) is a function of Dec(C, sk n ) and m n+1 , and ^ is a symbol representing a power.
 
     Each segment storage apparatus  200   n  includes a decryption unit  210   n , a secret-key segment changing unit  120   n , and a recording unit  190   n . The recording unit  190   n  records the secret-key segment sk n . The decryption unit  210   N  of the segment storage apparatus  200   N  uses the secret-key segment sk N  to obtain a plaintext segment m N  given by m N =Dec(C, sk N ) and sends the plaintext segment m N  to the segment storage apparatus  200   N-1  (S 210   N ). 
     The decryption unit  210   n  of the segment storage apparatus  200   n  (n=2, . . . , N−1) uses the plaintext segment m n+1  obtained from the segment storage apparatus  200   n+1  and the secret-key segment sk n  to obtain a plaintext segment m n  as m n =f(Dec(C, sk n ), m n+1 ), and sends the plaintext segment m n  to the segment storage apparatus  200   n−1  (S 210   n ). However, when N=2, the segment storage apparatus  200   n  (n=2, . . . , N−1) is not present. 
     The decryption unit  210   1  of the segment storage apparatus  200   1  uses the plaintext segment m 2  obtained from the segment storage apparatus  200   2  and the secret-key segment sk 1  to obtain plaintext M given by M=f(Dec(C, sk 1 ), m 2 ) (S 210   1 ). 
     The secret-key segment changing unit  120   n  obtains, periodically or under a predetermined condition, a set of secret-key segments (sk 1 ′, . . . , sk N ′) which satisfies the relationships
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   ′, . . . ,sk   N ′))
 
 m   N   =Dec ( C,sk   N ′)
 
 m   n   =f ( Dec ( C,sk   n ′), m   n+1 )
 
 M=m   1  
 
and which differs from (sk 1 , . . . , sk N ), and updates the secret-key segment sk n  recorded in the recording unit  190   n  to sk n ′ (S 120   n ). For example, if functions g and f are defined to satisfy
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
when the relationship
 
 SK=sk   1   + . . . +sk   N  
 
holds, a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N   ′=sk   1   + . . . +sk   N  
 
should be obtained. Alternatively, if functions g and f are defined to satisfy
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
when the relationship
 
 SK=sk   1   + . . . +sk   N  mod  q  
 
holds, a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N ′ mod  q=sk   1   + . . . +sk   N  mod  q  
 
should be obtained. In those examples, the requirements of the set of segments (sk 1 ′, . . . , sk N ′) are the same as those in the first embodiment, and the flow of changing the set of segments (sk 1 ′, . . . , sk N ′) is the same as in the first embodiment ( FIGS. 3 to 5 ).
 
     According to the segmented secret-key storage system in the second embodiment, the secret key SK is not revealed unless the secret-key segments are stolen from all the segment storage apparatuses in an interval between changes made to the secret-key segments. Accordingly, the risk of leakage can be greatly reduced in comparison with the risk of leakage of the secret key from a single apparatus. 
     An existing single decryption apparatus that records the secret key SK can migrate to the segment storage apparatus  200   N  in the second embodiment through the following procedure: Add the secret-key segment changing unit  120   N  to the existing decryption apparatus; and connect the segment storage apparatuses  200   1  to  200   N-1  in which the recording units  190   1  to  190   N-1  record sk 1 ==sk N-1 =0, to the network  900 . This configuration sets the initial state to sk N =SK and sk 1 ==sk N-1 =0. Then, when the secret key is segmented by changing the first set of secret-key segments (sk 1 , . . . , sk N ), the segmented secret-key storage system in the second embodiment can be configured. It is thus easy to migrate to the segmented secret-key storage system in the second embodiment from the existing system. 
     Examples of applicable encryption methods 
     When the segmented secret-key storage system in the second embodiment is implemented, the relationships
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
must hold. Encryption methods that satisfy the relationships will be indicated below. Other encryption methods are also applicable so long as the relationships are satisfied.
 
     (1) RSA Encryption 
     In RSA encryption, plaintext M and ciphertext C satisfy the relationships
 
 C=M^e  mod  q  
 
 M=Dec ( C,d )= C^d  mod  q  
 
where q is the composite (product) of two large prime numbers, {q, e} is the public key, and d is the secret key SK. If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  
 
 f ( Dec ( C,sk ), m   n+1 )= Dec ( C,sk   n )× m   n+1  mod  q  
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 d=SK=sk   1   + . . . +sk   N  
 
then
 
                     m     N   -   1       =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk     N   -   1         )       ,     m   N       )                   =       ⁢       C   ^     (       sk     N   -   1       +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q                 
because
 
 m   N   =Dec ( C,sk   N )= C^sk   N  mod  q  
 
This is repeated to provide
 
                     m   n     =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   n       )       ,     m     n   +   1         )                   =       ⁢       C   ^     (       sk   n     +   …   +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q                 
and then
 
                     m   1     =       ⁢       C   ^     (       sk   1     +   …   +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q                 =       ⁢   M               
Therefore,
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
hold.
 
     (2) ElGamal Encryption 
     In ElGamal encryption, when the public key PK is {g, h}, the secret key SK is x, and r is a random number (h=g^x; x and r are integers between 0 and q−1, both inclusive; q is the order of a cyclic group G; g is the generator of the cyclic group G), plaintext M and ciphertext C, which are elements of the cyclic group G, satisfy these relationships
 
 C={C   1   ,C   2   }={g^r,Mh^r }
 
 M=Dec ( C,x )= C   2 /( C   1   ^x )
 
     If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  mod  q  
 
 f ( Dec ( C,sk   n ), m   n+1 )=( Dec ( C,sk   n )× m   n+1 )/ C   2  
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 x=SK=sk   1   + . . . +sk   N  mod  q  
 
then
 
                     m     N   -   1       =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk     N   -   1         )       ,     m   N       )                   =       ⁢       (       Dec   ⁡     (     C   ,     sk     N   -   1         )       ×     m   N       )     /     C   2                   =       ⁢       (         C   2     /     (       C   1     ^     sk     N   -   1         )       ×       C   2     /     (       C   1     ^     sk   N       )         )     /     C   2                   =       ⁢       C   2     /     (       (       C   1     ^     sk     N   -   1         )     ⁢     (       C   1     ^     sk   N       )       )                   =       ⁢       C   2     /     (       C   1     ^     (       sk     N   -   1       +     sk   N       )       )                   
because
 
 m   N   =Dec ( C,sk   N )= C   2 /( C   1   ^sk   N )mod  q  
 
This is repeated to provide
 
                     m   n     =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   n       )       ,     m     n   +   1         )                   =       ⁢       C   2     /     (       C   1     ⁢             ⋀     ⁢     (       sk   n     +   …   +     sk   N       )       )                   
and then
 
                     m   1     =       ⁢       C   2     /     (       C   1     ⁢             ⋀     (       sk   1     +   …   +     sk   N       )     )                   =       ⁢   M               
Therefore,
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
hold.
 
     (3) Elliptic Curve ElGamal Encryption 
     In elliptic curve ElGamal encryption, when the public key PK is {G, H}, the secret key SK is x, and r is a random number (H=xG; x is an integer between 1 and q−1, both inclusive; r is an integer between 0 and q−1, both inclusive, q is the order of a base point G on the elliptic curve), plaintext M and ciphertext C satisfy these relationships
 
 C={C   1   ,C   2   }={rG,M+rH} 
 
 M=Dec ( C,x )= C   2   −XC   1  
 
If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  mod  q  
 
 f ( Dec ( C,sk   n ), m   n+1 )= Dec ( C,sk   n )+ m   n+1   C   2  
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 x=SK=sk   1   + . . . +sk   N  mod  q  
 
then
 
                     m     N   -   1       =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk     N   -   1         )       ,     m   N       )                   =       ⁢       Dec   ⁡     (     C   ,     sk     N   -   1         )       +     m   N     -     C   2                   =       ⁢       C   2     -       sk     N   -   1       ⁢     C   1       +     C   2     -       sk   N     ⁢     C   1       -     C   2                   =       ⁢       C   2     -       sk     N   -   1       ⁢     C   1       -       sk   N     ⁢     C   1                     =       ⁢       C   2     -       (       sk     N   -   1       +     sk   N       )     ⁢     C   1                     
because
 
 m   N   =Dec ( C,sk   N )= C   2   −sk   N   C   1  
 
This is repeated to provide
 
                     m   n     =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   n       )       ,     m     n   +   1         )                   =       ⁢       C   2     -       (       sk   n     +   …   +     sk   N       )     ⁢     C   1                     
and then
 
     
       
         
           
             
               
                 
                   
                     m 
                     1 
                   
                   = 
                     
                   ⁢ 
                   
                     
                       C 
                       2 
                     
                     - 
                     
                       
                         ( 
                         
                           
                             sk 
                             1 
                           
                           + 
                           … 
                           + 
                           
                             sk 
                             N 
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         C 
                         1 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   M 
                 
               
             
           
         
       
     
     Therefore,
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
hold.
 
     (4) ID-Based Encryption 
     In ID-based encryption, when the public key PK is {P ID , P, Q}, the secret key SK is S ID , and r is a random number (S ID =sP ID ; Q=sP; P ID  is a point on an elliptic curve of order q transformed from ID by using a hash function; P is the generator of a subgroup on the elliptic curve; s is the master secret key; e(,) represents pairing on the elliptic curve), plaintext M and ciphertext C satisfy these relationships
 
 C={C   1   ,C   2   }={rP,M×e ( P   ID   ,rQ )}
 
 M=Dec ( C,S   ID )= C   2   ×e ( S   ID   ,C   1 ) −1  
 
If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   y  mod  q  
 
 f ( Dec ( C,sk   n ), m   n+1 )=( Dec ( C,sk   n )× m   n+1 )/ C   2  
 
and if a set of secret-key segments (sk 1 , . . . , sk y ) is selected to satisfy
 
 S   ID   =SK=sk   1   + . . . +sk   y  mod  q  
 
then
 
                     m     N   -   1       =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk     N   -   1         )       ,     m   N       )                   =       ⁢       (       Dec   ⁡     (     C   ,     sk     N   -   1         )       +     m   N       )     /     C   2                   =       ⁢     (       C   2     ×       e   ⁡     (       sk     N   -   1       ,     C   1       )         -   1       ×     C   2     ×         e   ⁡     (       sk   N     ,     C   1       )         -   1       /     C   2                       =       ⁢       C   2     ×       e   ⁡     (       sk     N   -   1       ,     C   1       )         -   1       ⁢       e   ⁡     (       sk   N     ,     C   1       )         -   1                     =       ⁢       C   2     ×       e   ⁡     (         sk     N   -   1       +     sk   N       ,     C   1       )         -   1                     
because
 
 m   N   =Dec ( C,sk   N )= C   2   ×e ( sk   N   ,C   1 ) −1  
 
This is repeated to provide
 
                     m   n     =       ⁢     f   ⁡     (       Dec   ⁡     (     C   ,     sk   n       )       ,     m     n   +   1         )                   =       ⁢       C   2     ×       e   ⁡     (         sk   n     +   …   +     sk   N       ,     C   1       )         -   1                     
and then
 
                     m   1     =       ⁢       C   2     ×       e   ⁡     (         sk   1     +   …   +     sk   N       ,     C   1       )         -   1                     =       ⁢   M               
Therefore,
 
 Dec ( C,SK )= Dec ( C,g ( sk   1   , . . . ,sk   N ))
 
 m   N   =Dec ( C,sk   N )
 
 m   n   =f ( Dec ( C,sk   n ), m   n+1 )
 
 M=m   1  
 
hold.
 
     Third Embodiment 
       FIG. 8  shows an example of the functional configuration of a segmented secret-key storage system in a third embodiment, and  FIG. 9  shows a processing flow of generating a signature. Examples of a processing flow of changing secret-key segments are as shown in  FIGS. 3 to 5 . The segmented secret-key storage system in the third embodiment includes a signature verification apparatus  700 , N segment storage apparatuses  300   1 , . . . ,  300   N , and a combining device  330 , which are connected by a network  900 . The signature verification apparatus  700  is an apparatus for verifying the validity of a generated signature Σ. The segment storage apparatus  300   n  records a secret-key segment sk n  among secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK corresponding to a public key PK. The combining device  330  obtains the signature Σ for the plaintext M. In  FIG. 8 , the combining device  330  is represented by a dotted box and is shown in different places. The combining device  330  may be a single independent apparatus or may be disposed in any segment storage apparatus  300   n . A plurality of apparatuses may include the combining device  330 , and the combining device  330  to be used may be selected in each signature processing flow. 
     Suppose that the following relationship holds 
                     Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   ⁡     (     M   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   1       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N       )         )                   
where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Sig(M, SK) is a symbol representing generation of the signature Σ with the secret key SK, g(sk 1 , . . . , sk N ) is a function of sk 1 , . . . , sk N , f(σ 1 , . . . , σ N ) is a function of σ 1 , . . . , σ N , and ^ is a symbol representing a power.
 
     Each segment storage apparatus  300   n  includes a generation unit  310   n , a secret-key segment changing unit  120   n , and a recording unit  190   n . The recording unit  190   n  records the secret-key segment sk n . The generation unit  310   n  uses the secret-key segment sk n  to obtain a signature segment σ n  given by σ n =Sig(M, sk n ) and sends the signature segment σ n  to the combining device  330  (S 310 ). The combining device  330  obtains the signature Σ according to Σ=f(σ 1 , . . . , σ y ) (S 330 ). 
     The secret-key segment changing unit  120   n  obtains, periodically or under a predetermined condition, a set of secret-key segments (sk 1 ′, . . . , sk N ′) which satisfies 
                     Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   ⁡     (     M   ,     g   ⁡     (       sk   1   ′     ,   …   ⁢           ,     sk   N   ′       )         )                   =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   1   ′       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N   ′       )         )                   
and which differs from (sk 1 , . . . , sk N ), and updates the secret-key segment sk n  recorded in the recording unit  190   n  to sk n ′ (S 120   n ). For example, if functions g and f are defined to satisfy
 
                     Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   ⁡     (     M   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   1       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N       )         )                   
when the relationship
 
 SK=sk   1   + . . . +sk   N  
 
holds, a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N   ′=sk   1   + . . . +sk   N  
 
should be obtained. Alternatively, if functions g and f are defined to satisfy
 
                     Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   ⁡     (     M   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   1       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N       )         )                   
when the relationship
 
 SK=sk   1   + . . . +sk   N  mod  q  
 
holds, a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N ′ mod  q=sk   1   + . . . +sk   N  mod  q  
 
should be obtained. In those examples, the requirements of the set of segments (sk 1 ′, . . . , sk N ′) are the same as those in the first embodiment, and the flow of changing the set of segments (sk 1 ′, . . . , sk N ′) is the same as in the first embodiment ( FIGS. 3 to 5 ).
 
     According to the segmented secret-key storage system in the third embodiment, the secret key SK is not revealed unless the secret-key segments are stolen from all the segment storage apparatuses in an interval between changes made to the secret-key segments. Accordingly, the risk of leakage can be greatly reduced in comparison with the risk of leakage of the secret key from a single apparatus. 
     An existing single signature generation apparatus that records the secret key SK can migrate to the segment storage apparatus  300   N  in the third embodiment through the following procedure: Add the secret-key segment changing unit  120   N  to the existing signature generation apparatus; and connect the segment storage apparatuses  300   1  to  300   N-1  in which the recording units  190   1  to  190   N-1  record sk 1 = . . . =sk N-1 =0, to the network  900 . This configuration sets the initial state to sk N =SK and sk 1 = . . . =sk N-1 =0. Then, when the secret key is segmented by changing the first set of secret-key segments (sk 1 , . . . , sk N ), the segmented secret-key storage system in the third embodiment can be configured. It is thus easy to migrate to the segmented secret-key storage system in the third embodiment from the existing system. 
     Examples of Applicable Signature Methods 
     When the segmented secret-key storage system in the third embodiment is implemented, the relationship 
                     Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   ⁡     (     M   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   1       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N       )         )                   
must hold. As for an RSA signature, for example, plaintext M and a signature Σ satisfy the relationships
 
Σ= Sig ( M,d )= M^d  mod  q  (Signature generation)
 
 M=E^e  mod  q  (Signature verification)
 
where q is the composite (product) of two large prime numbers, {q, e} is the public key PK, and d is the secret key SK. If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  
 
 f ( Sig ( M,sk   1 ), . . . , Sig ( M,sk   N ))= Sig ( M,sk   1 )× . . . × Sig ( M,sk   N )mod  q  
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 d=SK=sk   1   + . . . +sk   N  
 
then
 
               f   ⁡     (       Sig   ⁡     (     M   ,     sk   1       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N       )         )       =           M   ⋀     ⁡     (       sk   1     +   …   +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q     =   Σ           
because
 
 Sig ( M,sk   n )= M^sk   n  
 
Therefore,
 
                     Sig   ⁡     (     M   ,   SK     )       =       ⁢     Sig   ⁡     (     M   ,     g   ⁡     (       sk   1     ,   …   ⁢           ,     sk   N       )         )                   =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   1       )       ,   …   ⁢           ,     Sig   ⁡     (     M   ,     sk   N       )         )                   
holds. This description does not limit the signature method that implements this embodiment. Other signature methods are also applicable so long as the conditions given above are satisfied.
 
     Fourth Embodiment 
       FIG. 10  shows an example of the functional configuration of a segmented secret-key storage system in a fourth embodiment, and  FIG. 11  shows a processing flow of generating a signature. Examples of a processing flow of changing secret-key segments are as shown in  FIGS. 3 to 5 . The segmented secret-key storage system in the fourth embodiment includes a signature verification apparatus  700  and N segment storage apparatuses  400   1 , . . . ,  400   N , which are connected by a network  900 . The signature verification apparatus  700  is an apparatus for verifying the validity of a generated signature Σ. The segment storage apparatus  400   n  records a secret-key segment sk n  among secret-key segments sk 1 , . . . , sk N  obtained by segmenting a secret key SK corresponding to a public key PK. 
     Suppose that the following relationships hold
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   , . . . ,sk   N ))
 
σ N   =Sig ( M,sk   N ).
 
σ n   =f ( Sig ( M,sk   n ),σ n+1 )
 
Σ=σ 1  
 
where N is an integer not less than 2, n is an integer between 1 and N, both inclusive, Sig(M, SK) is a symbol representing generation of a signature Σ with the secret key SK, g(sk 1 , . . . , sk N ) is a function of sk 1 , . . . , sk N , f(Sig(M, sk n ), σ n+1 ) is a function of Sig(M, sk n ) and σ n+1 , and ^ is a symbol representing a power.
 
     Each segment storage apparatus  400   n  includes a generation unit  410   n , a secret-key segment changing unit  120   n , and a recording unit  190   n . The recording unit  190   n  records a secret-key segment sk n . The generation unit  410   N  of the segment storage apparatus  400   N  uses the secret-key segment sk N  to obtain a signature segment σ N  given by σ N =Sig(M, sk N ) and sends the signature segment σ N  to the segment storage apparatus  400   N-1  (S 410   N ). 
     The generation unit  410   n  of the segment storage apparatus  400   n  (n=2, . . . , N−1) uses the signature segment σ n+1  obtained from the segment storage apparatus  400   n+1  and the secret-key segment sk n  to obtain a signature segment σ n  given by σ n =f(Sig(M, sk n ), σ n+1 ), and sends the signature segment σ n  to the segment storage apparatus  400   n−1  (S 410   n ). However, when N=2, the segment storage apparatus  400   n  (n=2, . . . , N−1) is not present. The segment storage apparatus  400   1  uses the signature segment σ 2  obtained from the segment storage apparatus  400   2  and the secret-key segment sk 1  to obtain a signature Σ given by Σ=f(Sig(M, sk 1 ), σ 2 ) (S 410   1 ). 
     The secret-key segment changing unit  120   n  obtains, periodically or under a predetermined condition, a set of secret-key segments (sk 1 ′, sk N ′) which satisfies the relationships
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   ′, . . . ,sk   N ′))
 
σ N   =Sig ( M,sk   N ′)
 
σ n   =f ( Sig ( M,sk   n ′),σ n+1 )
 
Σ=σ 1  
 
and which differs from (sk 1 , . . . , sk N ), and updates the secret-key segment sk n  recorded in the recording unit  190   n  to sk n ′ (S 120   n ). For example, if functions g and f are defined to satisfy
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   , . . . ,sk   N )
 
σ N   =Sig ( M,sk   N )
 
σ n   =f ( Sig ( M,sk   n ),σ n+1 )
 
Σ=σ 1  
 
when the relationship
 
 SK=sk   1   + . . . +sk   N  
 
holds, a set of secret-key segments (sk 1 ′, . . . , sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N   ′=sk   1   + . . . +sk   N  
 
should be obtained. Alternatively, if functions g and f are defined to satisfy
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   , . . . ,sk   N ))
 
σ N   =Sig ( M,sk   N )
 
σ n   =f ( Sig ( M,sk   n ),σ n+1 )
 
Σ=σ 1  
 
when the relationship
 
 SK=sk   1   + . . . +sk   N  mod  q  
 
holds, a set of secret-key segments (sk 1 ′, sk N ′) that satisfies
 
 sk   1   ′+ . . . +sk   N ′ mod  q=sk   1   + . . . +sk   N  mod  q  
 
should be obtained. In those examples, the requirements of the set of segments (sk 1 ′, . . . , sk N ′) are the same as those in the first embodiment, and the flow of changing the set of segments (sk 1 ′, . . . , sk N ′) is the same as in the first embodiment ( FIGS. 3 to 5 ).
 
     According to the segmented secret-key storage system in the fourth embodiment, the secret key SK is not revealed unless the secret-key segments are stolen from all the segment storage apparatuses in an interval between changes made to the secret-key segments. Accordingly, the risk of leakage can be greatly reduced in comparison with the risk of leakage of the secret key from a single apparatus. 
     An existing single signature generation apparatus that records the secret key SK can migrate to the segment storage apparatus  400   N  in the fourth embodiment through the following procedure: Add the secret-key segment changing unit  120   N  to the existing signature generation apparatus; and connect the segment storage apparatuses  400   1  to  400   N-1  in which the recording units  190   1  to  190   N-1  record sk 1 = . . . =sk N =0, to the network  900 . This configuration sets the initial state to sk N =SK and sk 1 = . . . =sk N-1 =0. Then, when the secret key is segmented by changing the first set of secret-key segments (sk 1 , . . . , sk N ), the segmented secret-key storage system in the fourth embodiment can be configured. It is thus easy to migrate to the segmented secret-key storage system in the fourth embodiment from the existing system. 
     Examples of applicable signature methods 
     When the segmented secret-key storage system in the fourth embodiment is implemented, the relationships
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   , . . . ,sk   n ))
 
σ n   =f ( Sig ( M,sk   n ),σ n+1 )
 
must hold. As for an RSA signature, for example, plaintext M and signature Σ satisfy the relationships
 
Σ= Sig ( M,d )= M^d  mod  q  (Signature generation)
 
 M=Σ^e  mod  q  (Signature verification)
 
where q is the composite (product) of two large prime numbers, {q, e} is the public key, and d is the secret key SK. If functions g and f are defined as
 
 g ( sk   1   , . . . ,sk   N )= sk   1   + . . . +sk   N  
 
 f ( Sig ,( M,sk   n ),σ n+1 )= Sig ( M,sk   n )×σ n+1  mod  q  
 
and if a set of secret-key segments (sk 1 , . . . , sk N ) is selected to satisfy
 
 d=SK=sk   1   + . . . +sk   N  
 
then
 
                     σ     N   -   1       =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk     N   -   1         )       ,     σ     n   +     1   ⁢           ⁢   N           )                   =       ⁢         M   ⋀     ⁡     (       sk     N   -   1       +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q                 
because
 
σ N   =Sig ( M,sk   N )= M^sk   N  mod  q  
 
Therefore,
 
                     σ   n     =       ⁢     f   ⁡     (       Sig   ⁡     (     M   ,     sk   n       )       ,     σ     n   +   1         )                   =       ⁢         M   ⋀     ⁡     (       sk   n     +   …   +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q                 
and then
 
                     m   1     =       ⁢         M   ⋀     ⁡     (       sk   1     +   …   +     sk   N       )       ⁢           ⁢   mod   ⁢           ⁢   q                 =       ⁢   Σ               
As a result,
 
 Sig ( M,SK )= Sig ( M,g ( sk   1   , . . . ,sk   N ))
 
σ N   =Sig ( M,sk   n )
 
σ n   =f ( Sig ( M,sk   n ),σ n+1 )
 
Σ=σ 1  
 
hold. The description does not limit the signature method that implements this embodiment. Other signature methods are also applicable so long as the conditions given above are satisfied.
 
     Program, Recording Medium 
     Each type of processing described above may be executed not only time sequentially according to the order of description but also in parallel or individually when necessary or according to the processing capabilities of the apparatuses that execute the processing. Appropriate changes can be made to the above embodiments without departing from the scope of the present invention. 
     When the configurations described above are implemented by a computer, the processing details of the functions that should be provided by each apparatus are described in a program. When the program is executed by a computer, the processing functions described above are implemented on the computer. 
     The program containing the processing details can be recorded in a computer-readable recording medium. The computer-readable recording medium can be any type of medium, such as a magnetic storage device, an optical disc, a magneto-optical recording medium, or a semiconductor memory. 
     This program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or a CD-ROM with the program recorded on it, for example. The program may also be distributed by storing the program in a storage unit of a server computer and transferring the program from the server computer to another computer through the network. 
     A computer that executes this type of program first stores the program recorded on the portable recording medium or the program transferred from the server computer in its storage unit. Then, the computer reads the program stored in its storage unit and executes processing in accordance with the read program. In a different program execution form, the computer may read the program directly from the portable recording medium and execute processing in accordance with the program, or the computer may execute processing in accordance with the program each time the computer receives the program transferred from the server computer. Alternatively, the above-described processing may be executed by a so-called application service provider (ASP) service, in which the processing functions are implemented just by giving program execution instructions and obtaining the results without transferring the program from the server computer to the computer. The program of this form includes information that is provided for use in processing by the computer and is treated correspondingly as a program (something that is not a direct instruction to the computer but is data or the like that has characteristics that determine the processing executed by the computer). 
     In the description given above, the apparatuses are implemented by executing the predetermined programs on the computer, but at least a part of the processing details may be implemented by hardware. 
     DESCRIPTION OF REFERENCE NUMERALS 
     
         
           100 ,  200 ,  300 ,  400 : Segment storage apparatus 
           110 ,  210 : Decryption unit 
           120 : Secret-key segment changing unit 
           130 ,  330 : Combining device 
           190 : Recording unit 
           310 ,  410 : Generation unit 
           600 : Encryption apparatus 
           700 : Signature verification apparatus 
           900 : Network