分割保管装置、秘密密钥分割保管方法

摘要

减少因秘密密钥的泄漏导致的秘密信息的泄漏风险。本发明的秘密密钥分割系统对秘密密钥(SK)进行分割使得能够在解密时或者署名生成时进行合并，并且将各自的分割秘密密钥k1,…,skN在分割保管装置中记录。然后，定期地或者在满足预定的条件时，变更为满足能够合并的条件的另一分割秘密密钥的组。根据本发明的秘密密钥分割保管系统，如果不在变更分割秘密密钥的间隔内从所有的分割保管装置盗取分割秘密密钥，则不知道秘密密钥(SK)。从而，与秘密密钥从一个装置泄漏的风险相比，能够大幅减少泄漏的风险。

权利要求

1.一种分割保管装置，是秘密密钥分割保管系统中的一个分割保管装置，所述秘密密钥分割保管系统包括分别记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其特征在于，

设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))         ＝f(Dec(C，sk1)，…，Dec(C，skN))的关系成立，

{g，h}是公开密钥PK，x是0以上且q-1以下的整数、h＝g^x，r是0以上且q-1以下的整数，q是循环群G的位数，g是循环群G的生成元，明文M和密文C是循环群G的元素，C1和C2是构成密文C的元素，C＝{C1，C2}＝{g^r，Mh^r}

M＝Dec(C，x)＝C2/(C1^x)

的关系成立，

该分割保管装置包括：

解密部，利用记录的分割秘密密钥skn，如mn＝Dec(C，skn)那样求出分割明文mn，并将分割明文mn送至合并部件；以及分割秘密密钥变更部，求出

Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))         ＝f(Dec(C，sk1’)，…，Dec(C，skN’))成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，将各自记录的分割秘密密钥skn变更为skn’，其中

g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，sk1)，…，Dec(C，skN))＝Dec(C，sk1)×…×Dec(C，skN)/(C2^(N-1))。

2.一种分割保管装置，是秘密密钥分割保管系统中的一个分割保管装置，所述秘密密钥分割保管系统包括分别记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其特征在于，

设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)，mn+1为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))mN＝Dec(C，skN)

mn＝f(Dec(C，skn)，mn+1)

M＝m1

的关系成立，

{g，h}是公开密钥PK，x是0以上且q-1以下的整数、h＝g^x，r是0以上且q-1以下的整数，q是循环群G的位数，g是循环群G的生成元，明文M和密文C是循环群G的元素，C1和C2是构成密文C的元素，C＝{C1，C2}＝{g^r，Mh^r}

M＝Dec(C，x)＝C2/(C1^x)

的关系成立，

该分割保管装置包括：

解密部，在记录分割秘密密钥skN的情况下，利用分割秘密密钥skN如mN＝Dec(C，skN)那样求出分割明文mN，并将分割明文mN送至记录分割秘密密钥skN-1的所述分割保管装置，在记录分割秘密密钥sk1的情况下，利用从记录分割秘密密钥sk2的所述分割保管装置取得的分割明文m2和分割秘密密钥sk1，如M＝f(Dec(C，sk1)，m2)那样求出明文M，当N为3以上，记录分割秘密密钥skn(其中，n为2，...，N-1的其中一个)的情况下，利用从记录分割秘密密钥skn+1的所述分割保管装置取得的分割明文mn+1和分割秘密密钥skn，如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn，并将分割明文mn送至记录分割秘密密钥skn-1的所述分割保管装置；以及分割秘密密钥变更部，将分割秘密密钥skn变更为skn’，使得Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))mN＝Dec(C，skN’)

mn＝f(Dec(C，skn’)，mn+1)M＝m1

成立，并且成为与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，其中g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，skn)，mn+1)

＝(Dec(C，skn)×mn+1)/C2。

3.一种分割保管装置，是包括分别记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置的秘密密钥分割保管系统中的一个分割保管装置，其特征在于，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))         ＝f(Dec(C，sk1)，…，Dec(C，skN))的关系成立，

{G，H}是公开密钥PK，x是0以上且q-1以下的整数、H＝xG，r是0以上且q-1以下的整数，q是椭圆曲线上的基点G的位数，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝{rG，M+rH}

M＝Dec(C，x)＝C2-xC1

的关系成立，

该分割保管装置包括：

解密部，利用该分割保管装置记录的分割秘密密钥skn，如mn＝Dec(C，skn)那样求出分割明文mn，并将分割明文mn送至合并部件；以及分割秘密密钥变更部，将分割秘密密钥skn变更为skn’，使得成为Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))         ＝f(Dec(C，sk1’)，…，Dec(C，skN’))成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，其中g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，sk1)，…，Dec(C，skN))＝Dec(C，sk1)+…+Dec(C，skN)-(N-1)C2。

4.一种分割保管装置，是秘密密钥分割保管系统中的一个分割保管装置，所述秘密密钥分割保管系统包括分别记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其特征在于，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)，mn+1为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))mN＝Dec(C，skN)

mn＝f(Dec(C，skn)，mn+1)

M＝m1

的关系成立，

{G，H}是公开密钥PK，x是0以上且q-1以下的整数、H＝xG，r是0以上且q-1以下的整数，q是椭圆曲线上的基点G的位数，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝{rG，M+rH}

M＝Dec(C，x)＝C2-xC1

的关系成立，

该分割保管装置包括：

解密部，在记录分割秘密密钥skN的情况下，利用分割秘密密钥skN如mN＝Dec(C，skN)那样求出分割明文mN，并将分割明文mN送至记录分割秘密密钥skN-1的所述分割保管装置，在记录分割秘密密钥sk1的情况下，利用从记录分割秘密密钥sk2的所述分割保管装置取得的分割明文m2和分割秘密密钥sk1，如M＝f(Dec(C，sk1)，m2)那样求出明文M，当N为3以上且记录分割秘密密钥skn(其中，n为2，...，N-1的其中一个)的情况下，利用从记录分割秘密密钥skn+1的所述分割保管装置取得的分割明文mn+1和分割秘密密钥skn，如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn，并将分割明文mn送至记录分割秘密密钥skn-1的所述分割保管装置；以及分割秘密密钥变更部，将分割秘密密钥skn变更为skn’，使得分割秘密密钥的组成为Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))mN＝Dec(C，skN’)

mn＝f(Dec(C，skn’)，mn+1)M＝m1

成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，其中g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，skn)，mn+1)

＝Dec(C，skn)+mn+1-C2。

5.一种分割保管装置，是秘密密钥分割保管系统中的一个分割保管装置，所述秘密密钥分割保管系统包括分别记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其特征在于，设为N是2以上的整数，n为1以上且N以下的整数，Dec(c，SK)为表示利用秘密密钥SK对密文c进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))         ＝f(Dec(C，sk1)，…，Dec(C，skN))的关系成立，

{PID，P，Q}是公开密钥PK，SID是具有SID＝sPID的关系的位数q的椭圆曲线上的点，r是随机数，Q＝sP，PID是利用Hash函数将ID变换后的位数q的椭圆曲线上的点，P是所述椭圆曲线上的部分群的生成元，s是主秘密密钥，e(，)是所述椭圆曲线上的配对，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝{rP，M·e(PID，rQ)}M＝Dec(C，SID)＝C2·e(SID，C1)-1的关系成立，

该分割保管装置包括：

解密部，利用记录的分割秘密密钥skN，如mn＝Dec(C，skn)那样求分割明文mn，并将分割明文mn送至合并部件；以及分割秘密密钥变更部，将分割秘密密钥skn变更为skn’，使得分割秘密密钥的组成为Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))         ＝f(Dec(C，sk1’)，…，Dec(C，skN’))成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，其中g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，sk1)，…，Dec(C，skN))＝Dec(C，sk1)×…×Dec(C，skN)/(C2^(N-1))。

6.一种分割保管装置，是秘密密钥分割保管系统中的一个分割保管装置，所述秘密密钥分割保管系统包括分别记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其特征在于，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)，mn+1为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))mN＝Dec(C，skN)

mn＝f(Dec(C，skn)，mn+1)

M＝m1

的关系成立，

