"分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、前記分散情報生成装置は、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力し、前記n個の記憶装置は前記分散情報生成装置の出力を記憶し、前記復元装置は、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから前記分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする秘密情報分散システム。請求項1に記載の秘密情報分散システムであって、前記分散情報生成装置は、秘密情報をk,n閾値秘密分散法で分散符号化し、n個の分散情報v[1],v[2],...,v[n]を生成する秘密情報分散手段と、前記秘密情報の検証を行うn個のチェック用データe[1],e[2],...,e[n]を生成するチェック用データ生成手段と、前記分散情報v[1],...,v[n]と、チェック用データe[1],...,e[n]とを入力とし、予め定められたチェック関数hに入力して得られる出力a[i,j]=he[i],v[j]i≠jからn個の認証データa[i]=a[i,1],a[i,2],...,a[i,i-1],a[i,i1],...,a[i,n]i=1,...,nを出力する認証データ生成手段とを備え、前記記憶装置は、前記分散情報生成装置が生成した分散符号化された前記分散情報v[i]を格納する分散秘密情報記憶手段と、前記チェック用データ生成装置が生成した前記チェック用データe[i]を格納するチェック用データ記憶手段と、前記認証データ生成装置が生成した前記認証データa[i]を格納する認証データ記憶手段とを備え、前記復元装置は、k個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、k個以上の前記記憶装置から分散情報v[i-1],v[i-2],...,v[i-m]と、チェック用データe[i-1],e[i-2],...,e[i-m]と、認証データa[i-1],a[i-2],...,a[i-m]とを読み出し、全ての可能な相異なるi,ji,j=i-1,...,i-mに対して、he[i],v[j]=a[i,j]なる式が成立するか否かを判定し、当該判定の結果、k/2個以上のe[i]に対して前記式が成立しなかったv[j]が存在する場合は、k/2個以上のe[i]に対して前記式が成立しなかったv[j]の識別子集合{i-j1,i-j2,...,i-jw}を出力し、当該判定の結果、k/2個以上のe[i]に対して前記式が成立しなかったv[j]がそのようなv[j]が存在しない場合は、復元した秘密情報sを出力する不正情報特定手段とを備え、前記チェック関数hh:E×V→Aは、集合Vの任意の要素v[1],v[2],...,v[t-1],v,v’t≧k/2と、集合Aの任意の要素a[1],a[2],...,a[k-2],a’に対して、|{e[j]|he[j],v=a,he[j],v’=a’,he[j],v[l]=a[l]l=1,2,...,t-1}|/|{e[j]|he[j],v=a,he[j],v[l]=a[l]}l=1,2,...,t-1|≦εを任意のi,j,lについて満足することを特徴とする秘密情報分散システム。請求項1又は2に記載の秘密情報分散システムにおいて、チェック関数hが、n個の部分情報v[1],...,v[n]と、チェック用データe[i]=e[i,1],e[i,2],...,e[i,i-1],e[i,i1],e[i,i2],...,e[i,n]i=1,...,n、但し、各e[i,j]=e[i,j]{0},e[i,j]{1}i=1,...,nとに対し、he[i],v[j]=e[i,j]{1}×v[j]e[i,j]{0}によって定義されることを特徴とする秘密情報分散システム。請求項1に記載の秘密情報分散システムにおいて、前記分散情報生成装置は、前記チェック用データeをt,n閾値秘密分散法で分散符号化したn個のチェック用データeを前記記憶装置に出力し、前記復元装置は、前記t,n閾値秘密分散法で分散符号化されたチェック用データeを更に用いて前記分散情報の正当性の判定を行うことを特徴とする秘密情報分散システム。請求項4に記載の秘密情報分散システムにおいて、前記分散情報生成装置は、秘密情報をk,n閾値秘密分散法で分散符号化し、n個の分散情報v[1],v[2],...,v[n]を生成する秘密情報分散手段と、前記秘密情報の検証を行うチェック用データeをt,n閾値秘密分散法で分散符号化したn個のチェック用データe[1],e[2],...,e[n]を生成するチェック用データ生成手段と、前記分散情報v[1],...,v[n]と、チェック用データeとを入力とし、予め定められたチェック関数hに入力して得られる出力a[i]=he,v[i]i=1,...,nを認証データとして出力する認証データ生成手段とを備え、前記記憶装置は、前記分散情報生成装置が生成した分散符号化された前記分散情報v[i]を格納する分散秘密情報記憶手段と、前記チェック用データ生成装置が生成した前記チェック用データe[i]を格納するチェック用データ記憶手段と、前記認証データ生成装置が生成した前記認証データa[i]を格納する認証データ記憶手段とを備え、前記復元装置は、k個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、k個以上の前記記憶装置から分散情報v[i-1],v[i-2],...,v[i-m]と、分散符号化されたチェック用データe[i-1],e[i-2],...,e[i-m]と、認証データa[i-1],a[i-2],...,a[i-m]とを読み出し、e[i-1],...,e[i-m]からチェック用データeを復元し、全てのii=i-1,...,i-mに対して、he,v[i]=a[i]i=1,2,...,mなる式が成立するか否かをチェックし、前記式が成立しなかったv[i]の識別子集合{i-j1,i-j2,...,i-jw}を出力し、そのようなv[i]が存在しない場合は、復元した秘密情報sを出力する不正情報特定手段とを備え、前記チェック関数hh:E×V→Aは、集合Vの任意の要素v[1],v[2],...,v[t-1],v,v’と、集合Aの任意の要素a[1],a[2],...,a[t-1],a’に対して、|{e|he,v=a,he,v’=a’,he,v[i]=a[i]i=1,2,...,t-1}|/|{e|he,v=a,he,v[i]=a[i]i=1,2,...,t-1}|≦εを任意のiについて満足することを特徴とする秘密情報分散システム。請求項4又は5に記載の秘密情報分散システムにおいて、チェック関数hが、n個の部分情報v[1],...,v[n]と、チェック用データe=e{0},e{1},...,e{t}と、p≧nとなる任意の素数と、関数ψv[i]=p×i-1v[i]とに対し、he[i],v[j]=e{0}e{1}×ψv[i]e{3}×ψv[i]^2...e{t}×ψv[i]^tによって定義されることを特徴とする秘密情報分散システム。請求項1乃至6の何れか1項に記載の秘密情報分散システムにおいて、前記記憶装置は、当該各記憶装置に格納されている情報を前記復元装置に送信するタイミングを制御するアクセス制御手段を更に備え、前記復元装置は、前記記憶装置から読み出す情報の順序を制御する読み出し制御手段を更に備え、前記復元装置は前記読み出し制御装置の指定する順序に従い、秘密の復元に参加する前記k個以上の記憶装置の全てから、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する前記k個以上の記憶装置の全てから、チェック用データ記憶装置を読み出すことを特徴とする秘密情報分散システム。分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、前記分散情報生成装置が、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力し、前記n個の記憶装置が前記分散情報生成装置の出力を記憶し、前記復元装置が、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから前記分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする秘密情報分散方法。分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラム。分散情報生成装置と、n個nは2以上の自然数の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラム。上述したような技術を用いることによって、秘密復元時に入力される分散情報のうち改竄されていない時点での分散情報を参照せずに分散情報を改竄する不正に対しては、安全性が保証される。しかしながら、秘密復元に入力される改竄されていない時点での部分情報を参照した後で分散情報を改竄する、より強力な不正に対して安全な秘密分散法は従来一つも提案されていない。本発明はこのような状況に鑑みてなされたものであり、本発明は、改竄されていない時点での他の分散情報を参照した後で分散情報を改竄する強力な不正に対しても不正の検知を行うことが可能な、秘密情報分散システム及び秘密情報分散方法並びに秘密情報生成プログラム及び秘密情報復元プログラムを提供することを目的とする。本発明の第1の観点によれば、分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、前記分散情報生成装置は、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力し、前記n個の記憶装置は前記分散情報生成装置の出力を記憶し、前記復元装置は、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから前記分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする秘密情報分散システムが提供される。本発明の第2の観点によれば、分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、前記分散情報生成装置が、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力し、前記n個の記憶装置が前記分散情報生成装置の出力を記憶し、前記復元装置が、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから前記分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする秘密情報分散方法が提供される。本発明の第3の観点によれば、分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラムが提供される。本発明の第4の観点によれば、分散情報生成装置と、n個nは2以上の自然数の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラムが提供される。本発明によれば、正当な記憶装置に格納されているチェック用データeは、独立かつ一様ランダムに選ばれており、且つ、非改竄性のチェックに用いる関数hは、知り得た値以外の関数値をεより高い確率で類推することができないという性質を有していることから、改竄されていない時点での他の分散情報を参照した後で分散情報を改竄する強力な不正に対しても不正の検知を行うことが可能となる。次に、本発明の実施形態について図面を用いて詳細に説明する。なお、以下に述べる実施の形態は、本発明の好適な実施の形態として、技術的に好ましい種々の限定が付されている。しかし、だからといって、本発明の範囲は、以下の説明において特に本発明を限定する旨の記載がない限り、これらの態様に限られるものではない。すなわち、下述する実施形態は、本発明の好適な実施形態ではあるが、これらの実施形態のみに本発明の範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した形態での実施が可能である。本実施形態を説明するにあたり、まず本明細書で使用する用語について簡単に説明する。k,n閾値法:秘密情報をn個の分散情報に分散符号化し、そのうちの任意のk個の分散情報により、もとの秘密情報の復元が可能となる性質を有する秘密分散法を指す。なお、非特許文献1にk,n閾値法に関する記載がある。秘密情報s:保管対象となる秘密情報を指す。秘密情報データ集合S:保管対象となる秘密情報sの集合を指す。認証データa:認証に用いる認証データを指す。認証データ集合A:認証データaの集合であり、チェック関数hの値域を指す。Aの要素であるaをa[i]と記述した場合は、当該aが第i番目の認証データであることを表すものとする。分散情報データv:秘密情報s∈Sを分散符号化したデータ分散情報のうちの1つを指す。分散情報データV:秘密情報s∈Sを分散符号化したデータ分散情報の集合を指す。Vの要素であるvをv[i]と記述した場合は、当該vが第i番目の分散情報を表すものとする。チェック用データe:分散情報の非改竄性チェックに用いられるデータを指す。チェック用データ集合E:分散情報の非改竄性チェックに用いられるデータ集合である。Eの要素であるeをe[i]と記述した場合は、当該eは第i番目のチェック用データを表すものとする。演算子:本明細書において、それぞれ、の記号を和、-の記号を差、の記号を積、^の記号を冪乗、の演算子として用いる。[実施形態1]図1は、本発明の実施形態に係る秘密情報分散システム全体の基本的構成を表す図である。図1を参照すると、秘密情報分散システムは、分散情報生成装置100、復元装置200及び複数の記憶装置300-1~300-nを有する。分散情報生成装置100は、秘密情報s1を受け付け、受け付けた秘密情報s1に基づいて分散情報を生成する装置である。また、複数の記憶装置300-1~300-nは、分散情報生成装置100が生成した分散情報を記憶する装置である。更に、復元装置200は、記憶装置300-1~300-nが記憶する分散情報に基づいて復元を行う装置である。なお、図示の都合上、記憶装置300-1、300-2及び300-nの3つが図示されているが、これはあくまで一例であり、任意の台数の記憶装置300が存在していてよい。本発明の実施形態に係る秘密情報分散システムが秘密情報を保管する場合には、分散情報生成装置100が分散情報の非改竄性チェックに用いるチェック用データをランダムに生成し、k,n閾値法で生成した分散情報、チェック用データ、分散情報とチェック用データを用いて生成した認証データを記憶装置300に格納する。また、秘密情報を復元する場合には、k個以上の記憶装置300から分散符号化された秘密情報及びチェック用データ、認証データを復元装置200の指定する順序に従って読み出す。そして、各記憶装置内に格納されている分散情報とチェック用データが認証データと正しく対応しているかを判定し、全ての記憶装置300に関して、正しく対応していることが検証できた場合は、復元した秘密情報が正しいと判断し秘密を出力し、対応していない場合は分散情報が改竄されていると判断する対応していない分散情報の識別子リストを出力する。次に、図2を参照して分散情報生成装置100の構成について詳細に説明する。図2は分散情報生成装置100の構成を表すブロック図である。図2に示すように、分散情報生成装置100は、秘密情報分散部101、チェック用データ生成部102及び認証データ生成部103を有している。秘密情報分散部101は、秘密情報s1を入力とし、秘密情報s1をk,n閾値法で分散符号化したn個のデータv[1],v[2],...,v[n]v[i]∈Vを記憶装置300及び認証データ生成部103に対して出力する。チェック用データ生成部102は、チェック用データe[i]∈Ei=1,...,nを生成する。また、チェック用データ生成部102は、生成したチェック用データe[i]∈Ei=1,...,nを記憶装置300及び認証データ生成部103に対して出力する。認証データ生成部103は、秘密情報分散部101の出力v[i],...,v[n]と、チェック用データ生成部102の出力e[1],...,e[n]とを入力として、認証情報a[i]=a[i,1],a[i,2],...,a[i,i-1],a[i,i1],...,a[i,n]i=1,...,nであり、a[i,j]=he[i],v[j]を出力する。本実施形態では、チェック関数hh:E×V→Aは、集合Vの任意の要素v[1],v[2],...,v[k-2],v,v’と、集合Aの任意の要素a[1],a[2],...,a[k-2],a’に対して、|{e[j]|he[j],v=a,he[j],v’=a’,he[j],v[l]=a[l]l=1,2,...,k-2}|/|{e[j]|he[j],v=a,he[j],v[l]=a[l]}|≦εを任意のi,j,lについて満足するものとする。以上をまとめると、分散情報生成装置100は秘密情報データ集合Sの元となるすなわち集合Sの要素である秘密情報s1を入力とし、記憶装置300-1~300-n内の分散秘密情報記憶部301-1~301-nに秘密情報分散部101の出力であるVの元v[1]~v[n]を、チェック用データ記憶部302-1~302-nにチェック用データ生成部102の出力であるEの元e[1]~e[n]を、チェック用データ記憶部303-1~303-nに認証データ集合Aの元である認証データa[1]~a[n]をそれぞれ格納する。次に、図2を参照して記憶装置300-1~300-nの構成について詳細に説明する。記憶装置300-1~300-nは、分散秘密情報記憶部301-1~301-n、チェック用データ記憶部302-1~302-n、認証データ記憶部303-1~303-n及びアクセス制御部304-1~304-nを含んでいる。分散秘密情報記憶部301-1~301-nは、分散情報データ集合Vの元となる分散データvが格納される記憶部である。チェック用データ記憶部302-1~302-nは、チェック用データ集合Eの元となるチェック用データeが格納される記憶部である。認証データ記憶部303-1~303-nは、認証データ集合Aの元となる認証データaが格納される記憶部である。アクセス制御部304-1~304-nは、復元装置200内の読み出し制御部203からの信号に基づき、復元装置200から読み出せるデータを制御する。続いて、復元装置200の構成について図3を用いて説明する。図3は復元装置200の構成を表すブロック図である。図3に示すように、復元装置200は、秘密情報復元部201、不正情報特定部202及び読み出し制御部203を含んでいる。秘密情報復元部201は複数の記憶装置300が有する分散秘密情報記憶部301に格納されたデータを不正情報特定部202から読み出し、復元した秘密情報データs∈Sを出力する。不正情報特定部202は、k個以上の記憶装置300が備える分散秘密情報記憶部301に格納された分散情報v[i-1],...,v[i-m]と、チェック用データ記憶部302に格納されたチェック用データe[i-1],...,e[i-m]と、認証データ記憶部303に格納された認証データa[i-1],...,e[i-m]但し、各a[i]=a[i,1],a[i,2],...,a[i,i-1],a[i,i1],...,a[i,n]を読み出す。そして、全てのi=i-1,...,i-mと、iと相異なる全てのj=i-1,...,i-mの内、k/2個以上のjに対し、he[i],v[j]=a[i,j]が成立するかどうかを判定する。そして、この判定の結果、全てのjについて上式が成立するiの個数が2/k以上である場合は、分散情報に改竄がないものと判定し、v[i-1],...,v[i-m]を秘密情報復元部201に入力して得られる、復元された秘密情報s∈Sを出力する。一方、上式が成立するiの個数が2/k未満となるjが存在する場合は、he[i],v[j]=a[i,j]が成立する個数がk/2未満であったjのリストを改竄が生じた分散情報の識別子として出力する。読み出し制御部203は、記憶装置300-1~300-n内のアクセス制御部304-1~304-nに対して読み出したいデータを伝える制御信号を出力する。アクセス制御部304-1~304-nは前記制御信号に基づき、復元装置200にデータ読み出しの許可を与える。以上説明した、図1、図2及び図3に表された分散情報生成装置100及び復元装置200は、任意の方法により実現することが可能である。例えばハードウェアとして分散情報生成装置100及び復元装置200を実現するのであれば、論理回路等から構成されるLSILargeScaleIntegrationやDSPDigitalSignalProcessor等の半導体集積回路によって実現できる。また、分散情報生成装置100及び復元装置200は、ハードウェア及びソフトウェアの組合せとしても実現可能である。例えば、図4に示すように、プログラムにしたがって所定の処理を実行する処理装置10と、処理装置10に対してコマンドや情報等を入力するための入力部20と、処理装置10の処理結果をモニタするための出力部30とを含んだコンピュータによって分散情報生成装置100及び復元装置200を実現してもよい。この点について、以下詳細に説明する。図4を参照すると処理装置10は、CPU11と、主記憶部12と、記録媒体13と、データ蓄積部14と、メモリ制御インタフェース部15と、I/Oインタフェース部16とを有する。これら各構成要素は、バス18を介して相互に接続されている。CPU11はプログラムに基づいて演算を行う演算処理装置である。主記憶部12は、CPU11の演算処理に必要な情報を一時的に記憶する主記憶部である。記録媒体13は、CPU11に分散情報生成装置100または復元装置200としての処理を実行させるためのプログラムが記録された記録媒体である。処理装置10は、記録媒体13に記録されたプログラムに従って分散情報生成装置100または復元装置200としての機能を実現する。データ蓄積部14は、秘密情報やアクセス構造データが格納される補助記憶装置である。なお、記録媒体13及びデータ蓄積部14は、任意の装置により実現可能である。記録媒体13及びデータ蓄積部14は、例えば、HDDHarddiskdriveやFlashSSDSolidStateDriveにより実現される。また、この記憶装置は処理装置10内にある必要はなく、外部の記憶装置図示を省略するを利用するようにしてもよい。この場合記憶装置を別のコンピュータとして実現し、バスやUSB規格に準拠したケーブルや、インターネット等の手段を用いて接続するようにしてもよい。更に、単一の記憶装置により実現されてもよいが、複数の記憶装置の組合せにより実現されていてもよい。加えて、記録媒体13は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。例えば、フレキシブルディスク、CD-ROMCompactDiscReadOnlyMemory、DVDDigitalVersatileDisc、MOMagnetoOpticalDiskBDBlurayDisc等であってもよい。加えて、データ蓄積部14は、分散秘密情報記憶部301及びチェック用データ記憶部302及び認証用データ記憶部303を備える記憶装置300として用いてもよい。すなわち、散情報生成装置100、復元装置200及び記憶装置300は、複数のコンピュータで実現してもよく、単一のコンピュータで実現してもよい。メモリ制御インタフェース部15は、主記憶部12、記録媒体13及びデータ蓄積部14とCPU11等とのデータ転送を制御する。次に本実施形態の秘密情報分散システムの動作について図5及び図6を参照して説明する。図5は分散情報生成装置100の動作を示すフローチャートであり、図6は復元装置200の動作を示すフローチャートである。まず、分散情報生成部100の秘密情報分散部101には、秘密情報データ集合Sの元である秘密情報s1が入力されるステップA401。分散情報生成装置100は、秘密情報分散部101に秘密情報s1が入力されると、秘密情報分散部101により秘密情報s1をk,n閾値法により分散符号化し、生成されたv[i]i=1,...,nを記憶装置300-iの分散秘密情報記憶部301-i及び認証データ生成部103に格納するステップA402。また、分散情報生成装置100は、チェック用データ生成部102により、チェック用データe[i]i=1,...,nを生成し、生成したe[i]を、記憶装置300-iのチェック用データ記憶部302-i及び認証データ生成部103に格納するステップA403。分散情報生成装置100は、認証データ生成部103により、分散情報v[i]i=1,...,nと、チェック用データe[j]j=1,...,n,j≠iに対して、a[i,j]=he[i],v[j]を計算し、認証データa[i]=a[i,1],...,a[i,i-1],a[i,i1],...,a[i,n]i=1,...,nを、記憶装置300-iの認証データ記憶部303-iに格納するステップA404。図5に示すように、復元装置200は、記憶装置300のアクセス制御部304に分散秘密情報記憶部301、認証データ記憶部303のデータを読み出すことを示す制御信号を送り、k個以上の記憶装置300の分散秘密情報記憶部301と認証データ記憶部303から読み出した分散データv[i]i=i-1,i-2,...,i-m,認証情報a[i]i=i-1,i-2,...,i-mを不正情報特定部202に入力するステップT501。ステップT501でのデータ読み込み終了後、復元装置200は、ステップT501で読み出した記憶装置300と同じ記憶装置300のアクセス制御部304に対してチェック用データ記憶部302のデータを読み出すことを示す制御信号を送り、当該記憶装置300のチェック用データ記憶部302から読み出したチェック用データe[i]i=i-1,i-2,...,i-mを不正情報特定部202に入力するステップT502。すなわちステップT501及びT502では同一であってk個以上の記憶装置300から分散データv[i]、認証情報a[i]及びチェック用データe[i]を読み込むこととなる。ステップT501とステップT502でのデータ読み込み後、復元装置200は、ステップT501,T502で読み込んだv[i],e[i],a[i]=a[i,1],...,a[i,i-1],a[i,i1],...,a[i,n]i=i-1,i-2,...,i-mとj≠iなるjj=i-1,i-2,...,i-mに対し、he[i],v[j]=a[i,j]が成立するか否かを不正情報特定部202によりチェックするステップT503。ステップT503のチェックにより、全てのjに対して、he[i],v[j]=a[i,j]が成立するiの個数が2/k以上である場合は、秘密情報復元部201に読み込んだ全てのv[i]を秘密情報復元部201に入力して得られる復元された秘密情報s1を出力して終了ステップT504においてYes、ステップT505。一方、he[i],v[j]=a[i,j]が成立するiの個数が2/k未満となるjが存在する場合、he[i],v[j]=a[i,j]が成立するiの個数が2/k未満となるjのリストを改竄された分散情報の識別子として出力して終了するステップT504においてNo、ステップT506。上記実施形態によれば、不正な記憶装置300は、正当な記憶装置300のチェック用データを読み出した後に改竄の検出が行えないように分散情報記憶部301のデータを改竄することは不可能になり、正当な記憶装置300の送出する情報を参照した後に成功するようなデータを計算することができなくなるという効果を奏する。[実施形態2]次に、本発明の第2の実施形態について図面を参照して詳細に説明する。実施形態2に係る秘密情報分散システムの基本的構成は図1、図2及び図3に表される実施形態1と同様であるため、その説明を省略する。一方、実施形態2ではチェック用データ生成部102が、チェック用データe∈Eを生成する。そして、eをt,n閾値法で分散符号化する点において実施形態1と異なる。また、これに伴い復元装置200での動作も異なる。よって、この点を中心として説明をする。そして、特に言及しない点においては実施形態1と同様であるとする。まず、分散情報生成装置100について説明する。秘密情報分散部101は、秘密情報s1を入力とし、秘密情報s1をk,n閾値法で分散符号化したn個のデータv[1],v[2],...,v[n]v[i]∈Vを記憶装置300及び認証データ生成部103に対して出力する。本実施形態における、チェック用データ生成部102は、チェック用データe[i]∈Ei=1,...,nを生成する。また、チェック用データ生成部102は、生成したチェック用データe[i]∈Ei=1,...,nを記憶装置300に対して出力する。認証データ生成部は103、秘密情報分散部101の出力v[i],...,v[n]と、チェック用データe、認証情報a[i]=he,v[j]を出力する。本実施形態では、チェック関数hh:E×V→Aは、集合Vの任意の要素v[1],v[2],...,v[t-1],v,v’と、集合Aの任意の要素a[1],a[2],...,a[t-1],a’に対して、|{e|he,v=a,he,v’=a’,he,v[l]=a[l]l=t-1}|/|{e|he,v=a,he,v[l]=a[l]}|≦εを任意のi,j,lについて満足するものとする。以上をまとめると、分散情報生成装置100は秘密情報データ集合Sの元となるすなわち集合Sの要素である秘密情報s1を入力とし、記憶装置300-1~300-n内の分散秘密情報記憶部301-1~301-nに秘密情報分散部の出力であるVの元v[1]~v[n]を、チェック用データ記憶部302-1~302-nにチェック用データ生成部102の出力e[1]~e[n]を、チェック用データ記憶部303-1~303-nに認証データ集合Aの元である認証データa[1]~a[n]をそれぞれ格納する。また、本実施形態の記憶装置300-1~300-nは、分散情報データ集合Vの元が格納される分散情報記憶部301-1~301-nと、チェック用データ集合Eの元が格納されるチェック用データ記憶部302-1~302-nと、認証データ集合Aの元が格納される認証データ記憶部303-1~303-nと、復元装置200内の読み出し制御部からの信号に基づき、復元装置200から読み出せるデータを制御するアクセス制御部304-1~304-nとを含んでいる。次に、本実施形態の復元装置200の構成について説明する。図3は復元装置200の構成ブロック図である。図3に示すように、復元装置200は、秘密情報復元部201、不正情報特定部202、及び読み出し制御部203を備えている。秘密情報復元部201は複数の記憶装置300が備える分散秘密情報記憶部301に格納されたデータ不正情報特定部202からを読み出し、復元した秘密情報データs∈Sを出力する。不正情報特定部202は、k個以上の記憶装置300が備える分散秘密情報記憶部301に格納された分散情報v[i-1],...,v[i-m]と、チェック用データ記憶部302に格納されたチェック用データe[i-1],...,e[i-m]と、認証データ記憶部303に格納された認証データa[i-1],...,a[i-m]を読み出す。そして、e[i-1],...,e[i-m]からeの復元を行った後、全てのi=i-1,...,i-mに対し、he,v[i]=a[i]が成立するかどうかを判定する。そして、この判定の結果、全てのiについて上式が成立する時は分散情報に改竄がないものと判定し、v[i-1],...,v[i-m]を秘密情報復元部201に入力して得られる、復元した秘密情報s∈Sを出力する。一方、上式が成立しない時はhe,v[i]=a[i]が成立しないiのリストを改竄が生じた分散情報の識別子として出力する。このとき、eはt,n閾値秘密分散の分散情報であるためm≧kとなるm個のe[i-1],...,e[i-m]からt個の改竄されたe[i-j]の誤りを訂正し、正しいeが復元できることが知られている。読み出し制御部203は、記憶装置300-1~300-n内のアクセス制御部304-1~304-nに対して読み出したいデータを伝える制御信号を出力する。アクセス制御部304-1~304-nは前記制御信号に基づき、復元装置200にデータ読み出しの許可を与える。なお、本実施形態は実施形態1と同様、分散情報生成装置100及び復元装置200を半導体集積回路によって実現できる。また、本実施形態は実施形態1と同様、分散情報生成装置100及び復元装置200を図4に表されるような処理装置10により実現できる。なお具体的な実現方法は、実施形態1の説明において上述した内容と同様である。次に本実施形態の秘密情報分散システムの動作について図7及び図8を参照して説明する。図7は分散情報生成装置100の動作を示すフローチャートであり、図8は復元装置200の動作を示すフローチャートである。まず、分散情報生成部100の秘密情報分散部101には、秘密情報データ集合Sの元である秘密情報s1が入力されるステップU601。分散情報生成装置100は、秘密情報分散部101に秘密情報s1が入力されると、秘密情報分散部101により秘密情報s1をk,n閾値法により分散符号化し、生成されたv[i]i=1,...,nを記憶装置300-iの分散秘密情報記憶部301-i及び認証データ生成部103に格納するステップU602。また、分散情報生成装置100は、チェック用データ生成部102により、チェック用データeを生成し、eをt,n閾値法で分散符号化したe[i]i=1,...,nを生成し、生成したe[i]を、記憶装置300-iのチェック用データ記憶部302-iに格納するステップU603。分散情報生成装置100は、認証データ生成部103により、分散情報v[i]i=1,...,nと、チェック用データ生成部102が生成したチェック用データeに対して、a[i]=he,v[i]を計算し、認証データa[i]i=1,...,nを、記憶装置300-iの認証データ記憶部303-iに格納するステップU604。図7に示すように、復元装置200は、記憶装置300のアクセス制御部304に分散秘密情報記憶部301、認証データ記憶部303のデータを読み出すことを示す制御信号を送り、k個以上の記憶装置300の分散秘密情報記憶部301と認証データ記憶部303から読み出した分散データv[i],認証情報a[i]i=i-1,i-2,...,i-mを不正情報特定部202に入力するステップW701。ステップW701でのデータ読み込み終了後、復元装置200は、ステップW701で読み出した記憶装置300と同じ記憶装置300のアクセス制御部304に対してチェック用データ記憶部302のデータを読み出すことを示す制御信号を送り、当該記憶装置300のチェック用データ記憶部302から読み出したチェック用データe[i]i=i-1,i-2,...,i-mを不正情報特定部202に入力するステップW702。すなわちステップW701及びW702では同一であってk個以上の記憶装置300から分散データv[i]、認証情報a[i]及びチェック用データe[i]を読み込むこととなる。ステップW701とステップW702でのデータ読み込み後、復元装置200は、ステップW701,W702で読み込んだv[i],e[i],a[i]から、eの復元を行い、i=i-1,i-2,...,i-mに対し、he,v[i]=a[i]が成立するか否かを不正情報特定部202によりチェックするステップW703。ステップW703のチェックにより、he,v[i]=a[i]が成立する場合は、秘密情報復元部201に読み込んだ全てのv[i]を秘密情報復元部201に入力して得られる復元された秘密情報s1を出力して終了するステップW704においてYes、ステップW705。一方、he,v[i]=a[i]が成立しないiが存在する場合、he,v[i]=a[i]が成立しないiのリストを改竄された分散情報の識別子として出力して終了するステップW704においてNo、ステップW706。上記実施形態によれば、不正な記憶装置300は、正当な記憶装置300のチェック用データを読み出した後に改竄の検出が行えないように分散情報記憶部301のデータを改竄することは不可能になり、正当な記憶装置300の送出する情報を参照した後に成功するようなデータを計算することができなくなるという効果を奏する。次に、上述した各実施形態をより具体的に説明した例である、本発明の実施例について説明する。実施例1は、上述した実施形態1に対応する実施例である。本実施例におけるに秘密情報分散システムは、秘密情報sのデータ集合にGFpp:素数冪,GF:ガロア体を、チェック用データe[i]=e[i,1],...,e[i,i-1],e[i,i1],e[i,n]但し、e[i,j]=e[i,j]{0},e[i,j]{1},e[i,j]{b}はGFpの元として、認証用データとしてa[i]=a[i,1],...,a[i,i-1],a[i,i1],...,a[i,n]を用いる。次に本実施例に係る分散情報生成装置100及び復元装置200について説明する。本実施例に係る分散情報生成装置100には、秘密情報s∈GFpが入力される。分散情報生成装置100は、秘密情報sが入力されると、秘密情報分散部101によりGFp上の定数項がsであるk-1次多項式をランダムに生成する。このk-1次多項式をf-sxと記す。秘密情報分散部101は、相異なる1,2,...,nに対して、v[1]=f-s1,v[2]=f-s2,...,v[n]=f-snを計算し、その計算結果を記憶装置300-1の分散秘密情報記憶部301-1、記憶装置300-2の分散秘密情報記憶部301-2,...,記憶装置300-nの分散秘密情報記憶部301-nにそれぞれ格納する。チェック用データ生成部102は、GFpの元であるe[i,j]{b}i=1,...,n,j=1,...,n,b=0,1,j≠iをランダムに生成し、e[i]i=1,...,nを記憶装置300-iのチェック用データ記憶部302-iに格納する。次に、認証データ生成部103は、a[i,j]=e[i,j]{1}×v[j]e[i,j]{0}を計算し、a[i]=a[i,1],...,a[i,i-1],a[i,i1],...,a[i,n]i=1,...,nを記憶装置300-iの認証データ記憶部303-iにそれぞれ格納する。一方、本実施例に係る復元装置200は、まず、分散情報と認証データの読み出しを行う制御信号を読み出し制御部203から記憶装置300-[i-1],300-[i-2],...,300-[i-m]の各アクセス制御部304に送出し、記憶装置300-[i-1],300-[i-2],...,300-[i-m]の各分散秘密情報記憶部301と各認証データ記憶部303とからデータv[i],a[i]i=i-1,...,i-mを読み出す。次に、復元装置200は、乱数分散情報の読み出しを行う制御信号を読み出し制御部203から記憶装置300-[i-1],300-[i-2],...,300-[i-k]の各アクセス制御部304に送出し、記憶装置300-[i-1],300-[i-2],...,300-[i-k]の各チェック用データ記憶部302からデータe[i]を読み出す。不正情報特定部202は、v[i],e[i],a[i]i=i-1,...,i-mを入力とし、全てのi=i-1,...,i-mと、iとは相異なるj=i-1,...,i-mについてa[i,j]=e[i,j]{1}×v[j]e[i,j]{0}が成立するか否かをチェックし、全てのiについて上式が成立するjの個数が2/k以上であった場合は、v[i-1],...,v[i-m]からラグランジュ補完などの手段によって秘密情報sを計算して出力する。一方、成立していない場合は上式が成立するjが2/k未満となったjのリストを改竄された分散情報の識別子として出力する。本実施例に係る秘密情報分散システムでは、k/2未満の改竄された分散情報を確率1-1/pで特定することができるという効果を奏する。実施例2は、上述した実施形態2に対応する実施例である。本実施例におけるに秘密情報分散システムは、秘密情報sのデータ集合にGFpp:素数冪,GF:ガロア体を、チェック用データe=e{0},e{1},...,e{t}としてGFq^t1の元但し、qはp×n以上の素数、認証用データとしてGFqの元a[i]を用いる。次に本実施例に係る分散情報生成装置100及び復元装置200について説明する。本実施例に係る分散情報生成装置100には、秘密情報s∈GFpが入力される。分散情報生成装置100は、秘密情報sが入力されると、秘密情報分散部101によりGFp上の定数項がsであるk-1次多項式をランダムに生成する。このk-1次多項式をf-sxと記す。秘密情報分散部101は、相異なる1,2,...,nに対して、v[1]=f-s1,v[2]=f-s2,...,v[n]=f-snを計算し、その計算結果を記憶装置300-1の分散秘密情報記憶部301-1、記憶装置300-2の分散秘密情報記憶部301-2,...,記憶装置300-nの分散秘密情報記憶部301-nにそれぞれ格納する。チェック用データ生成部102は、GFqの元であるeをランダムに生成し、f-e0=eとなるt次多項式f-exをランダムに生成、e[i]=f-eii=1,...,nを記憶装置300-iのチェック用データ記憶部302-iに格納する。次に、認証データ生成部103は、a[i]=e{0}e{1}×ψv[i]e{2}×ψv[i]^2...e{t}×ψv[j]^tを計算し、記憶装置300-iの認証データ記憶部303-iにそれぞれ格納する。但し、ψv[i]はψv[i]=pi-1v[i]で定義される関数一方、本実施例に係る復元装置200は、まず、分散情報と認証データの読み出しを行う制御信号を読み出し制御部203から記憶装置300-[i-1],300-[i-2],...,300-[i-m]の各アクセス制御部304に送出し、記憶装置300-[i-1],300-[i-2],...,300-[i-m]の各分散秘密情報記憶部301と各認証データ記憶部303とからデータv[i],a[i]i=i-1,...,i-mを読み出す。次に、復元装置200は、乱数分散情報の読み出しを行う制御信号を読み出し制御部203から記憶装置300-[i-1],300-[i-2],...,300-[i-k]の各アクセス制御部304に送出し、記憶装置300-[i-1],300-[i-2],...,300-[i-k]の各チェック用データ記憶部302からデータe[i]を読み出す。不正情報特定部202は、v[i],e[i],a[i]i=i-1,...,i-mを入力とし、e[i-1],e[i-2],...,e[i-m]からバーレカンプマッシー法BerlekampMasseyalgorithmやユークリッド法Euclideanalgorithmなどの誤り訂正符号の復号法を利用して正しいeを復元する。そして、a[i]=e{0}e{1}×ψv[i]e{2}×ψv[i]^2...e{t}×ψv[j]^tが成立するか否かをチェックし、全てのiについて上式が成立する場合は、v[i-1],...,v[i-m]からラグランジュ補完などの手段によって秘密情報sを計算して出力し、成立しないiが存在する場合には、そのiのリストを改竄された分散情報の識別子として出力する。本実施例に係る秘密情報分散システムでは、k/2未満の改竄された分散情報を確率1-1/pで特定することができる。以上、本発明を好適な実施形態及び好適な実施例に基づき具体的に説明したが、本発明は上記のものに限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。以上説明した本発明の実施形態は、以下に示すような効果を奏する。本発明の実施形態によれば、部分情報の改竄を行う記憶装置は、プロトコルに従ってまず最初に改竄した分散情報と認証データを復元装置に渡す必要がある。このとき、部分情報の改竄を行う記憶装置は、改竄を行っていない正当な記憶装置に格納されているチェック用データの値を参照することができない。正当な記憶装置に格納されているチェック用データeは、独立かつ一様ランダムに選ばれており、また、非改竄性のチェックに用いる関数hは、知り得た値以外の関数値をεより高い確率で類推することができないという性質を有している。従って、仮に改竄を行う記憶装置が記憶装置に格納されている複数の分散情報と認証データを参照し、不正情報特定装置に特定されない形で改竄を行った場合でも、不正情報特定装置が偽造を特定できない確率はε以下となることが保証されるという効果を奏する。上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。上記目的を達成するため本発明の分散情報生成装置は、秘密情報を入力とし、前記秘密情報をk,n閾値法で分散符号化した分散情報を出力する秘密情報分散装置と、前記秘密情報の検証を行うチェック用データを生成するチェック用データ生成装置と、前記分散情報と、チェック用データとを入力とし、予め定められたチェック関数hに入力して得られる出力から認証データを生成する認証データ生成装置とを有する。また、本発明の復元装置は、k個以上の前記記憶装置から分散符号化された分散秘密情報を読み出し、秘密情報の復元を行う秘密情報復元装置と、k個以上の前記記憶装置から分散情報と、チェック用データと、認証データとを読み出し、分散情報の正当性チェックを行い、改竄された分散情報が存在する場合には、改竄された分散秘密情報の識別子リストを出力し、改竄された分散情報が存在しない場合には、復元された秘密情報を出力する不正情報特定装置と、前記記憶装置から読み出す情報の順序を制御する読み出し制御装置を有する。上記のような構成を採り、読み出し制御装置の指定する順序に従い、秘密の復元に参加する全ての記憶装置から、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する全ての記憶装置から、チェック用データ記憶装置を読み出すこととする。また、関数hを、複数の関数値he,vが分かった場合でも、同じチェックデータeに対する知り得た値以外のv’に関する関数値he,v’の値を低い確率εでしか類推できない特徴を有するものの中から選択する。付記1分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、前記分散情報生成装置は、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力し、前記n個の記憶装置は前記分散情報生成装置の出力を記憶し、前記復元装置は、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから前記分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする秘密情報分散システム。付記2付記1に記載の秘密情報分散システムであって、前記分散情報生成装置は、秘密情報をk,n閾値秘密分散法で分散符号化し、n個の分散情報v[1],v[2],...,v[n]を生成する秘密情報分散手段と、前記秘密情報の検証を行うn個のチェック用データe[1],e[2],...,e[n]を生成するチェック用データ生成手段と、前記分散情報v[1],...,v[n]と、チェック用データe[1],...,e[n]とを入力とし、予め定められたチェック関数hに入力して得られる出力a[i,j]=he[i],v[j]i≠jからn個の認証データa[i]=a[i,1],a[i,2],...,a[i,i-1],a[i,i1],...,a[i,n]i=1,...,nを出力する認証データ生成手段とを備え、前記記憶装置は、前記分散情報生成装置が生成した分散符号化された前記分散情報v[i]を格納する分散秘密情報記憶手段と、前記チェック用データ生成装置が生成した前記チェック用データe[i]を格納するチェック用データ記憶手段と、前記認証データ生成装置が生成した前記認証データa[i]を格納する認証データ記憶手段とを備え、前記復元装置は、k個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、k個以上の前記記憶装置から分散情報v[i-1],v[i-2],...,v[i-m]と、チェック用データe[i-1],e[i-2],...,e[i-m]と、認証データa[i-1],a[i-2],...,a[i-m]とを読み出し、全ての可能な相異なるi,ji,j=i-1,...,i-mに対して、he[i],v[j]=a[i,j]なる式が成立するか否かを判定し、当該判定の結果、k/2個以上のe[i]に対して前記式が成立しなかったv[j]が存在する場合は、k/2個以上のe[i]に対して前記式が成立しなかったv[j]の識別子集合{i-j1,i-j2,...,i-jw}を出力し、当該判定の結果、k/2個以上のe[i]に対して前記式が成立しなかったv[j]がそのようなv[j]が存在しない場合は、復元した秘密情報sを出力する不正情報特定手段とを備え、前記チェック関数hh:E×V→Aは、集合Vの任意の要素v[1],v[2],...,v[t-1],v,v’t≧k/2と、集合Aの任意の要素a[1],a[2],...,a[k-2],a’に対して、|{e[j]|he[j],v=a,he[j],v’=a’,he[j],v[l]=a[l]l=1,2,...,t-1}|/|{e[j]|he[j],v=a,he[j],v[l]=a[l]}l=1,2,...,t-1|≦εを任意のi,j,lについて満足することを特徴とする秘密情報分散システム。付記3付記1又は2に記載の秘密情報分散システムにおいて、チェック関数hが、n個の部分情報v[1],...,v[n]と、チェック用データe[i]=e[i,1],e[i,2],...,e[i,i-1],e[i,i1],e[i,i2],...,e[i,n]i=1,...,n、但し、各e[i,j]=e[i,j]{0},e[i,j]{1}i=1,...,nとに対し、he[i],v[j]=e[i,j]{1}×v[j]e[i,j]{0}によって定義されることを特徴とする秘密情報分散システム。付記4付記1に記載の秘密情報分散システムにおいて、前記分散情報生成装置は、前記チェック用データeをt,n閾値秘密分散法で分散符号化したn個のチェック用データeを前記記憶装置に出力し、前記復元装置は、前記t,n閾値秘密分散法で分散符号化されたチェック用データeを更に用いて前記分散情報の正当性の判定を行うことを特徴とする秘密情報分散システム。付記5付記4に記載の秘密情報分散システムにおいて、前記分散情報生成装置は、秘密情報をk,n閾値秘密分散法で分散符号化し、n個の分散情報v[1],v[2],...,v[n]を生成する秘密情報分散手段と、前記秘密情報の検証を行うチェック用データeをt,n閾値秘密分散法で分散符号化したn個のチェック用データe[1],e[2],...,e[n]を生成するチェック用データ生成手段と、前記分散情報v[1],...,v[n]と、チェック用データeとを入力とし、予め定められたチェック関数hに入力して得られる出力a[i]=he,v[i]i=1,...,nを認証データとして出力する認証データ生成手段とを備え、前記記憶装置は、前記分散情報生成装置が生成した分散符号化された前記分散情報v[i]を格納する分散秘密情報記憶手段と、前記チェック用データ生成装置が生成した前記チェック用データe[i]を格納するチェック用データ記憶手段と、前記認証データ生成装置が生成した前記認証データa[i]を格納する認証データ記憶手段とを備え、前記復元装置は、k個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、k個以上の前記記憶装置から分散情報v[i-1],v[i-2],...,v[i-m]と、分散符号化されたチェック用データe[i-1],e[i-2],...,e[i-m]と、認証データa[i-1],a[i-2],...,a[i-m]とを読み出し、e[i-1],...,e[i-m]からチェック用データeを復元し、全てのii=i-1,...,i-mに対して、he,v[i]=a[i]i=1,2,...,mなる式が成立するか否かをチェックし、前記式が成立しなかったv[i]の識別子集合{i-j1,i-j2,...,i-jw}を出力し、そのようなv[i]が存在しない場合は、復元した秘密情報sを出力する不正情報特定手段とを備え、前記チェック関数hh:E×V→Aは、集合Vの任意の要素v[1],v[2],...,v[t-1],v,v’と、集合Aの任意の要素a[1],a[2],...,a[t-1],a’に対して、|{e|he,v=a,he,v’=a’,he,v[i]=a[i]i=1,2,...,t-1}|/|{e|he,v=a,he,v[i]=a[i]i=1,2,...,t-1}|≦εを任意のiについて満足することを特徴とする秘密情報分散システム。付記6付記4又は5に記載の秘密情報分散システムにおいて、チェック関数hが、n個の部分情報v[1],...,v[n]と、チェック用データe=e{0},e{1},...,e{t}と、p≧nとなる任意の素数と、関数ψv[i]=p×i-1v[i]とに対し、he[i],v[j]=e{0}e{1}×ψv[i]e{3}×ψv[i]^2...e{t}×ψv[i]^tによって定義されることを特徴とする秘密情報分散システム。付記7付記1乃至6の何れか1に記載の秘密情報分散システムにおいて、前記記憶装置は、当該各記憶装置に格納されている情報を前記復元装置に送信するタイミングを制御するアクセス制御手段を更に備え、前記復元装置は、前記記憶装置から読み出す情報の順序を制御する読み出し制御手段を更に備え、前記復元装置は前記読み出し制御装置の指定する順序に従い、秘密の復元に参加する前記k個以上の記憶装置の全てから、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する前記k個以上の記憶装置の全てから、チェック用データ記憶装置を読み出すことを特徴とする秘密情報分散システム。付記8分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、前記分散情報生成装置が、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力し、前記n個の記憶装置が前記分散情報生成装置の出力を記憶し、前記復元装置が、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから前記分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする秘密情報分散方法。付記9分散情報生成装置と、n個nは2以上の自然数の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、前記秘密情報をk,n閾値秘密分散法で分散符号化することにより生成したn個の分散情報データvと前記秘密情報の検証を行うn個のチェック用データeとをチェック関数hに入力して得られる出力からn個の認証用データaを生成し、前記n個の分散情報データv、n個のチェック用データe及びn個の認証用データaをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラム。付記10分散情報生成装置と、n個nは2以上の自然数の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、前記n個の記憶装置の内のk個以上の前記記憶装置のそれぞれから分散情報データv、チェック用データe及び認証用データaを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データvから復元された秘密情報を出力する、ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラム。上記の実施形態の一部又は全部は、更に以下のようにも記載されうるが、以下には限られない。上記目的を達成するため本発明の分散情報生成装置は、秘密情報を入力とし、前記秘密情報をk,n閾値法で分散符号化した分散情報を出力する秘密情報分散装置と、前記秘密情報の検証を行うチェック用データを生成するチェック用データ生成装置と、前記分散情報と、チェック用データとを入力とし、予め定められたチェック関数hに入力して得られる出力から認証データを生成する認証データ生成装置とを有する。また、本発明の復元装置は、k個以上の前記記憶装置から分散符号化された分散秘密情報を読み出し、秘密情報の復元を行う秘密情報復元装置と、k個以上の前記記憶装置から分散情報と、チェック用データと、認証データとを読み出し、分散情報の正当性チェックを行い、改竄された分散情報が存在する場合には、改竄された分散秘密情報の識別子リストを出力し、改竄された分散情報が存在しない場合には、復元された秘密情報を出力する不正情報特定装置と、前記記憶装置から読み出す情報の順序を制御する読み出し制御装置を有する。上記のような構成を採り、読み出し制御装置の指定する順序に従い、秘密の復元に参加する全ての記憶装置から、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する全ての記憶装置から、チェック用データ記憶装置を読み出すこととする。また、関数hを、複数の関数値he,vが分かった場合でも、同じチェックデータeに対する知り得た値以外のv’に関する関数値he,v’の値を低い確率εでしか類推できない特徴を有するものの中から選択する。"