秘密分散装置、方法及びプログラム
【課題】 多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現する。
【解決手段】 閾値４以上の（ｋ，ｎ）閾値法の秘密分散装置であって、ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成し、秘密情報Ｓをｎ−１個に分割して分割秘密データＫ（１），…，Ｋ（ｎ−１）を生成し、乱数データＵ（０，１），…，Ｕ（ｋ−２，ｎ−１）を生成し、分割秘密データ及び乱数データと生成行列Ｇとの行列の積を算出し、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、分散部分データＤ（ｊ，ｉ）を算出し、ヘッダ情報Ｈ（ｊ）を生成し、ヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，ｉ）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布する。
【解決手段】 閾値４以上の（ｋ，ｎ）閾値法の秘密分散装置であって、ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成し、秘密情報Ｓをｎ−１個に分割して分割秘密データＫ（１），…，Ｋ（ｎ−１）を生成し、乱数データＵ（０，１），…，Ｕ（ｋ−２，ｎ−１）を生成し、分割秘密データ及び乱数データと生成行列Ｇとの行列の積を算出し、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、分散部分データＤ（ｊ，ｉ）を算出し、ヘッダ情報Ｈ（ｊ）を生成し、ヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，ｉ）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、（ｋ，ｎ）閾値法を用いた秘密分散装置、方法及びプログラムに係り、例えば多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現し得る秘密分散装置、方法及びプログラムに関する。
【背景技術】
【０００２】
一般に、暗号化鍵などの秘密情報を紛失した場合の対策としては、予め秘密情報のコピーを作成しておくことが有効である。しかしながら、秘密情報のコピーを作成すると、盗難のリスクが高くなるという問題が生じる。このような問題を解決する手法として、１９７９年にシャミア（Shamir）が（ｋ，ｎ）閾値法と呼ばれる秘密分散法を提案している（例えば、非特許文献１参照）。
【０００３】
（ｋ，ｎ）閾値法では、秘密情報をｎ個の分散情報に分割し、ｎ個の分散情報の中から任意のｋ個を集めれば元の秘密情報を復元できるが、ｋ−１個の分散情報からでは、元の秘密情報に関する情報を全く得られない。すなわち、（ｋ，ｎ）閾値法は、閾値ｋを境にした秘密情報の復元特性をもっている（なお、１＜ｋ＜ｎ）。
【０００４】
このため、（ｋ，ｎ）閾値法によれば、ｋ−１個以下の分散情報が漏洩しても元の秘密情報が安全であり、ｎ−ｋ個以下の分散情報を紛失しても元の秘密情報を復元できるといった管理を実現できる。
【０００５】
しかしながら、シャミアの（ｋ，ｎ）閾値法では、秘密情報の分散や復元の処理を、多くの計算量を要する多項式補間により実現するので、大量のデータを秘密分散するためには、高速な計算機を必要とする不都合がある。
【０００６】
一方、このような不都合を解決し、計算量を大幅に削減し得る（ｋ，ｎ）閾値法として、藤井らの方式と栗原らの方式が知られている（例えば、非特許文献２、非特許文献３参照）。ここで、藤井らの方式と栗原らの方式は、秘密情報の分散処理や復元処理を排他的論理和演算のみで実現するので、高速に実行可能となっている。
【０００７】
しかしながら、藤井らの方式と栗原らの方式は、閾値ｋが２又は３に限定されるという不都合がある。
【非特許文献１】A. Shamir: “How to share a secret", Communications of the ACM, 22, 11, pp.612-613 (1979)
【非特許文献２】藤井吉弘,多田美奈子,保坂範和,栃窪孝也,加藤岳久: “高速な(2,ｎ)閾値法の構成とシステムへの応用", CSS2005予稿集, (2005)
【非特許文献３】栗原淳,清本晋作,福島和英,田中俊昭: “XORを用いた(3,ｎ)閾値秘密分散法", SCIS2007予稿集, (2007)
【発明の開示】
【発明が解決しようとする課題】
【０００８】
以上説明したように、シャミアによる（ｋ，ｎ）閾値法では、多項式補間を用いるため、高速な計算機が必要となる不都合がある。一方、藤井らの方式と栗原らの方式は、閾値ｋが２又は３に限定されるという不都合がある。
【０００９】
本発明は上記実情を考慮してなされたもので、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現し得る秘密分散装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の発明は、秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置であって、１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段と、前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する手段と、前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積を算出し（但し、ＧＦ（２）上の演算）、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、０≦ｊ≦ｎ−１、０≦ｉ≦ｎ−２）を算出する手段と、前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段とを備えた秘密分散装置である。
【００１１】
第２の発明は、秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）型の秘密分散装置であって、前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて第２分割秘密データＫ（０）を生成する手段と、前記各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する手段と、前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する手段と、前記乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、ｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する手段と（但し、(+)は排他的論理和を表す記号）、前記分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び前記乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する手段と、前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段とを備えた秘密分散装置である。
【００１２】
なお、第１及び第２の各発明は、「装置」として表現したが、これに限らず、「プログラム」、「プログラムを記憶した記憶媒体」又は「方法」として表現してもよい。
【００１３】
（作用）
第１の発明は、生成行列Ｇを用いて分散部分データを生成する構成により、秘密情報の分散や復元の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現することができる。
【００１４】
第２の発明は、前述した生成行列Ｇと同様に分散部分データを生成する構成により、秘密情報の分散の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現することができる。
【発明の効果】
【００１５】
以上説明したように本発明によれば、多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の各実施形態について図面を用いて説明する。なお、以下の各装置は、装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。
【００１７】
（第１の実施形態）
図１は本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図である。この秘密分散システムは、１台のクライアント装置１００及びｎ−１台の保管サーバ装置２００，３００，…，ｎ００が互いにインターネット等のネットワークＮＷを介して接続されている。
【００１８】
これら合計ｎ台の装置１００，２００，３００，…，ｎ００は、（ｋ，ｎ）閾値法におけるｎ人のメンバに対応する。特に、ｎ台の装置１００，２００，…，ｎ００が個別に有するｎ個の保存部１０１，２０１，…，ｎ０１は、ｎ人のメンバが個別に有するｎ個の記憶装置に対応する。各装置１００，２００，３００，…，ｎ００には、それぞれ分散情報の配布順番を示すｊ番号（行番号）が割当てられている。例えば、クライアント装置１００には、ｊ＝０番目が割り当てられており、保管サーバ装置２００にはｊ＝１番目が割り当てられている。保管サーバ装置３００にはｊ＝２番目が割り当てられ、…、保管サーバ装置ｎ００にはｊ＝ｎ−１番目が割り当てられている。
【００１９】
ここで、クライアント装置１００は、秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ台の装置１００，２００，…，ｎ００に配布し、且つ、ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置を実現するものである。なお、分散情報の個数はｋ個以上であればよい。この閾値ｋは２以上が使用可能であるが、非特許文献２，３との相違を明確にする観点から、本実施形態では４以上を用いている。例えばｋ＝４，ｎ＝４とし、秘密情報Ｓをｎ−１（＝３）個に分割して後述するＫ（１），Ｋ（２），Ｋ（３）とし、配布した４個の分散情報Ｄ（０），Ｄ（１），Ｄ（２），Ｄ（３）から秘密情報Ｓを復元してもよい。
【００２０】
クライアント装置１００は、保存部１０１、入力部１０２、生成行列生成部１０３、逆行列生成部１０４、分散部分データ生成部１０５、ハッシュ値生成部１０６、元データ復元部１０７、ハッシュ値検証部１０８、制御部１０９、出力部１１０及び通信部１１１が互いにバスを介して接続されている。
【００２１】
保存部１０１は、制御部１０９から読出／書込可能なハードウェア資源としての記憶装置であり、後述する分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、秘密情報Ｓが一時的に記憶される。また、保存部１０１は、分散情報Ｄ（０）〜Ｄ（ｎ−１）が作成されると、分散情報作成情報が記憶され、分散情報が配布された後、ｊ＝０番目の分散情報Ｄ（０）が記憶されると共に、秘密情報Ｓが削除される。ここで、分散情報作成情報は、分散情報Ｄ（ｊ）の識別情報ｊと、分散情報Ｄ（ｊ）の配布先識別情報（装置ＩＤ、装置のアドレス情報等）とが互いに関連付けられた情報である。
【００２２】
入力部１０２は、キーボード又はマウス等の通常の入力デバイスであり、操作者の操作により、分散処理又は復号処理の開始等の命令や、秘密情報Ｓ等の情報をクライアント装置１００内に入力する機能をもっている。
【００２３】
生成行列生成部１０３は、制御部１０９により制御され、図２にｋ＝４，ｎ＝５とした（４，５）閾値法の例を示す如き、１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する機能をもっている。但し、生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列である。ＧＦ（２）は位数２の有限体である。フルランクとは、行列の基本変形を施して得られるランク（rank：階数）がフル（full：満杯）（＝ｋ（ｎ−１））であり、線形独立であることを意味している。
【００２４】
具体的には、生成行列生成部１０３は、入力された分散数ｎ及び閾値ｋが保存部１０１に記憶されたとき、保存部１０１内の分散数ｎ及び閾値ｋに基づいて、第０行がゼロベクトルであり、第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列とは左右対称な行列であるｎ行×（ｎ−１）列の第１小行列を生成する処理と、最も左側の第１小行列の各列を上に１回巡回シフトさせたｎ行×（ｎ−１）列の新たな第１小行列を当該巡回シフト前の第１小行列の左側に隣接させる第１隣接処理と、第１隣接処理をｎ−１回実行し、ｎ行×n（ｎ−１）列の第１部分行列を生成する処理と、この第１部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第０行目から第ｎ-2行目に割り当てて、生成行列Ｇの第０行目から第ｎ−２行目までの部分行列を生成する第１部分行列割当て処理と、第０行がゼロベクトルであり、この第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列であるｎ行×（ｎ−１）列の第２小行列を生成する処理と、最も右側の第２小行列の各列を下にｊ回巡回シフトさせたｎ行×（ｎ−１）列の新たな第２小行列を当該巡回シフト前の第２小行列の右側に隣接させる第２隣接処理（但し、ｊ＝０，１，…，ｋ−２）と、第２隣接処理をｎ−１回実行し、ｎ行×n（ｎ−１）列の第２部分行列を生成する第２部分行列生成処理と、この第２部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目に割り当てて、生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目までの部分行列を生成する第２部分行列割当て処理（但し、ｊ＝０，１，…，ｋ−２）と、第２隣接処理及び第２部分行列割当て処理におけるｊの値が初期値０から最終値ｋ−２までの間、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理を実行する毎に当該ｊの値を１だけ増加させつつ、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理をｋ−１回実行する処理と、第１部分割当て処理により割り当てられた第０行目から第ｎ−２行目までの部分行列と、ｋ−１回の第２部分割当て処理により割り当てられた第ｎ−１行目から第（ｎ−１）（ｋ−１）＋ｎ−２行目までの部分行列とにより、ｋ（ｎ−１）行×ｎ（ｎ−１）列の生成行列Ｇを得る処理とを実行する機能をもっている。
【００２５】
逆行列生成部１０４は、制御部１０９により制御され、生成行列Ｇの逆行列を生成するものであり、例えば図３にｋ＝４，ｎ＝５とした（４，５）閾値法の例を示す如き、収集されたｋ個の列ベクトルから形成される生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））の逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’を算出する機能をもっている。
【００２６】
ここで、ｇ（Ｄ（＊））は、＊個目の分散情報Ｄ（＊）を算出するのに使用した生成行列Ｇの部分行列であり、列ベクトルともいう。また、（ｉ_1）の表記は、任意の１個目を表し、（ｉ_j）の表記は任意のｊ個目を表し、（ｉ_k）の表記は任意のｋ個目を表している。すなわち、カッコ内の左側のｉと下線“ｉ＿”は、“任意の”を表している（表記“ｉ＿”のｉは行番号ではない）。また、例えばＤ（ｉ_1）は、任意の１個目のＤ（＊）なので、Ｄ（０）〜Ｄ（４）のいずれでもよい。
【００２７】
分散部分データ生成部１０５は、制御部１０９により制御され、保存部１０１に一時的に記憶された秘密情報Ｓに基づいて、図４、図５に一例（ｋ＝４，ｎ＝５の例）を示すように、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を生成する機能をもっている。具体的には、分散部分データ生成部１０５は、以下の各機能（ｆ１０５−１）〜（ｆ１０５−３）をもっている。
【００２８】
（ｆ１０５−１） 保存部１０１に記憶された秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、０≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する機能。
【００２９】
（ｆ１０５−２） 各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、１≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する機能。なお、各乱数Ｕ（ｈ，ｇ）は、互いに独立である。
【００３０】
（ｆ１０５−３） 分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）、生成行列Ｇに基づいて、行列（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と生成行列Ｇの積を算出し（但し、ＧＦ（２）上の演算）、計算結果のj×(ｎ−１)+ｉ列目のデータをＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を算出する（但し、０≦ｊ≦ｎ−１，０≦ｉ≦ｎ−２）機能。
【００３１】
ハッシュ値生成部１０６は、制御部１０９により制御され、制御部１０９からバスを介してヘッダ情報Ｈ（ｊ）が入力されると、ヘッダ情報Ｈ（ｊ）のハッシュ値ｈ（Ｈ（ｊ））を生成し、得られたハッシュ値ｈ（Ｈ（ｊ））をバスに出力する機能をもっている。なお、ハッシュ値生成部１０６は、ヘッダ情報Ｈ（ｊ）を検証しない場合、省略可能である。
【００３２】
元データ復元部１０７は、制御部１０９に制御され、ｎ台の装置１００，…，ｎ００に配布されたｎ個の分散情報Ｄ（０）〜Ｄ（ｎ−１）のうち、任意のｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k）（但し、０≦ｉ_j≦ｎ−１）に基づいて、秘密情報Ｓを復元する秘密情報復元機能をもっている。具体的には元データ復元部１０７は、以下の各機能（ｆ１０７−１）〜（ｆ１０７−２）をもっている。
【００３３】
（ｆ１０７−１） 収集されたｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k）及び生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’に基づき、行列（Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k））と逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’の積を算出し、計算結果のｉ列目のデータをＫ（ｉ＋１）に割り当てて、分割秘密データＫ（１），…，Ｋ（ｎ−１）とする機能。
【００３４】
（ｆ１０７−２） 復元されたｎ−１個の分割秘密データＫ（１），…，Ｋ（ｎ−１）を互いに連接することにより、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（ｎ−１）を復元する機能（但し、‖は連接を表す記号）。
【００３５】
ハッシュ値検証部１０８は、制御部１０９により制御され、制御部１０９からバスを介してヘッダ情報Ｈ（ｊ）及びそのハッシュ値ｈ（Ｈ（ｊ））が入力されると、ハッシュ値ｈ（Ｈ（ｊ））に基づいてヘッダ情報Ｈ（ｊ）を検証し、検証結果をバスに出力する機能をもっている。検証内容は、ヘッダ情報Ｈ（ｊ）から計算したハッシュ値と、入力されたハッシュ値ｈ（Ｈ（ｊ））との一致により、ヘッダ情報Ｈ（ｊ）を正当と判定する方式である。なお、ハッシュ値検証部１０８は、ヘッダ情報Ｈ（ｊ）を検証しない場合、省略可能である。
【００３６】
ここで、ヘッダ情報Ｈ（ｊ）は、図６の上方に一例を示すように、行番号ｊを示すデータ識別子、ヘッダのサイズを表すヘッダーサイズ、元データのサイズを表す元データサイズｍ、元の秘密情報Ｓの分割数を示す分割数ｎ−１、分散部分データＤ（ｊ，ｉ）の処理単位ビットを示す処理単位ビット長ａ、乱数Ｒ（ｊ，ｉ）のデータサイズを示す乱数データサイズａ、分割秘密データＫ（ｊ）のサイズを表す分割データサイズａ、パディングの有無やアルゴリズムを表すパディングアルゴリズム、ハッシュアルゴリズム情報（オプション）、生成行列Ｇの部分行列ｇ（Ｄ（ｊ））（オプション）、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’（オプション）（但し、必ずｇ（Ｄ（j））を含む）などが考えられる。
【００３７】
ハッシュアルゴリズム情報は、ヘッダ情報のハッシュ値を算出し、ヘッダ情報の原本性を保証する場合などに追加される。すなわち、ハッシュアルゴリズム情報は、セキュリティの要件などに応じて追加又は省略される。但し、セキュリティの要件として予めシステムでハッシュアルゴリズムを決めている場合には、ハッシュアルゴリズム情報は、ヘッダ情報から省略可能である。
【００３８】
なお、分散情報Ｄ（ｊ）のデータフォーマットは、図６の下方に一例を示すように、ヘッダ情報Ｈ（ｊ）、そのハッシュ値ｈ（Ｈ（ｊ））、ｎ−１個の分散部分データＤ（ｊ，０），Ｄ（ｊ，１），…，Ｄ（ｊ，ｎ-2）から構成されている。ここで、ハッシュ値ｈ（Ｈ（ｊ））は、オプション（option）であり、ヘッダ情報Ｈ（ｊ）内のハッシュアルゴリズム情報と同様に、セキュリティの要件に応じて省略可能となっている。
【００３９】
制御部１０９は、入力部１０２から入力される命令に基づいて、後述する図７、図８及び図１７のフローチャートに基づいて、各部１０１，１０３〜１０８，１１０，１１１を制御する機能をもっている。また、制御部１０９は、例えば、以下の機能（ｆ１０９−１）〜（ｆ１０９−２）をもっている。
【００４０】
（ｆ１０９−１） 分散部分データ生成部１０５により生成された各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する機能。
【００４１】
（ｆ１０９−２） 互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を通信部１１１を介して個別にｎ台の装置１００，２００，…，ｎ００に配布する機能。なお、制御部１０９は、分散情報Ｄ（０）〜Ｄ（ｎ−１）の漏洩防止の観点から、分散情報Ｄ（０）〜Ｄ（ｎ−１）を暗号化した状態で配布してもよい。
【００４２】
出力部１１０は、ディスプレイ装置やプリンタ装置等の通常の出力デバイスであり、制御部１０９により制御され、命令等の入力画面や、復元後の秘密情報Ｓ等の出力画面等を出力する機能をもっている。
【００４３】
通信部１１１は、制御部１０９により制御され、クライアント装置１００とネットワークＮＷとの間の通信インターフェイス機能をもっている。
【００４４】
一方、各保管サーバ装置２００〜ｎ００について説明する。
各保管サーバ装置２００〜ｎ００は、記憶する分散情報Ｄ（１）〜Ｄ（ｎ−１）が互いに異なる他は互いに同一構成のため、ここではｎ＝２の保管サーバ装置２００を代表例に挙げて説明する。
【００４５】
保管サーバ装置２００は、保存部２０１及び通信部２０２を備えている。
【００４６】
保存部２０１は、通信部２０２から読出／書込可能なハードウェア資源としての記憶装置であり、クライアント装置１００から配布された分散情報Ｄ（１）（＝Ｄ（ｎ−１）でｎ＝２）が記憶される。
【００４７】
通信部２０２は、クライアント装置１００から配布された分散情報Ｄ（１）を保存部２０１に書き込む機能と、クライアント装置１００から要求された分散情報Ｄ（１）を保存部２０１から読み出してこの分散情報Ｄ（１）をクライアント装置１００に返信する機能とをもっている。
【００４８】
なお、通信部２０２は、分散情報Ｄ（１）の漏洩防止の観点から、クライアント装置１００の認証機能を有してもよく、この場合、クライアント装置１００の認証の後、分散情報Ｄ（１）を返信する構成として設けられる。
【００４９】
ここで、各保管サーバ装置２００，３００，…，ｎ００は、他のクライアント装置や、ＵＳＢ(Universal Serial Bus)メモリ、携帯電話、ＰＤＡ(Personal Digital Assistants：携帯情報端末)に置き換え可能であり、あるいは外付けＨＤＤ(Hard Disc Drive: 固定磁気ディスク装置)などのように、コンピュータ以外の他の装置と置き換えることも可能である。
【００５０】
なお、各保管装置２００，３００，…，ｎ００は、他のクライアント装置に置き換えられる場合、前述同様に、分散部分データ生成部１０５や元データ復元部１０７などの機能を保持していてもよい。すなわち、秘密情報を復元できる装置は、クライアント装置１００以外にあってもよい。例えば、各保管装置２００，３００，…，ｎ００のうちの任意の台数の装置ｊ００，…が秘密情報を復元できる構成としてもよい。
【００５１】
なお、分散の場合も同様に、秘密情報を分散できる装置は、クライアント装置１００以外にあってもよい。例えば、各保管装置２００，３００，…，ｎ００のうちの任意の台数の装置ｊ００，…が分散情報を配布できる構成としてもよい。
【００５２】
また、各保管装置２００，３００，…，ｎ００がＵＳＢメモリや携帯電話などのように物理的な接続手段又は無線通信手段を有する装置に置き換えられる場合、ネットワークＮＷを省略してもよい。上述した各保管装置２００，３００，…，ｎ００を他の装置に置き換えた変形例は、以下の各実施形態でも同様に適用可能である。
【００５３】
次に、以上のように構成された秘密分散システムの動作を説明する。
始めに、ｎ人のメンバ（初期メンバ）に、秘密情報Ｓを（ｋ，ｎ）閾値法で分散した分散情報Ｄ（ｊ）を配布する場合を考える。このときｎは素数を選ばなければならない。従って、合成数のｎ人に分散情報を配布したい場合は、ｎ＜ｎ’でありかつｎ’が素数となるようなｎ’について秘密分散法を適用することになる。以下では（ｋ，ｎ）閾値法についての一例を示す。
【００５４】
（分散処理の動作）
クライアント装置１００においては、分散情報Ｄ（０）〜Ｄ（ｎ−１）を配布する前に、ビット長ｍの秘密情報Ｓが一時的に保存部１０１に記憶されているとする。
【００５５】
このとき、クライアント装置１００においては、図７に示すように、操作者の操作により、分散処理の開始命令が入力部１０２から入力されたとする（ＳＴ１）。
【００５６】
クライアント装置１００は、この開始命令に基づいて、分散処理を開始する。制御部１０９は、分散数をｎ、閾値をｋ、秘密情報Ｓのビット長をｍ、処理単位ビットをａと定める（ＳＴ１）。なお、秘密情報Ｓのビット長ｍは、保存部１０１内の秘密情報Ｓから分かる。処理単位ビットａは、分散データ生成部１３の仕様により予め定まっている。
【００５７】
続いて、制御部１０９は、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａを超える（ｍ／（ｎ−１）＞ａ）か否かを判定し（ＳＴ２）、処理単位ビットａを超える場合、ｎより大きい素数ｎ’を探索し、得られた素数ｎ’を分散数ｎと置き換えて（ＳＴ３）、ステップＳＴ１に戻る。
【００５８】
一方、ステップＳＴ２の判定結果が否の場合、制御部１０９は、分散数ｎ及び閾値ｋを生成行列生成部１０３に入力する。
【００５９】
生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇ（但し、任意のｋ個の列ベクトルがフルランク、行列Ｇのサイズはｋ（ｎ−１）×ｎ（ｎ−１）、列ベクトルのサイズはｋ（ｎ−１）×（ｎ−１)）を制御部１０９に出力する（ＳＴ４）。
【００６０】
以下、ステップＳＴ４における生成行列Ｇの生成処理の手順を図８〜図１５を用いて説明する。
【００６１】
図８に示すように、生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇを保存部１０１から検索する（ＳＴ４−１）。該当する生成行列Ｇが存在する場合、ＳＴ４−８へ進む。該当する生成行列Ｇが存在しない場合、図９に示すように、第０行がゼロベクトル、下（ｎ−１）×（ｎ−１）行列が単位行列と左右対称な行列（（０，ｎ-2）−要素，（１，ｎ-3）−要素，…，（ｎ-3，１）−要素，（ｎ-2，０）−要素が全て１で、他の要素は全て０の行列）から構成されるｎ行×（ｎ−１）列の第１小行列ｉを生成する（ＳＴ４−２）。
【００６２】
続いて、図１０に示すように、（最も左側の）第１小行列iの各列を上に１回巡回シフトさせたｎ×（ｎ−１）行列を新たな第１小行列i−１として、当該巡回シフト前の第１小行列ｉの左側に隣接させる（ＳＴ４−３）。iがｎ−１から１までＳＴ４−３を繰り返して、ｎ×n（ｎ−１）の第１部分行列を生成する。この第１部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第０行目から第ｎ-2行目に割り当てる（ＳＴ４−４）。（４，５）閾値法の例では、生成行列Ｇの０行目から３行目までの部分行列が生成される。
【００６３】
生成行列生成部１０３は、図１１に示すように、第０行がゼロベクトル、下（ｎ−１）×（ｎ−１）行列が単位行列から構成されるｎ行×（ｎ−１）列の第２小行列ｉを生成する（ＳＴ４−５）。
【００６４】
続いて図１２〜図１５に示すように、（最も右側の）第２小行列ｉの各列を下にｊ回巡回シフトさせたｎ×（ｎ−１）行列を新たな第２小行列ｉ＋１として、当該巡回シフト前の第２小行列ｉの右側に隣接させる（ＳＴ４−６）。ｉが１からｎ−１までＳＴ４−６を繰り返して、ｎ×ｎ（ｎ−１）の第２部分行列を生成する。この第２部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から（ｎ−１）（ｊ＋１）＋ｎ−２行目に割り当てて、ｊをインクリメントする（ＳＴ４−７）。ｊが０からｋ−２までＳＴ４−６〜ＳＴ４−７を繰り返して生成行列Ｇを生成する。（４，５）閾値法の例では、生成行列Ｇは図２に示すような構成となる。
【００６５】
しかる後、生成行列生成部１０３は、得られた生成行列Ｇを制御部１０９に出力する（ＳＴ４−８）。
【００６６】
以上により生成行列Ｇの生成処理が完了する。
【００６７】
ステップＳＴ４の完了後、制御部１０９は、秘密情報Ｓ、生成行列Ｇ、分散数ｎ及び閾値ｋを分散部分データ生成部１０５に入力する。
【００６８】
分散部分データ生成部１０５は、図７に示すように、秘密情報Ｓ及び分散数ｎに基づいて、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａと等しいか（ｍ／（ｎ−１）＝ａ）か否かを判定する（ＳＴ５）。
【００６９】
ステップＳＴ４の判定結果が否の場合、分散部分データ生成部１０５は、秘密情報Ｓをｎ−１個の分割秘密データＫ（１）〜Ｋ（ｎ−１）に分割した際の末尾の分割秘密データＫ（ｎ−１）をパディングする（パディング有）とし（ＳＴ６）、ステップＳＴ７に進む。
【００７０】
なお、パディングは、必ずしも末尾の分割秘密データＫ（ｎ-2）に行わなくても良く、他の分割秘密データＫ（ｊ）に行っても良い。但し、本実施形態では、秘密情報Ｓは４個にちょうど分割できた場合（パディング無し）を例に挙げて述べる。また、図２に示した如き、分散数ｎ＝５，閾値ｋ＝４の（４，５）閾値法を例に挙げて述べる。
【００７１】
ステップＳＴ５の判定の結果、処理単位ビットａと等しい場合、分散部分データ生成部１０５は、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、０≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する（ＳＴ７）。（４，５）閾値法の例では、分割秘密データＫ（１），…，Ｋ（４）が生成される。
【００７２】
次に、各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｇ≦ｋ−２）と列番号（但し、１≦ｈ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する（ＳＴ７）。（４，５）閾値法の例では、乱数データＵ（０，１），…，Ｕ（２，４）が生成される。
【００７３】
分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）及び生成行列Ｇに基づいて、ｎ（ｎ−１）個の分散部分データ（Ｄ（０，０），…，Ｄ（ｊ，ｉ），…，Ｄ（ｎ−１，ｎ−２））＝（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））Ｇを算出する（ＳＴ８）。なお、処理単位ビットａにあわせて、生成行列Ｇの要素が１の場合はａ×ａのＧＦ（２）上の単位行列、０の場合はａ×ａのＧＦ（２）上のゼロ行列として扱う。（４，５）閾値法の例では、図４、図５に示したように、２０個の分散部分データＤ（ｊ，ｉ）が生成される。例えば、分散部分データＤ（０，０）の算出過程を図１６に示す。
【００７４】
しかる後、分散部分データ生成部１０５は、得られた分散部分データｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を制御部１０９に出力する。
【００７５】
制御部１０９は、各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する（ＳＴ９）。ヘッダ情報Ｈ（ｊ）には、Ｋ（ｎ−１）に対するパディングの有無、元データのサイズなどの情報が含まれる。
【００７６】
制御部１０９は、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別にｎ個の保存部１０１，２０１，…，ｎ０１に配布するように、分散情報Ｄ（０）を保存部１０１に書き込み、分散情報Ｄ（１），…，Ｄ（ｎ−１）を個別に保管サーバ装置２００，…，ｎ００に配布する（ＳＴ１０）。（４，５）閾値法の例では、５個の分散情報Ｄ（０），…，Ｄ（４）が配布される。各保管サーバ装置２００〜５００では、配布された分散情報Ｄ（１），…，Ｄ（４）を保存部２０１〜５０１に記憶する。
【００７７】
以上により、秘密情報の分散処理が完了する。
【００７８】
なお、（４，５）閾値法において、必ずしも５個の分散情報Ｄ（０）〜Ｄ（４）を配布する必要は無い。例えば４個の分散情報Ｄ（０）〜Ｄ（３）を配布しておき、残り１個の分散情報Ｄ（４）を新メンバが追加されたときに新メンバに配布してもよい。
【００７９】
（復元処理の動作）
クライアント装置１００においては、操作者の操作により、復元処理の開始命令が入力部１０２から入力されたとする。
【００８０】
クライアント装置１００は、この開始命令に基づいて、図１７に示すように、復元処理を開始する。制御部１０９は、ｎ台の装置１００，…，ｎ００に配布したｎ個の分散情報Ｄ（０）〜Ｄ（ｎ−１）のうち、任意のｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）（但し、０≦ｉ_ｊ≦ｎ−１）を収集する（ＳＴ１１）。
【００８１】
制御部１０９は、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）のヘッダ情報Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１を取得する（ＳＴ１２）。取得できた場合は、ＳＴ１５へ進む。取得できなかった場合は、Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から生成行列Ｇのｋ個の列ベクトルｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ）を得ると、このｋ個の列ベクトルから生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））を形成して取得する（ＳＴ１３）。
【００８２】
次に、制御部１０９は、生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））を逆行列生成部１０４に入力する。
【００８３】
逆行列生成部１０４は、生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））から生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１を算出する（ＳＴ１４）。
【００８４】
（４，５）閾値法の例では、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）に対応する生成行列Ｇの部分行列（（ｇ（Ｄ（１）），ｇ（Ｄ（２）），ｇ（Ｄ（３）），ｇ（Ｄ（４）））は図２に示したような行列になり、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）に対応する生成行列Ｇの部分逆行列（（ｇ（Ｄ（１）），ｇ（Ｄ（２）），ｇ（Ｄ（３）），ｇ（Ｄ（４）））−１は図３に示したような行列となる。
【００８５】
逆行列生成部１０４は、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１を出力する（ＳＴ１５）。
【００８６】
制御部１０９は、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１と分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）を元データ復元部１０７に入力する。
【００８７】
元データ復元部１０７は、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）のヘッダ情報Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から、図１７に示すように、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）であることを解析する（ＳＴ１６）。（４，５）閾値法の例では、例えば分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）であることを確認する。
【００８８】
次に、分散情報からなる行列（Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k））と生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））−１の行列の積を算出する（ＳＴ１７）。なお、処理単位ビットａにあわせて、生成行列Ｇの要素が１の場合はａ×ａのＧＦ（２）上の単位行列、０の場合はａ×ａのＧＦ（２）上のゼロ行列として扱う。
【００８９】
次に、計算結果のｉ＋１列目のデータをＫ（ｉ）に割り当てて、分割秘密データＫ（１），…，Ｋ（ｎ−１）を算出する。（４，５）閾値法の例では、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）から復元した場合、図１８〜図２２に示したように、分割秘密データＫ（１），Ｋ（２），Ｋ（３），Ｋ（４）が算出される。
【００９０】
制御部１０９は、分割秘密データＫ（１），…，Ｋ（ｎ−１）に対して、ヘッダ情報Ｈ（ｉ），Ｈ（ｊ）に基づいて、パディングなどの処理があれば除去する。
【００９１】
しかる後、制御部１０９は、分割秘密データＫ（１），…，Ｋ（ｎ−１）を互いに連接することにより、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（ｎ−１）を復元する（ＳＴ１８）。この例では、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（４）が復元される。
【００９２】
上述したように本実施形態によれば、生成行列Ｇを用いて分散部分データを生成する構成により、秘密情報の分散や復元の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現することができる。
【００９３】
また、本実施形態は、非特許文献２，３との相違を明確にする観点から閾値４以上として述べたが、閾値が２又は３でも実施できることはいうまでもない。このように本実施形態は、分散数ｎ及び閾値ｋが限定されないので、各種のシステムへの応用範囲を広げることができる。
【００９４】
また、本実施形態の分散・復元処理は、多項式補間が不要であり、ＸＯＲのみで実行するため、前述した高速に実行可能なことに加え、大容量データを扱うのに好適であり、低スペック機器でも秘密分散を実行できる利点を有する。
【００９５】
なお、本実施形態は、生成行列生成部１０３により生成行列Ｇを生成し、逆行列生成部１０４により逆行列を生成した場合について説明したが、これに限らず、分散数ｎ及び閾値ｋが予め分かっていれば、図２３に示すように、生成行列生成部１０３及び逆行列生成部１０４に代えて、予め生成行列Ｇ及びＧの逆行列のデータが保存された読出／書込可能な記憶装置としての行列保存部１１２を備えた構成に変形してもよい。このように変形しても、生成行列Ｇ及び逆行列による（ｋ，ｎ）閾値法を実現することができる。
【００９６】
また同様に、分散数ｎと閾値ｋとの組合せ毎に、予め生成行列Ｇ及びＧの逆行列のデータを行列保存部１１２に保存しておき、入力されたｎ，ｋの値を検索キーにして、行列保存部１１２から生成行列Ｇ及びＧの逆行列のデータを読み出す構成に変形してもよいことはいうまでもない。
【００９７】
（第２の実施形態）
図２４は本発明の第２の実施形態に係る秘密分散システムの構成を示す模式図である。
【００９８】
本実施形態は、第１の実施形態の変形例であり、分散アルゴリズムにより分散可能な（ｋ，ｎ）閾値法の秘密分散システムとなっている。これに伴い、前述した生成行列生成部１０３及び逆行列生成部１０４が省略され、分散部分データ生成部１０５ａ及び制御部１０９ａの機能が変更されている。
【００９９】
分散部分データ生成部１０５ａは、制御部１０９ａにより制御され、保存部１０１に一時的に記憶された秘密情報Ｓに基づいて、図４、図５に一例（ｋ＝４，ｎ＝５の例）を示すように、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を生成する機能をもっている。具体的には、分散部分データ生成部１０５ａは、以下の各機能（ｆ１０５ａ−１）〜（ｆ１０５ａ−６）をもっている。
【０１００】
（ｆ１０５ａ−１） 保存部１０１に記憶された秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する機能。
【０１０１】
（ｆ１０５ａ−２） 各分割秘密データのサイズと同一サイズのゼロ値データを作成し、作成結果に行番号ｊ＝０を割り当てて分割秘密データＫ（０）を生成する機能。
【０１０２】
（ｆ１０５ａ−３） 各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する機能。
【０１０３】
（ｆ１０５ａ−４） 各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する機能。なお、各乱数Ｕ（ｈ，ｇ）は、互いに異なる値である。
【０１０４】
（ｆ１０５ａ−５） 乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）に基づいて、ｎ×（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する機能（但し、(+)は排他的論理和を表す記号）。
【０１０５】
なお、Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）＝Ｕ（ｈ，０）（＝０）の場合、必ずしもＵ（ｈ，０）の項を計算する必要はなく、例えばＵ（０，３）(+)Ｕ（１，４）(+)Ｕ（２，０）をＵ（０，３）(+)Ｕ（１，４）としてもよい。このように、Ｕ（ｈ，０）（＝０）の場合、Ｕ（ｇ，０）の項を計算する必要が無いことは、本明細書中の他の箇所でも同様である。
【０１０６】
（ｆ１０５ａ−６） 分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する機能（但し、(+)は排他的論理和を表す記号）。
【０１０７】
なお、Ｋ（ｊ−ｉ(mod ｎ)）＝Ｋ（０）（＝０）の場合、必ずしもＫ（０）の項を計算する必要は無く、例えばＫ（０）の項の計算無しにＤ（ｊ，ｉ）＝Ｒ（ｊ，ｉ）としてもよい。このように、Ｋ（０）（＝０）の場合、必ずしもＫ（０）の項を計算する必要が無いことは、本明細書中の他の箇所でも同様である。
【０１０８】
制御部１０９ａは、入力部１０２から入力される命令に基づいて、後述する図２５及び図２６に示すフローチャートに基づいて、各部１０１，１０５ａ〜１０８，１１０，１１１を制御する機能をもっている。
【０１０９】
次に、以上のように構成された秘密分散システムの動作を説明する。ここでは（ｋ，ｎ）閾値法を例に挙げて述べる。
【０１１０】
始めに、ｎ人のメンバ（初期メンバ）に、秘密情報Ｓを（ｋ，ｎ）閾値法で分散した分散情報Ｄ（ｊ）を配布する場合を考える。このときｎは素数を選ばなければならない。従って、合成数のｎ人に分散情報を配布したい場合は、ｎ＜ｎ’でありかつｎ’が素数となるようなｎ’について秘密分散法を適用することになる。以下では（ｋ，ｎ）閾値法についての一例を示す。
【０１１１】
（分散処理の動作）
クライアント装置１００においては、分散情報Ｄ（０）〜Ｄ（ｎ−１）を配布する前に、ビット長ｍの秘密情報Ｓが一時的に保存部１０１に記憶されているとする。
【０１１２】
このとき、クライアント装置１００においては、図２５に示すように、操作者の操作により、分散処理の開始命令が入力部１０２から入力されたとする。
【０１１３】
クライアント装置１００は、この開始命令に基づいて、分散処理を開始する。制御部１０９ａは、秘密情報Ｓのビット長をｍ、分散数をｎ、処理単位ビットをａと定める（ＳＴ２１）。なお、秘密情報Ｓのビット長ｍは、保存部１０１内の秘密情報Ｓから分かる。処理単位ビットａは、分散データ生成部１３の仕様により予め定まっている。
【０１１４】
続いて、制御部１０９ａは、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａを超える（ｍ／（ｎ−１）＞ａ）か否かを判定し（ＳＴ２２）、処理単位ビットａを超える場合、ｎより大きい素数ｎ’を探索し、得られた素数ｎ’を分散数ｎと置き換えて（ＳＴ２３）、ステップＳＴ２１に戻る。
【０１１５】
一方、ステップＳＴ２２の判定の結果が否の場合、制御部１０９ａは、秘密情報Ｓ及び分散数ｎを分散部分データ生成部１０５ａに入力する。
【０１１６】
分散部分データ生成部１０５ａは、秘密情報Ｓ及び分散数ｎに基づいて、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａと等しいか（ｍ／（ｎ−１）＝ａ）か否かを判定する（ＳＴ２４）。
【０１１７】
ステップＳＴ２４の判定結果が否の場合、分散部分データ生成部１０５ａは、秘密情報Ｓをｎ−１個の分割秘密データＫ（１）〜Ｋ（ｎ−１）に分割した際の末尾の分割秘密データＫ（ｎ−１）をパディングする（パディング有）とし（ＳＴ２５）、ステップＳＴ２６に進む。
【０１１８】
なお、パディングは、必ずしも末尾の分割秘密データＫ（ｎ-2）に行わなくても良く、他の分割秘密データＫ（ｊ）に行っても良い。但し、本実施形態では、秘密情報Ｓは４個にちょうど分割できた場合（パディング無し）を例に挙げて述べる。また、図４、図５に示した如き、分散数ｎ＝５，閾値ｋ＝４の（４，５）閾値法を例に挙げて述べる。
【０１１９】
ステップＳＴ２４の判定の結果、処理単位ビットａと等しい場合、分散部分データ生成部１０５ａは、図２６に示すように、ステップＳＴ２６を開始する。
【０１２０】
すなわち、分散部分データ生成部１０５ａは、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、０≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する。（４，５）閾値法の例では、分割秘密データＫ（１），…，Ｋ（４）が生成される。
【０１２１】
また、分散部分データ生成部１０５ａは、各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて分割秘密データＫ（０）を生成する（ＳＴ２６−１）。
【０１２２】
さらに、分散部分データ生成部１０５ａは、各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する。
【０１２３】
次に、各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する（ＳＴ２６−２）。
【０１２４】
そして、乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、乱数データＲ（ｊ，ｉ）＝０としつつ（ＳＴ２６−３）、ｈを０からｋ−２まで繰り返してｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する（ＳＴ２６−４）。（４，５）閾値法の例では、乱数データＲ（０，０），…，Ｒ（４，３）が生成される。
【０１２５】
次に、分散部分データ生成部１０５ａは、分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び乱数データＲ（０，０），…，Ｒ（ｊ，ｉ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する（ＳＴ２７）。この算出は、行番号ｊを０からｎ−１まで繰り返すと共に、列番号ｉを０からｎ-2まで繰り返すことにより行う。（４，５）閾値法の例では、図４、図５に示したように、２０個の分散部分データＤ（ｊ，ｉ）が生成される。
【０１２６】
しかる後、分散部分データ生成部１０５ａは、得られた分散部分データｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を制御部１０９ａに出力する。
【０１２７】
制御部１０９ａは、各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する（ＳＴ２８）。ヘッダ情報Ｈ（ｊ）には、Ｋ（ｎ−１）に対するパディングの有無、元データのサイズなどの情報が含まれる。
【０１２８】
制御部１０９ａは、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別にｎ個の保存部１０１，２０１，…，ｎ０１に配布するように、分散情報Ｄ（０）を保存部１０１に書き込み、分散情報Ｄ（１），…，Ｄ（ｎ−１）を個別に保管サーバ装置２００，…，ｎ００に配布する（ＳＴ２９）。
【０１２９】
（４，５）閾値法の例では、５個の分散情報Ｄ（０），…，Ｄ（４）が配布される。各保管サーバ装置２００〜５００では、配布された分散情報Ｄ（１），…，Ｄ（４）を保存部２０１〜５０１に記憶する。
【０１３０】
以上により、秘密情報の分散処理が完了する。
【０１３１】
なお、（４，５）閾値法において、必ずしも５個の分散情報Ｄ（０）〜Ｄ（４）を配布する必要は無い。例えば４個の分散情報Ｄ（０）〜Ｄ（３）を配布しておき、残り１個の分散情報Ｄ（４）を新メンバが追加されたときに新メンバに配布してもよい。
【０１３２】
上述したように本実施形態によれば、第１の実施形態の生成行列Ｇと同様の結果を得るアルゴリズムを用いて分散部分データを生成する構成により、秘密情報の分散の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現することができる。
【０１３３】
すなわち、本実施形態によれば、生成行列Ｇを用いずに、第１の実施形態と同様の作用効果を得ることができる。
【０１３４】
（第３の実施形態）
次に、本発明の第３の実施形態に係る秘密分散システムについて説明する。
本実施形態は、第１の実施形態の変形形態であり、第１の実施形態とは異なるビットパターンの生成行列Ｇと、その生成行列Ｇを利用した分散処理とに関する。
【０１３５】
ここで、生成行列Ｇは、図２７にｋ＝４，ｎ＝５とした（４，５）閾値法の例を示すように、図１１〜図１５に示したｊ＝０〜２の場合の第４〜１５行目と同じ値の第０〜１１行目を有し、図２８及び図２９に示す如きｊ＝３の場合と同じ値の第１２〜１５行目を有している。
【０１３６】
この生成行列Ｇは、図３０に示すように、図８の第１小行列ｉに関するステップＳＴ４−２〜ＳＴ４−４を省略し、図８の第２小行列ｉに関するステップＳＴ４−１，ＳＴ４−５，ＳＴ４−６と同様の各ステップＳＴ４−１，ＳＴ４−５及びＳＴ４−６と、図８のステップＳＴ４−７に代えて割当て行をＧの第（ｎ−１）ｊ行目から第（ｎ−１）ｊ＋ｎ−２行目としたステップＳＴ４−７’とを備え、且つｊが０からｋ−１までステップＳＴ４−６及びＳＴ４−７’を繰り返し実行する生成方法により生成される。
【０１３７】
すなわち、生成行列生成部１０３は、入力された分散数ｎ及び閾値ｋが保存部１０１に記憶されたとき、保存部１０１内の分散数ｎ及び閾値ｋに基づいて、第０行がゼロベクトルであり、この第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列であるｎ行×（ｎ−１）列の第２小行列を生成する処理と、最も右側の第２小行列の各列を下にｊ回巡回シフトさせたｎ行×（ｎ−１）列の新たな第２小行列を当該巡回シフト前の第２小行列の右側に隣接させる第２隣接処理（但し、ｊ＝０，１，…，ｋ−１）と、第２隣接処理をｎ−１回実行し、ｎ行×n（ｎ−１）列の第２部分行列を生成する第２部分行列生成処理と、この第２部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第（ｎ−１）ｊ行目から第（ｎ−１）ｊ＋ｎ−２行目に割り当てて、生成行列Ｇの第（ｎ−１）ｊ行目から第（ｎ−１）ｊ＋ｎ−２行目までの部分行列を生成する第２部分行列割当て処理（但し、ｊ＝０，１，…，ｋ−１）と、第２隣接処理及び第２部分行列割当て処理におけるｊの値が初期値０から最終値ｋ−１までの間、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理を実行する毎に当該ｊの値を１だけ増加させつつ、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理をｋ回実行する処理と、ｋ回の第２部分割当て処理により割り当てられた第０行目から第（ｎ−１）（ｋ−１）＋ｎ−２行目までの部分行列とにより、ｋ（ｎ−１）行×ｎ（ｎ−１）列の生成行列Ｇを得る処理とを実行する機能をもっている。
【０１３８】
なお、本実施形態においては、第１小行列に関するステップＳＴ４−２〜ＳＴ４−４を省略したため、上述した第２小行列、第２部分行列、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理から「第２」の語句を省略してもよい。
【０１３９】
また、生成行列Ｇの変更に伴い、図３１のステップＳＴ８’及び図３２に示すように、分散部分データ算出時の生成行列Ｇに左側から積算される行列において、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）の右側に分散秘密データＫ（１）〜Ｋ（ｎ−１）が配置される。この配置は、前述した図７のステップＳＴ８とは逆の配置となっている。
【０１４０】
分散部分データＤ（ｊ，ｉ）は、図３３及び図５に一例（ｎ＝４，ｎ＝５）を示すように、ｎ（ｎ−１）個が分散部分データ生成部１０５により生成される。
【０１４１】
ここで、分散部分データ生成部１０５の機能（ｆ１０５−３）は、以下の機能（ｆ１０５−３’）のようになる。
【０１４２】
（ｆ１０５−３’） 乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）、分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、生成行列Ｇに基づいて、行列（Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と生成行列Ｇの積を算出し（但し、ＧＦ（２）上の演算）、計算結果のj×(ｎ−１)+ｉ列目のデータをＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を算出する（但し、０≦ｊ≦ｎ−１，０≦ｉ≦ｎ−２）機能。
【０１４３】
次に、以上のように構成された秘密分散システムの動作を説明する。
【０１４４】
（分散処理の動作）
いま、前述同様に、図３１に示すステップＳＴ１〜ＳＴ３が実行され、ステップＳＴ４’に進むとする。
【０１４５】
生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇ（但し、任意のｋ個の列ベクトルがフルランク、行列Ｇのサイズはｋ（ｎ−１）×ｎ（ｎ−１）、列ベクトルのサイズはｋ（ｎ−１）×（ｎ−１)）を制御部１０９に出力する（ＳＴ４’）。
【０１４６】
以下、ステップＳＴ４’における生成行列Ｇの生成処理の手順を図２８〜図３０を用いて説明する。
【０１４７】
図３０に示すように、生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇを保存部１０１から検索する（ＳＴ４−１）。該当する生成行列Ｇが存在する場合、ＳＴ４−８へ進む。該当する生成行列Ｇが存在しない場合、図１１に示したように、第０行がゼロベクトル、下（ｎ−１）×（ｎ−１）行列が単位行列から構成されるｎ行×（ｎ−１）列の第２小行列ｉを生成する（ＳＴ４−５）。
【０１４８】
続いて図１２〜図１４の上方及び図２８に示したように、（最も右側の）第２小行列ｉの各列を下にｊ回巡回シフトさせたｎ×（ｎ−１）行列を新たな第２小行列ｉ＋１として、当該巡回シフト前の第２小行列ｉの右側に隣接させる（ＳＴ４−６）。ｉが１からｎ−１までＳＴ４−６を繰り返して、ｎ×ｎ（ｎ−１）の第２部分行列を生成する。この第２部分行列の第１行目から第ｎ−１行目を図２９に示すように生成行列Ｇの第（ｎ−１）ｊ行目から（ｎ−１）ｊ＋ｎ−２行目に割り当てて、ｊをインクリメントする（ＳＴ４−７’）。ｊが０からｋ−１までＳＴ４−６〜ＳＴ４−７’を繰り返して生成行列Ｇを生成する。（４，５）閾値法の例では、生成行列Ｇは図２７に示すような構成となる。
【０１４９】
しかる後、生成行列生成部１０３は、得られた生成行列Ｇを制御部１０９に出力する（ＳＴ４−８）。
【０１５０】
以上により生成行列Ｇの生成処理が完了する。
【０１５１】
ステップＳＴ４の完了後、前述同様に、図３１に示すステップＳＴ５〜ＳＴ７が実行され、ステップＳＴ８’に進むとする。
【０１５２】
分散部分データ生成部１０５は、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）及び分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）からなる行列（Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と生成行列Ｇの積を算出し（ＳＴ８’）、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を算出する。（４，５）閾値法の例では、図３３及び図５に示したように、２０個の分散部分データＤ（ｊ，ｉ）が生成される。例えば、分散部分データＤ（０，０）の算出過程を図３２に示す。
【０１５３】
以下、前述同様に、ステップＳＴ９及びＳＴ１０が実行され、分散処理が完了する。
【０１５４】
（復元処理の動作）
復元処理の動作は、図１７を用いて前述同様に実行される。厳密には、前述とは異なる生成行列Ｇのビットパターンに伴い、生成行列Ｇの任意のｋ個の列ベクトルからなる部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））のビットパターンと、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１のビットパターンとが、前述とは異なるものとなる。但し、ビットパターンが異なっても、復元処理の動作が前述同様に実行されることに変わりはない。
【０１５５】
上述したように本実施形態によれば、第１の実施形態とは異なるビットパターンの生成行列Ｇを生成する構成としても、第１の実施形態と同様の効果を得ることができる。
【０１５６】
また、第１の実施形態のステップＳＴ４−２〜ＳＴ４−４を省略した構成により、生成行列Ｇの生成アルゴリズムを簡素化することができる。補足すると、ステップＳＴ４−２〜ＳＴ４−４を省略したことにより、ステップＳＴ４−６〜ＳＴ４−７’の繰り返し回数ｊが１回増えているが、同様なステップの繰り返しなので、生成アルゴリズムは簡素化されている。
【０１５７】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１５８】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１５９】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１６０】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１６１】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１６２】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１６３】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１６４】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１６５】
【図１】本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図である。
【図２】同実施形態における生成行列の一例を示す模式図である。
【図３】同実施形態における逆行列の一例を示す模式図である。
【図４】同実施形態における分散部分データの一例を示す模式図である。
【図５】同実施形態における乱数データの一例を示す模式図である。
【図６】同実施形態におけるヘッダ情報及び分散情報の一例を示す模式図である。
【図７】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図８】同実施形態における生成行列生成処理の動作を説明するためのフローチャートである。
【図９】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１０】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１１】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１２】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１３】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１４】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１５】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１６】同実施形態における分散部分データの算出過程を説明するための模式図である。
【図１７】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図１８】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図１９】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２０】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２１】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２２】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２３】同実施形態における変形例を説明するための模式図である。
【図２４】本発明の第２の実施形態に係る秘密分散システムの構成を示す模式図である。
【図２５】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図２６】同実施形態における分割秘密データ及び乱数の生成動作を説明するためのフローチャートである。
【図２７】本発明の第３の実施形態における生成行列の一例を示す模式図である。
【図２８】同実施形態における生成行列の生成動作を説明するための模式図である。
【図２９】同実施形態における生成行列の生成動作を説明するための模式図である。
【図３０】同実施形態における生成行列生成処理の動作を説明するためのフローチャートである。
【図３１】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図３２】同実施形態における分散部分データの算出過程を説明するための模式図である。
【図３３】同実施形態における分散部分データの一例を示す模式図である。
【符号の説明】
【０１６６】
１００…クライアント装置、１０１〜ｎ０１…保存部、１０２…入力部、１０３…生成行列生成部、１０４…逆行列生成部、１０５，１０５ａ…分散部分データ生成部、１０６…ハッシュ値生成部、１０７…元データ復元部、１０８…ハッシュ値検証部、１０９，１０９ａ…制御部、１１０…出力部、１１１，２０２〜ｎ０２…通信部、２００，３００，…，ｎ００…保管サーバ装置、ＮＷ…ネットワーク。
【技術分野】
【０００１】
本発明は、（ｋ，ｎ）閾値法を用いた秘密分散装置、方法及びプログラムに係り、例えば多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現し得る秘密分散装置、方法及びプログラムに関する。
【背景技術】
【０００２】
一般に、暗号化鍵などの秘密情報を紛失した場合の対策としては、予め秘密情報のコピーを作成しておくことが有効である。しかしながら、秘密情報のコピーを作成すると、盗難のリスクが高くなるという問題が生じる。このような問題を解決する手法として、１９７９年にシャミア（Shamir）が（ｋ，ｎ）閾値法と呼ばれる秘密分散法を提案している（例えば、非特許文献１参照）。
【０００３】
（ｋ，ｎ）閾値法では、秘密情報をｎ個の分散情報に分割し、ｎ個の分散情報の中から任意のｋ個を集めれば元の秘密情報を復元できるが、ｋ−１個の分散情報からでは、元の秘密情報に関する情報を全く得られない。すなわち、（ｋ，ｎ）閾値法は、閾値ｋを境にした秘密情報の復元特性をもっている（なお、１＜ｋ＜ｎ）。
【０００４】
このため、（ｋ，ｎ）閾値法によれば、ｋ−１個以下の分散情報が漏洩しても元の秘密情報が安全であり、ｎ−ｋ個以下の分散情報を紛失しても元の秘密情報を復元できるといった管理を実現できる。
【０００５】
しかしながら、シャミアの（ｋ，ｎ）閾値法では、秘密情報の分散や復元の処理を、多くの計算量を要する多項式補間により実現するので、大量のデータを秘密分散するためには、高速な計算機を必要とする不都合がある。
【０００６】
一方、このような不都合を解決し、計算量を大幅に削減し得る（ｋ，ｎ）閾値法として、藤井らの方式と栗原らの方式が知られている（例えば、非特許文献２、非特許文献３参照）。ここで、藤井らの方式と栗原らの方式は、秘密情報の分散処理や復元処理を排他的論理和演算のみで実現するので、高速に実行可能となっている。
【０００７】
しかしながら、藤井らの方式と栗原らの方式は、閾値ｋが２又は３に限定されるという不都合がある。
【非特許文献１】A. Shamir: “How to share a secret", Communications of the ACM, 22, 11, pp.612-613 (1979)
【非特許文献２】藤井吉弘,多田美奈子,保坂範和,栃窪孝也,加藤岳久: “高速な(2,ｎ)閾値法の構成とシステムへの応用", CSS2005予稿集, (2005)
【非特許文献３】栗原淳,清本晋作,福島和英,田中俊昭: “XORを用いた(3,ｎ)閾値秘密分散法", SCIS2007予稿集, (2007)
【発明の開示】
【発明が解決しようとする課題】
【０００８】
以上説明したように、シャミアによる（ｋ，ｎ）閾値法では、多項式補間を用いるため、高速な計算機が必要となる不都合がある。一方、藤井らの方式と栗原らの方式は、閾値ｋが２又は３に限定されるという不都合がある。
【０００９】
本発明は上記実情を考慮してなされたもので、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現し得る秘密分散装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
第１の発明は、秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置であって、１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段と、前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する手段と、前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積を算出し（但し、ＧＦ（２）上の演算）、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、０≦ｊ≦ｎ−１、０≦ｉ≦ｎ−２）を算出する手段と、前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段とを備えた秘密分散装置である。
【００１１】
第２の発明は、秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）型の秘密分散装置であって、前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて第２分割秘密データＫ（０）を生成する手段と、前記各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する手段と、前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する手段と、前記乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、ｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する手段と（但し、(+)は排他的論理和を表す記号）、前記分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び前記乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する手段と、前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段とを備えた秘密分散装置である。
【００１２】
なお、第１及び第２の各発明は、「装置」として表現したが、これに限らず、「プログラム」、「プログラムを記憶した記憶媒体」又は「方法」として表現してもよい。
【００１３】
（作用）
第１の発明は、生成行列Ｇを用いて分散部分データを生成する構成により、秘密情報の分散や復元の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現することができる。
【００１４】
第２の発明は、前述した生成行列Ｇと同様に分散部分データを生成する構成により、秘密情報の分散の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現することができる。
【発明の効果】
【００１５】
以上説明したように本発明によれば、多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の各実施形態について図面を用いて説明する。なお、以下の各装置は、装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。
【００１７】
（第１の実施形態）
図１は本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図である。この秘密分散システムは、１台のクライアント装置１００及びｎ−１台の保管サーバ装置２００，３００，…，ｎ００が互いにインターネット等のネットワークＮＷを介して接続されている。
【００１８】
これら合計ｎ台の装置１００，２００，３００，…，ｎ００は、（ｋ，ｎ）閾値法におけるｎ人のメンバに対応する。特に、ｎ台の装置１００，２００，…，ｎ００が個別に有するｎ個の保存部１０１，２０１，…，ｎ０１は、ｎ人のメンバが個別に有するｎ個の記憶装置に対応する。各装置１００，２００，３００，…，ｎ００には、それぞれ分散情報の配布順番を示すｊ番号（行番号）が割当てられている。例えば、クライアント装置１００には、ｊ＝０番目が割り当てられており、保管サーバ装置２００にはｊ＝１番目が割り当てられている。保管サーバ装置３００にはｊ＝２番目が割り当てられ、…、保管サーバ装置ｎ００にはｊ＝ｎ−１番目が割り当てられている。
【００１９】
ここで、クライアント装置１００は、秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ台の装置１００，２００，…，ｎ００に配布し、且つ、ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置を実現するものである。なお、分散情報の個数はｋ個以上であればよい。この閾値ｋは２以上が使用可能であるが、非特許文献２，３との相違を明確にする観点から、本実施形態では４以上を用いている。例えばｋ＝４，ｎ＝４とし、秘密情報Ｓをｎ−１（＝３）個に分割して後述するＫ（１），Ｋ（２），Ｋ（３）とし、配布した４個の分散情報Ｄ（０），Ｄ（１），Ｄ（２），Ｄ（３）から秘密情報Ｓを復元してもよい。
【００２０】
クライアント装置１００は、保存部１０１、入力部１０２、生成行列生成部１０３、逆行列生成部１０４、分散部分データ生成部１０５、ハッシュ値生成部１０６、元データ復元部１０７、ハッシュ値検証部１０８、制御部１０９、出力部１１０及び通信部１１１が互いにバスを介して接続されている。
【００２１】
保存部１０１は、制御部１０９から読出／書込可能なハードウェア資源としての記憶装置であり、後述する分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、秘密情報Ｓが一時的に記憶される。また、保存部１０１は、分散情報Ｄ（０）〜Ｄ（ｎ−１）が作成されると、分散情報作成情報が記憶され、分散情報が配布された後、ｊ＝０番目の分散情報Ｄ（０）が記憶されると共に、秘密情報Ｓが削除される。ここで、分散情報作成情報は、分散情報Ｄ（ｊ）の識別情報ｊと、分散情報Ｄ（ｊ）の配布先識別情報（装置ＩＤ、装置のアドレス情報等）とが互いに関連付けられた情報である。
【００２２】
入力部１０２は、キーボード又はマウス等の通常の入力デバイスであり、操作者の操作により、分散処理又は復号処理の開始等の命令や、秘密情報Ｓ等の情報をクライアント装置１００内に入力する機能をもっている。
【００２３】
生成行列生成部１０３は、制御部１０９により制御され、図２にｋ＝４，ｎ＝５とした（４，５）閾値法の例を示す如き、１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する機能をもっている。但し、生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列である。ＧＦ（２）は位数２の有限体である。フルランクとは、行列の基本変形を施して得られるランク（rank：階数）がフル（full：満杯）（＝ｋ（ｎ−１））であり、線形独立であることを意味している。
【００２４】
具体的には、生成行列生成部１０３は、入力された分散数ｎ及び閾値ｋが保存部１０１に記憶されたとき、保存部１０１内の分散数ｎ及び閾値ｋに基づいて、第０行がゼロベクトルであり、第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列とは左右対称な行列であるｎ行×（ｎ−１）列の第１小行列を生成する処理と、最も左側の第１小行列の各列を上に１回巡回シフトさせたｎ行×（ｎ−１）列の新たな第１小行列を当該巡回シフト前の第１小行列の左側に隣接させる第１隣接処理と、第１隣接処理をｎ−１回実行し、ｎ行×n（ｎ−１）列の第１部分行列を生成する処理と、この第１部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第０行目から第ｎ-2行目に割り当てて、生成行列Ｇの第０行目から第ｎ−２行目までの部分行列を生成する第１部分行列割当て処理と、第０行がゼロベクトルであり、この第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列であるｎ行×（ｎ−１）列の第２小行列を生成する処理と、最も右側の第２小行列の各列を下にｊ回巡回シフトさせたｎ行×（ｎ−１）列の新たな第２小行列を当該巡回シフト前の第２小行列の右側に隣接させる第２隣接処理（但し、ｊ＝０，１，…，ｋ−２）と、第２隣接処理をｎ−１回実行し、ｎ行×n（ｎ−１）列の第２部分行列を生成する第２部分行列生成処理と、この第２部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目に割り当てて、生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目までの部分行列を生成する第２部分行列割当て処理（但し、ｊ＝０，１，…，ｋ−２）と、第２隣接処理及び第２部分行列割当て処理におけるｊの値が初期値０から最終値ｋ−２までの間、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理を実行する毎に当該ｊの値を１だけ増加させつつ、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理をｋ−１回実行する処理と、第１部分割当て処理により割り当てられた第０行目から第ｎ−２行目までの部分行列と、ｋ−１回の第２部分割当て処理により割り当てられた第ｎ−１行目から第（ｎ−１）（ｋ−１）＋ｎ−２行目までの部分行列とにより、ｋ（ｎ−１）行×ｎ（ｎ−１）列の生成行列Ｇを得る処理とを実行する機能をもっている。
【００２５】
逆行列生成部１０４は、制御部１０９により制御され、生成行列Ｇの逆行列を生成するものであり、例えば図３にｋ＝４，ｎ＝５とした（４，５）閾値法の例を示す如き、収集されたｋ個の列ベクトルから形成される生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））の逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’を算出する機能をもっている。
【００２６】
ここで、ｇ（Ｄ（＊））は、＊個目の分散情報Ｄ（＊）を算出するのに使用した生成行列Ｇの部分行列であり、列ベクトルともいう。また、（ｉ_1）の表記は、任意の１個目を表し、（ｉ_j）の表記は任意のｊ個目を表し、（ｉ_k）の表記は任意のｋ個目を表している。すなわち、カッコ内の左側のｉと下線“ｉ＿”は、“任意の”を表している（表記“ｉ＿”のｉは行番号ではない）。また、例えばＤ（ｉ_1）は、任意の１個目のＤ（＊）なので、Ｄ（０）〜Ｄ（４）のいずれでもよい。
【００２７】
分散部分データ生成部１０５は、制御部１０９により制御され、保存部１０１に一時的に記憶された秘密情報Ｓに基づいて、図４、図５に一例（ｋ＝４，ｎ＝５の例）を示すように、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を生成する機能をもっている。具体的には、分散部分データ生成部１０５は、以下の各機能（ｆ１０５−１）〜（ｆ１０５−３）をもっている。
【００２８】
（ｆ１０５−１） 保存部１０１に記憶された秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、０≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する機能。
【００２９】
（ｆ１０５−２） 各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、１≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する機能。なお、各乱数Ｕ（ｈ，ｇ）は、互いに独立である。
【００３０】
（ｆ１０５−３） 分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）、生成行列Ｇに基づいて、行列（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と生成行列Ｇの積を算出し（但し、ＧＦ（２）上の演算）、計算結果のj×(ｎ−１)+ｉ列目のデータをＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を算出する（但し、０≦ｊ≦ｎ−１，０≦ｉ≦ｎ−２）機能。
【００３１】
ハッシュ値生成部１０６は、制御部１０９により制御され、制御部１０９からバスを介してヘッダ情報Ｈ（ｊ）が入力されると、ヘッダ情報Ｈ（ｊ）のハッシュ値ｈ（Ｈ（ｊ））を生成し、得られたハッシュ値ｈ（Ｈ（ｊ））をバスに出力する機能をもっている。なお、ハッシュ値生成部１０６は、ヘッダ情報Ｈ（ｊ）を検証しない場合、省略可能である。
【００３２】
元データ復元部１０７は、制御部１０９に制御され、ｎ台の装置１００，…，ｎ００に配布されたｎ個の分散情報Ｄ（０）〜Ｄ（ｎ−１）のうち、任意のｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k）（但し、０≦ｉ_j≦ｎ−１）に基づいて、秘密情報Ｓを復元する秘密情報復元機能をもっている。具体的には元データ復元部１０７は、以下の各機能（ｆ１０７−１）〜（ｆ１０７−２）をもっている。
【００３３】
（ｆ１０７−１） 収集されたｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k）及び生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’に基づき、行列（Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k））と逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’の積を算出し、計算結果のｉ列目のデータをＫ（ｉ＋１）に割り当てて、分割秘密データＫ（１），…，Ｋ（ｎ−１）とする機能。
【００３４】
（ｆ１０７−２） 復元されたｎ−１個の分割秘密データＫ（１），…，Ｋ（ｎ−１）を互いに連接することにより、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（ｎ−１）を復元する機能（但し、‖は連接を表す記号）。
【００３５】
ハッシュ値検証部１０８は、制御部１０９により制御され、制御部１０９からバスを介してヘッダ情報Ｈ（ｊ）及びそのハッシュ値ｈ（Ｈ（ｊ））が入力されると、ハッシュ値ｈ（Ｈ（ｊ））に基づいてヘッダ情報Ｈ（ｊ）を検証し、検証結果をバスに出力する機能をもっている。検証内容は、ヘッダ情報Ｈ（ｊ）から計算したハッシュ値と、入力されたハッシュ値ｈ（Ｈ（ｊ））との一致により、ヘッダ情報Ｈ（ｊ）を正当と判定する方式である。なお、ハッシュ値検証部１０８は、ヘッダ情報Ｈ（ｊ）を検証しない場合、省略可能である。
【００３６】
ここで、ヘッダ情報Ｈ（ｊ）は、図６の上方に一例を示すように、行番号ｊを示すデータ識別子、ヘッダのサイズを表すヘッダーサイズ、元データのサイズを表す元データサイズｍ、元の秘密情報Ｓの分割数を示す分割数ｎ−１、分散部分データＤ（ｊ，ｉ）の処理単位ビットを示す処理単位ビット長ａ、乱数Ｒ（ｊ，ｉ）のデータサイズを示す乱数データサイズａ、分割秘密データＫ（ｊ）のサイズを表す分割データサイズａ、パディングの有無やアルゴリズムを表すパディングアルゴリズム、ハッシュアルゴリズム情報（オプション）、生成行列Ｇの部分行列ｇ（Ｄ（ｊ））（オプション）、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））’（オプション）（但し、必ずｇ（Ｄ（j））を含む）などが考えられる。
【００３７】
ハッシュアルゴリズム情報は、ヘッダ情報のハッシュ値を算出し、ヘッダ情報の原本性を保証する場合などに追加される。すなわち、ハッシュアルゴリズム情報は、セキュリティの要件などに応じて追加又は省略される。但し、セキュリティの要件として予めシステムでハッシュアルゴリズムを決めている場合には、ハッシュアルゴリズム情報は、ヘッダ情報から省略可能である。
【００３８】
なお、分散情報Ｄ（ｊ）のデータフォーマットは、図６の下方に一例を示すように、ヘッダ情報Ｈ（ｊ）、そのハッシュ値ｈ（Ｈ（ｊ））、ｎ−１個の分散部分データＤ（ｊ，０），Ｄ（ｊ，１），…，Ｄ（ｊ，ｎ-2）から構成されている。ここで、ハッシュ値ｈ（Ｈ（ｊ））は、オプション（option）であり、ヘッダ情報Ｈ（ｊ）内のハッシュアルゴリズム情報と同様に、セキュリティの要件に応じて省略可能となっている。
【００３９】
制御部１０９は、入力部１０２から入力される命令に基づいて、後述する図７、図８及び図１７のフローチャートに基づいて、各部１０１，１０３〜１０８，１１０，１１１を制御する機能をもっている。また、制御部１０９は、例えば、以下の機能（ｆ１０９−１）〜（ｆ１０９−２）をもっている。
【００４０】
（ｆ１０９−１） 分散部分データ生成部１０５により生成された各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する機能。
【００４１】
（ｆ１０９−２） 互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を通信部１１１を介して個別にｎ台の装置１００，２００，…，ｎ００に配布する機能。なお、制御部１０９は、分散情報Ｄ（０）〜Ｄ（ｎ−１）の漏洩防止の観点から、分散情報Ｄ（０）〜Ｄ（ｎ−１）を暗号化した状態で配布してもよい。
【００４２】
出力部１１０は、ディスプレイ装置やプリンタ装置等の通常の出力デバイスであり、制御部１０９により制御され、命令等の入力画面や、復元後の秘密情報Ｓ等の出力画面等を出力する機能をもっている。
【００４３】
通信部１１１は、制御部１０９により制御され、クライアント装置１００とネットワークＮＷとの間の通信インターフェイス機能をもっている。
【００４４】
一方、各保管サーバ装置２００〜ｎ００について説明する。
各保管サーバ装置２００〜ｎ００は、記憶する分散情報Ｄ（１）〜Ｄ（ｎ−１）が互いに異なる他は互いに同一構成のため、ここではｎ＝２の保管サーバ装置２００を代表例に挙げて説明する。
【００４５】
保管サーバ装置２００は、保存部２０１及び通信部２０２を備えている。
【００４６】
保存部２０１は、通信部２０２から読出／書込可能なハードウェア資源としての記憶装置であり、クライアント装置１００から配布された分散情報Ｄ（１）（＝Ｄ（ｎ−１）でｎ＝２）が記憶される。
【００４７】
通信部２０２は、クライアント装置１００から配布された分散情報Ｄ（１）を保存部２０１に書き込む機能と、クライアント装置１００から要求された分散情報Ｄ（１）を保存部２０１から読み出してこの分散情報Ｄ（１）をクライアント装置１００に返信する機能とをもっている。
【００４８】
なお、通信部２０２は、分散情報Ｄ（１）の漏洩防止の観点から、クライアント装置１００の認証機能を有してもよく、この場合、クライアント装置１００の認証の後、分散情報Ｄ（１）を返信する構成として設けられる。
【００４９】
ここで、各保管サーバ装置２００，３００，…，ｎ００は、他のクライアント装置や、ＵＳＢ(Universal Serial Bus)メモリ、携帯電話、ＰＤＡ(Personal Digital Assistants：携帯情報端末)に置き換え可能であり、あるいは外付けＨＤＤ(Hard Disc Drive: 固定磁気ディスク装置)などのように、コンピュータ以外の他の装置と置き換えることも可能である。
【００５０】
なお、各保管装置２００，３００，…，ｎ００は、他のクライアント装置に置き換えられる場合、前述同様に、分散部分データ生成部１０５や元データ復元部１０７などの機能を保持していてもよい。すなわち、秘密情報を復元できる装置は、クライアント装置１００以外にあってもよい。例えば、各保管装置２００，３００，…，ｎ００のうちの任意の台数の装置ｊ００，…が秘密情報を復元できる構成としてもよい。
【００５１】
なお、分散の場合も同様に、秘密情報を分散できる装置は、クライアント装置１００以外にあってもよい。例えば、各保管装置２００，３００，…，ｎ００のうちの任意の台数の装置ｊ００，…が分散情報を配布できる構成としてもよい。
【００５２】
また、各保管装置２００，３００，…，ｎ００がＵＳＢメモリや携帯電話などのように物理的な接続手段又は無線通信手段を有する装置に置き換えられる場合、ネットワークＮＷを省略してもよい。上述した各保管装置２００，３００，…，ｎ００を他の装置に置き換えた変形例は、以下の各実施形態でも同様に適用可能である。
【００５３】
次に、以上のように構成された秘密分散システムの動作を説明する。
始めに、ｎ人のメンバ（初期メンバ）に、秘密情報Ｓを（ｋ，ｎ）閾値法で分散した分散情報Ｄ（ｊ）を配布する場合を考える。このときｎは素数を選ばなければならない。従って、合成数のｎ人に分散情報を配布したい場合は、ｎ＜ｎ’でありかつｎ’が素数となるようなｎ’について秘密分散法を適用することになる。以下では（ｋ，ｎ）閾値法についての一例を示す。
【００５４】
（分散処理の動作）
クライアント装置１００においては、分散情報Ｄ（０）〜Ｄ（ｎ−１）を配布する前に、ビット長ｍの秘密情報Ｓが一時的に保存部１０１に記憶されているとする。
【００５５】
このとき、クライアント装置１００においては、図７に示すように、操作者の操作により、分散処理の開始命令が入力部１０２から入力されたとする（ＳＴ１）。
【００５６】
クライアント装置１００は、この開始命令に基づいて、分散処理を開始する。制御部１０９は、分散数をｎ、閾値をｋ、秘密情報Ｓのビット長をｍ、処理単位ビットをａと定める（ＳＴ１）。なお、秘密情報Ｓのビット長ｍは、保存部１０１内の秘密情報Ｓから分かる。処理単位ビットａは、分散データ生成部１３の仕様により予め定まっている。
【００５７】
続いて、制御部１０９は、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａを超える（ｍ／（ｎ−１）＞ａ）か否かを判定し（ＳＴ２）、処理単位ビットａを超える場合、ｎより大きい素数ｎ’を探索し、得られた素数ｎ’を分散数ｎと置き換えて（ＳＴ３）、ステップＳＴ１に戻る。
【００５８】
一方、ステップＳＴ２の判定結果が否の場合、制御部１０９は、分散数ｎ及び閾値ｋを生成行列生成部１０３に入力する。
【００５９】
生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇ（但し、任意のｋ個の列ベクトルがフルランク、行列Ｇのサイズはｋ（ｎ−１）×ｎ（ｎ−１）、列ベクトルのサイズはｋ（ｎ−１）×（ｎ−１)）を制御部１０９に出力する（ＳＴ４）。
【００６０】
以下、ステップＳＴ４における生成行列Ｇの生成処理の手順を図８〜図１５を用いて説明する。
【００６１】
図８に示すように、生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇを保存部１０１から検索する（ＳＴ４−１）。該当する生成行列Ｇが存在する場合、ＳＴ４−８へ進む。該当する生成行列Ｇが存在しない場合、図９に示すように、第０行がゼロベクトル、下（ｎ−１）×（ｎ−１）行列が単位行列と左右対称な行列（（０，ｎ-2）−要素，（１，ｎ-3）−要素，…，（ｎ-3，１）−要素，（ｎ-2，０）−要素が全て１で、他の要素は全て０の行列）から構成されるｎ行×（ｎ−１）列の第１小行列ｉを生成する（ＳＴ４−２）。
【００６２】
続いて、図１０に示すように、（最も左側の）第１小行列iの各列を上に１回巡回シフトさせたｎ×（ｎ−１）行列を新たな第１小行列i−１として、当該巡回シフト前の第１小行列ｉの左側に隣接させる（ＳＴ４−３）。iがｎ−１から１までＳＴ４−３を繰り返して、ｎ×n（ｎ−１）の第１部分行列を生成する。この第１部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第０行目から第ｎ-2行目に割り当てる（ＳＴ４−４）。（４，５）閾値法の例では、生成行列Ｇの０行目から３行目までの部分行列が生成される。
【００６３】
生成行列生成部１０３は、図１１に示すように、第０行がゼロベクトル、下（ｎ−１）×（ｎ−１）行列が単位行列から構成されるｎ行×（ｎ−１）列の第２小行列ｉを生成する（ＳＴ４−５）。
【００６４】
続いて図１２〜図１５に示すように、（最も右側の）第２小行列ｉの各列を下にｊ回巡回シフトさせたｎ×（ｎ−１）行列を新たな第２小行列ｉ＋１として、当該巡回シフト前の第２小行列ｉの右側に隣接させる（ＳＴ４−６）。ｉが１からｎ−１までＳＴ４−６を繰り返して、ｎ×ｎ（ｎ−１）の第２部分行列を生成する。この第２部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から（ｎ−１）（ｊ＋１）＋ｎ−２行目に割り当てて、ｊをインクリメントする（ＳＴ４−７）。ｊが０からｋ−２までＳＴ４−６〜ＳＴ４−７を繰り返して生成行列Ｇを生成する。（４，５）閾値法の例では、生成行列Ｇは図２に示すような構成となる。
【００６５】
しかる後、生成行列生成部１０３は、得られた生成行列Ｇを制御部１０９に出力する（ＳＴ４−８）。
【００６６】
以上により生成行列Ｇの生成処理が完了する。
【００６７】
ステップＳＴ４の完了後、制御部１０９は、秘密情報Ｓ、生成行列Ｇ、分散数ｎ及び閾値ｋを分散部分データ生成部１０５に入力する。
【００６８】
分散部分データ生成部１０５は、図７に示すように、秘密情報Ｓ及び分散数ｎに基づいて、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａと等しいか（ｍ／（ｎ−１）＝ａ）か否かを判定する（ＳＴ５）。
【００６９】
ステップＳＴ４の判定結果が否の場合、分散部分データ生成部１０５は、秘密情報Ｓをｎ−１個の分割秘密データＫ（１）〜Ｋ（ｎ−１）に分割した際の末尾の分割秘密データＫ（ｎ−１）をパディングする（パディング有）とし（ＳＴ６）、ステップＳＴ７に進む。
【００７０】
なお、パディングは、必ずしも末尾の分割秘密データＫ（ｎ-2）に行わなくても良く、他の分割秘密データＫ（ｊ）に行っても良い。但し、本実施形態では、秘密情報Ｓは４個にちょうど分割できた場合（パディング無し）を例に挙げて述べる。また、図２に示した如き、分散数ｎ＝５，閾値ｋ＝４の（４，５）閾値法を例に挙げて述べる。
【００７１】
ステップＳＴ５の判定の結果、処理単位ビットａと等しい場合、分散部分データ生成部１０５は、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、０≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する（ＳＴ７）。（４，５）閾値法の例では、分割秘密データＫ（１），…，Ｋ（４）が生成される。
【００７２】
次に、各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｇ≦ｋ−２）と列番号（但し、１≦ｈ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する（ＳＴ７）。（４，５）閾値法の例では、乱数データＵ（０，１），…，Ｕ（２，４）が生成される。
【００７３】
分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）及び生成行列Ｇに基づいて、ｎ（ｎ−１）個の分散部分データ（Ｄ（０，０），…，Ｄ（ｊ，ｉ），…，Ｄ（ｎ−１，ｎ−２））＝（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））Ｇを算出する（ＳＴ８）。なお、処理単位ビットａにあわせて、生成行列Ｇの要素が１の場合はａ×ａのＧＦ（２）上の単位行列、０の場合はａ×ａのＧＦ（２）上のゼロ行列として扱う。（４，５）閾値法の例では、図４、図５に示したように、２０個の分散部分データＤ（ｊ，ｉ）が生成される。例えば、分散部分データＤ（０，０）の算出過程を図１６に示す。
【００７４】
しかる後、分散部分データ生成部１０５は、得られた分散部分データｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を制御部１０９に出力する。
【００７５】
制御部１０９は、各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する（ＳＴ９）。ヘッダ情報Ｈ（ｊ）には、Ｋ（ｎ−１）に対するパディングの有無、元データのサイズなどの情報が含まれる。
【００７６】
制御部１０９は、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別にｎ個の保存部１０１，２０１，…，ｎ０１に配布するように、分散情報Ｄ（０）を保存部１０１に書き込み、分散情報Ｄ（１），…，Ｄ（ｎ−１）を個別に保管サーバ装置２００，…，ｎ００に配布する（ＳＴ１０）。（４，５）閾値法の例では、５個の分散情報Ｄ（０），…，Ｄ（４）が配布される。各保管サーバ装置２００〜５００では、配布された分散情報Ｄ（１），…，Ｄ（４）を保存部２０１〜５０１に記憶する。
【００７７】
以上により、秘密情報の分散処理が完了する。
【００７８】
なお、（４，５）閾値法において、必ずしも５個の分散情報Ｄ（０）〜Ｄ（４）を配布する必要は無い。例えば４個の分散情報Ｄ（０）〜Ｄ（３）を配布しておき、残り１個の分散情報Ｄ（４）を新メンバが追加されたときに新メンバに配布してもよい。
【００７９】
（復元処理の動作）
クライアント装置１００においては、操作者の操作により、復元処理の開始命令が入力部１０２から入力されたとする。
【００８０】
クライアント装置１００は、この開始命令に基づいて、図１７に示すように、復元処理を開始する。制御部１０９は、ｎ台の装置１００，…，ｎ００に配布したｎ個の分散情報Ｄ（０）〜Ｄ（ｎ−１）のうち、任意のｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）（但し、０≦ｉ_ｊ≦ｎ−１）を収集する（ＳＴ１１）。
【００８１】
制御部１０９は、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）のヘッダ情報Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１を取得する（ＳＴ１２）。取得できた場合は、ＳＴ１５へ進む。取得できなかった場合は、Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から生成行列Ｇのｋ個の列ベクトルｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ）を得ると、このｋ個の列ベクトルから生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））を形成して取得する（ＳＴ１３）。
【００８２】
次に、制御部１０９は、生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））を逆行列生成部１０４に入力する。
【００８３】
逆行列生成部１０４は、生成行列Ｇの部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））から生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１を算出する（ＳＴ１４）。
【００８４】
（４，５）閾値法の例では、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）に対応する生成行列Ｇの部分行列（（ｇ（Ｄ（１）），ｇ（Ｄ（２）），ｇ（Ｄ（３）），ｇ（Ｄ（４）））は図２に示したような行列になり、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）に対応する生成行列Ｇの部分逆行列（（ｇ（Ｄ（１）），ｇ（Ｄ（２）），ｇ（Ｄ（３）），ｇ（Ｄ（４）））−１は図３に示したような行列となる。
【００８５】
逆行列生成部１０４は、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１を出力する（ＳＴ１５）。
【００８６】
制御部１０９は、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１と分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）を元データ復元部１０７に入力する。
【００８７】
元データ復元部１０７は、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）のヘッダ情報Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から、図１７に示すように、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）であることを解析する（ＳＴ１６）。（４，５）閾値法の例では、例えば分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）であることを確認する。
【００８８】
次に、分散情報からなる行列（Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k））と生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_j）），…，ｇ（Ｄ（ｉ_k）））−１の行列の積を算出する（ＳＴ１７）。なお、処理単位ビットａにあわせて、生成行列Ｇの要素が１の場合はａ×ａのＧＦ（２）上の単位行列、０の場合はａ×ａのＧＦ（２）上のゼロ行列として扱う。
【００８９】
次に、計算結果のｉ＋１列目のデータをＫ（ｉ）に割り当てて、分割秘密データＫ（１），…，Ｋ（ｎ−１）を算出する。（４，５）閾値法の例では、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）から復元した場合、図１８〜図２２に示したように、分割秘密データＫ（１），Ｋ（２），Ｋ（３），Ｋ（４）が算出される。
【００９０】
制御部１０９は、分割秘密データＫ（１），…，Ｋ（ｎ−１）に対して、ヘッダ情報Ｈ（ｉ），Ｈ（ｊ）に基づいて、パディングなどの処理があれば除去する。
【００９１】
しかる後、制御部１０９は、分割秘密データＫ（１），…，Ｋ（ｎ−１）を互いに連接することにより、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（ｎ−１）を復元する（ＳＴ１８）。この例では、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（４）が復元される。
【００９２】
上述したように本実施形態によれば、生成行列Ｇを用いて分散部分データを生成する構成により、秘密情報の分散や復元の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な閾値４以上の（ｋ，ｎ）閾値法を実現することができる。
【００９３】
また、本実施形態は、非特許文献２，３との相違を明確にする観点から閾値４以上として述べたが、閾値が２又は３でも実施できることはいうまでもない。このように本実施形態は、分散数ｎ及び閾値ｋが限定されないので、各種のシステムへの応用範囲を広げることができる。
【００９４】
また、本実施形態の分散・復元処理は、多項式補間が不要であり、ＸＯＲのみで実行するため、前述した高速に実行可能なことに加え、大容量データを扱うのに好適であり、低スペック機器でも秘密分散を実行できる利点を有する。
【００９５】
なお、本実施形態は、生成行列生成部１０３により生成行列Ｇを生成し、逆行列生成部１０４により逆行列を生成した場合について説明したが、これに限らず、分散数ｎ及び閾値ｋが予め分かっていれば、図２３に示すように、生成行列生成部１０３及び逆行列生成部１０４に代えて、予め生成行列Ｇ及びＧの逆行列のデータが保存された読出／書込可能な記憶装置としての行列保存部１１２を備えた構成に変形してもよい。このように変形しても、生成行列Ｇ及び逆行列による（ｋ，ｎ）閾値法を実現することができる。
【００９６】
また同様に、分散数ｎと閾値ｋとの組合せ毎に、予め生成行列Ｇ及びＧの逆行列のデータを行列保存部１１２に保存しておき、入力されたｎ，ｋの値を検索キーにして、行列保存部１１２から生成行列Ｇ及びＧの逆行列のデータを読み出す構成に変形してもよいことはいうまでもない。
【００９７】
（第２の実施形態）
図２４は本発明の第２の実施形態に係る秘密分散システムの構成を示す模式図である。
【００９８】
本実施形態は、第１の実施形態の変形例であり、分散アルゴリズムにより分散可能な（ｋ，ｎ）閾値法の秘密分散システムとなっている。これに伴い、前述した生成行列生成部１０３及び逆行列生成部１０４が省略され、分散部分データ生成部１０５ａ及び制御部１０９ａの機能が変更されている。
【００９９】
分散部分データ生成部１０５ａは、制御部１０９ａにより制御され、保存部１０１に一時的に記憶された秘密情報Ｓに基づいて、図４、図５に一例（ｋ＝４，ｎ＝５の例）を示すように、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を生成する機能をもっている。具体的には、分散部分データ生成部１０５ａは、以下の各機能（ｆ１０５ａ−１）〜（ｆ１０５ａ−６）をもっている。
【０１００】
（ｆ１０５ａ−１） 保存部１０１に記憶された秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する機能。
【０１０１】
（ｆ１０５ａ−２） 各分割秘密データのサイズと同一サイズのゼロ値データを作成し、作成結果に行番号ｊ＝０を割り当てて分割秘密データＫ（０）を生成する機能。
【０１０２】
（ｆ１０５ａ−３） 各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する機能。
【０１０３】
（ｆ１０５ａ−４） 各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する機能。なお、各乱数Ｕ（ｈ，ｇ）は、互いに異なる値である。
【０１０４】
（ｆ１０５ａ−５） 乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）に基づいて、ｎ×（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する機能（但し、(+)は排他的論理和を表す記号）。
【０１０５】
なお、Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）＝Ｕ（ｈ，０）（＝０）の場合、必ずしもＵ（ｈ，０）の項を計算する必要はなく、例えばＵ（０，３）(+)Ｕ（１，４）(+)Ｕ（２，０）をＵ（０，３）(+)Ｕ（１，４）としてもよい。このように、Ｕ（ｈ，０）（＝０）の場合、Ｕ（ｇ，０）の項を計算する必要が無いことは、本明細書中の他の箇所でも同様である。
【０１０６】
（ｆ１０５ａ−６） 分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する機能（但し、(+)は排他的論理和を表す記号）。
【０１０７】
なお、Ｋ（ｊ−ｉ(mod ｎ)）＝Ｋ（０）（＝０）の場合、必ずしもＫ（０）の項を計算する必要は無く、例えばＫ（０）の項の計算無しにＤ（ｊ，ｉ）＝Ｒ（ｊ，ｉ）としてもよい。このように、Ｋ（０）（＝０）の場合、必ずしもＫ（０）の項を計算する必要が無いことは、本明細書中の他の箇所でも同様である。
【０１０８】
制御部１０９ａは、入力部１０２から入力される命令に基づいて、後述する図２５及び図２６に示すフローチャートに基づいて、各部１０１，１０５ａ〜１０８，１１０，１１１を制御する機能をもっている。
【０１０９】
次に、以上のように構成された秘密分散システムの動作を説明する。ここでは（ｋ，ｎ）閾値法を例に挙げて述べる。
【０１１０】
始めに、ｎ人のメンバ（初期メンバ）に、秘密情報Ｓを（ｋ，ｎ）閾値法で分散した分散情報Ｄ（ｊ）を配布する場合を考える。このときｎは素数を選ばなければならない。従って、合成数のｎ人に分散情報を配布したい場合は、ｎ＜ｎ’でありかつｎ’が素数となるようなｎ’について秘密分散法を適用することになる。以下では（ｋ，ｎ）閾値法についての一例を示す。
【０１１１】
（分散処理の動作）
クライアント装置１００においては、分散情報Ｄ（０）〜Ｄ（ｎ−１）を配布する前に、ビット長ｍの秘密情報Ｓが一時的に保存部１０１に記憶されているとする。
【０１１２】
このとき、クライアント装置１００においては、図２５に示すように、操作者の操作により、分散処理の開始命令が入力部１０２から入力されたとする。
【０１１３】
クライアント装置１００は、この開始命令に基づいて、分散処理を開始する。制御部１０９ａは、秘密情報Ｓのビット長をｍ、分散数をｎ、処理単位ビットをａと定める（ＳＴ２１）。なお、秘密情報Ｓのビット長ｍは、保存部１０１内の秘密情報Ｓから分かる。処理単位ビットａは、分散データ生成部１３の仕様により予め定まっている。
【０１１４】
続いて、制御部１０９ａは、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａを超える（ｍ／（ｎ−１）＞ａ）か否かを判定し（ＳＴ２２）、処理単位ビットａを超える場合、ｎより大きい素数ｎ’を探索し、得られた素数ｎ’を分散数ｎと置き換えて（ＳＴ２３）、ステップＳＴ２１に戻る。
【０１１５】
一方、ステップＳＴ２２の判定の結果が否の場合、制御部１０９ａは、秘密情報Ｓ及び分散数ｎを分散部分データ生成部１０５ａに入力する。
【０１１６】
分散部分データ生成部１０５ａは、秘密情報Ｓ及び分散数ｎに基づいて、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａと等しいか（ｍ／（ｎ−１）＝ａ）か否かを判定する（ＳＴ２４）。
【０１１７】
ステップＳＴ２４の判定結果が否の場合、分散部分データ生成部１０５ａは、秘密情報Ｓをｎ−１個の分割秘密データＫ（１）〜Ｋ（ｎ−１）に分割した際の末尾の分割秘密データＫ（ｎ−１）をパディングする（パディング有）とし（ＳＴ２５）、ステップＳＴ２６に進む。
【０１１８】
なお、パディングは、必ずしも末尾の分割秘密データＫ（ｎ-2）に行わなくても良く、他の分割秘密データＫ（ｊ）に行っても良い。但し、本実施形態では、秘密情報Ｓは４個にちょうど分割できた場合（パディング無し）を例に挙げて述べる。また、図４、図５に示した如き、分散数ｎ＝５，閾値ｋ＝４の（４，５）閾値法を例に挙げて述べる。
【０１１９】
ステップＳＴ２４の判定の結果、処理単位ビットａと等しい場合、分散部分データ生成部１０５ａは、図２６に示すように、ステップＳＴ２６を開始する。
【０１２０】
すなわち、分散部分データ生成部１０５ａは、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、０≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する。（４，５）閾値法の例では、分割秘密データＫ（１），…，Ｋ（４）が生成される。
【０１２１】
また、分散部分データ生成部１０５ａは、各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて分割秘密データＫ（０）を生成する（ＳＴ２６−１）。
【０１２２】
さらに、分散部分データ生成部１０５ａは、各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する。
【０１２３】
次に、各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する（ＳＴ２６−２）。
【０１２４】
そして、乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、乱数データＲ（ｊ，ｉ）＝０としつつ（ＳＴ２６−３）、ｈを０からｋ−２まで繰り返してｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する（ＳＴ２６−４）。（４，５）閾値法の例では、乱数データＲ（０，０），…，Ｒ（４，３）が生成される。
【０１２５】
次に、分散部分データ生成部１０５ａは、分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び乱数データＲ（０，０），…，Ｒ（ｊ，ｉ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する（ＳＴ２７）。この算出は、行番号ｊを０からｎ−１まで繰り返すと共に、列番号ｉを０からｎ-2まで繰り返すことにより行う。（４，５）閾値法の例では、図４、図５に示したように、２０個の分散部分データＤ（ｊ，ｉ）が生成される。
【０１２６】
しかる後、分散部分データ生成部１０５ａは、得られた分散部分データｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を制御部１０９ａに出力する。
【０１２７】
制御部１０９ａは、各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する（ＳＴ２８）。ヘッダ情報Ｈ（ｊ）には、Ｋ（ｎ−１）に対するパディングの有無、元データのサイズなどの情報が含まれる。
【０１２８】
制御部１０９ａは、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別にｎ個の保存部１０１，２０１，…，ｎ０１に配布するように、分散情報Ｄ（０）を保存部１０１に書き込み、分散情報Ｄ（１），…，Ｄ（ｎ−１）を個別に保管サーバ装置２００，…，ｎ００に配布する（ＳＴ２９）。
【０１２９】
（４，５）閾値法の例では、５個の分散情報Ｄ（０），…，Ｄ（４）が配布される。各保管サーバ装置２００〜５００では、配布された分散情報Ｄ（１），…，Ｄ（４）を保存部２０１〜５０１に記憶する。
【０１３０】
以上により、秘密情報の分散処理が完了する。
【０１３１】
なお、（４，５）閾値法において、必ずしも５個の分散情報Ｄ（０）〜Ｄ（４）を配布する必要は無い。例えば４個の分散情報Ｄ（０）〜Ｄ（３）を配布しておき、残り１個の分散情報Ｄ（４）を新メンバが追加されたときに新メンバに配布してもよい。
【０１３２】
上述したように本実施形態によれば、第１の実施形態の生成行列Ｇと同様の結果を得るアルゴリズムを用いて分散部分データを生成する構成により、秘密情報の分散の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現することができる。
【０１３３】
すなわち、本実施形態によれば、生成行列Ｇを用いずに、第１の実施形態と同様の作用効果を得ることができる。
【０１３４】
（第３の実施形態）
次に、本発明の第３の実施形態に係る秘密分散システムについて説明する。
本実施形態は、第１の実施形態の変形形態であり、第１の実施形態とは異なるビットパターンの生成行列Ｇと、その生成行列Ｇを利用した分散処理とに関する。
【０１３５】
ここで、生成行列Ｇは、図２７にｋ＝４，ｎ＝５とした（４，５）閾値法の例を示すように、図１１〜図１５に示したｊ＝０〜２の場合の第４〜１５行目と同じ値の第０〜１１行目を有し、図２８及び図２９に示す如きｊ＝３の場合と同じ値の第１２〜１５行目を有している。
【０１３６】
この生成行列Ｇは、図３０に示すように、図８の第１小行列ｉに関するステップＳＴ４−２〜ＳＴ４−４を省略し、図８の第２小行列ｉに関するステップＳＴ４−１，ＳＴ４−５，ＳＴ４−６と同様の各ステップＳＴ４−１，ＳＴ４−５及びＳＴ４−６と、図８のステップＳＴ４−７に代えて割当て行をＧの第（ｎ−１）ｊ行目から第（ｎ−１）ｊ＋ｎ−２行目としたステップＳＴ４−７’とを備え、且つｊが０からｋ−１までステップＳＴ４−６及びＳＴ４−７’を繰り返し実行する生成方法により生成される。
【０１３７】
すなわち、生成行列生成部１０３は、入力された分散数ｎ及び閾値ｋが保存部１０１に記憶されたとき、保存部１０１内の分散数ｎ及び閾値ｋに基づいて、第０行がゼロベクトルであり、この第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列であるｎ行×（ｎ−１）列の第２小行列を生成する処理と、最も右側の第２小行列の各列を下にｊ回巡回シフトさせたｎ行×（ｎ−１）列の新たな第２小行列を当該巡回シフト前の第２小行列の右側に隣接させる第２隣接処理（但し、ｊ＝０，１，…，ｋ−１）と、第２隣接処理をｎ−１回実行し、ｎ行×n（ｎ−１）列の第２部分行列を生成する第２部分行列生成処理と、この第２部分行列の第１行目から第ｎ−１行目を生成行列Ｇの第（ｎ−１）ｊ行目から第（ｎ−１）ｊ＋ｎ−２行目に割り当てて、生成行列Ｇの第（ｎ−１）ｊ行目から第（ｎ−１）ｊ＋ｎ−２行目までの部分行列を生成する第２部分行列割当て処理（但し、ｊ＝０，１，…，ｋ−１）と、第２隣接処理及び第２部分行列割当て処理におけるｊの値が初期値０から最終値ｋ−１までの間、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理を実行する毎に当該ｊの値を１だけ増加させつつ、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理をｋ回実行する処理と、ｋ回の第２部分割当て処理により割り当てられた第０行目から第（ｎ−１）（ｋ−１）＋ｎ−２行目までの部分行列とにより、ｋ（ｎ−１）行×ｎ（ｎ−１）列の生成行列Ｇを得る処理とを実行する機能をもっている。
【０１３８】
なお、本実施形態においては、第１小行列に関するステップＳＴ４−２〜ＳＴ４−４を省略したため、上述した第２小行列、第２部分行列、第２隣接処理、第２部分行列生成処理及び第２部分行列割当て処理から「第２」の語句を省略してもよい。
【０１３９】
また、生成行列Ｇの変更に伴い、図３１のステップＳＴ８’及び図３２に示すように、分散部分データ算出時の生成行列Ｇに左側から積算される行列において、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）の右側に分散秘密データＫ（１）〜Ｋ（ｎ−１）が配置される。この配置は、前述した図７のステップＳＴ８とは逆の配置となっている。
【０１４０】
分散部分データＤ（ｊ，ｉ）は、図３３及び図５に一例（ｎ＝４，ｎ＝５）を示すように、ｎ（ｎ−１）個が分散部分データ生成部１０５により生成される。
【０１４１】
ここで、分散部分データ生成部１０５の機能（ｆ１０５−３）は、以下の機能（ｆ１０５−３’）のようになる。
【０１４２】
（ｆ１０５−３’） 乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）、分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、生成行列Ｇに基づいて、行列（Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と生成行列Ｇの積を算出し（但し、ＧＦ（２）上の演算）、計算結果のj×(ｎ−１)+ｉ列目のデータをＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を算出する（但し、０≦ｊ≦ｎ−１，０≦ｉ≦ｎ−２）機能。
【０１４３】
次に、以上のように構成された秘密分散システムの動作を説明する。
【０１４４】
（分散処理の動作）
いま、前述同様に、図３１に示すステップＳＴ１〜ＳＴ３が実行され、ステップＳＴ４’に進むとする。
【０１４５】
生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇ（但し、任意のｋ個の列ベクトルがフルランク、行列Ｇのサイズはｋ（ｎ−１）×ｎ（ｎ−１）、列ベクトルのサイズはｋ（ｎ−１）×（ｎ−１)）を制御部１０９に出力する（ＳＴ４’）。
【０１４６】
以下、ステップＳＴ４’における生成行列Ｇの生成処理の手順を図２８〜図３０を用いて説明する。
【０１４７】
図３０に示すように、生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇを保存部１０１から検索する（ＳＴ４−１）。該当する生成行列Ｇが存在する場合、ＳＴ４−８へ進む。該当する生成行列Ｇが存在しない場合、図１１に示したように、第０行がゼロベクトル、下（ｎ−１）×（ｎ−１）行列が単位行列から構成されるｎ行×（ｎ−１）列の第２小行列ｉを生成する（ＳＴ４−５）。
【０１４８】
続いて図１２〜図１４の上方及び図２８に示したように、（最も右側の）第２小行列ｉの各列を下にｊ回巡回シフトさせたｎ×（ｎ−１）行列を新たな第２小行列ｉ＋１として、当該巡回シフト前の第２小行列ｉの右側に隣接させる（ＳＴ４−６）。ｉが１からｎ−１までＳＴ４−６を繰り返して、ｎ×ｎ（ｎ−１）の第２部分行列を生成する。この第２部分行列の第１行目から第ｎ−１行目を図２９に示すように生成行列Ｇの第（ｎ−１）ｊ行目から（ｎ−１）ｊ＋ｎ−２行目に割り当てて、ｊをインクリメントする（ＳＴ４−７’）。ｊが０からｋ−１までＳＴ４−６〜ＳＴ４−７’を繰り返して生成行列Ｇを生成する。（４，５）閾値法の例では、生成行列Ｇは図２７に示すような構成となる。
【０１４９】
しかる後、生成行列生成部１０３は、得られた生成行列Ｇを制御部１０９に出力する（ＳＴ４−８）。
【０１５０】
以上により生成行列Ｇの生成処理が完了する。
【０１５１】
ステップＳＴ４の完了後、前述同様に、図３１に示すステップＳＴ５〜ＳＴ７が実行され、ステップＳＴ８’に進むとする。
【０１５２】
分散部分データ生成部１０５は、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）及び分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）からなる行列（Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と生成行列Ｇの積を算出し（ＳＴ８’）、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を算出する。（４，５）閾値法の例では、図３３及び図５に示したように、２０個の分散部分データＤ（ｊ，ｉ）が生成される。例えば、分散部分データＤ（０，０）の算出過程を図３２に示す。
【０１５３】
以下、前述同様に、ステップＳＴ９及びＳＴ１０が実行され、分散処理が完了する。
【０１５４】
（復元処理の動作）
復元処理の動作は、図１７を用いて前述同様に実行される。厳密には、前述とは異なる生成行列Ｇのビットパターンに伴い、生成行列Ｇの任意のｋ個の列ベクトルからなる部分行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））のビットパターンと、生成行列Ｇの部分逆行列（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））−１のビットパターンとが、前述とは異なるものとなる。但し、ビットパターンが異なっても、復元処理の動作が前述同様に実行されることに変わりはない。
【０１５５】
上述したように本実施形態によれば、第１の実施形態とは異なるビットパターンの生成行列Ｇを生成する構成としても、第１の実施形態と同様の効果を得ることができる。
【０１５６】
また、第１の実施形態のステップＳＴ４−２〜ＳＴ４−４を省略した構成により、生成行列Ｇの生成アルゴリズムを簡素化することができる。補足すると、ステップＳＴ４−２〜ＳＴ４−４を省略したことにより、ステップＳＴ４−６〜ＳＴ４−７’の繰り返し回数ｊが１回増えているが、同様なステップの繰り返しなので、生成アルゴリズムは簡素化されている。
【０１５７】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１５８】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１５９】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１６０】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１６１】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１６２】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１６３】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１６４】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１６５】
【図１】本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図である。
【図２】同実施形態における生成行列の一例を示す模式図である。
【図３】同実施形態における逆行列の一例を示す模式図である。
【図４】同実施形態における分散部分データの一例を示す模式図である。
【図５】同実施形態における乱数データの一例を示す模式図である。
【図６】同実施形態におけるヘッダ情報及び分散情報の一例を示す模式図である。
【図７】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図８】同実施形態における生成行列生成処理の動作を説明するためのフローチャートである。
【図９】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１０】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１１】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１２】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１３】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１４】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１５】同実施形態における生成行列の生成動作を説明するための模式図である。
【図１６】同実施形態における分散部分データの算出過程を説明するための模式図である。
【図１７】同実施形態における復元処理の動作を説明するためのフローチャートである。
【図１８】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図１９】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２０】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２１】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２２】同実施形態における分割秘密データの算出動作を説明するための模式図である。
【図２３】同実施形態における変形例を説明するための模式図である。
【図２４】本発明の第２の実施形態に係る秘密分散システムの構成を示す模式図である。
【図２５】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図２６】同実施形態における分割秘密データ及び乱数の生成動作を説明するためのフローチャートである。
【図２７】本発明の第３の実施形態における生成行列の一例を示す模式図である。
【図２８】同実施形態における生成行列の生成動作を説明するための模式図である。
【図２９】同実施形態における生成行列の生成動作を説明するための模式図である。
【図３０】同実施形態における生成行列生成処理の動作を説明するためのフローチャートである。
【図３１】同実施形態における分散処理の動作を説明するためのフローチャートである。
【図３２】同実施形態における分散部分データの算出過程を説明するための模式図である。
【図３３】同実施形態における分散部分データの一例を示す模式図である。
【符号の説明】
【０１６６】
１００…クライアント装置、１０１〜ｎ０１…保存部、１０２…入力部、１０３…生成行列生成部、１０４…逆行列生成部、１０５，１０５ａ…分散部分データ生成部、１０６…ハッシュ値生成部、１０７…元データ復元部、１０８…ハッシュ値検証部、１０９，１０９ａ…制御部、１１０…出力部、１１１，２０２〜ｎ０２…通信部、２００，３００，…，ｎ００…保管サーバ装置、ＮＷ…ネットワーク。
【特許請求の範囲】
【請求項１】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置であって、
１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段と、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、
この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する手段と、
前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積を算出し（但し、ＧＦ（２）上の演算）、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、０≦ｊ≦ｎ−１、０≦ｉ≦ｎ−２）を算出する手段と、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段と
を備えたことを特徴とする秘密分散装置。
【請求項２】
請求項１に記載の秘密分散装置において、
前記算出する手段は、
前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積に代えて、
前記乱数データ及び前記分割秘密データ（Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と前記生成行列Ｇとの行列の積を算出することを特徴とする秘密分散装置。
【請求項３】
請求項１又は請求項２に記載の秘密分散装置において、
前記配布する手段は、前記ｎ個の列ベクトルにおける各々の列ベクトルを前記ｎ個の分散情報Ｄ（０），…，Ｄ（ｎ−１）に個別に含めており、
前記ｎ個の記憶装置のうち、任意のｋ個の記憶装置から収集されたｋ個の分散情報からｋ個の列ベクトルを得る手段と、
このｋ個の列ベクトルから前記生成行列の部分行列を形成し、この部分行列の逆行列を算出する手段と、
前記収集されたｋ個の分散情報と前記逆行列との行列の積を演算し（但し、ＧＦ（２）上の演算）、前記分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を得る手段と、
得られた分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）から前記秘密情報Ｓを復元する手段と
を備えたことを特徴とする秘密分散装置。
【請求項４】
請求項１に記載の秘密分散装置が実行する秘密分散方法であって、
入力された分散数ｎ及び閾値ｋを前記記憶手段に記憶する工程と、
前記記憶手段内の分散数ｎ及び閾値ｋに基づいて、第０行がゼロベクトルであり、前記第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列とは左右対称な行列であるｎ行×（ｎ−１）列の第１小行列を生成する工程と、
最も左側の第１小行列の各列を上に１回巡回シフトさせたｎ行×（ｎ−１）列の新たな第１小行列を当該巡回シフト前の第１小行列の左側に隣接させる第１隣接工程と、
前記第１隣接工程をｎ−１回実行し、ｎ行×n（ｎ−１）列の第１部分行列を生成する工程と、
この第１部分行列の第１行目から第ｎ−１行目を前記生成行列Ｇの第０行目から第ｎ-2行目に割り当てて、前記生成行列Ｇの第０行目から第ｎ−２行目までの部分行列を生成する第１部分行列割当て工程と、
第０行がゼロベクトルであり、この第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列であるｎ行×（ｎ−１）列の第２小行列を生成する工程と、
最も右側の第２小行列の各列を下にｊ回巡回シフトさせたｎ行×（ｎ−１）列の新たな第２小行列を当該巡回シフト前の第２小行列の右側に隣接させる第２隣接工程（但し、ｊ＝０，１，…，ｋ−２）と、
前記第２隣接工程をｎ−１回実行し、ｎ行×n（ｎ−１）列の第２部分行列を生成する第２部分行列生成工程と、
この第２部分行列の第１行目から第ｎ−１行目を前記生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目に割り当てて、前記生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目までの部分行列を生成する第２部分行列割当て工程（但し、ｊ＝０，１，…，ｋ−２）と、
前記第２隣接工程及び前記第２部分行列割当て工程におけるｊの値が初期値０から最終値ｋ−２までの間、前記第２隣接工程、前記第２部分行列生成工程及び前記第２部分行列割当て工程を実行する毎に当該ｊの値を１だけ増加させつつ、前記第２隣接工程、前記第２部分行列生成工程及び前記第２部分行列割当て工程をｋ−１回実行する工程と、
前記第１部分割当て工程により割り当てられた第０行目から第ｎ−２行目までの部分行列と、前記ｋ−１回の第２部分割当て工程により割り当てられた第ｎ−１行目から第（ｎ−１）（ｋ−１）＋ｎ−２行目までの部分行列とにより、前記ｋ（ｎ−１）行×ｎ（ｎ−１）列の生成行列Ｇを得る工程と
を備えたことを特徴とする秘密分散方法。
【請求項５】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）型の秘密分散装置であって、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、
この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて第２分割秘密データＫ（０）を生成する手段と、
前記各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する手段と、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する手段と、
前記乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、ｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する手段と（但し、(+)は排他的論理和を表す記号）、
前記分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び前記乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する手段と、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段と
を備えたことを特徴とする秘密分散装置。
【請求項６】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓを一時的に前記コンピュータのメモリに書き込む手段、
前記メモリ内の秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する手段、
前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積を算出し（但し、ＧＦ（２）上の演算）、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、０≦ｊ≦ｎ−１、０≦ｉ≦ｎ−２）を算出する手段、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段、
として機能させるためのプログラム。
【請求項７】
請求項６に記載のプログラムにおいて、
前記配布する手段は、前記ｎ個の列ベクトルにおける各々の列ベクトルを前記ｎ個の分散情報Ｄ（０），…，Ｄ（ｎ−１）に個別に含める手順を含んでおり、
前記コンピュータを、
前記ｎ個の記憶装置のうち、任意のｋ個の記憶装置から収集されたｋ個の分散情報からｋ個の列ベクトルを得る手段、
このｋ個の列ベクトルから前記生成行列の部分行列を形成し、この部分行列の逆行列を算出する手段、
前記収集されたｋ個の分散情報と前記逆行列との行列の積を演算し（但し、ＧＦ（２）上の演算）、前記分割秘密データＫ（１），…，Ｋ（ｎ−１）を得る手段、
得られた分割秘密データＫ（１），…，Ｋ（ｎ−１）から前記秘密情報Ｓを復元する手段、
として機能させるためのプログラム。
【請求項８】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓを一時的に前記コンピュータのメモリに書き込む手段、
前記メモリ内の秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて第２分割秘密データＫ（０）を生成する手段、
前記各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する手段、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する手段、
前記乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、ｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する手段と（但し、(+)は排他的論理和を表す記号）、
前記分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び前記乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する手段、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段、
として機能させるためのプログラム。
【請求項１】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置であって、
１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段と、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、
この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する手段と、
前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積を算出し（但し、ＧＦ（２）上の演算）、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、０≦ｊ≦ｎ−１、０≦ｉ≦ｎ−２）を算出する手段と、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段と
を備えたことを特徴とする秘密分散装置。
【請求項２】
請求項１に記載の秘密分散装置において、
前記算出する手段は、
前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積に代えて、
前記乱数データ及び前記分割秘密データ（Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と前記生成行列Ｇとの行列の積を算出することを特徴とする秘密分散装置。
【請求項３】
請求項１又は請求項２に記載の秘密分散装置において、
前記配布する手段は、前記ｎ個の列ベクトルにおける各々の列ベクトルを前記ｎ個の分散情報Ｄ（０），…，Ｄ（ｎ−１）に個別に含めており、
前記ｎ個の記憶装置のうち、任意のｋ個の記憶装置から収集されたｋ個の分散情報からｋ個の列ベクトルを得る手段と、
このｋ個の列ベクトルから前記生成行列の部分行列を形成し、この部分行列の逆行列を算出する手段と、
前記収集されたｋ個の分散情報と前記逆行列との行列の積を演算し（但し、ＧＦ（２）上の演算）、前記分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を得る手段と、
得られた分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）から前記秘密情報Ｓを復元する手段と
を備えたことを特徴とする秘密分散装置。
【請求項４】
請求項１に記載の秘密分散装置が実行する秘密分散方法であって、
入力された分散数ｎ及び閾値ｋを前記記憶手段に記憶する工程と、
前記記憶手段内の分散数ｎ及び閾値ｋに基づいて、第０行がゼロベクトルであり、前記第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列とは左右対称な行列であるｎ行×（ｎ−１）列の第１小行列を生成する工程と、
最も左側の第１小行列の各列を上に１回巡回シフトさせたｎ行×（ｎ−１）列の新たな第１小行列を当該巡回シフト前の第１小行列の左側に隣接させる第１隣接工程と、
前記第１隣接工程をｎ−１回実行し、ｎ行×n（ｎ−１）列の第１部分行列を生成する工程と、
この第１部分行列の第１行目から第ｎ−１行目を前記生成行列Ｇの第０行目から第ｎ-2行目に割り当てて、前記生成行列Ｇの第０行目から第ｎ−２行目までの部分行列を生成する第１部分行列割当て工程と、
第０行がゼロベクトルであり、この第０行の下の（ｎ−１）行×（ｎ−１）列が単位行列であるｎ行×（ｎ−１）列の第２小行列を生成する工程と、
最も右側の第２小行列の各列を下にｊ回巡回シフトさせたｎ行×（ｎ−１）列の新たな第２小行列を当該巡回シフト前の第２小行列の右側に隣接させる第２隣接工程（但し、ｊ＝０，１，…，ｋ−２）と、
前記第２隣接工程をｎ−１回実行し、ｎ行×n（ｎ−１）列の第２部分行列を生成する第２部分行列生成工程と、
この第２部分行列の第１行目から第ｎ−１行目を前記生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目に割り当てて、前記生成行列Ｇの第（ｎ−１）（ｊ＋１）行目から第（ｎ−１）（ｊ＋１）＋ｎ−２行目までの部分行列を生成する第２部分行列割当て工程（但し、ｊ＝０，１，…，ｋ−２）と、
前記第２隣接工程及び前記第２部分行列割当て工程におけるｊの値が初期値０から最終値ｋ−２までの間、前記第２隣接工程、前記第２部分行列生成工程及び前記第２部分行列割当て工程を実行する毎に当該ｊの値を１だけ増加させつつ、前記第２隣接工程、前記第２部分行列生成工程及び前記第２部分行列割当て工程をｋ−１回実行する工程と、
前記第１部分割当て工程により割り当てられた第０行目から第ｎ−２行目までの部分行列と、前記ｋ−１回の第２部分割当て工程により割り当てられた第ｎ−１行目から第（ｎ−１）（ｋ−１）＋ｎ−２行目までの部分行列とにより、前記ｋ（ｎ−１）行×ｎ（ｎ−１）列の生成行列Ｇを得る工程と
を備えたことを特徴とする秘密分散方法。
【請求項５】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）型の秘密分散装置であって、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、
この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて第２分割秘密データＫ（０）を生成する手段と、
前記各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する手段と、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する手段と、
前記乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、ｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する手段と（但し、(+)は排他的論理和を表す記号）、
前記分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び前記乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する手段と、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段と、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段と
を備えたことを特徴とする秘密分散装置。
【請求項６】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓを一時的に前記コンピュータのメモリに書き込む手段、
前記メモリ内の秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１）を生成する手段、
前記分割秘密データ及び前記乱数データ（Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１），Ｕ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ−２，ｎ−１））と前記生成行列Ｇとの行列の積を算出し（但し、ＧＦ（２）上の演算）、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、０≦ｊ≦ｎ−１、０≦ｉ≦ｎ−２）を算出する手段、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ−２）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段、
として機能させるためのプログラム。
【請求項７】
請求項６に記載のプログラムにおいて、
前記配布する手段は、前記ｎ個の列ベクトルにおける各々の列ベクトルを前記ｎ個の分散情報Ｄ（０），…，Ｄ（ｎ−１）に個別に含める手順を含んでおり、
前記コンピュータを、
前記ｎ個の記憶装置のうち、任意のｋ個の記憶装置から収集されたｋ個の分散情報からｋ個の列ベクトルを得る手段、
このｋ個の列ベクトルから前記生成行列の部分行列を形成し、この部分行列の逆行列を算出する手段、
前記収集されたｋ個の分散情報と前記逆行列との行列の積を演算し（但し、ＧＦ（２）上の演算）、前記分割秘密データＫ（１），…，Ｋ（ｎ−１）を得る手段、
得られた分割秘密データＫ（１），…，Ｋ（ｎ−１）から前記秘密情報Ｓを復元する手段、
として機能させるためのプログラム。
【請求項８】
秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧４）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）型の秘密分散装置のプログラムであって、
前記秘密分散装置のコンピュータを、
前記分散情報Ｄ（０）〜Ｄ（ｎ−１）が配布される前に、前記秘密情報Ｓを一時的に前記コンピュータのメモリに書き込む手段、
前記メモリ内の秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段、
前記各分割秘密データのサイズと同一サイズのゼロ値を作成し、作成結果に行番号ｊ＝０を割り当てて第２分割秘密データＫ（０）を生成する手段、
前記各分割秘密データのサイズと同一のサイズのゼロ値データをｋ−１個作成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ＝０を割り当てて、乱数データＵ（０，０），…，Ｕ（ｈ，０），…，Ｕ（ｋ−２，０）を生成する手段、
前記各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、行番号ｈ（但し、０≦ｈ≦ｋ−２）と列番号ｇ（但し、１≦ｇ≦ｎ−１）を割り当てて、乱数データＵ（０，１），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）を生成する手段、
前記乱数データＵ（０，０），…，Ｕ（ｈ，ｇ），…，Ｕ（ｋ-2，ｎ−１）に基づいて、ｎ（ｎ−１）個の乱数データＲ（ｊ，ｉ）＝Ｕ（０，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｈ，ｈ×ｊ＋ｉ＋１(mod ｎ)）(+)… (+)Ｕ（ｋ−１，ｈ×ｊ＋ｉ＋１(mod ｎ)）を算出する手段と（但し、(+)は排他的論理和を表す記号）、
前記分割秘密データＫ（０），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）及び前記乱数データＲ（０，０），…，Ｒ（ｉ，ｊ），…，Ｒ（ｎ−１，ｎ-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｊ，ｉ）を算出する手段、
前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（０），…，Ｈ（ｊ），…，Ｈ（ｎ−１）を生成する手段、
互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，０）〜Ｄ（ｊ，ｎ-2）からなるｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（ｎ−１）を個別に前記ｎ個の記憶装置に配布する手段、
として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【公開番号】特開２００８−２３３８２３（Ｐ２００８−２３３８２３Ａ）
【公開日】平成２０年１０月２日（２００８．１０．２）
【国際特許分類】
【出願番号】特願２００７−７７４２１（Ｐ２００７−７７４２１）
【出願日】平成１９年３月２３日（２００７．３．２３）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成２０年１０月２日（２００８．１０．２）
【国際特許分類】
【出願日】平成１９年３月２３日（２００７．３．２３）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]