{PID，P，Q}是公开密钥PK，SID是具有SID＝sPID的关系的位数q的椭圆曲线上的点，r是随机数，Q＝sP，PID是利用Hash函数将ID变换后的位数q的椭圆曲线上的点，P是所述椭圆曲线上的部分群的生成元，s是主秘密密钥，e(，)是所述椭圆曲线上的配对，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝{rP，M·e(PID，rQ)}M＝Dec(C，SID)＝C2·e(SID，C1)-1的关系成立，

该分割保管装置包括：

解密部，在记录分割秘密密钥skN的情况下，利用分割秘密密钥skN如mN＝Dec(C，SkN)那样求出分割明文mN，并将分割明文mN送至记录分割秘密密钥skN-1的所述分割保管装置，在记录分割秘密密钥sk1的情况下，利用从记录分割秘密密钥sk2的所述分割保管装置取得的分割明文m2和分割秘密密钥sk1，如M＝f(Dec(C，sk1)，m2)那样求出明文M，当N为3以上且记录分割秘密密钥skn(其中，n为2，...，N-1的其中一个)的情况下，利用从记录分割秘密密钥skn+1的所述分割保管装置取得的分割明文mn+1和分割秘密密钥skn，如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn，并将分割明文mn送至记录分割秘密密钥skn-1的所述分割保管装置；以及分割秘密密钥变更部，将分割秘密密钥skn变更为skn’，使得分割秘密密钥的组成为Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))mN＝Dec(C，skN’)

mn＝f(Dec(C，skn’)，mn+1)M＝m1

成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，其中g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，skn)，mn+1)

＝(Dec(C，skn)×mn+1)/C2。

7.一种秘密密钥分割保管方法，利用了：

N个分割保管装置，分别记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个；以及合并部件，求出对密文C进行解密后的明文M，

其中，

设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))         ＝f(Dec(C，sk1)，…，Dec(C，skN))的关系成立，

{g，h}是公开密钥PK，x是0以上且q-1以下的整数、h＝g^x，r是0以上且q-1以下的整数，q是循环群G的位数，g是循环群G的生成元，明文M和密文C是循环群G的元素，C1和C2是构成密文C的元素，C＝{C1，C2}＝{g^r，Mh^r}

M＝Dec(C，x)＝C2/(C1^x)

的关系成立，

所述秘密密钥分割保管方法具有：

解密步骤，所有的所述分割保管装置利用各自记录的分割秘密密钥skn，如mn＝Dec(C，skn)那样求出分割明文mn，并将分割明文mn送至所述合并部件；

合并步骤，所述合并部件如M＝f(m1，...，mN)那样求出明文M；以及分割秘密密钥变更步骤，所述分割保管装置求出

Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))         ＝f(Dec(C，sk1’)，…，Dec(C，skN’))成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，将各自记录的分割秘密密钥skn变更为skn’，其中

g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，sk1)，…，Dec(C，skN))＝Dec(C，sk1)×…×Dec(C，skN)/(C2^(N-1))。

8.一种秘密密钥分割保管方法，利用了分别记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其中，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)，mn+1为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))mN＝Dec(C，skN)

mn＝f(Dec(C，skn)，mn+1)

M＝m1

的关系成立，

{g，h}是公开密钥PK，x是0以上且q-1以下的整数、h＝g^x，r是0以上且q-1以下的整数，q是循环群G的位数，g是循环群G的生成元，明文M和密文C是循环群G的元素，C1和C2是构成密文C的元素，C＝{C1，C2}＝{g^r，Mh^r}

M＝Dec(C，x)＝C2/(C1^x)

的关系成立，

所述秘密密钥分割保管方法具有：

第N解密步骤，记录分割秘密密钥skN的所述分割保管装置利用分割秘密密钥skN，如mN＝Dec(C，skN)那样求出分割明文mN，并将分割明文mN送至记录分割秘密密钥skN-1的所述分割保管装置；

第n解密步骤，当N为3以上的情况下，记录分割秘密密钥skn(其中，n为2，...，N-1的其中一个)的所述分割保管装置利用从记录分割秘密密钥skn+1的所述分割保管装置取得的分割明文mn+1和分割秘密密钥skn，如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn，并将分割明文mn送至记录分割秘密密钥skn-1的所述分割保管装置；

第1解密步骤，记录分割秘密密钥sk1的所述分割保管装置利用从记录分割秘密密钥sk2的所述分割保管装置取得的分割明文m2和分割秘密密钥sk1，如M＝f(Dec(C，sk1)，m2)那样求出明文M；以及分割秘密密钥变更步骤，所有的所述分割保管装置求出Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))mN＝Dec(C，skN’)

mn＝f(Dec(C，skn’)，mn+1)M＝m1

成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，将各自记录的分割秘密密钥skn变更为skn’，其中

g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，skn)，mn+1)

＝(Dec(C，skn)×mn+1)/C2。

9.一种秘密密钥分割保管方法，利用了分别记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，以及求出对密文C解密后的明文M的合并部件，其中，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))         ＝f(Dec(C，sk1)，…，Dec(C，skN))的关系成立，

{G，H}是公开密钥PK，x是0以上且q-1以下的整数、H＝xG，r是0以上且q-1以下的整数，q是椭圆曲线上的基点G的位数，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝{rG，M+rH}

M＝Dec(C，x)＝C2-xC1

的关系成立，

所述秘密密钥分割保管方法具有：

解密步骤，所有的所述分割保管装置利用各自记录的分割秘密密钥skn，如mn＝Dec(C，skn)那样求出分割明文mn，并将分割明文mn送至所述合并部件；

合并步骤，所述合并部件如M＝f(m1，...，mN)那样求出明文M；以及分割秘密密钥变更步骤，所述分割保管装置求出

Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))         ＝f(Dec(C，sk1’)，…，Dec(C，skN’))成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，将各自记录的分割秘密密钥skn变更为skn’，其中

g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，sk1)，…，Dec(C，skN))＝Dec(C，sk1)+…+Dec(C，skN)-(N-1)C2。

10.一种秘密密钥分割保管方法，利用了分别记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其中，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)，mn+1为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))mN＝Dec(C，skN)

mn＝f(Dec(C，skn)，mn+1)

M＝m1

的关系成立，

{G，H}是公开密钥PK，x是0以上且q-1以下的整数、H＝xG，r是0以上且q-1以下的整数，q是椭圆曲线上的基点G的位数，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝(rG，M+rH}

M＝Dec(C，x)＝C2-xC1

的关系成立，

所述秘密密钥分割保管方法具有：

第N解密步骤，记录分割秘密密钥skN的所述分割保管装置利用分割秘密密钥skN，如mN＝Dec(C，skN)那样求出分割明文mN，并将分割明文mN送至记录分割秘密密钥skN-1的所述分割保管装置；

第n解密步骤，当N为3以上的情况下，记录分割秘密密钥skn(其中，n为2，...，N-1的其中一个)的所述分割保管装置利用从记录分割秘密密钥skn+1的所述分割保管装置取得的分割明文mn+1和分割秘密密钥skn，如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn，并将分割明文mn送至记录分割秘密密钥skn-1的所述分割保管装置；

第1解密步骤，记录分割秘密密钥sk1的所述分割保管装置利用从记录分割秘密密钥sk2的所述分割保管装置取得的分割明文m2和分割秘密密钥sk1，如M＝f(Dec(C，sk1)，m2)那样求出明文M；以及分割秘密密钥变更步骤，所有的所述分割保管装置求出Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))mN＝Dec(C，skN’)

mn＝f(Dec(C，skn’)，mn+1)M＝m1

成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，将各自记录的分割秘密密钥skn变更为skn’，其中

g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，skn)，mn+1)

＝(Dec(C，skn)×mn+1)/C2。

11.一种秘密密钥分割保管方法，利用了分别记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其中，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))         ＝f(Dec(C，sk1)，…，Dec(C，skN))的关系成立，

{PID，P，Q}是公开密钥PK，SID是具有SID＝sPID的关系的位数q的椭圆曲线上的点，r是随机数，Q＝sP，PID是利用Hash函数将ID变换后的位数q的椭圆曲线上的点，P是所述椭圆曲线上的部分群的生成元，s是主秘密密钥，e(，)是所述椭圆曲线上的配对，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝{rP，M·e(PID，rQ)}M＝Dec(C，SID)＝C2·e(SID，C1)-1的关系成立，

