JP4334582B2 - 秘密分散装置、方法及びプログラム - Google Patents

Description

本発明は、（ｋ，ｎ）閾値法を用いた秘密分散装置、方法及びプログラムに係り、例えば多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現し得る秘密分散装置、方法及びプログラムに関する。

一般に、暗号化鍵などの秘密情報を紛失した場合の対策としては、予め秘密情報のコピーを作成しておくことが有効である。しかしながら、秘密情報のコピーを作成すると、盗難のリスクが高くなるという問題が生じる。このような問題を解決する手法として、１９７９年にシャミア（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)

以上説明したように、シャミアによる（ｋ，ｎ）閾値法では、多項式補間を用いるため、高速な計算機が必要となる不都合がある。一方、藤井らの方式と栗原らの方式は、閾値ｋが２又は３に限定されるという不都合がある。

本発明は上記実情を考慮してなされたもので、多項式補間を用いずに高速に実行可能な任意の閾値ｋに対する（ｋ，ｎ）閾値法を実現し得る秘密分散装置、方法及びプログラムを提供することを目的とする。

第１の発明は、秘密情報Ｓが分散されて生成されたｎ個の分散情報Ｄ（１），…，Ｄ（ｎ）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法（但し、２≦ｋ≦ｎ）の秘密分散装置であって、１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつ列ベクトルｎ個からなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルから構成される行列がフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段と、前記分散情報Ｄ（１）〜Ｄ（ｎ）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、前記各分割秘密データのサイズと同一サイズの（ｋ−１）（ｎ−１）個の乱数データＲ（１），…，Ｒ（（ｋ−１）（ｎ−１））を生成する手段と、前記乱数データ及び前記分割秘密データ（Ｒ（１），…，Ｒ（（ｋ−１）（ｎ−１）），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と前記生成行列Ｇとの行列の積を算出し、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、１≦ｊ≦ｎ、１≦ｉ≦ｎ−１）を算出する分散部分データ算出手段と、前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ−１）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（１），…，Ｈ（ｊ），…，Ｈ（ｎ）を生成する手段と、行番号ｊを有するヘッダ情報Ｈ（ｊ）と、ｎ−１個の分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ−１）の列ベクトルからなるヘッダ情報と同一の行番号を持つ分散情報Ｄ（ｊ）を個別に前記ｎ個の記憶装置にそれぞれ配布する手段と、配布したｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）のうち任意のｋ個の分散情報に含まれるｋ個の列ベクトルから生成行列Ｇのうちのｋ（ｎ−１）行×ｋ（ｎ−１）列の部分行列Ｇ’を構成し、この部分行列Ｇ’を（ｎ−１）行×（ｎ−１）列で区分けした行列単位で１行目からｋ−１行目までの乱数成分をゼロにするように基本行列Ｂ⁽¹⁾，…，Ｂ^(k-1)を再帰的に部分行列Ｇ’，…，Ｇ^(k-2)に乗じることにより、最後に乗じて得られた部分行列Ｇ^(k-1)の区分けした単位におけるｋ行ｋ列目の成分の逆行列を用いて基本行列Ｂ^(k)を作成し、全ての基本行列を乗じて復元行列Ｂ⁽¹⁾…Ｂ^(k-1)Ｂ^(k)を算出する手段と、当該ｋ個の分散情報に前記復元行列を乗算することにより、秘密情報を復元する復元手段とを備えた秘密分散装置である。

なお、第１の発明は、「装置」として表現したが、これに限らず、「プログラム」、「プログラムを記憶した記憶媒体」又は「方法」として表現してもよい。

（作用）
第１の発明は、生成行列Ｇを用いて分散部分データを生成する構成により、秘密情報の分散処理を排他的論理和により非常に高速に実行することができる。また、復元処理においては、生成行列Ｇの逆行列をそのまま求めることなく、生成行列を区分けしたブロック単位で再帰的に処理して復元行列を求める構成により、生成行列Ｇの逆行列を求める場合に比べ、高速に実行することができる。

以上説明したように本発明によれば、多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現することができる。

以下、本発明の各実施形態について図面を用いて説明する。なお、以下の各装置は、装置毎に、ハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又は記憶媒体から対応する装置のコンピュータにインストールされ、対応する装置の機能を実現させるためのプログラムが用いられる。

（第１の実施形態）
図１は本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図である。この秘密分散システムは、１台のクライアント装置１００及びｎ−１台の保管サーバ装置２００，３００，…，ｎ００が互いにインターネット等のネットワークＮＷを介して接続されている。

これら合計ｎ台の装置１００，２００，３００，…，ｎ００は、（ｋ，ｎ）閾値法におけるｎ人のメンバに対応する。特に、ｎ台の装置１００，２００，…，ｎ００が個別に有するｎ個の保存部１０１，２０１，…，ｎ０１は、ｎ人のメンバが個別に有するｎ個の記憶装置に対応する。各装置１００，２００，３００，…，ｎ００には、それぞれ分散情報の配布順番を示すｊ番号（行番号）が割当てられている。例えば、クライアント装置１００には、ｊ＝１番目が割り当てられており、保管サーバ装置２００にはｊ＝２番目が割り当てられている。保管サーバ装置３００にはｊ＝３番目が割り当てられ、…、保管サーバ装置ｎ００にはｊ＝ｎ番目が割り当てられている。

ここで、クライアント装置１００は、秘密情報Ｓが分散されてなるｎ個（但し、ｎ≧ｋ≧２）の分散情報Ｄ（０），…，Ｄ（ｎ−１）を個別にｎ台の装置１００，２００，…，ｎ００に配布し、且つ、ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法の秘密分散装置を実現するものである。なお、分散情報の個数はｋ個以上であればよい。例えばｋ＝４，ｎ＝５とし、秘密情報Ｓをｎ−１（＝４）個に分割して後述するＫ（１），Ｋ（２），Ｋ（３），Ｋ（４）とし、配布した５個の分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４），Ｄ（５）から任意の４個の分散情報を用いて秘密情報Ｓを復元してもよい。

クライアント装置１００は、保存部１０１、入力部１０２、生成行列生成部１０３、復元行列生成部１０４、分散部分データ生成部１０５、ハッシュ値生成部１０６、元データ復元部１０７、ハッシュ値検証部１０８、制御部１０９、出力部１１０及び通信部１１１が互いにバスを介して接続されている。

保存部１０１は、制御部１０９から読出／書込可能なハードウェア資源としての記憶装置であり、後述する分散情報Ｄ（１）〜Ｄ（ｎ）が配布される前に、秘密情報Ｓが一時的に記憶される。また、保存部１０１は、分散情報Ｄ（１）〜Ｄ（ｎ）が作成されると、分散情報作成情報が記憶され、分散情報が配布された後、ｊ＝１番目の分散情報Ｄ（１）が記憶されると共に、秘密情報Ｓが削除される。ここで、分散情報作成情報は、分散情報Ｄ（ｊ）の識別情報ｊと、分散情報Ｄ（ｊ）の配布先識別情報（装置ＩＤ、装置のアドレス情報等）とが互いに関連付けられた情報である。

入力部１０２は、キーボード又はマウス等の通常の入力デバイスであり、操作者の操作により、分散処理又は復号処理の開始等の命令や、秘密情報Ｓ等の情報をクライアント装置１００内に入力する機能をもっている。

生成行列生成部１０３は、制御部１０９により制御され、図２にｋ＝４，ｎ＝５とした（４，５）閾値法の例を示す如き、１個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつｎ個の列ベクトルからなり、ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルがフルランクとなるＧＦ（２）の生成行列Ｇを生成する機能をもっている。但し、生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列である。ＧＦ（２）は位数２の有限体である。フルランクとは、行列の基本変形を施して得られるランク（rank：階数）がフル（full：満杯）（＝ｋ（ｎ−１））であり、線形独立であることを意味している。

