JP4305049B2 - 秘密分散方法、秘密分散システム、及び分散演算装置 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、秘密とする情報を分散して管理するために、その秘密とする情報を分散する秘密分散方法、秘密分散システム、及び分散演算装置に関し、特に、暗号化や認証における秘密鍵や認証情報を分散して管理するために、それら秘密鍵や認証情報を分散する秘密分散方法、秘密分散システム、及び分散演算装置に関するものである。
【０００２】
【従来の技術】
情報の秘匿のための暗号化に用いる秘密鍵や認証を行うための秘密情報など、重要な秘密情報を保管する場合、その秘密情報の紛失や破壊の心配と、その秘密情報の盗難の心配がある。秘密情報の紛失、破壊により失ってしまうことへの対策としては、その秘密情報のコピーを作成し保管することが考えられるが、秘密情報のコピーが増えることにより、その秘密情報の盗難の危険性が増してしまう。この問題を解決する方法として、秘密分散法がある。
【０００３】
秘密分散法の一つに、Ｓｈａｍｉｒ法（シャミア法）と呼ばれる（ｋ，ｎ）しきい値秘密分散法がある（例えば、非特許文献１参照）。（ｋ，ｎ）しきい値秘密分散法においては、秘密情報をｎ（ｎは２以上の整数）個の分散情報に符号化し、ｋ（ｋはｎ以下の整数）個以上の分散情報が集まれば、もとの秘密情報を復元することができるが、ｋ−１個以下の分散情報を集めても、もとの秘密情報を全く知ることができないという性質を、多項式補間を用いることにより実現している。また、他の秘密分散法として、よりシンプルな加算秘密分散法がある。以下に、Ｓｈａｍｉｒの（ｋ，ｎ）しきい値秘密分散法、及び、加算秘密分散法について説明する。
【０００４】
［Ｓｈａｍｉｒの（ｋ，ｎ）しきい値秘密分散法の説明］
Ｓｈａｍｉｒの（ｋ，ｎ）しきい値秘密分散法においては、具体的には、次式（１）に示されるようなｋ−１次多項式ｆ（ｘ）を用いてもとの秘密情報を分散する。
ｆ（ｘ）＝Ｓ＋Ｒ_１ｘ＋Ｒ_２ｘ^２＋…＋Ｒ_ｋ−１ｘ^ｋ−１ …（１）
ここで、Ｓは、もとの秘密情報であり、Ｒ_１，Ｒ_２，…，Ｒ_ｋ−１は、分配者が決める乱数である。
【０００５】
分散情報が配布されるｎ人の各メンバにメンバＩＤとして、ｍ_１，ｍ_２，…，ｍ_ｎが付与されている場合に、メンバＩＤ ｍ_ｊ（ｊ＝１，２，…，ｎ）に対する分散情報Ｘｍ_ｊは、上記式（１）を用いて、次式（２）のように計算できる。
Ｘｍ_ｊ
＝ｆ（ｍ_ｊ）
＝Ｓ＋Ｒ_１ｍ_ｊ＋Ｒ_２（ｍ_ｊ）^２＋…＋Ｒ_ｋ−１（ｍ_ｊ）^ｋ−１ …（２）
【０００６】
図２は、（ｋ，ｎ）しきい値秘密分散法に基づく秘密分散を実施する秘密分散計算部１０１の動作を説明するための図である。図１に示されるように、秘密分散計算部１０１は、もとの秘密情報Ｓ及びこの秘密情報の分散情報が配布されるメンバ全員のメンバＩＤ ｍ_ｊ（ｊ＝１，２，…，ｎ）を受け取り、もとの秘密情報Ｓに基づいて上記式（１）の多項式ｆ（ｘ）を生成し、その多項式ｆ（ｘ）及びメンバＩＤ ｍ_ｊに基づいて、各メンバＩＤ ｍ_ｊに対応する分散情報Ｘｍ_ｊを、上記式（２）を用いて生成して出力する。出力した各分散情報Ｘｍ_ｊはそれぞれ、対応するメンバＩＤを持つメンバに秘密裏に配布する。
【０００７】
各メンバに配布した分散情報からもとの秘密情報Ｓを再構成する際には、分散情報が分配されたｎ人のメンバのうちｔ人（ｋ≦ｔ≦ｎ）のメンバを集め、集められたｔ人のメンバのメンバＩＤ ｍ′_ｊ（ｊ＝１，２，…，ｔ）と分散情報Ｘｍ′_ｊ（ｊ＝１，２，…，ｔ）を持ち寄り、次式（３）及び（４）を用いて、もとの秘密情報Ｓを計算する。
【数１】

式（３）は、式（４）で計算されるメンバＩＤから求めた係数ｒｍ′_ｊと分散情報Ｘｍ′_ｊを乗算したものを、集まったメンバｔ人すべてに関して加算している。式（４）は、分散情報Ｘｍ′_ｊに対応するメンバＩＤ ｍ′_ｊ以外のメンバＩＤ ｍ′_ｉ（ｉ＝１，２，…，ｔでｉ≠ｊとなるもの）についての値ｍ′_ｉ／（ｍ′_ｉ−ｍ′_ｊ）をすべて乗算している。
【０００８】
［加算秘密分散法の説明］
次に、加算秘密分散法について説明する。加算秘密分散法は、複数のメンバからなるあるグループで、もとの秘密情報Ｓを単純な加減算により秘密分散する秘密分散法である。図３は、加算秘密分散法に基づく秘密分散を実施する秘密分散計算部２０１の動作を説明するための図である。秘密分散計算部２０１は、次のような計算を行う。秘密分散計算部２０１へ入力されるもとの秘密情報をＳとし、分散情報を配布するメンバがｎ人であるとすると、秘密分散計算部２０１は、まず、乱数をｎ−１個選ぶ。それらの乱数Ｘ_１，Ｘ_２，…，Ｘ_ｎ−１から、次式（５）を満たすＸ_ｎを求める。
Ｘ_ｎ＝Ｓ−（Ｘ_１＋Ｘ_２＋…＋Ｘ_ｎ−１） …（５）
【０００９】
秘密分散計算部２０１は、式（５）により得られた値Ｘ_１，Ｘ_２，…，Ｘ_ｎを出力し、各メンバに重複しないように配布する。値Ｘ_１，Ｘ_２，…，Ｘ_ｎのうち、いくつかは等しい値が在ってもよい。このような加算秘密分散法においては、メンバ全員（すなわちｎ人）が集まらない限り、もとの秘密情報Ｓを再構成することができない。もとの秘密情報Ｓを再構成するときには、次式（６）を計算する。
Ｓ＝Ｘ_１＋Ｘ_２＋…＋Ｘ_ｎ …（６）
【００１０】
［マルチパーティ・プロトコルの説明］
前述の秘密分散法とは別に、マルチパーティ・プロトコルという技術がある。ここで、マルチパーティ・プロトコルとは、ある関数への入力値を公開せずに、その関数の計算を集まったメンバで協力して行う方式であり、分散計算とも呼ばれる（例えば、非特許文献１参照）。ここでは、有限体要素の分散計算（加算と定数乗算の計算）について簡単に説明する。
【００１１】
マルチパーティ・プロトコルを実行するメンバがｎ人いるとする。そのメンバそれぞれが、メンバＩＤとしてｍ_ｊ（ｊ＝１，２，…，ｎ）と、そのメンバ固有の秘密情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）を保有しており、次式（７）のような関数値Ｙをマルチパーティ・プロトコルの分散計算で計算したいとする。
Ｙ＝Ｆ（Ｘｍ_１，Ｘｍ_２，…，Ｘｍ_ｎ） …（７）
ここで、各メンバのメンバＩＤであるｍ_ｊ及び秘密情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）は、有限体ＧＦ（ｑ）（ｑは素数又は素数のべき乗）上の値であるものとする。また、上記式（７）の関数Ｆにおける演算は、有限体ＧＦ（ｑ）上の演算であるものとする。
【００１２】
各メンバ固有の秘密情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ）を、他のメンバに公開しないまま、関数値Ｙを計算するために、マルチパーティ・プロトコルでは、まず、各メンバ固有の秘密情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）を、加算秘密分散法、又は、（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散して部分情報を生成し、他のメンバに配布する。メンバＩＤがｍ_ｊであるメンバの秘密情報が、Ｘｍ_ｊであるとすると、このメンバは、加算秘密分散法を用いる場合、ｎ−１個の乱数Ｒｍ_ｊ，ｐ（ｐ＝１，２，…，ｎで、ｐ≠ｊとなるもの）を生成し、メンバＩＤがｍ_ｐであるメンバにＸｍ_ｊの部分情報Ｘｍ_ｊ，ｐ（ｐ＝１，２，…，ｎで、ｐ≠ｊとなるもの）として、
Ｘｍ_ｊ，ｐ＝Ｒｍ_ｊ，ｐ …（８）
を配布する。
【００１３】
自分自身に対するＸｍ_ｊの部分情報Ｘｍ_ｊ，ｊとしては、次式（９）で算出する。
【数２】