所述秘密密钥分割保管方法具有：

解密步骤，利用记录的分割秘密密钥skN，如mn＝Dec(C，skn)那样求明文mn，并将分割明文mn送至合并部件；

合并步骤，所述合并部件如M＝f(m1，...，mN)那样求出明文M；以及分割秘密密钥变更步骤，所述分割保管装置求出

Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))         ＝f(Dec(C，sk1’)，…，Dec(C，skN’))成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，将各自记录的分割秘密密钥skn变更为skn’，其中

g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，sk1)，…，Dec(C，skN))＝Dec(C，sk1)×…×Dec(C，skN)/(C2^(N-1))。

12.一种秘密密钥分割保管方法，利用了分别记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，其中，设为N是2以上的整数，n为1以上且N以下的整数，Dec(c，SK)为表示利用秘密密钥SK对密文c进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)，mn+1为变量的函数，且Dec(C，SK)＝Dec(C，g(sk1，…，skN))mN＝Dec(C，skN)

mn＝f(Dec(C，skn)，mn+1)

M＝m1

的关系成立，

{PID，P，Q}是公开密钥PK，SID是具有SID＝sPID的关系的位数q的椭圆曲线上的点，r是随机数，Q＝sP，PID是利用Hash函数将ID变换后的位数q的椭圆曲线上的点，P是所述椭圆曲线上的部分群的生成元，s是主秘密密钥，e(，)是所述椭圆曲线上的配对，C1和C2是构成密文C的元素，明文M和密文CC＝{C1，C2}＝{rP，M·e(PID，rQ)}M＝Dec(C，SID)＝C2·e(SID，C1)-1的关系成立，

所述秘密密钥分割保管方法具有：

第N解密步骤，记录分割秘密密钥skN的所述分割保管装置利用分割秘密密钥skN，如mN＝Dec(C，skN)那样求出分割明文mN，并将分割明文mN送至记录分割秘密密钥skN-1的所述分割保管装置；

第n解密步骤，当N为3以上的情况下，记录分割秘密密钥skn(其中，n为2，...，N-1的其中一个)的所述分割保管装置利用从记录分割秘密密钥skn+1的所述分割保管装置取得的分割明文mn+1和分割秘密密钥skn，如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn，并将分割明文mn送至记录分割秘密密钥skn-1的所述分割保管装置；

第1解密步骤，记录分割秘密密钥sk1的所述分割保管装置利用从记录分割秘密密钥sk2的所述分割保管装置取得的分割明文m2和分割秘密密钥sk1，如M＝f(Dec(C，sk1)，m2)那样求出明文M；以及分割秘密密钥变更步骤，所有的所述分割保管装置求出Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))mN＝Dec(C，skN’)

mn＝f(Dec(C，skn’)，mn+1)M＝m1

成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1’，...，skN’)，将各自记录的分割秘密密钥skn变更为skn’，其中

g(sk1，…，skN)＝sk1+…+skN mod qf(Dec(C，skn)，mn+1)

＝(Dec(C，skn)×mn+1)/C2。

说明书

分割保管装置、秘密密钥分割保管方法

技术领域

[0001] 本发明涉及用于安全地保管用于密码/认证的秘密密钥的秘密密钥分割保管系统、分割保管装置、秘密密钥分割保管方法。

背景技术

[0002] 保管用于密码/认证的秘密密钥是重要的问题。在现代密码学中，秘密密钥不泄漏是安全性的前提。因此，为了使秘密密钥不泄漏，研究用于保管密钥的防篡改的硬件，TPM(Trusted Platform Module，可信平台模块)或HSM(Hardware security module，硬件安全模块)那样的产品正在被付诸实用。

[0003] 作为防止因秘密密钥的泄漏所导致的秘密信息泄漏的方法，还考虑更新秘密密钥的方法。作为这样的技术，已知专利文献1等。

[0004] [现有技术文献]

[0005] [专利文献]

[0006] [专利文献1]特开2012-150287号公报

发明内容

[0007] 发明要解决的课题

[0008] 但是，TPM或HSM那样的硬件大多为低速，当想要保管大量的密钥时容量不够充分。另一方面，定期或者基于规定的条件而更新秘密密钥的方法，也存在从秘密密钥泄漏起直到更新为止的期间秘密信息会泄漏的风险。

[0009] 本发明鉴于这样的课题而完成，其目的在于减少因秘密密钥的泄漏导致的秘密信息的泄漏风险。

[0010] 用于解决课题的方案

[0011] 本发明的第一秘密密钥分割保管系统，包括：加密装置，利用公开密钥PK对明文M进行加密，并输出密文C；N个分割保管装置，记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个；以及合并部件，求出对密文C进行解密后的明文M。首先，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，且

[0012] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0013]          ＝f(Dec(C，sk1)，…，Dec(C，skN))

[0014] 的关系成立。并且，在第一秘密密钥分割保管系统中，所有的分割保管装置包括解密部和分割秘密密钥变更部。解密部利用各自记录的分割秘密密钥skn，如mn＝Dec(C，skn)那样求出分割明文mn，并将分割明文mn送至合并部件。分割秘密密钥变更部求出

[0015] Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))

[0016]          ＝f(Dec(C，sk1’)，…，Dec(C，skN’))

[0017] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′。合并部件如M＝f(m1，...，mN)那样求出明文M。

[0018] 本发明的第二秘密密钥分割保管系统是包括如下装置的秘密密钥分割保管系统：加密装置，利用公开密钥PK对明文M进行加密，并输出密文C；以及N个分割保管装置，记录将与公开密钥PK对应的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个。首先，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)，mn+1为变量的函数，且

[0019] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0020] mN＝Dec(C，skN)

[0021] mn＝f(Dec(C，skn)，mn+1)

[0022] M＝m1

[0023] 的关系成立。记录分割秘密密钥skN的分割保管装置包括：解密部，该解密部利用分割秘密密钥skN如mN＝Dec(C，skN)那样求出分割明文mN，并将分割明文mN送至记录分割秘密密钥skN-1的分割保管装置。记录分割秘密密钥skn(其中，N为3以上，且n为2，...，N-1的其中一个)的分割保管装置包括：解密部，该解密部利用从记录分割秘密密钥skn+1的分割保管装置取得的分割明文mn+1和分割秘密密钥skn，如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn，并将分割明文mn送至记录分割秘密密钥skn-1的分割保管装置。记录分割秘密密钥sk1的分割保管装置包括：解密部，该解密部利用从记录分割秘密密钥sk2的分割保管装置取得的分割明文m2和分割秘密密钥sk1，如M＝f(Dec(C，sk1)，m2)那样求出明文M。所有的分割保管装置还包括：分割秘密密钥变更部，该分割秘密密钥变更部求出

[0024] Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))

[0025] mN＝Dec(C，skN’)

[0026] mn＝f(Dec(C，skn’)，mn+1)

[0027] M＝m1

[0028] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′。

[0029] 本发明的第三秘密密钥分割保管系统，包括：N个分割保管装置，记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个；以及合并部件，求出对于明文M的署名∑。首先，设为N是2以上的整数，n为1以上且N以下的整数，Sig(M，SK)为表示利用秘密密钥SK生成署名∑的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(σ1，...，σN)为以σ1，...，σN为变量的函数，且

[0030] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0031]           ＝f(Sig(M，sk1)，…，Sig(M，skN))

[0032] 的关系成立。所有的分割保管装置包括生成部和分割秘密密钥变更部。生成部利用各自记录的分割秘密密钥skn，如σn＝Sig(M，skn)那样求出分割署名σn，并将分割署名σn送至合并部件。分割秘密密钥变更部求出

[0033] Sig(M，SK)＝Sig(M，g(sk1’，…，skN’))

[0034]           ＝f(Sig(M，sk1’)，…，Sig(M，skN’))

[0035] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′。合并部件如∑＝f(σ1，...，σN)那样求出署名∑。

