秘密情報分散システム及び秘密情報分散方法並びに秘密情報生成プログラム及び秘密情報復元プログラム
【課題】改竄されていない時点での他の分散情報を参照した後で分散情報を改竄する強力な不正に対しても不正の検知を行う。
【解決手段】分散情報生成装置は、秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ記憶装置に出力し、ｎ個の記憶装置は分散情報生成装置の出力を記憶し、復元装置は、ｎ個の記憶装置の内のｋ個以上の記憶装置のそれぞれから各データを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定する。
【解決手段】分散情報生成装置は、秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ記憶装置に出力し、ｎ個の記憶装置は分散情報生成装置の出力を記憶し、復元装置は、ｎ個の記憶装置の内のｋ個以上の記憶装置のそれぞれから各データを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は秘密情報の保管に関し、特に秘密情報を分散して安全に保管する秘密情報分散に関する。
【背景技術】
【０００２】
秘密情報を保管する場合、紛失や破壊の脅威と盗難の脅威とが存在する。ここで、秘密情報とは何らかの秘密にしておくべき情報であり、具体的にどのような情報であってもよい。秘密情報は、例えば、暗号化に用いる秘密鍵等を指すものとする。
【０００３】
前者の紛失や破壊の脅威に対しては秘密情報のコピーを作成することが有効な対策である。しかし、コピーを作成することで後者の盗難に対する脅威が増してしまう。このような問題を解決するための情報セキュリティ技術の１つとして秘密分散法がある。
【０００４】
秘密分散法は、もととなる秘密情報を複数の分散情報に分散し、予め定められた分散情報を集めると秘密情報を一意に復元可能であるが、それ以外の分散情報を集めても秘密に関する情報を全く漏らさないという特徴を持つ。
【０００５】
本明細書では、分散情報の数をｎ（ｎは２以上の自然数）とし、各分散情報を１からｎで識別する。
【０００６】
秘密分散法では、秘密情報を復元できる分散情報の集合をアクセス構造という分散情報の集合族Γで定義することが可能である。アクセス構造Γは、秘密情報を復元できる最小の分散情報の識別子の集合を要素として持つ集合族である。また、アクセス構造Γを持つ秘密分散法において、分散情報の集合ｗが秘密を復元可能であるとは、ｗに対応する分散情報の識別子集合Ｗに対して、Ｖ∈ΓかつＶ⊆ＷとなるようなＶが存在することを意味する。また、前記のような性質を満たす分散情報識別子の集合ＷをΓのアクセス集合と定義する。
【０００７】
例えば、（ｋ，ｎ）閾値法と呼ばれる、（１）ｎ個の分散情報のうち、ｋ個未満の分散情報では秘密に関する情報は全く得られない、（２）ｋ個以上の分散情報からは秘密は一意に復元されるという特徴を持つ秘密分散法に置けるアクセス構造ΓはΓ＝［Ｖ｜Ｖ⊆［１，．．．，ｎ］かつＶの要素数はｋ］という集合族によって定義される。以下、秘密分散法において、秘密情報を復元する際の問題点について考える。
【０００８】
或る復元者が秘密情報を復元する場合、この復元者は分散情報を保持する他のものから分散情報を集める必要がある。このとき、分散情報の被要求側が配付された値を改竄することなく復元者へ渡すとは限らない。なお、ここで言う「改竄」とは、意図的なものだけでなく、装置故障や単なるミス等の意図しない変更も含むものとする。
【０００９】
改竄された分散情報を用いて秘密情報を復元すると、その値は秘密情報と異なる値になってしまうことがある。そのため、秘密分散法には復元に用いる分散情報に改竄された場合に、改竄された分散情報を高い確率で検知できる手法が望まれる。これらの問題を解決するための一つの技術の例として下記の非特許文献２〜４の方法が知られている。
【００１０】
非特許文献２には、ｋ／２個未満の分散情報が改竄された場合に、高い確率で改竄された分散情報を特定できる（ｋ，ｎ）閾値法が記載されている。
【００１１】
非特許文献３には、ｋ／３個未満の分散情報が改竄された場合に、高い確率で改竄された分散情報を特定できる（ｋ，ｎ）閾値法が記載されている。非特許文献３に記載されている方式は、非特許文献２と比較して、分散情報のサイズが小さいことを特徴とする。
【００１２】
非特許文献４には、ｋ／３個未満の分散情報が改竄された場合に、高い確率で改竄された分散情報を特定できる（ｋ，ｎ）閾値法が記載されている。非特許文献４に記載されている方式は、非特許文献３と比較して、分散情報のサイズが小さいことを特徴とする。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Adi Shamir, "How to share a secret", Comm. ACM, 22(11), 612-613(1979)
【非特許文献２】T. Rabin and M. Ben-Or, "Verifiable Secret Sharing and Multiparty Protocols with Honest Majority," Proc. STOC'89, pp. 73--85.
【非特許文献３】K. Kurosawa, S. Obana and W. Ogata, "t-Cheater Identifiable (k,n) Threshold Secret Sharing Schemes," Proc. Crypto'95, Lecture Notes in Computer Science, vol. 963, Springer Verlag, pp. 410--423, 1995.
【非特許文献４】尾花, t人までの不正者を特定できる準最適な秘密分散法, 2007年 暗号と情報セキュリティシンポジウム
【発明の概要】
【発明が解決しようとする課題】
【００１４】
上述したような技術を用いることによって、秘密復元時に入力される分散情報のうち改竄されていない時点での分散情報を参照せずに分散情報を改竄する不正に対しては、安全性が保証される。
【００１５】
しかしながら、秘密復元に入力される改竄されていない時点での部分情報を参照した後で分散情報を改竄する、より強力な不正に対して安全な秘密分散法は従来一つも提案されていない。
【００１６】
本発明はこのような状況に鑑みてなされたものであり、本発明は、改竄されていない時点での他の分散情報を参照した後で分散情報を改竄する強力な不正に対しても不正の検知を行うことが可能な、秘密情報分散システム及び秘密情報分散方法並びに秘密情報生成プログラム及び秘密情報復元プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の第１の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、前記分散情報生成装置は、前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、前記ｎ個の記憶装置は前記分散情報生成装置の出力を記憶し、前記復元装置は、前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、ことを特徴とする秘密情報分散システムが提供される。
【００１８】
本発明の第２の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、前記分散情報生成装置が、前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、前記ｎ個の記憶装置が前記分散情報生成装置の出力を記憶し、前記復元装置が、前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、ことを特徴とする秘密情報分散方法が提供される。
【００１９】
本発明の第３の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラムが提供される。
【００２０】
本発明の第４の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラムが提供される。
【発明の効果】
【００２１】
本発明によれば、正当な記憶装置に格納されているチェック用データｅは、独立かつ一様ランダムに選ばれており、且つ、非改竄性のチェックに用いる関数ｈは、知り得た値以外の関数値をεより高い確率で類推することができないという性質を有していることから、改竄されていない時点での他の分散情報を参照した後で分散情報を改竄する強力な不正に対しても不正の検知を行うことが可能となる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施形態に係る秘密情報分散システム全体の基本的構成を表すブロック図である。
【図２】本発明の実施形態に係る分散情報生成装置及び記憶装置の基本的構成を表すブロック図である。
【図３】本発明の実施形態に係る復元装置及び記憶装置の基本的構成を表す構成ブロック図である。
【図４】本発明の実施形態に係る分散情報生成装置及び復元装置が行う処理を実行する処理装置の基本的構成を表す構成ブロック図である。
【図５】本発明の第１の実施形態に係る分散情報生成装置の動作処理を表すフローチャートである。
【図６】本発明の第１の実施形態に係る復元装置の動作処理を表すフローチャートである。
【図７】本発明の第２の実施形態に係る分散情報生成装置の動作処理を表すフローチャートである。
【図８】本発明の第２の実施形態に係る復元装置の動作処理を表すフローチャートである。
【発明を実施するための形態】
【００２３】
次に、本発明の実施形態について図面を用いて詳細に説明する。なお、以下に述べる実施の形態は、本発明の好適な実施の形態として、技術的に好ましい種々の限定が付されている。しかし、だからといって、本発明の範囲は、以下の説明において特に本発明を限定する旨の記載がない限り、これらの態様に限られるものではない。すなわち、下述する実施形態は、本発明の好適な実施形態ではあるが、これらの実施形態のみに本発明の範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した形態での実施が可能である。
【００２４】
本実施形態を説明するにあたり、まず本明細書で使用する用語について簡単に説明する。
【００２５】
（ｋ，ｎ）閾値法：秘密情報をｎ個の分散情報に分散符号化し、そのうちの任意のｋ個の分散情報により、もとの秘密情報の復元が可能となる性質を有する秘密分散法を指す。なお、非特許文献１に（ｋ，ｎ）閾値法に関する記載がある。
【００２６】
秘密情報ｓ：保管対象となる秘密情報を指す。
【００２７】
秘密情報データ集合Ｓ：保管対象となる秘密情報ｓの集合を指す。
【００２８】
認証データａ：認証に用いる認証データを指す。
【００２９】
認証データ集合Ａ：認証データａの集合であり、チェック関数ｈの値域を指す。Ａの要素であるａを「ａ［ｉ］」と記述した場合は、当該ａが第ｉ番目の認証データであることを表すものとする。
【００３０】
分散情報データｖ：秘密情報ｓ∈Ｓを分散符号化したデータ（分散情報）のうちの１つを指す。
【００３１】
分散情報データＶ：秘密情報ｓ∈Ｓを分散符号化したデータ（分散情報）の集合を指す。Ｖの要素であるｖを「ｖ［ｉ］」と記述した場合は、当該ｖが第ｉ番目の分散情報を表すものとする。
【００３２】
チェック用データｅ：分散情報の非改竄性チェックに用いられるデータを指す。
【００３３】
チェック用データ集合Ｅ：分散情報の非改竄性チェックに用いられるデータ集合である。Ｅの要素であるｅを「ｅ［ｉ］」と記述した場合は、当該ｅは第ｉ番目のチェック用データを表すものとする。
【００３４】
演算子：本明細書において、それぞれ、「＋」の記号を和、「−」の記号を差、「＊」の記号を積、「＾」の記号を冪乗、の演算子として用いる。
【００３５】
［実施形態１］
図１は、本発明の実施形態に係る秘密情報分散システム全体の基本的構成を表す図である。図１を参照すると、秘密情報分散システムは、分散情報生成装置１００、復元装置２００及び複数の記憶装置３００−１〜３００−ｎを有する。
【００３６】
分散情報生成装置１００は、秘密情報ｓ１を受け付け、受け付けた秘密情報ｓ１に基づいて分散情報を生成する装置である。また、複数の記憶装置３００−１〜３００−ｎは、分散情報生成装置１００が生成した分散情報を記憶する装置である。更に、復元装置２００は、記憶装置３００−１〜３００−ｎが記憶する分散情報に基づいて復元を行う装置である。なお、図示の都合上、記憶装置３００−１、３００−２及び３００−ｎの３つが図示されているが、これはあくまで一例であり、任意の台数の記憶装置３００が存在していてよい。
【００３７】
本発明の実施形態に係る秘密情報分散システムが秘密情報を保管する場合には、分散情報生成装置１００が分散情報の非改竄性チェックに用いるチェック用データをランダムに生成し、（ｋ，ｎ）閾値法で生成した分散情報、チェック用データ、分散情報とチェック用データを用いて生成した認証データを記憶装置３００に格納する。
【００３８】
また、秘密情報を復元する場合には、ｋ個以上の記憶装置３００から分散符号化された秘密情報及びチェック用データ、認証データを復元装置２００の指定する順序に従って読み出す。
【００３９】
そして、各記憶装置内に格納されている分散情報とチェック用データが認証データと正しく対応しているかを判定し、全ての記憶装置３００に関して、正しく対応していることが検証できた場合は、復元した秘密情報が正しいと判断し秘密を出力し、対応していない場合は分散情報が改竄されていると判断する対応していない分散情報の識別子リストを出力する。
【００４０】
次に、図２を参照して分散情報生成装置１００の構成について詳細に説明する。
【００４１】
図２は分散情報生成装置１００の構成を表すブロック図である。図２に示すように、分散情報生成装置１００は、秘密情報分散部１０１、チェック用データ生成部１０２及び認証データ生成部１０３を有している。
【００４２】
秘密情報分散部１０１は、秘密情報ｓ１を入力とし、秘密情報ｓ１を（ｋ，ｎ）閾値法で分散符号化したｎ個のデータｖ［１］，ｖ［２］，．．．，ｖ［ｎ］（ｖ［ｉ］∈Ｖ）を記憶装置３００及び認証データ生成部１０３に対して出力する。
【００４３】
チェック用データ生成部１０２は、チェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を生成する。また、チェック用データ生成部１０２は、生成したチェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を記憶装置３００及び認証データ生成部１０３に対して出力する。
【００４４】
認証データ生成部１０３は、秘密情報分散部１０１の出力ｖ［ｉ］，．．．，ｖ［ｎ］と、チェック用データ生成部１０２の出力ｅ［１］，．．．，ｅ［ｎ］とを入力として、認証情報ａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎであり、ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］））を出力する。
【００４５】
本実施形態では、チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｋ−２］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｋ−２］，ａ’に対して、｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ’）＝ａ’，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝１，２，．．．，ｋ−２）｝｜／｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］｝｜≦εを任意のｉ，ｊ，ｌについて満足するものとする。
【００４６】
以上をまとめると、分散情報生成装置１００は秘密情報データ集合Ｓの元となる（すなわち集合Ｓの要素である）秘密情報ｓ１を入力とし、記憶装置３００−１〜３００−ｎ内の分散秘密情報記憶部３０１−１〜３０１−ｎに秘密情報分散部１０１の出力であるＶの元ｖ［１］〜ｖ［ｎ］を、チェック用データ記憶部３０２−１〜３０２−ｎにチェック用データ生成部１０２の出力であるＥの元ｅ［１］〜ｅ［ｎ］を、チェック用データ記憶部３０３−１〜３０３−ｎに認証データ集合Ａの元である認証データａ［１］〜ａ［ｎ］をそれぞれ格納する。
【００４７】
次に、図２を参照して記憶装置３００−１〜３００−ｎの構成について詳細に説明する。
【００４８】
記憶装置３００−１〜３００−ｎは、分散秘密情報記憶部３０１−１〜３０１−ｎ、チェック用データ記憶部３０２−１〜３０２−ｎ、認証データ記憶部３０３−１〜３０３−ｎ及びアクセス制御部３０４−１〜３０４−ｎを含んでいる。
【００４９】
分散秘密情報記憶部３０１−１〜３０１−ｎは、分散情報データ集合Ｖの元となる分散データｖが格納される記憶部である。
【００５０】
チェック用データ記憶部３０２−１〜３０２−ｎは、チェック用データ集合Ｅの元となるチェック用データｅが格納される記憶部である。
【００５１】
認証データ記憶部３０３−１〜３０３−ｎは、認証データ集合Ａの元となる認証データａが格納される記憶部である。
【００５２】
アクセス制御部３０４−１〜３０４−ｎは、復元装置２００内の読み出し制御部２０３からの信号に基づき、復元装置２００から読み出せるデータを制御する。
【００５３】
続いて、復元装置２００の構成について図３を用いて説明する。図３は復元装置２００の構成を表すブロック図である。
【００５４】
図３に示すように、復元装置２００は、秘密情報復元部２０１、不正情報特定部２０２及び読み出し制御部２０３を含んでいる。
【００５５】
秘密情報復元部２０１は複数の記憶装置３００が有する分散秘密情報記憶部３０１に格納されたデータを不正情報特定部２０２から読み出し、復元した秘密情報データｓ∈Ｓを出力する。
【００５６】
不正情報特定部２０２は、ｋ個以上の記憶装置３００が備える分散秘密情報記憶部３０１に格納された分散情報ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］と、チェック用データ記憶部３０２に格納されたチェック用データｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］と、認証データ記憶部３０３に格納された認証データａ［ｉ−１］，．．．，ｅ［ｉ−ｍ］（但し、各ａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］））を読み出す。そして、全てのｉ＝ｉ−１，．．．，ｉ−ｍと、ｉと相異なる全てのｊ＝ｉ−１，．．．，ｉ−ｍの内、ｋ／２個以上のｊに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するかどうかを判定する。そして、この判定の結果、全てのｊについて上式が成立するｉの個数が２／ｋ以上である場合は、分散情報に改竄がないものと判定し、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］を秘密情報復元部２０１に入力して得られる、復元された秘密情報ｓ∈Ｓを出力する。
【００５７】
一方、上式が成立するｉの個数が２／ｋ未満となるｊが存在する場合は、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立する個数がｋ／２未満であったｊのリストを改竄が生じた分散情報の識別子として出力する。
【００５８】
読み出し制御部２０３は、記憶装置３００−１〜３００−ｎ内のアクセス制御部３０４−１〜３０４−ｎに対して読み出したいデータを伝える制御信号を出力する。アクセス制御部３０４−１〜３０４−ｎは前記制御信号に基づき、復元装置２００にデータ読み出しの許可を与える。
【００５９】
以上説明した、図１、図２及び図３に表された分散情報生成装置１００及び復元装置２００は、任意の方法により実現することが可能である。
【００６０】
例えばハードウェアとして分散情報生成装置１００及び復元装置２００を実現するのであれば、論理回路等から構成されるＬＳＩ（Large Scale Integration）やＤＳＰ（Digital Signal Processor）等の半導体集積回路によって実現できる。
【００６１】
また、分散情報生成装置１００及び復元装置２００は、ハードウェア及びソフトウェアの組合せとしても実現可能である。例えば、図４に示すように、プログラムにしたがって所定の処理を実行する処理装置１０と、処理装置１０に対してコマンドや情報等を入力するための入力部２０と、処理装置１０の処理結果をモニタするための出力部３０とを含んだコンピュータによって分散情報生成装置１００及び復元装置２００を実現してもよい。この点について、以下詳細に説明する。
【００６２】
図４を参照すると処理装置１０は、ＣＰＵ１１と、主記憶部１２と、記録媒体１３と、データ蓄積部１４と、メモリ制御インタフェース部１５と、Ｉ／Ｏインタフェース部１６とを有する。これら各構成要素は、バス１８を介して相互に接続されている。
【００６３】
ＣＰＵ１１はプログラムに基づいて演算を行う演算処理装置である。主記憶部１２は、ＣＰＵ１１の演算処理に必要な情報を一時的に記憶する主記憶部である。
【００６４】
記録媒体１３は、ＣＰＵ１１に分散情報生成装置１００または復元装置２００としての処理を実行させるためのプログラムが記録された記録媒体である。処理装置１０は、記録媒体１３に記録されたプログラムに従って分散情報生成装置１００または復元装置２００としての機能を実現する。
【００６５】
データ蓄積部１４は、秘密情報やアクセス構造データが格納される補助記憶装置である。
【００６６】
なお、記録媒体１３及びデータ蓄積部１４は、任意の装置により実現可能である。記録媒体１３及びデータ蓄積部１４は、例えば、ＨＤＤ（Hard disk drive）やＦｌａｓｈ ＳＳＤ（Solid State Drive）により実現される。また、この記憶装置は処理装置１０内にある必要はなく、外部の記憶装置（図示を省略する）を利用するようにしてもよい。この場合記憶装置を別のコンピュータとして実現し、バスやＵＳＢ規格に準拠したケーブルや、インターネット等の手段を用いて接続するようにしてもよい。更に、単一の記憶装置により実現されてもよいが、複数の記憶装置の組合せにより実現されていてもよい。加えて、記録媒体１３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。例えば、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory）、ＤＶＤ（Digital Versatile Disc)、ＭＯ（Magneto Optical Disk(Disc)）ＢＤ（Blu-ray Disc）等であってもよい。加えて、データ蓄積部１４は、分散秘密情報記憶部３０１及びチェック用データ記憶部３０２及び認証用データ記憶部３０３を備える記憶装置３００として用いてもよい。すなわち、散情報生成装置１００、復元装置２００及び記憶装置３００は、複数のコンピュータで実現してもよく、単一のコンピュータで実現してもよい。
【００６７】
メモリ制御インタフェース部１５は、主記憶部１２、記録媒体１３及びデータ蓄積部１４とＣＰＵ１１等とのデータ転送を制御する。
【００６８】
次に本実施形態の秘密情報分散システムの動作について図５及び図６を参照して説明する。図５は分散情報生成装置１００の動作を示すフローチャートであり、図６は復元装置２００の動作を示すフローチャートである。
【００６９】
まず、分散情報生成部１００の秘密情報分散部１０１には、秘密情報データ集合Ｓの元である秘密情報ｓ１が入力される（ステップＡ４０１）。
【００７０】
分散情報生成装置１００は、秘密情報分散部１０１に秘密情報ｓ１が入力されると、秘密情報分散部１０１により秘密情報ｓ１を（ｋ，ｎ）閾値法により分散符号化し、生成されたｖ［ｉ］（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉの分散秘密情報記憶部３０１−ｉ及び認証データ生成部１０３に格納する（ステップＡ４０２）。
【００７１】
また、分散情報生成装置１００は、チェック用データ生成部１０２により、チェック用データｅ［ｉ］（ｉ＝１，．．．，ｎ）を生成し、生成したｅ［ｉ］を、記憶装置３００−ｉのチェック用データ記憶部３０２−ｉ及び認証データ生成部１０３に格納する（ステップＡ４０３）。
【００７２】
分散情報生成装置１００は、認証データ生成部１０３により、分散情報ｖ［ｉ］（ｉ＝１，．．．，ｎ）と、チェック用データｅ［ｊ］（ｊ＝１，．．．，ｎ，ｊ≠ｉ）に対して、ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］）を計算し、認証データａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を、記憶装置３００−ｉの認証データ記憶部３０３−ｉに格納する（ステップＡ４０４）。
【００７３】
図５に示すように、復元装置２００は、記憶装置３００のアクセス制御部３０４に分散秘密情報記憶部３０１、認証データ記憶部３０３のデータを読み出すことを示す制御信号を送り、ｋ個以上の記憶装置３００の分散秘密情報記憶部３０１と認証データ記憶部３０３から読み出した分散データｖ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ），認証情報ａ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＴ５０１）。
【００７４】
ステップＴ５０１でのデータ読み込み終了後、復元装置２００は、ステップＴ５０１で読み出した記憶装置３００と同じ記憶装置３００のアクセス制御部３０４に対してチェック用データ記憶部３０２のデータを読み出すことを示す制御信号を送り、当該記憶装置３００のチェック用データ記憶部３０２から読み出したチェック用データｅ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＴ５０２）。すなわちステップＴ５０１及びＴ５０２では同一であってｋ個以上の記憶装置３００から分散データｖ［ｉ］、認証情報ａ［ｉ］及びチェック用データｅ［ｉ］を読み込むこととなる。
【００７５】
ステップＴ５０１とステップＴ５０２でのデータ読み込み後、復元装置２００は、ステップＴ５０１，Ｔ５０２で読み込んだｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）とｊ≠ｉなるｊ（ｊ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）に対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するか否かを不正情報特定部２０２によりチェックする（ステップＴ５０３）。
【００７６】
ステップＴ５０３のチェックにより、全てのｊに対して、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するｉの個数が２／ｋ以上である場合は、秘密情報復元部２０１に読み込んだ全てのｖ［ｉ］を秘密情報復元部２０１に入力して得られる復元された秘密情報ｓ１を出力して終了（ステップＴ５０４においてＹｅｓ、ステップＴ５０５）。
【００７７】
一方、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するｉの個数が２／ｋ未満となるｊが存在する場合、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するｉの個数が２／ｋ未満となるｊのリストを改竄された分散情報の識別子として出力して終了する（ステップＴ５０４においてＮｏ、ステップＴ５０６）。
【００７８】
上記実施形態によれば、不正な記憶装置３００は、正当な記憶装置３００のチェック用データを読み出した後に改竄の検出が行えないように分散情報記憶部３０１のデータを改竄することは不可能になり、正当な記憶装置３００の送出する情報を参照した後に成功するようなデータを計算することができなくなるという効果を奏する。
【００７９】
［実施形態２］
次に、本発明の第２の実施形態について図面を参照して詳細に説明する。
【００８０】
実施形態２に係る秘密情報分散システムの基本的構成は図１、図２及び図３に表される実施形態１と同様であるため、その説明を省略する。
【００８１】
一方、実施形態２ではチェック用データ生成部１０２が、チェック用データｅ∈Ｅを生成する。そして、ｅを（ｔ，ｎ）閾値法で分散符号化する点において実施形態１と異なる。また、これに伴い復元装置２００での動作も異なる。よって、この点を中心として説明をする。そして、特に言及しない点においては実施形態１と同様であるとする。
【００８２】
まず、分散情報生成装置１００について説明する。
【００８３】
秘密情報分散部１０１は、秘密情報ｓ１を入力とし、秘密情報ｓ１を（ｋ，ｎ）閾値法で分散符号化したｎ個のデータｖ［１］，ｖ［２］，．．．，ｖ［ｎ］（ｖ［ｉ］∈Ｖ）を記憶装置３００及び認証データ生成部１０３に対して出力する。
【００８４】
本実施形態における、チェック用データ生成部１０２は、チェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を生成する。また、チェック用データ生成部１０２は、生成したチェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を記憶装置３００に対して出力する。
【００８５】
認証データ生成部は１０３、秘密情報分散部１０１の出力ｖ［ｉ］，．．．，ｖ［ｎ］と、チェック用データｅ、認証情報ａ［ｉ］＝ｈ（ｅ，ｖ［ｊ］）を出力する。
【００８６】
本実施形態では、チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｔ−１］，ａ’に対して、｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ’）＝ａ’，ｈ（ｅ，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝ｔ−１）｝｜／｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ［ｌ］）＝ａ［ｌ］｝｜≦εを任意のｉ，ｊ，ｌについて満足するものとする。
【００８７】
以上をまとめると、分散情報生成装置１００は秘密情報データ集合Ｓの元となる（すなわち集合Ｓの要素である）秘密情報ｓ１を入力とし、記憶装置３００−１〜３００−ｎ内の分散秘密情報記憶部３０１−１〜３０１−ｎに秘密情報分散部の出力であるＶの元ｖ［１］〜ｖ［ｎ］を、チェック用データ記憶部３０２−１〜３０２−ｎにチェック用データ生成部１０２の出力ｅ［１］〜ｅ［ｎ］を、チェック用データ記憶部３０３−１〜３０３−ｎに認証データ集合Ａの元である認証データａ［１］〜ａ［ｎ］をそれぞれ格納する。
【００８８】
また、本実施形態の記憶装置３００−１〜３００−ｎは、分散情報データ集合Ｖの元が格納される分散情報記憶部３０１−１〜３０１−ｎと、チェック用データ集合Ｅの元が格納されるチェック用データ記憶部３０２−１〜３０２−ｎと、認証データ集合Ａの元が格納される認証データ記憶部３０３−１〜３０３−ｎと、復元装置２００内の読み出し制御部からの信号に基づき、復元装置２００から読み出せるデータを制御するアクセス制御部３０４−１〜３０４−ｎとを含んでいる。
【００８９】
次に、本実施形態の復元装置２００の構成について説明する。図３は復元装置２００の構成ブロック図である。図３に示すように、復元装置２００は、秘密情報復元部２０１、不正情報特定部２０２、及び読み出し制御部２０３を備えている。
【００９０】
秘密情報復元部２０１は複数の記憶装置３００が備える分散秘密情報記憶部３０１に格納されたデータ不正情報特定部２０２からを読み出し、復元した秘密情報データｓ∈Ｓを出力する。
【００９１】
不正情報特定部２０２は、ｋ個以上の記憶装置３００が備える分散秘密情報記憶部３０１に格納された分散情報ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］と、チェック用データ記憶部３０２に格納されたチェック用データｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］と、認証データ記憶部３０３に格納された認証データａ［ｉ−１］，．．．，ａ［ｉ−ｍ］を読み出す。そして、ｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からｅの復元を行った後、全てのｉ＝ｉ−１，．．．，ｉ−ｍに対し、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立するかどうかを判定する。そして、この判定の結果、全てのｉについて上式が成立する時は分散情報に改竄がないものと判定し、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］を秘密情報復元部２０１に入力して得られる、復元した秘密情報ｓ∈Ｓを出力する。
【００９２】
一方、上式が成立しない時はｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立しないｉのリストを改竄が生じた分散情報の識別子として出力する。
【００９３】
このとき、ｅは（ｔ，ｎ）閾値秘密分散の分散情報であるためｍ≧ｋとなるｍ個のｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からｔ個の改竄されたｅ［ｉ−ｊ］の誤りを訂正し、正しいｅが復元できることが知られている。
【００９４】
読み出し制御部２０３は、記憶装置３００−１〜３００−ｎ内のアクセス制御部３０４−１〜３０４−ｎに対して読み出したいデータを伝える制御信号を出力する。アクセス制御部３０４−１〜３０４−ｎは前記制御信号に基づき、復元装置２００にデータ読み出しの許可を与える。
【００９５】
なお、本実施形態は実施形態１と同様、分散情報生成装置１００及び復元装置２００を半導体集積回路によって実現できる。また、本実施形態は実施形態１と同様、分散情報生成装置１００及び復元装置２００を図４に表されるような処理装置１０により実現できる。なお具体的な実現方法は、実施形態１の説明において上述した内容と同様である。
【００９６】
次に本実施形態の秘密情報分散システムの動作について図７及び図８を参照して説明する。図７は分散情報生成装置１００の動作を示すフローチャートであり、図８は復元装置２００の動作を示すフローチャートである。
【００９７】
まず、分散情報生成部１００の秘密情報分散部１０１には、秘密情報データ集合Ｓの元である秘密情報ｓ１が入力される（ステップＵ６０１）。
【００９８】
分散情報生成装置１００は、秘密情報分散部１０１に秘密情報ｓ１が入力されると、秘密情報分散部１０１により秘密情報ｓ１を（ｋ，ｎ）閾値法により分散符号化し、生成されたｖ［ｉ］（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉの分散秘密情報記憶部３０１−ｉ及び認証データ生成部１０３に格納する（ステップＵ６０２）。
【００９９】
また、分散情報生成装置１００は、チェック用データ生成部１０２により、チェック用データｅを生成し、ｅを（ｔ，ｎ）閾値法で分散符号化したｅ［ｉ］（ｉ＝１，．．．，ｎ）を生成し、生成したｅ［ｉ］を、記憶装置３００−ｉのチェック用データ記憶部３０２−ｉに格納する（ステップＵ６０３）。
【０１００】
分散情報生成装置１００は、認証データ生成部１０３により、分散情報ｖ［ｉ］（ｉ＝１，．．．，ｎ）と、チェック用データ生成部１０２が生成したチェック用データｅに対して、ａ［ｉ］＝ｈ（ｅ，ｖ［ｉ］）を計算し、認証データａ［ｉ］（ｉ＝１，．．．，ｎ）を、記憶装置３００−ｉの認証データ記憶部３０３−ｉに格納する（ステップＵ６０４）。
【０１０１】
図７に示すように、復元装置２００は、記憶装置３００のアクセス制御部３０４に分散秘密情報記憶部３０１、認証データ記憶部３０３のデータを読み出すことを示す制御信号を送り、ｋ個以上の記憶装置３００の分散秘密情報記憶部３０１と認証データ記憶部３０３から読み出した分散データｖ［ｉ］，認証情報ａ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＷ７０１）。
【０１０２】
ステップＷ７０１でのデータ読み込み終了後、復元装置２００は、ステップＷ７０１で読み出した記憶装置３００と同じ記憶装置３００のアクセス制御部３０４に対してチェック用データ記憶部３０２のデータを読み出すことを示す制御信号を送り、当該記憶装置３００のチェック用データ記憶部３０２から読み出したチェック用データｅ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＷ７０２）。すなわちステップＷ７０１及びＷ７０２では同一であってｋ個以上の記憶装置３００から分散データｖ［ｉ］、認証情報ａ［ｉ］及びチェック用データｅ［ｉ］を読み込むこととなる。
【０１０３】
ステップＷ７０１とステップＷ７０２でのデータ読み込み後、復元装置２００は、ステップＷ７０１，Ｗ７０２で読み込んだｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］から、ｅの復元を行い、ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）に対し、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立するか否かを不正情報特定部２０２によりチェックする（ステップＷ７０３）。
【０１０４】
ステップＷ７０３のチェックにより、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立する場合は、秘密情報復元部２０１に読み込んだ全てのｖ［ｉ］を秘密情報復元部２０１に入力して得られる復元された秘密情報ｓ１を出力して終了する（ステップＷ７０４においてＹｅｓ、ステップＷ７０５）。
【０１０５】
一方、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立しないｉが存在する場合、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立しないｉのリストを改竄された分散情報の識別子として出力して終了する（ステップＷ７０４においてＮｏ、ステップＷ７０６）。
【０１０６】
上記実施形態によれば、不正な記憶装置３００は、正当な記憶装置３００のチェック用データを読み出した後に改竄の検出が行えないように分散情報記憶部３０１のデータを改竄することは不可能になり、正当な記憶装置３００の送出する情報を参照した後に成功するようなデータを計算することができなくなるという効果を奏する。
【０１０７】
次に、上述した各実施形態をより具体的に説明した例である、本発明の実施例について説明する。
【実施例１】
【０１０８】
実施例１は、上述した実施形態１に対応する実施例である。本実施例におけるに秘密情報分散システムは、秘密情報ｓのデータ集合にＧＦ（ｐ）（ｐ：素数冪，ＧＦ：ガロア体）を、チェック用データｅ［ｉ］＝（ｅ［ｉ，１］，．．．，ｅ［ｉ，ｉ−１］，ｅ［ｉ，ｉ＋１］，ｅ［ｉ，ｎ］）（但し、ｅ［ｉ，ｊ］＝（ｅ［ｉ，ｊ］｛０｝，ｅ［ｉ，ｊ］｛１｝）），ｅ［ｉ，ｊ］｛ｂ｝はＧＦ（ｐ）の元）として、認証用データとしてａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）を用いる。
【０１０９】
次に本実施例に係る分散情報生成装置１００及び復元装置２００について説明する。本実施例に係る分散情報生成装置１００には、秘密情報ｓ∈ＧＦ（ｐ）が入力される。
【０１１０】
分散情報生成装置１００は、秘密情報ｓが入力されると、秘密情報分散部１０１によりＧＦ（ｐ）上の定数項がｓであるｋ−１次多項式をランダムに生成する。このｋ−１次多項式をｆ−ｓ（ｘ）と記す。
【０１１１】
秘密情報分散部１０１は、相異なる１，２，．．．，ｎに対して、ｖ［１］＝ｆ−ｓ（１），ｖ［２］＝ｆ−ｓ（２），…，ｖ［ｎ］＝ｆ−ｓ（ｎ）を計算し、その計算結果を記憶装置３００−１の分散秘密情報記憶部３０１−１、記憶装置３００−２の分散秘密情報記憶部３０１−２，…，記憶装置３００−ｎの分散秘密情報記憶部３０１−ｎにそれぞれ格納する。
【０１１２】
チェック用データ生成部１０２は、ＧＦ（ｐ）の元であるｅ［ｉ，ｊ］｛ｂ｝（ｉ＝１，．．．，ｎ，ｊ＝１，．．．，ｎ，ｂ＝０，１，ｊ≠ｉ）をランダムに生成し、ｅ［ｉ］（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉのチェック用データ記憶部３０２−ｉに格納する。
【０１１３】
次に、認証データ生成部１０３は、ａ［ｉ，ｊ］＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝を計算し、ａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉの認証データ記憶部３０３−ｉにそれぞれ格納する。
【０１１４】
一方、本実施例に係る復元装置２００は、まず、分散情報と認証データの読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各分散秘密情報記憶部３０１と各認証データ記憶部３０３とからデータｖ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を読み出す。
【０１１５】
次に、復元装置２００は、乱数分散情報の読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｋ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，…，３００−［ｉ−ｋ］の各チェック用データ記憶部３０２からデータｅ［ｉ］を読み出す。
【０１１６】
不正情報特定部２０２は、ｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を入力とし、全てのｉ＝ｉ−１，．．．，ｉ−ｍと、ｉとは相異なるｊ＝ｉ−１，．．．，ｉ−ｍについてａ［ｉ，ｊ］＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝が成立するか否かをチェックし、全てのｉについて上式が成立するｊの個数が２／ｋ以上であった場合は、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］からラグランジュ補完などの手段によって秘密情報ｓを計算して出力する。一方、成立していない場合は上式が成立するｊが２／ｋ未満となったｊのリストを改竄された分散情報の識別子として出力する。
【０１１７】
本実施例に係る秘密情報分散システムでは、ｋ／２未満の改竄された分散情報を確率１−１／ｐで特定することができるという効果を奏する。
【実施例２】
【０１１８】
実施例２は、上述した実施形態２に対応する実施例である。本実施例におけるに秘密情報分散システムは、秘密情報ｓのデータ集合にＧＦ（ｐ）（ｐ：素数冪，ＧＦ：ガロア体）を、チェック用データｅ＝（ｅ｛０｝，ｅ｛１｝，．．．，ｅ｛ｔ｝）としてＧＦ（ｑ）＾（ｔ＋１）の元（但し、ｑはｐ×ｎ以上の素数）、認証用データとしてＧＦ（ｑ）の元ａ［ｉ］を用いる。
【０１１９】
次に本実施例に係る分散情報生成装置１００及び復元装置２００について説明する。本実施例に係る分散情報生成装置１００には、秘密情報ｓ∈ＧＦ（ｐ）が入力される。
【０１２０】
分散情報生成装置１００は、秘密情報ｓが入力されると、秘密情報分散部１０１によりＧＦ（ｐ）上の定数項がｓであるｋ−１次多項式をランダムに生成する。このｋ−１次多項式をｆ−ｓ（ｘ）と記す。
【０１２１】
秘密情報分散部１０１は、相異なる１，２，．．．，ｎに対して、ｖ［１］＝ｆ−ｓ（１），ｖ［２］＝ｆ−ｓ（２），…，ｖ［ｎ］＝ｆ−ｓ（ｎ）を計算し、その計算結果を記憶装置３００−１の分散秘密情報記憶部３０１−１、記憶装置３００−２の分散秘密情報記憶部３０１−２，…，記憶装置３００−ｎの分散秘密情報記憶部３０１−ｎにそれぞれ格納する。
【０１２２】
チェック用データ生成部１０２は、ＧＦ（ｑ）の元であるｅをランダムに生成し、ｆ−ｅ（０）＝ｅとなるｔ次多項式ｆ−ｅ（ｘ）をランダムに生成、ｅ［ｉ］＝ｆ−ｅ（ｉ）（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉのチェック用データ記憶部３０２−ｉに格納する。
【０１２３】
次に、認証データ生成部１０３は、ａ［ｉ］＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛２｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｊ］＾ｔ）を計算し、記憶装置３００−ｉの認証データ記憶部３０３−ｉにそれぞれ格納する。（但し、ψ（ｖ［ｉ］）はψ（ｖ［ｉ］）＝ｐ＊（ｉ−１）＋ｖ［ｉ］で定義される関数）
一方、本実施例に係る復元装置２００は、まず、分散情報と認証データの読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各分散秘密情報記憶部３０１と各認証データ記憶部３０３とからデータｖ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を読み出す。
【０１２４】
次に、復元装置２００は、乱数分散情報の読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｋ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，…，３００−［ｉ−ｋ］の各チェック用データ記憶部３０２からデータｅ［ｉ］を読み出す。
【０１２５】
不正情報特定部２０２は、ｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を入力とし、ｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］からバーレカンプマッシー法（Berlekamp-Massey algorithm）やユークリッド法（Euclidean algorithm）などの誤り訂正符号の復号法を利用して正しいｅを復元する。そして、ａ［ｉ］＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛２｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｊ］＾ｔ）が成立するか否かをチェックし、全てのｉについて上式が成立する場合は、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］からラグランジュ補完などの手段によって秘密情報ｓを計算して出力し、成立しないｉが存在する場合には、そのｉのリストを改竄された分散情報の識別子として出力する。
【０１２６】
本実施例に係る秘密情報分散システムでは、ｋ／２未満の改竄された分散情報を確率１−１／ｐで特定することができる。
【０１２７】
以上、本発明を好適な実施形態及び好適な実施例に基づき具体的に説明したが、本発明は上記のものに限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【０１２８】
以上説明した本発明の実施形態は、以下に示すような効果を奏する。
【０１２９】
本発明の実施形態によれば、部分情報の改竄を行う記憶装置は、プロトコルに従ってまず最初に改竄した分散情報と認証データを復元装置に渡す必要がある。このとき、部分情報の改竄を行う記憶装置は、改竄を行っていない正当な記憶装置に格納されているチェック用データの値を参照することができない。正当な記憶装置に格納されているチェック用データｅは、独立かつ一様ランダムに選ばれており、また、非改竄性のチェックに用いる関数ｈは、知り得た値以外の関数値をεより高い確率で類推することができないという性質を有している。従って、仮に改竄を行う記憶装置が記憶装置に格納されている複数の分散情報と認証データを参照し、不正情報特定装置に特定されない形で改竄を行った場合でも、不正情報特定装置が偽造を特定できない確率はε以下となることが保証されるという効果を奏する。
【０１３０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１３１】
上記目的を達成するため本発明の分散情報生成装置は、秘密情報を入力とし、前記秘密情報を（ｋ，ｎ）閾値法で分散符号化した分散情報を出力する秘密情報分散装置と、前記秘密情報の検証を行うチェック用データを生成するチェック用データ生成装置と、前記分散情報と、チェック用データとを入力とし、予め定められたチェック関数ｈに入力して得られる出力から認証データを生成する認証データ生成装置とを有する。
【０１３２】
また、本発明の復元装置は、ｋ個以上の前記記憶装置から分散符号化された分散秘密情報を読み出し、秘密情報の復元を行う秘密情報復元装置と、ｋ個以上の前記記憶装置から分散情報と、チェック用データと、認証データとを読み出し、分散情報の正当性チェックを行い、改竄された分散情報が存在する場合には、改竄された分散秘密情報の識別子リストを出力し、改竄された分散情報が存在しない場合には、復元された秘密情報を出力する不正情報特定装置と、前記記憶装置から読み出す情報の順序を制御する読み出し制御装置を有する。
【０１３３】
上記のような構成を採り、読み出し制御装置の指定する順序に従い、秘密の復元に参加する全ての記憶装置から、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する全ての記憶装置から、チェック用データ記憶装置を読み出すこととする。また、関数ｈを、複数の関数値ｈ（ｅ，ｖ）が分かった場合でも、同じチェックデータｅに対する知り得た値以外のｖ’に関する関数値ｈ（ｅ，ｖ’）の値を低い確率εでしか類推できない特徴を有するものの中から選択する。
【０１３４】
（付記１） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、
前記分散情報生成装置は、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置は前記分散情報生成装置の出力を記憶し、
前記復元装置は、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散システム。
【０１３５】
（付記２） 付記１に記載の秘密情報分散システムであって、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［１］，．．．，ｅ［ｎ］とを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］）（ｉ≠ｊ）からｎ個の認証データａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］），ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、チェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、全ての可能な相異なるｉ，ｊ（ｉ，ｊ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］」なる式が成立するか否かを判定し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］が存在する場合は、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］がそのようなｖ［ｊ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’（ｔ≧ｋ／２）と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｋ−２］，ａ’に対して、｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ’）＝ａ’，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］｝（ｌ＝１，２，．．．，ｔ−１）｜≦εを任意のｉ，ｊ，ｌについて満足することを特徴とする秘密情報分散システム。
【０１３６】
（付記３） 付記１又は２に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［ｉ］＝（ｅ［ｉ，１］，ｅ［ｉ，２］，．．．，ｅ［ｉ，ｉ−１］，ｅ［ｉ，ｉ＋１］，ｅ［ｉ，ｉ＋２］，．．．，ｅ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ、但し、各ｅ［ｉ，ｊ］＝（ｅ［ｉ，ｊ］｛０｝，ｅ［ｉ，ｊ］｛１｝））（ｉ＝１，．．．，ｎ）とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝によって定義されることを特徴とする秘密情報分散システム。
【０１３７】
（付記４） 付記１に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、前記チェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅを前記記憶装置に出力し、
前記復元装置は、前記（ｔ，ｎ）閾値秘密分散法で分散符号化されたチェック用データｅを更に用いて前記分散情報の正当性の判定を行うことを特徴とする秘密情報分散システム。
【０１３８】
（付記５） 付記４に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うチェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅとを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ］＝ｈ（ｅ，ｖ［ｉ］）（ｉ＝１，．．．，ｎ）を認証データとして出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、分散符号化されたチェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、ｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からチェック用データｅを復元し、全てのｉ（ｉ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｍ）」なる式が成立するか否かをチェックし、前記式が成立しなかったｖ［ｉ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、そのようなｖ［ｉ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｔ−１］，ａ’に対して、｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ’）＝ａ’，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１｝｜≦εを任意のｉについて満足することを特徴とする
秘密情報分散システム。
【０１３９】
（付記６） 付記４又は５に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ＝（ｅ｛０｝，ｅ｛１｝，．．．，ｅ｛ｔ｝）と、ｐ≧ｎとなる任意の素数と、関数ψ（ｖ［ｉ］）＝ｐ×（ｉ−１）＋ｖ［ｉ］とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛３｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｉ］）＾ｔによって定義されることを特徴とする秘密情報分散システム。
【０１４０】
（付記７） 付記１乃至６の何れか１に記載の秘密情報分散システムにおいて、
前記記憶装置は、
当該各記憶装置に格納されている情報を前記復元装置に送信するタイミングを制御するアクセス制御手段を更に備え、
前記復元装置は、
前記記憶装置から読み出す情報の順序を制御する読み出し制御手段を更に備え、
前記復元装置は前記読み出し制御装置の指定する順序に従い、秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、チェック用データ記憶装置を読み出すことを特徴とする秘密情報分散システム。
【０１４１】
（付記８） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、
前記分散情報生成装置が、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置が前記分散情報生成装置の出力を記憶し、
前記復元装置が、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散方法。
【０１４２】
（付記９） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラム。
【０１４３】
（付記１０） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラム。
【０１４４】
上記の実施形態の一部又は全部は、更に以下のようにも記載されうるが、以下には限られない。
【０１４５】
上記目的を達成するため本発明の分散情報生成装置は、秘密情報を入力とし、前記秘密情報を（ｋ，ｎ）閾値法で分散符号化した分散情報を出力する秘密情報分散装置と、前記秘密情報の検証を行うチェック用データを生成するチェック用データ生成装置と、前記分散情報と、チェック用データとを入力とし、予め定められたチェック関数ｈに入力して得られる出力から認証データを生成する認証データ生成装置とを有する。
【０１４６】
また、本発明の復元装置は、ｋ個以上の前記記憶装置から分散符号化された分散秘密情報を読み出し、秘密情報の復元を行う秘密情報復元装置と、ｋ個以上の前記記憶装置から分散情報と、チェック用データと、認証データとを読み出し、分散情報の正当性チェックを行い、改竄された分散情報が存在する場合には、改竄された分散秘密情報の識別子リストを出力し、改竄された分散情報が存在しない場合には、復元された秘密情報を出力する不正情報特定装置と、前記記憶装置から読み出す情報の順序を制御する読み出し制御装置を有する。
【０１４７】
上記のような構成を採り、読み出し制御装置の指定する順序に従い、秘密の復元に参加する全ての記憶装置から、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する全ての記憶装置から、チェック用データ記憶装置を読み出すこととする。また、関数ｈを、複数の関数値ｈ（ｅ，ｖ）が分かった場合でも、同じチェックデータｅに対する知り得た値以外のｖ’に関する関数値ｈ（ｅ，ｖ’）の値を低い確率εでしか類推できない特徴を有するものの中から選択する。
【符号の説明】
【０１４８】
１０ 処理装置
１１ ＣＰＵ
１２ 主記憶部
１３ 記録媒体
１４ データ蓄積部
１５ メモリ制御インタフェース部
１６ Ｉ／Ｏインタフェース部
１００ 分散情報生成装置
１０１ 秘密情報分散部
１０２ チェック用データ生成部
１０３ 認証データ部
２００ 復元装置
２０１ 秘密情報復元部
２０２ 不正情報特定部
２０３ 読み出し制御部
３００−１〜３００−ｎ記憶装置
３０１−１〜３０１−ｎ 分散秘密情報記憶部
３０２−１〜３０２−ｎ チェック用データ記憶部
３０３−１〜３０３−ｎ 認証データ記憶部
３０４−１〜３０４−ｎ アクセス制御部
【技術分野】
【０００１】
本発明は秘密情報の保管に関し、特に秘密情報を分散して安全に保管する秘密情報分散に関する。
【背景技術】
【０００２】
秘密情報を保管する場合、紛失や破壊の脅威と盗難の脅威とが存在する。ここで、秘密情報とは何らかの秘密にしておくべき情報であり、具体的にどのような情報であってもよい。秘密情報は、例えば、暗号化に用いる秘密鍵等を指すものとする。
【０００３】
前者の紛失や破壊の脅威に対しては秘密情報のコピーを作成することが有効な対策である。しかし、コピーを作成することで後者の盗難に対する脅威が増してしまう。このような問題を解決するための情報セキュリティ技術の１つとして秘密分散法がある。
【０００４】
秘密分散法は、もととなる秘密情報を複数の分散情報に分散し、予め定められた分散情報を集めると秘密情報を一意に復元可能であるが、それ以外の分散情報を集めても秘密に関する情報を全く漏らさないという特徴を持つ。
【０００５】
本明細書では、分散情報の数をｎ（ｎは２以上の自然数）とし、各分散情報を１からｎで識別する。
【０００６】
秘密分散法では、秘密情報を復元できる分散情報の集合をアクセス構造という分散情報の集合族Γで定義することが可能である。アクセス構造Γは、秘密情報を復元できる最小の分散情報の識別子の集合を要素として持つ集合族である。また、アクセス構造Γを持つ秘密分散法において、分散情報の集合ｗが秘密を復元可能であるとは、ｗに対応する分散情報の識別子集合Ｗに対して、Ｖ∈ΓかつＶ⊆ＷとなるようなＶが存在することを意味する。また、前記のような性質を満たす分散情報識別子の集合ＷをΓのアクセス集合と定義する。
【０００７】
例えば、（ｋ，ｎ）閾値法と呼ばれる、（１）ｎ個の分散情報のうち、ｋ個未満の分散情報では秘密に関する情報は全く得られない、（２）ｋ個以上の分散情報からは秘密は一意に復元されるという特徴を持つ秘密分散法に置けるアクセス構造ΓはΓ＝［Ｖ｜Ｖ⊆［１，．．．，ｎ］かつＶの要素数はｋ］という集合族によって定義される。以下、秘密分散法において、秘密情報を復元する際の問題点について考える。
【０００８】
或る復元者が秘密情報を復元する場合、この復元者は分散情報を保持する他のものから分散情報を集める必要がある。このとき、分散情報の被要求側が配付された値を改竄することなく復元者へ渡すとは限らない。なお、ここで言う「改竄」とは、意図的なものだけでなく、装置故障や単なるミス等の意図しない変更も含むものとする。
【０００９】
改竄された分散情報を用いて秘密情報を復元すると、その値は秘密情報と異なる値になってしまうことがある。そのため、秘密分散法には復元に用いる分散情報に改竄された場合に、改竄された分散情報を高い確率で検知できる手法が望まれる。これらの問題を解決するための一つの技術の例として下記の非特許文献２〜４の方法が知られている。
【００１０】
非特許文献２には、ｋ／２個未満の分散情報が改竄された場合に、高い確率で改竄された分散情報を特定できる（ｋ，ｎ）閾値法が記載されている。
【００１１】
非特許文献３には、ｋ／３個未満の分散情報が改竄された場合に、高い確率で改竄された分散情報を特定できる（ｋ，ｎ）閾値法が記載されている。非特許文献３に記載されている方式は、非特許文献２と比較して、分散情報のサイズが小さいことを特徴とする。
【００１２】
非特許文献４には、ｋ／３個未満の分散情報が改竄された場合に、高い確率で改竄された分散情報を特定できる（ｋ，ｎ）閾値法が記載されている。非特許文献４に記載されている方式は、非特許文献３と比較して、分散情報のサイズが小さいことを特徴とする。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Adi Shamir, "How to share a secret", Comm. ACM, 22(11), 612-613(1979)
【非特許文献２】T. Rabin and M. Ben-Or, "Verifiable Secret Sharing and Multiparty Protocols with Honest Majority," Proc. STOC'89, pp. 73--85.
【非特許文献３】K. Kurosawa, S. Obana and W. Ogata, "t-Cheater Identifiable (k,n) Threshold Secret Sharing Schemes," Proc. Crypto'95, Lecture Notes in Computer Science, vol. 963, Springer Verlag, pp. 410--423, 1995.
【非特許文献４】尾花, t人までの不正者を特定できる準最適な秘密分散法, 2007年 暗号と情報セキュリティシンポジウム
【発明の概要】
【発明が解決しようとする課題】
【００１４】
上述したような技術を用いることによって、秘密復元時に入力される分散情報のうち改竄されていない時点での分散情報を参照せずに分散情報を改竄する不正に対しては、安全性が保証される。
【００１５】
しかしながら、秘密復元に入力される改竄されていない時点での部分情報を参照した後で分散情報を改竄する、より強力な不正に対して安全な秘密分散法は従来一つも提案されていない。
【００１６】
本発明はこのような状況に鑑みてなされたものであり、本発明は、改竄されていない時点での他の分散情報を参照した後で分散情報を改竄する強力な不正に対しても不正の検知を行うことが可能な、秘密情報分散システム及び秘密情報分散方法並びに秘密情報生成プログラム及び秘密情報復元プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の第１の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、前記分散情報生成装置は、前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、前記ｎ個の記憶装置は前記分散情報生成装置の出力を記憶し、前記復元装置は、前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、ことを特徴とする秘密情報分散システムが提供される。
【００１８】
本発明の第２の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、前記分散情報生成装置が、前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、前記ｎ個の記憶装置が前記分散情報生成装置の出力を記憶し、前記復元装置が、前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、ことを特徴とする秘密情報分散方法が提供される。
【００１９】
本発明の第３の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラムが提供される。
【００２０】
本発明の第４の観点によれば、分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラムが提供される。
【発明の効果】
【００２１】
本発明によれば、正当な記憶装置に格納されているチェック用データｅは、独立かつ一様ランダムに選ばれており、且つ、非改竄性のチェックに用いる関数ｈは、知り得た値以外の関数値をεより高い確率で類推することができないという性質を有していることから、改竄されていない時点での他の分散情報を参照した後で分散情報を改竄する強力な不正に対しても不正の検知を行うことが可能となる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施形態に係る秘密情報分散システム全体の基本的構成を表すブロック図である。
【図２】本発明の実施形態に係る分散情報生成装置及び記憶装置の基本的構成を表すブロック図である。
【図３】本発明の実施形態に係る復元装置及び記憶装置の基本的構成を表す構成ブロック図である。
【図４】本発明の実施形態に係る分散情報生成装置及び復元装置が行う処理を実行する処理装置の基本的構成を表す構成ブロック図である。
【図５】本発明の第１の実施形態に係る分散情報生成装置の動作処理を表すフローチャートである。
【図６】本発明の第１の実施形態に係る復元装置の動作処理を表すフローチャートである。
【図７】本発明の第２の実施形態に係る分散情報生成装置の動作処理を表すフローチャートである。
【図８】本発明の第２の実施形態に係る復元装置の動作処理を表すフローチャートである。
【発明を実施するための形態】
【００２３】
次に、本発明の実施形態について図面を用いて詳細に説明する。なお、以下に述べる実施の形態は、本発明の好適な実施の形態として、技術的に好ましい種々の限定が付されている。しかし、だからといって、本発明の範囲は、以下の説明において特に本発明を限定する旨の記載がない限り、これらの態様に限られるものではない。すなわち、下述する実施形態は、本発明の好適な実施形態ではあるが、これらの実施形態のみに本発明の範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した形態での実施が可能である。
【００２４】
本実施形態を説明するにあたり、まず本明細書で使用する用語について簡単に説明する。
【００２５】
（ｋ，ｎ）閾値法：秘密情報をｎ個の分散情報に分散符号化し、そのうちの任意のｋ個の分散情報により、もとの秘密情報の復元が可能となる性質を有する秘密分散法を指す。なお、非特許文献１に（ｋ，ｎ）閾値法に関する記載がある。
【００２６】
秘密情報ｓ：保管対象となる秘密情報を指す。
【００２７】
秘密情報データ集合Ｓ：保管対象となる秘密情報ｓの集合を指す。
【００２８】
認証データａ：認証に用いる認証データを指す。
【００２９】
認証データ集合Ａ：認証データａの集合であり、チェック関数ｈの値域を指す。Ａの要素であるａを「ａ［ｉ］」と記述した場合は、当該ａが第ｉ番目の認証データであることを表すものとする。
【００３０】
分散情報データｖ：秘密情報ｓ∈Ｓを分散符号化したデータ（分散情報）のうちの１つを指す。
【００３１】
分散情報データＶ：秘密情報ｓ∈Ｓを分散符号化したデータ（分散情報）の集合を指す。Ｖの要素であるｖを「ｖ［ｉ］」と記述した場合は、当該ｖが第ｉ番目の分散情報を表すものとする。
【００３２】
チェック用データｅ：分散情報の非改竄性チェックに用いられるデータを指す。
【００３３】
チェック用データ集合Ｅ：分散情報の非改竄性チェックに用いられるデータ集合である。Ｅの要素であるｅを「ｅ［ｉ］」と記述した場合は、当該ｅは第ｉ番目のチェック用データを表すものとする。
【００３４】
演算子：本明細書において、それぞれ、「＋」の記号を和、「−」の記号を差、「＊」の記号を積、「＾」の記号を冪乗、の演算子として用いる。
【００３５】
［実施形態１］
図１は、本発明の実施形態に係る秘密情報分散システム全体の基本的構成を表す図である。図１を参照すると、秘密情報分散システムは、分散情報生成装置１００、復元装置２００及び複数の記憶装置３００−１〜３００−ｎを有する。
【００３６】
分散情報生成装置１００は、秘密情報ｓ１を受け付け、受け付けた秘密情報ｓ１に基づいて分散情報を生成する装置である。また、複数の記憶装置３００−１〜３００−ｎは、分散情報生成装置１００が生成した分散情報を記憶する装置である。更に、復元装置２００は、記憶装置３００−１〜３００−ｎが記憶する分散情報に基づいて復元を行う装置である。なお、図示の都合上、記憶装置３００−１、３００−２及び３００−ｎの３つが図示されているが、これはあくまで一例であり、任意の台数の記憶装置３００が存在していてよい。
【００３７】
本発明の実施形態に係る秘密情報分散システムが秘密情報を保管する場合には、分散情報生成装置１００が分散情報の非改竄性チェックに用いるチェック用データをランダムに生成し、（ｋ，ｎ）閾値法で生成した分散情報、チェック用データ、分散情報とチェック用データを用いて生成した認証データを記憶装置３００に格納する。
【００３８】
また、秘密情報を復元する場合には、ｋ個以上の記憶装置３００から分散符号化された秘密情報及びチェック用データ、認証データを復元装置２００の指定する順序に従って読み出す。
【００３９】
そして、各記憶装置内に格納されている分散情報とチェック用データが認証データと正しく対応しているかを判定し、全ての記憶装置３００に関して、正しく対応していることが検証できた場合は、復元した秘密情報が正しいと判断し秘密を出力し、対応していない場合は分散情報が改竄されていると判断する対応していない分散情報の識別子リストを出力する。
【００４０】
次に、図２を参照して分散情報生成装置１００の構成について詳細に説明する。
【００４１】
図２は分散情報生成装置１００の構成を表すブロック図である。図２に示すように、分散情報生成装置１００は、秘密情報分散部１０１、チェック用データ生成部１０２及び認証データ生成部１０３を有している。
【００４２】
秘密情報分散部１０１は、秘密情報ｓ１を入力とし、秘密情報ｓ１を（ｋ，ｎ）閾値法で分散符号化したｎ個のデータｖ［１］，ｖ［２］，．．．，ｖ［ｎ］（ｖ［ｉ］∈Ｖ）を記憶装置３００及び認証データ生成部１０３に対して出力する。
【００４３】
チェック用データ生成部１０２は、チェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を生成する。また、チェック用データ生成部１０２は、生成したチェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を記憶装置３００及び認証データ生成部１０３に対して出力する。
【００４４】
認証データ生成部１０３は、秘密情報分散部１０１の出力ｖ［ｉ］，．．．，ｖ［ｎ］と、チェック用データ生成部１０２の出力ｅ［１］，．．．，ｅ［ｎ］とを入力として、認証情報ａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎであり、ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］））を出力する。
【００４５】
本実施形態では、チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｋ−２］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｋ−２］，ａ’に対して、｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ’）＝ａ’，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝１，２，．．．，ｋ−２）｝｜／｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］｝｜≦εを任意のｉ，ｊ，ｌについて満足するものとする。
【００４６】
以上をまとめると、分散情報生成装置１００は秘密情報データ集合Ｓの元となる（すなわち集合Ｓの要素である）秘密情報ｓ１を入力とし、記憶装置３００−１〜３００−ｎ内の分散秘密情報記憶部３０１−１〜３０１−ｎに秘密情報分散部１０１の出力であるＶの元ｖ［１］〜ｖ［ｎ］を、チェック用データ記憶部３０２−１〜３０２−ｎにチェック用データ生成部１０２の出力であるＥの元ｅ［１］〜ｅ［ｎ］を、チェック用データ記憶部３０３−１〜３０３−ｎに認証データ集合Ａの元である認証データａ［１］〜ａ［ｎ］をそれぞれ格納する。
【００４７】
次に、図２を参照して記憶装置３００−１〜３００−ｎの構成について詳細に説明する。
【００４８】
記憶装置３００−１〜３００−ｎは、分散秘密情報記憶部３０１−１〜３０１−ｎ、チェック用データ記憶部３０２−１〜３０２−ｎ、認証データ記憶部３０３−１〜３０３−ｎ及びアクセス制御部３０４−１〜３０４−ｎを含んでいる。
【００４９】
分散秘密情報記憶部３０１−１〜３０１−ｎは、分散情報データ集合Ｖの元となる分散データｖが格納される記憶部である。
【００５０】
チェック用データ記憶部３０２−１〜３０２−ｎは、チェック用データ集合Ｅの元となるチェック用データｅが格納される記憶部である。
【００５１】
認証データ記憶部３０３−１〜３０３−ｎは、認証データ集合Ａの元となる認証データａが格納される記憶部である。
【００５２】
アクセス制御部３０４−１〜３０４−ｎは、復元装置２００内の読み出し制御部２０３からの信号に基づき、復元装置２００から読み出せるデータを制御する。
【００５３】
続いて、復元装置２００の構成について図３を用いて説明する。図３は復元装置２００の構成を表すブロック図である。
【００５４】
図３に示すように、復元装置２００は、秘密情報復元部２０１、不正情報特定部２０２及び読み出し制御部２０３を含んでいる。
【００５５】
秘密情報復元部２０１は複数の記憶装置３００が有する分散秘密情報記憶部３０１に格納されたデータを不正情報特定部２０２から読み出し、復元した秘密情報データｓ∈Ｓを出力する。
【００５６】
不正情報特定部２０２は、ｋ個以上の記憶装置３００が備える分散秘密情報記憶部３０１に格納された分散情報ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］と、チェック用データ記憶部３０２に格納されたチェック用データｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］と、認証データ記憶部３０３に格納された認証データａ［ｉ−１］，．．．，ｅ［ｉ−ｍ］（但し、各ａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］））を読み出す。そして、全てのｉ＝ｉ−１，．．．，ｉ−ｍと、ｉと相異なる全てのｊ＝ｉ−１，．．．，ｉ−ｍの内、ｋ／２個以上のｊに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するかどうかを判定する。そして、この判定の結果、全てのｊについて上式が成立するｉの個数が２／ｋ以上である場合は、分散情報に改竄がないものと判定し、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］を秘密情報復元部２０１に入力して得られる、復元された秘密情報ｓ∈Ｓを出力する。
【００５７】
一方、上式が成立するｉの個数が２／ｋ未満となるｊが存在する場合は、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立する個数がｋ／２未満であったｊのリストを改竄が生じた分散情報の識別子として出力する。
【００５８】
読み出し制御部２０３は、記憶装置３００−１〜３００−ｎ内のアクセス制御部３０４−１〜３０４−ｎに対して読み出したいデータを伝える制御信号を出力する。アクセス制御部３０４−１〜３０４−ｎは前記制御信号に基づき、復元装置２００にデータ読み出しの許可を与える。
【００５９】
以上説明した、図１、図２及び図３に表された分散情報生成装置１００及び復元装置２００は、任意の方法により実現することが可能である。
【００６０】
例えばハードウェアとして分散情報生成装置１００及び復元装置２００を実現するのであれば、論理回路等から構成されるＬＳＩ（Large Scale Integration）やＤＳＰ（Digital Signal Processor）等の半導体集積回路によって実現できる。
【００６１】
また、分散情報生成装置１００及び復元装置２００は、ハードウェア及びソフトウェアの組合せとしても実現可能である。例えば、図４に示すように、プログラムにしたがって所定の処理を実行する処理装置１０と、処理装置１０に対してコマンドや情報等を入力するための入力部２０と、処理装置１０の処理結果をモニタするための出力部３０とを含んだコンピュータによって分散情報生成装置１００及び復元装置２００を実現してもよい。この点について、以下詳細に説明する。
【００６２】
図４を参照すると処理装置１０は、ＣＰＵ１１と、主記憶部１２と、記録媒体１３と、データ蓄積部１４と、メモリ制御インタフェース部１５と、Ｉ／Ｏインタフェース部１６とを有する。これら各構成要素は、バス１８を介して相互に接続されている。
【００６３】
ＣＰＵ１１はプログラムに基づいて演算を行う演算処理装置である。主記憶部１２は、ＣＰＵ１１の演算処理に必要な情報を一時的に記憶する主記憶部である。
【００６４】
記録媒体１３は、ＣＰＵ１１に分散情報生成装置１００または復元装置２００としての処理を実行させるためのプログラムが記録された記録媒体である。処理装置１０は、記録媒体１３に記録されたプログラムに従って分散情報生成装置１００または復元装置２００としての機能を実現する。
【００６５】
データ蓄積部１４は、秘密情報やアクセス構造データが格納される補助記憶装置である。
【００６６】
なお、記録媒体１３及びデータ蓄積部１４は、任意の装置により実現可能である。記録媒体１３及びデータ蓄積部１４は、例えば、ＨＤＤ（Hard disk drive）やＦｌａｓｈ ＳＳＤ（Solid State Drive）により実現される。また、この記憶装置は処理装置１０内にある必要はなく、外部の記憶装置（図示を省略する）を利用するようにしてもよい。この場合記憶装置を別のコンピュータとして実現し、バスやＵＳＢ規格に準拠したケーブルや、インターネット等の手段を用いて接続するようにしてもよい。更に、単一の記憶装置により実現されてもよいが、複数の記憶装置の組合せにより実現されていてもよい。加えて、記録媒体１３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。例えば、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory）、ＤＶＤ（Digital Versatile Disc)、ＭＯ（Magneto Optical Disk(Disc)）ＢＤ（Blu-ray Disc）等であってもよい。加えて、データ蓄積部１４は、分散秘密情報記憶部３０１及びチェック用データ記憶部３０２及び認証用データ記憶部３０３を備える記憶装置３００として用いてもよい。すなわち、散情報生成装置１００、復元装置２００及び記憶装置３００は、複数のコンピュータで実現してもよく、単一のコンピュータで実現してもよい。
【００６７】
メモリ制御インタフェース部１５は、主記憶部１２、記録媒体１３及びデータ蓄積部１４とＣＰＵ１１等とのデータ転送を制御する。
【００６８】
次に本実施形態の秘密情報分散システムの動作について図５及び図６を参照して説明する。図５は分散情報生成装置１００の動作を示すフローチャートであり、図６は復元装置２００の動作を示すフローチャートである。
【００６９】
まず、分散情報生成部１００の秘密情報分散部１０１には、秘密情報データ集合Ｓの元である秘密情報ｓ１が入力される（ステップＡ４０１）。
【００７０】
分散情報生成装置１００は、秘密情報分散部１０１に秘密情報ｓ１が入力されると、秘密情報分散部１０１により秘密情報ｓ１を（ｋ，ｎ）閾値法により分散符号化し、生成されたｖ［ｉ］（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉの分散秘密情報記憶部３０１−ｉ及び認証データ生成部１０３に格納する（ステップＡ４０２）。
【００７１】
また、分散情報生成装置１００は、チェック用データ生成部１０２により、チェック用データｅ［ｉ］（ｉ＝１，．．．，ｎ）を生成し、生成したｅ［ｉ］を、記憶装置３００−ｉのチェック用データ記憶部３０２−ｉ及び認証データ生成部１０３に格納する（ステップＡ４０３）。
【００７２】
分散情報生成装置１００は、認証データ生成部１０３により、分散情報ｖ［ｉ］（ｉ＝１，．．．，ｎ）と、チェック用データｅ［ｊ］（ｊ＝１，．．．，ｎ，ｊ≠ｉ）に対して、ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］）を計算し、認証データａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を、記憶装置３００−ｉの認証データ記憶部３０３−ｉに格納する（ステップＡ４０４）。
【００７３】
図５に示すように、復元装置２００は、記憶装置３００のアクセス制御部３０４に分散秘密情報記憶部３０１、認証データ記憶部３０３のデータを読み出すことを示す制御信号を送り、ｋ個以上の記憶装置３００の分散秘密情報記憶部３０１と認証データ記憶部３０３から読み出した分散データｖ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ），認証情報ａ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＴ５０１）。
【００７４】
ステップＴ５０１でのデータ読み込み終了後、復元装置２００は、ステップＴ５０１で読み出した記憶装置３００と同じ記憶装置３００のアクセス制御部３０４に対してチェック用データ記憶部３０２のデータを読み出すことを示す制御信号を送り、当該記憶装置３００のチェック用データ記憶部３０２から読み出したチェック用データｅ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＴ５０２）。すなわちステップＴ５０１及びＴ５０２では同一であってｋ個以上の記憶装置３００から分散データｖ［ｉ］、認証情報ａ［ｉ］及びチェック用データｅ［ｉ］を読み込むこととなる。
【００７５】
ステップＴ５０１とステップＴ５０２でのデータ読み込み後、復元装置２００は、ステップＴ５０１，Ｔ５０２で読み込んだｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）とｊ≠ｉなるｊ（ｊ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）に対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するか否かを不正情報特定部２０２によりチェックする（ステップＴ５０３）。
【００７６】
ステップＴ５０３のチェックにより、全てのｊに対して、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するｉの個数が２／ｋ以上である場合は、秘密情報復元部２０１に読み込んだ全てのｖ［ｉ］を秘密情報復元部２０１に入力して得られる復元された秘密情報ｓ１を出力して終了（ステップＴ５０４においてＹｅｓ、ステップＴ５０５）。
【００７７】
一方、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するｉの個数が２／ｋ未満となるｊが存在する場合、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］が成立するｉの個数が２／ｋ未満となるｊのリストを改竄された分散情報の識別子として出力して終了する（ステップＴ５０４においてＮｏ、ステップＴ５０６）。
【００７８】
上記実施形態によれば、不正な記憶装置３００は、正当な記憶装置３００のチェック用データを読み出した後に改竄の検出が行えないように分散情報記憶部３０１のデータを改竄することは不可能になり、正当な記憶装置３００の送出する情報を参照した後に成功するようなデータを計算することができなくなるという効果を奏する。
【００７９】
［実施形態２］
次に、本発明の第２の実施形態について図面を参照して詳細に説明する。
【００８０】
実施形態２に係る秘密情報分散システムの基本的構成は図１、図２及び図３に表される実施形態１と同様であるため、その説明を省略する。
【００８１】
一方、実施形態２ではチェック用データ生成部１０２が、チェック用データｅ∈Ｅを生成する。そして、ｅを（ｔ，ｎ）閾値法で分散符号化する点において実施形態１と異なる。また、これに伴い復元装置２００での動作も異なる。よって、この点を中心として説明をする。そして、特に言及しない点においては実施形態１と同様であるとする。
【００８２】
まず、分散情報生成装置１００について説明する。
【００８３】
秘密情報分散部１０１は、秘密情報ｓ１を入力とし、秘密情報ｓ１を（ｋ，ｎ）閾値法で分散符号化したｎ個のデータｖ［１］，ｖ［２］，．．．，ｖ［ｎ］（ｖ［ｉ］∈Ｖ）を記憶装置３００及び認証データ生成部１０３に対して出力する。
【００８４】
本実施形態における、チェック用データ生成部１０２は、チェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を生成する。また、チェック用データ生成部１０２は、生成したチェック用データｅ［ｉ］∈Ｅ（ｉ＝１，．．．，ｎ）を記憶装置３００に対して出力する。
【００８５】
認証データ生成部は１０３、秘密情報分散部１０１の出力ｖ［ｉ］，．．．，ｖ［ｎ］と、チェック用データｅ、認証情報ａ［ｉ］＝ｈ（ｅ，ｖ［ｊ］）を出力する。
【００８６】
本実施形態では、チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｔ−１］，ａ’に対して、｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ’）＝ａ’，ｈ（ｅ，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝ｔ−１）｝｜／｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ［ｌ］）＝ａ［ｌ］｝｜≦εを任意のｉ，ｊ，ｌについて満足するものとする。
【００８７】
以上をまとめると、分散情報生成装置１００は秘密情報データ集合Ｓの元となる（すなわち集合Ｓの要素である）秘密情報ｓ１を入力とし、記憶装置３００−１〜３００−ｎ内の分散秘密情報記憶部３０１−１〜３０１−ｎに秘密情報分散部の出力であるＶの元ｖ［１］〜ｖ［ｎ］を、チェック用データ記憶部３０２−１〜３０２−ｎにチェック用データ生成部１０２の出力ｅ［１］〜ｅ［ｎ］を、チェック用データ記憶部３０３−１〜３０３−ｎに認証データ集合Ａの元である認証データａ［１］〜ａ［ｎ］をそれぞれ格納する。
【００８８】
また、本実施形態の記憶装置３００−１〜３００−ｎは、分散情報データ集合Ｖの元が格納される分散情報記憶部３０１−１〜３０１−ｎと、チェック用データ集合Ｅの元が格納されるチェック用データ記憶部３０２−１〜３０２−ｎと、認証データ集合Ａの元が格納される認証データ記憶部３０３−１〜３０３−ｎと、復元装置２００内の読み出し制御部からの信号に基づき、復元装置２００から読み出せるデータを制御するアクセス制御部３０４−１〜３０４−ｎとを含んでいる。
【００８９】
次に、本実施形態の復元装置２００の構成について説明する。図３は復元装置２００の構成ブロック図である。図３に示すように、復元装置２００は、秘密情報復元部２０１、不正情報特定部２０２、及び読み出し制御部２０３を備えている。
【００９０】
秘密情報復元部２０１は複数の記憶装置３００が備える分散秘密情報記憶部３０１に格納されたデータ不正情報特定部２０２からを読み出し、復元した秘密情報データｓ∈Ｓを出力する。
【００９１】
不正情報特定部２０２は、ｋ個以上の記憶装置３００が備える分散秘密情報記憶部３０１に格納された分散情報ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］と、チェック用データ記憶部３０２に格納されたチェック用データｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］と、認証データ記憶部３０３に格納された認証データａ［ｉ−１］，．．．，ａ［ｉ−ｍ］を読み出す。そして、ｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からｅの復元を行った後、全てのｉ＝ｉ−１，．．．，ｉ−ｍに対し、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立するかどうかを判定する。そして、この判定の結果、全てのｉについて上式が成立する時は分散情報に改竄がないものと判定し、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］を秘密情報復元部２０１に入力して得られる、復元した秘密情報ｓ∈Ｓを出力する。
【００９２】
一方、上式が成立しない時はｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立しないｉのリストを改竄が生じた分散情報の識別子として出力する。
【００９３】
このとき、ｅは（ｔ，ｎ）閾値秘密分散の分散情報であるためｍ≧ｋとなるｍ個のｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からｔ個の改竄されたｅ［ｉ−ｊ］の誤りを訂正し、正しいｅが復元できることが知られている。
【００９４】
読み出し制御部２０３は、記憶装置３００−１〜３００−ｎ内のアクセス制御部３０４−１〜３０４−ｎに対して読み出したいデータを伝える制御信号を出力する。アクセス制御部３０４−１〜３０４−ｎは前記制御信号に基づき、復元装置２００にデータ読み出しの許可を与える。
【００９５】
なお、本実施形態は実施形態１と同様、分散情報生成装置１００及び復元装置２００を半導体集積回路によって実現できる。また、本実施形態は実施形態１と同様、分散情報生成装置１００及び復元装置２００を図４に表されるような処理装置１０により実現できる。なお具体的な実現方法は、実施形態１の説明において上述した内容と同様である。
【００９６】
次に本実施形態の秘密情報分散システムの動作について図７及び図８を参照して説明する。図７は分散情報生成装置１００の動作を示すフローチャートであり、図８は復元装置２００の動作を示すフローチャートである。
【００９７】
まず、分散情報生成部１００の秘密情報分散部１０１には、秘密情報データ集合Ｓの元である秘密情報ｓ１が入力される（ステップＵ６０１）。
【００９８】
分散情報生成装置１００は、秘密情報分散部１０１に秘密情報ｓ１が入力されると、秘密情報分散部１０１により秘密情報ｓ１を（ｋ，ｎ）閾値法により分散符号化し、生成されたｖ［ｉ］（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉの分散秘密情報記憶部３０１−ｉ及び認証データ生成部１０３に格納する（ステップＵ６０２）。
【００９９】
また、分散情報生成装置１００は、チェック用データ生成部１０２により、チェック用データｅを生成し、ｅを（ｔ，ｎ）閾値法で分散符号化したｅ［ｉ］（ｉ＝１，．．．，ｎ）を生成し、生成したｅ［ｉ］を、記憶装置３００−ｉのチェック用データ記憶部３０２−ｉに格納する（ステップＵ６０３）。
【０１００】
分散情報生成装置１００は、認証データ生成部１０３により、分散情報ｖ［ｉ］（ｉ＝１，．．．，ｎ）と、チェック用データ生成部１０２が生成したチェック用データｅに対して、ａ［ｉ］＝ｈ（ｅ，ｖ［ｉ］）を計算し、認証データａ［ｉ］（ｉ＝１，．．．，ｎ）を、記憶装置３００−ｉの認証データ記憶部３０３−ｉに格納する（ステップＵ６０４）。
【０１０１】
図７に示すように、復元装置２００は、記憶装置３００のアクセス制御部３０４に分散秘密情報記憶部３０１、認証データ記憶部３０３のデータを読み出すことを示す制御信号を送り、ｋ個以上の記憶装置３００の分散秘密情報記憶部３０１と認証データ記憶部３０３から読み出した分散データｖ［ｉ］，認証情報ａ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＷ７０１）。
【０１０２】
ステップＷ７０１でのデータ読み込み終了後、復元装置２００は、ステップＷ７０１で読み出した記憶装置３００と同じ記憶装置３００のアクセス制御部３０４に対してチェック用データ記憶部３０２のデータを読み出すことを示す制御信号を送り、当該記憶装置３００のチェック用データ記憶部３０２から読み出したチェック用データｅ［ｉ］（ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）を不正情報特定部２０２に入力する（ステップＷ７０２）。すなわちステップＷ７０１及びＷ７０２では同一であってｋ個以上の記憶装置３００から分散データｖ［ｉ］、認証情報ａ［ｉ］及びチェック用データｅ［ｉ］を読み込むこととなる。
【０１０３】
ステップＷ７０１とステップＷ７０２でのデータ読み込み後、復元装置２００は、ステップＷ７０１，Ｗ７０２で読み込んだｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］から、ｅの復元を行い、ｉ＝ｉ−１，ｉ−２，．．．，ｉ−ｍ）に対し、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立するか否かを不正情報特定部２０２によりチェックする（ステップＷ７０３）。
【０１０４】
ステップＷ７０３のチェックにより、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立する場合は、秘密情報復元部２０１に読み込んだ全てのｖ［ｉ］を秘密情報復元部２０１に入力して得られる復元された秘密情報ｓ１を出力して終了する（ステップＷ７０４においてＹｅｓ、ステップＷ７０５）。
【０１０５】
一方、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立しないｉが存在する場合、ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］が成立しないｉのリストを改竄された分散情報の識別子として出力して終了する（ステップＷ７０４においてＮｏ、ステップＷ７０６）。
【０１０６】
上記実施形態によれば、不正な記憶装置３００は、正当な記憶装置３００のチェック用データを読み出した後に改竄の検出が行えないように分散情報記憶部３０１のデータを改竄することは不可能になり、正当な記憶装置３００の送出する情報を参照した後に成功するようなデータを計算することができなくなるという効果を奏する。
【０１０７】
次に、上述した各実施形態をより具体的に説明した例である、本発明の実施例について説明する。
【実施例１】
【０１０８】
実施例１は、上述した実施形態１に対応する実施例である。本実施例におけるに秘密情報分散システムは、秘密情報ｓのデータ集合にＧＦ（ｐ）（ｐ：素数冪，ＧＦ：ガロア体）を、チェック用データｅ［ｉ］＝（ｅ［ｉ，１］，．．．，ｅ［ｉ，ｉ−１］，ｅ［ｉ，ｉ＋１］，ｅ［ｉ，ｎ］）（但し、ｅ［ｉ，ｊ］＝（ｅ［ｉ，ｊ］｛０｝，ｅ［ｉ，ｊ］｛１｝）），ｅ［ｉ，ｊ］｛ｂ｝はＧＦ（ｐ）の元）として、認証用データとしてａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）を用いる。
【０１０９】
次に本実施例に係る分散情報生成装置１００及び復元装置２００について説明する。本実施例に係る分散情報生成装置１００には、秘密情報ｓ∈ＧＦ（ｐ）が入力される。
【０１１０】
分散情報生成装置１００は、秘密情報ｓが入力されると、秘密情報分散部１０１によりＧＦ（ｐ）上の定数項がｓであるｋ−１次多項式をランダムに生成する。このｋ−１次多項式をｆ−ｓ（ｘ）と記す。
【０１１１】
秘密情報分散部１０１は、相異なる１，２，．．．，ｎに対して、ｖ［１］＝ｆ−ｓ（１），ｖ［２］＝ｆ−ｓ（２），…，ｖ［ｎ］＝ｆ−ｓ（ｎ）を計算し、その計算結果を記憶装置３００−１の分散秘密情報記憶部３０１−１、記憶装置３００−２の分散秘密情報記憶部３０１−２，…，記憶装置３００−ｎの分散秘密情報記憶部３０１−ｎにそれぞれ格納する。
【０１１２】
チェック用データ生成部１０２は、ＧＦ（ｐ）の元であるｅ［ｉ，ｊ］｛ｂ｝（ｉ＝１，．．．，ｎ，ｊ＝１，．．．，ｎ，ｂ＝０，１，ｊ≠ｉ）をランダムに生成し、ｅ［ｉ］（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉのチェック用データ記憶部３０２−ｉに格納する。
【０１１３】
次に、認証データ生成部１０３は、ａ［ｉ，ｊ］＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝を計算し、ａ［ｉ］＝（ａ［ｉ，１］，．．．，ａ［ｉ，ｉ−１］，ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉの認証データ記憶部３０３−ｉにそれぞれ格納する。
【０１１４】
一方、本実施例に係る復元装置２００は、まず、分散情報と認証データの読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各分散秘密情報記憶部３０１と各認証データ記憶部３０３とからデータｖ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を読み出す。
【０１１５】
次に、復元装置２００は、乱数分散情報の読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｋ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，…，３００−［ｉ−ｋ］の各チェック用データ記憶部３０２からデータｅ［ｉ］を読み出す。
【０１１６】
不正情報特定部２０２は、ｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を入力とし、全てのｉ＝ｉ−１，．．．，ｉ−ｍと、ｉとは相異なるｊ＝ｉ−１，．．．，ｉ−ｍについてａ［ｉ，ｊ］＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝が成立するか否かをチェックし、全てのｉについて上式が成立するｊの個数が２／ｋ以上であった場合は、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］からラグランジュ補完などの手段によって秘密情報ｓを計算して出力する。一方、成立していない場合は上式が成立するｊが２／ｋ未満となったｊのリストを改竄された分散情報の識別子として出力する。
【０１１７】
本実施例に係る秘密情報分散システムでは、ｋ／２未満の改竄された分散情報を確率１−１／ｐで特定することができるという効果を奏する。
【実施例２】
【０１１８】
実施例２は、上述した実施形態２に対応する実施例である。本実施例におけるに秘密情報分散システムは、秘密情報ｓのデータ集合にＧＦ（ｐ）（ｐ：素数冪，ＧＦ：ガロア体）を、チェック用データｅ＝（ｅ｛０｝，ｅ｛１｝，．．．，ｅ｛ｔ｝）としてＧＦ（ｑ）＾（ｔ＋１）の元（但し、ｑはｐ×ｎ以上の素数）、認証用データとしてＧＦ（ｑ）の元ａ［ｉ］を用いる。
【０１１９】
次に本実施例に係る分散情報生成装置１００及び復元装置２００について説明する。本実施例に係る分散情報生成装置１００には、秘密情報ｓ∈ＧＦ（ｐ）が入力される。
【０１２０】
分散情報生成装置１００は、秘密情報ｓが入力されると、秘密情報分散部１０１によりＧＦ（ｐ）上の定数項がｓであるｋ−１次多項式をランダムに生成する。このｋ−１次多項式をｆ−ｓ（ｘ）と記す。
【０１２１】
秘密情報分散部１０１は、相異なる１，２，．．．，ｎに対して、ｖ［１］＝ｆ−ｓ（１），ｖ［２］＝ｆ−ｓ（２），…，ｖ［ｎ］＝ｆ−ｓ（ｎ）を計算し、その計算結果を記憶装置３００−１の分散秘密情報記憶部３０１−１、記憶装置３００−２の分散秘密情報記憶部３０１−２，…，記憶装置３００−ｎの分散秘密情報記憶部３０１−ｎにそれぞれ格納する。
【０１２２】
チェック用データ生成部１０２は、ＧＦ（ｑ）の元であるｅをランダムに生成し、ｆ−ｅ（０）＝ｅとなるｔ次多項式ｆ−ｅ（ｘ）をランダムに生成、ｅ［ｉ］＝ｆ−ｅ（ｉ）（ｉ＝１，．．．，ｎ）を記憶装置３００−ｉのチェック用データ記憶部３０２−ｉに格納する。
【０１２３】
次に、認証データ生成部１０３は、ａ［ｉ］＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛２｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｊ］＾ｔ）を計算し、記憶装置３００−ｉの認証データ記憶部３０３−ｉにそれぞれ格納する。（但し、ψ（ｖ［ｉ］）はψ（ｖ［ｉ］）＝ｐ＊（ｉ−１）＋ｖ［ｉ］で定義される関数）
一方、本実施例に係る復元装置２００は、まず、分散情報と認証データの読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｍ］の各分散秘密情報記憶部３０１と各認証データ記憶部３０３とからデータｖ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を読み出す。
【０１２４】
次に、復元装置２００は、乱数分散情報の読み出しを行う制御信号を読み出し制御部２０３から記憶装置３００−［ｉ−１］，３００−［ｉ−２］，．．．，３００−［ｉ−ｋ］の各アクセス制御部３０４に送出し、記憶装置３００−［ｉ−１］，３００−［ｉ−２］，…，３００−［ｉ−ｋ］の各チェック用データ記憶部３０２からデータｅ［ｉ］を読み出す。
【０１２５】
不正情報特定部２０２は、ｖ［ｉ］，ｅ［ｉ］，ａ［ｉ］（ｉ＝ｉ−１，．．．，ｉ−ｍ）を入力とし、ｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］からバーレカンプマッシー法（Berlekamp-Massey algorithm）やユークリッド法（Euclidean algorithm）などの誤り訂正符号の復号法を利用して正しいｅを復元する。そして、ａ［ｉ］＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛２｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｊ］＾ｔ）が成立するか否かをチェックし、全てのｉについて上式が成立する場合は、ｖ［ｉ−１］，．．．，ｖ［ｉ−ｍ］からラグランジュ補完などの手段によって秘密情報ｓを計算して出力し、成立しないｉが存在する場合には、そのｉのリストを改竄された分散情報の識別子として出力する。
【０１２６】
本実施例に係る秘密情報分散システムでは、ｋ／２未満の改竄された分散情報を確率１−１／ｐで特定することができる。
【０１２７】
以上、本発明を好適な実施形態及び好適な実施例に基づき具体的に説明したが、本発明は上記のものに限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【０１２８】
以上説明した本発明の実施形態は、以下に示すような効果を奏する。
【０１２９】
本発明の実施形態によれば、部分情報の改竄を行う記憶装置は、プロトコルに従ってまず最初に改竄した分散情報と認証データを復元装置に渡す必要がある。このとき、部分情報の改竄を行う記憶装置は、改竄を行っていない正当な記憶装置に格納されているチェック用データの値を参照することができない。正当な記憶装置に格納されているチェック用データｅは、独立かつ一様ランダムに選ばれており、また、非改竄性のチェックに用いる関数ｈは、知り得た値以外の関数値をεより高い確率で類推することができないという性質を有している。従って、仮に改竄を行う記憶装置が記憶装置に格納されている複数の分散情報と認証データを参照し、不正情報特定装置に特定されない形で改竄を行った場合でも、不正情報特定装置が偽造を特定できない確率はε以下となることが保証されるという効果を奏する。
【０１３０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１３１】
上記目的を達成するため本発明の分散情報生成装置は、秘密情報を入力とし、前記秘密情報を（ｋ，ｎ）閾値法で分散符号化した分散情報を出力する秘密情報分散装置と、前記秘密情報の検証を行うチェック用データを生成するチェック用データ生成装置と、前記分散情報と、チェック用データとを入力とし、予め定められたチェック関数ｈに入力して得られる出力から認証データを生成する認証データ生成装置とを有する。
【０１３２】
また、本発明の復元装置は、ｋ個以上の前記記憶装置から分散符号化された分散秘密情報を読み出し、秘密情報の復元を行う秘密情報復元装置と、ｋ個以上の前記記憶装置から分散情報と、チェック用データと、認証データとを読み出し、分散情報の正当性チェックを行い、改竄された分散情報が存在する場合には、改竄された分散秘密情報の識別子リストを出力し、改竄された分散情報が存在しない場合には、復元された秘密情報を出力する不正情報特定装置と、前記記憶装置から読み出す情報の順序を制御する読み出し制御装置を有する。
【０１３３】
上記のような構成を採り、読み出し制御装置の指定する順序に従い、秘密の復元に参加する全ての記憶装置から、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する全ての記憶装置から、チェック用データ記憶装置を読み出すこととする。また、関数ｈを、複数の関数値ｈ（ｅ，ｖ）が分かった場合でも、同じチェックデータｅに対する知り得た値以外のｖ’に関する関数値ｈ（ｅ，ｖ’）の値を低い確率εでしか類推できない特徴を有するものの中から選択する。
【０１３４】
（付記１） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、
前記分散情報生成装置は、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置は前記分散情報生成装置の出力を記憶し、
前記復元装置は、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散システム。
【０１３５】
（付記２） 付記１に記載の秘密情報分散システムであって、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［１］，．．．，ｅ［ｎ］とを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］）（ｉ≠ｊ）からｎ個の認証データａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］），ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、チェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、全ての可能な相異なるｉ，ｊ（ｉ，ｊ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］」なる式が成立するか否かを判定し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］が存在する場合は、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］がそのようなｖ［ｊ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’（ｔ≧ｋ／２）と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｋ−２］，ａ’に対して、｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ’）＝ａ’，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］｝（ｌ＝１，２，．．．，ｔ−１）｜≦εを任意のｉ，ｊ，ｌについて満足することを特徴とする秘密情報分散システム。
【０１３６】
（付記３） 付記１又は２に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［ｉ］＝（ｅ［ｉ，１］，ｅ［ｉ，２］，．．．，ｅ［ｉ，ｉ−１］，ｅ［ｉ，ｉ＋１］，ｅ［ｉ，ｉ＋２］，．．．，ｅ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ、但し、各ｅ［ｉ，ｊ］＝（ｅ［ｉ，ｊ］｛０｝，ｅ［ｉ，ｊ］｛１｝））（ｉ＝１，．．．，ｎ）とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝によって定義されることを特徴とする秘密情報分散システム。
【０１３７】
（付記４） 付記１に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、前記チェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅを前記記憶装置に出力し、
前記復元装置は、前記（ｔ，ｎ）閾値秘密分散法で分散符号化されたチェック用データｅを更に用いて前記分散情報の正当性の判定を行うことを特徴とする秘密情報分散システム。
【０１３８】
（付記５） 付記４に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うチェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅとを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ］＝ｈ（ｅ，ｖ［ｉ］）（ｉ＝１，．．．，ｎ）を認証データとして出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、分散符号化されたチェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、ｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からチェック用データｅを復元し、全てのｉ（ｉ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｍ）」なる式が成立するか否かをチェックし、前記式が成立しなかったｖ［ｉ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、そのようなｖ［ｉ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｔ−１］，ａ’に対して、｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ’）＝ａ’，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１｝｜≦εを任意のｉについて満足することを特徴とする
秘密情報分散システム。
【０１３９】
（付記６） 付記４又は５に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ＝（ｅ｛０｝，ｅ｛１｝，．．．，ｅ｛ｔ｝）と、ｐ≧ｎとなる任意の素数と、関数ψ（ｖ［ｉ］）＝ｐ×（ｉ−１）＋ｖ［ｉ］とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛３｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｉ］）＾ｔによって定義されることを特徴とする秘密情報分散システム。
【０１４０】
（付記７） 付記１乃至６の何れか１に記載の秘密情報分散システムにおいて、
前記記憶装置は、
当該各記憶装置に格納されている情報を前記復元装置に送信するタイミングを制御するアクセス制御手段を更に備え、
前記復元装置は、
前記記憶装置から読み出す情報の順序を制御する読み出し制御手段を更に備え、
前記復元装置は前記読み出し制御装置の指定する順序に従い、秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、チェック用データ記憶装置を読み出すことを特徴とする秘密情報分散システム。
【０１４１】
（付記８） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、
前記分散情報生成装置が、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置が前記分散情報生成装置の出力を記憶し、
前記復元装置が、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散方法。
【０１４２】
（付記９） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラム。
【０１４３】
（付記１０） 分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラム。
【０１４４】
上記の実施形態の一部又は全部は、更に以下のようにも記載されうるが、以下には限られない。
【０１４５】
上記目的を達成するため本発明の分散情報生成装置は、秘密情報を入力とし、前記秘密情報を（ｋ，ｎ）閾値法で分散符号化した分散情報を出力する秘密情報分散装置と、前記秘密情報の検証を行うチェック用データを生成するチェック用データ生成装置と、前記分散情報と、チェック用データとを入力とし、予め定められたチェック関数ｈに入力して得られる出力から認証データを生成する認証データ生成装置とを有する。
【０１４６】
また、本発明の復元装置は、ｋ個以上の前記記憶装置から分散符号化された分散秘密情報を読み出し、秘密情報の復元を行う秘密情報復元装置と、ｋ個以上の前記記憶装置から分散情報と、チェック用データと、認証データとを読み出し、分散情報の正当性チェックを行い、改竄された分散情報が存在する場合には、改竄された分散秘密情報の識別子リストを出力し、改竄された分散情報が存在しない場合には、復元された秘密情報を出力する不正情報特定装置と、前記記憶装置から読み出す情報の順序を制御する読み出し制御装置を有する。
【０１４７】
上記のような構成を採り、読み出し制御装置の指定する順序に従い、秘密の復元に参加する全ての記憶装置から、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する全ての記憶装置から、チェック用データ記憶装置を読み出すこととする。また、関数ｈを、複数の関数値ｈ（ｅ，ｖ）が分かった場合でも、同じチェックデータｅに対する知り得た値以外のｖ’に関する関数値ｈ（ｅ，ｖ’）の値を低い確率εでしか類推できない特徴を有するものの中から選択する。
【符号の説明】
【０１４８】
１０ 処理装置
１１ ＣＰＵ
１２ 主記憶部
１３ 記録媒体
１４ データ蓄積部
１５ メモリ制御インタフェース部
１６ Ｉ／Ｏインタフェース部
１００ 分散情報生成装置
１０１ 秘密情報分散部
１０２ チェック用データ生成部
１０３ 認証データ部
２００ 復元装置
２０１ 秘密情報復元部
２０２ 不正情報特定部
２０３ 読み出し制御部
３００−１〜３００−ｎ記憶装置
３０１−１〜３０１−ｎ 分散秘密情報記憶部
３０２−１〜３０２−ｎ チェック用データ記憶部
３０３−１〜３０３−ｎ 認証データ記憶部
３０４−１〜３０４−ｎ アクセス制御部
【特許請求の範囲】
【請求項１】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、
前記分散情報生成装置は、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置は前記分散情報生成装置の出力を記憶し、
前記復元装置は、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散システム。
【請求項２】
請求項１に記載の秘密情報分散システムであって、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［１］，．．．，ｅ［ｎ］とを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］）（ｉ≠ｊ）からｎ個の認証データａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］），ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、チェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、全ての可能な相異なるｉ，ｊ（ｉ，ｊ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］」なる式が成立するか否かを判定し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］が存在する場合は、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］がそのようなｖ［ｊ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’（ｔ≧ｋ／２）と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｋ−２］，ａ’に対して、｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ’）＝ａ’，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］｝（ｌ＝１，２，．．．，ｔ−１）｜≦εを任意のｉ，ｊ，ｌについて満足することを特徴とする秘密情報分散システム。
【請求項３】
請求項１又は２に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［ｉ］＝（ｅ［ｉ，１］，ｅ［ｉ，２］，．．．，ｅ［ｉ，ｉ−１］，ｅ［ｉ，ｉ＋１］，ｅ［ｉ，ｉ＋２］，．．．，ｅ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ、但し、各ｅ［ｉ，ｊ］＝（ｅ［ｉ，ｊ］｛０｝，ｅ［ｉ，ｊ］｛１｝））（ｉ＝１，．．．，ｎ）とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝によって定義されることを特徴とする秘密情報分散システム。
【請求項４】
請求項１に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、前記チェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅを前記記憶装置に出力し、
前記復元装置は、前記（ｔ，ｎ）閾値秘密分散法で分散符号化されたチェック用データｅを更に用いて前記分散情報の正当性の判定を行うことを特徴とする秘密情報分散システム。
【請求項５】
請求項４に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うチェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅとを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ］＝ｈ（ｅ，ｖ［ｉ］）（ｉ＝１，．．．，ｎ）を認証データとして出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、分散符号化されたチェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、ｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からチェック用データｅを復元し、全てのｉ（ｉ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｍ）」なる式が成立するか否かをチェックし、前記式が成立しなかったｖ［ｉ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、そのようなｖ［ｉ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｔ−１］，ａ’に対して、｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ’）＝ａ’，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１｝｜≦εを任意のｉについて満足することを特徴とする
秘密情報分散システム。
【請求項６】
請求項４又は５に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ＝（ｅ｛０｝，ｅ｛１｝，．．．，ｅ｛ｔ｝）と、ｐ≧ｎとなる任意の素数と、関数ψ（ｖ［ｉ］）＝ｐ×（ｉ−１）＋ｖ［ｉ］とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛３｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｉ］）＾ｔによって定義されることを特徴とする秘密情報分散システム。
【請求項７】
請求項１乃至６の何れか１項に記載の秘密情報分散システムにおいて、
前記記憶装置は、
当該各記憶装置に格納されている情報を前記復元装置に送信するタイミングを制御するアクセス制御手段を更に備え、
前記復元装置は、
前記記憶装置から読み出す情報の順序を制御する読み出し制御手段を更に備え、
前記復元装置は前記読み出し制御装置の指定する順序に従い、秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、チェック用データ記憶装置を読み出すことを特徴とする秘密情報分散システム。
【請求項８】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、
前記分散情報生成装置が、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置が前記分散情報生成装置の出力を記憶し、
前記復元装置が、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散方法。
【請求項９】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラム。
【請求項１０】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラム。
【請求項１】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムであって、
前記分散情報生成装置は、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置は前記分散情報生成装置の出力を記憶し、
前記復元装置は、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散システム。
【請求項２】
請求項１に記載の秘密情報分散システムであって、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［１］，．．．，ｅ［ｎ］とを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ，ｊ］＝ｈ（ｅ［ｉ］，ｖ［ｊ］）（ｉ≠ｊ）からｎ個の認証データａ［ｉ］＝（ａ［ｉ，１］，ａ［ｉ，２］，．．．，ａ［ｉ，ｉ−１］），ａ［ｉ，ｉ＋１］，．．．，ａ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ）を出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、チェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、全ての可能な相異なるｉ，ｊ（ｉ，ｊ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ａ［ｉ，ｊ］」なる式が成立するか否かを判定し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］が存在する場合は、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、当該判定の結果、ｋ／２個以上のｅ［ｉ］に対して前記式が成立しなかったｖ［ｊ］がそのようなｖ［ｊ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’（ｔ≧ｋ／２）と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｋ−２］，ａ’に対して、｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ’）＝ａ’，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］（ｌ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ［ｊ］｜ｈ（ｅ［ｊ］，ｖ）＝ａ，ｈ（ｅ［ｊ］，ｖ［ｌ］）＝ａ［ｌ］｝（ｌ＝１，２，．．．，ｔ−１）｜≦εを任意のｉ，ｊ，ｌについて満足することを特徴とする秘密情報分散システム。
【請求項３】
請求項１又は２に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ［ｉ］＝（ｅ［ｉ，１］，ｅ［ｉ，２］，．．．，ｅ［ｉ，ｉ−１］，ｅ［ｉ，ｉ＋１］，ｅ［ｉ，ｉ＋２］，．．．，ｅ［ｉ，ｎ］）（ｉ＝１，．．．，ｎ、但し、各ｅ［ｉ，ｊ］＝（ｅ［ｉ，ｊ］｛０｝，ｅ［ｉ，ｊ］｛１｝））（ｉ＝１，．．．，ｎ）とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ［ｉ，ｊ］｛１｝×ｖ［ｊ］＋ｅ［ｉ，ｊ］｛０｝によって定義されることを特徴とする秘密情報分散システム。
【請求項４】
請求項１に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、前記チェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅを前記記憶装置に出力し、
前記復元装置は、前記（ｔ，ｎ）閾値秘密分散法で分散符号化されたチェック用データｅを更に用いて前記分散情報の正当性の判定を行うことを特徴とする秘密情報分散システム。
【請求項５】
請求項４に記載の秘密情報分散システムにおいて、
前記分散情報生成装置は、
秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化し、ｎ個の分散情報ｖ［１］，ｖ［２］，．．．，ｖ［ｎ］を生成する秘密情報分散手段と、
前記秘密情報の検証を行うチェック用データｅを（ｔ，ｎ）閾値秘密分散法で分散符号化したｎ個のチェック用データｅ［１］，ｅ［２］，．．．，ｅ［ｎ］を生成するチェック用データ生成手段と、
前記分散情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅとを入力とし、予め定められたチェック関数ｈに入力して得られる出力ａ［ｉ］＝ｈ（ｅ，ｖ［ｉ］）（ｉ＝１，．．．，ｎ）を認証データとして出力する認証データ生成手段とを備え、
前記記憶装置は、
前記分散情報生成装置が生成した分散符号化された前記分散情報ｖ［ｉ］を格納する分散秘密情報記憶手段と、
前記チェック用データ生成装置が生成した前記チェック用データｅ［ｉ］を格納するチェック用データ記憶手段と、
前記認証データ生成装置が生成した前記認証データａ［ｉ］を格納する認証データ記憶手段とを備え、
前記復元装置は、
ｋ個以上の前記記憶装置から分散符号化された分散情報を読み出し、秘密情報の復元を行う秘密情報復元手段と、
ｋ個以上の前記記憶装置から分散情報ｖ［ｉ−１］，ｖ［ｉ−２］，．．．，ｖ［ｉ−ｍ］と、分散符号化されたチェック用データｅ［ｉ−１］，ｅ［ｉ−２］，．．．，ｅ［ｉ−ｍ］と、認証データａ［ｉ−１］，ａ［ｉ−２］，．．．，ａ［ｉ−ｍ］とを読み出し、ｅ［ｉ−１］，．．．，ｅ［ｉ−ｍ］からチェック用データｅを復元し、全てのｉ（ｉ＝ｉ−１，．．．，ｉ−ｍ）に対して、「ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｍ）」なる式が成立するか否かをチェックし、前記式が成立しなかったｖ［ｉ］の識別子集合｛ｉ−ｊ１，ｉ−ｊ２，．．．，ｉ−ｊｗ｝を出力し、そのようなｖ［ｉ］が存在しない場合は、復元した秘密情報ｓを出力する不正情報特定手段とを備え、
前記チェック関数ｈ（ｈ：Ｅ×Ｖ→Ａ）は、集合Ｖの任意の要素ｖ［１］，ｖ［２］，．．．，ｖ［ｔ−１］，ｖ，ｖ’と、集合Ａの任意の要素ａ［１］，ａ［２］，．．．，ａ［ｔ−１］，ａ’に対して、｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ’）＝ａ’，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１）｝｜／｜｛ｅ｜ｈ（ｅ，ｖ）＝ａ，ｈ（ｅ，ｖ［ｉ］）＝ａ［ｉ］（ｉ＝１，２，．．．，ｔ−１｝｜≦εを任意のｉについて満足することを特徴とする
秘密情報分散システム。
【請求項６】
請求項４又は５に記載の秘密情報分散システムにおいて、
チェック関数ｈが、ｎ個の部分情報ｖ［１］，．．．，ｖ［ｎ］と、チェック用データｅ＝（ｅ｛０｝，ｅ｛１｝，．．．，ｅ｛ｔ｝）と、ｐ≧ｎとなる任意の素数と、関数ψ（ｖ［ｉ］）＝ｐ×（ｉ−１）＋ｖ［ｉ］とに対し、ｈ（ｅ［ｉ］，ｖ［ｊ］）＝ｅ｛０｝＋ｅ｛１｝×ψ（ｖ［ｉ］）＋ｅ｛３｝×ψ（ｖ［ｉ］）＾２＋．．．＋ｅ｛ｔ｝×ψ（ｖ［ｉ］）＾ｔによって定義されることを特徴とする秘密情報分散システム。
【請求項７】
請求項１乃至６の何れか１項に記載の秘密情報分散システムにおいて、
前記記憶装置は、
当該各記憶装置に格納されている情報を前記復元装置に送信するタイミングを制御するアクセス制御手段を更に備え、
前記復元装置は、
前記記憶装置から読み出す情報の順序を制御する読み出し制御手段を更に備え、
前記復元装置は前記読み出し制御装置の指定する順序に従い、秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、まず始めに分散秘密情報記憶装置および認証データ記憶装置に格納されている情報を読み出し、その後に、前記秘密の復元に参加する前記ｋ個以上の記憶装置の全てから、チェック用データ記憶装置を読み出すことを特徴とする秘密情報分散システム。
【請求項８】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備えたシステムが行う、秘密情報を分散して保管する秘密情報分散方法であって、
前記分散情報生成装置が、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力し、
前記ｎ個の記憶装置が前記分散情報生成装置の出力を記憶し、
前記復元装置が、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから前記分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする秘密情報分散方法。
【請求項９】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、復元装置とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記分散情報生成装置に組み込まれる分散情報生成プログラムであって、
前記秘密情報を（ｋ，ｎ）閾値秘密分散法で分散符号化することにより生成したｎ個の分散情報データｖと前記秘密情報の検証を行うｎ個のチェック用データｅとをチェック関数ｈに入力して得られる出力からｎ個の認証用データａを生成し、前記ｎ個の分散情報データｖ、ｎ個のチェック用データｅ及びｎ個の認証用データａをそれぞれ前記記憶装置に出力する分散情報生成としてコンピュータを機能させることを特徴とする分散情報生成プログラム。
【請求項１０】
分散情報生成装置と、ｎ個（ｎは２以上の自然数）の記憶装置と、とを備え、秘密情報を分散して保管する秘密情報分散システムにおける前記復元装置に組み込まれる復元プログラムであって、
前記ｎ個の記憶装置の内のｋ個以上の前記記憶装置のそれぞれから分散情報データｖ、チェック用データｅ及び認証用データａを読み出し、当該読み出した情報に基づいて分散情報の正当性を判定し、当該判定の結果改竄された分散情報が存在する場合には当該改竄された分散秘密情報の識別子リストを出力し、当該判定の結果改竄された分散情報が存在しない場合には、前記読み出した分散情報データｖから復元された秘密情報を出力する、
ことを特徴とする復元装置としてコンピュータを機能させることを特徴とする復元プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１３−９２４５（Ｐ２０１３−９２４５Ａ）
【公開日】平成２５年１月１０日（２０１３．１．１０）
【国際特許分類】
【出願番号】特願２０１１−１４１７５５（Ｐ２０１１−１４１７５５）
【出願日】平成２３年６月２７日（２０１１．６．２７）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２５年１月１０日（２０１３．１．１０）
【国際特許分類】
【出願日】平成２３年６月２７日（２０１１．６．２７）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]