【００１４】
また、メンバＩＤがｍ_ｊであるメンバの秘密情報がＸｍ_ｊであるとし、このメンバが（ｋ，ｎ）しきい値秘密分散法を用いる場合、
ｆｍ_ｊ（ｘ）
＝Ｘｍ_ｊ＋Ｒｍ_ｊ，１ｘ＋Ｒｍ_ｊ，２ｘ^２＋…＋Ｒｍ_{ｊ，ｋ−１}ｘ^ｋ−１…（１０）
なるｋ−１次の多項式（ｋ≦ｎ）を作り（Ｒｍ_ｊ，１、Ｒｍ_ｊ，２、…、Ｒｍ_{ｊ，ｋ−１}は、乱数としてｋ−１個選ぶ）、メンバＩＤがｍ_ｐ（ｐ＝１，２，…，ｎ）であるメンバに対して配布する部分情報Ｘｍ_ｊ，ｐを、式（１０）を用いて次式（１１）のように計算する。
Ｘｍ_ｊ，ｐ＝ｆｍ_ｊ（ｍ_ｐ） …（１１）
なお、部分情報Ｘｍ_ｊ，ｐの配布は、メンバＩＤがｍ_ｐ（ｐ＝１，２，…，ｎ）であるメンバ以外には秘密となるよう、秘密通信路を用いて行う。
【００１５】
このようにすると、各メンバは、他の各メンバの秘密情報の部分情報を持っている状態になる。メンバＩＤがｍ_ｊであるメンバは、他のメンバから配布された部分情報（及び自分自身の秘密情報の部分情報）Ｘｍ_１，ｊ、Ｘｍ_２，ｊ、…、Ｘｍ_ｎ，ｊのｎ個の分散情報を持っていることになる。
【００１６】
まず、マルチパーティ・プロトコルにおける分散加算（足し算計算）を説明する。各メンバは、値Ａ及びＢの部分情報Ａｍ_ｊ及びＢｍ_ｊを既に持っているとする。これは、分散計算の途中結果であってもよいし、上記のような秘密情報の部分情報Ｘｍ_ｐ，ｊであってもよい。マルチパーティ・プロトコルでは、各メンバは、部分情報Ａｍ_ｊとＢｍ_ｊの足し算を行うことで、計算結果Ｃ＝Ａ＋Ｂの分散情報Ｃｍ_ｊ（ｊ＝１，２，…，ｎ）を得ることができる。例えば、メンバＩＤがｍ_ｊであるメンバは、値Ａ及びＢの部分情報として、それぞれＡｍ_ｊ及びＢｍ_ｊを持っているので、次式（１２）のような計算を行い、計算結果Ｃｍ_ｊを得る。
Ｃｍ_ｊ＝Ａｍ_ｊ＋Ｂｍ_ｊ …（１２）
【００１７】
次に、マルチパーティ・プロトコルにおける分散定数乗算（定数の掛け算計算）を説明する。各メンバは、値Ａの部分情報Ａｍ_ｊを既に持っているとし、ある定数をＤとおく。部分情報Ａｍ_ｊは、分散計算の途中結果であってもよいし、上記のような秘密情報の分散情報Ｘｍ_ｐ，ｊであってもよい。マルチパーティ・プロトコルでは、各メンバは、定数Ｄと部分情報Ａｍ_ｊの掛け算を行うことで、計算結果Ｃ＝Ｄ・Ａの分散情報Ｃｍ_ｊ（ｊ＝１，２，…，ｎ）を得ることができる。例えば、メンバＩＤがｍ_ｊであるメンバは、値Ａの部分情報としてＡｍ_ｊを持っているので、次式（１３）のような計算を行い、計算結果Ｃｍ_ｊを得る。
Ｃｍ_ｊ＝Ｄ・Ａｍ_ｊ …（１３）
【００１８】
【非特許文献１】
岡本龍明他著、「現代暗号」（産業図書）、第２１４−２１６ページ及び第２２７−２３６ページ
【非特許文献２】
ドナルド・ビーバー及びシャフィ・ゴールドワッセル、「マルチパーティ・プロトコル・コンピューテーション・ウィズ・フォールティ・マジョリティ」、プロシーディングズ・オブ・エフオーシーエス、第４６８〜４７３ページ、１９８９年（D. Beaver and S. Goldwasser, “Multiparty Computation with Faulty Majority”, Proc. of FOCS (Foundations of Computer Science), pp. 468-473, 1989）
【００１９】
【発明が解決しようとする課題】
しかしながら、上記秘密分散法においては、次のような課題があった。数人のメンバが分散情報Ｘｍ_ｊを既に持っている場合、他の分散情報Ｘｍ_ｐ（ｐ≠ｊ）を算出するためには、もとの秘密情報Ｓと、既にメンバに保有されている分散情報Ｘｍ_ｊを、少なくとも秘密分散を実行する組織（センター等であってもよいし、メンバの１人であってもよい）に公開するか、又は、既にメンバに保有されている分散情報Ｘｍ_ｊを含むすべてのメンバの分散情報を再計算し直す必要があった。より具体的に説明すれば、次の２通りの場合がある。
【００２０】
場合〔１〕は、既にｎ人のメンバに秘密情報Ｓの分散情報Ｘｍ_１，Ｘｍ_２，…，Ｘｍ_ｎが配布されており、ｔ１人の新規メンバが追加され、新規メンバのそれぞれに、分散情報Ｘｍ_ｎ＋１，Ｘｍ_ｎ＋２，…，Ｘｍ_ｎ＋ｔ１を与える場合である。この場合には、既に分散情報を配布されたメンバの分散情報Ｘｍ_１，Ｘｍ_２，…，Ｘｍ_ｎを公開することにより、上記式（１）の多項式を復元し、追加された新規メンバ分の分散情報Ｘｍ_ｎ＋１，Ｘｍ_ｎ＋２，…，Ｘｍ_ｎ＋ｔ１を計算し直すか、追加された新規メンバをも含むすべてのメンバの分散情報を秘密情報Ｓから再計算し直す必要があった。
【００２１】
場合〔２〕は、数人（ｔ３人とする）のメンバがなんらかの分散情報Ｘｍ_ｊを既に持っており、新たな秘密情報Ｓ′を与え、その秘密情報Ｓ′を再構成させるための分散情報として、分散情報Ｘｍ_ｊを含んだｎ個（ｎ＞ｔ３）の分散情報Ｘｍ_ｐを算出する場合である。この場合も、既に保有されている分散情報Ｘｍ_ｊと秘密情報Ｓ′を公開することにより、他の分散情報Ｘｍ_ｐ（ｐ≠ｊ）を算出するか、秘密情報Ｓ′からメンバ全員の分散情報を再計算し直す必要があった。
【００２２】
そこで、本発明は、上記したような従来技術の課題を解決するためになされたものであり、その目的は、既に何人かのメンバが保有している分散情報を秘密にしたまま、既に保有されている分散情報を変更せず、分散情報を未だ保有していないメンバの分散情報を算出することができる秘密分散方法、秘密分散システム、及びこの秘密分散システムを構成する分散演算装置を提供することである。
【００２３】
【課題を解決するための手段】
本発明に係る秘密分散方法は、もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって生成されたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）をそれぞれ保有しているｎ（ｎは正の整数）人の初期メンバの分散演算装置からなるグループに、ｔ（ｔは正の整数）人の新規メンバの分散演算装置が追加された場合に、上記ｎ人の初期メンバの分散演算装置及び上記ｔ人の新規メンバの分散演算装置のうちのｋ（ｋはｎ以下の整数）人以上のメンバの分散演算装置が保有する分散情報から上記もとの秘密情報を再構成することができるように、且つ、上記ｎ人の初期メンバの分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）をそのままにして、上記ｔ人の新規メンバの分散演算装置に保有させるｔ個の分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を算出するシステムにおける秘密分散方法であって、上記初期メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を分散して複数の部分情報を生成し、上記部分情報のそれぞれを上記初期メンバの分散演算装置及び上記新規メンバの分散演算装置のそれぞれに配布する工程と、上記初期メンバの分散演算装置及び上記新規メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する部分情報を用いた分散計算により中間計算結果を生成し、上記新規メンバの分散演算装置のそれぞれに配布する工程と、上記新規メンバの分散演算装置のそれぞれが、受け取った上記中間計算結果を用いて、自身の分散演算装置が保有することになる上記分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を算出する工程とを有するものである。
【００２４】
また、本発明に係る他の秘密分散方法は、ｎ（ｎは正の整数）人のメンバの分散演算装置からなるグループがあり、上記ｎ人のメンバの分散演算装置のうちのｔ（ｔはｎより小さい正の整数）人のメンバの分散演算装置のそれぞれが既に分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有している既保有メンバの分散演算装置であり、残りのｎ−ｔ人のメンバの分散演算装置が分散情報を保有していない未保有メンバの分散演算装置である場合に、上記ｎ人のメンバの分散演算装置のうちのｋ（ｋはｎ以下の整数）人以上のメンバの分散演算装置の保有する分散情報からもとの秘密情報を再構成することができるように、且つ、上記ｔ人の既保有メンバの分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）をそのままにして、上記ｎ−ｔ人の未保有メンバの分散演算装置に保有させるｎ−ｔ個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を算出するシステムにおける秘密分散方法であって、上記既保有メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を分散して複数の第１の部分情報を生成し、上記第１の部分情報のそれぞれを上記メンバの分散演算装置のそれぞれに配布する工程と、上記メンバの分散演算装置に情報を配布できる装置が、上記もとの秘密情報から生成された複数の第２の部分情報のそれぞれを、上記メンバの分散演算装置のそれぞれに配布する工程と、上記メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する第１及び第２の部分情報を用いた分散計算により中間計算結果を生成し、上記未保有メンバの分散演算装置に配布する工程と、上記未保有メンバの分散演算装置が、受け取った上記中間計算結果を用いて、自身の分散演算装置が保有することになる上記分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を算出する工程とを有するものである。
【００２５】
また、本発明に係る分散演算装置は、もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって得られたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）が既に与えられている場合に、上記もとの秘密情報を（ｋ，ｎ＋ｔ）しきい値秘密分散法を用いて秘密分散したような、さらにｔ個の分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置であって、既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）の部分情報を受信する部分情報用受信部と、分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）の部分情報を算出する部分情報計算部と、上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）の部分情報を送信する部分情報用送信部とを有し、上記部分情報計算部は、既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を保持する分散演算装置を特定するメンバＩＤ、及び、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤより計算される係数を算出し、上記算出された係数と、上記部分情報用受信部で受信した、対応する分散情報Ｘ_ｙの部分情報とを掛け合わせ、上記掛け合わせによって得られた値を足し合わせることによって分散情報Ｘ_ｙの部分情報を算出するものである。
【００２６】
また、本発明に係る他の分散演算装置は、すべてを加算するともとの秘密情報を再構成できる加算秘密分散法を用いて秘密分散されたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）のうち、ｔ個（ｔ＜ｎ）の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）が既に与えられている場合に、残りの分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置であって、既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、もとの秘密情報の部分情報を受信する部分情報用受信部と、分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を算出する部分情報計算部と、上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を送信する部分情報用送信部とを有し、上記部分情報計算部は、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｔ−１個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ−１）の部分情報を算出するために、乱数を生成してそれを分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ−１）とし、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｎ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、上記算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ−１）の部分情報を足し合わせ、上記部分情報用受信部で受信したもとの秘密情報の部分情報から、上記足し合わせによって算出した値を引き算することによって上記部分情報を算出するものである。
【００２７】
また、本発明に係る他の分散演算装置は、もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって得られたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）のうち、ｔ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）が既に与えられている場合に、ｎ≧ｋ＞ｔなる関係があって、残りの分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置であって、既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、上記もとの秘密情報の部分情報を受信する部分情報用受信部と、分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を算出する部分情報計算部と、上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を送信する部分情報用送信部と
を有し、上記部分情報計算部は、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｋ−ｔ−１個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を算出するために、乱数を生成してそれを分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）とし、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有する分散演算装置を特定するメンバＩＤと、上記算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤと、から計算される係数を算出し、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記部分情報用受信部で受信したもとの秘密情報の部分情報と、上記算出された係数とを掛け合わせて第１の乗算値を算出し、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記掛け合わせた係数と、上記部分情報用受信部で受信した、対応する分散情報Ｘ_ｙの部分情報とを掛け合わせて第２の乗算値を算出し、
分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記第１の乗算値と上記第２の乗算値を足し合わせるものである。
【００２８】
また、本発明に係る他の分散演算装置は、もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって得られたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）のうち、ｔ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）が既に与えられている場合に、ｎ≧ｋ＞ｔなる関係があって、残りの分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置であって、既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、上記もとの秘密情報の部分情報を受信する部分情報用受信部と、分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を算出する部分情報計算部と、上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を送信する部分情報用送信部とを有し、上記部分情報計算部は、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｋ−ｔ−１個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を算出するために、乱数を生成してそれを分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）とし、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有する分散演算装置を特定するメンバＩＤと、上記算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤと、から計算される係数を算出し、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記部分情報用受信部で受信したもとの秘密情報の部分情報と、上記算出された係数とを掛け合わせて第１の乗算値を算出し、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記係数と、上記部分情報用受信部で受信した、対応する分散情報Ｘ_ｙの部分情報とを掛け合わせて第２の乗算値を算出し、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記第１の乗算値と上記第２の乗算値を足し合わせ、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ個の分散情報Ｘ_ｙ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有する分散演算装置を特定するメンバＩＤと、上算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、上記加算により算出した分散情報Ｘ_ｉ（ｉ＝ｋ）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤと、から計算される係数を算出し、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ個の分散情報Ｘ_ｙ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）の部分情報を算出するために、上記係数と、上記受信部で受信した、対応する分散情報Ｘ_ｉの部分情報とを掛け合わせて第３の乗算値を算出し、分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ個の分散情報Ｘ_ｙ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）の部分情報を算出するために、上記第３の乗算値を足し合わせるものである。
【００２９】
【発明の実施の形態】
以下の説明においては、数人のメンバが分散情報Ｘｍ_ｊを既に持っている場合に、その分散情報Ｘｍ_ｊ、必要ならば、秘密情報Ｓ又はＳ′を入力とするマルチパーティ・プロトコルによる分散計算を行うことにより、固定となっている（すなわち、変更されずそのまま保有され続ける）分散情報Ｘｍ_ｊや、秘密情報Ｓ又はＳ′を秘密にしたまま、秘密情報の他の分散情報Ｘｍ_ｐ（ｐ≠ｊ）を、メンバの分散演算装置が協力して求める場合を説明する。第１の実施形態は、従来技術の説明において場合〔１〕として記載した課題を解決する実施形態であり、（ｋ，ｎ）しきい値秘密分散法を用いて、分散情報を既に保有している当初からのメンバの分散情報をそのまま変更せずに、追加される新規メンバに保有させる分散情報を求める。また、第２の実施形態は、従来技術の説明において場合〔２〕として記載した課題を解決する実施形態であり、加算秘密分散法、又は、（ｋ，ｎ）しきい値秘密分散法を用いて、分散情報を既に保有しているメンバの分散情報をそのまま変更せずに、分散情報を未だ保有していないメンバに保有させる分散情報を求める。
【００３０】
≪第１の実施形態≫
第１の実施形態においては、既にｎ人のメンバ（初期メンバ）に、秘密情報Ｓを（ｋ，ｎ）しきい値秘密分散法で分散した分散情報Ｘｍ_１，Ｘｍ_２，…，Ｘｍ_ｎが配布されており、新たに追加されたｔ１人の新規メンバに分散情報Ｘｍ_ｎ＋ｙ（ｙ＝１，２，…，ｔ１）を与える場合を考える。第１の実施形態においては、既に配布されている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）を入力とするマルチパーティ・プロトコルによる分散計算を行うことにより、固定となっている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）、及び、もとの秘密情報Ｓを公開せずに、秘密情報Ｓの新規メンバに保有させる分散情報Ｘｍ_ｎ＋ｙ（ｙ＝１，２，…，ｔ１）を、各メンバの分散演算装置が協力して求める。
【００３１】
第１の実施形態においては、まず前提として、複数（ｎ人）のメンバからなるあるグループで、秘密情報Ｓを（ｋ，ｎ）しきい値秘密分散法（ｋ≦ｎ）を用いて分散し、その分散情報が秘密裏に既に配布されている状態を考える。秘密情報Ｓを分散させるときに用いたメンバＩＤをｍ_１，ｍ_２，…，ｍ_ｎとする。メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバに配布した分散情報をＸｍ_ｊ（ｊ＝１，２，…，ｎ）とする。そして、新たにグループに参加するｔ１人の新規メンバ（メンバＩＤをｍ_ｎ＋１，ｍ_ｎ＋２，…，ｍ_ｎ＋ｔ１とする）に保有させる秘密情報Ｓの分散情報Ｘｍ_ｊ（ｊ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ１）を生成して該当メンバに配布する場合を考える。
【００３２】
また、メンバのうち、どの２人のメンバ間にも、その２人のメンバ以外には通信内容を秘密とすることができる秘密通信路が確立されているものとする。図４は、第１の実施形態において各メンバ間の通信に用いる秘密通信路を示す図である。図４において、四角形で示されるブロックは集まったメンバ（分散演算装置）を示し、ｍ_１，ｍ_２，…，ｍ_ｊ，…，ｍ_ｎは、メンバＩＤを示し、両方向の矢印は、それぞれ対応するメンバ以外には通信内容を秘密とする秘密通信路を示している。
【００３３】
次に、図５を用いて、第１の実施形態の概要を簡単に説明する。図５は、第１の実施形態に係る秘密分散方法を実施する秘密分散システムの構成を示す図である。図５においては、メンバ（分散演算装置）の人数は４人とし、そのうち３人のメンバＰ_Ａ，Ｐ_Ｂ，Ｐ_Ｃは、もとの秘密情報Ｓを（２，３）又は（３，３）しきい値秘密分散法で分散させた分散情報Ａ，Ｂ，Ｃをそれぞれ持っているとし、新規メンバＰ_Ｄの分散情報Ｄを、分散情報Ａ，Ｂ，Ｃや、もとの秘密情報Ｓを公開しないで新たに計算したいとする。このとき、分散情報を既に持つメンバＰ_Ａ，Ｐ_Ｂ，Ｐ_Ｃが、各自持っている分散情報Ａ，Ｂ，Ｃをさらに秘密分散して部分情報を生成し（図５の処理▲１▼であり、分散情報Ａから部分情報Ａ_１，Ａ_２，Ａ_３，Ａ_４を生成し、分散情報Ｂから部分情報Ｂ_１，Ｂ_２，Ｂ_３，Ｂ_４を生成し、分散情報Ｃから部分情報Ｃ_１，Ｃ_２，Ｃ_３，Ｃ_４を生成する。）、それらを他のメンバに配布する（図５の処理▲２▼）。各メンバＰ_Ａ，Ｐ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄは、受け取った分散情報の部分情報をもとに、分散計算を行う（図５の処理▲３▼）。各メンバＰ_Ａ，Ｐ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄは、その分散計算の結果を新規メンバＰ_Ｄへ送信し（図５の処理▲４▼）、メンバＰ_Ｄは、受け取った計算結果に基づいて分散情報Ｄを生成する（図５の処理▲５▼）。この結果、メンバＰ_Ａ，Ｐ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄは、それぞれ、もとの秘密情報Ｓを（２，４）又は（３，４）しきい値秘密分散法で分散した分散情報Ａ，Ｂ，Ｃ，Ｄを持つことになる。
【００３４】
図６は、第１の実施形態（又は後述する第２の実施形態）に係る秘密分散システムを構成する分散演算装置及び秘密通信路を示す図である。分散情報を計算するメンバは、それぞれ、分散計算で分散情報を計算するために必要な手段を持つ分散演算装置３０１を持っており、図６の秘密分散システムは、複数の分散演算装置３０１を有している。各メンバの分散演算装置３０１は、それぞれ他のメンバの分散演算装置３０１とは、図４で説明した秘密通信路３０２で接続されている。各メンバの分散演算装置３０１における処理は、各メンバがそれぞれ他のメンバにはその処理の内容が分からないように行う。
【００３５】
次に、図１を用いて分散演算装置３０１の構成を説明する。分散演算装置３０１は、秘密分散法を実行して分散情報から部分情報を生成し配布するＳＳＳ部（秘密分散法実行部）４０１、部分情報に基づいて分散計算を行い、分散計算結果を配布する分散計算部４０２、及び、分散計算結果に基づいて分散情報を生成するＲＳＳＳ部（秘密再構成法実行部）４０３のうち、少なくともいずれか１つを有する。例えば、図５の例を取り上げて説明すると、ＳＳＳ部４０１は、図５における処理▲１▼及び処理▲２▼、すなわち、分散情報を分散して部分情報を生成し配布する処理を行う。また、分散計算部４０２は、図５における処理▲３▼及び処理▲４▼、すなわち、分散計算を行って、その結果を分散情報が必要なメンバに送信する処理を行う。また、ＲＳＳＳ部４０３は、図５における処理▲５▼、すなわち、他のメンバから分散計算結果を受信して分散情報を生成する処理を行う。したがって、図５においてメンバＰ_Ａ，Ｐ_Ｂ，Ｐ_Ｃとして示される分散演算装置３０１は、少なくとも、ＳＳＳ部４０１と、分散計算部４０２とを有していればよい（図７）。これに対し、図５においてメンバＰ_Ｄとして示される分散演算装置３０１は、少なくとも、分散計算部４０２と、ＲＳＳＳ部４０３とを有していればよい（図８）。特に、計算資源が限られる分散演算装置３０１は、ＳＳＳ部４０１、分散計算部４０２、又は、ＲＳＳＳ部４０３のうち、いずれか１つのみしか持たない場合もありうる（図９、図１０、図１１）。
【００３６】
ＳＳＳ部４０１は、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバに既に配布されている秘密情報Ｓの分散情報Ｘｍ_ｊを分散して部分情報を求め、各メンバへの配布の処理を行う。ＳＳＳ部４０１は、秘密分散部４０１１と、送信部４０１２とからなる。既に分散情報を保有している、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバの分散演算演算部３０１は、ＳＳＳ部４０１を持つ。
【００３７】
ＳＳＳ部４０１の秘密分散部４０１１へは、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバに既に配布されている秘密情報Ｓの分散情報Ｘｍ_ｊが入力される。秘密分散システムにおける分散演算装置３０１のうち、分散計算部４０２を持つものがｔ２個存在するとし、それらのメンバＩＤをｍ′_１，ｍ′_２，…，ｍ′_ｔ２とする。秘密分散部４０１１は、入力された分散情報Ｘｍ_ｊを（ｋ′，ｔ２）しきい値秘密分散法（ｋ′≦ｔ２）、又は、加算秘密分散法を用いて分散して、ｔ２個の部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ２）を生成し、それら部分情報Ｘｍ′_ｊ，ｐを送信部４０１２へ出力する。
【００３８】
ＳＳＳ部４０１の送信部４０１２は入力された分散情報を他のメンバと通信する秘密通信路３０２を経て、分散計算部４０２を持つ分散演算装置３０１（メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ２）であるメンバの分散演算装置３０１）へ配布する。分散演算装置３０１がＳＳＳ部４０１と分散計算部４０２を有する場合（図１又は図７の場合）には、秘密分散部４０１１は、自分自身への部分情報Ｘｍ′_ｊ，ｐ（ｍ_ｊ＝ｍ′_ｐ）を、（後述する）分散計算部４０２の部分情報計算部４０２１へ出力する。
【００３９】
分散計算部４０２は、他の分散演算装置３０１から部分情報を受け取って、計算したい分散情報Ｘｍ_ｎ＋ｙ（メンバＩＤがｍ_ｎ＋ｙ（ｙ＝１，２，…，ｔ１）の分散情報）の部分情報Ｘｍ′_{ｎ＋ｙ，ｐ}（ｐ＝１，２，…，ｔ２）を計算する部分である。分散計算部４０２は、部分情報計算部４０２１及び送受信部４０２２からなる。メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ２）であるメンバのｔ２個の分散演算装置３０１が分散計算部４０２を持つとする。
【００４０】
分散計算部４０２の送受信部４０２２（メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ２））は、ＳＳＳ部４０１を持つ分散演算装置３０１（メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ））からの部分情報Ｘｍ′_ｊ，ｐを受信して、部分情報計算部４０２１へ出力し、また、部分情報計算部４０２１からの出力（計算結果）を受け取って、他の分散演算装置３０１へ送信する。
【００４１】
分散計算部４０２の部分情報計算部４０２１（メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ２））は、送受信部４０２２からの部分情報を受け取る。また、分散演算装置３０１がＳＳＳ部４０１と分散計算部４０２とを有する場合（図１又は図７の場合）には、秘密分散部４０１１から、自分自身への部分情報Ｘｍ′_ｊ，ｐ（ｍ_ｊ＝ｍ′_ｐ）も受け取る。部分情報計算部４０２１は、受け取った情報から、次式（１４）及び（１５）を用いた計算を行って、ｔ１個の部分情報Ｘｍ′_{ｎ＋ｙ，ｐ}（ｙ＝１，２，…，ｔ１）を算出する。
【数３】