[0036] 本发明的第四秘密密钥分割保管系统，包括记录将秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN的其中一个的N个分割保管装置，且生成对于明文M的署名。首先，设为N是2以上的整数，n为1以上且N以下的整数，Sig(M，SK)为表示利用秘密密钥SK生成署名∑的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Sig(M，skn)，σn+1)为以Sig(M，skn)，σn+1为变量的函数，且

[0037] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0038] σN＝Sig(M，skn)

[0039] σn＝f(Sig(M，skn)，σn+1)

[0040] ∑＝σ1

[0041] 的关系成立。记录分割秘密密钥skN的分割保管装置包括：生成部，该生成部利用分割秘密密钥skN，如σN＝Sig(M，skN)那样求出分割署名σN，并将分割署名σN送至记录分割秘密密钥skN-1的分割保管装置。记录分割秘密密钥skn(其中，N为3以上，且n为2，...，N-1的其中一个)的分割保管装置包括：生成部，该生成部利用从记录分割秘密密钥skn+1的分割保管装置取得的分割署名σn+1和分割秘密密钥skn，如σn＝f(Sig(M，skn)，σn+1)那样求出分割署名σn，并将分割署名σn送至记录分割秘密密钥skn-1的分割保管装置。记录分割秘密密钥sk1的分割保管装置包括：生成部，该生成部利用从记录分割秘密密钥sk2的分割保管装置取得的分割署名σ2和分割秘密密钥sk1，如∑＝f(Sig(M，sk1)，σ2)那样求出署名∑。所有的分割保管装置还包括：分割秘密密钥变更部，该分割秘密密钥变更部求出

[0042] Sig(M，SK)＝Sig(M，g(sk1’，…，skN’))

[0043] σN＝Sig(M，skn’)

[0044] σn＝f(Sig(M，skn’)，σn+1)

[0045] ∑＝σ1

[0046] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′。

[0047] 发明效果

[0048] 根据本发明的秘密密钥分割保管系统，如果不在变更分割秘密密钥的间隔内从所有的分割保管装置盗取分割秘密密钥，则不知道秘密密钥SK。从而，与秘密密钥从一个装置泄漏的风险相比，能够大幅减少泄漏的风险。

附图说明

[0049] 图1是表示实施例1的秘密密钥分割保管系统的功能结构例的图。

[0050] 图2是表示将实施例1的秘密密钥分割保管系统的密文解密成明文的处理流程的图。

[0051] 图3是表示变更本发明的分割秘密密钥的处理流程的第一个例子的图。

[0052] 图4是表示变更本发明的分割秘密密钥的处理流程的第二个例子的图。

[0053] 图5是表示变更本发明的分割秘密密钥的处理流程的第三个例子的图。

[0054] 图6是表示实施例2的秘密密钥分割保管系统的功能结构例的图。

[0055] 图7是表示将实施例2的秘密密钥分割保管系统的密文解密成明文的处理流程的图。

[0056] 图8是表示实施例3的秘密密钥分割保管系统的功能结构例的图。

[0057] 图9是表示生成实施例3的秘密密钥分割保管系统的署名的处理流程的图。

[0058] 图10是表示实施例4的秘密密钥分割保管系统的功能结构例的图。

[0059] 图11是表示生成实施例4的秘密密钥分割保管系统的署名的处理流程的图。

具体实施方式

[0060] 以下，详细说明本发明的实施方式。另外，对于具有相同的功能的结构部附加相同的标号，并省略重复说明。

[0061] [实施例1]

[0062] 图1表示实施例1的秘密密钥分割保管系统的功能结构例。图2表示将密文解密成明文的处理流程，图3～图5表示变更分割秘密密钥的处理流程的例子。实施例1的秘密密钥分割保管系统包括在网络900上连接的加密装置600、N个分割保管装置1001，...，100N、合并部件130。加密装置600利用公开密钥PK对明文M进行加密，输出密文C。分割保管装置100n记录将对应于公开密钥PK的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN中的分割秘密密钥skn。合并部件130求出对密文C进行了解密后的明文M。在图1中，合并部件130以虚线表示在各种场所。如此，合并部件130可以是独立的一个装置，也可以在其中一个分割保管装置100n的内部具备。此外，也可以是各种装置具备合并部件130，且按照解密的每个处理流程而选择要使用哪个合并部件130。

[0063] 在此，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(m1，...，mN)为以m1，...，mN为变量的函数，^为表示取幂的记号，且如下的关系成立。

[0064] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0065]          ＝f(Dec(C，sk1)，…，Dec(C，skN))

[0066] 各个分割保管装置100n包括解密部110n、分割秘密密钥变更部120n、记录部190n。记录部190n记录分割秘密密钥skn。解密部110n利用分割秘密密钥skn，如mn＝Dec(C，skn)那样求出分割明文mn，并将分割明文mn送至合并部件130(S110n)。合并部件130如M＝f(m1，...，mN)那样求出明文M(S130)。

[0067] 分割秘密密钥变更部120n定期地或者在符合预定的条件时，求出

[0068] Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))

[0069]          ＝f(Dec(C，sk1’)，…，Dec(C，skN’))

[0070] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′(S120n)。符合预定的条件时是指，进行了预定次数的解密处理时等，适当规定即可。例如，以如果

[0071] SK＝sk1+…+skN

[0072] 的关系成立，则

[0073] Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))

[0074]          ＝f(Dec(C，sk1’)，…，Dec(C，skN’))

[0075] 成立那样决定了函数g、f的情况下，分割秘密密钥变更部120n求出成为

[0076] sk1’+…+skN’＝sk1+…+skN

[0077] 的分割秘密密钥的组(sk1′，...，skN′)即可。此外，在以如果

[0078] SK＝sk1+…+skN mod q

[0079] 的关系成立，则

[0080] Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))

[0081]          ＝f(Dec(C，sk1’)，…，Dec(C，skN’))

[0082] 成立那样决定了函数g、f的情况下，分割秘密密钥变更部120n求出成为

[0083] sk1’+…+skN’mod q＝sk1+…+skN mod q

[0084] 的分割秘密密钥的组(sk1′，...，skN′)即可。

[0085] 在图3所示的变更分割秘密密钥的处理流程的情况下，将分割保管装置100n的分割秘密密钥的变更量设为αn，分割保管装置1001，...，100N以成为

[0086] α1+…+αN＝0

[0087] 或者

[0088] α1+…+αN mod q＝0

[0089] 的方式求出α1，...，αN，分割保管装置100n取得αn(S121)。并且，分割秘密密钥变更部120n如下变更分割秘密密钥(S122n)。

[0090] skn’＝skn+αn

[0091] 图4所示的变更分割秘密密钥的处理流程的情况下，选择两个分割保管装置100i、100j。另外，i和j是1以上且N以下的i≠j的整数。此外，当N＝2的情况下，i＝1，j＝2或者i＝
2，j＝1。然后，在分割保管装置100i、100j之间共享变更量α(S121ij)。然后，分割保管装置
100i的分割秘密密钥变更部120i如

[0092] ski’＝ski+α

[0093] 那样变更分割秘密密钥，分割保管装置100j的分割秘密密钥变更部120j如[0094] skj’＝skj-α

[0095] 那样变更分割秘密密钥(S122ij)。确认是否所有的分割保管装置被选择，判断是否要重复该处理(S124)。通过该重复处理，所有的分割秘密密钥被变更。另外，这样在两个分割保管装置之间共享值α，利用α将分割秘密密钥ski、skj分别变更为ski′、skj′的方法的情况下，在共享值α的步骤(S121ij)中，能够使用认证密钥交换协议。如果是认证密钥交换协议，则使用分割保管装置100i和分割保管装置100j的双方生成的随机数来决定α，因而哪个分割保管装置都无法随意地决定α。从而，能够进一步提高安全性。

[0096] 图5所示的变更分割秘密密钥的处理流程是N＝2时的处理流程。该情况下，由于不需要选择分割保管装置，因而在分割保管装置1001、1002之间共享变更量α(S121)。然后，分割保管装置1001的分割秘密密钥变更部1201如

[0097] sk1’＝sk1+α