具体的には、生成行列生成部１０３は、入力された分散数ｎ及び閾値ｋが保存部１０１に記憶されたとき、保存部１０１内の分散数ｎ及び閾値ｋに基づいて、（ｎ−１）行×（ｎ−１）列の単位で行列を区分けした際に、区分けしたｉ行ｊ列のブロックについて、（ｎ−１）行×（ｎ−１）列の単位行列Ｅの最終行に１行×（ｎ−１）列のゼロ行列を追加し、ｎ行×（ｎ−１）列の図３に示す如き行列Ｅ’を生成する処理と、ｎ行×（ｎ−１）列の行列Ｅ’を縦方向に（ｉ−１）（ｊ−１）回巡回シフトして行列Ｅ’（(i-1)(j-1)）を作成する図４の処理と、この行列Ｅ’（(i-1)(j-1)）から最終行を除いた（ｎ−１）行×（ｎ−１）列の行列Ｅ（(i-1)(j-1)）を取得して、ｉ行ｊ列のブロックに割り当てる図５の処理とをｉ行ｊ列の全てのブロック（１≦ｉ≦ｋ、１≦ｊ≦ｎ）に対して実行することにより、図６に示すような生成行列Ｇを得る処理を実行する機能を持っている。なお、巡回シフトにおける縦方向は、上方向でも下方向でも同一方向であればよい。

復元行列生成部１０４は、制御部１０９により制御され、図７乃至図１０に示すように、配布されたｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）のうち任意のｋ個の分散情報に含まれるｋ個の列ベクトルから生成行列Ｇのうちのｋ（ｎ−１）行×ｋ（ｎ−１）列の部分行列Ｇ’を構成する機能と、この部分行列Ｇ’＝（ｇ（Ｄ（ｉ_1），…，Ｄ（ｉ_k）））＝（Ｕ_(1,1)，…，Ｕ_(i,j)，…，Ｕ_(k,k)）（但し、Ｕ_(i,j)＝Ｅ（(i-1)(j-1)））から当該部分行列Ｇ’を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けした１行目の成分を全てゼロにするための基本行列Ｂ⁽¹⁾を生成する機能と、部分行列Ｇ’に基本行列Ｂ⁽¹⁾を乗じて、区分けした１行目の成分を全てゼロにする処理を行い、部分行列Ｇ⁽¹⁾＝Ｇ’Ｂ⁽¹⁾を得る処理と、当該部分行列Ｇ⁽¹⁾を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けした２行目の成分を全てゼロにするための基本行列Ｂ⁽²⁾を生成する機能と、部分行列Ｇ⁽¹⁾に基本行列Ｂ⁽²⁾を乗じて、区分けした２行目の成分を全てゼロにする処理を行い、部分行列Ｇ⁽²⁾＝Ｇ⁽¹⁾Ｂ⁽²⁾を得る処理と、以下同様にして、得られた部分行列を部分行列Ｇ^(d-1)としたとき、この部分行列Ｇ^(d-1)を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けしたｄ行目の成分を全てゼロにするための基本行列Ｂ^(d)を生成する基本行列生成処理と、部分行列Ｇ^(d-1)に基本行列Ｂ^(d)を乗じて、区分けしたｄ行目の成分を全てゼロにする処理を行い、部分行列Ｇ^(d)＝Ｇ^(d-1)Ｂ^(d)を得る部分行列生成処理と、これら基本行列生成処理及び部分行列生成処理をｄ＝ｋ−１行目まで再帰的に実行し、部分行列Ｇ^(k-1)＝Ｇ^(k-2)Ｂ^(k-1)を得る処理と、部分行列Ｇ^(k-1)におけるｋ行ｋ列目の行列Ｕ_(k,k)の逆行列Ｕ_(k,k) ^-1をｋ行ｋ列目に配置して他の成分をゼロにした基本行列Ｂ^(k)を算出する機能と、全ての基本行列Ｂ⁽¹⁾，…，Ｂ^(k-1)，Ｂ^(k)を乗じて復元行列Ｂ⁽¹⁾…Ｂ^(k-1)Ｂ^(k)を生成する機能とをもっている。なお、復元行列は、基本行列Ｂ^(k)を求める前に、行列の積Ｂ⁽¹⁾…Ｂ^(k-1)を算出しておき、このＢ⁽¹⁾…Ｂ^(k-1)にＢ^(k)を乗じることにより、生成してもよい。

また、部分行列Ｇ^(k-1)は、次式で表すこともできる。
Ｇ^(k-1)＝Ｇ^(k-2)Ｂ^(k-1)
＝Ｇ^(k-3)Ｂ^(k-2)Ｂ^(k-1)
：
＝Ｇ⁽¹⁾Ｂ⁽²⁾…Ｂ^(k-2)Ｂ^(k-1)
＝Ｇ’Ｂ⁽¹⁾Ｂ⁽²⁾…Ｂ^(k-2)Ｂ^(k-1)
また、部分行列Ｇ^(k-1)の逆行列（Ｇ^(k-1)）^-1の（ｎ−１）行（ｎ−１）列で区分けした最後の右（ｎ−１）列の行列と、基本行列Ｂ^(k)の（ｎ−１）行（ｎ−１）列で区分けした最後の右（ｎ−１）列の行列は等しくなる。

ここで、ｇ（Ｄ（ｊ））は、ｊ個目の分散情報Ｄ（ｊ）を算出するのに使用した生成行列Ｇの部分行列であり、列ベクトルともいう。また、（ｉ_1）の表記は、任意の１個目を表し、（ｉ_j）の表記は任意のｊ個目を表し、（ｉ_k）の表記は任意のｋ個目を表している。すなわち、カッコ内の左側のｉと下線“ｉ＿”は、“任意の”を表している（表記“ｉ＿”のｉは行番号ではない）。また、例えばＤ（ｉ_1）は、任意の１個目のＤ（＊）なので、Ｄ（１）〜Ｄ（５）のいずれでもよい。

基本行列Ｂ^(d)（＝Ｂ⁽¹⁾，…，Ｂ^(k-1)）は、ｋ（ｎ−１）行×ｋ（ｎ−１）列の行列であり、（ｎ−１）行×（ｎ−１）列の単位で区分けしたｋ行ｋ列の成分をｂ_1,1，…，ｂ_i,j，…，ｂ_k,kとするとき、部分行列Ｇ^(d-1)（但し、Ｇ⁽⁰⁾＝Ｇ’）の成分Ｕ_(i,j)、単位行列Ｅ及びゼロ行列０を用いて図８及び以下のように示される（但し、１≦ｄ≦ｋ−１）。

ｂ_i,j＝Ｅ （i=d, d+1≦j≦k）、
ｂ_i,j＝Ｕ_(d,j) ^-1×Ｕ_(d,d) （i=j, d+1≦i,j≦k）、
ｂ_i,j＝０ （上記以外のi,j）
また、基本行列Ｂ^(d)（＝Ｂ⁽¹⁾，…，Ｂ^(k-1)）は、ｋ（ｎ−１）行×ｋ（ｎ−１）列の行列であり、（ｎ−１）行×（ｎ−１）列の単位で区分けしたｋ行ｋ列の成分をｂ_1,1，…，ｂ_i,j，…，ｂ_k,kとするとき、部分行列Ｇ^(d-1)（但し、Ｇ⁽⁰⁾＝Ｇ’）の成分Ｕ_(i,j)、単位行列Ｅ及びゼロ行列０を用いて図９及び以下のように示すこともできる（但し、１≦ｄ≦ｋ−１）。

ｂ_i,j＝Ｅ （i=j, d+1≦i,j≦k）、
ｂ_i,j＝Ｕ_(d,d) ^-1×Ｕ_(d,j) （i=d, d+1≦j≦k）、
ｂ_i,j＝０ （上記以外のi,j）
また、基本行列Ｂ^(k)は、ｋ（ｎ−１）行×ｋ（ｎ−１）列の行列であり、（ｎ−１）行×（ｎ−１）列の単位で区分けしたｋ行ｋ列の成分をｂ_1,1，…，ｂ_i,j，…，ｂ_k,kとするとき、部分行列Ｇ^(k-1)のｋ行ｋ列目の成分の逆行列Ｕ_(k,k) ^-1及びゼロ行列０を用いて図１０及び以下のように示される。