【００４２】
ＲＳＳＳ部４０３は、分散計算部４０２を持つ分散演算装置３０１から部分情報の計算結果を受信して、それら部分情報から求めたい分散情報を算出する処理を行う部分である。ＲＳＳＳ部４０３は、秘密再構成部４０３１及び受信部４０３２からなる。求めたい分散情報に該当するメンバ（すなわち、メンバＩＤがｍ_ｊ（ｊ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ１）であるメンバ）の分散演算装置３０１は、このＲＳＳＳ部４０３を持つ。
【００４３】
ＲＳＳＳ部４０３の受信部４０３２（メンバＩＤがｍ_ｊ（ｊ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ１））は、分散計算部４０２を持つ分散演算装置３０１から、計算結果である、分散情報Ｘｍ_ｊの部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ２）を受信して、その受信情報を秘密再構成部４０３１へ出力する。
【００４４】
ＲＳＳＳ部４０３の秘密再構成部４０３１（メンバＩＤがｍ_ｊ（ｊ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ１））は、受信部４０３２から部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ２）を受け取る。また、分散演算装置３０１が分散計算部４０２とＲＳＳＳ部４０３とを有する場合（図１又は図８の場合）には、部分情報計算部４０２１から自分自身への部分情報Ｘｍ′_ｊ，ｐ（ｍ_ｊ＝ｍ′_ｐ）を受け取る。それら受け取った部分情報を再構成することにより、分散情報Ｘｍ_ｊを得る。この再構成は、ＳＳＳ部４０１を持つ分散演算装置３０１の秘密分散部４０１１での秘密分散法が、（ｋ′，ｔ２）しきい値秘密分散法（ｋ′≦ｔ２）を用いたならば、しきい値秘密分散法の再構成方法、加算秘密分散法を用いたならば加算秘密分散法の再構成方法で行う。
【００４５】
図１２は、第１の実施形態の秘密分散システムの動作を示すフローチャートである。複数（ｎ人の）メンバからなるあるグループで、秘密情報Ｓを（ｋ，ｎ）しきい値秘密分散法（ｋ≦ｎ）を用いて分散し、その分散情報が秘密裏に既に配布されている状態を考え、追加されたｔ１人の新規メンバ（メンバＩＤをｍ_ｎ＋１，ｍ_ｎ＋２，…，ｍ_ｎ＋ｔ１とする）の秘密情報Ｓの分散情報Ｘｍ_ｊ（ｊ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ１）を生成して該当メンバに配布する場合を考える。秘密情報Ｓを分散させるときに用いたメンバＩＤをｍ_１，ｍ_２，…，ｍ_ｎとし、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバに配布した分散情報をＸｍ_ｊ（ｊ＝１，２，…，ｎ）とする。
【００４６】
まず、分散情報を既に持つ、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバの分散演算装置３０１は、自身の持つ分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）を、しきい値秘密分散法、又は、加算秘密分散法で分散して部分情報を生成し、分散計算部４０２を持つメンバ（メンバＩＤをｍ′_ｐ（ｐ＝１，２，…，ｔ２）とする）の分散演算装置３０１へ配布する（ステップＳ５０１）。ステップＳ５０１は、ＳＳＳ部４０１における動作を示しており、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバの分散演算装置３０１は、自身の持つ分散情報Ｘｍ_ｊから部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ２）を生成し、その部分情報をメンバＩＤがｍ′_ｐであるメンバの分散演算装置３０１へ配布する。
【００４７】
次に、分散計算部４０２を持つメンバ（メンバＩＤをｍ′_ｐ（ｐ＝１，２，…，ｔ２）とする）の分散演算装置３０１は、配布された部分情報Ｘｍ′_ｊ，ｐ（ｊ＝１，２，…，ｎ）を用いて演算を施し、新たに求めたい分散情報の部分情報を求め、ＲＳＳＳ部４０３を持つメンバ（メンバＩＤがｍ_ｎ＋ｙ（ｙ＝１，２，…，ｔ１））の分散演算装置３０１へ送信する（ステップＳ５０２）。ステップＳ５０２は、分散計算部４０２における動作を示しており、メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ２）であるメンバの分散演算装置３０１は、配布される部分情報Ｘｍ′_ｊ，ｐ（ｊ＝１，２，…，ｎ）から、式（１４）及び（１５）を用いて新たに求めたい分散情報の部分情報Ｘｍ′_{ｎ＋ｙ，ｐ}（ｙ＝１，２，…，ｔ１）を算出し、メンバＩＤがｍ_ｎ＋ｙであるメンバの分散演算装置３０１へ送信する。
【００４８】
次に、ＲＳＳＳ部４０３を持つメンバ（メンバＩＤがｍ_ｎ＋ｙ（ｙ＝１，２，…，ｔ１））の分散演算装置３０１は、受け取ったｔ２個の部分情報Ｘｍ′_{ｎ＋ｙ，ｐ}（ｐ＝１，２，…，ｔ２）から、しきい値秘密分散法、又は、加算秘密分散法の再構成方法を用いて（ただし、ステップＳ５０１と同じ秘密分散法の再構成方法を用いる）、分散情報Ｘｍ_ｎ＋ｙを再構成する（ステップＳ５０３）。ステップＳ５０３は、ＲＳＳＳ部４０３における動作を示している。
【００４９】
この結果、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ＋ｔ１）であるメンバは、それぞれ、もとの秘密情報Ｓを（ｋ，ｎ＋ｔ１）しきい値秘密分散法で分散した分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ＋ｔ１）を持つことになり、さらに、秘密分散する前に既に配布されていた分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）はそのまま変更せずに再利用することができている。
【００５０】
以上説明したように、第１の実施形態に係る秘密分散方法又は秘密分散システムを用いれば、複数のメンバからなるあるグループで、秘密情報Ｓを（ｋ，ｎ）しきい値秘密分散法（ｋ≦ｎ）を用いて分散し、その分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）が秘密裏に既に配布されている状態を考え、ｔ１人の新規メンバ（メンバＩＤをｍ_ｎ＋１，ｍ_ｎ＋２，…，ｍ_ｎ＋ｔ１とする）の秘密情報Ｓの分散情報Ｘｍ_ｊ（ｊ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ１）を新たに生成して該当メンバに配布する場合に、秘密情報Ｓ、及び、既に配布されている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）を公開することなく、新たに追加するｔ１個の分散情報Ｘｍ_ｊ（ｊ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ１）を生成して該当メンバに配布することができる。このとき、既に配布されていた分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｎ）は、そのまま有効に利用でき、既に配布されていた分散情報の再計算も必要としない。
【００５１】
また、第１の実施形態に係る秘密分散方法又は秘密分散システムを用いれば、秘密分散を行うためのセンターを必要としないという利点もある。秘密分散を行うためのセンターがある場合、メンバの保有する分散情報をすべてセンターが把握してしまうため、センターがメンバになりすます不正（「分散情報Ｘｍ_ｊを持っているので、私はメンバＩＤがｍ_ｊのメンバです」といった「なりすまし」のような不正）があり得るが、第１の実施形態によれば、このような不正を防ぐことができる。
【００５２】
≪第２の実施形態≫
第２の実施形態において、ｔ３人のメンバがなんらかの分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を既に持っており、新たな秘密情報Ｓ′を与え、その秘密情報Ｓ′を再構成させるための分散情報として分散情報Ｘｍ_ｊを含むｎ個（ｎ＞ｔ３）の分散情報Ｘｍ_ｐを算出する場合を考える。すなわち、ｎ（ｎは正の整数）人のメンバからなるグループがあり、これらｎ人のメンバのうちのｔ３（ｔ３はｎより小さい正の整数）人のメンバのそれぞれが既に分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を保有している既保有メンバであり、残りのｎ−ｔ３人のメンバが分散情報を保有していない未保有メンバである場合に、上記ｎ人のメンバのうちのｋ（ｋはｎ以下の整数）人以上のメンバの保有する分散情報からもとの秘密情報を再構成することができるように、且つ、ｔ３人の既保有メンバが保有する分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）をそのままにして、ｎ−ｔ３人の未保有メンバに保有させるｎ−ｔ３個の分散情報Ｘｍ_ｙ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）を算出する場合を考える。このときの秘密情報Ｓ′の秘密分散法としては、加算秘密分散法、又は、（ｋ，ｎ）しきい値秘密分散法の場合を考え、既に保有されていた分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）と、算出する他のｎ−ｔ３個の分散情報Ｘｍ_ｙ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）とから、秘密情報Ｓ′が再構成できるようにする。第２の実施形態においては、秘密情報Ｓ′、及び、既に保有されている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を入力とするマルチパーティ・プロトコルによる分散計算を行うことにより、その既に保有されている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）、及び、もとの秘密情報Ｓ′を公開しないまま、秘密分散の他のｎ−ｔ３個の分散情報Ｘｍ_ｙ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）を、メンバの分散演算装置が協力して求める。
【００５３】
第２の実施形態においては、ｔ３人のメンバがなんらかの分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を既に持っている状態を考える。これらのメンバのメンバＩＤをそれぞれｍ_１，ｍ_２，…，ｍ_ｔ３とする。そして、秘密情報Ｓ′が与えられたとき、その秘密情報Ｓ′を秘密分散したｎ個（ｎ＞ｔ３）の分散情報を算出したいとする。秘密情報Ｓ′を秘密分散する秘密分散法は、次の２通りを考える。
【００５４】
第１の秘密分散法（第１のＳＳＳ）は、加算秘密分散法（ｎ個の分散情報を加算することで秘密情報Ｓ′を得られるようにする秘密分散法）である。ただし、ｎ＞ｔ３である場合を考える。
【００５５】
第２の秘密分散法（第２のＳＳＳ）は、（ｋ，ｎ）しきい値秘密分散法（秘密分散したｎ個の分散情報のうち、ｋ個以上の分散情報から秘密情報Ｓ′を再構成することができる秘密分散法）である。ただし、ｎ≧ｋ＞ｔ３である場合を考える。
【００５６】
このとき、第１のＳＳＳ及び第２のＳＳＳのどちらの場合においても、既に保有されている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を、算出したい分散情報に含まれるようにする。そして、残りのｎ−ｔ３個の分散情報Ｘｍ_ｙ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）を生成して該当メンバに配布する場合を考える。
【００５７】
第１の実施形態と同様に、メンバのうち、どの２人のメンバ間にも、その２人のメンバ以外には通信内容を秘密とすることができる秘密通信路が確立されているとする（図４）。
【００５８】
まず、図１３を用いて、第２の実施形態の概要を簡単に説明する。図１３は、第２の実施形態に係る秘密分散方法を実施する秘密分散システムの構成を示す図である。図１３においては、メンバ（分散演算装置）の人数は４人とし、そのうち１人のメンバＰ_Ａは、なんらかの分散情報Ａを既に保有しているとする。そのとき、秘密情報Ｓ′のメンバＰ_Ａの分散情報をＡとし、他のメンバＰ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄの秘密情報Ｓ′の分散情報Ｂ，Ｃ，Ｄを、分散情報Ａや、秘密情報Ｓ′を公開しないで計算したいとする。このとき、メンバＰ_Ａ（分散情報を既に保有するメンバ）が持っている分散情報Ａをさらに分散して部分情報Ａ_１，Ａ_２，Ａ_３，Ａ_４を生成し（図１３の処理▲１▼）、さらに、秘密情報Ｓ′を分散して部分情報Ｓ′_１，Ｓ′_２，Ｓ′_３，Ｓ′_４を生成して（図１３の処理▲１▼′）、それらを他のメンバに配布する（図１３の処理▲２▼′）。図１３においては、秘密情報Ｓ′を分散するのに、メンバ以外の組織の秘密情報Ｓ′の保管機関が行うように描いているが、実際には、メンバのうちの１人であっても構わない。各メンバは、受け取った分散情報や秘密情報の部分情報をもとに、分散計算を行う（図１３の処理▲３▼）。この分散計算においては、各メンバは、計算結果である、分散情報Ｂ，Ｃ，Ｄそれぞれの部分情報を出力する（各メンバは３個ずつ部分情報を出力する）。各メンバは、その分散計算の計算結果をそれぞれ該当するメンバ（メンバＰ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄ）へ送信し（図１３の処理▲４▼）、メンバＰ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄは、それらを集めて再構成することで、それぞれ、分散情報Ｂ，Ｃ，Ｄを得ることができる（図１３の処理▲５▼）。
【００５９】
このとき、第１のＳＳＳ（加算秘密分散法）の場合には、分散情報Ａ，Ｂ，Ｃ，Ｄをすべて加算すると秘密情報Ｓ′を得ることができ（ｔ３＝１；ｎ＝４である）、第２のＳＳＳ（（ｋ，ｎ）しきい値秘密分散法）の場合には、秘密情報Ｓ′を、（２，４）、（３，４）又は、（４，４）しきい値秘密分散法で分散した分散情報がＡ，Ｂ，Ｃ，Ｄとなっている（ｔ３＝１；ｎ＝４；ｋ＝２、３、又は、４）。
【００６０】
第２の実施形態の秘密分散システムは、第１の実施形態と同様な構成（図６）をしているが、分散演算装置の構成と動作が異なるので、分散演算装置の符号を６０１として説明する。分散情報を計算するメンバは、それぞれ、分散計算で分散情報を計算するために必要な手段を持つ分散演算装置６０１を持っており、この秘密分散システムは、複数の分散演算装置６０１からなる（図６）。各メンバの分散演算装置６０１は、それぞれ他のメンバの分散演算装置６０１とは、図４で説明した秘密通信路３０２で接続されている。各メンバの分散演算装置６０１における処理は、各メンバがそれぞれ他のメンバにはその処理の内容が分からないように行う。
【００６１】
次に、図１４を用いて分散演算装置６０１の構成を説明する。分散演算装置６０１は、ＳＳＳ部（秘密分散法実行部）７０１、分散計算部７０２、ＲＳＳＳ部（秘密再構成法実行部）７０３、及びＳＳＳ部（秘密分散法実行部）７０４のうち、少なくともいずれか１つを有する。例えば、図１３の例を取り上げて説明すると、ＳＳＳ部７０１は、図１３における処理▲１▼及び処理▲２▼、すなわち、分散情報を分散して部分情報を生成し配布する処理を行う。ＳＳＳ部７０４は、図１３における処理▲１▼′及び処理▲２▼′、すなわち、秘密情報Ｓ′を分散して部分情報を生成し配布する処理を行う。また、分散計算部７０２は、図１３における処理▲３▼及び処理▲４▼、すなわち、分散計算を行って、その結果を分散情報が必要なメンバに送信する処理を行う。また、ＲＳＳＳ部７０３は、図１３における処理▲５▼、すなわち、他のメンバから分散計算の結果を受信して分散情報を生成する処理を行う。したがって、図１３におけるメンバＰ_Ａの分散演算装置６０１は、少なくともＳＳＳ部７０１及び分散計算部７０２を有し（図１５）、メンバＰ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄの分散演算装置６０１は、少なくとも分散計算部７０２及びＲＳＳＳ部７０３を有する（図１６）。また、秘密情報Ｓ′を分散するＳＳＳ部７０４をメンバＰ_Ａの分散演算装置６０１に含めたような構成（図１７）、又は、メンバＰ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄの分散演算装置６０１に含めたような構成（図１８）も可能である。特に、計算資源が限られる分散演算装置６０１は、ＳＳＳ部７０１、分散計算部７０２、ＲＳＳＳ部７０３、又は、ＳＳＳ部７０４のうち、いずれか１つのみしか持たない場合もありうる（図１９、図２０、図２１、図２２）。また、ＳＳＳ部７０１とＳＳＳ部７０４との組み合わせ、又は、ＳＳＳ部７０１と分散計算部７０２との組み合わせ、又は、ＲＳＳＳ部７０３とＳＳＳ部７０４との組み合わせの構成（図２３、図２４、図２５）も可能である。
【００６２】
ＳＳＳ部７０１は、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｔ３）であるメンバが既に保有している分散情報Ｘｍ_ｊを分散して部分情報を求め、各メンバへの配布の処理を行う。ＳＳＳ部７０１は、第１の実施形態のＳＳＳ部４０１と同様に、秘密分散部７０１１及び送信部７０１２からなる。既に分散情報を保有している、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｔ３）であるメンバの分散演算装置６０１は、ＳＳＳ部７０１を持つ。
【００６３】
ＳＳＳ部７０１の秘密分散部７０１１へは、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｔ３）であるメンバが既に保有する分散情報Ｘｍ_ｊが入力される。秘密分散システムにおける分散演算装置６０１のうち、分散計算部７０２を持つものがｔ４個存在するとし、それらのメンバＩＤをｍ′_１，ｍ′_２，…，ｍ′_ｔ４とする。秘密分散部７０１１は、入力された分散情報Ｘｍ_ｊを、（ｋ′，ｔ４）しきい値秘密分散法（ｋ′≦ｔ４）、又は、加算秘密分散法を用いて分散して（上記第１のＳＳＳ又は第２のＳＳＳどちらの場合でも、（ｋ′，ｔ４）しきい値秘密分散法、又は、加算秘密分散法を用いることができる）、ｔ４個の部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ４）を生成し、これらの部分情報Ｘｍ′_ｊ，ｐを送信部７０１２へ出力する。
【００６４】
ＳＳＳ部７０１の送信部７０１２は、入力された分散情報を他のメンバと通信する秘密通信路３０２を経て、分散計算部７０２を持つ分散演算装置６０１（メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ４）であるメンバの分散演算装置６０１）へ配布する。分散演算装置６０１がＳＳＳ部７０１と分散計算部７０２とを有する場合には、秘密分散部７０１１は、自分自身への部分情報Ｘｍ′_ｊ，ｐ（ｍ_ｊ＝ｍ′_ｐ）を、（後述する）分散計算部７０２の部分情報計算部７０２１へ出力する。
【００６５】
分散計算部７０２は、他の分散演算装置６０１から部分情報を受け取って、計算したい分散情報Ｘｍ_ｙ（メンバＩＤがｍ_ｙ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）の分散情報）の部分情報Ｘｍ′_ｙ，ｐを計算する部分である。分散計算部７０２は、第１の実施形態のＳＳＳ部４０１と同様に、部分情報計算部７０２１及び送受信部７０２２からなる。メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ４）であるメンバの、ｔ４個の分散演算装置６０１が分散計算部７０２を持つとする。
【００６６】
分散計算部７０２の送受信部７０２２（メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ４））は、ＳＳＳ部７０１を持つ分散演算装置６０１（メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｔ３））からの部分情報Ｘｍ′_ｊ，ｐを受信して、部分情報計算部７０２１へ出力し、また、部分情報計算部７０２１からの出力（計算結果）を受け取って、他の分散演算装置６０１へ送信する。
【００６７】
分散計算部７０２の部分情報計算部７０２１（メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ４））は、送受信部７０２２で受信した部分情報を受け取る。また、分散演算装置６０１がＳＳＳ部７０１と分散計算部７０２とを有する場合には、秘密分散部７０１１から、自分自身への部分情報Ｘｍ′_ｊ，ｐ（ｍ_ｊ＝ｍ′_ｐ）も受け取る。部分情報計算部７０２１は、受け取った情報から、次のような計算を行って、ｎ−ｔ３個の部分情報Ｘｍ′_ｙ，ｐ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）を算出する。この算出方法は、上記第１のＳＳＳ又は第２のＳＳＳの場合によって異なる。まず、第１のＳＳＳの場合から説明する。
【００６８】
［第１のＳＳＳ（加算秘密分散法）の場合］
ｎ−ｔ３個の部分情報Ｘｍ′_ｊ，ｐ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ）のうち、ｎ−ｔ３−１個の部分情報Ｘｍ′_ｙ，ｐ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ−１）は、乱数Ｒ_ｙ，ｐを生成し、
Ｘｍ′_ｙ，ｐ＝Ｒ_ｙ，ｐ …（１６）
とする。また、それ以外の残りの１個の部分情報Ｘｍ′_ｎ，ｐは、既に保有されている分散情報Ｘｍ_ｊの部分情報Ｘｍ′_ｊ，ｐ（ｊ＝１，２，…，ｔ３）、及び、式（１６）で求めた部分情報Ｘｍ′_ｊ，ｐ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ−１）を用いて、次式（１７）により算出する。ここで、Ｓ′_ｐは秘密情報Ｓ′の部分情報であり詳細は後述する。
【数４】

