(57)【要約】  秘密鍵の漏洩による秘密情報の漏洩のリスクを低減する。本発明の秘密鍵分割システムは、秘密鍵ＳＫを復号時または署名生成時に統合できるように分割し、それぞれの分割秘密鍵をｋ１，…，ｓｋＮを分割保管装置で記録する。そして、定期的または所定の条件を満たす時に統合できる条件を満たす別の分割秘密鍵の組に変更する。本発明の秘密鍵分割保管システムによれば、分割秘密鍵を変更する間隔内に、すべての分割保管装置から分割秘密鍵を盗まなければ秘密鍵ＳＫが分からない。したがって、１個の装置から秘密鍵が漏洩するリスクに比べ、大幅に漏洩のリスクを低減できる。
2014112551.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵ＰＫを用いて平文Ｍを暗号化し、暗号文Ｃを出力する暗号化装置と、
前記公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
暗号文Ｃを復号した平文Ｍを求める統合手段と、
を備えた秘密鍵分割保管システムであって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
すべての前記分割保管装置は、
それぞれが記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、前記統合手段に分割平文ｍｎを送る復号部と、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
前記統合手段は、平文ＭをＭ＝ｆ（ｍ１，…，ｍＮ）のように求める
ことを特徴とする秘密鍵分割保管システム。
【請求項２】
公開鍵ＰＫを用いて平文Ｍを暗号化し、暗号文Ｃを出力する暗号化装置と、
前記公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
を備えた秘密鍵分割保管システムであって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する前記分割保管装置は、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送る復号部を備え、
分割秘密鍵ｓｋ１を記録する前記分割保管装置は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める復号部を備え、
Ｎが３以上の場合は、分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する前記分割保管装置は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る復号部を備え、
すべての前記分割保管装置は、さらに、Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部も備える
ことを特徴とする秘密鍵分割保管システム。
【請求項３】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
平文Ｍに対する署名Σを求める統合手段と、
を備えた秘密鍵分割保管システムであって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｃ，ｓｋＮ））
の関係が成り立ち、
すべての前記分割保管装置は、
それぞれが記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、前記統合手段に分割署名σｎを送る生成部と、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
前記統合手段は、署名ΣをΣ＝ｆ（σ１，…，σＮ）のように求める
ことを特徴とする秘密鍵分割保管システム。
【請求項４】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備え、平文Ｍに対する署名を生成する秘密鍵分割保管システムであって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）はＳｉｇ（Ｍ，ｓｋｎ），σｎ＋１を変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する前記分割保管装置は、分割秘密鍵ｓｋＮを用いて分割署名σＮをσＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）のように求め、分割署名σＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送る生成部を備え、
分割秘密鍵ｓｋ１を記録する前記分割保管装置は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割署名σ２と分割秘密鍵ｓｋ１を用いて署名ΣをΣ＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），σ２）のように求める生成部を備え、
Ｎが３以上の場合は、分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する前記分割保管装置は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割署名σｎ＋１と分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）のように求め、分割署名σｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る生成部を備え、
すべての前記分割保管装置は、さらに、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ’）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部も備える
ことを特徴とする秘密鍵分割保管システム。
【請求項５】
請求項１から４のいずれかに記載の秘密鍵分割保管システムであって、
ｉとｊは１以上Ｎ以下のｉ≠ｊの整数とし、
前記分割秘密鍵変更部は、いずれか２つの分割保管装置の間で認証鍵交換プロトコルを用いて値αを共有し、
前記値αを共有する分割保管装置が記録する分割秘密鍵ｓｋｉ，ｓｋｊを、αを用いてそれぞれ、ｓｋｉ’，ｓｋｊ’に変更する
ことを特徴とする秘密鍵分割保管システム。
【請求項６】
請求項１から５のいずれかに記載の秘密鍵分割保管システムであって、
初期状態がｓｋＮ＝ＳＫ，ｓｋ１＝…＝ｓｋＮ−１＝０であり、
最初の分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）の変更によって、秘密鍵を分割する
ことを特徴とする秘密鍵分割保管システム。
【請求項７】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
当該分割保管装置が記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、前記統合手段に分割平文ｍｎを送る復号部と、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【請求項８】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する場合は、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送り、
分割秘密鍵ｓｋ１を記録する場合は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める復号部と、
Ｎが３以上であって分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する場合は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送り、
分割秘密鍵の組を
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【請求項９】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｃ，ｓｋＮ））
の関係が成り立ち、
当該分割保管装置が記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、前記統合手段に分割署名σｎを送る生成部と、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【請求項１０】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）はＳｉｇ（Ｍ，ｓｋｎ），σｎ＋１を変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する場合は、分割秘密鍵ｓｋＮを用いて分割署名σＮをσＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）のように求め、分割署名σＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送り、
分割秘密鍵ｓｋ１を記録する場合は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割署名σ２と分割秘密鍵ｓｋ１を用いて署名ΣをΣ＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），σ２）のように求める生成部と、
Ｎが３以上であって分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する場合は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割署名σｎ＋１と分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）のように求め、分割署名σｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送り、
分割秘密鍵の組を
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ’）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【請求項１１】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
暗号文Ｃを復号した平文Ｍを求める統合手段と、
を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
すべての前記分割保管装置が、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、前記統合手段に分割平文ｍｎを送る復号ステップと、
前記統合手段が、平文ＭをＭ＝ｆ（ｍ１，…，ｍＮ）のように求める統合ステップと、
前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有する秘密鍵分割保管方法。
【請求項１２】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する前記分割保管装置が、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送る第Ｎ復号ステップと、
Ｎが３以上の場合は、分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する前記分割保管装置が、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る第ｎ復号ステップと、
分割秘密鍵ｓｋ１を記録する前記分割保管装置が、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める第１復号ステップと、
すべての前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有する秘密鍵分割保管方法。
【請求項１３】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
平文Ｍに対する署名Σを求める統合手段と、
を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｃ，ｓｋＮ））
の関係が成り立ち、
すべての前記分割保管装置が、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、前記統合手段に分割署名σｎを送る生成ステップと、
前記統合手段が、署名ΣをΣ＝ｆ（σ１，…，σＮ）のように求める統合ステップと、
前記分割保管装置が、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有する秘密鍵分割保管方法。
【請求項１４】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を用いて平文Ｍに対する署名を生成する秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）はＳｉｇ（Ｍ，ｓｋｎ），σｎ＋１を変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する前記分割保管装置が、分割秘密鍵ｓｋＮを用いて分割署名σＮをσＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）のように求め、分割署名σＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送る第Ｎ生成ステップと、
Ｎが３以上の場合は、分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する前記分割保管装置が、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割署名σｎ＋１と分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）のように求め、分割署名σｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る第ｎ生成ステップと、
分割秘密鍵ｓｋ１を記録する前記分割保管装置が、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割署名σ２と分割秘密鍵ｓｋ１を用いて署名ΣをΣ＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），σ２）のように求める第１生成ステップと、
すべての前記分割保管装置が、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ’）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有する秘密鍵分割保管方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号・認証のための秘密鍵を安全に保管するための秘密鍵分割保管システム、分割保管装置、秘密鍵分割保管方法に関する。
【背景技術】
【０００２】
暗号・認証のための秘密鍵を保管することは重要な問題である。現代暗号においては、秘密鍵が漏洩しないことが安全性の前提である。そのため、秘密鍵が漏洩しないようにするために、鍵を保管する耐タンパなハードウェアが研究され、ＴＰＭ（Trusted Platform Module）やＨＳＭ（Hardware security module）のような製品が実用化されている。【０００３】
秘密鍵の漏洩による秘密情報漏洩を防止する方法としては、秘密鍵を更新する方法も考えられる。このような技術としては特許文献１などが知られている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１２−１５０２８７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＴＰＭやＨＳＭのようなハードウェアは低速であり、大量の鍵を保管したい場合には容量が十分でない場合が多い。一方、秘密鍵を定期的に、または定めた条件の基に更新する方法も、秘密鍵が漏洩してから更新するまでの間に秘密情報が漏洩するリスクがある。【０００６】
本発明は、このような課題を鑑みてなされたものであり、秘密鍵の漏洩による秘密情報の漏洩のリスクを低減することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の第１の秘密鍵分割保管システムは、公開鍵ＰＫを用いて平文Ｍを暗号化し、暗号文Ｃを出力する暗号化装置と、公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つを記録するＮ個の分割保管装置と、暗号文Ｃを復号した平文Ｍを求める統合手段とを備える。まず、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立つとする。そして、第１の秘密鍵分割保管システムでは、すべての分割保管装置は、復号部と分割秘密鍵変更部とを備える。復号部は、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、統合手段に分割平文ｍｎを送る。分割秘密鍵変更部は、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する。統合手段は、平文ＭをＭ＝ｆ（ｍ１，…，ｍＮ）のように求める。【０００８】
本発明の第２の秘密鍵分割保管システムは、公開鍵ＰＫを用いて平文Ｍを暗号化し、暗号文Ｃを出力する暗号化装置と、公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つを記録するＮ個の分割保管装置とを備えた秘密鍵分割保管システムである。まず、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立つとする。分割秘密鍵ｓｋＮを記録する分割保管装置は、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する分割保管装置に送る復号部を備える。分割秘密鍵ｓｋｎ（ただし、Ｎが３以上であって、ｎが２，…，Ｎ−１のいずれか）を記録する分割保管装置は、分割秘密鍵ｓｋｎ＋１を記録する分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する分割保管装置に送る復号部を備える。分割秘密鍵ｓｋ１を記録する分割保管装置は、分割秘密鍵ｓｋ２を記録する分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める復号部を備える。すべての分割保管装置は、さらに、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部も備える。【０００９】
本発明の第３の秘密鍵分割保管システムは、秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つを記録するＮ個の分割保管装置と、平文Ｍに対する署名Σを求める統合手段とを備える。まず、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｃ，ｓｋＮ））
の関係が成り立つとする。すべての分割保管装置は、生成部と分割秘密鍵変更部を備える。生成部は、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、統合手段に分割署名σｎを送る。分割秘密鍵変更部は、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する。統合手段は、署名ΣをΣ＝ｆ（σ１，…，σＮ）のように求める。【００１０】
本発明の第４の秘密鍵分割保管システムは、秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つを記録するＮ個の分割保管装置を備え、平文Ｍに対する署名を生成する。まず、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）はＳｉｇ（Ｍ，ｓｋｎ），σｎ＋１を変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
の関係が成り立つとする。分割秘密鍵ｓｋＮを記録する分割保管装置は、分割秘密鍵ｓｋＮを用いて分割署名σＮをσＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）のように求め、分割署名σＮを、分割秘密鍵ｓｋＮ−１を記録する分割保管装置に送る生成部を備える。分割秘密鍵ｓｋｎ（ただし、Ｎが３以上であって、ｎが２，…，Ｎ−１のいずれか）を記録する分割保管装置は、分割秘密鍵ｓｋｎ＋１を記録する分割保管装置から取得した分割署名σｎ＋１と分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）のように求め、分割署名σｎを、分割秘密鍵ｓｋｎ−１を記録する分割保管装置に送る生成部を備える。分割秘密鍵ｓｋ１を記録する分割保管装置は、分割秘密鍵ｓｋ２を記録する分割保管装置から取得した分割署名σ２と分割秘密鍵ｓｋ１を用いて署名ΣをΣ＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），σ２）のように求める生成部を備える。すべての分割保管装置は、さらに、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ’）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部も備える。
【発明の効果】
【００１１】
本発明の秘密鍵分割保管システムによれば、分割秘密鍵を変更する間隔内に、すべての分割保管装置から分割秘密鍵を盗まなければ秘密鍵ＳＫが分からない。したがって、１個の装置から秘密鍵が漏洩するリスクに比べ、大幅に漏洩のリスクを低減できる。
【図面の簡単な説明】
【００１２】
【図１】実施例１の秘密鍵分割保管システムの機能構成例を示す図。
【図２】実施例１の秘密鍵分割保管システムの暗号文を平文に復号する処理フローを示す図。
【図３】本発明の分割秘密鍵を変更する処理フローの１つ目の例を示す図。
【図４】本発明の分割秘密鍵を変更する処理フローの２つ目の例を示す図。
【図５】本発明の分割秘密鍵を変更する処理フローの３つ目の例を示す図。
【図６】実施例２の秘密鍵分割保管システムの機能構成例を示す図。
【図７】実施例２の秘密鍵分割保管システムの暗号文を平文に復号する処理フローを示す図。
【図８】実施例３の秘密鍵分割保管システムの機能構成例を示す図。
【図９】実施例３の秘密鍵分割保管システムの署名を生成する処理フローを示す図。
【図１０】実施例４の秘密鍵分割保管システムの機能構成例を示す図。
【図１１】実施例４の秘密鍵分割保管システムの署名を生成する処理フローを示す図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１４】
図１に実施例１の秘密鍵分割保管システムの機能構成例を示す。図２に暗号文を平文に復号する処理フローを、図３〜５に分割秘密鍵を変更する処理フローの例を示す。実施例１の秘密鍵分割保管システムは、ネットワーク９００で接続された暗号化装置６００、Ｎ個の分割保管装置１００１，…，１００Ｎ、統合手段１３０を備える。暗号化装置６００は、公開鍵ＰＫを用いて平文Ｍを暗号化し、暗号文Ｃを出力する。分割保管装置１００ｎは、公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮの中の分割秘密鍵ｓｋｎを記録する。統合手段１３０は、暗号文Ｃを復号した平文Ｍを求める。図１では、統合手段１３０は点線で色々な場所に示している。このように、統合手段１３０は独立した１つの装置でもよいし、いずれかの分割保管装置１００ｎの内部に備えられていてもよい。また、色々な装置が統合手段１３０を備えておき、復号の処理フローごとにどの統合手段１３０を用いるのかを選択してもよい。【００１５】
ここで、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数、＾はべき乗を示す記号とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立つとする。【００１６】
それぞれの分割保管装置１００ｎは、復号部１１０ｎ、分割秘密鍵変更部１２０ｎ、記録部１９０ｎを備える。記録部１９０ｎは、分割秘密鍵ｓｋｎを記録している。復号部１１０ｎは、分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、統合手段１３０に分割平文ｍｎを送る（Ｓ１１０ｎ）。統合手段１３０は、平文ＭをＭ＝ｆ（ｍ１，…，ｍＮ）のように求める（Ｓ１３０）。【００１７】
分割秘密鍵変更部１２０ｎは、定期的に、または所定の条件に適合したときに、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する（Ｓ１２０ｎ）。所定の条件に適合したときとは、所定の回数復号の処理を行ったときなどであり、適宜定めればよい。例えば、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ
の関係が成り立てば
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立つように、関数ｇ、ｆを決めた場合、分割秘密鍵変更部１２０ｎは、
ｓｋ１’＋…＋ｓｋＮ’  ＝  ｓｋ１＋…＋ｓｋＮ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。また、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
の関係が成り立てば
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立つように、関数ｇ、ｆを決めた場合、分割秘密鍵変更部１２０ｎは、
ｓｋ１’＋…＋ｓｋＮ’  ｍｏｄ  ｑ  ＝  ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。【００１８】
図３に示した分割秘密鍵を変更する処理フローの場合、分割保管装置１００ｎの分割秘密鍵の変更分をαｎとし、分割保管装置１００１，…，１００Ｎが、
α１＋…＋αＮ  ＝０
または
α１＋…＋αＮ  ｍｏｄ  ｑ  ＝０
となるように、α１，…，αＮを求め、分割保管装置１００ｎがαｎを取得する（Ｓ１２１）。そして、分割秘密鍵変更部１２０ｎが
ｓｋｎ’＝ｓｋｎ＋αｎ
のように分割秘密鍵を変更する（Ｓ１２２ｎ）。【００１９】
図４に示した分割秘密鍵を変更する処理フローの場合、２つの分割保管装置１００ｉ，１００ｊを選択する。なお、ｉとｊは１以上Ｎ以下のｉ≠ｊの整数である。また、Ｎ＝２の場合は、ｉ＝１，ｊ＝２またはｉ＝２，ｊ＝１である。そして、分割保管装置１００ｉ，１００ｊの間で変更分αを共有する（Ｓ１２１ｉｊ）。そして、分割保管装置１００ｉの分割秘密鍵変更部１２０ｉが
ｓｋｉ’＝ｓｋｉ＋α
のように分割秘密鍵を変更し、分割保管装置１００ｊの分割秘密鍵変更部１２０ｊが
ｓｋｊ’＝ｓｋｊ−α
のように分割秘密鍵を変更する（Ｓ１２２ｉｊ）。すべての分割保管装置が選択されたかを確認し、この処理を繰り返すかを判断する（Ｓ１２４）。この繰り返し処理によってすべての分割秘密鍵が変更される。なお、このように２つの分割保管装置の間で値αを共有し、分割秘密鍵ｓｋｉ，ｓｋｊを、αを用いてそれぞれ、ｓｋｉ’，ｓｋｊ’に変更する方法の場合、値αを共有するステップ（Ｓ１２１ｉｊ）では、認証鍵交換プロトコルを用いることができる。認証鍵交換プロトコルであれば、分割保管装置１００ｉと分割保管装置１００ｊの両方が生成した乱数を用いてαが決まるので、いずれの分割保管装置も恣意的にαを決めることができない。したがって、より安全性を高くできる。【００２０】
図５に示した分割秘密鍵を変更する処理フローは、Ｎ＝２の場合の処理フローである。この場合は、分割保管装置を選択する必要がないので、分割保管装置１００１，１００２の間で変更分αを共有する（Ｓ１２１）。そして、分割保管装置１００１の分割秘密鍵変更部１２０１が
ｓｋ１’＝ｓｋ１＋α
のように分割秘密鍵を変更し、分割保管装置１００２の分割秘密鍵変更部１２０２が
ｓｋ２’＝ｓｋ２−α
のように分割秘密鍵を変更すればよい（Ｓ１２２）。この場合も、値αを共有するステップ（Ｓ１２１）では、認証鍵交換プロトコルを用いることができる。【００２１】
実施例１の秘密鍵分割保管システムによれば、分割秘密鍵を変更する間隔内に、すべての分割保管装置から分割秘密鍵を盗まなければ秘密鍵ＳＫが分からない。したがって、１個の装置から秘密鍵が漏洩するリスクに比べ、大幅に漏洩のリスクを低減できる。【００２２】
なお、以下のように運用すれば、秘密鍵ＳＫを１個の装置で記録している既存の復号装置を、実施例１の分割保管装置１００Ｎに移行することも可能である。既存の復号装置に分割秘密鍵変更部１２０Ｎを追加し、記録部１９０１，…，１９０Ｎ−１にｓｋ１＝…＝ｓｋＮ−１＝０を記録した分割保管装置１００１，…，１００Ｎ−１をネットワーク９００につなぐ。このように構成すれば、初期状態がｓｋＮ＝ＳＫ，ｓｋ１＝…＝ｓｋＮ−１＝０となる。そして、最初の分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）の変更によって、秘密鍵を分割すれば、実施例１の秘密鍵分割保管システムを構成できる。したがって、実施例１の秘密鍵分割保管システムであれば、既存のシステムからも容易に移行できる。【００２３】
＜適用できる暗号方式の具体例＞
実施例１の秘密鍵分割保管システムを実現するためには、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立たなければならない。ここでは、この関係が成り立つ暗号方式を紹介する。ただし、上記の関係が成り立てば、これらの暗号方式に限定するものではない。【００２４】
（１）ＲＳＡ暗号
ＲＳＡ暗号では、ｑを２つの大きい素数の合成数（積）とし、公開鍵ＰＫを｛ｑ，ｅ｝、秘密鍵ＳＫをｄとすると、平文Ｍと暗号文Ｃは、
Ｃ＝Ｍ＾ｅ  ｍｏｄ  ｑ
Ｍ＝Ｄｅｃ（Ｃ，ｄ）＝Ｃ＾ｄ  ｍｏｄ  ｑ
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）×…×Ｄｅｃ（Ｃ，ｓｋＮ）  ｍｏｄ  ｑ
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｄ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ
が成り立つように選択すれば、
Ｄｅｃ（Ｃ，ｓｋｎ）＝Ｃ＾ｓｋｎ  ｍｏｄ  ｑ
なので、
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｃ＾（ｓｋ１＋…＋ｓｋＮ）  ｍｏｄ  ｑ
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
が成り立つ。【００２５】
（２）ＥｌＧａｍａｌ暗号
ＥｌＧａｍａｌ暗号では、公開鍵ＰＫを｛ｇ，ｈ｝、秘密鍵ＳＫをｘ、ｒを乱数とすると（ただし、ｈ＝ｇ＾ｘ、ｘとｒは０以上ｑ−１以下の整数、ｑは巡回群Ｇの位数、ｇは巡回群Ｇの生成元）、巡回群Ｇの要素である平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｇ＾ｒ，Ｍｈ＾ｒ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２／（Ｃ１＾ｘ）
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）×…×Ｄｅｃ（Ｃ，ｓｋＮ）／（Ｃ２＾（Ｎ−１））
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｘ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
が成り立つように選択すれば、
Ｄｅｃ（Ｃ，ｓｋｎ）＝Ｃ２／（Ｃ１＾ｓｋｎ）
なので、
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｃ２／（Ｃ１＾ｓｋ１）×…×Ｃ２／（Ｃ１＾ｓｋＮ）／（Ｃ２＾（Ｎ−１））
＝Ｃ２／（Ｃ１＾（ｓｋ１＋…＋ｓｋＮ）
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
が成り立つ。【００２６】
（３）楕円ＥｌＧａｍａｌ暗号
楕円ＥｌＧａｍａｌ暗号では、公開鍵ＰＫを｛Ｇ，Ｈ｝、秘密鍵ＳＫをｘ、ｒを乱数とすると（ただし、Ｈ＝ｘＧ、ｘは１以上ｑ−１以下の整数、ｒは０以上ｑ−１以下の整数、ｑは楕円曲線上のベースポイントＧの位数）、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＧ，Ｍ＋ｒＨ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２−ｘＣ１
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）＋…＋Ｄｅｃ（Ｃ，ｓｋＮ）−（Ｎ−１）Ｃ２
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｘ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
が成り立つように選択すれば、
Ｄｅｃ（Ｃ，ｓｋｎ）＝Ｃ２−ｓｋｎＣ１
なので、
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｃ２−ｓｋ１Ｃ１＋…＋Ｃ２−ｓｋＮＣ１−（Ｎ−１）Ｃ２
＝Ｃ２−（ｓｋ１＋…＋ｓｋＮ）Ｃ１
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
が成り立つ。【００２７】
（４）ＩＤベース暗号
ＩＤベース暗号では、公開鍵ＰＫを｛ＰＩＤ，Ｐ，Ｑ｝、秘密鍵ＳＫをＳＩＤ、ｒを乱数とすると（ただし、ＳＩＤ＝ｓＰＩＤ、Ｑ＝ｓＰ、ＰＩＤはＩＤをハッシュ関数を用いて変換した位数ｑの楕円曲線上の点、Ｐは前記楕円曲線上の部分群の生成元、ｓはマスター秘密鍵、ｅ（，）は前記楕円曲線上のペアリング）、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＰ，Ｍ・ｅ（ＰＩＤ，ｒＱ）｝
Ｍ＝Ｄｅｃ（Ｃ，ＳＩＤ）＝Ｃ２・ｅ（ＳＩＤ，Ｃ１）−１
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）×…×Ｄｅｃ（Ｃ，ｓｋＮ）／（Ｃ２＾（Ｎ−１））
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ＳＩＤ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
が成り立つように選択すれば、
Ｄｅｃ（Ｃ，ｓｋｎ）＝Ｃ２・ｅ（ｓｋｎ，Ｃ１）−１
なので、
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｃ２・ｅ（ｓｋ１，Ｃ１）−１…Ｃ２・ｅ（ｓｋＮ，Ｃ１）−１／（Ｃ２＾（Ｎ−１））
＝Ｃ２・ｅ（ｓｋ１＋…＋ｓｋＮ，Ｃ１）−１
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
が成り立つ。
【実施例２】
【００２８】
図６に実施例２の秘密鍵分割保管システムの機能構成例を、図７に暗号文を平文に復号する処理フローを示す。分割秘密鍵を変更する処理フローの例は、図３〜５と同じである。実施例２の秘密鍵分割保管システムは、ネットワーク９００で接続された暗号化装置６００、Ｎ個の分割保管装置２００１，…，２００Ｎを備える。暗号化装置６００は、公開鍵ＰＫを用いて平文Ｍを暗号化し、暗号文Ｃを出力する。分割保管装置２００ｎは、公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮの中の分割秘密鍵ｓｋｎを記録する。【００２９】
ここで、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ）とｍｎ＋１を変数とする関数、＾はべき乗を示す記号とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立つとする。【００３０】
それぞれの分割保管装置２００ｎは、復号部２１０ｎ、分割秘密鍵変更部１２０ｎ、記録部１９０ｎを備える。記録部１９０ｎは、分割秘密鍵ｓｋｎを記録している。分割保管装置２００Ｎの復号部２１０Ｎは、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを分割保管装置２００Ｎ−１に送る（Ｓ２１０Ｎ）。【００３１】
分割保管装置２００ｎ（ただし、ｎ＝２，…，Ｎ−１）の復号部２１０ｎは、分割保管装置ｎ＋１から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて、分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求める。そして、分割平文ｍｎを、分割保管装置２００ｎ−１に送る（Ｓ２１０ｎ）。ただし、Ｎ＝２の場合は、分割保管装置２００ｎ（ただし、ｎ＝２，…，Ｎ−１）は存在しない。【００３２】
分割保管装置２００１の復号部２１０１は、分割保管装置２００２から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて、平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める（Ｓ２１０１）。【００３３】
分割秘密鍵変更部１２０ｎは、定期的に、または所定の条件に適合したときに、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する（Ｓ１２０ｎ）。例えば、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ
の関係が成り立てば
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’  ＝  ｓｋ１＋…＋ｓｋＮ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。また、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
の関係が成り立てば
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’  ｍｏｄ  ｑ  ＝  ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。これらの例の場合、組（ｓｋ１’，…，ｓｋＮ’）に求められる条件は実施例１と同じなので、組（ｓｋ１’，…，ｓｋＮ’）を変更するフローは、実施例１と同じである（図３〜５）。【００３４】
よって、実施例２の秘密鍵分割保管システムでも、分割秘密鍵を変更する間隔内に、すべての分割保管装置から分割秘密鍵を盗まなければ秘密鍵ＳＫが分からない。したがって、１個の装置から秘密鍵が漏洩するリスクに比べ、大幅に漏洩のリスクを低減できる。【００３５】
なお、以下のように運用すれば、秘密鍵ＳＫを１個の装置で記録している既存の復号装置を、実施例２の分割保管装置２００Ｎに移行することも可能である。既存の復号装置に分割秘密鍵変更部１２０Ｎを追加し、記録部１９０１，…，１９０Ｎ−１にｓｋ１＝…＝ｓｋＮ−１＝０を記録した分割保管装置２００１，…，２００Ｎ−１をネットワーク９００につなぐ。このように構成すれば、初期状態がｓｋＮ＝ＳＫ，ｓｋ１＝…＝ｓｋＮ−１＝０となる。そして、最初の分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）の変更によって、秘密鍵を分割すれば、実施例２の秘密鍵分割保管システムを構成できる。したがって、実施例２の秘密鍵分割保管システムであれば、既存のシステムからも容易に移行できる。【００３６】
＜適用できる暗号方式の具体例＞
実施例２の秘密鍵分割保管システムを実現するためには、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立たなければならない。ここでは、この関係が成り立つ暗号方式を紹介する。ただし、上記の関係が成り立てば、これらの暗号方式に限定するものではない。【００３７】
（１）ＲＳＡ暗号
ＲＳＡ暗号では、ｑを２つの大きい素数の合成数（積）とし、公開鍵ＰＫを｛ｑ，ｅ｝、秘密鍵ＳＫをｄとすると、平文Ｍと暗号文Ｃは、
Ｃ＝Ｍ＾ｅ  ｍｏｄ  ｑ
Ｍ＝Ｄｅｃ（Ｃ，ｄ）＝Ｃ＾ｄ  ｍｏｄ  ｑ
の関係が成り立つ。そこで、関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１  ｍｏｄ  ｑ
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｄ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ
が成り立つように選択すれば、
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）＝Ｃ＾ｓｋＮ  ｍｏｄ  ｑ
なので、
ｍＮ−１＝ｆ（Ｄｅｃ（Ｃ，ｓｋＮ−１），ｍＮ）
＝Ｃ＾（ｓｋＮ−１＋ｓｋＮ）  ｍｏｄ  ｑ
となる。そして、これが繰り返されるので、
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｃ＾（ｓｋｎ＋・・・＋ｓｋＮ）  ｍｏｄ  ｑ
となり、
ｍ１＝Ｃ＾（ｓｋ１＋・・・＋ｓｋＮ）  ｍｏｄ  ｑ
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
が成り立つ。【００３８】
（２）ＥｌＧａｍａｌ暗号
ＥｌＧａｍａｌ暗号では、公開鍵ＰＫを｛ｇ，ｈ｝、秘密鍵ＳＫをｘ、ｒを乱数とすると（ただし、ｈ＝ｇ＾ｘ、ｘとｒは０以上ｑ−１以下の整数、ｑは巡回群Ｇの位数、ｇは巡回群Ｇの生成元）、巡回群Ｇの要素である平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｇ＾ｒ，Ｍｈ＾ｒ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２／（Ｃ１＾ｘ）
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝（Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１）／Ｃ２
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｘ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
が成り立つように選択すれば、
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）＝Ｃ２／（Ｃ１＾ｓｋＮ）  ｍｏｄ  ｑ
なので、
ｍＮ−１＝ｆ（Ｄｅｃ（Ｃ，ｓｋＮ−１），ｍＮ）
＝（Ｄｅｃ（Ｃ，ｓｋＮ−１）×ｍＮ）／Ｃ２
＝（Ｃ２／（Ｃ１＾ｓｋＮ−１）・Ｃ２／（Ｃ１＾ｓｋＮ））／Ｃ２
＝Ｃ２／（（Ｃ１＾ｓｋＮ−１）（Ｃ１＾ｓｋＮ））
＝Ｃ２／（Ｃ１＾（ｓｋＮ−１＋ｓｋＮ））
となる。そして、これが繰り返されるので、
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｃ２／（Ｃ１＾（ｓｋｎ＋・・・＋ｓｋＮ））
となり、
ｍ１＝Ｃ２／（Ｃ１＾（ｓｋｎ＋・・・＋ｓｋＮ））
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
が成り立つ。【００３９】
（３）楕円ＥｌＧａｍａｌ暗号
楕円ＥｌＧａｍａｌ暗号では、公開鍵ＰＫを｛Ｇ，Ｈ｝、秘密鍵ＳＫをｘ、ｒを乱数とすると（ただし、Ｈ＝ｘＧ、ｘは１以上ｑ−１以下の整数、ｒは０以上ｑ−１以下の整数、ｑは楕円曲線上のベースポイントＧの位数）、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＧ，Ｍ＋ｒＨ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２−ｘＣ１
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｄｅｃ（Ｃ，ｓｋｎ）＋ｍｎ＋１−Ｃ２
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｘ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
が成り立つように選択すれば、
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）＝Ｃ２−ｓｋＮＣ１
なので、
ｍＮ−１＝ｆ（Ｄｅｃ（Ｃ，ｓｋＮ−１），ｍＮ）
＝Ｄｅｃ（Ｃ，ｓｋＮ−１）＋ｍＮ−Ｃ２
＝Ｃ２−ｓｋＮ−１Ｃ１＋Ｃ２−ｓｋＮＣ１−Ｃ２
＝Ｃ２−ｓｋＮ−１Ｃ１−ｓｋＮＣ１
＝Ｃ２−（ｓｋＮ−１＋ｓｋＮ）Ｃ１
となる。そして、これが繰り返されるので、
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｃ２−（ｓｋｎ＋・・・＋ｓｋＮ）Ｃ１
となり、
ｍ１＝Ｃ２−（ｓｋ１＋・・・＋ｓｋＮ）Ｃ１
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
が成り立つ。【００４０】
（４）ＩＤベース暗号
ＩＤベース暗号では、公開鍵ＰＫを｛ＰＩＤ，Ｐ，Ｑ｝、秘密鍵ＳＫをＳＩＤ、ｒを乱数とすると（ただし、ＳＩＤ＝ｓＰＩＤ、Ｑ＝ｓＰ、ＰＩＤはＩＤをハッシュ関数を用いて変換した位数ｑの楕円曲線上の点、Ｐは前記楕円曲線上の部分群の生成元、ｓはマスター秘密鍵、ｅ（，）は前記楕円曲線上のペアリング）、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＰ，Ｍ・ｅ（ＰＩＤ，ｒＱ）｝
Ｍ＝Ｄｅｃ（Ｃ，ＳＩＤ）＝Ｃ２・ｅ（ＳＩＤ，Ｃ１）−１
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝（Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１）／Ｃ２
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ＳＩＤ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
が成り立つように選択すれば、
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）＝Ｃ２・ｅ（ｓｋＮ，Ｃ１）−１
なので、
ｍＮ−１＝ｆ（Ｄｅｃ（Ｃ，ｓｋＮ−１），ｍＮ）
＝（Ｄｅｃ（Ｃ，ｓｋＮ−１）×ｍＮ）／Ｃ２
＝（Ｃ２・ｅ（ｓｋＮ−１，Ｃ１）−１・Ｃ２・ｅ（ｓｋＮ，Ｃ１）−１）／Ｃ２
＝Ｃ２・ｅ（ｓｋＮ−１，Ｃ１）−１ｅ（ｓｋＮ，Ｃ１）−１
＝Ｃ２・ｅ（ｓｋＮ−１＋ｓｋＮ，Ｃ１）−１
となる。そして、これが繰り返されるので、
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｃ２・ｅ（ｓｋｎ＋・・・＋ｓｋＮ，Ｃ１）−１
となり、
ｍ１＝Ｃ２・ｅ（ｓｋ１＋・・・＋ｓｋＮ，Ｃ１）−１
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
が成り立つ。
【実施例３】
【００４１】
図８に実施例３の秘密鍵分割保管システムの機能構成例を、図９に署名を生成する処理フローを示す。分割秘密鍵を変更する処理フローは図３〜５と同じである。実施例３の秘密鍵分割保管システムは、ネットワーク９００で接続された署名検証装置７００、Ｎ個の分割保管装置３００１，…，３００Ｎ、統合手段３３０を備える。署名検証装置７００は、作成された署名Σの正当性を検証する装置である。分割保管装置３００ｎは、公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮの中の分割秘密鍵ｓｋｎを記録する。統合手段３３０は、平文Ｍに対する署名Σを求める。図８では、統合手段３３０は点線で色々な場所に示している。このように、統合手段３３０は独立した１つの装置でもよいし、いずれかの分割保管装置３００ｎの内部に備えられていてもよい。また、色々な装置が統合手段３３０を備えておき、署名の処理フローごとにどの統合手段３３０を用いるのかを選択してもよい。【００４２】
ここで、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数、＾はべき乗を示す記号とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｃ，ｓｋＮ））
の関係が成り立つとする。【００４３】
それぞれの分割保管装置３００ｎは、生成部３１０ｎ、分割秘密鍵変更部１２０ｎ、記録部１９０ｎを備える。記録部１９０ｎは、分割秘密鍵ｓｋｎを記録している。生成部３１０ｎは、分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、統合手段３３０に分割署名σｎを送る（Ｓ３１０ｎ）。統合手段は、署名ΣをΣ＝ｆ（σ１，…，σＮ）のように求める（Ｓ３３０）。【００４４】
分割秘密鍵変更部１２０ｎは、定期的に、または所定の条件に適合したときに、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する（Ｓ１２０ｎ）。例えば、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｃ，ｓｋＮ））
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’  ＝  ｓｋ１＋…＋ｓｋＮ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。また、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｃ，ｓｋＮ））
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’  ｍｏｄ  ｑ  ＝  ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。これらの例の場合、組（ｓｋ１’，…，ｓｋＮ’）に求められる条件は実施例１と同じなので、組（ｓｋ１’，…，ｓｋＮ’）を変更するフローは、実施例１と同じである（図３〜５）。【００４５】
よって、実施例３の秘密鍵分割保管システムでも、分割秘密鍵を変更する間隔内に、すべての分割保管装置から分割秘密鍵を盗まなければ秘密鍵ＳＫが分からない。したがって、１個の装置から秘密鍵が漏洩するリスクに比べ、大幅に漏洩のリスクを低減できる。【００４６】
なお、以下のように運用すれば、秘密鍵ＳＫを１個の装置で記録している既存の署名生成装置を、実施例３の分割保管装置３００Ｎに移行することも可能である。既存の署名生成装置に分割秘密鍵変更部１２０Ｎを追加し、記録部１９０１，…，１９０Ｎ−１にｓｋ１＝…＝ｓｋＮ−１＝０を記録した分割保管装置３００１，…，３００Ｎ−１をネットワーク９００につなぐ。このように構成すれば、初期状態がｓｋＮ＝ＳＫ，ｓｋ１＝…＝ｓｋＮ−１＝０となる。そして、最初の分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）の変更によって、秘密鍵を分割すれば、実施例３の秘密鍵分割保管システムを構成できる。したがって、実施例３の秘密鍵分割保管システムであれば、既存のシステムからも容易に移行できる。【００４７】
＜適用できる署名方式の具体例＞
実施例３の秘密鍵分割保管システムを実現するためには、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
の関係が成り立たなければならない。例えば、ＲＳＡ署名の場合は、ｑを２つの大きい素数の合成数（積）とし、公開鍵ＰＫを｛ｑ，ｅ｝、秘密鍵ＳＫをｄとすると、平文Ｍと署名Σは、
Σ＝Ｓｉｇ（Ｍ，ｄ）＝Ｍ＾ｄ  ｍｏｄ  ｑ    （署名生成）
Ｍ＝Σ＾ｅ  ｍｏｄ  ｑ                      （署名検証）
の関係が成り立つ。そこで、関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ
ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
＝Ｓｉｇ（Ｍ，ｓｋ１）×…×Ｓｉｇ（Ｍ，ｓｋＮ）  ｍｏｄ  ｑ
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｄ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ
が成り立つように選択すれば、
Ｓｉｇ（Ｍ，ｓｋｎ）＝Ｍ＾ｓｋｎ
なので、
ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
＝Ｍ＾（ｓｋ１＋…＋ｓｋＮ）  ｍｏｄ  ｑ
＝Σ
となる。したがって、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
が成り立つ。ただし、この説明は本実施例を実現する署名方式を限定するものではない。上記の条件を満足すれば別の署名方式でもよい。
【実施例４】
【００４８】
図１０に実施例４の秘密鍵分割保管システムの機能構成例を、図１１に署名を生成する処理フローを示す。分割秘密鍵を変更する処理フローの例は、図３〜５と同じである。実施例４の秘密鍵分割保管システムは、ネットワーク９００で接続された署名検証装置７００、Ｎ個の分割保管装置４００１，…，４００Ｎを備える。署名検証装置７００は、作成された署名Σの正当性を検証する装置である。分割保管装置４００ｎは、公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮの中の分割秘密鍵ｓｋｎを記録する。【００４９】
ここで、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）はＳｉｇ（Ｍ，ｓｋｎ），σｎ＋１を変数とする関数、＾はべき乗を示す記号とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋｎ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
の関係が成り立つとする。【００５０】
それぞれの分割保管装置４００ｎは、生成部４１０ｎ、分割秘密鍵変更部１２０ｎ、記録部１９０ｎを備える。記録部１９０ｎは、分割秘密鍵ｓｋｎを記録している。分割保管装置４００Ｎの生成部４１０Ｎは、分割秘密鍵ｓｋＮを用いて分割署名σＮをσＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）のように求め、分割署名σＮを、分割保管装置４００Ｎ−１に送る（Ｓ４１０Ｎ）。【００５１】
分割保管装置４００ｎ（ただし、ｎ＝２，…，Ｎ−１）の生成部４１０ｎは、分割保管装置４００ｎ＋１から取得した分割署名σｎ＋１と分割秘密鍵ｓｋｎを用いて、分割署名σｎをσｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）のように求める。そして、分割署名σｎを、分割保管装置４００ｎ−１に送る（Ｓ４１０ｎ）。ただし、Ｎ＝２の場合は、分割保管装置４００ｎ（ｎ＝２，…，Ｎ−１）は存在しない。分割保管装置４００１は、分割保管装置４００２から取得した分割署名σ２と分割秘密鍵ｓｋ１を用いて署名ΣをΣ＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），σ２）のように求める（Ｓ４１０１）。【００５２】
分割秘密鍵変更部１２０ｎは、定期的に、または所定の条件に適合したときに、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋｎ’）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する（Ｓ１２０ｎ）。例えば、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋｎ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’   ｍｏｄ  ｑ  ＝  ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。また、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋｎ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’   ｍｏｄ  ｑ  ＝  ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。これらの例の場合、組（ｓｋ１’，…，ｓｋＮ’）に求められる条件は実施例１と同じなので、組（ｓｋ１’，…，ｓｋＮ’）を変更するフローは、実施例１と同じである（図３〜５）。【００５３】
よって、実施例４の秘密鍵分割保管システムでも、分割秘密鍵を変更する間隔内に、すべての分割保管装置から分割秘密鍵を盗まなければ秘密鍵ＳＫが分からない。したがって、１個の装置から秘密鍵が漏洩するリスクに比べ、大幅に漏洩のリスクを低減できる。【００５４】
なお、以下のように運用すれば、秘密鍵ＳＫを１個の装置で記録している既存の署名生成装置を、実施例４の分割保管装置４００Ｎに移行することも可能である。既存の署名生成装置に分割秘密鍵変更部１２０Ｎを追加し、記録部１９０１，…，１９０Ｎ−１にｓｋ１＝…＝ｓｋＮ−１＝０を記録した分割保管装置４００１，…，４００Ｎ−１をネットワーク９００につなぐ。このように構成すれば、初期状態がｓｋＮ＝ＳＫ，ｓｋ１＝…＝ｓｋＮ−１＝０となる。そして、最初の分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）の変更によって、秘密鍵を分割すれば、実施例４の秘密鍵分割保管システムを構成できる。したがって、実施例４の秘密鍵分割保管システムであれば、既存のシステムからも容易に移行できる。【００５５】
＜適用できる署名方式の具体例＞
実施例４の秘密鍵分割保管システムを実現するためには、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
の関係が成り立たなければならない。例えば、ＲＳＡ署名の場合は、ｑを２つの大きい素数の合成数（積）とし、公開鍵ＰＫを｛ｑ，ｅ｝、秘密鍵ＳＫをｄとすると、平文Ｍと署名Σは、
Σ＝Ｓｉｇ（Ｍ，ｄ）＝Ｍ＾ｄ  ｍｏｄ  ｑ    （署名生成）
Ｍ＝Σ＾ｅ  ｍｏｄ  ｑ                      （署名検証）
の関係が成り立つ。そこで、関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ
ｆ（Ｓｉｎ（Ｍ，ｓｋｎ），ｍｎ＋１）
＝（Ｓｉｎ（Ｍ，ｓｋｎ）×ｍｎ＋１  ｍｏｄ  ｑ
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｄ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ
が成り立つように選択すれば、
σＮ＝Ｓｉｇ（Ｍ，ｓｋｎ）＝Ｍ＾ｓｋＮ  ｍｏｄ  ｑ
なので、
σＮ−１＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），σｎ＋１）
＝Ｍ＾（ｓｋＮ−１＋ｓｋＮ）  ｍｏｄ  ｑ
＝Σ
となる。したがって、
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
＝Ｍ＾（ｓｋｎ＋・・・＋ｓｋＮ）  ｍｏｄ  ｑ
となり、
ｍ１＝Ｍ＾（ｓｋ１＋・・・＋ｓｋＮ）  ｍｏｄ  ｑ
＝Σ
となる。したがって、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋｎ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立つ。ただし、この説明は本実施例を実現する署名方式を限定するものではない。上記の条件を満足すれば別の署名方式でもよい。【００５６】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。【００５７】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。【００５８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。【００５９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。【００６０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。【００６１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００６２】
１００，２００，３００，４００  分割保管装置
１１０，２１０  復号部                １２０  分割秘密鍵変更部
１３０，３３０  統合手段              １９０  記録部
３１０，４１０  生成部                ６００  暗号化装置
７００  署名検証装置                  ９００  ネットワーク
【図１】
2014112551.tif 000003
【図２】
2014112551.tif 000004
【図３】
2014112551.tif 000005
【図４】
2014112551.tif 000006
【図５】
2014112551.tif 000007
【図６】
2014112551.tif 000008
【図７】
2014112551.tif 000009
【図８】
2014112551.tif 000010
【図９】
2014112551.tif 000011
【図１０】
2014112551.tif 000012
【図１１】
2014112551.tif 000013
【手続補正書】
【提出日】平成27年7月10日(2015.7.10)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
本発明の第３の秘密鍵分割保管システムは、秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つを記録するＮ個の分割保管装置と、平文Ｍに対する署名Σを求める統合手段とを備える。まず、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
の関係が成り立つとする。すべての分割保管装置は、生成部と分割秘密鍵変更部を備える。生成部は、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、統合手段に分割署名σｎを送る。分割秘密鍵変更部は、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｍ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する。統合手段は、署名ΣをΣ＝ｆ（σ１，…，σＮ）のように求める。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
分割保管装置２００ｎ（ただし、ｎ＝２，…，Ｎ−１）の復号部２１０ｎは、分割保管装置２００ｎ＋１から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて、分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求める。そして、分割平文ｍｎを、分割保管装置２００ｎ−１に送る（Ｓ２１０ｎ）。ただし、Ｎ＝２の場合は、分割保管装置２００ｎ（ただし、ｎ＝２，…，Ｎ−１）は存在しない。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
（２）ＥｌＧａｍａｌ暗号
ＥｌＧａｍａｌ暗号では、公開鍵ＰＫを｛ｇ，ｈ｝、秘密鍵ＳＫをｘ、ｒを乱数とすると（ただし、ｈ＝ｇ＾ｘ、ｘとｒは０以上ｑ−１以下の整数、ｑは巡回群Ｇの位数、ｇは巡回群Ｇの生成元）、巡回群Ｇの要素である平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｇ＾ｒ，Ｍｈ＾ｒ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２／（Ｃ１＾ｘ）
の関係が成り立つ。関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝（Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１）／Ｃ２
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｘ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
が成り立つように選択すれば、
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）＝Ｃ２／（Ｃ１＾ｓｋＮ）  ｍｏｄ  ｑ
なので、
ｍＮ−１＝ｆ（Ｄｅｃ（Ｃ，ｓｋＮ−１），ｍＮ）
＝（Ｄｅｃ（Ｃ，ｓｋＮ−１）×ｍＮ）／Ｃ２
＝（Ｃ２／（Ｃ１＾ｓｋＮ−１）・Ｃ２／（Ｃ１＾ｓｋＮ））／Ｃ２
＝Ｃ２／（（Ｃ１＾ｓｋＮ−１）（Ｃ１＾ｓｋＮ））
＝Ｃ２／（Ｃ１＾（ｓｋＮ−１＋ｓｋＮ））
となる。そして、これが繰り返されるので、
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｃ２／（Ｃ１＾（ｓｋｎ＋・・・＋ｓｋＮ））
となり、
ｍ１＝Ｃ２／（Ｃ１＾（ｓｋ１＋・・・＋ｓｋＮ））
＝Ｍ
となる。したがって、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
が成り立つ。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００４２
【補正方法】変更
【補正の内容】
【００４２】
ここで、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数、＾はべき乗を示す記号とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
の関係が成り立つとする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００４４
【補正方法】変更
【補正の内容】
【００４４】
分割秘密鍵変更部１２０ｎは、定期的に、または所定の条件に適合したときに、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｍ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する（Ｓ１２０ｎ）。例えば、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’  ＝  ｓｋ１＋…＋ｓｋＮ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。また、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’  ｍｏｄ  ｑ  ＝  ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。これらの例の場合、組（ｓｋ１’，…，ｓｋＮ’）に求められる条件は実施例１と同じなので、組（ｓｋ１’，…，ｓｋＮ’）を変更するフローは、実施例１と同じである（図３〜５）。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
ここで、Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）はＳｉｇ（Ｍ，ｓｋｎ），σｎ＋１を変数とする関数、＾はべき乗を示す記号とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
の関係が成り立つとする。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
分割秘密鍵変更部１２０ｎは、定期的に、または所定の条件に適合したときに、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ’）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する（Ｓ１２０ｎ）。例えば、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’＝ｓｋ１＋…＋ｓｋＮ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。また、
ＳＫ＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
の関係が成り立てば
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
が成り立つように、関数ｇ、ｆを決めた場合、
ｓｋ１’＋…＋ｓｋＮ’   ｍｏｄ  ｑ  ＝  ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
となる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求めればよい。これらの例の場合、組（ｓｋ１’，…，ｓｋＮ’）に求められる条件は実施例１と同じなので、組（ｓｋ１’，…，ｓｋＮ’）を変更するフローは、実施例１と同じである（図３〜５）。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】変更
【補正の内容】
【００５５】
＜適用できる署名方式の具体例＞
実施例４の秘密鍵分割保管システムを実現するためには、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
の関係が成り立たなければならない。例えば、ＲＳＡ署名の場合は、ｑを２つの大きい素数の合成数（積）とし、公開鍵ＰＫを｛ｑ，ｅ｝、秘密鍵ＳＫをｄとすると、平文Ｍと署名Σは、
Σ＝Ｓｉｇ（Ｍ，ｄ）＝Ｍ＾ｄ  ｍｏｄ  ｑ    （署名生成）
Ｍ＝Σ＾ｅ  ｍｏｄ  ｑ                      （署名検証）
の関係が成り立つ。そこで、関数ｇ、ｆを、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ
ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
＝（Ｓｉｇ（Ｍ，ｓｋｎ）×σｎ＋１  ｍｏｄ  ｑ
のように定め、分割秘密鍵の組（ｓｋ１，…，ｓｋＮ）を、
ｄ＝ＳＫ＝ｓｋ１＋…＋ｓｋＮ
が成り立つように選択すれば、
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）＝Ｍ＾ｓｋＮ  ｍｏｄ  ｑ
なので、
σＮ−１＝ｆ（Ｓｉｇ（Ｍ，ｓｋＮ−１），σN）
＝Ｍ＾（ｓｋＮ−１＋ｓｋＮ）  ｍｏｄ  ｑ
となる。したがって、
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
＝Ｍ＾（ｓｋｎ＋・・・＋ｓｋＮ）  ｍｏｄ  ｑ
となり、
ｍ１＝Ｍ＾（ｓｋ１＋・・・＋ｓｋＮ）  ｍｏｄ  ｑ
＝Σ
となる。したがって、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
が成り立つ。ただし、この説明は本実施例を実現する署名方式を限定するものではない。上記の条件を満足すれば別の署名方式でもよい。
【手続補正９】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項３
【補正方法】変更
【補正の内容】
【請求項３】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
平文Ｍに対する署名Σを求める統合手段と、
を備えた秘密鍵分割保管システムであって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
の関係が成り立ち、
すべての前記分割保管装置は、
それぞれが記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、前記統合手段に分割署名σｎを送る生成部と、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｍ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
前記統合手段は、署名ΣをΣ＝ｆ（σ１，…，σＮ）のように求める
ことを特徴とする秘密鍵分割保管システム。
【手続補正１０】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項５
【補正方法】変更
【補正の内容】
【請求項５】
請求項１から４のいずれかに記載の秘密鍵分割保管システムであって、
ｉとｊは１以上Ｎ以下のｉ≠ｊの整数とし、
いずれか２つの分割保管装置の前記分割秘密鍵変更部は、認証鍵交換プロトコルを用いて値αを共有し、
前記値αを共有する分割保管装置が記録する分割秘密鍵ｓｋｉ，ｓｋｊを、αを用いてそれぞれ、ｓｋｉ’，ｓｋｊ’に変更する
ことを特徴とする秘密鍵分割保管システム。
【手続補正１１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７
【補正方法】変更
【補正の内容】
【請求項７】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
当該分割保管装置が記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、統合手段に分割平文ｍｎを送る復号部と、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【手続補正１２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項８
【補正方法】変更
【補正の内容】
【請求項８】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する場合は、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送り、
分割秘密鍵ｓｋ１を記録する場合は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求め、
Ｎが３以上であって分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する場合は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る復号部と、
分割秘密鍵の組を
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【手続補正１３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
の関係が成り立ち、
当該分割保管装置が記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、統合手段に分割署名σｎを送る生成部と、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｍ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【手続補正１４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）はＳｉｇ（Ｍ，ｓｋｎ），σｎ＋１を変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）
Σ＝σ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する場合は、分割秘密鍵ｓｋＮを用いて分割署名σＮをσＮ＝Ｓｉｇ（Ｍ，ｓｋＮ）のように求め、分割署名σＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送り、
分割秘密鍵ｓｋ１を記録する場合は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割署名σ２と分割秘密鍵ｓｋ１を用いて署名ΣをΣ＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），σ２）のように求め、
Ｎが３以上であって分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する場合は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割署名σｎ＋１と分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ），σｎ＋１）のように求め、分割署名σｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る生成部と、
分割秘密鍵の組を
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
σＮ＝Ｓｉｇ（Ｍ，ｓｋＮ’）
σｎ＝ｆ（Ｓｉｇ（Ｍ，ｓｋｎ’），σｎ＋１）
Σ＝σ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備える
ことを特徴とする分割保管装置。
【手続補正１５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１３
【補正方法】変更
【補正の内容】
【請求項１３】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
平文Ｍに対する署名Σを求める統合手段と、
を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｓｉｇ（Ｍ，ＳＫ）は秘密鍵ＳＫを用いて署名Σを生成することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（σ１，…，σＮ）はσ１，…，σＮを変数とする関数とし、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１），…，Ｓｉｇ（Ｍ，ｓｋＮ））
の関係が成り立ち、
すべての前記分割保管装置が、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割署名σｎをσｎ＝Ｓｉｇ（Ｍ，ｓｋｎ）のように求め、前記統合手段に分割署名σｎを送る生成ステップと、
前記統合手段が、署名ΣをΣ＝ｆ（σ１，…，σＮ）のように求める統合ステップと、
前記分割保管装置が、
Ｓｉｇ（Ｍ，ＳＫ）＝Ｓｉｇ（Ｍ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｓｉｇ（Ｍ，ｓｋ１’），…，Ｓｉｇ（Ｍ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有する秘密鍵分割保管方法。
【手続補正１６】
【補正対象書類名】図面
【補正対象項目名】図１０
【補正方法】変更
【補正の内容】
【図１０】
2014112551.tif 000014
【手続補正書】
【提出日】平成28年9月8日(2016.9.8)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
｛ｇ，ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、ｈ＝ｇ＾ｘ、ｒは０以上ｑ−１以下の整数、ｑは巡回群Ｇの位数、ｇは巡回群Ｇの生成元、平文Ｍと暗号文Ｃは巡回群Ｇの要素であり、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｇ＾ｒ，Ｍｈ＾ｒ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２／（Ｃ１＾ｘ）
の関係が成り立ち、
当該分割保管装置が記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、統合手段に分割平文ｍｎを送る復号部と、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）×…×Ｄｅｃ（Ｃ，ｓｋＮ）／（Ｃ２＾（Ｎ−１））
であることを特徴とする分割保管装置。
【請求項２】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
｛ｇ，ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、ｈ＝ｇ＾ｘ、ｒは０以上ｑ−１以下の整数、ｑは巡回群Ｇの位数、ｇは巡回群Ｇの生成元、平文Ｍと暗号文Ｃは巡回群Ｇの要素であり、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｇ＾ｒ，Ｍｈ＾ｒ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２／（Ｃ１＾ｘ）
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する場合は、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送り、
分割秘密鍵ｓｋ１を記録する場合は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求め、
Ｎが３以上であって分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する場合は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る復号部と、
分割秘密鍵の組を
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝（Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１）／Ｃ２
であることを特徴とする分割保管装置。
【請求項３】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
｛Ｇ，Ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、Ｈ＝ｘＧ、ｒは０以上ｑ−１以下の整数、ｑは楕円曲線上のベースポイントＧの位数、平文Ｍと暗号文Ｃは
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＧ，Ｍ＋ｒＨ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２−ｘＣ１
の関係が成り立ち、
当該分割保管装置が記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、統合手段に分割平文ｍｎを送る復号部と、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）＋…＋Ｄｅｃ（Ｃ，ｓｋＮ）−（Ｎ−１）Ｃ２
であることを特徴とする分割保管装置。
【請求項４】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
｛Ｇ，Ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、Ｈ＝ｘＧ、ｒは０以上ｑ−１以下の整数、ｑは楕円曲線上のベースポイントＧの位数、平文Ｍと暗号文Ｃは
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＧ，Ｍ＋ｒＨ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２−ｘＣ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する場合は、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送り、
分割秘密鍵ｓｋ１を記録する場合は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求め、
Ｎが３以上であって分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する場合は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る復号部と、
分割秘密鍵の組を
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｄｅｃ（Ｃ，ｓｋｎ）＋ｍｎ＋１−Ｃ２
であることを特徴とする分割保管装置。
【請求項５】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
｛ＰＩＤ，Ｐ，Ｑ｝は公開鍵ＰＫ、ＳＩＤはＳＩＤ＝ｓＰＩＤである秘密鍵ＳＫ、ｒは乱数、Ｑ＝ｓＰ、ＰＩＤはＩＤをハッシュ関数を用いて変換した位数ｑの楕円曲線上の点、Ｐは前記楕円曲線上の部分群の生成元、ｓはマスター秘密鍵、ｅ（，）は前記楕円曲線上のペアリング、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＰ，Ｍ・ｅ（ＰＩＤ，ｒＱ）｝
Ｍ＝Ｄｅｃ（Ｃ，ＳＩＤ）＝Ｃ２・ｅ（ＳＩＤ，Ｃ１）−１
の関係が成り立ち、
当該分割保管装置が記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、統合手段に分割平文ｍｎを送る復号部と、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）×…×Ｄｅｃ（Ｃ，ｓｋＮ）／（Ｃ２＾（Ｎ−１））
であることを特徴とする分割保管装置。
【請求項６】
秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を備えた秘密鍵分割保管システムの中の１つの分割保管装置であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
｛ＰＩＤ，Ｐ，Ｑ｝は公開鍵ＰＫ、ＳＩＤはＳＩＤ＝ｓＰＩＤである秘密鍵ＳＫ、ｒは乱数、Ｑ＝ｓＰ、ＰＩＤはＩＤをハッシュ関数を用いて変換した位数ｑの楕円曲線上の点、Ｐは前記楕円曲線上の部分群の生成元、ｓはマスター秘密鍵、ｅ（，）は前記楕円曲線上のペアリング、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＰ，Ｍ・ｅ（ＰＩＤ，ｒＱ）｝
Ｍ＝Ｄｅｃ（Ｃ，ＳＩＤ）＝Ｃ２・ｅ（ＳＩＤ，Ｃ１）−１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する場合は、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送り、
分割秘密鍵ｓｋ１を記録する場合は、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求め、
Ｎが３以上であって分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する場合は、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る復号部と、
分割秘密鍵の組を
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）となるように分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更部と
を備え、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝（Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１）／Ｃ２
であることを特徴とする分割保管装置。
【請求項７】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
暗号文Ｃを復号した平文Ｍを求める統合手段と、
を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
｛ｇ，ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、ｈ＝ｇ＾ｘ、ｒは０以上ｑ−１以下の整数、ｑは巡回群Ｇの位数、ｇは巡回群Ｇの生成元、平文Ｍと暗号文Ｃは巡回群Ｇの要素であり、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｇ＾ｒ，Ｍｈ＾ｒ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２／（Ｃ１＾ｘ）
の関係が成り立ち、
すべての前記分割保管装置が、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、前記統合手段に分割平文ｍｎを送る復号ステップと、
前記統合手段が、平文ＭをＭ＝ｆ（ｍ１，…，ｍＮ）のように求める統合ステップと、
前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有し、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）×…×Ｄｅｃ（Ｃ，ｓｋＮ）／（Ｃ２＾（Ｎ−１））
であることを特徴とする秘密鍵分割保管方法。
【請求項８】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
｛ｇ，ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、ｈ＝ｇ＾ｘ、ｒは０以上ｑ−１以下の整数、ｑは巡回群Ｇの位数、ｇは巡回群Ｇの生成元、平文Ｍと暗号文Ｃは巡回群Ｇの要素であり、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｇ＾ｒ，Ｍｈ＾ｒ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２／（Ｃ１＾ｘ）
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する前記分割保管装置が、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送る第Ｎ復号ステップと、
Ｎが３以上の場合は、分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する前記分割保管装置が、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る第ｎ復号ステップと、
分割秘密鍵ｓｋ１を記録する前記分割保管装置が、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める第１復号ステップと、
すべての前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有し、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝（Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１）／Ｃ２
であることを特徴とする秘密鍵分割保管方法。
【請求項９】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
暗号文Ｃを復号した平文Ｍを求める統合手段と、
を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
｛Ｇ，Ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、Ｈ＝ｘＧ、ｒは０以上ｑ−１以下の整数、ｑは楕円曲線上のベースポイントＧの位数、平文Ｍと暗号文Ｃは
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＧ，Ｍ＋ｒＨ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２−ｘＣ１
の関係が成り立ち、
すべての前記分割保管装置が、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、前記統合手段に分割平文ｍｎを送る復号ステップと、
前記統合手段が、平文ＭをＭ＝ｆ（ｍ１，…，ｍＮ）のように求める統合ステップと、
前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有し、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）＋…＋Ｄｅｃ（Ｃ，ｓｋＮ）−（Ｎ−１）Ｃ２
であることを特徴とする秘密鍵分割保管方法。
【請求項１０】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
｛Ｇ，Ｈ｝は公開鍵ＰＫ、ｘは０以上ｑ−１以下の整数であって秘密鍵ＳＫ、Ｈ＝ｘＧ、ｒは０以上ｑ−１以下の整数、ｑは楕円曲線上のベースポイントＧの位数、平文Ｍと暗号文Ｃは
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＧ，Ｍ＋ｒＨ｝
Ｍ＝Ｄｅｃ（Ｃ，ｘ）＝Ｃ２−ｘＣ１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する前記分割保管装置が、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送る第Ｎ復号ステップと、
Ｎが３以上の場合は、分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する前記分割保管装置が、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る第ｎ復号ステップと、
分割秘密鍵ｓｋ１を記録する前記分割保管装置が、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める第１復号ステップと、
すべての前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有し、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝Ｄｅｃ（Ｃ，ｓｋｎ）＋ｍｎ＋１−Ｃ２
であることを特徴とする秘密鍵分割保管方法。
【請求項１１】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置と、
暗号文Ｃを復号した平文Ｍを求める統合手段と、
を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（ｍ１，…，ｍＮ）はｍ１，…，ｍＮを変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
の関係が成り立ち、
｛ＰＩＤ，Ｐ，Ｑ｝は公開鍵ＰＫ、ＳＩＤはＳＩＤ＝ｓＰＩＤである秘密鍵ＳＫ、ｒは乱数、Ｑ＝ｓＰ、ＰＩＤはＩＤをハッシュ関数を用いて変換した位数ｑの楕円曲線上の点、Ｐは前記楕円曲線上の部分群の生成元、ｓはマスター秘密鍵、ｅ（，）は前記楕円曲線上のペアリング、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＰ，Ｍ・ｅ（ＰＩＤ，ｒＱ）｝
Ｍ＝Ｄｅｃ（Ｃ，ＳＩＤ）＝Ｃ２・ｅ（ＳＩＤ，Ｃ１）−１
の関係が成り立ち、
すべての前記分割保管装置が、それぞれが記録する分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝Ｄｅｃ（Ｃ，ｓｋｎ）のように求め、前記統合手段に分割平文ｍｎを送る復号ステップと、
前記統合手段が、平文ＭをＭ＝ｆ（ｍ１，…，ｍＮ）のように求める統合ステップと、
前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１’），…，Ｄｅｃ（Ｃ，ｓｋＮ’））
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有し、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋ１），…，Ｄｅｃ（Ｃ，ｓｋＮ））
＝Ｄｅｃ（Ｃ，ｓｋ１）×…×Ｄｅｃ（Ｃ，ｓｋＮ）／（Ｃ２＾（Ｎ−１））
であることを特徴とする秘密鍵分割保管方法。
【請求項１２】
公開鍵ＰＫに対応する秘密鍵ＳＫを分割した分割秘密鍵ｓｋ１，…，ｓｋＮのいずれか１つをそれぞれが記録するＮ個の分割保管装置を用いた秘密鍵分割保管方法であって、
Ｎは２以上の整数、ｎは１以上Ｎ以下の整数、Ｄｅｃ（Ｃ，ＳＫ）は秘密鍵ＳＫを用いて暗号文Ｃを復号することを示す記号、ｇ（ｓｋ１，…，ｓｋＮ）はｓｋ１，…，ｓｋＮを変数とする関数、ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）はＤｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１を変数とする関数とし、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１，…，ｓｋＮ））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
Ｍ＝ｍ１
の関係が成り立ち、
｛ＰＩＤ，Ｐ，Ｑ｝は公開鍵ＰＫ、ＳＩＤはＳＩＤ＝ｓＰＩＤである秘密鍵ＳＫ、ｒは乱数、Ｑ＝ｓＰ、ＰＩＤはＩＤをハッシュ関数を用いて変換した位数ｑの楕円曲線上の点、Ｐは前記楕円曲線上の部分群の生成元、ｓはマスター秘密鍵、ｅ（，）は前記楕円曲線上のペアリング、平文Ｍと暗号文Ｃは、
Ｃ＝｛Ｃ１，Ｃ２｝＝｛ｒＰ，Ｍ・ｅ（ＰＩＤ，ｒＱ）｝
Ｍ＝Ｄｅｃ（Ｃ，ＳＩＤ）＝Ｃ２・ｅ（ＳＩＤ，Ｃ１）−１
の関係が成り立ち、
分割秘密鍵ｓｋＮを記録する前記分割保管装置が、分割秘密鍵ｓｋＮを用いて分割平文ｍＮをｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ）のように求め、分割平文ｍＮを、分割秘密鍵ｓｋＮ−１を記録する前記分割保管装置に送る第Ｎ復号ステップと、
Ｎが３以上の場合は、分割秘密鍵ｓｋｎ（ただし、ｎは２，…，Ｎ−１のいずれか）を記録する前記分割保管装置が、分割秘密鍵ｓｋｎ＋１を記録する前記分割保管装置から取得した分割平文ｍｎ＋１と分割秘密鍵ｓｋｎを用いて分割平文ｍｎをｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）のように求め、分割平文ｍｎを、分割秘密鍵ｓｋｎ−１を記録する前記分割保管装置に送る第ｎ復号ステップと、
分割秘密鍵ｓｋ１を記録する前記分割保管装置が、分割秘密鍵ｓｋ２を記録する前記分割保管装置から取得した分割平文ｍ２と分割秘密鍵ｓｋ１を用いて平文ＭをＭ＝ｆ（Ｄｅｃ（Ｃ，ｓｋ１），ｍ２）のように求める第１復号ステップと、
すべての前記分割保管装置が、
Ｄｅｃ（Ｃ，ＳＫ）＝Ｄｅｃ（Ｃ，ｇ（ｓｋ１’，…，ｓｋＮ’））
ｍＮ＝Ｄｅｃ（Ｃ，ｓｋＮ’）
ｍｎ＝ｆ（Ｄｅｃ（Ｃ，ｓｋｎ’），ｍｎ＋１）
Ｍ＝ｍ１
が成り立ち、かつ（ｓｋ１，…，ｓｋＮ）とは異なる分割秘密鍵の組（ｓｋ１’，…，ｓｋＮ’）を求め、それぞれが記録する分割秘密鍵ｓｋｎをｓｋｎ’に変更する分割秘密鍵変更ステップと
を有し、
ｇ（ｓｋ１，…，ｓｋＮ）＝ｓｋ１＋…＋ｓｋＮ  ｍｏｄ  ｑ
ｆ（Ｄｅｃ（Ｃ，ｓｋｎ），ｍｎ＋１）
＝（Ｄｅｃ（Ｃ，ｓｋｎ）×ｍｎ＋１）／Ｃ２
であることを特徴とする秘密鍵分割保管方法。
【国際調査報告】
2014112551.tif 000015
2014112551.tif 000016
2014112551.tif 000017
2014112551.tif 000018