ｂ_i,j＝Ｕ_(k,k) ^-1 （i＝j＝k）、
ｂ_i,j＝０ （上記以外のi,j）
なお、図１１は基本行列Ｂ⁽¹⁾の一例を示しており、図１２はｋ＝４，ｎ＝５とした（４，５）閾値法における図８に示される基本行列を用いて構成した復元行列Ｂ⁽¹⁾Ｂ⁽²⁾Ｂ⁽³⁾Ｂ⁽⁴⁾の一例を示している。このような復元行列Ｂ⁽¹⁾Ｂ⁽²⁾…Ｂ^(k-1)Ｂ^(k)は、ｋ（ｎ−１）行×ｋ（ｎ−１）列の行列を（ｎ−１）行×（ｎ−１）列の単位で区分けしたｋ行ｋ列の成分のうち、１列目〜ｋ−１列目の成分がゼロ行列であることから、ｋ列目の成分のみが演算に用いられる。このため、復元行列Ｂ⁽¹⁾Ｂ⁽²⁾…Ｂ^(k-1)Ｂ^(k)による復元処理は、ｋ（ｎ−１）行×ｋ（ｎ−１）列の行列の逆行列による復元処理に比べ、演算の負荷が小さいという利点がある。さらに図８の基本行列よりも、図９の基本行列を用いた行列の基本変形を行うほうが、逆行列演算の回数が少なくなるという利点がある。

分散部分データ生成部１０５は、制御部１０９により制御され、保存部１０１に一時的に記憶された秘密情報Ｓに基づいて、図１３に一例（ｋ＝４，ｎ＝５の例）を示すように、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を生成する機能をもっている。具体的には、分散部分データ生成部１０５は、以下の各機能（ｆ１０５−１）〜（ｆ１０５−３）をもっている。

（ｆ１０５−１） 保存部１０１に記憶された秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する機能。

（ｆ１０５−２） 各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、乱数データＲ（１），…，Ｒ（（ｋ−１）（ｎ−１））を生成する機能。なお、各乱数Ｒ（ｉ）、１≦ｉ≦（ｋ−１）（ｎ−１）は、互いに独立である。

（ｆ１０５−３） 分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、乱数データＲ（１），…，Ｒ（（ｋ−１）（ｎ−１））、生成行列Ｇに基づいて、行列（Ｒ（１），…，Ｒ（（ｋ−１）（ｎ−１）），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と生成行列Ｇの積を算出し（但し、ＧＦ（２）上の演算）、計算結果のj×(ｎ−１)+ｉ列目のデータをＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を算出する（但し、１≦ｊ≦ｎ，１≦ｉ≦ｎ−１）機能。

ハッシュ値生成部１０６は、制御部１０９により制御され、制御部１０９からバスを介してヘッダ情報Ｈ（ｊ）が入力されると、ヘッダ情報Ｈ（ｊ）のハッシュ値ｈ（Ｈ（ｊ））を生成し、得られたハッシュ値ｈ（Ｈ（ｊ））をバスに出力する機能をもっている。なお、ハッシュ値生成部１０６は、ヘッダ情報Ｈ（ｊ）を検証しない場合、省略可能である。

元データ復元部１０７は、制御部１０９に制御され、ｎ台の装置１００，…，ｎ００に配布されたｎ個の分散情報Ｄ（１）〜Ｄ（ｎ）のうち、任意のｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k）（但し、１≦ｉ_j≦ｎ）に基づいて、秘密情報Ｓを復元する復元機能をもっている。具体的には元データ復元部１０７は、以下の各機能（ｆ１０７−１）〜（ｆ１０７−２）をもっている。

（ｆ１０７−１） 収集されたｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k）及び生成行列Ｇから復元行列生成部１０４により取得した復元行列を用いて、行列の積を算出し、計算結果を分割秘密データＫ（１），…，Ｋ（ｎ−１）として出力する機能。

（ｆ１０７−２） 復元されたｎ−１個の分割秘密データＫ（１），…，Ｋ（ｎ−１）を互いに連接することにより、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（ｎ−１）を復元する機能（但し、‖は連接を表す記号）。

ハッシュ値検証部１０８は、制御部１０９により制御され、制御部１０９からバスを介してヘッダ情報Ｈ（ｊ）及びそのハッシュ値ｈ（Ｈ（ｊ））が入力されると、ハッシュ値ｈ（Ｈ（ｊ））に基づいてヘッダ情報Ｈ（ｊ）を検証し、検証結果をバスに出力する機能をもっている。検証内容は、ヘッダ情報Ｈ（ｊ）から計算したハッシュ値と、入力されたハッシュ値ｈ（Ｈ（ｊ））との一致により、ヘッダ情報Ｈ（ｊ）を正当と判定する方式である。なお、ハッシュ値検証部１０８は、ヘッダ情報Ｈ（ｊ）を検証しない場合、省略可能である。

ここで、ヘッダ情報Ｈ（ｊ）は、図１４の上方に一例を示すように、行番号ｊを示すデータ識別子、ヘッダのサイズを表すヘッダーサイズ、元データのサイズを表す元データサイズｍ、元の秘密情報Ｓの分割数を示す分割数ｎ−１、分散部分データＤ（ｊ，ｉ）の処理単位ビットを示す処理単位ビット長ａ、乱数Ｒ（ｊ）のデータサイズを示す乱数データサイズａ、分割秘密データＫ（ｊ）のサイズを表す分割データサイズａ、パディングの有無やアルゴリズムを表すパディングアルゴリズム、ハッシュアルゴリズム情報（オプション）、生成行列Ｇの部分行列ｇ（Ｄ（ｊ））（オプション）などが考えられる。

ハッシュアルゴリズム情報は、ヘッダ情報のハッシュ値を算出し、ヘッダ情報の原本性を保証する場合などに追加される。すなわち、ハッシュアルゴリズム情報は、セキュリティの要件などに応じて追加又は省略される。但し、セキュリティの要件として予めシステムでハッシュアルゴリズムを決めている場合には、ハッシュアルゴリズム情報は、ヘッダ情報から省略可能である。

なお、分散情報Ｄ（ｊ）のデータフォーマットは、図１４の下方に一例を示すように、ヘッダ情報Ｈ（ｊ）、そのハッシュ値ｈ（Ｈ（ｊ））、ｎ−１個の分散部分データＤ（ｊ，１），Ｄ（ｊ，１），…，Ｄ（ｊ，ｎ-１）から構成されている。ここで、ハッシュ値ｈ（Ｈ（ｊ））は、オプション（option）であり、ヘッダ情報Ｈ（ｊ）内のハッシュアルゴリズム情報と同様に、セキュリティの要件に応じて省略可能となっている。

制御部１０９は、入力部１０２から入力される命令に基づいて、後述する図１５乃至図１８のフローチャートに基づいて、各部１０１，１０３〜１０８，１１０，１１１を制御する機能をもっている。また、制御部１０９は、例えば、以下の機能（ｆ１０９−１）〜（ｆ１０９−２）をもっている。

（ｆ１０９−１） 分散部分データ生成部１０５により生成された各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ-１）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（１），…，Ｈ（ｊ），…，Ｈ（ｎ）を生成する機能。

（ｆ１０９−２） 互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ-１）からなるｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）を通信部１１１を介して個別にｎ台の装置１００，２００，…，ｎ００に配布する機能。なお、制御部１０９は、分散情報Ｄ（１）〜Ｄ（ｎ）の漏洩防止の観点から、分散情報Ｄ（１）〜Ｄ（ｎ）を暗号化した状態で配布してもよい。

出力部１１０は、ディスプレイ装置やプリンタ装置等の通常の出力デバイスであり、制御部１０９により制御され、命令等の入力画面や、復元後の秘密情報Ｓ等の出力画面等を出力する機能をもっている。

通信部１１１は、制御部１０９により制御され、クライアント装置１００とネットワークＮＷとの間の通信インターフェイス機能をもっている。