[0098] 那样变更分割秘密密钥，分割保管装置1002的分割秘密密钥变更部1202如[0099] sk2’＝sk2-α

[0100] 那样变更分割秘密密钥即可(S122)。该情况下也同样，在共享值α的步骤(S121)中，能够使用认证密钥交换协议。

[0101] 根据实施例1的秘密密钥分割保管系统，如果不在变更分割秘密密钥的间隔内从所有的分割保管装置盗取分割秘密密钥，则不知道秘密密钥SK。从而，与秘密密钥从一个装置泄漏的风险相比，能够大幅减少泄漏的风险。

[0102] 另外，若如下运用，则还能够将在一个装置中记录秘密密钥SK的现有的解密装置转变为实施例1的分割保管装置100N。在现有的解密装置上追加分割秘密密钥变更部120N，将在记录部1901，...，190N-1中记录了sk1＝...＝skN-1＝0的分割保管装置1001，...，100N-1连接到网络900。若这样构成，则初始状态成为skN＝SK，sk1＝...＝skN-1＝0。然后，若通过最初的分割秘密密钥的组(sk1，...，skN)的变更来分割秘密密钥，则能够构成实施例1的秘密密钥分割保管系统。从而，如果是实施例1的秘密密钥分割保管系统，则从现有的系统也能够容易转变。

[0103] <能够应用的密码方式的具体例>

[0104] 为了实现实施例1的秘密密钥分割保管系统，必须成立以下关系。

[0105] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0106]          ＝f(Dec(C，sk1)，…，Dec(C，skN))

[0107] 在此，介绍该关系成立的密码方式。但是，并不是说上述的关系要成立就限定于这些密码方式。

[0108] (1)RSA密码

[0109] 在RSA密码中，将q设为两个大的素数的合成数(积)，将公开密钥PK设为{q，e}，将秘密密钥SK设为d时，明文M和密文C成立

[0110] C＝M^e mod q

[0111] M＝Dec(C，d)＝C^d mod q

[0112] 的关系。若如

[0113] g(sk1，…，skN)＝sk1+…+skN

[0114] f(Dec(C，sk1)，…，Dec(C，skN))

[0115] ＝Dec(C，sk1)×…×Dec(C，skN)mod q

[0116] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0117] d＝SK＝sk1+…+skN

[0118] 成立，则由于

[0119] Dec(C，skn)＝C^skn mod q

[0120] ，因而成为如下。

[0121] f(Dec(C，sk1)，…，Dec(C，skN))

[0122] ＝C^(sk1+…+skN)mod q

[0123] ＝M

[0124] 从而，下式成立。

[0125] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0126]          ＝f(Dec(C，sk1)，…，Dec(C，skN))

[0127] (2)E|Gama|密码

[0128] 在E|Gama|密码中，如果将公开密钥PK设为{g，h}，将秘密密钥SK设为x，将r设为随机数(其中，h＝g^x，x和r是0以上且q-1以下的整数，q是循环群G的位数，g是循环群G的生成元)，则作为循环群G的元素的明文M和密文C成立

[0129] C＝{C1，C2}＝{g^r，Mh^r}

[0130] M＝Dec(C，x)＝C2/(C1^x)

[0131] 的关系。若如

[0132] g(sk1，…，skN)＝sk1+…+skN mod q

[0133] f(Dec(C，sk1)，…，Dec(C，skN))

[0134] ＝Dec(C，sk1)×…×Dec(C，skN)/(C2^(N-1))

[0135] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0136] x＝SK＝sk1+…+skN mod q

[0137] 成立，则由于

[0138] Dec(C，skn)＝C2/(C1^skn)

[0139] ，因而成为如下。

[0140] f(Dec(C，sk1)，…，Dec(C，skN))

[0141] ＝C2/(C1^sk1)×…×C2/(C1^skN)/(C2^(N-1))

[0142] ＝C2/(C1^(sk1+…+skN)

[0143] ＝M

[0144] 从而，下式成立。

[0145] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0146]          ＝f(Dec(C，sk1)，…，Dec(C，skN))

[0147] (3)椭圆E|Gama|密码

[0148] 在椭圆E|Gama|密码中，如果将公开密钥PK设为{G，H}，将秘密密钥SK设为x，将r设为随机数(其中，H＝xG，x是1以上且q-1以下的整数，r是0以上且q-1以下的整数，q是椭圆曲线上的基点(Base point)G的位数)，则明文M和密文C成立

[0149] C＝{C1，C2}＝{rG，M+rH}

[0150] M＝Dec(C，x)＝C2-xC1

[0151] 的关系。若如

[0152] g(sk1，…，skN)＝sk1+…+skN mod q

[0153] f(Dec(C，sk1)，…，Dec(C，skN))

[0154] ＝Dec(C，sk1)+…+Dec(C，skN)-(N-1)C2那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0155] x＝SK＝sk1+…+skN mod q

[0156] 成立，则由于

[0157] Dec(C，skn)＝C2-sknC1

[0158] ，因而成为如下。

[0159] f(Dec(C，sk1)，…，Dec(C，skN))

[0160] ＝C2-sk1C1+…+C2-skNC1-(N-1)C2

[0161] ＝C2-(sk1+…+skN)C1

[0162] ＝M

[0163] 从而，下式成立。

[0164] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0165]          ＝f(Dec(C，sk1)，…，Dec(C，skN))

[0166] (4)基于ID的密码

[0167] 在基于ID的密码中，如果将公开密钥PK设为{PID，P，Q}，将秘密密钥SK设为SID，将r设为随机数(其中，SID＝sPID，Q＝sP，PID是利用Hash函数将ID变换后的位数q的椭圆曲线上的点，P是所述椭圆曲线上的部分群的生成元，s是主秘密密钥，e(，)是所述椭圆曲线上的配对)，则明文M和密文C成立

[0168] C＝{C1，C2}＝{rP，M·e(PID，rQ)}

[0169] M＝Dec(C，SID)＝C2·e(SID，C1)-1

[0170] 的关系。若如

[0171] g(sk1，…，skN)＝sk1+…+skN mod q

[0172] f(Dec(C，sk1)，…，Dec(C，skN))

[0173] ＝Dec(C，sk1)×…×Dec(C，skN)/(C2^(N-1))

[0174] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0175] SID＝SK＝sk1+…+skN mod q

[0176] 成立，则由于

[0177] Dec(C，skn)＝C2·e(skn，C1)-1

[0178] ，因而成为如下。

[0179] f(Dec(C，sk1)，…，Dec(C，skN))

[0180] ＝C2·e(sk1，C1)-1…C2·e(skN，C1)-1/(C2^(N-1))

[0181] ＝C2·e(sk1+…+skN，C1)-1

[0182] ＝M

[0183] 从而，下式成立。

[0184] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0185]          ＝f(Dec(C，sk1)，…，Dec(C，skN))

[0186] 实施例2

[0187] 图6表示实施例2的秘密密钥分割保管系统的功能结构例，图7表示将密文解密成明文的处理流程。变更分割秘密密钥的处理流程的例子与图3～图5相同。实施例2的秘密密钥分割保管系统包括在网络900上连接的加密装置600、N个分割保管装置2001，...，200N。加密装置600利用公开密钥PK对明文M进行加密，并输出密文C。分割保管装置200n记录将对应于公开密钥PK的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN中的分割秘密密钥skn。

[0188] 在此，设为N是2以上的整数，n为1以上且N以下的整数，Dec(C，SK)为表示利用秘密密钥SK对密文C进行解密的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Dec(C，skn)，mn+1)为以Dec(C，skn)和mn+1为变量的函数，^为表示取幂的记号，且如下的关系成立。

[0189] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0190] mN＝Dec(C，skN)

[0191] mn＝f(Dec(C，skn)，mn+1)

[0192] M＝m1

[0193] 各个分割保管装置200n包括解密部210n、分割秘密密钥变更部120n、记录部190n。记录部190n记录分割秘密密钥skn。分割保管装置200N的解密部210N利用分割秘密密钥skN如mN＝Dec(C，skN)那样求出分割明文mN，并将分割明文mN送至分割保管装置200N-1(S210N)。