なお、ｔ３＝ｎ−１の場合には、算出したい分散情報は、ｎ−ｔ３＝１個となるので、式（１６）の処理、すなわち乱数生成して、その乱数を部分情報に割り当てる処理は行わない。
【００６９】
［第２のＳＳＳ（（ｋ，ｎ）しきい値秘密分散法）の場合］
ｎ−ｔ３個の部分情報Ｘｍ′_ｊ，ｐ（ｊ＝ｔ３＋１，ｔ３＋２，…,ｎ）のうち、ｋ−ｔ３−１個の部分情報Ｘｍ′_ｙ，ｐ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｋ−１）は、乱数Ｒ_ｙ，ｐを生成し、
Ｘｍ′_ｙ，ｐ＝Ｒ_ｙ，ｐ …（１８）
とする。また、それ以外の部分情報Ｘｍ′_ｊ，ｐ（ｊ＝ｋ，ｋ＋１，…，ｎ）のうち、１個の部分情報Ｘｍ′_ｙ，ｐ（ｙ＝ｋ）は、秘密情報Ｓ′の部分情報Ｓ′_ｐ（詳細は後述）、既に保有されている分散情報Ｘｍ_ｊの部分情報Ｘｍ′_ｊ，ｐ（ｊ＝１，２，…，ｔ３）、及び、式（１８）で求めた部分情報Ｘｍ′_ｊ，ｐ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｋ−１）を用いて、次式（１９）〜（２１）を用いて算出する。
【数５】