一方、各保管サーバ装置２００〜ｎ００について説明する。
各保管サーバ装置２００〜ｎ００は、記憶する分散情報Ｄ（１）〜Ｄ（ｎ）が互いに異なる他は互いに同一構成のため、ここではｎ＝２の保管サーバ装置２００を代表例に挙げて説明する。

保管サーバ装置２００は、保存部２０１及び通信部２０２を備えている。

保存部２０１は、通信部２０２から読出／書込可能なハードウェア資源としての記憶装置であり、クライアント装置１００から配布された分散情報Ｄ（２）（＝Ｄ（ｎ）でｎ＝２）が記憶される。

通信部２０２は、クライアント装置１００から配布された分散情報Ｄ（２）を保存部２０１に書き込む機能と、クライアント装置１００から要求された分散情報Ｄ（２）を保存部２０１から読み出してこの分散情報Ｄ（２）をクライアント装置１００に返信する機能とをもっている。

なお、通信部２０２は、分散情報Ｄ（２）の漏洩防止の観点から、クライアント装置１００の認証機能を有してもよく、この場合、クライアント装置１００の認証の後、分散情報Ｄ（２）を返信する構成として設けられる。

ここで、各保管サーバ装置２００，３００，…，ｎ００は、他のクライアント装置や、ＵＳＢ(Universal Serial Bus)メモリ、携帯電話、ＰＤＡ(Personal Digital Assistants：携帯情報端末)に置き換え可能であり、あるいは外付けＨＤＤ(Hard Disc Drive: 固定磁気ディスク装置)などのように、コンピュータ以外の他の装置と置き換えることも可能である。

なお、各保管装置２００，３００，…，ｎ００は、他のクライアント装置に置き換えられる場合、前述同様に、分散部分データ生成部１０５や元データ復元部１０７などの機能を保持していてもよい。すなわち、秘密情報を復元できる装置は、クライアント装置１００以外にあってもよい。例えば、各保管装置２００，３００，…，ｎ００のうちの任意の台数の装置ｊ００，…が秘密情報を復元できる構成としてもよい。

なお、分散の場合も同様に、秘密情報を分散できる装置は、クライアント装置１００以外にあってもよい。例えば、各保管装置２００，３００，…，ｎ００のうちの任意の台数の装置ｊ００，…が分散情報を配布できる構成としてもよい。

また、各保管装置２００，３００，…，ｎ００がＵＳＢメモリや携帯電話などのように物理的な接続手段又は無線通信手段を有する装置に置き換えられる場合、ネットワークＮＷを省略してもよい。上述した各保管装置２００，３００，…，ｎ００を他の装置に置き換えた変形例は、以下の各実施形態でも同様に適用可能である。

次に、以上のように構成された秘密分散システムの動作を図１５乃至図１８のフローチャートを参照しながら説明する。
始めに、ｎ人のメンバ（初期メンバ）に、秘密情報Ｓを（ｋ，ｎ）閾値法で分散した分散情報Ｄ（ｊ）を配布する場合を考える。このときｎは素数を選ばなければならない。従って、合成数のｎ人に分散情報を配布したい場合は、ｎ＜ｎ’でありかつｎ’が素数となるようなｎ’について秘密分散法を適用することになる。以下では（ｋ，ｎ）閾値法についての一例を示す。

（分散処理の動作）
クライアント装置１００においては、分散情報Ｄ（１）〜Ｄ（ｎ）を配布する前に、ビット長ｍの秘密情報Ｓが一時的に保存部１０１に記憶されているとする。

このとき、クライアント装置１００においては、図１５に示すように、操作者の操作により、分散処理の開始命令が入力部１０２から入力されたとする（ＳＴ１）。

クライアント装置１００は、この開始命令に基づいて、分散処理を開始する。制御部１０９は、分散数をｎ、閾値をｋ、秘密情報Ｓのビット長をｍ、処理単位ビットをａと定める（ＳＴ１）。なお、秘密情報Ｓのビット長ｍは、保存部１０１内の秘密情報Ｓから分かる。処理単位ビットａは、分散データ生成部１３の仕様により予め定まっている。

続いて、制御部１０９は、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａを超える（ｍ／（ｎ−１）＞ａ）か否かを判定し（ＳＴ２）、処理単位ビットａを超える場合、ｎより大きい素数ｎ’を探索し、得られた素数ｎ’を分散数ｎと置き換えて（ＳＴ３）、ステップＳＴ１に戻る。

一方、ステップＳＴ２の判定結果が否の場合、制御部１０９は、分散数ｎ及び閾値ｋを生成行列生成部１０３に入力する。

生成行列生成部１０３は、分散数ｎ、閾値ｋの生成行列Ｇ（但し、任意のｋ個の列ベクトルがフルランク、行列Ｇのサイズはｋ（ｎ−１）×ｎ（ｎ−１）、列ベクトルのサイズはｋ（ｎ−１）×（ｎ−１)）を制御部１０９に出力する（ＳＴ４）。

以下、ステップＳＴ４における生成行列Ｇの生成処理の手順を説明する。

生成行列生成部１０３は、図１６に示すように、（ｎ−１）行×（ｎ−１）列で区分けした行列に対して、それぞれ（ｎ−１）行×（ｎ−１）列の単位行列Ｅの最終行に１行のゼロ行列を追加して得られたｎ行×（ｎ−１）列の行列Ｅ’を縦方向に(i-1)(j-1)ビット巡回シフトし、得られた行列Ｅ’（(i-1)(j-1)）の上から（ｎ−１）行×（ｎ−１）列を抽出した小行列Ｅ（(i-1)(j-1)）を配置して生成行列Ｇを生成する（ＳＴ４−１）。（４，５）閾値法の例では、生成行列Ｇは図２に示すような構成となる。

しかる後、生成行列生成部１０３は、得られた生成行列Ｇを制御部１０９に出力する（ＳＴ４−２）。

以上により生成行列Ｇの生成処理が完了する。

ステップＳＴ４の完了後、制御部１０９は、秘密情報Ｓ、生成行列Ｇ、分散数ｎ及び閾値ｋを分散部分データ生成部１０５に入力する。

分散部分データ生成部１０５は、図１５に示すように、秘密情報Ｓ及び分散数ｎに基づいて、ビット長ｍの秘密情報Ｓをｎ−１個に分割した際のビット長（ｍ／（ｎ−１））が処理単位ビットａと等しいか（ｍ／（ｎ−１）＝ａ）か否かを判定する（ＳＴ５）。

ステップＳＴ４の判定結果が否の場合、分散部分データ生成部１０５は、秘密情報Ｓをｎ−１個の分割秘密データＫ（１）〜Ｋ（ｎ−１）に分割した際の末尾の分割秘密データＫ（ｎ−１）をパディングする（パディング有）とし（ＳＴ６）、ステップＳＴ７に進む。

なお、パディングは、必ずしも末尾の分割秘密データＫ（ｎ-2）に行わなくても良く、他の分割秘密データＫ（ｊ）に行っても良い。但し、本実施形態では、秘密情報Ｓは４個にちょうど分割できた場合（パディング無し）を例に挙げて述べる。また、図２に示した如き、分散数ｎ＝５，閾値ｋ＝４の（４，５）閾値法を例に挙げて述べる。

ステップＳＴ５の判定の結果、処理単位ビットａと等しい場合、分散部分データ生成部１０５は、この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する（ＳＴ７）。（４，５）閾値法の例では、分割秘密データＫ（１），…，Ｋ（４）が生成される。

次に、各分割秘密データのサイズと同一のサイズの乱数を（ｋ−１）（ｎ−１）個生成し、乱数データＲ（１），…，Ｒ（（ｋ−１）（ｎ−１））を生成する（ＳＴ７）。（４，５）閾値法の例では、乱数データＲ（１），…，Ｒ（１２）が生成される。