[0194] 分割保管装置200n(其中，n＝2，...，N-1)的解密部210n利用从分割保管装置200n+1取得的分割明文mn+1和分割秘密密钥skn如mn＝f(Dec(C，skn)，mn+1)那样求出分割明文mn。然后，将分割明文mn送至分割保管装置200n-1(S210n)。但是，当N＝2时，分割保管装置200n(其中，n＝2，...，N-1)不存在。

[0195] 分割保管装置2001的解密部2101利用从分割保管装置2002取得的分割明文m2和分割秘密密钥sk1如M＝f(Dec(C，sk1)，m2)那样求出明文M(S2101)。

[0196] 分割秘密密钥变更部120n定期地或者在符合预定的条件时，求出

[0197] Dec(C，SK)＝Dec(C，g(sk1’，…，skN’))

[0198] mN＝Dec(C，skN’)

[0199] mn＝f(Dec(C，skn’)，mn+1)

[0200] M＝m1

[0201] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′(S120n)。例如，以如果

[0202] SK＝sk1+…+skN

[0203] 的关系成立，则

[0204] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0205] mN＝Dec(C，skN)

[0206] mn＝f(Dec(C，skn)，mn+1)

[0207] M＝m1

[0208] 成立那样决定了函数g、f的情况下，求出成为

[0209] sk1’+…+skN’＝sk1+…+skN

[0210] 的分割秘密密钥的组(sk1′，...，skN′)即可。此外，在以如果

[0211] SK＝sk1+…+skN mod q

[0212] 的关系成立，则

[0213] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0214] mN＝Dec(C，skN)

[0215] mn＝f(Dec(C，skn)，mn+1)

[0216] M＝m1

[0217] 成立那样决定了函数g、f的情况下，求出成为

[0218] sk1’+…+skN’mod q＝sk1+…+skN mod q

[0219] 的分割秘密密钥的组(sk1′，...，skN′)即可。在这些例子的情况下，组(sk1′，...，skN′)所要求的条件与实施例1相同，因此变更组(sk1′，...，skN′)的流程与实施例1相同(图3～5)。

[0220] 因此，实施例2的秘密密钥分割保管系统也同样，如果不在变更分割秘密密钥的间隔内从所有的分割保管装置盗取分割秘密密钥，则不知道秘密密钥SK。从而，与秘密密钥从一个装置泄漏的风险相比，能够大幅减少泄漏的风险。

[0221] 另外，若如下运用，则还能够将在一个装置中记录着秘密密钥SK的现有的解密装置转变为实施例2的分割保管装置200N。在现有的解密装置上追加分割秘密密钥变更部120N，将在记录部1901，...，190N-1中记录了sk1＝...＝skN-1＝0的分割保管装置2001，...，
200N-1连接到网络900。若这样构成，则初始状态成为skN＝SK，sk1＝...＝skN-1＝0。然后，若通过最初的分割秘密密钥的组(sk1，...，skN)的变更来分割秘密密钥，则能够构成实施例2的秘密密钥分割保管系统。从而，如果是实施例2的秘密密钥分割保管系统，则从现有的系统也能够容易转变。

[0222] <能够应用的密码方式的具体例>

[0223] 为了实现实施例2的秘密密钥分割保管系统，必须成立以下关系。

[0224] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0225] mN＝Dec(C，skN)

[0226] mn＝f(Dec(C，skn)，mn+1)

[0227] M＝m1

[0228] 在此，介绍该关系成立的密码方式。但是，并不是说上述的关系要成立就限定于这些密码方式。

[0229] (1)RSA密码

[0230] 在RSA密码中，将q设为两个大的素数的合成数(积)，将公开密钥PK设为{q，e}，将秘密密钥SK设为d时，明文M和密文C成立

[0231] C＝M^e mod q

[0232] M＝Dec(C，d)＝C^d mod q

[0233] 的关系。因此，若如

[0234] g(sk1，…，skN)＝sk1+…+skN

[0235] f(Dec(C，skn)，mn+1)

[0236] ＝Dec(C，skn)×mn+1 mod q

[0237] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0238] d＝SK＝sk1+…+skN

[0239] 成立，则由于

[0240] mN＝Dec(C，skN)＝C^skN mod q

[0241] ，因而成为如下。

[0242] mN-1＝f(Dec(C，skN-1)，mN)

[0243] ＝C^(skN-1+skN)mod q

[0244] 然后，由于它重复，因而成为

[0245] mn＝f(Dec(C，skn)，mn+1)

[0246] ＝C^(skn+…+skN)mod q

[0247] ，成为如下。

[0248] m1＝C^(sk1+…+skN)mod q

[0249] 从而，下式成立。

[0250] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0251] mN＝Dec(C，skN)

[0252] mn＝f(Dec(C，skn)，mn+1)

[0253] M＝m1

[0254] (2)E|Gama|密码

[0255] 在E|Gama|密码中，如果将公开密钥PK设为{g，h}，将秘密密钥SK设为x，将r设为随机数(其中，h＝g^x，x和r是0以上且q-1以下的整数，q是循环群G的位数，g是循环群G的生成元)，则作为循环群G的元素的明文M和密文C成立

[0256] C＝{C1，C2}＝{g^r，Mh^r}

[0257] M＝Dec(C，x)＝C2/(C1^x)

[0258] 的关系。若如

[0259] g(sk1，…，skN)＝sk1+…+skN mod q

[0260] f(Dec(C，skn)，mn+1)

[0261] ＝(Dec(C，skn)×mn+1)/C2

[0262] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0263] x＝SK＝sk1+…+skN mod q

[0264] 成立，则由于

[0265] mN＝Dec(C，skN)＝C2/(C1^skN)mod q

[0266] ，因而成为如下。

[0267] mN-1＝f(Dec(C，skN-1)，mN)

[0268] ＝(Dec(C，skN-1)×mN)/C2

[0269] ＝(C2/(C1^skN-1)·C2/(C1^skN))/C2

[0270] ＝C2/((C1^skN-1)(C1^skN))

[0271] ＝C2/(C1^(skN-1+skN))

[0272] 然后，由于它重复，因而成为

[0273] mn＝f(Dec(C，skn)，mn+1)

[0274] ＝C2/(C1^(skn+…+skN))

[0275] ，成为如下。

[0276] m1＝C2/(C1^(sk1+…+skN))

[0277] ＝M

[0278] 从而，下式成立。

[0279] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0280] mN＝Dec(C，skN)

[0281] mn＝f(Dec(C，skn)，mn+1)

[0282] M＝m1

[0283] (3)椭圆E|Gama|密码

[0284] 在椭圆E|Gama|密码中，如果将公开密钥PK设为{G，H}，将秘密密钥SK设为x，将r设为随机数(其中，H＝xG，x是1以上且q-1以下的整数，r是0以上且q-1以下的整数，q是椭圆曲线上的基点(Base point)G的位数)，则明文M和密文C成立

[0285] C＝{C1，C2}＝{rG，M+rH}

[0286] M＝Dec(C，×)＝C2-xC1

[0287] 的关系。若如

[0288] g(sk1，…，skN)＝sk1+…+skN mod q

[0289] f(Dec(C，skn)，mn+1)

[0290] ＝Dec(C，skn)+mn+1-C2

[0291] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0292] x＝SK＝sk1+…+skN mod q

[0293] 成立，则由于

[0294] mN＝Dec(C，skN)＝C2-skNC1

[0295] ，因而成为如下。

[0296] mN-1＝f(Dec(C，skN-1)，mN)

[0297] ＝Dec(C，skN-1)+mN-C2

[0298] ＝C2-skN-1C1+C2-skNC1-C2

[0299] ＝C2-skN-1C1-skNC1

[0300] ＝C2-(skN-1+skN)C1

[0301] 然后，由于它重复，因而成为

[0302] mn＝f(Dec(C，skn)，mn+1)

[0303] ＝C2-(skn+…+skN)C1

[0304] ，成为如下。

[0305] m1＝C2-(sk1+…+skN)C1

[0306] ＝M

[0307] 从而，下式成立。

[0308] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0309] mN＝Dec(C，skN)

[0310] mn＝f(Dec(C，skn)，mn+1)