【００７０】
また、それ以外の残りのｎ−ｋ個の部分情報Ｘｍ′_ｙ，ｐ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）は、上記式（１９）〜（２１）と同様に求めるか、又は、次のように求める。既に保有されている分散情報Ｘｍ_ｊの部分情報Ｘｍ′_ｊ，ｐ（ｊ＝１，２，…，ｔ３）、式（１８）で求めた部分情報Ｘｍ′_ｊ，ｐ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｋ−１）、及び、式（１９）〜（２１）で求めた部分情報Ｘｍ′_ｊ，ｐ（ｊ＝ｋ）を用いて、次式（２２）及び（２３）を用いて算出する。
【数６】

【００７１】
なお、ｔ３＝ｋ−１の場合には、算出したい分散情報は、ｋ−ｔ３−１＝０となるので、式（１８）の処理、すなわち乱数生成して、その乱数を部分情報に割り当てる処理は行わない。また、ｎ＝ｋの場合には、ｎ−ｋ＝０となるので、最後に記述した残りのｎ−ｋ個の部分情報Ｘｍ′_ｙ，ｐ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）の算出方法については行わない。
【００７２】
ＲＳＳＳ部７０３は、分散計算部７０２を持つ分散演算装置６０１から部分情報の計算結果を受信して、それら計算結果から求めたい分散情報を算出する処理を行う部分である。ＲＳＳＳ部７０３は、秘密再構成部７０３１及び受信部７０３２からなる。求めたい分散情報に該当するメンバ（メンバＩＤがｍ_ｔ３＋１，_{ｍｔ３＋２}，…，ｍ_ｎであるメンバ）の分散演算装置６０１は、このＲＳＳＳ部７０３を持つ。
【００７３】
ＲＳＳＳ部７０３の受信部７０３２（メンバＩＤがｍ_ｊ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ））は、分散計算部７０２を持つ分散演算装置６０１から、計算結果である、分散情報Ｘｍ_ｊの部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ４）を受信して、その受信情報を秘密再構成部７０３１へ出力する。
【００７４】
ＲＳＳＳ部７０３の秘密再構成部７０３１（メンバＩＤがｍ_ｊ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ））は、受信部７０３２から部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ４）を受け取る。また、分散演算装置６０１が分散計算部７０２とＲＳＳＳ部７０３を有する場合には、部分情報計算部７０２１から自分自身への部分情報Ｘｍ′_ｊ，ｐ（ｍ_ｊ＝ｍ′_ｐ）を受け取る。それら受け取った部分情報を再構成することにより、分散情報Ｘｍ_ｊを得る。この再構成は、ＳＳＳ部７０１を持つ分散演算装置６０１の秘密分散部７０１１での秘密分散法が、（ｋ′，ｔ４）しきい値秘密分散法（ｋ′≦ｔ４）を用いたならば、しきい値秘密分散法の再構成方法、加算秘密分散法を用いたならば加算秘密分散法の再構成方法で行う。
【００７５】
ＳＳＳ部７０４は、分散したいもとの秘密情報Ｓ′を分散して部分情報Ｓ′_ｐを生成し、分散計算部７０２を持つ分散演算装置６０１へ配布する処理を行う部分である。図１３で説明したように、ＳＳＳ部７０４は、メンバの分散演算装置６０１以外の装置が独立して持っていてもよいし、メンバの１人が持っていてもよいが、この秘密分散システムを構成する処理部分（分散演算装置６０１）のうち、少なくとも１つは、ＳＳＳ部７０４を持っている必要がある。複数の分散演算装置６０１がＳＳＳ部７０４を持っていてもよいが、実際に秘密分散の計算を行う場合には、そのうちただ１つのみが動作する。ＳＳＳ部７０４は、秘密分散部７０４１及び送信部７０４２からなる。
【００７６】
ＳＳＳ部７０４の秘密分散部７０４１へは、分散したいもとの秘密情報Ｓ′が入力される。秘密分散装置における分散演算装置６０１のうち、分散計算部７０２を持つものがｔ４個存在するとし、それらのメンバＩＤをｍ′_１，ｍ′_２，…，ｍ′_ｔ４とする。秘密分散部７０４１は、入力された分散情報Ｓ′を（ｋ′，ｔ４）しきい値秘密分散法（ｋ′≦ｔ４）、又は、加算秘密分散法を用いて分散して、ｔ４個の部分情報Ｓ′_ｐ（ｐ＝１，２，…，ｔ４）を生成し、それら部分情報Ｓ′_ｐを送信部７０４２へ出力する。この秘密分散法は、ＳＳＳ部７０１を持つ分散演算装置６０１の秘密分散部７０１１での秘密分散法が、（ｋ′，ｔ４）しきい値秘密分散法（ｋ′≦ｔ４）を用いたならば、（ｋ′，ｔ４）しきい値秘密分散法、加算秘密分散法を用いたならば加算秘密分散法で行う。
【００７７】
ＳＳＳ部７０４の送信部７０４２は入力された分散情報を他のメンバと通信する秘密通信路３０２を経て、分散計算部７０２を持つ分散演算装置６０１（メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ４）であるメンバの分散演算装置６０１）へ配布する。分散演算装置６０１がＳＳＳ部７０４と分散計算部７０２とを有する場合（メンバＩＤをｍ_ｊとする）には、秘密分散部７０４１は、自分自身への部分情報Ｓ′_ｐ（ｍ_ｊ＝ｍ′_ｐ）を、分散計算部７０２の部分情報計算部７０２１へ出力する。
【００７８】
図２６は、第２の実施形態の秘密分散システムの動作を示すフローチャートである。ｔ３人のメンバがなんらかの分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を既に持っている状態を考え、これらのメンバのメンバＩＤをそれぞれｍ_１，ｍ_２，…，ｍ_ｔ３とする。そして、ある秘密情報Ｓ′が与えられたとき、ｎ個（ｎ＞ｔ３）の分散情報から秘密情報Ｓ′が得られるような秘密分散法のｎ個の分散情報を算出したいとする。ただし、既に保有されている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を、そのまま変更せずに、算出したい分散情報に含まれるようにする。そして、残りのｎ−ｔ３個の分散情報Ｘｍ_ｊ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ）を生成して該当メンバに配布する場合を考える。
【００７９】
まず、分散情報を既に持つ、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｔ３）であるメンバの分散演算装置６０１は、自身の持つ分散情報Ｘｍ_ｊを、しきい値秘密分散法、又は、加算秘密分散法で分散して部分情報を生成し、分散計算部７０２を持つメンバ（メンバＩＤをｍ′_ｐ（ｐ＝１，２，…，ｔ４）とする）の分散演算装置６０１へ配布する（ステップＳ８０１）。また、ＳＳＳ部７０４を持つ分散演算装置６０１は、秘密情報Ｓ′をしきい値秘密分散法、又は、加算秘密分散法で分散して（ただし、ステップＳ８０１と同じ秘密分散法を用いる）部分情報を生成し、分散計算部７０２を持つメンバ（メンバＩＤをｍ′_ｐ（ｐ＝１，２，…，ｔ４））の分散演算装置６０１へ配布する（ステップＳ８０２）。ステップＳ８０１とステップＳ８０２は、図２６に示されるように並列に動作させてもよいし、プログラムソフトウェアで実行させるように直列に動作させてもよい。直列に動作させるときには、ステップＳ８０１とステップＳ８０２のどちらを先に実行してもよい。ステップＳ８０１は、分散演算装置６０１のＳＳＳ部７０１の動作に相当し、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｔ３）であるメンバの分散演算装置６０１は、自身の持つ分散情報Ｘｍ_ｊから部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ４）を生成し、その部分情報Ｘｍ′_ｊ，ｐを、メンバＩＤがｍ′_ｐであるメンバの分散演算装置６０１へ配布する。ステップＳ８０２は、分散演算装置６０１のＳＳＳ部７０４の動作に相当し、秘密情報Ｓ′から部分情報Ｓ′_ｐ（ｐ＝１，２，…，ｔ４）を生成し、その部分情報Ｓ′_ｐを、メンバＩＤがｍ′_ｐであるメンバの分散演算装置６０１へ配布する。
【００８０】
次に、分散計算部７０２を持つメンバ（メンバＩＤをｍ′_ｐ（ｐ＝１，２，…，ｔ４））の分散演算装置６０１は、配布された部分情報Ｘｍ′_ｊ，ｐ（ｊ＝１，２，…，ｔ３）、及び、部分情報Ｓ′_ｐを用いて演算を施し、新たに求めたい分散情報の部分情報を求め、ＲＳＳＳ部７０３を持つメンバ（メンバＩＤがｍ_ｊ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ））の分散演算装置６０１へ送信する（ステップＳ８０３）。ステップＳ８０３は、分散計算部７０２における動作を示しており、メンバＩＤがｍ′_ｐ（ｐ＝１，２，…，ｔ４）であるメンバの分散演算装置６０１は、配布される部分情報Ｘｍ′_ｊ，ｐ（ｊ＝１，２，…，ｔ３）から、上記第１のＳＳＳの場合は式（１６）及び（１７）を用い、上記第２のＳＳＳの場合は式（１８）〜（２３）を用いて、新たに求めたい分散情報の部分情報Ｘｍ′_ｊ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ）を算出し、メンバＩＤがｍ_ｊであるメンバの分散演算装置６０１へ送信する。
【００８１】
次に、ＲＳＳＳ部７０３を持つメンバ（メンバＩＤがｍ_ｊ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ））の分散演算装置６０１は、受け取った部分情報Ｘｍ′_ｊ，ｐ（ｐ＝１，２，…，ｔ４）から、しきい値秘密分散法、又は、加算秘密分散法の再構成方法を用いて（ただし、ステップＳ８０１と同じ秘密分散法の再構成方法を用いる）、分散情報Ｘｍ_ｊ（ｊ＝ｔ３＋１，ｔ３＋２，…，ｎ）を再構成する（ステップＳ８０４）。ステップＳ８０４は、ＲＳＳＳ部７０３における動作を示している。
【００８２】
この結果、メンバＩＤがｍ_ｊ（ｊ＝１，２，…，ｎ）であるメンバは、それぞれ、もとの秘密情報Ｓ′を、秘密分散法で分散した分散情報Ｘｍ_ｊを持つことになる。さらに、秘密分散する前に既に配布されていた分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）はそのまま変更せずに再利用することができている。
【００８３】
以上説明したように、第２の実施形態に係る秘密分散方法又は秘密分散システムを用いれば、ｎ人のメンバからなるグループがあり、これらｎ人のメンバのうちのｔ３人のメンバのそれぞれが既に分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を保有している既保有メンバであり、残りのｎ−ｔ３人のメンバが分散情報を保有していない未保有メンバである場合に、上記ｎ人のメンバのうちのｋ人以上のメンバの保有する分散情報からもとの秘密情報を再構成することができるように、且つ、ｔ３人の既保有メンバが保有する分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）をそのままにして、ｎ−ｔ３人の未保有メンバに保有させるｎ−ｔ３個の分散情報Ｘｍ_ｙ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）を算出することができる。したがって、第２の実施形態によれば、秘密情報Ｓ′や、既に保有されている分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）を全員に公開することなく、残りの分散情報Ｘｍ_ｙ（ｙ＝ｔ３＋１，ｔ３＋２，…，ｎ）を生成して該当メンバに配布することができる。このとき、既に配布されていた分散情報Ｘｍ_ｊ（ｊ＝１，２，…，ｔ３）は、そのまま有効に利用でき、既に配布されていた分散情報の再計算も必要としない。
【００８４】
また、第１の実施形態と同様に、秘密分散を行うためのセンターを必要としないといった利点もある。秘密分散を行うためのセンターがある場合、メンバの保有する分散情報をすべてセンターが把握してしまうため、センターがメンバになりすます不正（「分散情報Ｘｍ_ｊを持っているので、私はメンバＩＤがｍ_ｊのメンバです」といった「なりすまし」のような不正）があり得るが、第２の実施形態によれば、このような不正を防ぐことができる。
【００８５】
さらに、第２の実施形態に係る秘密分散方法及び秘密分散システムは、次のような用途に適用可能である。この用途例を図２７を用いて説明する。参加者Ｐ_Ａ，Ｐ_Ｂ，Ｐ_Ｃからなるグループ▲１▼で秘密情報Ｓを分散し、参加者Ｐ_Ａ，Ｐ_Ｂ，Ｐ_Ｃは、それぞれ、ある秘密情報Ｓの分散情報Ａ，Ｂ，Ｃを既に保有している場合を考える。参加者Ｐ_ＡとＰ_Ｂは、参加者Ｐ_Ａ，Ｐ_Ｂ，Ｐ_Ｄ，Ｐ_Ｅからなるグループ▲２▼にも所属しており、秘密情報Ｓ′の分散情報をも得る必要がある場合、従来の技術だと、参加者Ｐ_Ａの既にもつ秘密情報Ｓの分散情報Ａと、秘密情報Ｓ′の分散情報Ａ′とは、通常一致することはなく、参加者Ｐ_Ａは、この場合、２つの分散情報を持つ必要があった（参加者Ｐ_Ｂも同様）。分散情報Ａと分散情報Ａ′とを一致させようとして秘密情報Ｓ′の秘密分散を行う場合、分散情報Ａを公開しなければ算出することができなかった。これを、第２の実施形態に係る秘密分散方法を用いて、参加者Ｐ_Ａ，Ｐ_Ｂの既に保有する情報Ａ，Ｂを再利用できるよう、参加者Ｐ_Ｄ，Ｐ_Ｅの分散情報Ｄ，Ｅを算出すると、参加者Ｐ_Ａ，Ｐ_Ｂは、それぞれ、１つの分散情報Ａ，Ｂのみを保管しておくだけでよくなり、情報Ａ，Ｂを公開することもない。すなわち、第２の実施形態によると、複数の秘密情報からの分散情報を保有しなければならない場合に、その分散情報の個数を少なくする（記憶装置が小さくて済む）ことができる。しかも、分散情報を公開することなく秘密分散を行うことができる。
【００８６】
≪変形例≫
上記第１及び第２の実施形態においての「メンバ」は、必ずしも１人の人間である必要はなく、計算手段（ＳＳＳ部、部分情報計算部、ＲＳＳＳ部）を構成要素として持つ装置とすることができる。
【００８７】
また、１人の人間が、上記装置を複数個持って処理を進めることができるし（この場合は、１人の人間が複数のメンバとなる）、一つの上記装置を複数の人間が持って処理を進めることもできる（この場合は、複数の人間が１人のメンバとなる）。
【００８８】
また、第１の実施形態の分散演算装置においては、ＳＳＳ部４０１、分散計算部４０２、ＲＳＳＳ部４０３のうち、２つ以上を構成要素として持つ場合、送信する手段（送信部４０１２、送受信部４０２２）や受信する手段（送受信部４０２２、受信部４０３２）を、それぞれ複数持つ場合が生じるが、そのような場合には、共通となる部分を共通化して構成することもできる。
【００８９】
同様に、第２の実施形態の分散演算装置でも、ＳＳＳ部７０１、分散計算部７０２、ＲＳＳＳ部７０３、ＳＳＳ部７０４のうち、２つ以上を構成要素として持つ場合、送信する手段（送信部７０１２、送受信部７０２２、送信部７０４２）や受信する手段（送受信部７０２２、受信部７０３２）を、それぞれ複数持つ場合が生じるが、そのような場合には、共通となる部分を共通化して構成することもできる。
【００９０】
【発明の効果】
以上説明したように、本発明によれば、もとの秘密情報及び既に何人かのメンバが保有している分散情報を秘密にしたまま、既に保有されている分散情報を変更せず、分散情報を未だ保有していないメンバの分散情報を算出することができるという効果がある。
【００９１】
また、本発明によれば、秘密分散を行うためのセンターを必要とせず、センターがメンバになりすます不正を防止できるという効果がある。
【図面の簡単な説明】
【図１】 本発明の第１の実施形態に係る分散演算装置（ＳＳＳ部、分散計算部、及びＲＳＳＳ部を有する場合）の構成を示すブロック図である。
【図２】 （ｋ，ｎ）しきい値秘密分散法に基づく秘密分散を実施する秘密分散計算部の動作を説明するための図である。
【図３】 加算秘密分散法に基づく秘密分散を実施する秘密分散計算部の動作を説明するための図である。
【図４】 秘密通信路の説明図である。
【図５】 本発明の第１の実施形態に係る秘密分散システムの構成を示す図である。
【図６】 本発明の第１及び第２の実施形態に係る秘密分散システムを構成する分散演算装置及び秘密通信路を示す図である。
【図７】 本発明の第１の実施形態に係る分散演算装置（ＳＳＳ部及び分散計算部を有する場合）の構成を示すブロック図である。
【図８】 本発明の第１の実施形態に係る分散演算装置（分散計算部及びＲＳＳＳ部を有する場合）の構成を示すブロック図である。
【図９】 本発明の第１の実施形態に係る分散演算装置（ＳＳＳ部を有する場合）の構成を示すブロック図である。
【図１０】 本発明の第１の実施形態に係る分散演算装置（分散計算部を有する場合）の構成を示すブロック図である。
【図１１】 本発明の第１の実施形態に係る分散演算装置（ＲＳＳＳ部を有する場合）の構成を示すブロック図である。
【図１２】 本発明の第１の実施形態に係る秘密分散システムの動作を示すフローチャートである。
【図１３】 本発明の第２の実施形態に係る秘密分散システムの構成を示す図である。
【図１４】 本発明の第２の実施形態に係る分散演算装置（分散情報から部分情報を生成するＳＳＳ部、分散計算部、ＲＳＳＳ部、及びもとの秘密情報から分散情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図１５】 本発明の第２の実施形態に係る分散演算装置（分散情報から部分情報を生成するＳＳＳ部及び分散計算部を有する場合）の構成を示すブロック図である。
【図１６】 本発明の第２の実施形態に係る分散演算装置（分散計算部及びＲＳＳＳ部を有する場合）の構成を示すブロック図である。
【図１７】 本発明の第２の実施形態に係る分散演算装置（分散情報から部分情報を生成するＳＳＳ部、分散計算部、及びもとの秘密情報から分散情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図１８】 本発明の第２の実施形態に係る分散演算装置（分散計算部、ＲＳＳＳ部、及びもとの秘密情報から分散情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図１９】 本発明の第２の実施形態に係る分散演算装置（分散情報から部分情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図２０】 本発明の第２の実施形態に係る分散演算装置（分散計算部を有する場合）の構成を示すブロック図である。
【図２１】 本発明の第２の実施形態に係る分散演算装置（ＲＳＳＳ部を有する場合）の構成を示すブロック図である。
【図２２】 本発明の第２の実施形態に係る分散演算装置（もとの秘密情報から分散情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図２３】 本発明の第２の実施形態に係る分散演算装置（分散情報から部分情報を生成するＳＳＳ部、及びもとの秘密情報から分散情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図２４】 本発明の第２の実施形態に係る分散演算装置（分散計算部、及びもとの秘密情報から分散情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図２５】 本発明の第２の実施形態に係る分散演算装置（ＲＳＳＳ部、及びもとの秘密情報から分散情報を生成するＳＳＳ部を有する場合）の構成を示すブロック図である。
【図２６】 本発明の第２の実施形態に係る秘密分散システムの動作を示すフローチャートである。
【図２７】 本発明の第２の実施形態に係る分散演算装置の用途例を示す図である。
【符号の説明】
３０１ 分散演算装置、
３０２ 秘密通信路、
４０１ ＳＳＳ部（秘密分散法実行部）、
４０１１ 秘密分散部、
４０１２ 送信部、
４０２ 分散計算部、
４０２１ 部分情報計算部、
４０２２ 送受信部、
４０３ ＲＳＳＳ部（秘密再構成法実行部）、
４０３１ 秘密再構成部、
４０３２ 受信部、
６０１ 分散演算装置、
７０１ ＳＳＳ部（分散情報から部分情報を生成する秘密分散法実行部）、
７０１１ 秘密分散部、
７０１２ 送信部、
７０２ 分散計算部、
７０２１ 部分情報計算部、
７０２２ 送受信部、
７０３ ＲＳＳＳ部（秘密再構成法実行部）、
７０３１ 秘密再構成部、
７０３２ 受信部、
７０４ ＳＳＳ部（もとの秘密情報から分散情報を生成する秘密分散法実行部）、
７０４１ 秘密分散部、
７０４２ 送信部、
Ｓ，Ｓ′ もとの秘密情報、
Ａ，Ｂ，Ｃ，Ｄ もとの秘密情報の分散情報、
Ａ_１〜Ａ_４，Ｂ_１〜Ｂ_４，Ｃ_１〜Ｃ_４ 分散情報の部分情報、
Ｐ_Ａ，Ｐ_Ｂ，Ｐ_Ｃ，Ｐ_Ｄ メンバ、
ｍ_１，ｍ_２，…，ｍ_ｎ メンバＩＤ、
Ｘｍ_ｊ メンバＩＤがｍ_ｊであるメンバに配布される分散情報。