分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）、乱数データＲ（１），…，Ｒ（（ｋ−１）（ｎ−１））及び生成行列Ｇに基づいて、ｎ（ｎ−１）個の分散部分データ（Ｄ（１，１），…，Ｄ（ｊ，ｉ），…，Ｄ（ｎ，ｎ−１））＝（Ｒ（１），…，Ｒ（（ｋ−１）（ｎ−１）），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））Ｇを算出する（ＳＴ８）。なお、処理単位ビットａにあわせて、生成行列Ｇの要素が１の場合はａ×ａのＧＦ（２）上の単位行列、０の場合はａ×ａのＧＦ（２）上のゼロ行列として扱う。（４，５）閾値法の例では、図１３に示したように、２０個の分散部分データＤ（ｊ，ｉ）が生成される。例えば、分散部分データＤ（１，１）の算出過程を図２０に示す。

しかる後、分散部分データ生成部１０５は、得られた分散部分データｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）を制御部１０９に出力する。

制御部１０９は、各分散部分データのうち、同一の行番号ｊを有するｎ−１個の分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ−１）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（１），…，Ｈ（ｊ），…，Ｈ（ｎ）を生成する（ＳＴ９）。ヘッダ情報Ｈ（ｊ）には、Ｋ（ｎ−１）に対するパディングの有無、元データのサイズなどの情報が含まれる。

制御部１０９は、互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ-１）からなるｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）を個別にｎ個の保存部１０１，２０１，…，ｎ０１に配布するように、分散情報Ｄ（１）を保存部１０１に書き込み、分散情報Ｄ（２），…，Ｄ（ｎ）を個別に保管サーバ装置２００，…，ｎ００に配布する（ＳＴ１０）。（４，５）閾値法の例では、５個の分散情報Ｄ（１），…，Ｄ（５）が配布される。各保管サーバ装置２００〜５００では、配布された分散情報Ｄ（２），…，Ｄ（５）を保存部２０１〜５０１に記憶する。

以上により、秘密情報の分散処理が完了する。

なお、（４，５）閾値法において、必ずしも５個の分散情報Ｄ（１）〜Ｄ（５）を配布する必要は無い。例えば４個の分散情報Ｄ（１）〜Ｄ（４）を配布しておき、残り１個の分散情報Ｄ（５）を管理者が適切に保管しておき、新メンバが追加されたときに新メンバに配布してもよい。

（復元処理の動作）
クライアント装置１００においては、操作者の操作により、復元処理の開始命令が入力部１０２から入力されたとする。

クライアント装置１００は、この開始命令に基づいて、図１７に示すように、復元処理を開始する。制御部１０９は、ｎ台の装置１００，…，ｎ００に配布したｎ個の分散情報Ｄ（１）〜Ｄ（ｎ）のうち、任意のｋ個の分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）（但し、１≦ｉ_ｊ≦ｎ）を収集する（ＳＴ１１）。

制御部１０９は、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）のヘッダ情報Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から生成行列Ｇのｋ個の列ベクトルｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ）を得ると、このｋ個の列ベクトルから生成行列Ｇの部分行列Ｇ’＝（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））を形成して取得する（ＳＴ１２）。

次に、制御部１０９は、生成行列Ｇの部分行列Ｇ’を復元行列生成部１０４に入力する。

復元行列生成部１０４は、生成行列Ｇの部分行列Ｇ’＝（ｇ（Ｄ（ｉ_1）），…，ｇ（Ｄ（ｉ_ｊ）），…，ｇ（Ｄ（ｉ_ｋ））から当該部分行列Ｇ’を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けした１行目の成分を全てゼロにするための基本行列Ｂ⁽¹⁾を生成する。

具体的には、復元行列生成部１０４は、ｋ（ｎ−１）行×ｋ（ｎ−１）列の行列を（ｎ−１）行×（ｎ−１）列の単位で区分けした行列のｄ行ｄ＋１〜ｋ列に単位行列Ｅを配置する（ＳＴ１３−１）。

さらに、復元行列生成部１０４は、当該区分けした行列のｄ＋１〜ｋ行ｄ＋１〜ｋ列に、部分行列Ｇ’から得られるＵ_d,j ^-1×Ｕ_d,dを配置する（ＳＴ１３−２）。

また、復元行列生成部１０４は、当該区分けした行列の残りの成分に、ゼロ行列を配置し（ＳＴ１３−３）、基本行列Ｂ⁽¹⁾を生成する。

続いて、復元行列生成部１０４は、部分行列Ｇ’に基本行列Ｂ⁽¹⁾を乗じて、区分けした１行目の成分を全てゼロにする処理を行い、部分行列Ｇ⁽¹⁾＝Ｇ’Ｂ⁽¹⁾を得る。

また同様に、復元行列生成部１０４は、当該部分行列Ｇ⁽¹⁾を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けした２行目の成分を全てゼロにするための基本行列Ｂ⁽²⁾を生成し、部分行列Ｇ⁽¹⁾に基本行列Ｂ⁽²⁾を乗じて、区分けした２行目の成分を全てゼロにする処理を行い、部分行列Ｇ⁽²⁾＝Ｇ⁽¹⁾Ｂ⁽²⁾を得る。

以下同様にして、再帰的にｋ−１行目まで処理を実行し、部分行列Ｇ^(k-1)＝Ｇ^(k-2)Ｂ^(k-1)を得る（ＳＴ１３）。

また別の具体例として、復元行列生成部１０４は、ｋ（ｎ−１）行×ｋ（ｎ−１）列の行列を（ｎ−１）行×（ｎ−１）列の単位で区分けした行列のｄ＋１〜ｋ行ｄ＋１〜ｋ列に単位行列Ｅを配置する（ＳＴ１３’−１）。

さらに、復元行列生成部１０４は、当該区分けした行列のｄ行ｄ＋１〜ｋ列に、部分行列Ｇ’から得られるＵ_d,d ^-1×Ｕ_d,jを配置する（ＳＴ１３’−２）。

また、復元行列生成部１０４は、当該区分けした行列の残りの成分に、ゼロ行列を配置し（ＳＴ１３’−３）、基本行列Ｂ⁽¹⁾を生成する。

続いて、復元行列生成部１０４は、部分行列Ｇ’に基本行列Ｂ⁽¹⁾を乗じて、区分けした１行目の成分を全てゼロにする処理を行い、部分行列Ｇ⁽¹⁾＝Ｇ’Ｂ⁽¹⁾を得る。

また同様に、復元行列生成部１０４は、当該部分行列Ｇ⁽¹⁾を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けした２行目の成分を全てゼロにするための基本行列Ｂ⁽²⁾を生成し、部分行列Ｇ⁽¹⁾に基本行列Ｂ⁽²⁾を乗じて、区分けした２行目の成分を全てゼロにする処理を行い、部分行列Ｇ⁽²⁾＝Ｇ⁽¹⁾Ｂ⁽²⁾を得る。

以下同様にして、再帰的にｋ−１行目まで処理を実行し、部分行列Ｇ^(k-1)＝Ｇ^(k-2)Ｂ^(k-1)を得る（ＳＴ１３）。

このとき、復元行列生成部１０４は、基本行列の積Ｂ⁽¹⁾…Ｂ^(k-1)を算出する（ＳＴ１４−１）。続いて、復元行列生成部１０４は、部分行列Ｇ^(k-1)におけるｋ行ｋ列目の行列Ｕ_(k,k)の逆行列Ｕ_(k,k) ^-1をｋ行ｋ列目に配置して他の成分をゼロにした基本行列Ｂ^(k)を算出し、前述した基本行列の積Ｂ⁽¹⁾…Ｂ^(k-1)にこの基本行列Ｂ^(k)を乗じて復元行列Ｂ⁽¹⁾…Ｂ^(k-1)Ｂ^(k)を算出する（ＳＴ１４−２）。

（４，５）閾値法の例では、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）に対応する部分行列Ｇ’（ｇ（Ｄ（１）），ｇ（Ｄ（２）），ｇ（Ｄ（３）），ｇ（Ｄ（４）））は図２の１列目〜１６列目に示したような行列になり、分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）に対して、図１８または図１９に示すように基本行列を用いて（ｎ−１）行（ｎ−１）列で区分けした成分を全てゼロにする処理を１行目から３行目まで繰り返し、最後に区分けしたｋ行ｋ列目の逆行列を算出することで復元行列Ｂ⁽¹⁾Ｂ⁽²⁾Ｂ⁽³⁾Ｂ⁽⁴⁾を算出する。図１８で示した基本行列を用いた場合における復元行列は図１２に示したような行列となる。