[0311] M＝m1

[0312] (4)基于ID的密码

[0313] 在基于ID的密码中，如果将公开密钥PK设为{PID，P，Q}，将秘密密钥SK设为SID，将r设为随机数(其中，SID＝sPID，Q＝sP，PID是利用Hash函数将ID变换后的位数q的椭圆曲线上的点，P是所述椭圆曲线上的部分群的生成元，s是主秘密密钥，e(，)是所述椭圆曲线上的配对)，则明文M和密文C成立

[0314] C＝{C1，C2}＝{rP，M·e(PID，rQ)}

[0315] M＝Dec(C，SID)＝C2·e(SID，C1)-1

[0316] 的关系。若如

[0317] g(sk1，…，skN)＝sk1+…+skNmod q

[0318] f(Dec(C，skn)，mn+1)

[0319] ＝(Dec(C，skn)×mn+1)/C2

[0320] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0321] SID＝SK＝sk1+…+skN mod q

[0322] 成立，则由于

[0323] mN＝Dec(C，skN)＝C2·e(skN，C1)-1

[0324] ，因而成为如下。

[0325] mN-1＝f(Dec(C，skN-1)，mN)

[0326] ＝(Dec(C，skN-1)×mN)/C2

[0327] ＝(C2·e(skN-1，C1)-1·C2·e(skN，C1)-1)/C2

[0328] ＝C2·e(skN-1，C1)-1e(skN，C1)-1

[0329] ＝C2·e(skN-1+skN，C1)-1

[0330] 然后，由于它重复，因而成为

[0331] mn＝f(Dec(C，skn)，mn+1)

[0332] ＝C2·e(skn+…+skN，C1)-1

[0333] ，成为如下。

[0334] m1＝C2·e(sk1+…+skN，C1)-1

[0335] ＝M

[0336] 从而，下式成立。

[0337] Dec(C，SK)＝Dec(C，g(sk1，…，skN))

[0338] mN＝Dec(C，skN)

[0339] mn＝f(Dec(C，skn)，mn+1)

[0340] M＝m1

[0341] 实施例3

[0342] 图8表示实施例3的秘密密钥分割保管系统的功能结构例，图9表示生成署名的处理流程。变更分割秘密密钥的处理流程与图3～5相同。实施例3的秘密密钥分割保管系统包括在网络900上连接的署名验证装置700、N个分割保管装置3001，...，300N、合并部件330。署名验证装置700是验证所制作的署名∑的正当性的装置。分割保管装置300n记录将对应于公开密钥PK的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN中的分割秘密密钥skn。合并部件330求出对于明文M的署名∑。在图8中，合并部件330以虚线表示在各种场所。如此，合并部件330可以是独立的一个装置，也可以在其中一个分割保管装置300n的内部具备。此外，也可以是各种装置具备合并部件330，且按照署名的每个处理流程而选择要使用哪个合并部件330。

[0343] 在此，设为N是2以上的整数，n为1以上且N以下的整数，Sig(M，SK)为表示利用秘密密钥SK生成署名∑的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(σ1，...，σN)为以σ1，...，σN为变量的函数，^为表示取幂的记号，且如下的关系成立。

[0344] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0345]          ＝f(Sig(M，sk1)，…，Sig(M，skN))

[0346] 各个分割保管装置300n包括生成部310n、分割秘密密钥变更部120n、记录部190n。记录部190n记录分割秘密密钥skn。生成部310n利用分割秘密密钥skn，如σn＝Sig(M，skn)那样求出分割署名σn，并将分割署名σn送至合并部件330(S310n)。合并部件如∑＝f(σ1，...，σN)那样求出署名∑(S330)。

[0347] 分割秘密密钥变更部120n定期地或者在符合预定的条件时，求出

[0348] Sig(M，SK)＝Sig(M，g(sk1’，…，skN’))

[0349]          ＝f(Sig(M，sk1’)，…，Sig(M，skN’))

[0350] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′(S120n)。例如，以如果

[0351] SK＝sk1+…+skN

[0352] 的关系成立，则

[0353] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0354]          ＝f(Sig(M，sk1)，…，Sig(M，skN))

[0355] 成立那样决定了函数g、f的情况下，求出成为

[0356] sk1’+…+skN’＝sk1+…+skN

[0357] 的分割秘密密钥的组(sk1′，...，skN′)即可。此外，在以如果

[0358] SK＝sk1+…+skN mod q

[0359] 的关系成立，则

[0360] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0361]          ＝f(Sig(M，sk1)，…，Sig(M，skN))

[0362] 成立那样决定了函数g、f的情况下，求出成为

[0363] sk1’+…+skN’mod q＝sk1+…+skN mod q

[0364] 的分割秘密密钥的组(sk1′，...，skN′)即可。在这些例子的情况下，组(sk1′，...，skN′)所要求的条件与实施例1相同，因此变更组(sk1′，...，skN′)的流程与实施例1相同(图3～5)。

[0365] 因此，实施例3的秘密密钥分割保管系统也同样，如果不在变更分割秘密密钥的间隔内从所有的分割保管装置盗取分割秘密密钥，则不知道秘密密钥SK。从而，与秘密密钥从一个装置泄漏的风险相比，能够大幅减少泄漏的风险。

[0366] 另外，若如下运用，则还能够将在一个装置中记录着秘密密钥SK的现有的署名生成装置转变为实施例3的分割保管装置300N。在现有的署名生成装置上追加分割秘密密钥变更部120N，将在记录部1901，...，190N-1中记录了sk1＝...＝skN-1＝0的分割保管装置3001，...，300N-1连接到网络900。若这样构成，则初始状态成为skN＝SK，sk1＝...＝skN-1＝
0。然后，若通过最初的分割秘密密钥的组(sk1，...，skN)的变更来分割秘密密钥，则能够构成实施例3的秘密密钥分割保管系统。从而，如果是实施例3的秘密密钥分割保管系统，则从现有的系统也能够容易转变。

[0367] <能够应用的署名方式的具体例>

[0368] 为了实现实施例3的秘密密钥分割保管系统，必须成立以下关系。

[0369] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0370]          ＝f(Sig(M，sk1)，…，Sig(M，skN))

[0371] 例如，在RSA署名的情况下，将q设为两个大的素数的合成数(积)，将公开密钥PK设为{q，e}，将秘密密钥SK设为d时，明文M和署名∑成立

[0372] ∑＝Sig(M，d)＝M^d mod q(署名生成)

[0373] M＝∑^e mod q(署名验证)

[0374] 的关系。因此，若如

[0375] g(sk1，…，skN)＝sk1+…+skN

[0376] f(Sig(M，sk1)，…，Sig(M，skN))

[0377] ＝Sig(M，sk1)×…×Sig(M，skN)mod q

[0378] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0379] d＝SK＝sk1+…+skN

[0380] 成立，则由于

[0381] Sig(M，skn)＝M^skn

[0382] ，因而成为如下。

[0383] f(Sig(M，sk1)，…，Sig(M，skN))

[0384] ＝M^(sk1+…+skN)mod q

[0385] ＝∑

[0386] 从而，下式成立。

[0387] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0388]          ＝f(Sig(M，sk1)，…，Sig(M，skN))

[0389] 但是，该说明并非要限定实现本实施例的署名方式。只要满足上述的条件则也可以是其他的署名方式。

[0390] 实施例4

[0391] 图10表示实施例4的秘密密钥分割保管系统的功能结构例，图11表示生成署名的处理流程。变更分割秘密密钥的处理流程与图3～5相同。实施例4的秘密密钥分割保管系统包括在网络900上连接的署名验证装置700、N个分割保管装置4001，...，400N。署名验证装置700是验证所制作的署名∑的正当性的装置。分割保管装置400n记录将对应于公开密钥PK的秘密密钥SK进行分割后的分割秘密密钥sk1，...，skN中的分割秘密密钥skn。

[0392] 在此，设为N是2以上的整数，n为1以上且N以下的整数，Sig(M，SK)为表示利用秘密密钥SK生成署名∑的情况的记号，g(sk1，...，skN)为以sk1，...，skN为变量的函数，f(Sig(M，skn)，σn+1)为以Sig(M，skn)，σn+1为变量的函数，^为表示取幂的记号，且如下的关系成立。