Claims (15)

1. もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって生成されたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）をそれぞれ保有しているｎ（ｎは正の整数）人の初期メンバの分散演算装置からなるグループに、ｔ（ｔは正の整数）人の新規メンバの分散演算装置が追加された場合に、
   上記ｎ人の初期メンバの分散演算装置及び上記ｔ人の新規メンバの分散演算装置のうちのｋ（ｋはｎ以下の整数）人以上のメンバの分散演算装置が保有する分散情報から上記もとの秘密情報を再構成することができるように、且つ、上記ｎ人の初期メンバの分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）をそのままにして、上記ｔ人の新規メンバの分散演算装置に保有させるｔ個の分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を算出するシステムにおける秘密分散方法であって、
   上記初期メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を分散して複数の部分情報を生成し、上記部分情報のそれぞれを上記初期メンバの分散演算装置及び上記新規メンバの分散演算装置のそれぞれに配布する工程と、
   上記初期メンバの分散演算装置及び上記新規メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する部分情報を用いた分散計算により中間計算結果を生成し、上記新規メンバの分散演算装置のそれぞれに配布する工程と、
   上記新規メンバの分散演算装置のそれぞれが、受け取った上記中間計算結果を用いて、自身の分散演算装置が保有することになる上記分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を算出する工程と
   を有することを特徴とする秘密分散方法。