制御部１０９は、生成行列Ｇの復元行列と分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）を元データ復元部１０７に入力する。

元データ復元部１０７は、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）のヘッダ情報Ｈ（ｉ_1），…，Ｈ（ｉ_ｊ），…，Ｈ（ｉ_ｋ）から、図１７に示すように、分散情報Ｄ（ｉ_1），…，Ｄ（ｉ_ｊ），…，Ｄ（ｉ_ｋ）であることを解析する。（４，５）閾値法の例では、例えば分散情報Ｄ（１），Ｄ（２），Ｄ（３），Ｄ（４）であることを確認する。

次に、分散情報からなる行列（Ｄ（ｉ_1），…，Ｄ（ｉ_j），…，Ｄ（ｉ_k））と復元行列Ｂ⁽¹⁾Ｂ⁽²⁾…Ｂ^(k-1)Ｂ^(k)との積を算出し、分割秘密データＫ（１），…，Ｋ（ｎ−１）を得る（ＳＴ１５）。なお、処理単位ビットａにあわせて、復元行列の要素が１の場合はａ×ａのＧＦ（２）上の単位行列、０の場合はａ×ａのＧＦ（２）上のゼロ行列として扱う。

具体的には（４，５）閾値法において、分散情報Ｄ（２），Ｄ（３），Ｄ（４），Ｄ（５）から復元した場合、図２１に示したように、例えば復元行列の１３列目から分割秘密データＫ（１）が算出される。同様に１４列目、１５列目、１６列目から、それぞれＫ（２）、Ｋ（３）、Ｋ（４）を算出する。このとき、復元行列の１列目〜１２列目はゼロ行列であって演算に用いられないので、演算の負荷が小さくて済む。

制御部１０９は、分割秘密データＫ（１），…，Ｋ（ｎ−１）に対して、ヘッダ情報Ｈ（ｉ），Ｈ（ｊ）に基づいて、パディングなどの処理があれば除去する。

しかる後、制御部１０９は、分割秘密データＫ（１），…，Ｋ（ｎ−１）を互いに連接することにより、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（ｎ−１）を復元する（ＳＴ１６）。この例では、秘密情報Ｓ＝Ｋ（１）‖Ｋ（２）‖…‖Ｋ（４）が復元される。

上述したように本実施形態によれば、生成行列Ｇを用いて分散部分データを生成する構成により、秘密情報の分散や復元の処理を排他的論理和により非常に高速に実現し、多項式補間を用いずに高速に実行可能な（ｋ，ｎ）閾値法を実現することができる。

本実施形態は、分散数ｎ及び閾値ｋが限定されないので、各種のシステムへの応用範囲を広げることができる。

また、本実施形態の分散処理は、多項式補間が不要であり、ＸＯＲのみで実行するため、前述した高速に実行可能なことに加え、大容量データを扱うのに好適である。

また、復元処理は生成行列Ｇの部分行列Ｇ’の逆行列を求めることなく、生成行列Ｇの部分行列Ｇ’を（ｎ−１）行（ｎ−１）列のブロック単位で再帰的に処理して復元行列を求める構成により、部分行列Ｇ’の逆行列を求める場合よりも高速に実行可能であり、低スペック機器でも秘密分散を実行できる利点を有する。

この利点について、計算量の面で比較する。ここで、行列の乗算の計算量は行列のサイズの２乗のオーダーであり、逆行列の計算量は行列のサイズの３乗のオーダーとなることが知られている。したがって、逆行列の計算量のほうが乗算の計算量よりも大きいので、復元処理の計算量は逆行列のサイズや回数で評価することができる。

まず、生成行列Ｇの逆行列を用いる場合の計算量は、生成行列Ｇのサイズがｋ（ｎ−１）行×ｋ（ｎ−１）列なので、計算量は（ｋ（ｎ−１））^３であり、一般的にはＯ（（ｋｎ）^３）で表すことができる。

ここでＯ（・）は、計算量のオーダーが・であることを意味する。

次に、図８のように再帰的に処理して復元行列を求める場合は、サイズ（ｎ−１）行×（ｎ−１）列の逆行列の計算が

回必要となるので、逆行列の計算は（ｎ−１）^３であり、その回数が（（ｋ−２）（ｋ−１）／２）＋１回であるので、その計算量は一般的にＯ（ｋ^２ｎ^３）で表すことができる。

次に、図９のように再帰的に処理して復元行列を求める場合は、サイズ（ｎ−１）行×（ｎ−１）列の逆行列の計算が（ｋ−２）＋１回必要となるので、その計算量はＯ（ｋｎ^３）で表すことができる。

したがって、図８よりも図９のように処理するほうが、より好ましい実施形態といえる。

また、復元処理においては、復元行列を求める処理が高速なことに加え、復元行列の乗算処理も高速に実行できる。乗算処理が高速な理由は、復元行列を（ｎ−１）行×（ｎ−１）列の単位で区分けした行列において、復元行列の１列目からｋ−１列目の成分がゼロ行列であって乗算に用いられず、復元行列のｋ列目の成分のみが乗算に用いられるためである。

なお、本実施形態は、生成行列生成部１０３により生成行列Ｇを生成し、復元行列生成部１０４により復元行列を生成した場合について説明したが、これに限らず、分散数ｎ及び閾値ｋが予め分かっていれば、図２２に示すように、生成行列生成部１０３及び復元行列生成部１０４に代えて、予め生成行列Ｇ及びＧの復元行列のデータが保存された読出／書込可能な記憶装置としての行列保存部１１２を備えた構成に変形してもよい。このように変形することで排他的論理和演算のみで分散・復元処理が可能な（ｋ，ｎ）閾値法を実現することができる。

また同様に、分散数ｎと閾値ｋとの組合せ毎に、予め生成行列Ｇ及びＧの復元行列のデータを行列保存部１１２に保存しておき、入力されたｎ，ｋの値を検索キーにして、行列保存部１１２から生成行列Ｇ及びＧの復元行列のデータを読み出す構成に変形してもよいことはいうまでもない。

また一般に、（ｋ，ｎ）閾値法において、秘密情報Ｓのサイズを｜Ｓ｜とすると、分散に必要な乱数のサイズ｜Ｒ｜が次式を満たすことが知られている。

｜Ｒ｜≧（ｋ−１）｜Ｓ｜
ここで、本実施形態においては、乱数のサイズが上式の下限を満たしていることが明らかであり、次式の通り、乱数のサイズ｜Ｒ｜が（ｋ，ｎ）閾値法の分散に必要な最小のサイズとなっている。

｜Ｒ｜＝（ｋ−１）｜Ｓ｜
このため、本実施形態では、秘密情報Ｓの分散処理に必要な演算を高い効率で実施することができる。

一方、非特許文献３に記載の（３，５）閾値法の乱数のサイズを比較のために述べる。非特許文献３においては、秘密情報Ｓを分割した部分秘密情報Ｓ_iと乱数成分Ｒ，Ｔを分割した乱数情報Ｒ_i，Ｔ_iからなるベクトルＵをＵ＝（Ｓ₁，…Ｓ₄，Ｒ₁，…Ｒ₄，Ｔ₁，…Ｔ₅）と表記し、（３，５）閾値法の生成行列をＧ（３）とすると、Ｇ（３）は非特許文献３の表３から次のようになる。

ここで、Ｇ（２）は非特許文献２の表２の(２，５)閾値法における生成行列とし、（３，５）閾値法における乱数成分Ｔと関係する下の区分けしたブロックは、本実施形態で示したＥ’そのものであり、そのサイズが５×４行列となっている。従って、非特許文献３記載の方式の乱数成分のサイズ｜Ｒ｜は次式で表される。

すなわち、非特許文献３記載の方式は、本実施形態とは異なり、乱数成分のサイズ｜Ｒ｜が下限になっていないことが分かる。