[0393] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0394] σN＝Sig(M，skN)

[0395] σn＝f(Sig(M，skn)，σn+1)

[0396] ∑＝σ1

[0397] 各个分割保管装置400n包括生成部410n、分割秘密密钥变更部120n、记录部190n。记录部190n记录分割秘密密钥skn。分割保管装置400N的生成部410N利用分割秘密密钥skN，如σN＝Sig(M，skN)那样求出分割署名σN，并将分割署名σN送至分割保管装置400N-1(S410N)。

[0398] 分割保管装置400n(其中，n＝2，...，N-1)的生成部410n利用从分割保管装置400n+1取得的分割署名σn+1和分割秘密密钥skn，如σn＝f(Sig(M，skn)，σn+1)那样求出分割署名σn，并将分割署名σn送至分割保管装置400n-1(S410n)。但是，当N＝2时，分割保管装置400n(其中，n＝2，...，N-1)不存在。分割保管装置4001利用从分割保管装置4002取得的分割署名σ2和分割秘密密钥sk1，如∑＝f(Sig(M，sk1)，σ2)那样求出署名∑(S4101)。

[0399] 分割秘密密钥变更部120n定期地或者在符合预定的条件时，求出

[0400] Sig(M，SK)＝Sig(M，g(sk1’，…，skN’))

[0401] σN＝Sig(M，skN’)

[0402] σn＝f(Sig(M，skn’)，σn+1)

[0403] ∑＝σ1

[0404] 成立，并且与(sk1，...，skN)不同的分割秘密密钥的组(sk1′，...，skN′)，将各自记录的分割秘密密钥skn变更为skn′(S120n)。例如，以如果

[0405] SK＝sk1+…+skN

[0406] 的关系成立，则

[0407] Sig(M，SK)＝Sig(M，g(sk]，…，skN))

[0408] σN＝Sig(M，skN)

[0409] σn＝f(Sig(M，skn)，σn+1)

[0410] ∑＝σ1

[0411] 成立那样决定了函数g、f的情况下，求出成为

[0412] sk1’+…+skN’＝sk1+…+skN

[0413] 的分割秘密密钥的组(sk1′，...，skN′)即可。此外，在以如果

[0414] SK＝sk1+…+skN mod q

[0415] 的关系成立，则

[0416] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0417] σN＝Sig(M，skN)

[0418] σn＝f(Sig(M，skn)，σn+1)

[0419] ∑＝σ1

[0420] 成立那样决定了函数g、f的情况下，求出成为

[0421] sk1’+…+skN’mod q＝sk1+…+skN mod q

[0422] 的分割秘密密钥的组(sk1′，...，skN′)即可。在这些例子的情况下，组(sk1′，...，skN′)所要求的条件与实施例1相同，因此变更组(sk1′，...，skN′)的流程与实施例1相同(图3～5)。

[0423] 因此，实施例4的秘密密钥分割保管系统也同样，如果不在变更分割秘密密钥的间隔内从所有的分割保管装置盗取分割秘密密钥，则不知道秘密密钥SK。从而，与秘密密钥从一个装置泄漏的风险相比，能够大幅减少泄漏的风险。

[0424] 另外，若如下运用，则还能够将在一个装置中记录着秘密密钥SK的现有的署名生成装置转变为实施例4的分割保管装置400N。在现有的署名生成装置上追加分割秘密密钥变更部120N，将在记录部1901，...，190N-1中记录了sk1＝...＝skN-1＝0的分割保管装置4001，...，400N-1连接到网络900。若这样构成，则初始状态成为skN＝SK，sk1＝...＝skN-1＝
0。然后，若通过最初的分割秘密密钥的组(sk1，...，skN)的变更来分割秘密密钥，则能够构成实施例4的秘密密钥分割保管系统。从而，如果是实施例4的秘密密钥分割保管系统，则从现有的系统也能够容易转变。

[0425] <能够应用的署名方式的具体例>

[0426] 为了实现实施例4的秘密密钥分割保管系统，必须成立以下关系。

[0427] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0428] σn＝f(Sig(M，skn)，σn+1)

[0429] 例如，在RSA署名的情况下，将q设为两个大的素数的合成数(积)，将公开密钥PK设为{q，e}，将秘密密钥SK设为d时，明文M和署名∑成立

[0430] ∑＝Sig(M，d)＝M^d mod q(署名生成)

[0431] M＝∑^e mod q(署名验证)

[0432] 的关系。因此，若如

[0433] g(sk1，…，skN)＝sk1+…+skN

[0434] f(Sig(M，skn)，σn+1)

[0435] ＝(Sig(M，skn)×σn+1 mod q

[0436] 那样决定函数g、f，并且选择分割秘密密钥的组(sk1，...，skN)使得

[0437] d＝SK＝sk1+…+skN

[0438] 成立，则由于

[0439] σN＝Sig(M，skN)＝M^skN mod q

[0440] 因而成为如下。

[0441] σN-1＝f(Sig(M，skN-1)，σN)

[0442] ＝M^(skN-1+skN)mod q

[0443] 从而，成为

[0444] σn＝f(Sig(M，skn)，σn+1)

[0445] ＝M^(skn+…+skN)mod q，

[0446] 成为如下。

[0447] m1＝M^(sk1+…+skN)mod q

[0448] ＝∑

[0449] 从而，下式成立。

[0450] Sig(M，SK)＝Sig(M，g(sk1，…，skN))

[0451] σN＝Sig(M，skN)

[0452] σn＝f(Sig(M，skn)，σn+1)

[0453] ∑＝σ1

[0454] 但是，该说明并非要限定实现本实施例的署名方式。只要满足上述的条件则也可以是其他的署名方式。

[0455] [程序、记录介质]

[0456] 上述的各种处理不仅可以按照记载以时序方式执行，也可以根据执行处理的装置的处理能力或者需要而并行地或者单独地执行。除此之外，在不脱离本发明的宗旨的范围内能够进行适当变更是不言而喻的。

[0457] 此外，在通过计算机实现上述的结构的情况下，各装置应具有的功能的处理内容由程序记述。并且，通过在计算机上执行该程序，从而在计算机上实现上述处理功能。

[0458] 记述了该处理内容的程序能够记录在计算机可读取的记录介质中。作为计算机可读取的记录介质，例如可以是磁记录介质、光盘、光磁记录介质、半导体存储器等任意介质。

[0459] 此外，该程序的流通例如通过对记录了该程序的DVD、CD-ROM等的可移动型记录介质进行销售、转让、出借等而进行。进而，也可以设为如下结构：将该程序保存到服务器计算机的存储装置中，经由网络从服务器计算机将该程序转发给其他的计算机，从而使该程序流通。

[0460] 执行这样的程序的计算机例如首先将记录在可移动型记录介质中的程序或者从服务器计算机转发的程序暂时保存到自身的存储装置。然后，在执行处理时，该计算机读取在自身的记录介质中保存的程序，执行按照读取的程序的处理。此外，作为该程序的其他执行方式，可以设为计算机从可移动型记录介质直接读取程序，执行按照该程序的处理，进而，也可以设为每当从服务器计算机向该计算机转发程序时，依次执行按照获取的程序的处理。此外，也可以设为如下结构：通过不从服务器计算机向该计算机转发程序而仅根据其执行指示和结果取得来实现处理功能的、所谓的ASP(Application Service Provider)型的服务，执行上述的处理。另外，假设在本方式的程序中包含提供用于电子计算机的处理且遵循程序的信息(不是对于计算机的直接的指令但具有规定计算机的处理的性质的数据等)。

[0461] 此外，在该方式中，设为通过使计算机执行预定的程序而构成本装置，但也可以设为将这些处理内容的至少一部分以硬件方式实现。

[0462] 标号说明

[0463] 100、200、300、400 分割保管装置

[0464] 110、210解密部         120分割秘密密钥变更部

[0465] 130、330合并部件       190记录部

[0466] 310、410生成部         600加密装置

[0467] 700署名验证装置       900网络