2. ｎ（ｎは正の整数）人のメンバの分散演算装置からなるグループがあり、上記ｎ人のメンバの分散演算装置のうちのｔ（ｔはｎより小さい正の整数）人のメンバの分散演算装置のそれぞれが既に分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有している既保有メンバの分散演算装置であり、残りのｎ−ｔ人のメンバの分散演算装置が分散情報を保有していない未保有メンバの分散演算装置である場合に、
   上記ｎ人のメンバの分散演算装置のうちのｋ（ｋはｎ以下の整数）人以上のメンバの分散演算装置の保有する分散情報からもとの秘密情報を再構成することができるように、且つ、上記ｔ人の既保有メンバの分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）をそのままにして、上記ｎ−ｔ人の未保有メンバの分散演算装置に保有させるｎ−ｔ個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を算出するシステムにおける秘密分散方法であって、
   上記既保有メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を分散して複数の第１の部分情報を生成し、上記第１の部分情報のそれぞれを上記メンバの分散演算装置のそれぞれに配布する工程と、
   上記メンバの分散演算装置に情報を配布できる装置が、上記もとの秘密情報から生成された複数の第２の部分情報のそれぞれを、上記メンバの分散演算装置のそれぞれに配布する工程と、
   上記メンバの分散演算装置のそれぞれが、自身の分散演算装置が保有する第１及び第２の部分情報を用いた分散計算により中間計算結果を生成し、上記未保有メンバの分散演算装置に配布する工程と、
   上記未保有メンバの分散演算装置が、受け取った上記中間計算結果を用いて、自身の分散演算装置が保有することになる上記分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を算出する工程と
   を有することを特徴とする秘密分散方法。
3. 分散演算に参加するメンバとしての分散演算装置を複数台有し、
   上記複数台の分散演算装置は、初期メンバとしてのｎ（ｎは正の整数）台の初期分散演算装置及び新規メンバとしてのｔ（ｔは正の整数）台の新規分散演算装置を含み、
   上記ｎ台の初期分散演算装置が、もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって生成されたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を、それぞれ保有している場合に、
   上記ｎ台の初期分散演算装置及び上記ｔ台の新規分散演算装置のうちのｋ（ｋはｎ以下の整数）台以上の分散演算装置の保有する分散情報から上記もとの秘密情報を再構成することができるように、且つ、上記ｎ台の初期分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）をそのままにして、上記ｔ台の新規分散演算装置に保有させるｔ個の分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を算出する秘密分散システムであって、
   上記初期分散演算装置のそれぞれが、自身が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を分散して複数の部分情報を生成し、上記部分情報のそれぞれを上記初期分散演算装置及び上記新規分散演算装置のそれぞれに配布し、
   上記初期分散演算装置及び上記新規分散演算装置のそれぞれが、自身が保有する部分情報を用いた分散計算により中間計算結果を生成し、上記新規分散演算装置のそれぞれに配布し、
   上記新規分散演算装置のそれぞれが、受け取った上記中間計算結果を用いて、自身が保有することになる上記分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を算出する
   ことを特徴とする秘密分散システム。