次に、本実施形態において、生成行列Ｇを構成するＧiについて考察する。（ｋ，ｎ）閾値法において、生成行列Ｇを構成する区分けしたｉブロック目のＧ_i,kと、（ｋ−１，ｎ）閾値法において、生成行列Ｇを構成する区分けしたｉブロック目のＧ_i,k-1とには次式の関係がある。

すなわち、（ｋ，ｎ）閾値法のＧ_i,kは、（ｋ−１、ｎ）閾値法のＧ_i,k-1を用いて帰納的に求めることができる。

（第２の実施形態）
次に、本発明の第２の実施形態に係る秘密分散システムについて説明する。

本実施形態は、第１の実施形態の変形例である。第１の実施形態においては、生成行列Ｇを（ｎ−１）行（ｎ−１）列の単位行列Ｅにゼロ行列を付加した行列Ｅ’を巡回シフトさせることにより、生成行列Ｇを生成する。

一方、本実施形態では、第１の実施形態の単位行列Ｅに代えて、図２３に示す如き、より一般的に行列式が１となる（ｎ−１）行（ｎ−１）列の行列を巡回シフトさせることにより、生成行列Ｇを生成する構成となっている。ここで、行列式が１となる行列とは、ランクがフルランクな行列を意味する。

すなわち、本実施形態は、第１の実施形態に比べ、行列式が１となる（ｎ−１）行（ｎ−１）列の行列を用いて生成行列Ｇを生成する点のみ異なり、他の処理については第１の実施形態と同一構成となっている。

以上のような構成としても、第１の実施形態と同様の作用効果を得ることができる。

（第３の実施形態）
次に、本発明の第３の実施形態に係る秘密分散システムについて説明する。

本実施形態は、第１の実施形態の変形例である。第１の実施形態においては、（ｋ，ｎ）閾値法を用いて、分散処理及び復元処理を実行している。

一方、本実施形態では、第１の実施形態の（ｋ，ｎ）閾値法に代えて、（ｎ，ｎ）閾値法を用いることにより、復元処理の高速化を図っている。これに伴い、復元行列生成部１０４に代えて、逆行列Ｇ^-1の生成処理が必要となる。

分散部分データ生成部１０５は、制御部１０９により制御され、保存部１０１に一時的に記憶された秘密情報Ｓ及び生成行列Ｇに基づいて、ｎ個の分散情報Ｄ（１）〜Ｄ（ｎ）を生成する機能を持っている。

具体的には、予め分散処理で作成した生成行列Ｇに対して逆行列Ｇ^-1を求め、図２４に示すように、その逆行列Ｇ^-1を生成行列Ｇとみなしてｎ個の分散情報Ｄ（１）〜Ｄ（ｎ）を生成する。

復元時には、ｎ個の分散情報Ｄ（１）〜Ｄ（ｎ）を集め、図２５に示すように、分散処理で生成した生成行列Ｇを復元行列とみなして復元処理を行う。

以上のような構成によれば、第１の実施形態と同様の作用効果に加え、復元処理を高速に実行することができる。

なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。

また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。

また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。

さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。

また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。

尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。

また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。

なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。

本発明の第１の実施形態に係る秘密分散システムの構成を示す模式図である。 同実施形態における生成行列の一例を示す模式図である。 同実施形態における区分けした１ブロックの行列を説明するための模式図である。 同実施形態における１ブロックの行列の巡回シフトを説明するための模式図である。 同実施形態における巡回シフト後の行列の取得及び割当てを説明するための模式図である。 同実施形態における生成行列を説明するための模式図である。 同実施形態における基本行列の生成を説明するための模式図である。 同実施形態における基本行列の構成を説明するための模式図である。 同実施形態における基本行列の別の構成を説明するための模式図である。 同実施形態における基本行列の構成を説明するための模式図である。 同実施形態における基本行列の一例を示す模式図である。 同実施形態における復元行列の一例を示す模式図である。 同実施形態における分散情報を説明するための模式図である。 同実施形態におけるヘッダ情報および分散情報の一例を示す模式図である。 同実施形態における分散処理の動作を説明するためのフローチャートである。 同実施形態における分散処理の動作を説明するためのフローチャートである。 同実施形態における復元処理の動作を説明するためのフローチャートである。 同実施形態における復元処理の動作を説明するためのフローチャートである。 同実施形態における別の基本行列を用いた復元処理の動作を説明するためのフローチャートである。 同実施形態における分散部分データの算出過程を説明するための模式図である。 同実施形態における分割秘密データの算出過程を説明するための模式図である。 同実施形態における変形構成を示す模式図である。 本発明の第２の実施形態に係る秘密分散システムに適用される行列式の一例を示す模式図である。 本発明の第３の実施形態に係る秘密分散システムに適用される生成行列の一例を示す模式図である。 同実施形態における復元行列の一例を示す模式図である。

符号の説明

１００…クライアント装置、１０１…保存部、１０２…入力部、１０３…生成行列生成部、１０４…復元行列生成部、１０５…分散部分データ生成部、１０６…ハッシュ値生成部、１０７…元データ復元部、１０８…ハッシュ値検証部、１０９…制御部、１１０…出力部、１１１…通信部、１１２…行列保存部、２００，３００，〜，ｎ００…保管サーバ装置、ＮＷ…ネットワーク。

Claims (6)

1. 秘密情報Ｓが分散されて生成されたｎ個の分散情報Ｄ（１），…，Ｄ（ｎ）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法（但し、２≦ｋ≦ｎ）の秘密分散装置であって、
   １個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつ列ベクトルｎ個からなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルから構成される行列がフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段と、
   前記分散情報Ｄ（１）〜Ｄ（ｎ）が配布される前に、前記秘密情報Ｓが一時的に記憶される記憶手段と、
   この秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段と、
   前記各分割秘密データのサイズと同一サイズの（ｋ−１）（ｎ−１）個の乱数データＲ（１），…，Ｒ（（ｋ−１）（ｎ−１））を生成する手段と、
   前記乱数データ及び前記分割秘密データ（Ｒ（１），…，Ｒ（（ｋ−１）（ｎ−１）），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と前記生成行列Ｇとの行列の積を算出し、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、１≦ｊ≦ｎ、１≦ｉ≦ｎ−１）を算出する分散部分データ算出手段と、
   前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ−１）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（１），…，Ｈ（ｊ），…，Ｈ（ｎ）を生成する手段と、
   互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ−１）と、前記ｎ個の列ベクトルの各々とからなるｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）を個別に前記ｎ個の記憶装置に配布する手段と、
   配布したｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）のうち任意のｋ個の分散情報に含まれるｋ個の列ベクトルから生成行列Ｇのうちのｋ（ｎ−１）行×ｋ（ｎ−１）列の部分行列Ｇ’を構成し、この部分行列Ｇ’を（ｎ−１）行×（ｎ−１）列で区分けした行列単位で１行目からｋ−１行目までの乱数成分をゼロにするように基本行列Ｂ⁽¹⁾，…，Ｂ^(k-1)を再帰的に部分行列Ｇ’，…，Ｇ^(k-2)に乗じることにより、最後に乗じて得られた部分行列Ｇ^(k-1)の区分けした単位におけるｋ行ｋ列目の成分の逆行列を用いて基本行列Ｂ^(k)を作成し、全ての基本行列を乗じて復元行列Ｂ⁽¹⁾…Ｂ^(k-1)Ｂ^(k)を算出する復元行列算出手段と、
   当該ｋ個の分散情報に前記復元行列を乗算することにより、秘密情報を復元する復元手段と
   を備えたことを特徴とする秘密分散装置。
2. 請求項１に記載の秘密分散装置において、
   前記任意のｋ個はｎ個であり、
   前記分散部分データ算出手段は、前記生成行列Ｇに代えて、前記生成行列の逆行列Ｇ^-1を用いて前記分散部分データを算出し、
   前記復元行列算出手段及び前記復元手段に代えて、前記ｋ個の分散情報に前記逆行列Ｇ^-1を乗算することにより、秘密情報を復元する手段を備えたことを特徴とする秘密分散装置。
