(57)【要約】  分散情報管理装置１２１〜１２ｎは、秘密情報Ｓｔを分散符号化して生成された主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）を管理する。分散情報管理装置１２ｍは、主分散情報Ｓｍ（ｍ）を分散符号化することで再分散情報ＳＲｍ（ｍ，１）〜ＳＲｍ（ｍ，ｎ）を生成し、当該再分散情報ＳＲｍ（ｍ，１）〜ＳＲｍ（ｍ，ｎ）を他の全ての分散情報管理装置１２１〜１２ｎに供給する。分散情報管理装置１２ｍは、他の全ての分散情報管理装置１２１〜１２ｎから供給された再分散情報ＳＲｍ（１，ｍ）〜ＳＲｍ（ｎ，ｍ）に基づいて新主分散情報Ｓｎ（ｍ）を生成する。主分散情報Ｓｍ（ｍ）は新主分散情報Ｓｎ（ｍ）で置換される。
2009020078.tif 000002
【特許請求の範囲】
【請求項１】
秘密情報を分散符号化して生成された複数の主分散情報を管理するｎ個の分散情報管理装置からなる分散情報管理システムであって、
前記ｎ個の分散情報管理装置のうちｍ番目の分散情報管理装置（ｍは１〜ｎのうちの任意整数）は、
前記主分散情報のうちのｍ番目の主分散情報を保管する情報保管部と、
前記ｍ番目の主分散情報を分散符号化することにより複数の再分散情報を生成し前記再分散情報を前記分散情報管理システムに属する他の全ての分散情報管理装置に供給する主分散情報分散部と、
前記他の全ての分散情報管理装置から供給された再分散情報に基づいて新主分散情報を生成する分散情報生成部と、
を有し、
前記情報保管部に保管される主分散情報は、前記新主分散情報で置換されることにより更新されることを特徴とする分散情報管理システム。
【請求項２】
請求項１記載の分散情報管理システムであって、
前記情報保管部は、前記各主分散情報を分散符号化して生成された副分散情報のうちのｍ番目の副分散情報の集合を保管するとともに、前記分散情報管理システムに属する他の分散情報管理装置からの供給要求に応答して前記ｍ番目の副分散情報の集合のうち当該他の分散情報管理装置に対応する副分散情報を供給する機能を有し、
前記ｍ番目の分散情報管理装置は、
前記分散情報管理装置のうちの一部の分散情報管理装置から前記再分散情報を取得することに失敗したとき、当該一部の分散情報管理装置以外の分散情報管理装置の情報保管部に対して副分散情報の供給要求を発する要求生成部と、
当該供給要求に応じて供給された副分散情報を復号して主分散情報を復元する情報再構成部と、
当該復元された主分散情報を分散符号化することにより当該一部の分散情報管理装置からの取得に失敗した再分散情報を生成し、当該生成された再分散情報を前記分散情報生成部に供給する分散符号化部と、
を含む情報復元部をさらに有することを特徴とする分散情報管理システム。
【請求項３】
請求項２記載の分散情報管理システムであって、前記情報復元部は、前記供給要求に応じて供給された副分散情報の正当性を当該副分散情報に付加された検証情報を用いて検証する情報検証部を含むことを特徴とする分散情報管理システム。
【請求項４】
請求項１から３のうちのいずれか１項に記載の分散情報管理システムであって、前記主分散情報分散部は、前記他の全ての分散情報管理装置に供給すべき再分散情報の正当性を検証するための検証情報を生成し前記再分散情報に付加することを特徴とする分散情報管理システム。
【請求項５】
請求項４記載の分散情報管理システムであって、前記分散情報生成部は、前記他の全ての分散情報管理装置から供給された再分散情報の正当性を当該再分散情報に付加された検証情報を用いて検証する情報検証部を含むことを特徴とする分散情報管理システム。
【請求項６】
請求項１から５のうちのいずれか１項に記載の分散情報管理システムであって、前記主分散情報分散部は、独立変数に乗ずるべき係数と前記主分散情報を含む定数項とを有する生成多項式を用いて前記再分散情報を生成し、前記情報保管部は、前記生成多項式の係数を主分散パラメータとして保管することを特徴とする分散情報管理システム。
【請求項７】
請求項６記載の分散情報管理システムであって、
前記ｍ番目の分散情報管理装置は、
前記情報保管部に保管される主分散パラメータを分散符号化することにより複数の再分散パラメータを生成し前記再分散パラメータを前記分散情報管理システムに属する他の分散情報管理装置に供給する第１パラメータ分散部と、
前記他の分散情報管理装置から供給された再分散パラメータに基づいて新主分散パラメータを生成するパラメータ生成部と、
を有し、
前記情報保管部に保管される主分散パラメータは、前記新主分散パラメータで置換されることにより更新されることを特徴とする分散情報管理システム。
【請求項８】
請求項７記載の分散情報管理システムであって、前記第１パラメータ分散部は、前記主分散パラメータを複数のセグメントに分割し、前記セグメントの値を係数として有する生成多項式を用いて前記再分散パラメータを生成することを特徴とする分散情報管理システム。
【請求項９】
請求項７または８記載の分散情報管理システムであって、
前記情報保管部は、前記各主分散パラメータを分散符号化して生成された複数の副分散パラメータのうちのｍ番目の副分散パラメータの集合を保管するとともに、前記分散情報管理システムに属する他の分散情報管理装置からの供給要求に応答して前記ｍ番目の副分散パラメータの集合のうち当該他の分散情報管理装置に対応する副分散パラメータを供給する機能を有し、
前記ｍ番目の分散情報管理装置は、
前記他の分散情報管理装置のうちの一部の分散情報管理装置から前記再分散パラメータを取得することに失敗したとき、当該一部の分散情報管理装置以外の分散情報管理装置の情報保管部に対して副分散パラメータの供給要求を発する要求生成部と、
当該供給要求に応じて供給された副分散パラメータを復号して主分散パラメータを復元するパラメータ再構成部と、
当該復元された主分散パラメータを分散符号化することにより当該一部の分散情報管理装置からの取得に失敗した再分散パラメータを復元するパラメータ分散符号化部と、
を含むパラメータ復元部をさらに有することを特徴とする分散情報管理システム。
【請求項１０】
請求項９記載の分散情報管理システムであって、前記複数の副分散パラメータは、前記主分散パラメータを複数のセグメントに分割し、前記セグメントの値を係数として有する生成多項式を用いて生成されたものであることを特徴とする分散情報管理システム。
【請求項１１】
請求項９または１０記載の分散情報管理システムであって、前記パラメータ復元部は、前記供給要求に応じて供給された副分散パラメータの正当性を当該副分散パラメータに付加された検証情報を用いて検証することを特徴とする分散情報管理システム。
【請求項１２】
請求項７から１１のうちのいずれか１項に記載の分散情報管理システムであって、前記ｍ番目の分散情報管理装置は、前記新主分散パラメータを分散符号化することにより複数の新副分散パラメータを生成し、前記新副分散パラメータのうちのｊ番目の新副分散パラメータを前記分散情報管理システムに属するｊ番目の分散情報管理装置（ｊは、ｍを除く１〜ｎのうちの任意整数）の情報保管部に供給する第２パラメータ分散部をさらに有し、
前記ｊ番目の分散情報管理装置の情報保管部に保管される副分散パラメータは、前記第２パラメータ分散部から供給された新副分散パラメータで置換されることにより更新されることを特徴とする分散情報管理システム。
【請求項１３】
請求項７から１２のうちのいずれか１項に記載の分散情報管理システムであって、前記第１パラメータ分散部は、前記再分散パラメータの正当性を検証するための検証情報を生成し前記再分散パラメータに付加することを特徴とする分散情報管理システム。
【請求項１４】
請求項７から１３のうちのいずれか１項に記載の分散情報管理システムであって、前記パラメータ生成部は、前記他の分散情報管理装置から供給された再分散パラメータの正当性を当該再分散パラメータに付加された検証情報を用いて検証することを特徴とする分散情報管理システム。
【請求項１５】
請求項６から１４のうちのいずれか１項に記載の分散情報管理システムであって、前記情報保管部に保管される主分散パラメータは、前記主分散情報を暗号鍵として用いて暗号化されていることを特徴とする分散情報管理システム。
【請求項１６】
請求項１から１５のうちのいずれか１項に記載の分散情報管理システムであって、前記主分散情報分散部は、前記情報保管部に保管される主分散パラメータは暗号化されていることを特徴とする分散情報管理システム。
【請求項１７】
暗号鍵を用いて秘密情報を暗号化して暗号化秘密情報を生成し、当該暗号化秘密情報を分散符号化することにより生成された複数の暗号化主分散情報を管理するとともに、前記暗号鍵を分散符号化して生成された複数の主鍵分散情報を管理するｎ個の分散情報管理装置からなる分散情報管理システムであって、
前記ｎ個の分散情報管理装置のうちｍ番目の分散情報管理装置（ｍは１〜ｎのうちの任意整数）は、
前記主鍵分散情報のうちのｍ番目の主鍵分散情報を保管する情報保管部と、
前記ｍ番目の主鍵分散情報を分散符号化することにより複数の再鍵分散情報を生成し前記再鍵分散情報を前記分散情報管理システムに属する他の全ての分散情報管理装置に供給する主分散情報分散部と、
前記他の全ての分散情報管理装置から供給された再鍵分散情報に基づいて新主鍵分散情報を生成する分散情報生成部と、
を有し、
前記情報保管部に保管される主鍵分散情報は、前記新主鍵分散情報で置換されることにより更新されることを特徴とする分散情報管理システム。
【請求項１８】
請求項１７記載の分散情報管理システムであって、
前記情報保管部は、前記各主鍵分散情報を分散符号化して生成された副鍵分散情報のうちのｍ番目の副鍵分散情報の集合を保管するとともに、前記分散情報管理システムに属する他の分散情報管理装置からの供給要求に応じて前記ｍ番目の副鍵分散情報の集合のうち当該他の分散情報管理装置に対応する副鍵分散情報を供給する機能を有し、
前記ｍ番目の分散情報管理装置は、
前記分散情報管理装置のうちの一部の分散情報管理装置から前記再鍵分散情報を取得することに失敗したとき、当該一部の分散情報管理装置以外の分散情報管理装置の情報保管部に対して副鍵分散情報の供給要求を発する要求生成部と、
当該供給要求に応じて供給された副鍵分散情報を復号して主鍵分散情報を復元する情報再構成部と、
当該復元された主鍵分散情報を分散符号化することにより当該一部の分散情報管理装置からの取得に失敗した再鍵分散情報を生成し、当該生成された再鍵分散情報を前記分散情報生成部に供給する分散符号化部と、
を含む情報復元部をさらに有することを特徴とする分散情報管理システム。
【請求項１９】
請求項１７または１８記載の分散情報管理システムであって、前記主分散情報分散部は、独立変数に乗ずるべき係数と前記主分散情報を含む定数項とを有する生成多項式を用いて前記再鍵分散情報を生成し、前記情報保管部は、前記生成多項式の係数を主分散パラメータとして保管することを特徴とする分散情報管理システム。
【請求項２０】
請求項１９記載の分散情報管理システムであって、
前記ｍ番目の分散情報管理装置は、
前記情報保管部に保管される主分散パラメータを分散符号化することにより複数の再分散パラメータを生成し前記再分散パラメータを前記分散情報管理システムに属する他の分散情報管理装置に供給する第１パラメータ分散部と、
前記他の分散情報管理装置から供給された再分散パラメータに基づいて新主分散パラメータを生成するパラメータ生成部と、
を有し、
前記情報保管部に保管される主分散パラメータは、前記新主分散パラメータで置換されることにより更新されることを特徴とする分散情報管理システム。
【請求項２１】
請求項２０記載の分散情報管理システムであって、前記第１パラメータ分散部は、前記主分散パラメータを複数のセグメントに分割し、前記セグメントの値を係数として有する生成多項式を用いて前記再分散パラメータを生成することを特徴とする分散情報管理システム。
【請求項２２】
請求項２０または２１記載の分散情報管理システムであって、
前記情報保管部は、前記各主分散パラメータを分散符号化して生成された複数の副分散パラメータのうちのｍ番目の副分散パラメータの集合を保管するとともに、前記分散情報管理システムに属する他の分散情報管理装置からの供給要求に応答して前記ｍ番目の副分散パラメータの集合のうち当該他の分散情報管理装置に対応する副分散パラメータを供給する機能を有し、
前記ｍ番目の分散情報管理装置は、
前記他の分散情報管理装置のうちの一部の分散情報管理装置から前記再分散パラメータを取得することに失敗したとき、当該一部の分散情報管理装置以外の分散情報管理装置の情報保管部に対して副分散パラメータの供給要求を発する要求生成部と、
当該供給要求に応じて供給された副分散パラメータを復号して主分散パラメータを復元するパラメータ再構成部と、
当該復元された主分散パラメータを分散符号化することにより当該一部の分散情報管理装置からの取得に失敗した再分散パラメータを復元するパラメータ分散符号化部と、
を含むパラメータ復元部をさらに有することを特徴とする分散情報管理システム。
【請求項２３】
請求項２２記載の分散情報管理システムであって、前記複数の副分散パラメータは、前記主分散パラメータを複数のセグメントに分割し、前記セグメントの値を係数として有する生成多項式を用いて生成されたものであることを特徴とする分散情報管理システム。
【請求項２４】
請求項１８から２３のうちのいずれか１項に記載の分散情報管理システムであって、前記ｍ番目の分散情報管理装置は、前記新主分散パラメータを分散符号化することにより複数の新副分散パラメータを生成し、前記新副分散パラメータのうちのｊ番目の新副分散パラメータを前記分散情報管理システムに属するｊ番目の分散情報管理装置（ｊは、ｍを除く１〜ｎのうちの任意整数）の情報保管部に供給する第２パラメータ分散部をさらに有し、
前記ｊ番目の分散情報管理装置の情報保管部に保管される副分散パラメータは、前記第２パラメータ分散部から供給された新副分散パラメータで置換されることにより更新されることを特徴とする分散情報管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密情報を複数の分散情報に分散符号化する符号化技術に関する。
【背景技術】
【０００２】
秘密分散法（Secret Sharing Scheme）は、秘密情報を複数の分散情報に分散符号化する符号化法であり、分散情報のうち所定個数の分散情報の収集に成功すれば、それら分散情報に基づいて元の秘密情報を復号できるが、一定個数の分散情報を収集できなければ、元の秘密情報を復号できないという特徴を有する。秘密分散法としては、１９７９年にシャミアによって発表されたものが有名である。例えば、「Adi Shamir, "How to share a secret,”Communications of the ACM 22, pp. 612-613, 1979.）」（以下、非特許文献１と称す）を参照されたい。シャミアの秘密分散法では、秘密情報を含む定数項を有する生成多項式を用いることで、元の秘密情報を復元するために必要な複数の分散情報を生成することができる。たとえば、秘密情報を含む定数項ａ（０）を有する次の生成多項式ｇ（ｘ）を使用することができる。【０００３】
【数１】
2009020078.tif 000003
【０００４】
ここで、独立変数ｘ、係数ａ（ｋ−１），…，ａ（１）および定数項ａ（０）は整数であり、ｇ（ｘ）の関数値は、奇素数ｑを法とした剰余値として算出される。ｉ番目の分散情報Ｓｈ（ｉ）は、次式の通り、ｇ（ｘ）の関数値として与えられる。【０００５】
【数２】
2009020078.tif 000004
【０００６】
ここで、ｍｉは、ｉ番目の分散情報Ｓｈ（ｉ）に対応する値である。生成多項式ｇ（ｘ）を用いて分散符号化を実行するには、秘密情報を含む定数項ａ（０）と係数ａ（ｋ−１），…，ａ（１）とを予め決定しておく必要がある。逆に、定数項ａ（０）を含む係数ａ（ｋ−１），…，ａ（０）を一意に求めるには、互いに異なるｋ個の点（ｍ０，Ｓｈ（ｍ０）），（ｍ１，Ｓｈ（ｍ１）），…，（ｍｋ−１，Ｓｈ（ｍｋ−１））が必要である。すなわち、ｋ個の分散情報Ｓｈ（ｍ０），…，Ｓｈ（ｍｋ−１）の収集に成功すれば、以下の連立方程式を解くことにより定数項ａ（０）を求めることが可能である。【０００７】
【数３】
2009020078.tif 000005
【０００８】
ｋ−１個以下の分散情報が盗まれても、上記連立方程式を解いて定数項ａ（０）と係数ａ（ｋ−１）〜ａ（１）とを一意に求めることができないため、秘密情報は漏洩しない。連立方程式を解く代わりに公知のラグランジュ補間法を用いて定数項ａ（０）を算出してもよい。ラグランジュ補間法によれば、互いに異なるｋ個の点（ｍ０，Ｓｈ（ｍ０）），（ｍ１，Ｓｈ（ｍ１）），…，（ｍｋ−１，Ｓｈ（ｍｋ−１））から次の補間方程式Ｌ（ｘ）を構成できる。【０００９】
【数４】
2009020078.tif 000006
【００１０】
定数項ａ（０）は、補間方程式Ｌ（ｘ）を用いて下記の式により算出される。【００１１】
【数５】
2009020078.tif 000007
【００１２】
上記ｋの値（以下「閾値」と呼ぶ。）は、分散情報を生成する前に予め定めておくことができる。閾値が大きいほど不正者に対する安全性は向上するが、分散情報から秘密情報を復元するときに多数の分散情報が必要となる。逆に閾値を小さくすると少ない分散情報から秘密情報を復元できるため、秘密情報の復元が容易になるという利点があるが、安全性が低下する。このように閾値の大小には一長一短の関係があるため、安全性や利便性を考慮して閾値を設定することが望ましい。【００１３】
複数の分散情報は、それぞれ、複数の管理装置に分配されて管理されるが、分散情報が管理装置に供給される伝送路において分散情報の改竄や破壊が起こりうるので、各管理装置は、自己が管理する分散情報の正当性を検証できることが望ましい。単純にシャミアの秘密分散法を適用しただけでは、分散情報の正当性を確認する手段が存在しない。この点については、分散情報の正当性の検証が可能な秘密分散法としてＶＳＳ法（Verifiable Secret Sharing scheme：検証可能秘密分散法）が知られており、既に色々な種類のＶＳＳ法が提案されている。ＶＳＳ法を開示する先行技術文献としては、たとえば、「Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl, "Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems," Proc. 9th ACM Conference on Computer and Communications Security, pp. 88-97, 2002.」（以下、非特許文献２と称す）が挙げられる。ＶＳＳ法によれば、秘密情報から分散情報を生成する際に分散情報の正当性を検証するための検証情報が生成される。管理装置は、分散情報を受け取ったときに検証情報を使用して当該分散情報の正当性を検証することができる。また、秘密情報を復元する復号装置は、複数の管理装置から分散情報と検証情報とを収集し、これら分散情報の正当性を検証することが可能である。【００１４】
分散情報は元の秘密情報と同様に秘密裏に保管される必要があるが、分散情報が未来永劫不正者に漏洩せずに安全に保管され続けるという保証はない。不正者が時間をかければ元の秘密情報の復元に必要なｋ個以上の分散情報を取得できるおそれがある。この点については、秘密情報の復元に必要な分散情報を定期的に更新する秘密分散法であるＰＳＳ法（プロアクティブ型秘密分散法：Proactive Secret Sharing scheme）が知られている。ＰＳＳ法によれば、不正者が秘密情報の復元に必要なｋ個の分散情報を取得する前に分散情報を更新するため、仮に分散情報の更新前に分散情報の一部が不正者に漏洩したとしても、秘密情報の更新後は、当該漏洩した分散情報の一部を用いて秘密情報を復元することが不可能になる。すなわち、更新前の古い分散情報は無効化される。分散情報を更新するとき、古い分散情報と新しい分散情報とが混在することを防ぐために、全ての管理装置は連携して分散情報を同時期に更新する必要がある。非特許文献２に記載されているＰＳＳ法は、分散情報の更新時にビザンチン合意（Byzantine Agreement）と呼ばれるプロトコルを使用する。分散情報管理装置（サーバ：server）は、ビザンチン合意プロトコルに従って、他の分散情報管理装置との間で合意を確立した情報に基づいて新たな分散情報を生成する。しかしながら、ビザンチン合意プロトコルには、最悪の場合に合意が得られず終了しない状態になる可能性があり、このような状態になった場合には分散情報を更新できないという問題がある。また、合意が得られるまでに必要な通信量の平均値を求めることはできても、通信量そのものを正確に予測できないため、当該更新に必要な時間の見積もりが困難であるという問題がある。【００１５】
そこで、ビザンチン合意プロトコルを使用せずに分散情報の更新を可能にするＰＳＳ法が、「Bartosz Przydatek and Reto Strobl, "Asynchronous Proactive Cryptosystems Without Agreement (extended abstract)," Advances in Cryptology - ASIACRYPT '04, Lecture Notes in Computer Science, Springer Verlag, vol. 3329, pp. 152-169, 2004.」（以下、非特許文献３と称す）に開示されている。非特許文献３に記載されているＰＳＳ法は、ビザンチン合意プロトコルを使用しない。よって、非特許文献２に記載された秘密分散法よりも更新に必要な通信量が少なくなることが期待でき、また通信量の上限を正確に予測することができるので更新に必要な時間の最大値を容易に決めることができる。ところが、非特許文献３に記載されているＰＳＳ法は、分散情報の正当性を検証する手段をもたないため、上述のＶＳＳ法ではない。【００１６】
なお、秘密分散法に関する先行技術を記載した特許文献としては、特開２００３−３４８０６５号公報（以下、特許文献１と称す）および特開２００５−２５０８６６号公報（以下、特許文献２と称す）が挙げられる。
【発明の開示】
【００１７】
上記の通り、非特許文献２に開示されている秘密分散法には、分散情報の検証が可能ではあるが、ビザンチン合意プロトコルに起因して分散情報の更新に時間を要する可能性があるという問題があり、非特許文献３に開示されている秘密分散法には、更新時間の最大値を正確に予測できるが、分散情報の検証ができないという問題がある。それゆえ、非特許文献２に開示されている秘密分散法と非特許文献３に開示されている秘密分散法とは一長一短の関係にある。
【００１８】
本発明の１つの目的は、ビザンチン合意プロトコルを使用せずに分散情報の更新を可能にし、従来技術と比べてより安全かつ実用的な秘密分散を実現し得る分散情報管理システムを提供することである。
【００１９】
本発明の一態様に係る分散情報管理システムは、秘密情報を分散符号化して生成された複数の主分散情報を管理するｎ個の分散情報管理装置からなる分散情報管理システムであって、前記ｎ個の分散情報管理装置のうちｉ番目の分散情報管理装置（ｉは１〜ｎのうちの任意整数）は、前記主分散情報のうちのｉ番目の主分散情報を保管する情報保管部と、前記ｉ番目の主分散情報を分散符号化することにより複数の再分散情報を生成し前記再分散情報を前記分散情報管理システムに属する他の全ての分散情報管理装置に供給する主分散情報分散部と、前記他の全ての分散情報管理装置から供給された再分散情報に基づいて新主分散情報を生成する分散情報生成部と、を有し、前記情報保管部に保管される主分散情報は、前記新主分散情報で置換されることにより更新されることを特徴とするものである。
【００２０】
本発明の他の態様による分散情報管理システムは、暗号鍵を用いて秘密情報を暗号化して暗号化秘密情報を生成し、当該暗号化秘密情報を分散符号化することにより生成された複数の暗号化主分散情報を管理するとともに、前記暗号鍵を分散符号化して生成された複数の主鍵分散情報を管理するｎ個の分散情報管理装置からなる分散情報管理システムであって、前記ｎ個の分散情報管理装置のうちｍ番目の分散情報管理装置（ｍは１〜ｎのうちの任意整数）は、前記主鍵分散情報のうちのｍ番目の主鍵分散情報を保管する情報保管部と、前記ｍ番目の主鍵分散情報を分散符号化することにより複数の再鍵分散情報を生成し前記再鍵分散情報を前記分散情報管理システムに属する他の全ての分散情報管理装置に供給する主分散情報分散部と、前記他の全ての分散情報管理装置から供給された再鍵分散情報に基づいて新主鍵分散情報を生成する分散情報生成部と、を有し、前記情報保管部に保管される主鍵分散情報は、前記新主鍵分散情報で置換されることにより更新されることを特徴とするものである。
【図面の簡単な説明】
【００２１】
【図１】秘密情報管理システムの全体構成を概略的に示すブロック図である。
【図２】秘密情報分散装置の概略構成を示す機能ブロック図である。
【図３】秘密情報分散装置の主秘密分散部の概略構成を示す機能ブロック図である。
【図４】秘密情報分散装置の副秘密分散部の概略構成を示す機能ブロック図である。
【図５】ｍ番目の秘密分散情報のデータ・フォーマットを概略的に示す図である。
【図６】復号装置の概略構成を示す機能ブロック図である。
【図７】図１に示した分散パラメータ分配装置の概略構成を示す機能ブロック図である。
【図８Ａ−８Ｂ】図８Ａは分散パラメータ分配装置のパラメータ検証情報生成部の構成の一例を示す機能ブロック図である。図８Ｂは分散パラメータ分配装置のパラメータ検証情報生成部の構成の一例を示す機能ブロック図である。
【図９】分散パラメータ分配装置の構成の一部を示す機能ブロック図である。
【図１０】分散パラメータセットのデータ・フォーマットを概略的に示す図である。
【図１１】本発明の一実施例に係る分散情報管理システムの概略構成を示す機能ブロック図である。
【図１２】分散情報更新部の概略構成を示す機能ブロック図である。
【図１３】主分散情報分散部の概略構成を示す機能ブロック図である。
【図１４】主分散情報分散部の構成の一部を示す機能ブロック図である。
【図１５】再秘密分散情報のデータ・フォーマットを概略的に示す図である。
【図１６】分散情報生成部の概略構成を示す機能ブロック図である。
【図１７】情報復元部の概略構成を示す機能ブロック図である。
【図１８】本発明の一実施例に係る分散情報管理システムによる分散情報の更新のための動作シーケンスを概略的に示す図である。
【図１９】分散パラメータ更新部の概略構成を示す機能ブロック図である。
【図２０】パラメータ分散部の概略構成を示す機能ブロック図である。
【図２１】主再分散パラメータ情報のデータ・フォーマットを概略的に示す図である。
【図２２】パラメータ生成部の概略構成を示す機能ブロック図である。
【図２３】パラメータ構成部の概略構成を示す機能ブロック図である。
【図２４】パラメータ復元部の概略構成を示す機能ブロック図である。
【図２５】パラメータ分散部の概略構成を示す機能ブロック図である。
【図２６】本発明の一実施例に係る分散情報管理システムによる分散パラメータの更新のための動作シーケンスを概略的に示す図である。
【図２７】本発明の一実施例に係る分散情報管理システムによる分散パラメータの更新のための動作シーケンスを概略的に示す図である。
【図２８】第１の変形例に係る分散情報管理システムの概略構成を示す機能ブロック図である。
【図２９】第１の変形例の分散パラメータ分配装置の概略構成を示す機能ブロック図である。
【図３０】第１の変形例の分散パラメータ分配装置の構成の一部を示す機能ブロック図である。
【図３１】第１の変形例に係る暗号化分散パラメータセットのデータ・フォーマットを概略的に示す図である。
【図３２】第１の変形例の分散情報更新部の概略構成を示す機能ブロック図である。
【図３３】第１の変形例の情報復元部の概略構成を示す機能ブロック図である。
【図３４】第１の変形例の分散パラメータ更新部の概略構成を示す機能ブロック図である。
【図３５】第１の変形例のパラメータ復元部の概略構成を示す機能ブロック図である。
【図３６】第１の変形例のパラメータ分散部の概略構成を示す機能ブロック図である。
【図３７Ａ−３７Ｂ】図３７Ａは第２の変形例を説明するための図である。図３７Ｂは第２の変形例を説明するための図である。
【図３８】第３の変形例の主分散情報分散部の概略構成を示す機能ブロック図である。
【図３９】第３の変形例の主分散情報分散部の構成の一部を示す機能ブロック図である。
【図４０】第３の変形例のパラメータ生成部の概略構成を示す機能ブロック図である。
【図４１】第２実施例の秘密情報管理システムの概略構成を示す機能ブロック図である。
【図４２】第２実施例の秘密情報分散装置の概略構成を示す機能ブロック図である。
【図４３】第２実施例の復号装置の概略構成を示す機能ブロック図である。
【図４４】第２実施例に係る秘密分散情報のデータ・フォーマットを概略的に示す図である。
【図４５】第２実施例の鍵分散情報更新部の概略構成を示す機能ブロック図である。
【図４６】第２実施例に係る再鍵秘密分散情報のデータ・フォーマットを概略的に示す図である。
【図４７Ａ−４７Ｂ】図４７Ａは第２実施例の変形例を説明するための図である。図４７Ｂは第２実施例の変形例を説明するための図である。
【図４８】第２実施例の他の変形例を説明するための図である。
【発明を実施するための形態】
【００２２】
以下、本発明の種々の実施例について説明する。
【００２３】
＜基本構成＞
図１は、秘密情報管理システム１の全体構成を概略的に示す機能ブロック図である。この秘密情報管理システム１は、秘密情報分散装置１０、分散パラメータ分配装置１１、分散情報管理装置１２１，…，１２ｎ（ｎは２以上の整数）および復号装置１３を有する。本実施例では、これら機能ブロック１０，１１，１２１，…，１２ｎ，１３は、ＬＡＮ（Local Area Network），ＷＡＮ（Wide Area Network）あるいは専用回線などの通信伝送路を介して相互に通信可能な状態で接続されているが、これに限定されるものではない。機能ブロック１０，１１，１２１，…，１２ｎ，１３の全部または一部が単一の装置に組み込まれ且つ内部バスなどのデータ伝送路を介して相互に接続されていてもよい。また、これら機能ブロック１０，１１，１２１，…，１２ｎ，１３の一部は、ハードウェアにより実現されてもよいし、あるいは、ＣＰＵなどのプロセッサに実行されるソフトウェア・プログラムにより実現されてもよい。
【００２４】
図１に示されるように、秘密情報分散装置１０は、秘密情報Ｓｔに分散符号化を施して複数の秘密分散情報Ｋ（１），…，Ｋ（ｎ）を生成し、これら秘密分散情報Ｋ（１），…，Ｋ（ｎ）をそれぞれ対応する分散情報管理装置１２１，…，１２ｎに供給する。分散情報管理装置１２１，…，１２ｎはそれぞれ供給された秘密分散情報Ｋ（１），…，Ｋ（ｎ）を情報保管部１２１１，…，１２１ｎに保管し、自己が保管する秘密分散情報Ｋ（１）〜Ｋ（ｎ）を定期的に更新する機能を有する。また、分散情報管理装置１２１，…，１２ｎは、復号装置１３からの要求に応じて、秘密分散情報Ｋ（１）〜Ｋ（ｎ）を復号装置１３に供給する。復号装置１３は、秘密分散情報Ｋ（１）〜Ｋ（ｎ）のうちｋ個以上の秘密分散情報の収集に成功すれば、これら秘密分散情報に基づいて元の秘密情報Ｓｔを復元する機能を有する。
【００２５】
分散パラメータ分配装置１１は、後述する秘密分散情報の更新に使用されるべき分散パラメータφ（１），…，φ（ｎ）をそれぞれ対応する分散情報管理装置１２１，…，１２ｎに供給する。分散情報管理装置１２１，…，１２ｎはそれぞれ供給された分散パラメータφ（１），…，φ（ｎ）を情報保管部１２１１，…，１２１ｎに保管し、自己が保管する分散パラメータφ（１），…，φ（ｎ）を定期的に更新する機能を有する。この分散パラメータ分配装置１１は、秘密情報分散装置１０とは独立した構成を有しているが、これに限定されず、分散パラメータ分配装置１１が秘密情報分散装置１０に組み込まれていてもよい。
【００２６】
なお、秘密情報分散装置１０、分散パラメータ分配装置１１および復号装置１３は、いずれも分散情報管理システム２とは独立した構成を有しているが、これに限定されるものではない。図１に示した構成の代わりに、秘密情報分散装置１０、分散パラメータ分配装置１１あるいは復号装置１３が分散情報管理装置１２１〜１２ｎのいずれか１つに組み込まれていてもよい。
【００２７】
図２は、秘密情報分散装置１０の概略構成を示す機能ブロック図である。秘密情報分散装置１０は、主秘密分散部１０１、副秘密分散部１０２および情報合成部１０３からなる。主秘密分散部１０１は、分散パラメータφ（０）を用いて秘密情報Ｓｔに分散符号化を施して複数の主秘密分散情報Ｋｍ（１），…，Ｋｍ（ｎ）を生成する機能を有する。これら主秘密分散情報Ｋｍ（１），…，Ｋｍ（ｎ）はそれぞれ対応する分散情報管理装置１２１，…，１２ｎに供給される。
【００２８】
図３に示されるように主秘密分散部１０１は、主分散符号化部１０４、検証情報生成部１０５および情報合成部１０６を有している。主分散符号化部１０４は、分散パラメータφ（０）を用いて秘密情報Ｓｔを分散符号化して複数の主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）を生成する。秘密情報Ｓｔは、分散符号化に使用される生成多項式の定数項に含められ、分散パラメータφ（０）は当該生成多項式を定める係数群からなる。また、検証情報生成部１０５は、分散パラメータφ（０）を用いて秘密情報Ｓｔから複数の検証情報Ｖｍ（１）〜Ｖｍ（ｎ）を生成する機能を有する。これら検証情報Ｖｍ（１）〜Ｖｍ（ｎ）は、それぞれ、主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）の正当性を検証するための情報である。これら検証情報Ｖｍ（１）〜Ｖｍ（ｎ）を用いることでＶＳＳ法（Verifiable Secret Sharing scheme：検証可能秘密分散法）が実現可能になる。
【００２９】
情報合成部１０６は、主分散符号化部１０４から供給された主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）と、検証情報生成部１０５から供給された検証情報Ｖｍ（１）〜Ｖｍ（ｎ）とを合成して主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）を生成する。ｉ番目の主秘密分散情報Ｋｍ（ｉ）（ｉは１〜ｎのうちの任意整数）は、ｉ番目の主分散情報Ｓｍ（ｉ）とこれに付加されるｉ番目の検証情報Ｖｍ（ｉ）とで構成される。
【００３０】
図２に示されるように副秘密分散部１０２は、主秘密分散部１０１から供給された主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）の各々に分散符号化を施して複数の副秘密分散情報Ｋｂ（１，１）〜Ｋｂ（ｎ，ｎ）を生成し、当該生成された副秘密分散情報Ｋｂ（１，１）〜Ｋｂ（ｎ，ｎ）を情報合成部１０３に供給する。図４は、副秘密分散部１０２の概略構成を示す機能ブロック図である。図４の副秘密分散部１０２は、副分散符号化部１０７、検証情報生成部１０８および情報合成部１０９を有している。副分散符号化部１０７は、分散パラメータφ（０）を用いてｊ番目の主分散情報Ｓｍ（ｊ）を分散符号化して複数の副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）を生成し、当該生成された副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）を情報合成部１０９に供給する。一方、検証情報生成部１０８は、分散パラメータφ（０）を用いて主分散情報Ｓｍ（ｊ）から複数の検証情報Ｖｂ（ｊ，１）〜Ｖｂ（ｊ，ｎ）を生成し、当該検証情報Ｖｂ（ｊ，１）〜Ｖｂ（ｊ，ｎ）を情報合成部１０９に供給する。そして、情報合成部１０９は、副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）をそれぞれ対応する検証情報Ｖｂ（ｊ，１）〜Ｖｂ（ｊ，ｎ）に付加して副秘密分散情報Ｋｂ（ｊ，１）〜Ｋｂ（ｊ，ｎ）を生成する。
【００３１】
前述の通り、本明細書においては、主分散情報Ｓｍ（ｊ）と、当該主分散情報Ｓｍ（ｊ）から生成される副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）という２種類の分散情報が使用される。主分散情報Ｓｍ（ｊ）は、秘密情報Ｓｔを直接的に分散符号化して生成される、秘密情報Ｓｔに対するバックアップ情報である。一方、副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）は、秘密情報Ｓｔを間接的に分散符号化して生成される、主分散情報Ｓｍ（ｊ）に対するバックアップ情報といえる。
【００３２】
図２を参照すると、情報合成部１０３は、主秘密分散部１０１から供給された主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）と、副秘密分散部１０２から供給された副秘密分散情報Ｋｂ（１，１）〜Ｋｂ（ｎ，ｎ）とを合成してｎ個の秘密分散情報Ｋ（１）〜Ｋ（ｎ）を生成する。図５は、ｍ番目の分散情報管理装置１２ｍに供給されるべきｍ番目の秘密分散情報Ｋ（ｍ）のデータ・フォーマットを示す図である。図５に示される通り、主秘密分散情報Ｋｍ（ｍ）は、ｍ番目の主分散情報Ｓｍ（ｍ）とこれに付加された検証情報Ｖｍ（ｍ）とからなる主秘密分散情報Ｋｍ（ｍ）を含む。また、主秘密分散情報Ｋｍ（ｍ）は、主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）の各々に分散符号化を施して生成された副秘密分散情報Ｋｂ（１，１）〜Ｋｂ（ｎ，ｎ）のうち、ｍ番目の副秘密分散情報の集合Ｋｂ（１，ｍ）〜Ｋｂ（ｎ，ｍ）を含む。
【００３３】
図６は、復号装置１３の概略構成を示す機能ブロック図である。図６に示されるように復号装置１３は、分散情報検証部１３１および情報再構成部１３２を有する。分散情報検証部１３１は、分散情報管理装置１２１〜１２ｎから供給された秘密分散情報Ｋ（１）〜Ｋ（ｎ）の正当性を検証する機能を有する。より具体的には、分散情報検証部１３１は、秘密分散情報Ｋ（１）〜Ｋ（ｎ）のうちの主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）の正当性を、当該主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）にそれぞれ付加された検証情報Ｖｍ（１）〜Ｖｍ（ｎ）を用いて検証する。正当性を有するものと検証された主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）は情報再構成部１３２に供給されるが、正当性を有しないものと検証された主分散情報は情報再構成部１３２に供給されない。情報再構成部１３２は、分散情報検証部１３１から一定数（閾値）以上の主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）を取得することに成功すれば、これら主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）から元の秘密情報Ｓｔを復元することができる。なお、本実施例では、分散情報管理装置１２１〜１２ｎから秘密分散情報Ｋ（１）〜Ｋ（ｎ）が供給されるが、秘密情報Ｓｔの復元のために使用される情報は主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）のみであるから、分散情報管理装置１２１〜１２ｎは、主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）のみを復号装置１３に供給してもよい。
【００３４】
次に、上記した分散パラメータを用いた分散符号化について説明する。この分散符号化は、ＶＳＳ法（Verifiable Secret Sharing scheme：検証可能秘密分散法）により実現することができる。ＶＳＳ法の具体例について以下に説明するが、本発明に係るＶＳＳ法はこれらに限定されるものではない点に留意すべきである。分散符号化アルゴリズムの第１の具体例は以下の通りである。先ず、次の（ｋ−１）次の生成多項式ｇ（ｘ）が与えられる。
【００３５】
【数６】
2009020078.tif 000008
【００３６】
ここで、独立変数ｘ、係数ａ（ｋ−１），…，ａ（１）および定数項ａ（０）は整数であり、ｇ（ｘ）の関数値は、奇素数ｑを法とした剰余値として算出される。分散符号化されるべき秘密情報は、定数項ａ（０）に含められる。また、生成多項式ｇ（ｘ）の係数ａ（ｋ−１），…，ａ（１）は分散パラメータφ（０）を構成する。ｉ番目の分散情報Ｓｈ（ｉ）は、次式の通り、ｇ（ｘ）の関数値として与えられる。
【００３７】
【数７】
2009020078.tif 000009
【００３８】
ここで、ｍｉは、ｉ番目の分散情報管理装置１２ｉに割り当てられた一意の整数値とすることができる。この分散情報Ｓｈ（ｉ）に付加されるべき検証情報Ｖ（ｉ）は、生成多項式ｇ（ｘ）の係数を指数として用いるベキ乗剰余値の集合とすることができる。具体的は、検証情報Ｖ（ｉ）は次式で与えられる。
【００３９】
【数８】
2009020078.tif 000010
【００４０】
ここで、ｇは、ｐ＝βｑ＋１（βは自然数）を満たす素数ｐと整数ｑとの組み合わせを定めたときの位数ｑを持つ素体Ｚｐの元である。この検証情報Ｖ（ｉ）は、離散対数問題を安全性の根拠としている。
【００４１】
分散情報Ｓｈ（ｉ）の正当性の有無は、検証情報Ｖ（ｉ）を用いて次の検証式が成立するか否かで判別することが可能である。
【００４２】
【数９】
2009020078.tif 000011
【００４３】
また、上記したラグランジュ補間法により、次式を用いて秘密情報を含む定数項ａ（０）を復元すなわち再構成することができる。
【００４４】
【数１０】
2009020078.tif 000012
【００４５】
次に、分散符号化アルゴリズムの第２の具体例について説明する。上記第１の具体例は、離散対数問題を安全性の根拠とするものであるが、以下に説明する第２の具体例は、離散対数問題に依存せずに安全性の向上を図るものである。第２の具体例では、２変数ｘ，ｙを持つ以下の生成多項式ｇ（ｘ，ｙ）が与えられる。
【００４６】
【数１１】
2009020078.tif 000013
【００４７】
生成多項式ｇ（ｘ，ｙ）の係数ａ（ｊ，ｒ）は整数であり、ｇ（ｘ，ｙ）の関数値は、奇素数ｑを法とした剰余値として算出される。分散符号化されるべき秘密情報は、生成多項式ｇ（ｘ，ｙ）の定数項ａ（０，０）に含められる。また、生成多項式ｇ（ｘ，ｙ）の係数の集合｛ａ（ｊ，ｒ）｝は分散パラメータφ（０）を構成する。ｉ番目の分散情報Ｓｈ（ｉ）は、変数ｘを持つ次の関数を定める情報として与えられる。
【００４８】
【数１２】
2009020078.tif 000014
【００４９】
第２の具体例では、分散情報Ｓｈ（ｉ）に付加すべき検証情報は生成されない。よって、図１の秘密情報分散装置１０は、ｉ番目の分散情報Ｓｈ（ｉ）を主分散情報Ｓｍ（ｉ）としてｉ番目の分散情報管理装置１２ｉに供給するが、主分散情報Ｓｍ（ｉ）に対応する検証情報Ｖｍ（ｉ）を分散情報管理装置１２ｉに供給する必要がない。分散情報管理装置１２１〜１２ｎは、共同して、分散情報Ｓｈ（ｉ）〜Ｓｈ（ｎ）で定められる多項式関数を用いて分散情報を検証する。具体的には、ｉ番目の分散情報管理装置１２ｉとｊ番目の分散情報管理装置１２ｊとの間で分散情報が検証される場合、ｊ番目の分散情報管理装置１２ｊは、自己が保有する多項式関数を用いて次式の関数値Ｐｊを算出し、当該関数値Ｐｊをｉ番目の分散情報管理装置１２ｉに供給する。
【００５０】
【数１３】
2009020078.tif 000015
【００５１】
ここで、ωは、素体Ｚｑの元である。他方、ｉ番目の分散情報管理装置１２ｉは、自己が保有する多項式関数を用いて次式の関数値Ｐｉを算出する。
【００５２】
【数１４】
2009020078.tif 000016
【００５３】
次に、分散情報管理装置１２ｉは、分散情報管理装置１２ｊから供給された関数値Ｐｊを当該関数値Ｐｉと比較して、関数値Ｐｊが関数値Ｐｉと一致しなければ、分散情報Ｓｈ（ｉ）は正当性を有しないと判定する。分散情報管理装置１２ｉは、一定数以上の分散情報管理装置から供給された関数値のいずれについても分散情報Ｓｈ（ｉ）が正当性を有しないと判定しなかった場合に、分散情報Ｓｈ（ｉ）が正当性を有すると判定することができる。かかる場合、分散情報管理装置１２ｉは、次式で与えられる関数値α（ｉ）を最終的な分散情報として保管する。
【００５４】
【数１５】
2009020078.tif 000017
【００５５】
復号装置１３は、分散情報管理装置１２１〜１２ｎからｋ個の分散情報α（１）〜α（ｋ）を取得することに成功した場合、以下の連立方程式を解くことにより、元の定数項ａ（０，０）を算出することができる。
【００５６】
【数１６】
2009020078.tif 000018
【００５７】
次に、分散符号化アルゴリズムの第３の具体例について説明する。第３の具体例では、２変数ｘ，ｙを持つ次の生成多項式ｆ（ｘ，ｙ）、ｇ（ｘ，ｙ）が与えられる。
【００５８】
【数１７】
2009020078.tif 000019
【００５９】
ここで、生成多項式ｆ（ｘ，ｙ），ｇ（ｘ，ｙ）の係数ａ（ｊ，ｒ），ｂ（ｓ，ｔ）は整数であり、ｆ（ｘ，ｙ），ｇ（ｘ，ｙ）の関数値は、奇素数ｑを法とした剰余値として算出される。分散符号化されるべき秘密情報は、生成多項式ｆ（ｘ，ｙ）の定数項ａ（０，０）あるいは生成多項式ｇ（ｘ，ｙ）の定数項ｂ（０，０）に含めることができる。また、生成多項式ｆ（ｘ，ｙ）の係数の集合｛ａ（ｊ，ｒ）｝と生成多項式ｇ（ｘ，ｙ）の係数の集合｛ｂ（ｓ，ｔ）｝とは分散パラメータφ（０）を構成する。
【００６０】
先ず、秘密情報分散装置１０（図１）は、分散情報管理装置１２１〜１２ｎにそれぞれ供給すべき送信メッセージを生成する。ｉ番目の分散情報管理装置１２ｉへの送信メッセージは、次の４つの多項式関数Ｓｈｉ１（ｙ）、Ｓｈｉ２（ｘ）、Ｓｈｉ３（ｙ）、Ｓｈｉ４（ｘ）を定める係数群｛Ａｉ１（ｒ）｝，｛Ａｉ２（ｊ）｝，｛Ａｉ３（ｔ）｝，｛Ａｉ４（ｓ）｝として与えられる。
【００６１】
【数１８】
2009020078.tif 000020
【００６２】
また、秘密情報分散装置１０は、送信メッセージの正当性を検証するための検証情報（以下、「コミットメント情報」と呼ぶ。）を生成する。コミットメント情報｛Ｃ（ｊ，ｒ）｝（ｊ＝０〜ｋ−１；ｒ＝０〜ｋ−１）は、次式（Ａ）の通りである。
【００６３】
【数１９】
2009020078.tif 000021
【００６４】
そして、秘密情報分散装置１０は、送信メッセージおよび検証情報を分散情報管理装置１２１〜１２ｎに供給する。分散情報管理装置１２１〜１２ｎの各々は、秘密情報分散装置１０から供給された送信メッセージの正当性を、当該送信メッセージに付加された検証情報を用いて検証することができる。具体的には、ｉ番目の分散情報管理装置１２ｉは、全ての値ｒについて次の第１式が成立し且つ全ての値ｊについて次の第２式が成立すれば、送信メッセージが正当性を有する旨検証する。
【００６５】
【数２０】
2009020078.tif 000022
【００６６】
次に、分散情報管理装置１２１〜１２ｎは、共同して、検証済みの送信メッセージで定められる多項式関数を用いて分散情報を検証する。具体的には、分散情報管理装置１２１〜１２ｎは、相互にエコーメッセージを供給し合う。ｉ番目の分散情報管理装置１２ｉは、ｖ番目の分散情報管理装置１２ｖに対しては、次式で算出される関数値Ｓｈｉ１（ｍｖ），Ｓｈｉ２（ｍｖ），Ｓｈｉ３（ｍｖ），Ｓｈｉ４（ｍｖ）をエコーメッセージとして供給する。
【００６７】
【数２１】
2009020078.tif 000023
【００６８】
ｖ番目の分散情報管理装置１２ｖは、ｉ番目の分散情報管理装置１２ｉからエコーメッセージを受信すると、当該エコーメッセージの正当性をコミットメント情報｛Ｃ（ｊ，ｒ）｝を用いて検証する。具体的には、次式が成立するか否かでエコーメッセージの正当性の有無を検証することができる。
【００６９】
【数２２】
2009020078.tif 000024
【００７０】
ｖ番目の分散情報管理装置１２ｖは、他の分散情報管理装置１２１〜１２ｎから受信されたエコーメッセージの正当性をも検証する。その結果、一定数以上の正当性を有するエコーメッセージの取得に成功した場合、ｖ番目の分散情報管理装置１２ｖは、これらエコーメッセージに基づいて、秘密情報分散装置１０で生成された元の多項式Ｓｈｖ２（ｘ）、Ｓｈｖ１（ｙ）、Ｓｈｖ４（ｘ）、Ｓｈｖ３（ｙ）を復元すなわち再構成する。
【００７１】
【数２３】
2009020078.tif 000025
【００７２】
これら多項式は、たとえば、上記したラグランジュ補間法による補間方程式として復元することができる。すなわち、多項式Ｓｈｖ２（ｘ）は、エコーメッセージの関数値の集合｛Ｓｈｊ１（ｍｖ）｝（ｊ＝１〜ｋ）から復元され、多項式Ｓｈｖ１（ｙ）は、エコーメッセージの関数値の集合｛Ｓｈｊ２（ｍｖ）｝（ｊ＝１〜ｋ）から復元され、多項式Ｓｈｖ４（ｘ）は、エコーメッセージの関数値の集合｛Ｓｈｊ３（ｍｖ）｝（ｊ＝１〜ｋ）から復元され、多項式Ｓｈｖ３（ｙ）は、エコーメッセージの関数値の集合｛Ｓｈｊ４（ｍｖ）｝（ｊ＝１〜ｋ）から復元される。
【００７３】
次に、ｖ番目の分散情報管理装置１２ｖは、復元された多項式Ｓｈｖ２（ｘ）、Ｓｈｖ１（ｙ）、Ｓｈｖ４（ｘ）、Ｓｈｖ３（ｙ）を用いてレディメッセージを生成し、当該レディメッセージを他の分散情報管理装置１２１〜１２ｎに供給する。具体的には、ｖ番目の分散情報管理装置１２ｖからｉ番目の分散情報管理装置１２ｉに供給されるレディメッセージは、４つの関数値Ｓｈｖ２（ｍｉ）、Ｓｈｖ１（ｍｉ）、Ｓｈｖ４（ｍｉ）、Ｓｈｖ３（ｍｉ）の組み合わせである。
【００７４】
ｉ番目の分散情報管理装置１２ｉは、ｖ番目の分散情報管理装置１２ｖからレディメッセージを受信すると、当該レディメッセージの正当性をコミットメント情報｛Ｃ（ｊ，ｒ）｝を用いて検証する。具体的には、次式が成立するか否かでレディメッセージの正当性の有無を検証することができる。
【００７５】
【数２４】
2009020078.tif 000026
【００７６】
ｉ番目の分散情報管理装置１２ｉは、他の分散情報管理装置１２１〜１２ｎから受信されたレディメッセージの正当性をも検証する。その結果、一定数以上の正当性を有するエコーメッセージの取得に成功した場合、ｉ番目の分散情報管理装置１２ｉは、自己がエコーメッセージから復元した多項式Ｓｈｉ２（ｘ）、Ｓｈｉ１（ｙ）、Ｓｈｉ４（ｘ）、Ｓｈｉ３（ｙ）のうち、多項式Ｓｈｉ１（ｙ），Ｓｈｉ３（ｙ）の関数値Ｓｈｉ１（０），Ｓｈｉ３（０）の組を分散情報Ｓｈ（ｉ）として保管する。関数値Ｓｈｉ１（０），Ｓｈｉ３（０）は、次式（Ｂ）の通りである。
【００７７】
【数２５】
2009020078.tif 000027
【００７８】
復号装置１３の分散情報検証部１３１（図６）は、分散情報管理装置１２１〜１２ｎから供給された分散情報Ｓｈ（１）〜Ｓｈ（ｎ）の各々をコミットメント情報｛Ｃ（ｊ，ｒ）｝を用いて検証する。具体的には、復号装置１３がｉ番目の分散情報管理装置１２ｉから分散情報Ｓｈ（ｉ）を供給されたときは、次式（Ｃ）が成立するか否かで分散情報Ｓｈ（ｉ）の正当性の有無を検証することができる。
【００７９】
【数２６】
2009020078.tif 000028
【００８０】
復号装置１３の情報再構成部１３２は、分散情報管理装置１２１〜１２ｎから一定数（＝ｋ）以上の分散情報Ｓｈ（１）〜Ｓｈ（ｋ）を取得することに成功した場合、上記したラグランジュ補間法に従って定数項ａ（０，０），ｂ（０，０）を再構成し、これら定数項ａ（０，０），ｂ（０，０）に基づいて秘密情報Ｓｔを復元することができる。
【００８１】
次に、図１に示した分散パラメータ分配装置１１について説明する。図７は、図１に示した分散パラメータ分配装置１１の概略構成を示す機能ブロック図である。図７に示されるように分散パラメータ分配装置１１は、パラメータ生成部１１１、パラメータ分散部１１２、パラメータ検証情報生成部１１３、パラメータ検証情報生成部１１４およびパラメータ合成部１１５を有する。
【００８２】
パラメータ生成部１１１は、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）を生成し、これら主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）を、パラメータ分散部１１２、パラメータ検証情報生成部１１４およびパラメータ合成部１１５に供給する。主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）の各々は、分散情報管理装置１２１〜１２ｎでの分散符号化に使用される生成多項式を定める係数群からなる。
【００８３】
パラメータ検証情報生成部１１４は、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）の正当性を検証するための検証情報ＶＰｍ（１）〜ＶＰｍ（ｎ）を生成する機能を有する。図８（Ａ）は、パラメータ検証情報生成部１１４の概略構成の一例を示す機能ブロック図である。図８（Ａ）に示される通り、情報圧縮部１１４１は、ｉ番目の主分散パラメータＰｍ（ｉ）のビット長を固定ビット長に圧縮して圧縮データを誤り訂正符号化部１１４２に供給する。情報圧縮部１１４１は、たとえば、入力に対して固定ビット長の出力を与える公知のハッシュ関数などの非線形関数を使用するのが好ましい。非線形関数の代わりに変換テーブルを使用してもよい。また、誤り訂正符号化部１１４２は、情報圧縮部１１４１からの圧縮データに基づいて公知の誤り訂正符号を検証情報ＶＰｍ（ｉ）として生成する。ここで、検証情報検証情報ＶＰｍ（ｉ）は誤り訂正符号に限定される必要はなく、伝送路において主分散パラメータＰｍ（ｉ）の改竄や消失を検出可能にするものであれば足りる。
【００８４】
図７のパラメータ分散部１１２は、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）の各々を分散符号化して複数の副分散パラメータＰｂ（１，１）〜Ｐｂ（ｎ，ｎ）を生成する。図９に示されるように、パラメータ分散部１１２は、パラメータ生成部１１１からのｉ番目の主分散パラメータＰｍ（ｉ）を分散符号化して副分散パラメータＰｂ（ｉ，１）〜Ｐｂ（ｉ，ｎ）を生成する。また、パラメータ検証情報生成部１１３は、パラメータ分散部１１２からの副分散パラメータＰｂ（ｉ，１）〜Ｐｂ（ｉ，ｎ）の正当性を検証するための検証情報ＶＰｂ（ｉ，１）〜ＶＰｂ（ｉ，ｎ）を生成する機能を有する。図８（Ｂ）は、パラメータ検証情報生成部１１３の概略構成の一例を示す機能ブロック図である。図８（Ｂ）に示される通り、情報圧縮部１１３１は、ｊ番目の副分散パラメータＰｂ（ｉ，ｊ）のビット長を固定ビット長に圧縮して圧縮データを生成し誤り訂正符号化部１１３２に供給する。情報圧縮部１１３１は、たとえば、入力に対して固定ビット長の出力を与える公知のハッシュ関数などの非線形関数を使用するのが好ましい。また、誤り訂正符号化部１１３２は、情報圧縮部１１３１からの圧縮データに基づいて公知の誤り訂正符号を検証情報ＶＰｂ（ｉ，ｊ）として生成する。ここで、検証情報ＶＰｂ（ｉ，ｊ）は誤り訂正符号に限定される必要はなく、伝送路において副分散パラメータＰｂ（ｉ，ｊ）の改竄や消失を検出可能にするものであれば足りる。
【００８５】
図７に示される通り、パラメータ合成部１１５は、パラメータ生成部１１１から供給された主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）と、パラメータ検証情報生成部１１４から供給された検証情報ＶＰｍ（１）〜検証情報ＶＰｍ（ｎ）と、パラメータ分散部１１２から供給された副分散パラメータＰｂ（１，１）〜Ｐｂ（ｎ，ｎ）と、パラメータ検証情報生成部１１３から供給された検証情報ＶＰｂ（１，１）〜ＶＰｂ（ｎ，ｎ）とを合成して分散パラメータセットφ（１）〜φ（ｎ）を生成する。図１０は、ｍ番目の分散情報管理装置１２ｍに供給されるべき分散パラメータセットφ（ｍ）のデータ・フォーマットを概略的に示す図である。図１０に示されるように、分散パラメータセットφ（ｍ）は、ｍ番目の主分散パラメータＰｍ（ｍ）とこれに付加された検証情報ＶＰｍ（ｍ）とからなる主分散パラメータ情報Ｄｍ（ｍ）を含む。分散パラメータセットφ（ｍ）は、さらに、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）の各々に分散符号化を施して生成された副分散パラメータＰｂ（１，１）〜Ｐｂ（ｎ，ｎ）のうち、ｍ番目の副分散パラメータの集合Ｐｂ（１，ｍ）〜Ｐｂ（ｎ，ｍ）とこれらに対応する検証情報ＶＰｂ（１，ｍ）〜ＶＰｂ（ｎ，ｍ）とを含む。
【００８６】
ここで、副分散パラメータＰｂ（１，１）〜Ｐｂ（ｎ，ｎ）は、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）に対するバックアップ情報である。本実施例では、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）は、安全性の観点から互いに独立し且つ相互に関連しない係数群からなるが、これに限定されず、同一の係数群からなるものでもよい。
【００８７】
上記の通り、パラメータ分散部１１２は、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）の各々を分散符号化する機能を有するが、分散符号化の際に分散パラメータを使用しない公知のＩＤＡ（Information Dispersal Algorithm）に従って主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）の各々を分散符号化している。以下にＩＤＡの一例を説明する。ＩＤＡによれば、分散符号化されるべき秘密情報Ｓは、次式に示されるように複数のセグメントｂ（ｋ−１），…，ｂ（０）に分解される。
【００８８】
【数２７】
2009020078.tif 000029
【００８９】
次に、これらセグメントｂ（ｋ−１），…，ｂ（０）を係数および定数項として有する以下の生成多項式ｈ（ｘ）が与えられる。
【００９０】
【数２８】
2009020078.tif 000030
【００９１】
生成多項式ｈ（ｘ）の関数値は、奇素数ｑを法とした剰余値として算出される。この生成多項式ｈ（ｘ）を用いてｉ番目の分散情報Ｆ（ｍｉ）が、次式に従って算出される。
【００９２】
【数２９】
2009020078.tif 000031
【００９３】
ｋ個の分散情報Ｆ（ｍ１）〜Ｆ（ｍｋ）の収集に成功すれば、以下の連立方程式を解くことにより、元のセグメントｂ（ｋ−１），…，ｂ（０）を復元すなわち再構成することが可能である。
【００９４】
【数３０】
2009020078.tif 000032
【００９５】
＜第１実施例＞
図１１は、本発明の第１実施例に係る分散情報管理システム２の概略構成を示すブロック図である。分散情報管理システム２は、同一構成を有する分散情報管理装置１２１，…，１２ｍ，…，１２ｎの集合体である。ｍ番目の分散情報管理装置１２ｍに着目すれば、この分散情報管理装置１２ｍは、情報保管部１２１ｍ、分散情報更新部１２０ｍおよび分散パラメータ更新部１４０ｍを有している。
【００９６】
情報保管部１２１ｍは、秘密情報分散装置１０から供給された秘密分散情報Ｋ（ｍ）を保管し且つ分散パラメータ分配装置１１から供給された分散パラメータセットφ（ｍ）を保管する。分散情報更新部１２０ｍは、不正者が秘密分散情報Ｋ（ｍ）を盗みこれを用いて不正に秘密情報Ｓｔを復元することを防ぐため、情報保管部１２１ｍに保管されている秘密分散情報Ｋ（ｍ）を定期的に更新する機能を有する。分散パラメータ更新部１４０ｍも同様に情報保管部１２１ｍに保管されている分散パラメータセットφ（ｍ）を定期的に更新する機能を有している。たとえば、分散情報管理システム２に属する分散情報更新部１２０１〜１２０ｎは、予め設定された時刻あるいは外部機器（図示せず）から指定された時刻に一斉に秘密分散情報Ｋ（１）〜Ｋ（ｎ）の更新作業あるいは分散パラメータセットφ（１）〜φ（ｎ）の更新作業を実行することができる。
【００９７】
図１２は、分散情報更新部１２０ｍの概略構成を示す機能ブロック図である。図１２の情報保管部１２１ｍは、主分散情報分散部１２０１に対して主分散パラメータＰｍ（ｍ）と主分散情報Ｓｍ（ｍ）とを供給する。また、情報保管部１２１ｍは、情報復元部１２０３の要求に応じて情報復元部１２０３に副分散情報Ｓｂ（ｊ，ｍ）を供給することができる。主分散情報分散部１２０１は、主分散パラメータＰｍ（ｍ）を用いて主分散情報Ｓｍ（ｍ）に分散符号化を施して複数の再秘密分散情報ＫＲ（ｍ，１）〜ＫＲ（ｍ，ｎ）を生成する機能を有する。図１３は、この主分散情報分散部１２０１の概略構成を示す機能ブロック図である。図１３に示されるように、主分散情報分散部１２０１は、主再秘密分散部１２０４、副再秘密分散部１２０５および情報合成部１２０６を有する。主再秘密分散部１２０４は、図２に示した秘密情報分散装置１０の主秘密分散部１０１と同一の分散符号化機能を有しており、主再秘密分散部１２０４は、主分散パラメータＰｍ（ｍ）を用いて主分散情報Ｓｍ（ｍ）を分散符号化して複数の主再分散情報ＳＲｍ（ｍ，１）〜ＳＲｍ（ｍ，ｎ）を生成する。また主再秘密分散部１２０４は、主分散パラメータＰｍ（ｍ）を用いて主分散情報Ｓｍ（ｍ）から主再秘密分散情報ＫＲｍ（ｍ，１）〜ＫＲｍ（ｍ，ｎ）を生成し、当該主再秘密分散情報ＫＲｍ（ｍ，１）〜ＫＲｍ（ｍ，ｎ）を情報合成部１２０６に供給する。
【００９８】
副再秘密分散部１２０５は、図２に示した秘密情報分散装置１０の副秘密分散部１０２と同一の分散符号化機能を有しており、副再秘密分散部１２０５は、主分散パラメータＰｍ（ｍ）を用いて主再分散情報ＳＲｍ（ｍ，１）〜ＳＲｍ（ｍ，ｎ）を分散符号化して複数の副再秘密分散情報ＫＲｂ（ｍ，１，１）〜ＫＲｂ（ｍ，ｎ，ｎ）を生成する。図１４に示されるように、副再秘密分散部１２０５は、ｉ番目の主再分散情報ＳＲｍ（ｍ，ｉ）を分散符号化してｎ個の副再秘密分散情報ＫＲｂ（ｍ，ｉ，１）〜ＫＲｂ（ｍ，ｉ，ｎ）を生成する。
【００９９】
図１３の情報合成部１２０６は、主再秘密分散部１２０４からの主再秘密分散情報ＫＲｍ（ｍ，１）〜ＫＲｍ（ｍ，ｎ）と、副再秘密分散部１２０５からの副再秘密分散情報ＫＲｂ（ｍ，１，１）〜ＫＲｂ（ｍ，ｎ，ｎ）とを合成して再秘密分散情報ＫＲ（ｍ，１）〜ＫＲ（ｍ，ｎ）を生成することとなる。図１５は、再秘密分散情報ＫＲ（ｍ，ｊ）（ｊ＝１〜ｎ）のデータ・フォーマットを概略的に示す図である。図１５に示されるように、再秘密分散情報ＫＲ（ｍ，ｊ）は、主再分散情報ＳＲｍ（ｍ，ｊ）とこれに付加された検証情報ＶＲｍ（ｍ，ｊ）とからなる主再秘密分散情報ＫＲｍ（ｍ，ｊ）を含む。再秘密分散情報ＫＲ（ｍ，ｊ）はさらに、主再分散情報ＳＲｍ（ｍ，１）〜ＳＲｍ（ｍ，ｎ）の各々に分散符号化を施して生成された副再秘密分散情報ＫＲｂ（ｍ，１，１）〜ＫＲｂ（ｍ，ｎ，ｎ）のうち、ｊ番目の副再秘密分散情報の集合ＫＲｂ（ｍ，１，ｊ）〜ＫＲｂ（ｍ，ｎ，ｊ）を含む。
【０１００】
図１２に示すように主分散情報分散部１２０１は、再秘密分散情報ＫＲ（ｍ，１）〜ＫＲ（ｍ，ｎ）のうち、ｍ番目の分散情報管理装置１２ｍに割り当てられたｍ番目の再秘密分散情報ＫＲ（ｍ，ｍ）を分散情報生成部１２０２に供給し、当該再秘密分散情報ＫＲ（ｍ，ｍ）を除く再秘密分散情報ＫＲ（ｍ，１）〜ＫＲ（ｍ，ｎ）を、分散情報管理装置１２ｍを除く他の分散情報管理装置１２１〜１２ｎに供給する。これと並行して、他の各分散情報管理装置１２ｉ（ｉは、ｍを除く１〜ｎの整数）でも、再秘密分散情報ＫＲ（ｉ，１）〜ＫＲ（ｉ，ｎ）が生成され、当該再秘密分散情報ＫＲ（ｉ，１）〜ＫＲ（ｉ，ｎ）のうちＫＲ（ｉ，ｉ）を除く情報が、分散情報管理装置１２ｉを除く他の分散情報管理装置１２１〜１２ｎに供給される。情報保管部１２１ｍは、当該他の分散情報管理装置１２ｉから供給された再秘密分散情報ＫＲ（ｉ，ｍ）（ｉ≠ｍ）を受信し保管する。また、図１２に示されるように情報保管部１２１ｍは、保管されている再秘密分散情報ＫＲ（ｉ，ｍ）（ｉ≠ｍ）を分散情報生成部１２０２に供給する。
【０１０１】
図１６は、図１２に示した分散情報生成部１２０２の概略構成を示す機能ブロック図である。図１２に示されるように分散情報生成部１２０２には、情報保管部１２１ｍから再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）（ＫＲ（ｍ，ｍ）を除く。）が供給され、主分散情報分散部１２０１から再秘密分散情報ＫＲ（ｍ，ｍ）が供給される。
【０１０２】
図１６に示されるように、分散情報生成部１２０２は情報検証部１２０７Ａを有しており、この情報検証部１２０７Ａは、主再秘密分散情報ＫＲｍ（１，ｍ）〜ＫＲｍ（ｎ，ｍ）のうちの主再分散情報ＳＲｍ（１，ｍ）〜ＳＲｍ（ｎ，ｍ）の正当性を検証情報ＶＲｍ（１，ｍ）〜ＶＲｍ（ｎ，ｍ）を用いて検証し、正当性を有する主再分散情報ＳＲｍ（１，ｍ）〜ＳＲｍ（ｎ，ｍ）を含む主再秘密分散情報ＫＲｍ（１，ｍ）〜ＫＲｍ（ｎ，ｍ）のみを後段の分散情報構成部１２０８Ａに供給する。分散情報構成部１２０８Ａは、情報検証部１２０７Ａから供給された主再秘密分散情報ＫＲｍ（１，ｍ）〜ＫＲｍ（ｎ，ｍ）に基づいて新主秘密分散情報Ｋｍｎ（ｍ）を生成する機能を有する。新主秘密分散情報Ｋｍｎ（ｍ）の生成法については後述する。
【０１０３】
また、図１６に示されるように、分散情報生成部１２０２は情報検証部１２０７Ｂを有しており、この情報検証部１２０７Ｂは、副再秘密分散情報ＫＲｂ（１，１，ｍ）〜ＫＲｂ（ｎ，ｎ，ｍ）のうちの副再分散情報ＳＲｂ（１，１，ｍ）〜ＳＲｂ（ｎ，ｎ，ｍ）の正当性を検証情報ＶＲｂ（１，１，ｍ）〜ＶＲｂ（ｎ，ｎ，ｍ）を用いて検証し、正当性を有する副再分散情報ＳＲｂ（１，１，ｍ）〜ＳＲｂ（ｎ，ｎ，ｍ）を含む副再秘密分散情報ＫＲｂ（１，１，ｍ）〜ＫＲｂ（ｎ，ｎ，ｍ）のみを後段の分散情報構成部１２０８Ｂに供給する。分散情報構成部１２０８Ｂは、情報検証部１２０７Ｂから供給された副再秘密分散情報ＫＲｂ（１，ｉ，ｍ）〜ＫＲｂ（ｎ，ｉ，ｍ）（ｉは１〜ｎのうちの任意整数）に基づいて新副秘密分散情報Ｋｂｎ（ｉ，ｍ）を生成する機能を有する。新副秘密分散情報Ｋｂｎ（ｉ，ｍ）の生成法は、新主秘密分散情報Ｋｍｎ（ｍ）の生成法と同じである。
【０１０４】
情報合成部１２０９は、分散情報構成部１２０８Ａから供給された新主秘密分散情報Ｋｍｎ（ｍ）と、分散情報構成部１２０８Ｂから供給された新副秘密分散情報Ｋｂｎ（１，ｍ）〜Ｋｂｎ（ｎ，ｍ）とを合成して新秘密分散情報Ｋｎ（ｍ）を生成することとなる。図１２の情報保管部１２１ｍに保管されている秘密分散情報Ｋ（ｍ）は、新秘密分散情報Ｋｎ（ｍ）で置換されることにより更新される。
【０１０５】
また、図１６に示されるように、情報検証部１２０７Ａは、再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）に関する第１収集情報Ｄ０（ｍ）を生成し、情報検証部１２０７Ｂは、副再秘密分散情報ＫＲｂ（１，１，ｍ）〜ＫＲｂ（ｎ，ｎ，ｍ）に関する第２収集情報Ｄ１（ｍ）を生成する。これら第１および第２収集情報Ｄ０（ｍ），Ｄ１（ｍ）は、収集情報Ｄ（ｍ）として情報復元部１２０３に供給される。後述するように新秘密分散情報Ｋｎ（ｍ）は、分散情報管理システム２に属する全ての分散情報管理装置１２１〜１２ｎからｎ個の再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）を収集することに成功しなければ、生成され得ないものである。図１２の情報復元部１２０３は、分散情報生成部１２０２から供給される収集情報Ｄ（ｍ）に基づいて、新秘密分散情報Ｋｎ（ｍ）を生成するために再秘密分散情報ＫＲ（ｊ，ｍ）が不足していることを検出すると、当該再秘密分散情報ＫＲ（ｊ，ｍ）を復元する機能を有する。
【０１０６】
図１７は、情報復元部１２０３の概略構成を示す機能ブロック図である。新秘密分散情報Ｋｎ（ｍ）の生成に必要な再秘密分散情報ＫＲ（ｊ，ｍ）が不足する場合、要求生成部１２１２は、ｍ番目の分散情報管理装置１２ｍとｊ番目の分散情報管理装置１２ｊとを除く他の分散情報管理装置１２１〜１２ｎの情報保管部１２１１〜１２１ｎにそれぞれ供給要求Ｒｔ（１）〜Ｒｔ（ｎ）を発する。情報検証部１２１０は、当該供給要求Ｒｔ（１）〜Ｒｔ（ｎ）に応じて供給された副秘密分散情報Ｋｂ（ｊ，１）〜Ｋｂ（ｊ，ｎ）を受信する。情報検証部１２１０は、当該受信された副秘密分散情報Ｋｂ（ｊ，１）〜Ｋｂ（ｊ，ｎ）のうち副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）の正当性を検証情報Ｖｂ（ｊ，１）〜Ｖｂ（ｊ，ｎ）を用いて検証し、正当性を有するものと検証された副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）のみを情報再構成部１２１１に供給する。情報再構成部１２１１は、一定数以上の副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）の収集に成功すれば、これら副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）を復号して主分散情報Ｓｍ（ｊ）を復元すなわち再構成することができる。分散符号化部１２１３は、主分散パラメータＰｍ（ｊ）を用いて、情報再構成部１２１１から供給された主分散情報Ｓｍ（ｊ）を分散符号化することで不足の再秘密分散情報ＫＲ（ｊ，ｍ）を生成できる。当該生成された再秘密分散情報ＫＲ（ｊ，ｍ）は、分散情報生成部１２０２に供給されるので、分散情報生成部１２０２は、新秘密分散情報Ｋｎ（ｍ）を生成することが可能になる。
【０１０７】
なお、主分散パラメータＰｍ（ｊ）は、後述するように図１２の分散パラメータ更新部１４０ｍから供給されるが、主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）が同一の係数群からなる場合には分散パラメータ更新部１４０ｍから主分散パラメータＰｍ（ｊ）の供給を受けずに、主分散パラメータＰｍ（ｍ）を使用すればよい。
【０１０８】
上記構成を有する分散情報管理システム２の動作を図１８を参照しつつ以下に説明する。図１８は、分散情報管理システム２による秘密分散情報Ｋ（１）〜Ｋ（ｎ）の更新のための動作シーケンスの一例を概略的に示す図である。図１８の分散情報管理システム２は分散情報管理装置１２ｉ，１２ｍ，１２ｊにより構成されているが、ここで、分散情報管理装置１２ｉだけは、説明の便宜上、複数の分散情報管理装置１２１〜１２ｎ（１２ｍ，１２ｊを除く。）を表すものとする。
【０１０９】
図１８に示されるように、図１の秘密情報分散装置１０は、秘密分散情報Ｋ（ｉ）を分散情報管理装置１２ｉに供給し、秘密分散情報Ｋ（ｍ）を分散情報管理装置１２ｍに供給し、秘密分散情報Ｋ（ｊ）を分散情報管理装置１２ｊに供給する。これと並行して、図１の分散パラメータ分配装置１１は、分散パラメータセットφ（ｉ）を分散情報管理装置１２ｉに供給し、分散パラメータセットφ（ｍ）を分散情報管理装置１２ｍに供給し、分散パラメータセットφ（ｊ）を分散情報管理装置１２ｊに供給する。この結果、分散情報管理装置１２ｉの情報保管部１２１ｉは秘密分散情報Ｋ（ｉ）および分散パラメータセットφ（ｉ）を保管し、分散情報管理装置１２ｍの情報保管部１２１ｍは秘密分散情報Ｋ（ｍ）および分散パラメータセットφ（ｍ）を保管し、分散情報管理装置１２ｊの情報保管部１２１ｊは秘密分散情報Ｋ（ｊ）および分散パラメータセットφ（ｊ）を保管することとなる。
【０１１０】
ここで、情報保管部１２１ｍは、分散パラメータセットφ（ｍ）のうちの主分散パラメータＰｍ（ｍ）および副分散パラメータ情報Ｄｂ（１，ｍ）〜Ｄｂ（ｎ，ｍ）の正当性を検証情報ＶＰｍ（ｍ），ＶＰｂ（１，ｍ）〜ＶＰｂ（ｎ，ｍ）を用いて検証し、正当性を有すると検証された分散パラメータセットφ（ｍ）のみを保管することができる。他の情報保管部１２１ｉ，１２１ｊも同様である。
【０１１１】
その後、分散情報管理装置１２ｍの主分散情報分散部１２０１（図１２）は、主分散パラメータＰｍ（ｍ）を用いて主分散情報Ｓｍ（ｍ）に分散符号化を施して再秘密分散情報ＫＲ（ｍ，１）〜ＫＲ（ｍ，ｎ）を生成する。次いで主分散情報分散部１２０１は再秘密分散情報ＫＲ（ｍ，ｍ）を除く再秘密分散情報ＫＲ（ｍ，１）〜ＫＲ（ｍ，ｎ）を他の分散情報管理装置１２ｉ，１２ｊに供給する。すなわち、主分散情報分散部１２０１は、ｉ番目の再秘密分散情報ＫＲ（ｍ，ｉ）をこれに対応する分散情報管理装置１２ｉに供給し、ｊ番目の再秘密分散情報ＫＲ（ｍ，ｊ）をこれに対応する分散情報管理装置１２ｊに供給する。これと並行して、分散情報管理装置１２ｉも、同様に、再秘密分散情報ＫＲ（ｉ，１）〜ＫＲ（ｉ，ｎ）を生成し、ｍ番目の再秘密分散情報ＫＲ（ｉ，ｍ）をこれに対応する分散情報管理装置１２ｍに供給し、ｊ番目の再秘密分散情報ＫＲ（ｉ，ｊ）をこれに対応する分散情報管理装置１２ｊに供給する。また、分散情報管理装置１２ｊも、同様に、再秘密分散情報ＫＲ（ｊ，１）〜ＫＲ（ｊ，ｎ）を生成し、ｍ番目の再秘密分散情報ＫＲ（ｊ，ｍ）をこれに対応する分散情報管理装置１２ｍに供給し、ｉ番目の再秘密分散情報ＫＲ（ｊ，ｉ）を対応する分散情報管理装置１２ｉに供給する。
【０１１２】
図１８の動作シーケンスでは、分散情報管理装置１２ｉは、新秘密分散情報Ｋｎ（ｉ）の生成に必要な全ての再秘密分散情報ＫＲ（１，ｉ）〜ＫＲ（ｎ，ｉ）の取得に成功し、分散情報管理装置１２ｊも、新秘密分散情報Ｋｎ（ｊ）の生成に必要な全ての再秘密分散情報ＫＲ（１，ｊ）〜ＫＲ（ｎ，ｊ）の取得に成功するが、分散情報管理装置１２ｍは、新秘密分散情報Ｋｎ（ｍ）の生成に必要な全ての再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）のうち、分散情報管理装置１２ｊから再秘密分散情報ＫＲ（ｊ，ｍ）を取得することに失敗する。これは、たとえば、分散情報管理装置１２ｍ，１２ｊ間の伝送路上に障害が発生したり、分散情報管理装置１２ｊや伝送路上で再秘密分散情報ＫＲ（ｊ，ｍ）が改竄されたりしたことを意味する。
【０１１３】
かかる場合、分散情報管理装置１２ｉは、再秘密分散情報ＫＲ（１，ｉ）〜ＫＲ（ｎ，ｉ）に基づいて新主秘密分散情報Ｋｍｎ（ｉ）および新副秘密分散情報Ｋｂｎ（１，ｉ）〜Ｋｂｎ（ｎ，ｉ）を生成できる。情報保管部１２１ｉに保管されている秘密分散情報Ｋ（ｉ）は、新秘密分散情報Ｋｎ（ｉ）で置換されることにより更新される。一方、分散情報管理装置１２ｊも、再秘密分散情報ＫＲ（１，ｊ）〜ＫＲ（ｎ，ｊ）に基づいて新主秘密分散情報Ｋｍｎ（ｊ）および新副秘密分散情報Ｋｂｎ（１，ｊ）〜Ｋｂｎ（ｎ，ｊ）を生成することが可能である。情報保管部１２１ｊに保管されている秘密分散情報Ｋ（ｊ）も、新秘密分散情報Ｋｎ（ｊ）で置換されることにより更新される。
【０１１４】
新秘密分散情報Ｋｎ（ｉ）は、新主秘密分散情報Ｋｍｎ（ｉ）と新副秘密分散情報Ｋｂ（１，ｉ）〜Ｋｂ（ｎ，ｉ）とで構成され（図５参照）、新主秘密分散情報Ｋｍｎ（ｉ）は、新主分散情報Ｓｍｎ（ｉ）とこれに付加された新検証情報Ｖｍｎ（ｉ）とで構成されるべきである。説明の便宜上、新主分散情報Ｓｍｎ（ｉ）を表す値をＳｍｎ（ｉ）とし、主分散情報Ｓｍ（ｉ）を表す値をＳｍ（ｉ）とし、主再分散情報ＳＲｍ（ｊ，ｉ）を表す値をＳＲｍ（ｊ，ｉ）とする。このとき、新主分散情報Ｓｍｎ（ｉ）は、下記式（１）に従って算出することができる。
【０１１５】
【数３１】
2009020078.tif 000033
【０１１６】
たとえば、分散符号化に使用される（ｋ−１）次の生成多項式の定数項ａ０に秘密情報Ｓｔが含まれるものとすれば、上記のラグランジュ補間法により下記式（２）に従って定数項ａ０を復元することができる。
【０１１７】
【数３２】
2009020078.tif 000034
【０１１８】
上式（２）において、Ａは、全ての分散情報管理装置１２１〜１２ｎに一対一に対応する整数の集合Ｂ＝｛１，２，…，ｎ｝に属するｋ個以上の任意のｒ個の要素からなる部分集合を示す。上式（２）は、部分集合Ａの要素ｊについてのｒ個の加算式である。この式（２）は、下記の如く、集合Ｂの全要素すなわちｎ個の要素についての加算式（３）に変形することができる。
【０１１９】
【数３３】
2009020078.tif 000035
【０１２０】
一方、主再分散情報ＳＲｍ（ｊ，１）〜ＳＲｍ（ｊ，ｎ）のうちのｋ個以上の任意のｒ個の情報に基づいて、下記式（４）に従って主分散情報Ｓｍ（ｊ）を復元することができる。
【０１２１】
【数３４】
2009020078.tif 000036
【０１２２】
上式（２）を上式（１），（３）及び（４）を用いて変形することにより定数項ａ０は下記式のように表現することができる。
【０１２３】
【数３５】
2009020078.tif 000037
【０１２４】
したがって、新主分散情報Ｓｍｎ（ｉ）で主分散情報Ｓｍ（ｉ）を置換したとしても、新主分散情報Ｓｍｎ（１）〜Ｓｍｎ（ｎ）のうちのｋ個以上の情報の収集に成功すれば、元の秘密情報Ｓｔを復元することが可能である。
【０１２５】
また、新副秘密分散情報Ｋｂｎ（ｙ，ｍ）（１≦ｙ≦ｍ）は、上述の通り、図１６の分散情報構成部１２０８Ｂにより副再秘密分散情報ＫＲｂ（１，ｙ，ｍ）〜ＫＲｂ（ｎ，ｙ，ｍ）に基づいて生成されるが、新副秘密分散情報Ｋｂｎ（ｙ，ｍ）の生成法は、新主秘密分散情報Ｋｍｎ（ｉ）の生成法と同じである。すなわち、新副秘密分散情報Ｋｂｎ（ｙ，ｍ）は、新副分散情報Ｓｂｎ（ｙ，ｍ）とこれに付加された新検証情報Ｖｂｎ（ｙ，ｍ）とで構成され（図５参照）、副再秘密分散情報ＫＲｂ（ｉ，ｙ，ｍ）は、副再分散情報ＳＲｂ（ｉ，ｙ，ｍ）とこれに付加された検証情報ＶＲｂ（ｉ，ｙ，ｍ）とで構成される（図１５参照）。説明の便宜上、新副分散情報Ｓｂｎ（ｙ，ｍ）を表す値をＳｂｎ（ｙ，ｍ）とし、副再分散情報ＳＲｂ（ｉ，ｙ，ｍ）を表す値をＳＲｂ（ｉ，ｙ，ｍ）とする。このとき、新副分散情報Ｓｂｎ（ｙ，ｍ）は、次式（５）に従って算出することができる。
【０１２６】
【数３６】
2009020078.tif 000038
【０１２７】
次に、新主分散情報Ｓｍｎ（ｍ）および新副分散情報Ｓｂｎ（ｎ，ｍ）とともに生成される新検証情報Ｖｍｎ（ｍ），Ｖｂｎ（ｎ，ｍ）の生成法を、上記したＶＳＳ法の第３の具体例に基づいて以下に説明する。説明の便宜上、主再分散情報ＳＲｍ（ｊ，ｍ）と副再分散情報ＳＲｂ（ｊ，ｙ，ｍ）について次式（６Ａ）または（６Ｂ）によって対応付けられるＳＲｚ（ｊ，ｍ）を導入し、ＳＲｚ（ｊ，ｍ）を再分散情報と呼ぶこととする。
【０１２８】
【数３７】
2009020078.tif 000039
【０１２９】
また、新主分散情報Ｓｍｎ（ｍ）と新副分散情報Ｓｂｎ（ｙ，ｍ）について次式（６Ｃ）または（６Ｄ）によって対応付けられるＳｚｎ（ｍ）を導入し、Ｓｚｎ（ｍ）を新分散情報と呼ぶこととする。
【０１３０】
【数３８】
2009020078.tif 000040
【０１３１】
上式（６Ａ）と（６Ｃ）は同時に成立し、上式（６Ｂ）と（６Ｄ）は同時に成立する。かかる場合、再分散情報ＳＲｚ（ｊ，ｍ）は、ｊ番目の分散情報管理装置１２ｊから分散情報管理装置１２ｍに送信される情報である。上式（Ａ）により、再分散情報ＳＲｚ（ｊ，ｍ）に対する検証情報ＶＲｚ（ｊ，ｍ）は次式（７）で与えられる。
【０１３２】
【数３９】
2009020078.tif 000041
【０１３３】
ここで、｛Ｃ（α，β；ｊ，ｍ）｝は、各再分散情報ＳＲｚ（ｊ，ｍ）について上式（Ａ）で与えられるコミットメント情報の集合｛Ｃ（α，β）｝である。
【０１３４】
再分散情報ＳＲｚ（ｊ，ｍ）（＝ＳＲｍ（ｊ，ｍ）またはＳＲｂ（ｊ，ｙ，ｍ））は、次式（８）の組で与えられる。
【０１３５】
【数４０】
2009020078.tif 000042
【０１３６】
ここで、Ｓｈｍ１（０），Ｓｈｍ３（０）は上式（Ｂ）と同様の式で与えられる情報である。また、新分散情報Ｓｚｎ（ｍ）（＝Ｓｍｎ（ｍ）またはＳｂｎ（ｙ，ｍ））は、次式（９）の組で与えられる。
【０１３７】
【数４１】
2009020078.tif 000043
【０１３８】
上記の通り、新分散情報Ｓｚｎ（ｍ）は、或るラグランジュ係数Ｌｚｊ，ｎを用いてｎ個の再分散情報ＳＲｚγ（ｊ，ｍ）（γ＝１または２）に基づいて次式（１０）に従って算出することができる。
【０１３９】
【数４２】
2009020078.tif 000044
【０１４０】
よって、次式（１１Ａ），（１１Ｂ）が成立する。
【０１４１】
【数４３】
2009020078.tif 000045
【０１４２】
上式（Ｃ）によれば、再分散情報ＳＲｚ（ｊ，ｍ）の正当性の有無の検証は、次式（１２）が成立するか否かで行うことができる。
【０１４３】
【数４４】
2009020078.tif 000046
【０１４４】
よって、上式（１１Ａ），（１１Ｂ）、（１２）を用いて次式（１３）を得ることが可能である。
【０１４５】
【数４５】
2009020078.tif 000047
【０１４６】
この式（１３）は、新分散情報Ｓｚｎ（ｍ）の正当性を検証するための式とすることができる。故に、新分散情報Ｓｚｎ（ｍ）の検証情報Ｃｎ（α，０；ｍ）を次式（１４）に従って算出することができる。
【０１４７】
【数４６】
2009020078.tif 000048
【０１４８】
したがって、新検証情報Ｖｚｎ（ｍ）（＝Ｖｍｎ（ｍ）またはＶｂｎ（ｙ，ｍ））は、次式（１５）の如きＣｎ（α，０；ｍ）の集合で与えられる。
【０１４９】
【数４７】
2009020078.tif 000049
【０１５０】
上式（１５）を拡張して次式（１６）の一般式を得ることができる。
【０１５１】
【数４８】
2009020078.tif 000050
【０１５２】
図１８の処理シーケンスでは、分散情報管理装置１２ｍは、再秘密分散情報ＫＲ（ｊ，ｍ）の取得に失敗する。このとき、分散情報管理装置１２ｍでは、情報復元部１２０３の要求生成部１２１２（図１７）が分散情報管理装置１２ｉの情報保管部１２１ｉに対して副秘密分散情報Ｋｂ（ｊ，ｉ）の供給要求Ｒｔ（ｉ）を発する。情報検証部１２１０は、供給要求Ｒｔ（ｉ）に応じて供給された副秘密分散情報Ｋｂ（ｊ，ｉ）を受信し、当該副秘密分散情報Ｋｂ（ｊ，ｉ）のうちの副分散情報Ｓｂ（ｊ，ｉ）の正当性を検証情報Ｖｂ（ｊ，ｉ）を用いて検証する。図１７の情報再構成部１２１１が一定数以上の副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）（Ｓｂ（ｊ，ｊ）を除く。）を取得することに成功すれば、これら副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）（Ｓｂ（ｊ，ｊ）を除く。）を復号して主分散情報Ｓｍ（ｊ）を復元することができる。さらに、分散符号化部１２１３は、情報再構成部１２１１から供給された主分散情報Ｓｍ（ｊ）を分散符号化することで不足の再秘密分散情報ＫＲ（ｊ，ｍ）を復元できるので、図１２の分散情報生成部１２０２は、新秘密分散情報Ｋｎ（ｍ）の生成に必要な全ての再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）の取得に成功する。よって、分散情報生成部１２０２は、再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）に基づいて新秘密分散情報Ｋｎ（ｍ）を生成できる。そして、情報保管部１２１ｍに保管されている秘密分散情報Ｋ（ｍ）は、新秘密分散情報Ｋｎ（ｍ）で置換されることにより更新される。
【０１５３】
上記の通り、分散情報管理システム２は、ビザンチン合意プロトコルを使用せずに秘密分散情報Ｋ（１）〜Ｋ（ｎ）を更新することが可能である。非特許文献２に記載された更新方法では、分散情報管理装置１２ｍは、必ずしも、他の全ての分散情報管理装置１２１〜１２ｎから再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）を取得できなくてもよいが、全ての分散情報管理装置１２１〜１２ｎにおいて、どの分散情報管理装置が生成した再分散情報を用いて新たな秘密分散情報を生成するのかを規定する規則が一致していなければならない。かかる一致を確保するために、ビザンチン合意プロトコルが使用されている。上記第１実施例の更新方法では、必ず全ての分散情報管理装置１２１〜１２ｎから供給された再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）を用いて新秘密分散情報Ｋｎ（ｍ）を生成するので、ビザンチン合意のプロトコルが不要である。
【０１５４】
また、図１８に示したように分散情報管理装置１２ｍは、分散情報管理装置１２ｊから再秘密分散情報ＫＲ（ｊ，ｍ）の取得に失敗し、新秘密分散情報Ｋｎ（ｍ）の生成に必要な全ての再秘密分散情報ＫＲ（１，ｍ）〜ＫＲ（ｎ，ｍ）の取得に失敗した場合には、他の分散情報管理装置１２１〜１２ｎから取得した副分散情報Ｓｂ（ｊ，１）〜Ｓｂ（ｊ，ｎ）（Ｓｂ（ｊ，ｊ）を除く。）に基づいて、不足の再秘密分散情報ＫＲ（ｊ，ｍ）を復元することができる。よって、第１実施例の分散情報管理システム２は、安全且つ実用的な秘密分散を提供することができる。
【０１５５】
次に、分散パラメータセットφ（１）〜φ（ｎ）の更新作業について説明する。図１９は、分散パラメータ更新部１４０ｍの概略構成を示す機能ブロック図である。分散パラメータ更新部１４０ｍは、パラメータ分散部１４０１，パラメータ生成部１４０２，パラメータ復元部１４０３およびパラメータ分散部１４０４を有している。
【０１５６】
情報保管部１２１ｍは、パラメータ分散部１４０１に主分散パラメータＰｍ（ｍ）を供給する。また、情報保管部１２１ｍは、パラメータ復元部１４０３の要求に応じてパラメータ復元部１４０３に副分散パラメータＰｂ（ｊ，ｍ）を供給することができる。パラメータ分散部１４０１は、上記ＩＤＡに従って主分散パラメータＰｍ（ｍ）を分散符号化して主再分散パラメータ情報ＤＲｍ（ｍ，１）〜ＤＲｍ（ｍ，ｎ）を生成する。図２０は、このパラメータ分散部１４０１の概略構成を示す機能ブロック図である。図２０に示されるように、パラメータ分散部１４０１は、パラメータ分散符号化部１４０５、パラメータ検証情報生成部１４０６およびパラメータ合成部１４０７を有する。パラメータ分散符号化部１４０５は、図７に示したパラメータ分散部１１２と同一機能を有しており、上記ＩＤＡに従って主分散パラメータＰｍ（ｍ）を分散符号化してｎ個の主再分散パラメータＰＲｍ（ｍ，１）〜ＰＲｍ（ｍ，ｎ）を生成する。パラメータ検証情報生成部１４０６は、図７に示したパラメータ検証情報生成部１１３と同一機能を有しており、主再分散パラメータＰＲｍ（ｍ，１）〜ＰＲｍ（ｍ，ｎ）の正当性をそれぞれ検証するための検証情報ＶＰＲｍ（ｍ，１）〜ＶＰＲｍ（ｍ，ｎ）を生成する。
【０１５７】
図２０のパラメータ合成部１４０７は、パラメータ分散符号化部１４０５からの主再分散パラメータＰＲｍ（ｍ，１）〜ＰＲｍ（ｍ，ｎ）と、パラメータ検証情報生成部１４０６からの検証情報ＶＰＲｍ（ｍ，１）〜ＶＰＲｍ（ｍ，ｎ）とを合成して主再分散パラメータ情報ＤＲｍ（ｍ，１）〜ＤＲｍ（ｍ，ｎ）を生成することとなる。図２１は、ｉ番目の主再分散パラメータ情報ＤＲｍ（ｍ，ｉ）のデータ・フォーマットを概略的に示す図である。図２１に示される通り、主再分散パラメータ情報ＤＲｍ（ｍ，ｉ）は、主再分散パラメータＰＲｍ（ｍ，ｉ）とこれに付加される検証情報ＶＰＲｍ（ｍ，ｉ）とで構成されている。
【０１５８】
図１９に示されるように、パラメータ分散部１４０１で生成された主再分散パラメータ情報ＤＲｍ（ｍ，１）〜ＤＲｍ（ｍ，ｎ）のうち、ｍ番目の分散情報管理装置１２ｍに割り当てられたｍ番目の主再分散パラメータ情報ＤＲｍ（ｍ，ｍ）は、パラメータ生成部１４０２に供給される。また、主再分散パラメータ情報ＤＲｍ（ｍ，ｍ）を除く主再分散パラメータ情報ＤＲｍ（ｍ，１）〜ＤＲｍ（ｍ，ｎ）はそれぞれ対応する分散情報管理装置１２１〜１２ｎに供給される。これと並行して、他の各分散情報管理装置１２ｉ（ｉは、ｍを除く１〜ｎの整数）でも、主再分散パラメータ情報ＤＲｍ（ｉ，１）〜ＤＲｍ（ｉ，ｎ）が生成され、当該主再分散パラメータ情報ＤＲｍ（ｉ，１）〜ＤＲｍ（ｉ，ｎ）のうちＤＲｍ（ｉ，ｉ）を除く情報が、分散情報管理装置１２ｉを除く他の分散情報管理装置１２１〜１２ｎに供給される。情報保管部１２１ｍは、当該他の分散情報管理装置１２ｉから供給された主再分散パラメータ情報ＤＲｍ（ｉ，ｍ）（ｉ≠ｍ）を受信し保管する。また、図１９に示されるように情報保管部１２１ｍは、保管されている主再分散パラメータ情報ＤＲｍ（ｉ，ｍ）（ｉ≠ｍ）の中から主再分散パラメータ情報ＤＲｍ（１，ｍ）〜ＤＲｍ（ｎ，ｍ）（ＤＲｍ（ｍ，ｍ）を除く。）をパラメータ生成部１４０２に供給する。
【０１５９】
図２２は、図１９に示したパラメータ生成部１４０２の概略構成を示す機能ブロック図である。図１９に示されるようにパラメータ生成部１４０２には、情報保管部１２１ｍから主再分散パラメータ情報ＤＲｍ（１，ｍ）〜ＤＲｍ（ｎ，ｍ）（ＤＲｍ（ｍ，ｍ）を除く。）が供給され、パラメータ分散部１４０１から主再分散パラメータ情報ＤＲｍ（ｍ，ｍ）が供給される。図２２のパラメータ検証部１４０８は、これら主再分散パラメータ情報ＤＲｍ（１，ｍ）〜ＤＲｍ（ｎ，ｍ）のうちの主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）の正当性を検証情報ＶＰＲｍ（１，ｍ）〜ＶＰＲｍ（ｎ，ｍ）を用いて検証し、正当性を有するものと検証された主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）のみをパラメータ構成部１４０９に供給する。パラメータ構成部１４０９は、パラメータ検証部１４０８から供給されたＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）に基づいて新主分散パラメータ情報Ｄｍｎ（ｍ）を生成する機能を有する。情報保管部１２１ｍに保管されている分散パラメータセットφ（ｍ）の主分散パラメータ情報Ｄｍ（ｍ）は、新主分散パラメータ情報Ｄｍｎ（ｍ）で置換されることにより更新される。
【０１６０】
図２３は、パラメータ構成部１４０９の概略構成を示す機能ブロック図である。図２３に示されるように、パラメータ構成部１４０９は、結合部１４１０、情報圧縮部１４１１、結合部１４１２、カウンタ１４１３、パラメータ抽出部１４１４、パラメータ検証情報生成部１４１５およびパラメータ合成部１４１６を有している。結合部１４１０、情報圧縮部１４１１およびカウンタ１４１３の動作は、パラメータ構成制御部１４１７によって制御される。
【０１６１】
カウンタ１４１３は、計数値の系列Ｃ（１），…，Ｃ（ｑ）を生成しこれら計数値系列Ｃ（１），…，Ｃ（ｑ）を結合部１４１０に供給する。結合部１４１０は、パラメータ構成部１４０９に入力された主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）のビットと各計数値Ｃ（ｉ）（ｉは１〜ｑのうちの任意整数）のビットとを結合して結合ビット列Ｊ（ｉ）を生成する。結合部１４１０は、結合ビット列Ｊ（１），…，Ｊ（ｑ）を順番に生成してもよいし、あるいは、結合ビット列Ｊ（１），…，Ｊ（ｑ）を並列に生成してもよい。情報圧縮部１４１１は、各結合ビット列Ｊ（ｉ）のビット長を固定ビット長に圧縮して圧縮ビット列Ｈ（ｉ）を生成し、当該圧縮ビット列Ｈ（ｉ）を結合部１４１２に供給する。情報圧縮部１４１１は、たとえば、入力に対して固定ビット長の出力を与える公知のハッシュ関数などの非線形関数を使用するのが好ましい。
【０１６２】
結合部１４１２は、情報圧縮部１４１１から供給された圧縮ビット列Ｈ（１）〜Ｈ（ｑ）を結合して結合ビット列Ｈｊを生成し、当該結合ビット列Ｈｊをパラメータ抽出部１４１４に与える。パラメータ抽出部１４１４は、結合ビット列Ｈｊから所定ビット長の新主分散パラメータＰｍｎ（ｍ）を抽出する。たとえば、結合ビット列Ｈｊの先頭ビットから所定語長のビット列を新主分散パラメータＰｍｎ（ｍ）とすることができる。
【０１６３】
パラメータ検証情報生成部１４１５は、図７に示したパラメータ検証情報生成部１１４と同一機能を有しており、新主分散パラメータＰｍｎ（ｍ）の正当性を検証するための新検証情報ＶＰｍｎ（ｍ）を生成しパラメータ合成部１４１６に供給する。パラメータ合成部１４１６は、新主分散パラメータＰｍｎ（ｍ）に新検証情報ＶＰｍｎ（ｍ）を付加してＤｍｎ（ｍ）を生成することになる。
【０１６４】
図２２に示されるようにパラメータ生成部１４０２のパラメータ検証部１４０８は、主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）に関する収集情報Ｅ（ｍ）を生成しこれを図１９のパラメータ復元部１４０３に供給している。前述の通り、新主分散パラメータ情報Ｄｍｎ（ｍ）は、分散情報管理システム２に属する全ての分散情報管理装置１２１〜１２ｎからｎ個の主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）を収集することに成功しなければ、生成されない。図１９のパラメータ復元部１４０３は、パラメータ生成部１４０２のパラメータ検証部１４０８から供給される収集情報Ｅ（ｍ）に基づいて、新主分散パラメータ情報Ｄｍｎ（ｍ）の生成に必要な主再分散パラメータＰＲｍ（ｊ，ｍ）が不足していることを検出すると、当該主再分散パラメータＰＲｍ（ｊ，ｍ）を復元する機能を有する。
【０１６５】
図２４は、図１９に示したパラメータ復元部１４０３の概略構成を示す機能ブロック図である。新主分散パラメータ情報Ｄｍｎ（ｍ）の生成に必要な主再分散パラメータＰＲｍ（ｊ，ｍ）が不足する場合、要求生成部１４２０は、ｊ番目の分散情報管理装置１２ｊとｍ番目の分散情報管理装置１２ｍとを除く他の分散情報管理装置１２１〜１２ｎにそれぞれ供給要求ＰＲｔ（１）〜ＰＲｔ（ｎ）を発する。パラメータ検証部１４２１は、当該供給要求ＰＲｔ（１）〜ＰＲｔ（ｎ）に応じて供給された副分散パラメータ情報Ｄｂ（ｊ，１）〜Ｄｂ（ｊ，ｎ）（Ｄｂ（ｊ，ｊ）およびＤｂ（ｊ，ｍ）を除く。）を受信する。パラメータ検証部１４２１は、当該受信された副分散パラメータ情報Ｄｂ（ｊ，１）〜Ｄｂ（ｊ，ｎ）のうち副分散パラメータＰｂ（ｊ，１）〜Ｐｂ（ｊ，ｎ）の正当性を検証情報ＶＰｂ（ｊ，１）〜ＶＰｂ（ｊ，ｎ）を用いて検証し、正当性を有するものと検証された副分散パラメータＰｂ（ｊ，１）〜Ｐｂ（ｊ，ｎ）のみをパラメータ再構成部１４２２に供給する。パラメータ再構成部１４２２は、一定数以上の副分散パラメータＰｂ（ｊ，１）〜Ｐｂ（ｊ，ｎ）の収集に成功すれば、これら副分散パラメータＰｂ（ｊ，１）〜Ｐｂ（ｊ，ｎ）を復号して主分散パラメータＰｍ（ｊ）を復元すなわち再構成する。パラメータ分散符号化部１４２３は、上記ＩＤＡに従って主分散パラメータＰｍ（ｊ）を分散符号化することで不足の主再分散パラメータＰＲｍ（ｊ，ｍ）を生成できる。当該生成された主再分散パラメータＰＲｍ（ｊ，ｍ）は、パラメータ生成部１４０２に供給されるので、パラメータ生成部１４０２は、新主分散パラメータ情報Ｄｍｎ（ｍ）を生成することが可能になる。
【０１６６】
また、パラメータ再構成部１４２２で復元された主分散パラメータＰｍ（ｊ）は、分散情報更新部１２０ｍの情報復元部１２０３（図１２）に供給されるため、情報復元部１２０３は、その主分散パラメータＰｍ（ｊ）を用いて不足の主再分散情報ＳＲｍ（ｊ，ｍ）を生成することが可能である。
【０１６７】
図１９に示されるように、パラメータ生成部１４０２で生成された新主分散パラメータ情報Ｄｍｎ（ｍ）は、情報保管部１２１ｍだけでなくパラメータ分散部１４０４にも供給される。パラメータ分散部１４０４は、新主分散パラメータ情報Ｄｍｎ（ｍ）に分散符号化を施して新副分散パラメータ情報Ｄｂｎ（ｍ，１）〜Ｄｂｎ（ｍ，ｎ）を生成する機能を有する。図２５は、パラメータ分散部１４０４の概略構成を示す機能ブロック図である。図２５に示されるようにパラメータ分散部１４０４は、パラメータ分散符号化部１４３０、パラメータ検証情報生成部１４３１およびパラメータ合成部１４３２を含む。パラメータ分散符号化部１４３０は、図７に示したパラメータ分散部１１２と同一機能を有しており、ＩＤＡに従って新主分散パラメータＰｍｎ（ｍ）を分散符号化して新副分散パラメータＰｂｎ（ｍ，１）〜Ｐｂｎ（ｍ，ｎ）を生成する。パラメータ検証情報生成部１４３１は、図７に示したパラメータ検証情報生成部１１３と同一機能を有しており、パラメータ分散符号化部１４３０から供給された新副分散パラメータＰｂｎ（ｍ，１）〜Ｐｂｎ（ｍ，ｎ）をそれぞれ検証するための検証情報ＶＰｂｎ（ｍ，１）〜ＶＰｂｎ（ｍ，ｎ）を生成する。そして、パラメータ合成部１４３２は、新副分散パラメータＰｂｎ（ｍ，１）〜Ｐｂｎ（ｍ，ｎ）にそれぞれ対応する検証情報ＶＰｂｎ（ｍ，１）〜ＶＰｂｎ（ｍ，ｎ）を付加して新副分散パラメータ情報Ｄｂｎ（ｍ，１）〜Ｄｂｎ（ｍ，ｎ）を生成することとなる。
【０１６８】
図１９に示されるように、パラメータ分散部１４０４で生成された新副分散パラメータ情報Ｄｂｎ（ｍ，１）〜Ｄｂｎ（ｍ，ｎ）のうちｍ番目の新副分散パラメータ情報Ｄｂｎ（ｍ，ｍ）は、情報保管部１２１ｍに供給される。分散パラメータセットφ（ｍ）の中の副分散パラメータ情報Ｄｂ（ｍ，ｍ）は、新副分散パラメータ情報Ｄｂｎ（ｍ，ｍ）で置換されることにより更新される。また、新副分散パラメータ情報Ｄｂｎ（ｍ，ｍ）を除く新副分散パラメータ情報Ｄｂｎ（ｍ，１）〜Ｄｂｎ（ｍ，ｎ）はそれぞれ対応する分散情報管理装置１２１〜１２ｎに供給される。これと並行して、他の各分散情報管理装置１２ｉ（ｉは、ｍを除く１〜ｎの整数）でも新副分散パラメータ情報Ｄｂｎ（ｉ，１）〜Ｄｂｎ（ｉ，ｎ）が生成されており、これら新副分散パラメータ情報Ｄｂｎ（ｉ，１）〜Ｄｂｎ（ｉ，ｎ）のうちのｍ番目の新副分散パラメータ情報Ｄｂｎ（ｉ，ｍ）が分散情報管理装置１２ｍの情報保管部１２１ｍに供給される。よって、図１９の情報保管部１２１ｍは、分散情報管理装置１２ｍを除く他の分散情報管理装置１２１〜１２ｎからそれぞれ新副分散パラメータ情報Ｄｂｎ（１，ｍ）〜Ｄｂｎ（ｎ，ｍ）を受信する。そして、情報保管部１２１ｍは、分散パラメータセットφ（ｍ）の中の副分散パラメータ情報Ｄｂ（１，ｍ）〜Ｄｂ（ｎ，ｍ）（Ｄｂ（ｍ，ｍ）を除く。）を、当該受信された新副分散パラメータ情報Ｄｂｎ（１，ｍ）〜Ｄｂｎ（ｎ，ｍ）（Ｄｂｎ（ｍ，ｍ）を除く。）で置換することにより、副分散パラメータ情報Ｄｂ（１，ｍ）〜Ｄｂ（ｎ，ｍ）を更新する。
【０１６９】
次に、分散情報管理システム２による分散パラメータセットφ（１）〜φ（ｎ）の更新作業を図２６および図２７を参照しつつ説明する。図２６および図２７は、分散パラメータセットφ（１）〜φ（ｎ）の更新のための動作シーケンスの一例を概略的に示す図である。図２６および図２７は、一点鎖線ＤＬを介して相互に接続されている。図２６および図２７の分散情報管理システム２は分散情報管理装置１２ｉ，１２ｍ，１２ｊにより構成されているが、ここで、分散情報管理装置１２ｉだけは、説明の便宜上、複数の分散情報管理装置１２１〜１２ｎ（１２ｍ，１２ｊを除く。）を表すものとする。
【０１７０】
図２６に示されるように、図１の秘密情報分散装置１０は、秘密分散情報Ｋ（ｉ）を分散情報管理装置１２ｉに供給し、秘密分散情報Ｋ（ｍ）を分散情報管理装置１２ｍに供給し、秘密分散情報Ｋ（ｊ）を分散情報管理装置１２ｊに供給する。これと並行して、図１の分散パラメータ分配装置１１は、分散パラメータセットφ（ｉ）を分散情報管理装置１２ｉに供給し、分散パラメータセットφ（ｍ）を分散情報管理装置１２ｍに供給し、分散パラメータセットφ（ｊ）を分散情報管理装置１２ｊに供給する。この結果、分散情報管理装置１２ｉの情報保管部１２１ｉは秘密分散情報Ｋ（ｉ）および分散パラメータセットφ（ｉ）を保管し、分散情報管理装置１２ｍの情報保管部１２１ｍは秘密分散情報Ｋ（ｍ）および分散パラメータセットφ（ｍ）を保管し、分散情報管理装置１２ｊの情報保管部１２１ｊは秘密分散情報Ｋ（ｊ）および分散パラメータセットφ（ｊ）を保管する。
【０１７１】
その後、分散情報管理装置１２ｍのパラメータ分散部１４０１（図１９）は、主分散パラメータＰｍ（ｍ）に分散符号化を施して主再分散パラメータ情報ＤＲｍ（ｍ，１）〜ＤＲｍ（ｍ，ｎ）を生成する。次いでパラメータ分散部１４０１は主再分散パラメータ情報ＤＲｍ（ｍ，ｍ）を除く主再分散パラメータ情報ＤＲｍ（ｍ，１）〜ＤＲｍ（ｍ，ｎ）を他の分散情報管理装置１２ｉ，１２ｊに供給する。すなわち、パラメータ分散部１４０１は、ｉ番目の主再分散パラメータ情報ＤＲｍ（ｍ，ｉ）を対応する分散情報管理装置１２ｉに供給し、ｊ番目の主再分散パラメータ情報ＤＲｍ（ｍ，ｊ）を対応する分散情報管理装置１２ｊに供給する。これと並行して、分散情報管理装置１２ｉも、同様に、主再分散パラメータ情報ＤＲｍ（ｉ，１）〜ＤＲｍ（ｉ，ｎ）を生成し、ｍ番目の主再分散パラメータ情報ＤＲｍ（ｉ，ｍ）をこれに対応する分散情報管理装置１２ｍに供給し、ｊ番目の主再分散パラメータ情報ＤＲｍ（ｉ，ｊ）をこれに対応する分散情報管理装置１２ｊに供給する。また、分散情報管理装置１２ｊも、同様に、主再分散パラメータ情報ＤＲｍ（ｊ，１）〜ＤＲｍ（ｊ，ｎ）を生成し、ｍ番目の主再分散パラメータ情報ＤＲｍ（ｊ，ｍ）をこれに対応する分散情報管理装置１２ｍに供給し、ｉ番目の主再分散パラメータ情報ＤＲｍ（ｊ，ｉ）をこれに対応する分散情報管理装置１２ｉに供給する。
【０１７２】
図２６の動作シーケンスでは、図１８の動作シーケンスに合わせて、分散情報管理装置１２ｉは、新主分散パラメータ情報Ｄｍｎ（ｉ）の生成に必要な全ての主再分散パラメータ情報ＤＲｍ（１，ｉ）〜ＤＲｍ（ｎ，ｉ）の取得に成功し、分散情報管理装置１２ｊも、新主分散パラメータ情報Ｄｍｎ（ｊ）の生成に必要な全ての主再分散パラメータ情報ＤＲｍ（１，ｊ）〜ＤＲｍ（ｎ，ｊ）の取得に成功するが、分散情報管理装置１２ｍは、新主分散パラメータ情報Ｄｍｎ（ｍ）の生成に必要な全ての主再分散パラメータ情報ＤＲｍ（１，ｍ）〜ＤＲｍ（ｎ，ｍ）のうち、分散情報管理装置１２ｊから主再分散パラメータ情報ＤＲｍ（ｊ，ｍ）を取得することに失敗する。
【０１７３】
かかる場合、分散情報管理装置１２ｉは、主再分散パラメータ情報ＤＲｍ（１，ｉ）〜ＤＲｍ（ｎ，ｉ）のうちの主再分散パラメータＰＲｍ（１，ｉ）〜ＰＲｍ（ｎ，ｉ）に基づいて新主分散パラメータ情報Ｄｍｎ（ｉ）を生成できる。図２７に示されるように、情報保管部１２１ｉに保管されている主分散パラメータ情報Ｄｍ（ｉ）は、新主分散パラメータ情報Ｄｍｎ（ｉ）で置換されることにより更新される。分散情報管理装置１２ｊも、主再分散パラメータ情報ＤＲｍ（１，ｊ）〜ＤＲｍ（ｎ，ｊ）のうちの主再分散パラメータＰＲｍ（１，ｊ）〜ＰＲｍ（ｎ，ｊ）に基づいて新主分散パラメータ情報Ｄｍｎ（ｊ）を生成することが可能である。情報保管部１２１ｊに保管されている主分散パラメータ情報Ｄｍ（ｊ）も、新主分散パラメータ情報Ｄｍｎ（ｊ）で置換されることにより更新される。
【０１７４】
一方、図２６に示されるように分散情報管理装置１２ｍは、主再分散パラメータ情報ＤＲｍ（ｊ，ｍ）の取得に失敗する。このとき、分散情報管理装置１２ｍでは、パラメータ復元部１４０３の要求生成部１４２０（図２４）が分散情報管理装置１２ｉの情報保管部１２１ｉに対して副分散パラメータ情報Ｄｂ（ｊ，ｉ）の供給要求ＰＲｔ（ｉ）を発する。パラメータ検証部１４２１は、供給要求ＰＲｔ（ｉ）に応じて供給された副分散パラメータ情報Ｄｂ（ｊ，ｉ）を受信し、当該副分散パラメータ情報Ｄｂ（ｊ，ｉ）のうちの副分散パラメータＰｂ（ｊ，ｉ）の正当性を検証情報ＶＰｂ（ｊ，ｉ）を用いて検証する。図２４のパラメータ再構成部１４２２が一定数以上の副分散パラメータＰｂ（ｊ，１）〜Ｐｂ（ｊ，ｎ）（Ｐｂ（ｊ，ｊ）を除く。）を取得することに成功すれば、これら副分散パラメータＰｂ（ｊ，１）〜Ｐｂ（ｊ，ｎ）（Ｐｂ（ｊ，ｊ）を除く。）を復号して主分散パラメータＰｍ（ｊ）を復元することができる。さらに、パラメータ分散符号化部１４２３は、パラメータ再構成部１４２２から供給された主分散パラメータＰｍ（ｊ）を分散符号化することで不足の主再分散パラメータＰＲｍ（ｊ，ｍ）を復元できるので、図１９のパラメータ生成部１４０２は、新主分散パラメータ情報Ｄｍｎ（ｍ）の生成に必要な全ての主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）の取得に成功する。よって、パラメータ生成部１４０２は、主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）に基づいて新主分散パラメータ情報Ｄｍｎ（ｍ）を生成できる。図２７に示されるように、分散情報管理装置１２ｍでは、情報保管部１２１ｉに保管されている主分散パラメータ情報Ｄｍ（ｉ）は、新主分散パラメータ情報Ｄｍｎ（ｉ）で置換されることにより更新される。
【０１７５】
その後、分散情報管理装置１２ｍでは、図１９のパラメータ分散部１４０４が、新主分散パラメータ情報Ｄｍｎ（ｍ）に分散符号化を施して新副分散パラメータ情報Ｄｂｎ（ｍ，１）〜Ｄｂｎ（ｍ，ｎ）を生成する。当該生成された新副分散パラメータ情報Ｄｂｎ（ｍ，１）〜Ｄｂｎ（ｍ，ｎ）のうち、ｍ番目の新副分散パラメータ情報Ｄｂｎ（ｍ，ｍ）は情報保管部１２１ｍに供給される。また、図２７に示されるように、新副分散パラメータ情報Ｄｂｎ（ｍ，ｉ）は、分散情報管理装置１２ｉの情報保管部１２１ｉに供給され、新副分散パラメータ情報Ｄｂｎ（ｍ，ｊ）は、分散情報管理装置１２ｊの情報保管部１２１ｊに供給される。
【０１７６】
同様に、分散情報管理装置１２ｉは、新主分散パラメータ情報Ｄｍｎ（ｉ）に分散符号化を施して新副分散パラメータ情報Ｄｂｎ（ｉ，１）〜Ｄｂｎ（ｉ，ｎ）を生成する。当該生成された新副分散パラメータ情報Ｄｂｎ（ｉ，１）〜Ｄｂｎ（ｉ，ｎ）のうち、ｉ番目の新副分散パラメータ情報Ｄｂｎ（ｉ，ｉ）は情報保管部１２１ｉに供給される。また、図２７に示されるように、新副分散パラメータ情報Ｄｂｎ（ｉ，ｍ）は、分散情報管理装置１２ｍの情報保管部１２１ｍに供給され、新副分散パラメータ情報Ｄｂｎ（ｉ，ｊ）は、分散情報管理装置１２ｊの情報保管部１２１ｊに供給される。
【０１７７】
また、分散情報管理装置１２ｊは、新主分散パラメータ情報Ｄｍｎ（ｊ）に分散符号化を施して新副分散パラメータ情報Ｄｂｎ（ｊ，１）〜Ｄｂｎ（ｊ，ｎ）を生成する。当該生成された新副分散パラメータ情報Ｄｂｎ（ｊ，１）〜Ｄｂｎ（ｊ，ｎ）のうち、ｊ番目の新副分散パラメータ情報Ｄｂｎ（ｊ，ｊ）は情報保管部１２１ｊに供給される。また、図２７に示されるように、新副分散パラメータ情報Ｄｂｎ（ｊ，ｍ）は、分散情報管理装置１２ｍの情報保管部１２１ｍに供給され、新副分散パラメータ情報Ｄｂｎ（ｊ，ｉ）は、分散情報管理装置１２ｉの情報保管部１２１ｉに供給される。
【０１７８】
そして、分散情報管理装置１２ｉは、情報保管部１２１ｉに保管されている副分散パラメータ情報Ｄｂ（１，ｉ）〜Ｄｂ（ｎ，ｉ）を新副分散パラメータ情報Ｄｂｎ（１，ｉ）〜Ｄｂｎ（ｎ，ｉ）で置換することにより副分散パラメータ情報Ｄｂ（１，ｉ）〜Ｄｂ（ｎ，ｉ）を更新する。分散情報管理装置１２ｍは、情報保管部１２１ｍに保管されている副分散パラメータ情報Ｄｂ（１，ｍ）〜Ｄｂ（ｎ，ｍ）を新副分散パラメータ情報Ｄｂｎ（１，ｍ）〜Ｄｂｎ（ｎ，ｍ）で置換することにより副分散パラメータ情報Ｄｂ（１，ｍ）〜Ｄｂ（ｎ，ｍ）を更新する。また、分散情報管理装置１２ｊは、情報保管部１２１ｊに保管されている副分散パラメータ情報Ｄｂ（１，ｊ）〜Ｄｂ（ｎ，ｊ）を新副分散パラメータ情報Ｄｂｎ（１，ｊ）〜Ｄｂｎ（ｎ，ｊ）で置換することにより副分散パラメータ情報Ｄｂ（１，ｊ）〜Ｄｂ（ｎ，ｊ）を更新する。以上により、分散情報管理システム２の分散パラメータセットφ（１）〜φ（ｎ）の更新作業が完了する。
【０１７９】
上記の如く、分散情報管理システム２は、ビザンチン合意プロトコルを使用せずに、分散情報管理装置１２１〜１２ｎに保管された分散パラメータセットφ（１）〜φ（ｎ）を定期的に更新することが可能である。また、図２６に示したように分散情報管理装置１２ｍは、分散情報管理装置１２ｊから主再分散パラメータ情報ＤＲｍ（ｊ，ｍ）の取得に失敗し、新主分散パラメータ情報Ｄｍｎ（ｍ）の生成に必要な全ての主再分散パラメータＰＲｍ（１，ｍ）〜ＰＲｍ（ｎ，ｍ）の取得に失敗した場合には、他の分散情報管理装置１２１〜１２ｎから取得した副分散パラメータＰｂ（ｊ，１）〜Ｐｂ（ｊ，ｎ）（Ｐｂ（ｊ，ｊ）を除く。）に基づいて、不足の主再分散パラメータＰＲｍ（ｊ，ｍ）を復元することができる。したがって、第１実施例の分散情報管理システム２は、安全且つ実用的な秘密分散を提供することが可能である。
【０１８０】
＜第１の変形例＞
次に、上記第１実施例の第１の変形例について以下に説明する。図２８は、第１の変形例に係る秘密情報管理システム１Ａの概略構成を示す機能ブロック図である。この秘密情報管理システム１Ａでは、分散情報管理装置１２Ａ１〜１２Ａｎは、分散パラメータ分配装置１１Ａから暗号化分散パラメータセットφｅ（１）〜φｅ（ｎ）を受信し保管する。
【０１８１】
図２９は、分散パラメータ分配装置１１Ａの概略構成を示す機能ブロック図である。分散パラメータ分配装置１１Ａは、パラメータ生成部１１１、暗号化部２００、パラメータ分散部１１２Ａ、パラメータ検証情報生成部１１３Ａ、パラメータ検証情報生成部１１４およびパラメータ合成部１１５Ａを有する。パラメータ生成部１１１およびパラメータ検証情報生成部１１４は、それぞれ、図７に示したパラメータ生成部１１１およびパラメータ検証情報生成部１１４と同一機能を有している。パラメータ分散部１１２Ａおよびパラメータ検証情報生成部１１３Ａは、入力情報が異なる点を除いて、それぞれ、図７に示したパラメータ分散部１１２およびパラメータ検証情報生成部１１３と同一機能を有している。
【０１８２】
暗号化部２００は、秘密情報分散装置１０から供給された主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）の主分散情報Ｓｍ（１）〜Ｓｍ（ｎ）を暗号鍵として用いて、パラメータ生成部１１１から供給された主分散パラメータＰｍ（１）〜Ｐｍ（ｎ）の各々を暗号化する機能を有する。図３０に示されるように、暗号化部２００は、ｉ番目の主分散情報Ｓｍ（ｉ）を暗号鍵として用いて、パラメータ生成部１１１から供給されたｉ番目の主分散パラメータＰｍ（ｉ）を暗号化して暗号化主分散パラメータＰｍｅ（ｉ）を生成する。パラメータ分散部１１２Ａは、暗号化部２００から供給された暗号化主分散パラメータＰｍｅ（ｉ）を分散符号化して暗号化副分散パラメータＰｂｅ（ｉ，１）〜Ｐｂｅ（ｉ，ｎ）を生成する。そして、パラメータ検証情報生成部１１３Ａは、暗号化副分散パラメータＰｂｅ（ｉ，１）〜Ｐｂｅ（ｉ，ｎ）の正当性をそれぞれ検証するための検証情報ＶＰｂｅ（ｉ，１）〜ＶＰｂｅ（ｉ，ｎ）を生成する。
【０１８３】
図２９に示されているように、パラメータ合成部１１５Ａは、主分散パラメータＰｍ（１）〜Ｐｍ（ｍ）、検証情報ＶＰｍ（１）〜ＶＰｍ（ｎ）、暗号化副分散パラメータＰｂｅ（１，１）〜Ｐｂｅ（ｎ，ｎ）および検証情報ＶＰｂｅ（１，１）〜ＶＰｂｅ（ｎ，ｎ）を合成して暗号化分散パラメータセットφｅ（１）〜φｅ（ｎ）を生成する。図３１は、ｍ番目の分散情報管理装置１２ｍに供給されるべき暗号化分散パラメータセットφｅ（ｍ）のデータ・フォーマットを概略的に示す図である。図３１に示されるように、暗号化分散パラメータセットφｅ（ｍ）は、ｍ番目の主分散パラメータＰｍ（ｍ）とこれに付加された検証情報ＶＰｍ（ｍ）とからなる主分散パラメータ情報Ｄｍ（ｍ）を含む。暗号化分散パラメータセットφｅ（ｍ）は、さらに、暗号化主分散パラメータＰｍｅ（１）〜Ｐｍｅ（ｎ）の各々に分散符号化を施して生成された暗号化副分散パラメータＰｂｅ（１，１）〜Ｐｂｅ（ｎ，ｎ）のうち、ｍ番目の暗号化副分散パラメータの集合Ｐｂｅ（１，ｍ）〜Ｐｂｅ（ｎ，ｍ）とこれらに対応する検証情報ＶＰｂｅ（１，ｍ）〜ＶＰｂｅ（ｎ，ｍ）とを含む。
【０１８４】
ｍ番目の分散情報管理装置１２ｍに着目すれば、この分散情報管理装置１２ｍの情報保管部１２１ｍは、暗号化分散パラメータセットφｅ（ｍ）を保管する点を除けば、図１１に示した情報保管部１２１ｍと同一機能を有する。
【０１８５】
図３２は、第１の変形例に係る分散情報更新部１２０Ａｍの概略構成を示す機能ブロック図である。図３２に示される主分散情報分散部１２０１Ａは、図１２に示した主分散情報分散部１２０１と同じ機能を有する。図３２の分散情報生成部１２０２は、図１２に示した分散情報生成部１２０２と同一機能を有する。情報復元部１２０３Ａは、主分散情報Ｓｍ（ｊ）を分散パラメータ更新部１４０Ａｍに供給する点を除けば、図１２に示した情報復元部１２０３と同一構成および同一機能を有する。図３３は、情報復元部１２０３Ａの概略構成を示す機能ブロック図である。この情報復元部１２０３Ａは、情報再構成部１２１１で生成された主分散情報Ｓｍ（ｊ）を分散パラメータ更新部１４０Ａｍに供給する。
【０１８６】
図３４は、第１の変形例に係る分散パラメータ更新部１４０Ａｍの概略構成を示す機能ブロック図である。図３４に示されるパラメータ分散部１４０１Ａは、図１９に示したパラメータ分散部１４０１と同一機能を有している。図３４に示されるパラメータ生成部１４０２Ａは、図１９に示したパラメータ生成部１４０２と同一機能を有している。
【０１８７】
パラメータ復元部１４０３Ａは、パラメータ生成部１４０２Ａから供給される収集情報Ｅ（ｍ）に基づいて、新主分散パラメータ情報Ｄｍｎ（ｍ）の生成に必要な主再分散パラメータＰＲｍ（ｊ，ｍ）が不足していることを検出すると、当該主再分散パラメータＰＲｍ（ｊ，ｍ）を復元する機能を有する。
【０１８８】
図３５は、図３４に示したパラメータ復元部１４０３Ａの概略構成を示す機能ブロック図である。パラメータ復元部１４０３Ａは、図２４に示したパラメータ復元部１４０３と同一構成を有し、さらに復号部１４４０を有している。新主分散パラメータ情報Ｄｍｎ（ｍ）の生成に必要な主再分散パラメータＰＲｍ（ｊ，ｍ）が不足する場合、要求生成部１４２０は、ｊ番目の分散情報管理装置１２ｊを除く他の分散情報管理装置１２１〜１２ｎにそれぞれ供給要求ＰＲｔ（１）〜ＰＲｔ（ｎ）を発する。パラメータ検証部１４２１は、当該供給要求ＰＲｔ（１）〜ＰＲｔ（ｎ）に応じて供給された暗号化副分散パラメータ情報Ｄｂｅ（ｊ，１）〜Ｄｂｅ（ｊ，ｎ）（Ｄｂｅ（ｊ，ｊ）およびＤｂｅ（ｊ，ｍ）を除く。）を受信する。パラメータ検証部１４２１は、当該受信された暗号化副分散パラメータ情報Ｄｂｅ（ｊ，１）〜Ｄｂｅ（ｊ，ｎ）のうち暗号化副分散パラメータＰｂｅ（ｊ，１）〜Ｐｂｅ（ｊ，ｎ）の正当性を検証情報ＶＰｂｅ（ｊ，１）〜ＶＰｂｅ（ｊ，ｎ）を用いて検証し、正当性を有するものと検証された暗号化副分散パラメータＰｂｅ（ｊ，１）〜Ｐｂｅ（ｊ，ｎ）のみをパラメータ再構成部１４２２に供給する。パラメータ再構成部１４２２は、一定数以上の暗号化副分散パラメータＰｂｅ（ｊ，１）〜Ｐｂｅ（ｊ，ｎ）の収集に成功すれば、これら暗号化副分散パラメータＰｂｅ（ｊ，１）〜Ｐｂｅ（ｊ，ｎ）を復号して暗号化主分散パラメータＰｍｅ（ｊ）を復元すなわち再構成する。
【０１８９】
復号部１４４０は、図３４の分散情報更新部１２０Ａｍから供給された暗号鍵Ｓｍ（ｊ）を用いて暗号化主分散パラメータＰｍｅ（ｊ）を復号して主分散パラメータＰｍ（ｊ）を生成する。パラメータ分散符号化部１４２３は、上記ＩＤＡに従って主分散パラメータＰｍ（ｊ）を分散符号化することで不足の主再分散パラメータＰＲｍ（ｊ，ｍ）を生成できる。当該生成された主再分散パラメータＰＲｍ（ｊ，ｍ）は、パラメータ生成部１４０２Ａに供給されるので、パラメータ生成部１４０２Ａは、新主分散パラメータ情報Ｄｍｎ（ｍ）を生成することが可能になる。
【０１９０】
また、復号部１４４０で生成された主分散パラメータＰｍ（ｊ）は、分散情報更新部１２０Ａｍの情報復元部１２０３Ａ（図３２）に供給されるため、情報復元部１２０３Ａは、その主分散パラメータＰｍ（ｊ）を用いて不足の主再分散情報ＳＲｍ（ｊ，ｍ）を生成することが可能である。
【０１９１】
図３４に示されるように、パラメータ生成部１４０２Ａで生成された新主分散パラメータ情報Ｄｍｎ（ｍ）は、情報保管部１２１Ａｍだけでなくパラメータ分散部１４０４Ａにも供給される。図３６は、パラメータ分散部１４０４Ａの概略構成を示す機能ブロック図である。図３６に示されるようにパラメータ分散部１４０４Ａは、暗号化部１４３３、パラメータ分散符号化部１４３０Ａ、パラメータ検証情報生成部１４３１Ａおよびパラメータ合成部１４３２Ａを含む。暗号化部１４３３は、分散情報更新部１２０Ａｍから供給された新秘密分散情報Ｋｎ（ｍ）の中の新主分散情報Ｓｍｎ（ｍ）を暗号鍵として用いて新主分散パラメータＰｍｎ（ｍ）を暗号化して暗号化新主分散パラメータＰｍｎｅ（ｍ）を生成する。パラメータ分散符号化部１４３０Ａは、図２０に示したパラメータ分散符号化部１４０５と同一機能を有しており、ＩＤＡに従って暗号化新主分散パラメータＰｍｎｅ（ｍ）を分散符号化して暗号化新副分散パラメータＰｂｎｅ（ｍ，１）〜Ｐｂｎｅ（ｍ，ｎ）を生成する。パラメータ検証情報生成部１４３１Ａは、図２０に示したパラメータ検証情報生成部１４３１と同一機能を有し、暗号化新副分散パラメータＰｂｎｅ（ｍ，１）〜Ｐｂｎｅ（ｍ，ｎ）をそれぞれ検証するための検証情報ＶＰｂｎｅ（ｍ，１）〜ＶＰｂｎｅ（ｍ，ｎ）を生成する。そして、パラメータ合成部１４３２Ａは、暗号化新副分散パラメータＰｂｎｅ（ｍ，１）〜Ｐｂｎｅ（ｍ，ｎ）にそれぞれ対応する検証情報ＶＰｂｎｅ（ｍ，１）〜ＶＰｂｎｅ（ｍ，ｎ）を付加して暗号化新副分散パラメータ情報Ｄｂｎｅ（ｍ，１）〜Ｄｂｎｅ（ｍ，ｎ）を生成することとなる。
【０１９２】
図３４に示されるように、パラメータ分散部１４０４Ａで生成された暗号化新副分散パラメータ情報Ｄｂｎｅ（ｍ，１）〜Ｄｂｎｅ（ｍ，ｎ）のうちｍ番目の暗号化新副分散パラメータ情報Ｄｂｎｅ（ｍ，ｍ）は、情報保管部１２１Ａｍに供給される。暗号化分散パラメータセットφｅ（ｍ）の中の暗号化副分散パラメータ情報Ｄｂｅ（ｍ，ｍ）は、暗号化新副分散パラメータ情報Ｄｂｎｅ（ｍ，ｍ）で置換されることにより更新される。また、暗号化新副分散パラメータ情報Ｄｂｎｅ（ｍ，ｍ）を除く暗号化新副分散パラメータ情報Ｄｂｎｅ（ｍ，１）〜Ｄｂｎｅ（ｍ，ｎ）はそれぞれ対応する分散情報管理装置１２１〜１２ｎに供給される。これと並行して、他の各分散情報管理装置１２ｉ（ｉは、ｍを除く１〜ｎの整数）でも暗号化新副分散パラメータ情報Ｄｂｎｅ（ｉ，１）〜Ｄｂｎｅ（ｉ，ｎ）が生成されており、これら暗号化新副分散パラメータ情報Ｄｂｎｅ（ｉ，１）〜Ｄｂｎｅ（ｉ，ｎ）のうちのｍ番目の暗号化新副分散パラメータ情報Ｄｂｎｅ（ｉ，ｍ）が分散情報管理装置１２ｍの情報保管部１２１ｍに供給される。よって、図３４の情報保管部１２１Ａｍは、分散情報管理装置１２ｍを除く他の分散情報管理装置１２１〜１２ｎからそれぞれ暗号化新副分散パラメータ情報Ｄｂｎｅ（１，ｍ）〜Ｄｂｎｅ（ｎ，ｍ）を受信する。そして、情報保管部１２１Ａｍは、暗号化分散パラメータセットφｅ（ｍ）の中の暗号化副分散パラメータ情報Ｄｂｅ（１，ｍ）〜Ｄｂｅ（ｎ，ｍ）（Ｄｂｅ（ｍ，ｍ）を除く。）を、当該受信された暗号化新副分散パラメータ情報Ｄｂｎｅ（１，ｍ）〜Ｄｂｎｅ（ｎ，ｍ）（Ｄｂｎｅ（ｍ，ｍ）を除く。）で置換することにより、暗号化副分散パラメータ情報Ｄｂｅ（１，ｍ）〜Ｄｂｅ（ｎ，ｍ）を更新する。
【０１９３】
上記の如く、第１の変形例に係る分散情報管理システム２Ａでは、暗号化副分散パラメータ情報Ｄｂｅ（１，ｉ）〜Ｄｂｅ（ｎ，ｉ）（ｉ＝１〜ｎ）は暗号化された状態で分散情報管理装置１２１〜１２ｎに保管され利用されるため、分散情報管理システム２Ａの安全性を向上させることができる。この分散情報管理システム２Ａにおいては、たとえば、「Hugo Krawczyk, "Secret Sharing Made Short," Advances in Cryptology - CRYPTO '93, Lecture Notes in Computer Science, Springer Verlag, vol. 773, pp. 136-146, 1993」（非特許文献４）や「Hugo Krawczyk, "Distributed Fingerprints and Secure Information Dispersal," Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, pp. 207-218, 1993」（非特許文献５）に記載されている安全且つ効率の良い秘密分散を援用することが可能である。
【０１９４】
なお、図３４に示されているようにパラメータ分散部１４０１Ａは、暗号化されていない主再分散パラメータＰＲｍ（ｍ，１）〜ＰＲｍ（ｍ，ｎ）を含む主再分散パラメータ情報ＤＲｍ（ｍ，１）〜ＤＲｍ（ｍ，ｎ）を生成しているが、これに限らず、主再分散パラメータＰＲｍ（ｍ，１）〜ＰＲｍ（ｍ，ｎ）が暗号化されていてもよい。
【０１９５】
＜第２の変形例＞
上記第１実施例では、図３７（Ａ）に示されるように分散情報管理システム２に属する各分散情報管理装置１２ｉ（ｉは、１〜ｎのうちの任意整数）は、必ず、分散パラメータセットφ（ｉ）と秘密分散情報Ｋ（ｉ）の双方を保管している。第２の変形例では、図３７（Ｂ）に示されるように、分散情報管理システム２に属する全ての分散情報管理装置１２１〜１２ｎのうち、ｍ個の分散情報管理装置１２１〜１２ｍは、分散パラメータセットφ（１）〜φ（ｍ）と秘密分散情報Ｋ（１）〜Ｋ（ｍ）の双方を有するが、残りの分散情報管理装置１２ｍ＋１〜１２ｎは、秘密分散情報を保管せずに分散パラメータセットφ（ｍ＋１）〜φ（ｎ）を保管する。
【０１９６】
第２の変形例では、秘密分散情報を保管しない分散情報管理装置１２ｍ＋１〜１２ｎと、秘密分散情報Ｋ（１）〜Ｋ（ｍ）を保管する分散情報管理装置１２１〜１２ｍとが混在することになる。このように優先度あるいは重要度に応じて、分散情報管理装置１２１〜１２ｎを区分して有効利用することが可能である。また、分散情報管理装置１２ｍ＋１〜１２ｎでは、秘密分散情報が保管されないので、データ保管量や処理量が少なくなる。
【０１９７】
＜第３の変形例＞
次に、上記第１実施例の第３の変形例について以下に説明する。第３の変形例は、図１３に示した主分散情報分散部１２０１の代わりに、図３８に示される主分散情報分散部１２０１Ｂを使用する。図３８の主分散情報分散部１２０１Ｂは、主分散情報分散部１２０１と同一の機能ブロック１２０４，１２０５，１２０６を有し、さらにパラメータ生成部１２２０を有している。
【０１９８】
図３８のパラメータ生成部１２２０は、主分散パラメータＰｍ（ｍ）と主分散情報Ｓｍ（ｍ）とに基づいて新たに主分散パラメータＰｍａ（ｍ），Ｐｍｂ（ｍ，１）〜Ｐｍｂ（ｍ，ｎ）を生成する機能を有する。主分散パラメータＰｍａ（ｍ）は、主再秘密分散部１２０４に供給され、主再秘密分散部１２０４による分散符号化に使用される。また、主分散パラメータＰｍｂ（ｍ，１）〜Ｐｍｂ（ｍ，ｎ）は、副再秘密分散部１２０５に供給される。副再秘密分散部１２０５は、図３９に示されるように、ｉ番目の主分散パラメータＰｍｂ（ｍ，ｉ）を用いてｉ番目の主再分散情報ＳＲｍ（ｍ，ｉ）を分散符号化してｎ個の副再秘密分散情報ＫＲｂ（ｍ，ｉ，１）〜ＫＲｂ（ｍ，ｉ，ｎ）を生成する。
【０１９９】
図４０は、パラメータ生成部１２２０の概略構成を示す機能ブロック図である。図４０のパラメータ生成部１２２０は、結合部１２２１、情報圧縮部１２２２、結合部１２２３、カウンタ１２２４、パラメータ構成制御部１２２５および情報分割部１２２６を含む。結合部１２２１、情報圧縮部１２２２およびカウンタ１２２４の動作は、パラメータ構成制御部１２２５によって制御される。
【０２００】
カウンタ１２２４は、計数値の系列Ｃ（１），…，Ｃ（ｑ）を生成しこれら計数値系列Ｃ（１），…，Ｃ（ｑ）を結合部１２２１に供給する。結合部１２２１は、パラメータ生成部１２２０に入力された主分散情報Ｓｍ（ｍ）のビットと主分散パラメータＰｍ（ｍ）のビットと各計数値Ｃ（ｉ）（ｉは１〜ｑのうちの任意整数）のビットとを結合して結合ビット列Ｊ（ｉ）を生成する。結合部１２２１は、結合ビット列Ｊ（１），…，Ｊ（ｑ）を順番に生成してもよいし、あるいは、結合ビット列Ｊ（１），…，Ｊ（ｑ）を並列に生成してもよい。情報圧縮部１２２２は、各結合ビット列Ｊ（ｉ）のビット長を固定ビット長に圧縮して圧縮ビット列Ｈ（ｉ）を生成し、当該圧縮ビット列Ｈ（ｉ）を結合部１２２３に供給する。情報圧縮部１２２２は、たとえば、入力に対して固定ビット長の出力を与える公知のハッシュ関数などの非線形関数を使用するのが好ましい。
【０２０１】
結合部１２２３は、情報圧縮部１２２２から供給された圧縮ビット列Ｈ（１）〜Ｈ（ｑ）を結合して結合ビット列Ｈｊを生成し、当該結合ビット列Ｈｊを情報分割部１２２６に与える。情報分割部１２２６は、結合ビット列Ｈｊを主分散パラメータＰｍａ（ｍ），Ｐｍｂ（ｍ，１）〜Ｐｍｂ（ｍ，ｎ）に分割し、これら主分散パラメータＰｍａ（ｍ），Ｐｍｂ（ｍ，１）〜Ｐｍｂ（ｍ，ｎ）を図３８の主再秘密分散部１２０４および副再秘密分散部１２０５に供給する。
【０２０２】
なお、図３８および図４０のパラメータ生成部１２２０は、主分散情報Ｓｍ（ｍ）および主分散パラメータＰｍ（ｍ）の双方から主分散パラメータＰｍａ（ｍ），Ｐｍｂ（ｍ，１）〜Ｐｍｂ（ｍ，ｎ）を生成しているが、この代わりに、パラメータ生成部１２２０が主分散パラメータＰｍ（ｍ）のみから主分散パラメータＰｍａ（ｍ），Ｐｍｂ（ｍ，１）〜Ｐｍｂ（ｍ，ｎ）を生成してもよい。
【０２０３】
第３の変形例では、分散符号化に必要なデータ量を持つ主分散パラメータＰｍａ（ｍ），Ｐｍｂ（ｍ，１）〜Ｐｍｂ（ｍ，ｎ）が主分散情報分散部１２０１Ｂで生成されるので、主分散パラメータＰｍ（ｍ）のデータ量を削減することが可能である。これにより、情報保管部１２１ｍに含まれる記憶装置のメモリ容量を削減でき、製造コストの低減も可能になる。
【０２０４】
＜第２実施例＞
次に、本発明の第２実施例について以下に説明する。図４１は、本発明の第２実施例に係る秘密情報管理システム１Ｃの概略構成を示す機能ブロック図である。この秘密情報管理システム１Ｃでは、分散情報管理システム２Ｃは、同一構成を有する分散情報管理装置１２Ｃ１，…，１２Ｃｍ，…，１２Ｃｎの集合体である。ｍ番目の分散情報管理装置１２Ｃｍに着目すれば、この分散情報管理装置１２Ｃｍは、情報保管部１２１ｍ、鍵分散情報更新部１５０ｍおよび分散パラメータ更新部１４０ｍを有している。
【０２０５】
図４１の情報保管部１２１１〜１２１ｎの機能は、上記第１実施例の情報保管部１２１１〜１２１ｎ（図１１）の機能と同じであり、また、図４１の分散パラメータ更新部１４０１〜１４０ｎの機能は、上記第１実施例の分散パラメータ更新部１４０１〜１４０ｎの機能と同じである。第２実施例では、図１に示した秘密情報分散装置１０の代わりに、図４２に示される秘密情報分散装置１０Ｃが使用され、図１に示した分散情報更新部１２０１〜１２０ｎの代わりに、図４１に示される鍵分散情報更新部１５０１〜１５０ｎが使用され、図１に示した復号装置１３の代わりに、図４３に示される復号装置１３Ｃが使用される。
【０２０６】
図４１の秘密情報分散装置１０Ｃは、暗号鍵を用いて秘密情報Ｓｔを暗号化して分散符号化するとともに、当該暗号鍵を分散符号化して複数の鍵分散情報を生成する。これら鍵分散情報は、分散情報管理装置１２Ｃ１〜１２Ｃｎの情報保管部１２１１〜１２１ｎに保管されつつ、鍵分散情報更新部１５０１〜１５０ｎによって定期的に更新される。
【０２０７】
図４２は、秘密情報分散装置１０Ｃの概略構成を示す機能ブロック図である。図４２に示されるように、秘密情報分散装置１０Ｃは、主秘密分散部１０１Ｃを有するが、この主秘密分散部１０１Ｃの機能は、図２０に示したパラメータ分散部１４０１の機能と同じである。秘密情報分散装置１０Ｃは、さらに、秘密情報Ｓｔを暗号化するモジュールとして、暗号鍵生成部３００、暗号化部３０１および秘密分散部３０２を有している。
【０２０８】
暗号鍵生成部３００は、たとえば疑似乱数から暗号鍵Ｋｙを生成し、この暗号鍵Ｋｙを暗号化部３０１および秘密分散部３０２に供給する。本変形例では、暗号鍵Ｋｙは、秘密情報分散装置１０Ｃの内部で生成されるが、この代わりに、外部の鍵生成源から暗号鍵Ｋｙが与えられてもよい。
【０２０９】
暗号化部３０１は、暗号鍵Ｋｙを用いて秘密情報Ｓｔを暗号化して暗号化秘密情報ＥＳｔを生成する。この暗号化秘密情報ＥＳｔは、主秘密分散部１０１Ｃに供給される。一方、秘密分散部３０２は、分散パラメータセットφ（０）を用いて、暗号鍵生成部３００から供給された暗号鍵Ｋｙを分散符号化して複数の鍵分散情報ＳＫｙ（１）〜ＳＫｙ（ｎ）を生成する。暗号鍵Ｋｙのサイズは、秘密情報Ｓｔのサイズに比べると非常に小さくすることができる。たとえば、暗号化部３０１が公知のＡＥＳ（Advanced Encryption Standard）の対称鍵暗号アルゴリズムに従って数十キロバイト程度の秘密情報Ｓｔを暗号化する場合、暗号鍵Ｋｙのサイズを１２８ビット程度にすることが可能である。
【０２１０】
図４４に示されるように、ｍ番目の鍵分散情報ＳＫｙ（ｍ）は、主鍵秘密分散情報ＳＫｍ（ｍ）と、複数の副鍵秘密分散情報ＳＫｂ（１，ｍ）〜ＳＫｂ（ｎ，ｍ）とからなる。秘密分散部３０２は、先ず、分散パラメータφ（０）を用いて暗号鍵Ｋｙを分散符号化して複数の主鍵分散情報Ｓｋｍ（１）〜Ｓｋｍ（ｍ）を生成し、これら主鍵分散情報Ｓｋｍ（１）〜Ｓｋｍ（ｍ）の正当性をそれぞれ検証するための検証情報ＳＶｍ（１）〜ＳＶｍ（ｍ）を生成する。さらに秘密分散部３０２は、分散パラメータφ（０）を用いて各主鍵分散情報Ｓｋｍ（ｉ）（ｉは１〜ｎのうちの任意整数）を分散符号化して複数の副鍵分散情報Ｓｋｂ（ｉ，１）〜Ｓｋｂ（ｉ，ｎ）を生成し、これら副鍵分散情報Ｓｋｂ（ｉ，１）〜Ｓｋｂ（ｉ，ｎ）の正当性をそれぞれ検証するための検証情報ＳＶｂ（ｉ，１）〜ＳＶｂ（ｉ，ｎ）を生成する。最終的に、秘密分散部３０２は、図４４に示されるフォーマットを持つ鍵分散情報ＳＫｙ（１）〜ＳＫｙ（ｎ）を生成することとなる。
【０２１１】
情報合成部１０３Ｃは、秘密分散部３０２からの鍵分散情報ＳＫｙ（１）〜ＳＫｙ（ｎ）と、主秘密分散部１０１Ｃからの主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）とを合成して秘密分散情報Ｋｅ（１）〜Ｋｅ（ｎ）を生成する。
【０２１２】
図４４は、ｍ番目の分散情報管理装置１２ｍに供給され且つ管理される秘密分散情報Ｋｅ（ｍ）のデータ・フォーマットを概略的に示す図である。図４４に示されるように、秘密分散情報Ｋｅ（ｍ）は、暗号化主分散情報ＥＫｍ（ｍ）とこれに付加された検証情報ＥＶｍ（ｍ）とからなる主秘密分散情報Ｋｍ（ｍ）と、鍵分散情報ＳＫｙ（ｍ）とを含む。各分散情報管理装置１２ｉの鍵分散情報更新部１５０ｉは、情報保管部１２１ｉに保管される鍵分散情報ＳＫｙ（ｉ）を定期的に更新する機能を有している。その更新方法は、第１実施例や第１〜第３の変形例において秘密分散情報Ｋ（１）〜Ｋ（ｎ）を更新する方法と実質的に同じである。すなわち、各秘密分散情報Ｋ（ｉ）の主秘密分散情報Ｋｍ（ｉ）の更新方法と同様の処理により、主鍵秘密分散情報ＳＫｍ（ｉ）が更新され、また、各秘密分散情報Ｋ（ｉ）の副秘密分散情報Ｋｂ（１，ｉ）〜Ｋｂ（ｎ，ｉ）の更新方法と同様の処理により、副鍵秘密分散情報ＳＫｂ（１，ｉ）〜ＳＫｂ（ｎ，ｉ）が更新される。
【０２１３】
図４１に示されるように、情報保管部１２１ｍは、秘密情報分散装置１０から供給された秘密分散情報Ｋｅ（ｍ）を保管し且つ分散パラメータ分配装置１１から供給された分散パラメータセットφ（ｍ）を保管する。
【０２１４】
図４５は、鍵分散情報更新部１５０ｍの概略構成を示す機能ブロック図である。この鍵分散情報更新部１５０ｍの構成は、入出力情報が異なる点を除いて、第１実施例の分散情報更新部１２０ｍの構成と実質的に同一である。すなわち、鍵分散情報更新部１５０ｍは、主分散情報分散部１２０１Ｃ、分散情報生成部１２０２Ｃおよび情報復元部１２０３Ｃを有している。
【０２１５】
図４５の情報保管部１２１ｍは、主分散情報分散部１２０１Ｃに対して主分散パラメータＰｍ（ｍ）と主鍵分散情報Ｓｋｍ（ｍ）とを供給する。また、情報保管部１２１ｍは、情報復元部１２０３Ｃの要求に応じて情報復元部１２０３Ｃに副鍵分散情報Ｓｋｂ（ｊ，ｍ）を供給することができる。主分散情報分散部１２０１Ｃは、主分散パラメータＰｍ（ｍ）を用いて主鍵分散情報Ｓｋｍ（ｍ）に分散符号化を施して複数の再鍵秘密分散情報ＳＫＲ（ｍ，１）〜ＳＫＲ（ｍ，ｎ）を生成する機能を有する。これら再鍵秘密分散情報ＳＫＲ（ｍ，１）〜ＳＫＲ（ｍ，ｎ）は、上記第１実施例の再秘密分散情報ＫＲ（ｍ，１）〜ＫＲ（ｍ，ｎ）と同様の方法で処理されるべきものである。
【０２１６】
図４６に、再鍵秘密分散情報ＳＫＲ（ｍ，ｊ）のデータ・フォーマットを概略的に示す。図４６に示されるように、再鍵秘密分散情報ＳＫＲ（ｍ，ｊ）は、主再鍵分散情報ＳｋＲｍ（ｍ，ｊ）とこれに付加された検証情報ＶＳＲｍ（ｍ，ｊ）とからなる主再鍵秘密分散情報ＳＫＲｍ（ｍ，ｊ）を含む。再鍵秘密分散情報ＳＫＲ（ｍ，ｊ）はさらに、主再鍵分散情報ＳｋＲｍ（ｍ，１）〜ＳｋＲｍ（ｍ，ｎ）の各々に分散符号化を施して生成された副再鍵秘密分散情報ＳＫＲｂ（ｍ，１，１）〜ＳＫＲｂ（ｍ，ｎ，ｎ）のうち、ｊ番目の副再鍵秘密分散情報の集合ＳＫＲｂ（ｍ，１，ｊ）〜ＳＫＲｂ（ｍ，ｎ，ｊ）を含む。各副再鍵秘密分散情報ＳＫＲｂ（ｍ，i，ｊ）（ｉは１〜ｎのうちの任意整数）は、副再鍵分散情報ＳｋＲｂ（ｍ，i，ｊ）とこれの正当性を検証するための検証情報ＳＶＲｂ（ｍ，i，ｊ）とからなる。
【０２１７】
図４５に示すように主分散情報分散部１２０１Ｃは、再鍵秘密分散情報ＳＫＲ（ｍ，１）〜ＳＫＲ（ｍ，ｎ）のうち、ｍ番目の分散情報管理装置１２ｍに割り当てられたｍ番目の再鍵秘密分散情報ＳＫＲ（ｍ，ｍ）を分散情報生成部１２０２Ｃに供給し、当該再鍵秘密分散情報ＳＫＲ（ｍ，ｍ）を除く再鍵秘密分散情報ＳＫＲ（ｍ，１）〜ＳＫＲ（ｍ，ｎ）を、分散情報管理装置１２ｍを除く他の分散情報管理装置１２１〜１２ｎに供給する。これと並行して、他の各分散情報管理装置１２ｉ（ｉは、ｍを除く１〜ｎの整数）でも、再鍵秘密分散情報ＳＫＲ（ｉ，１）〜ＳＫＲ（ｉ，ｎ）が生成され、当該再鍵秘密分散情報ＳＫＲ（ｉ，１）〜ＳＫＲ（ｉ，ｎ）のうちＳＫＲ（ｉ，ｉ）を除く情報が、分散情報管理装置１２ｉを除く他の分散情報管理装置１２１〜１２ｎに供給される。情報保管部１２１ｍは、当該他の分散情報管理装置１２ｉから供給された再鍵秘密分散情報ＳＫＲ（ｉ，ｍ）（ｉ≠ｍ）を受信し保管する。また、図４５に示されるように情報保管部１２１ｍは、保管されている再鍵秘密分散情報ＳＫＲ（ｉ，ｍ）（ｉ≠ｍ）を分散情報生成部１２０２Ｃに供給する。
【０２１８】
分散情報生成部１２０２Ｃは、情報保管部１２１ｍから供給された再鍵秘密分散情報ＳＫＲ（１，ｍ）〜ＳＫＲ（ｎ，ｍ）（ＳＫＲ（ｍ，ｍ）を除く。）と、主分散情報分散部１２０１Ｃから供給された再鍵秘密分散情報ＳＫＲ（ｍ，ｍ）とに基づいて新鍵分散情報ＳＫｙ（ｍ）を生成する機能を有する。分散情報生成部１２０２Ｃの構成は、入出力情報が異なる点を除いて、第１実施例の分散情報生成部１２０２（図１６）の構成と実質的に同じである。
【０２１９】
また、情報復元部１２０３Ｃは、分散情報生成部１２０２Ｃから供給される収集情報Ｄ（ｍ）に基づいて、新鍵分散情報ＳＫｙ（ｍ）を生成するために再鍵秘密分散情報ＳＫＲ（ｊ，ｍ）が不足していることを検出すると、当該再鍵秘密分散情報ＳＫＲ（ｊ，ｍ）を復元する機能を有する。この情報復元部１２０３Ｃの構成は、入出力情報が異なる点を除いて、上記第１実施例の情報復元部１２０３の構成（図１７）と実質的に同じである。
【０２２０】
一方、図４３の復号装置１３Ｃは、分散情報管理装置１２１〜１２ｎから、秘密分散情報Ｋｅ（１）〜Ｋｅ（ｎ）のうちｋ個以上の秘密分散情報の収集に成功すれば、これら秘密分散情報に基づいて元の秘密情報Ｓｔを復元する機能を有する。図４３に示されるように復号装置１３Ｃは、情報分離部３０３、鍵再構成部３０４、分散情報検証部１３１、情報再構成部１３２および暗号情報復号部３０５を有する。分散情報検証部１３１の構成は、入出力情報が異なる点を除いて図２４に示したパラメータ復元部１４０３のパラメータ検証部１４２１の構成と同じである。また、情報再構成部１３２の構成は、入出力情報が異なる点を除いて図２４に示したパラメータ再構成部１４２２の構成と同じである。
【０２２１】
情報分離部３０３は、分散情報管理装置１２１〜１２ｎから供給された秘密分散情報Ｋｅ（１）〜Ｋｅ（ｎ）から、主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）と鍵分散情報ＳＫｙ（１）〜ＳＫｙ（ｎ）とを分離する。鍵再構成部３０４は、情報分離部３０３から供給された鍵分散情報ＳＫｙ（１）〜ＳＫｙ（ｎ）を復号して暗号鍵Ｋｙを復元すなわち再構成する。分散情報検証部１３１は、情報分離部３０３から供給された主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）のうちの暗号化主分散情報ＥＫｍ（１）〜ＥＫｍ（ｎ）の正当性を検証する。情報再構成部１３２は、分散情報検証部１３１から一定数（閾値）以上の暗号化主分散情報ＥＫｍ（１）〜ＥＫｍ（ｎ）を取得することに成功すれば、これら暗号化主分散情報ＥＫｍ（１）〜ＥＫｍ（ｎ）から暗号化秘密情報ＥＳｔを復元することができる。
【０２２２】
暗号情報復号部３０５は、鍵再構成部３０４から供給された暗号鍵Ｋｙを用いて暗号化秘密情報ＥＳｔを復号して元の秘密情報Ｓｔを生成することができる。なお、第２実施例では、分散情報管理装置１２１〜１２ｎから秘密分散情報Ｋｅ（１）〜Ｋｅ（ｎ）が供給されるが、秘密情報Ｓｔの復元のために使用される情報は主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）と主鍵秘密分散情報ＳＫｍ（１）〜ＳＫｍ（ｎ）のみであるから、分散情報管理装置１２１〜１２ｎは、主秘密分散情報Ｋｍ（１）〜Ｋｍ（ｎ）と主鍵秘密分散情報ＳＫｍ（１）〜ＳＫｍ（ｎ）のみを復号装置１３Ｃに供給してもよい。
【０２２３】
上記の通り、秘密情報Ｓｔは、暗号鍵Ｋｙを用いて暗号化され且つ分散符号化されるため、暗号鍵Ｋｙがなければ元の秘密情報Ｓｔを復元することができない。このため、鍵分散情報ＳＫｙ（１）〜ＳＫｙ（１）を定期的に且つ安全に更新することで秘密情報Ｓｔの安全性を確保することができる。秘密情報Ｓｔと比べると暗号鍵Ｋｙの容量は小さいため、鍵分散情報ＳＫｙ（１）〜ＳＫｙ（１）の更新作業に要する時間や計算量を小さくすることができる。したがって、安全性の高い効率的な分散情報管理システム２Ｃを提供することが可能である。
【０２２４】
なお、第２実施例では、図４７（Ａ）に示されるように分散情報管理システム２Ｃに属する各分散情報管理装置１２ｉ（ｉは、１〜ｎのうちの任意整数）は、必ず、分散パラメータセットφ（ｉ）と秘密分散情報Ｋｅ（ｉ）の双方を保管しているが、これに限定されるものではない。上記第２の変形例の場合と同様に、図４７（Ｂ）に示されるように、分散情報管理システム２Ｃに属する全ての分散情報管理装置１２１〜１２ｎのうち、ｍ個の分散情報管理装置１２１〜１２ｍは、分散パラメータセットφ（１）〜φ（ｍ）と秘密分散情報Ｋｅ（１）〜Ｋｅ（ｍ）の双方を有するが、残りの分散情報管理装置１２ｍ＋１〜１２ｎは、鍵分散情報および分散パラメータセットを保管せずに主秘密分散情報Ｋｍ（ｍ＋１）〜Ｋｍ（ｎ）のみを保管してもよい。この場合、鍵分散情報および分散パラメータセットを保管しない分散情報管理装置１２ｍ＋１〜１２ｎと、鍵分散情報および分散パラメータセットを保管する分散情報管理装置１２１〜１２ｍとが混在することになる。分散情報管理装置１２ｍ＋１〜１２ｎでは、鍵分散情報および分散パラメータセットが保管されないので、データ保管量や処理量が少なくなる。
【０２２５】
また、優先度あるいは重要度に応じて、分散情報管理装置１２１〜１２ｎを区分して有効利用することが可能である。たとえば、図４８に示されるように、高い演算能力あるいは高い秘密保持能力を持つ分散情報管理装置１２１〜１２ｍには、分散パラメータセットφ（１）〜φ（ｍ）と秘密分散情報Ｋｅ（１）〜Ｋｅ（ｍ）の双方を保管させ、一方、低い演算能力あるいは低い秘密保持能力を持つ分散情報管理装置１２ｍ＋１〜１２ｎには、鍵分散情報を保管させずに主秘密分散情報Ｋｍ（ｍ＋１）〜Ｋｍ（ｎ）および分散パラメータセットφ（ｍ＋１）〜φ（ｎ）を保管させることが可能である。
【０２２６】
上記の通り、本発明の第１実施例、第２実施例および各種変形例に係る秘密情報管理システムついて説明した。このような秘密情報管理システムは、秘密情報Ｓｔを分散符号化して保管し管理することを必要とする技術分野であれば、通信系あるいは情報蓄積系を問わずに汎用的に利用できるシステムである。たとえば、ホログラフィックメモリのように多重記録が可能な記録媒体において秘密分散情報Ｋ（１）〜Ｋ（ｎ）あるいは秘密分散情報Ｋｅ（１）〜Ｋｅ（ｎ）を保管することも可能である。
【０２２７】
本出願は特願２００７−２０３０６３（出願日２００７年８月３日）を基礎としており、上記特許出願の開示内容は全て本出願に組込まれたものとする。
【０２２８】
【非特許文献１】Adi Shamir, "How to share a secret,”Communications of the ACM 22, pp. 612-613, 1979.
【非特許文献２】Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl, "Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems," Proc. 9th ACM Conference on Computer and Communications Security, pp. 88-97, 2002.
【非特許文献３】Bartosz Przydatek and Reto Strobl, "Asynchronous Proactive Cryptosystems Without Agreement (extended abstract)," Advances in Cryptology - ASIACRYPT '04, Lecture Notes in Computer Science, Springer Verlag, vol. 3329, pp. 152-169, 2004.
【非特許文献４】Hugo Krawczyk, "Secret Sharing Made Short," Advances in Cryptology - CRYPTO '93, Lecture Notes in Computer Science, Springer Verlag, vol. 773, pp. 136-146, 1993
【非特許文献５】Hugo Krawczyk, "Distributed Fingerprints and Secure Information Dispersal," Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, pp. 207-218, 1993
【特許文献１】特開２００３−３４８０６５号公報
【特許文献２】特開２００５−２５０８６６号公報
【図１】
2009020078.tif 000051
【図２】
2009020078.tif 000052
【図３】
2009020078.tif 000053
【図４】
2009020078.tif 000054
【図５】
2009020078.tif 000055
【図６】
2009020078.tif 000056
【図７】
2009020078.tif 000057
【図８】
2009020078.tif 000058
【図９】
2009020078.tif 000059
【図１０】
2009020078.tif 000060
【図１１】
2009020078.tif 000061
【図１２】
2009020078.tif 000062
【図１３】
2009020078.tif 000063
【図１４】
2009020078.tif 000064
【図１５】
2009020078.tif 000065
【図１６】
2009020078.tif 000066
【図１７】
2009020078.tif 000067
【図１８】
2009020078.tif 000068
【図１９】
2009020078.tif 000069
【図２０】
2009020078.tif 000070
【図２１】
2009020078.tif 000071
【図２２】
2009020078.tif 000072
【図２３】
2009020078.tif 000073
【図２４】
2009020078.tif 000074
【図２５】
2009020078.tif 000075
【図２６】
2009020078.tif 000076
【図２７】
2009020078.tif 000077
【図２８】
2009020078.tif 000078
【図２９】
2009020078.tif 000079
【図３０】
2009020078.tif 000080
【図３１】
2009020078.tif 000081
【図３２】
2009020078.tif 000082
【図３３】
2009020078.tif 000083
【図３４】
2009020078.tif 000084
【図３５】
2009020078.tif 000085
【図３６】
2009020078.tif 000086
【図３７】
2009020078.tif 000087
【図３８】
2009020078.tif 000088
【図３９】
2009020078.tif 000089
【図４０】
2009020078.tif 000090
【図４１】
2009020078.tif 000091
【図４２】
2009020078.tif 000092
【図４３】
2009020078.tif 000093
【図４４】
2009020078.tif 000094
【図４５】
2009020078.tif 000095
【図４６】
2009020078.tif 000096
【図４７】
2009020078.tif 000097
【図４８】
2009020078.tif 000098
【手続補正書】
【提出日】平成21年6月2日(2009.6.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２４
【補正方法】変更
【補正の内容】
【請求項２４】
請求項２０から２３のうちのいずれか１項に記載の分散情報管理システムであって、前記ｍ番目の分散情報管理装置は、前記新主分散パラメータを分散符号化することにより複数の新副分散パラメータを生成し、前記新副分散パラメータのうちのｊ番目の新副分散パラメータを前記分散情報管理システムに属するｊ番目の分散情報管理装置（ｊは、ｍを除く１〜ｎのうちの任意整数）の情報保管部に供給する第２パラメータ分散部をさらに有し、
前記ｊ番目の分散情報管理装置の情報保管部に保管される副分散パラメータは、前記第２パラメータ分散部から供給された新副分散パラメータで置換されることにより更新されることを特徴とする分散情報管理システム。
【国際調査報告】
2009020078.tif 000099
2009020078.tif 000100
2009020078.tif 000101
2009020078.tif 000102