4. 分散演算に参加するメンバとしての分散演算装置をｎ（ｎは正の整数）台有し、
   上記ｎ台の分散演算装置のうちのｔ（ｔはｎより小さい正の整数）台の分散演算装置のそれぞれが既に分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有している既保有メンバとしての既保有分散演算装置であり、残りのｎ−ｔ台の分散演算装置が分散情報を保有していない未保有メンバとしての未保有分散演算装置である場合に、
   上記ｎ台の分散演算装置のうちのｋ（ｋはｎ以下の整数）台以上の分散演算装置の保有する分散情報からもとの秘密情報を再構成することができるように、且つ、上記ｔ台の既保有分散演算装置が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）をそのままにして、上記ｎ−ｔ台の未保有分散演算装置に保有させるｎ−ｔ個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を算出する秘密分散システムであって、
   上記既保有分散演算装置のそれぞれが、自身が保有する分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を分散して複数の第１の部分情報を生成し、上記第１の部分情報のそれぞれを上記分散演算装置のそれぞれに配布し、
   上記もとの秘密情報から複数の第２の部分情報を生成し、上記第２の部分情報のそれぞれを上記分散演算装置のそれぞれに配布し、
   上記分散演算装置のそれぞれが、自身が保有する第１及び第２の部分情報を用いた分散計算により中間計算結果を生成し、上記未保有分散演算装置に配布し、
   上記未保有分散演算装置が、受け取った上記中間計算結果を用いて上記分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を算出する
   ことを特徴とする秘密分散システム。
5. もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって得られたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）が既に与えられている場合に、上記もとの秘密情報を（ｋ，ｎ＋ｔ）しきい値秘密分散法を用いて秘密分散したような、さらにｔ個の分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置において、
   既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）の部分情報を受け取り、受信する部分情報用受信部と、
   分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）の部分情報を算出する部分情報計算部と、
   上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）の部分情報を送信する部分情報用送信部と
   を有し、
   上記部分情報計算部は、
   既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を保持する分散演算装置を特定するメンバＩＤ、及び、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤより計算される係数を算出し、
   上記算出された係数と、上記部分情報用受信部で受信した、対応する分散情報Ｘ_ｙの部分情報とを掛け合わせ、
   上記掛け合わせによって得られた値を足し合わせることによって分散情報Ｘ_ｙの部分情報を算出する
   ことを特徴とする分散演算装置。
6. 上記既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を秘密分散することにより、その部分情報を生成する秘密分散部と、
   上記秘密分散部で生成した部分情報を送信する秘密分散用送信部と
   を有することを特徴とする請求項５に記載の分散演算装置。
7. 上記算出したい分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）の部分情報を受信する秘密再構成用受信部と、
   上記秘密再構成用受信部で受信した部分情報を秘密再構成することにより、分散情報Ｘ_ｙを算出する秘密再構成部と
   を有することを特徴とする請求項５又は６のいずれかに記載の分散演算装置。
8. すべてを加算するともとの秘密情報を再構成できる加算秘密分散法を用いて秘密分散されたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）のうち、ｔ個（ｔ＜ｎ）の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）が既に与えられている場合に、残りの分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置において、
   既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、もとの秘密情報の部分情報を受信する部分情報用受信部と、
   分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を算出する部分情報計算部と、
   上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を送信する部分情報用送信部と
   を有し、
   上記部分情報計算部は、
   分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｔ−１個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ−１）の部分情報を算出するために、乱数を生成してそれを分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ−１）とし、
   分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｎ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、上記算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ−１）の部分情報を足し合わせ、
   上記部分情報用受信部で受信したもとの秘密情報の部分情報から、上記足し合わせによって算出した値を引き算することによって上記部分情報を算出する
   ことを特徴とする分散演算装置。
9. もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって得られたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）のうち、ｔ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）が既に与えられている場合に、
   ｎ≧ｋ＞ｔなる関係があって、残りの分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置において、
   既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、上記もとの秘密情報の部分情報を受信する部分情報用受信部と、
   分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を算出する部分情報計算部と、
   上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を送信する部分情報用送信部と
   を有し、
   上記部分情報計算部は、
   分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｋ−ｔ−１個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を算出するために、乱数を生成してそれを分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）とし、
   分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有する分散演算装置を特定するメンバＩＤと、上記算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤと、から計算される係数を算出し、
   分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記部分情報用受信部で受信したもとの秘密情報の部分情報と、上記算出された係数とを掛け合わせて第１の乗算値を算出し、
   分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記掛け合わせた係数と、上記部分情報用受信部で受信した、対応する分散情報Ｘ_ｙの部分情報とを掛け合わせて第２の乗算値を算出し、
   分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ＋１個の分散情報Ｘ_ｙ（ｙ＝ｋ，ｋ＋１，…，ｎ）の部分情報を算出するために、上記第１の乗算値と上記第２の乗算値を足し合わせる
   ことを特徴とする分散演算装置。
10. もとの秘密情報を（ｋ，ｎ）しきい値秘密分散法を用いて秘密分散することによって得られたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）のうち、ｔ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）が既に与えられている場合に、
    ｎ≧ｋ＞ｔなる関係があって、残りの分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を分散計算により算出するために、その分散情報の部分情報を算出する分散演算装置において、
    既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）の部分情報、及び、上記もとの秘密情報の部分情報を受信する部分情報用受信部と、
    分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を算出する部分情報計算部と、
    上記部分情報計算部で算出した分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を送信する部分情報用送信部と
    を有し、
    上記部分情報計算部は、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｋ−ｔ−１個の分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を算出するために、乱数を生成してそれを分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｋ−１）とし、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有する分散演算装置を特定するメンバＩＤと、上記算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤと、から計算される係数を算出し、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記部分情報用受信部で受信したもとの秘密情報の部分情報と、上記算出された係数とを掛け合わせて第１の乗算値を算出し、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記係数と、上記部分情報用受信部で受信した、対応する分散情報Ｘ_ｙの部分情報とを掛け合わせて第２の乗算値を算出し、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、１個の分散情報Ｘ_ｙ（ｙ＝ｋ）の部分情報を算出するために、上記第１の乗算値と上記第２の乗算値を足し合わせ、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ個の分散情報Ｘ_ｙ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）の部分情報を算出するために、上記部分情報用受信部で受信した既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を保有する分散演算装置を特定するメンバＩＤと、上算出した分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｋ−１）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、上記加算により算出した分散情報Ｘ_ｉ（ｉ＝ｋ）の部分情報を最終的に受け取る分散演算装置を特定するメンバＩＤと、算出する分散情報Ｘ_ｙを最終的に受け取る分散演算装置を特定するメンバＩＤと、から計算される係数を算出し、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ個の分散情報Ｘ_ｙ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）の部分情報を算出するために、上記係数と、上記受信部で受信した、対応する分散情報Ｘ_ｉの部分情報とを掛け合わせて第３の乗算値を算出し、
    分散情報Ｘ_ｉ（ｉ＝ｔ＋１，ｔ＋２，…，ｎ）のうち、ｎ−ｋ個の分散情報Ｘ_ｙ（ｙ＝ｋ＋１，ｋ＋２，…，ｎ）の部分情報を算出するために、上記第３の乗算値を足し合わせる
    ことを特徴とする分散演算装置。
11. 上記既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を秘密分散することにより、その部分情報を生成する秘密分散部と、
    上記秘密分散部で生成した部分情報を送信する秘密分散用送信部と
    を有することを特徴とする請求項９又は１０のいずれかに記載の分散演算装置。
12. 上記算出したい分散情報Ｘ_ｙの部分情報を受信する秘密再構成用受信部と、
    上記秘密再構成用受信部で受信した部分情報を秘密再構成することにより、分散情報Ｘ_ｙを算出する秘密再構成部と
    を有することを特徴とする請求項９から１１までのいずれかに記載の分散演算装置。
13. 上記もとの秘密情報を秘密分散することにより、その部分情報を生成する第２の秘密分散部と、
    上記第２の秘密分散部で生成した部分情報を送信する第２の秘密分散用送信部と
    を有することを特徴とする請求項９から１２までのいずれかに記載の分散演算装置。
14. （ｋ，ｎ）しきい値秘密分散法を用いて秘密分散されてｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）が既に与えられている場合に、もとの秘密情報を（ｋ，ｎ＋ｔ）しきい値秘密分散法を用いて秘密分散したような、さらにｔ個の分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）を分散計算により算出する秘密分散システムにおいて、
    上記請求項５から７までのいずれかに記載された分散演算装置と同じ構成を有する第１の分散演算装置、
    上記既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）を秘密分散することにより、その部分情報を生成する秘密分散部、その秘密分散部で生成した部分情報を送信する秘密分散用送信部を有する第２の分散演算装置、及び
    上記算出したい分散情報Ｘ_ｙ（ｙ＝ｎ＋１，ｎ＋２，…，ｎ＋ｔ）の部分情報を受信する受信部、その受信部で受信した部分情報を秘密再構成することにより分散情報Ｘ_ｙを算出する秘密再構成部を有する第３の分散演算装置
    のうちの２台以上の分散演算装置を有することを特徴とする秘密分散システム。
15. もとの秘密情報を秘密分散法を用いて秘密分散することによって得られたｎ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｎ）のうち、ｔ個の分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）が既に与えられている場合に、残りの分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）を分散計算により算出する秘密分散システムにおいて、
    請求項８から１３までのいずれかに記載の分散演算装置と同じ構成を持つ第１に分散演算装置、
    上記既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を秘密分散することによりその部分情報を生成する秘密分散部、その秘密分散部で生成した部分情報を送信する送信部を有する第２の分散演算装置、
    上記算出したい分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を受信する受信部、その受信部で受信した部分情報を秘密再構成することにより分散情報Ｘ_ｙを算出する秘密再構成部を有する第３の分散演算装置、
    上記もとの秘密情報を秘密分散することによりその部分情報を生成する第２の秘密分散部、上記第２の秘密分散部で生成した部分情報を送信する第２の送信部を有する第４の分散演算装置、
    上記既に与えられている分散情報Ｘ_ｉ（ｉ＝１，２，…，ｔ）を秘密分散することによりその部分情報を生成する第３の秘密分散部、その秘密分散部で生成した部分情報を送信する第３の送信部、上記もとの秘密情報を秘密分散することによりその部分情報を生成する第４の秘密分散部、上記秘密分散部で生成した部分情報を送信する第４の送信部を有する第５の分散演算装置、及び
    上記算出したい分散情報Ｘ_ｙ（ｙ＝ｔ＋１，ｔ＋２，…，ｎ）の部分情報を受信する第２の受信部、その第２の受信部で受信した部分情報を秘密再構成することにより分散情報Ｘ_ｙを算出する第２の秘密再構成部、上記もとの秘密情報を秘密分散することによりその部分情報を生成する第５の秘密分散部、上記秘密分散部で生成した部分情報を送信する第５の送信部を有する第６の分散演算装置
    のうちの２台以上の分散演算装置を有することを特徴とする秘密分散システム。

Images