3. 請求項１又は請求項２に記載の秘密分散装置が実行する秘密分散方法であって、
   入力された分散数ｎ及び閾値ｋを前記記憶手段に記憶する工程と、
   前記記憶手段内の分散数ｎ及び閾値ｋに基づいて、（ｎ−１）行×（ｎ−１）列の単位で行列を区分けした際に、区分けしたｉ行ｊ列のブロックについて、（ｎ−１）行×（ｎ−１）列の単位行列Ｅの最終行に１行×（ｎ−１）列のゼロ行列を追加し、ｎ行×（ｎ−１）列の行列Ｅ’を生成する工程と、
   ｎ行×（ｎ−１）列の行列Ｅ’を縦方向に（ｉ−１）（ｊ−１）回巡回シフトして行列Ｅ’（(i-1)(j-1)）を作成する巡回シフト工程と、
   この行列Ｅ’（(i-1)(j-1)）から最終行を除いた（ｎ−１）行×（ｎ−１）列の行列Ｅ（(i-1)(j-1)）を取得して、ｉ行ｊ列のブロックに割り当てる割当て工程と、
   前記巡回シフト工程及び割当て工程を前記ｉ行ｊ列の全てのブロック（１≦ｉ≦ｋ、１≦ｊ≦ｎ）に対して実行することにより、生成行列Ｇを生成する工程と、
   を備えたことを特徴とする秘密分散方法。
4. 請求項３に記載の秘密分散方法であって、
   前記生成行列Ｇの部分行列Ｇ’＝（ｇ（Ｄ（ｉ_1），…，Ｄ（ｉ_k））＝（Ｕ_(1,1)，…，Ｕ_(i,j)，…，Ｕ_(k,k)）（但し、Ｕ_(i,j)＝Ｅ（(i-1)(j-1)））から当該部分行列Ｇ’を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けした１行目の成分を全てゼロにするための基本行列Ｂ⁽¹⁾を生成する工程と、
   前記部分行列Ｇ’に基本行列Ｂ⁽¹⁾を乗じて、区分けした１行目の成分を全てゼロにする処理を行い、部分行列Ｇ⁽¹⁾＝Ｇ’Ｂ⁽¹⁾を得る工程と、
   得られた部分行列を部分行列Ｇ^(d-1)としたとき、この部分行列Ｇ^(d-1)を（ｎ−１）行×（ｎ−１）列の単位で区分けした際に、区分けしたｄ行目の成分を全てゼロにするための基本行列Ｂ^(d)を生成する基本行列生成工程と、
   前記部分行列Ｇ^(d-1)に基本行列Ｂ^(d)を乗じて、区分けしたｄ行目の成分を全てゼロにする処理を行い、部分行列Ｇ^(d)＝Ｇ^(d-1)Ｂ^(d)を得る部分行列生成工程と、
   前記基本行列生成工程及び前記部分行列生成工程をｄ＝ｋ−１行目まで再帰的に実行し、部分行列Ｇ^(k-1)＝Ｇ^(k-2)Ｂ^(k-1)を得る工程と、
   この部分行列Ｇ^(k-1)におけるｋ行ｋ列目の行列Ｕ_(k,k)の逆行列Ｕ_(k,k) ^-1をｋ行ｋ列目の成分に配置すると共に、ゼロ行列を他の成分に配置して基本行列Ｂ^(k)を算出する工程と、
   全ての基本行列Ｂ⁽¹⁾，…，Ｂ^(k-1)，Ｂ^(k)を乗じて復元行列Ｂ⁽¹⁾…Ｂ^(k-1)Ｂ^(k)を生成する工程と、
   を備えたことを特徴とする秘密分散方法。
5. 秘密情報Ｓが分散されて生成されたｎ個の分散情報Ｄ（１），…，Ｄ（ｎ）を個別にｎ個の記憶装置に配布し、且つ、前記ｎ個の分散情報のうち、任意のｋ個の分散情報から秘密情報Ｓを復元可能な（ｋ，ｎ）閾値法（但し、２≦ｋ≦ｎ）の秘密分散装置のプログラムであって、
   前記秘密分散装置のコンピュータを、
   １個あたりｋ（ｎ−１）行×（ｎ−１)列のサイズをもつ列ベクトルｎ個からなり、前記ｎ個の列ベクトルのうちの任意のｋ個の列ベクトルから構成される行列がフルランクとなるＧＦ（２）の生成行列Ｇを生成する（但し、前記生成行列Ｇのサイズはｋ（ｎ−１）行×ｎ（ｎ−１）列、ＧＦ（２）は位数２の有限体）手段、
   前記分散情報Ｄ（１）〜Ｄ（ｎ）が配布される前に、前記秘密情報Ｓを一時的に前記コンピュータのメモリに書き込む手段、
   前記メモリ内の秘密情報Ｓをｎ−１個に分割すると共に、分割結果に１からｎ−１までの行番号ｊ（但し、１≦ｊ≦ｎ−１）を割り当てることにより、互いに同一サイズのｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１）を生成する手段、
   前記各分割秘密データのサイズと同一サイズの（ｋ−１）（ｎ−１）個の乱数データＲ（１），…，Ｒ（（ｋ−１）（ｎ−１））を生成する手段、
   前記乱数データ及び前記分割秘密データ（Ｒ（１），…，Ｒ（（ｋ−１）（ｎ−１）），Ｋ（１），…，Ｋ（ｊ），…，Ｋ（ｎ−１））と前記生成行列Ｇとの行列の積を算出し（但し、ＧＦ（２）上の演算）、この算出結果のｊ×（ｎ−１）+ｉ列目を分散部分データＤ（ｊ，ｉ）に割り当てて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）（但し、１≦ｊ≦ｎ、１≦ｉ≦ｎ−１）を算出する分散部分データ算出手段、
   前記各分散部分データのうち、同一の行番号ｊを有するｎ−１個の前記分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ−１）毎に、行番号ｊを割り当ててｎ個のヘッダ情報Ｈ（１），…，Ｈ（ｊ），…，Ｈ（ｎ）を生成する手段、
   互いに同一の行番号ｊを有するヘッダ情報Ｈ（ｊ）及び分散部分データＤ（ｊ，１）〜Ｄ（ｊ，ｎ−１）と、前記ｎ個の列ベクトルの各々とからなるｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）を個別に前記ｎ個の記憶装置に配布する手段、
   配布したｎ個の分散情報Ｄ（１），…，Ｄ（ｊ），…，Ｄ（ｎ）のうち任意のｋ個の分散情報に含まれるｋ個の列ベクトルから生成行列Ｇのうちのｋ（ｎ−１）行×ｋ（ｎ−１）列の部分行列Ｇ’を構成し、この部分行列Ｇ’を（ｎ−１）行×（ｎ−１）列で区分けした行列単位で１行目からｋ−１行目までの乱数成分をゼロにするように基本行列Ｂ⁽¹⁾，…，Ｂ^(k-1)を再帰的に部分行列Ｇ’，…，Ｇ^(k-2)に乗じることにより、最後に乗じて得られた部分行列Ｇ^(k-1)の区分けした単位におけるｋ行ｋ列目の成分の逆行列を用いて基本行列Ｂ^(k)を作成し、全ての基本行列を乗じて復元行列Ｂ⁽¹⁾…Ｂ^(k-1)Ｂ^(k)を算出する手段、
   当該ｋ個の分散情報に前記復元行列を乗算することにより、秘密情報を復元する復元手段、
   として機能させるためのプログラム。
6. 請求項５に記載のプログラムにおいて、
   前記任意のｋ個はｎ個であり、
   前記分散部分データ算出手段は、前記生成行列Ｇに代えて、前記復元行列を用いて前記分散部分データを算出する手段であり、
   前記復元行列算出手段及び前記復元手段に代えて、前記ｋ個の分散情報に前記逆行列Ｇ^-1を乗算することにより、秘密情報を復元する手段、として前記コンピュータを機能させるためのプログラム。

Images