(57)【要約】【課題】秘密分散において、正しいデータであることを確認可能な分散データを少ない計算量で生成する。【解決手段】秘密分散装置は、秘密データと公開パラメータを保持し、分割した秘密データと第１乱数群の乱数の排他的論理和から複数の部分分散データを生成し、秘密データ、第１乱数群から得られる第１の値、及び各部分分散データについてハッシュ値を算出し、各部分分散データについて、秘密データのハッシュ値と第１の値のハッシュ値と当該部分分散データとから得られる値と、第２乱数群と当該部分分散データとから得られる値と、を含む付加分散データから分散データを生成し、公開パラメータと秘密データのハッシュ値と第２乱数群とに基づいて算出される値と、公開パラメータと第１の値のハッシュ値と第２乱数群とに基づいて算出される値と、を分散データの検証用データに含める。【選択図】図１
2020064245.tif 000002
【特許請求の範囲】
【請求項１】
秘密分散装置であって、
プロセッサと記憶装置とを備え、
前記記憶装置は、秘密データと、公開パラメータと、を保持し、
前記プロセッサは、
前記秘密データを分割し、
前記分割した秘密データと、複数の乱数からなる第１乱数群と、の排他的論理和に基づいて、複数の部分分散データを生成し、
前記秘密データの所定のハッシュ関数によるハッシュ値と、前記第１乱数群の乱数から得られる第１の値の前記所定のハッシュ関数によるハッシュ値と、前記複数の部分分散データそれぞれの前記所定のハッシュ関数によるハッシュ値と、を算出し、
前記複数の部分分散データそれぞれについて、前記秘密データのハッシュ値と前記第１の値のハッシュ値とを係数又は定数項として有する第１の関数に当該部分分散データを代入して得られる値と、前記第１乱数群に含まれない乱数からなる第２乱数群の乱数を係数又は定数項として有する第２の関数に当該部分分散データを代入して得られる値と、を含む付加分散データを、当該部分分散データに付加して分散データを生成し、
前記分散データそれぞれを異なる出力先へと出力し、
前記公開パラメータと前記秘密データのハッシュ値と前記第２乱数群に含まれる第１乱数とに基づいて算出される第２の値と、前記公開パラメータと前記第１の値のハッシュ値と前記第２乱数群に含まれる第２乱数とに基づいて算出される第３の値と、を前記分散データの検証用データに含める、秘密分散装置。
【請求項２】
請求項１に記載の秘密分散装置であって、
前記公開パラメータは、ｑ＝（ｐ−１）／２が素数となるような素数ｐと、ｐを法とした有限体の位数ｑの異なる元であるｇ１∈ＧＦ（ｐ）及びｇ２∈ＧＦ（ｐ）と、を含み、
前記第１乱数群は、乱数Ｒ０，・・・，Ｒｎ−２（Ｒｊ∈｛０，１｝ｄ(０≦ｊ≦ｎ−２)）を含み、
前記第２乱数群は、乱数ａ∈ＧＦ（ｑ）及び乱数ｂ∈ＧＦ（ｑ）を含み、
前記第１の値は、前記乱数を結合したＲ＝Ｒ０｜｜・・・｜｜Ｒｎ−２であり、
前記第１の関数は、Ｆ(Ｘ)＝ｈＳ＋ｈＲＸ  ｍｏｄ  ｑであり（但し、ｈｓは前記秘密データのハッシュ値であり、ｈＲは、前記第１の値Ｒのハッシュ値である）、
前記第２の関数は、Ｆ’(Ｘ)＝ａ＋ｂＸ  ｍｏｄ  ｑであり、
前記プロセッサは、
前記秘密データＳ∈｛０，１｝ｄ（ｎ−１）を、それぞれ長さｄのｎ−１個のデータＳ１，・・・，Ｓｎ−１に分割し、
Ｄ（ｉ，ｊ）＝Ｓ（ｉ−ｊ  ｍｏｄ  ｎ）ｘｏｒ  Ｒｊ（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−２、但しＳ０∈｛０｝ｄ）を、各（ｉ，ｊ）について計算し、
各Ｄ（ｉ，ｊ）を各ｉについて連結したＤ’（ｉ）＝Ｄ（ｉ，０）｜｜・・・｜｜Ｄ（ｉ，ｎ−２）を前記部分分散データとして生成し、
前記部分分散データＤ’（ｉ）（０≦ｉ≦ｎ−１）それぞれに対して、前記付加分散データＤ（ｉ，ｎ−１）＝Ｆ(ｈＤ’（ｉ）)及びＤ（ｉ，ｎ）＝Ｆ’(ｈＤ’（ｉ）)を計算して、前記付加分散データと当該部分分散データを結合したＤ（ｉ）＝Ｄ’（ｉ）｜｜Ｄ（ｉ，ｎ−１）｜｜Ｄ（ｉ，ｎ）を、前記分散データとして生成し、
Ｇ１＝ｐｏｗ(ｇ１，ｈＳ）×ｐｏｗ(ｇ２，ａ）ｍｏｄ  ｐを前記第２の値として算出し、
Ｇ２＝ｐｏｗ(ｇ１，ｈＲ）×ｐｏｗ(ｇ２，ｂ）ｍｏｄ  ｐを前記第３の値として算出する、秘密分散装置。
【請求項３】
請求項１に記載の秘密分散装置であって、
前記記憶装置は、
復元対象の第１秘密データから生成された第１分散データと、第２分散データと、を保持し、
前記プロセッサは、
前記第１分散データと前記第２分散データとから前記第１秘密データの復元処理を実行し、
前記復元処理において、
前記第１分散データ及び第２分散データそれぞれから前記付加分散データを削除して、部分分散データを取得し、
前記第１分散データの部分分散データ及び前記第２分散データの部分分散データそれぞれを分割し、
前記第１分散データの部分分散データの分割後のデータと、前記第２分散データの部分分散データの分割後のデータと、の排他的論理和に基づいて、前記第１秘密データの復元分割データを生成し、
前記復元分割データを結合して、前記第１秘密データを復元する、秘密分散装置。
【請求項４】
請求項３に記載の秘密分散装置であって、
前記プロセッサは、
前記第１分散データ及び前記第２分散データそれぞれに対して、当該分散データに対応する付加分散データと、前記検証用データに含まれる前記第２の値及び前記第３の値と、に基づいて、当該分散データが正しいデータであるか否かを判定し、
前記第１分散データ及び前記第２分散データの双方が正しいデータであると判定した場合、前記復元処理を実行する、秘密分散装置。
【請求項５】
請求項３に記載の秘密分散装置であって、
前記プロセッサは、
前記分割した後の第１分散データ及び前記分割した後の第２分散データと、前記復元分割データと、の排他的論理和に基づいて、前記第１秘密データの分散データの生成に用いられた前記第１乱数群の乱数を復元し、
前記復元した乱数から算出した前記第１の値の前記所定のハッシュ関数によるハッシュ値と、前記復元した第１秘密データの前記所定のハッシュ関数によるハッシュ値と、に基づいて、前記復元した第１秘密データが正しいデータであるか否かを判定する、秘密分散装置。
【請求項６】
秘密分散システムであって、
秘密分散装置と、複数の保管装置と、検証用データ公開装置とを含み、
前記秘密分散装置は、
秘密データと、公開パラメータと、を保持し、
前記秘密データを分割し、
前記分割した秘密データと、複数の乱数からなる第１乱数群と、の排他的論理和に基づいて、複数の部分分散データを生成し、
前記秘密データの所定のハッシュ関数によるハッシュ値と、前記第１乱数群の乱数から得られる第１の値の前記所定のハッシュ関数によるハッシュ値と、前記複数の部分分散データそれぞれの前記所定のハッシュ関数によるハッシュ値と、を算出し、
前記複数の部分分散データそれぞれについて、前記秘密データのハッシュ値と前記第１の値のハッシュ値とを係数又は定数項として有する第１の関数に当該部分分散データを代入して得られる値と、前記第１乱数群に含まれない乱数からなる第２乱数群の乱数を係数又は定数項として有する第２の関数に当該部分分散データを代入して得られる値と、を含む付加分散データを、当該部分分散データに付加して分散データを生成し、
前記分散データそれぞれを異なる前記保管装置へ送信し、
前記公開パラメータと前記秘密データのハッシュ値と前記第２乱数群に含まれる第１乱数とに基づいて算出される第２の値と、前記公開パラメータと前記第１の値のハッシュ値と前記第２乱数群に含まれる第２乱数とに基づいて算出される第３の値と、を前記分散データの検証用データに含め、
前記検証用データ及び前記公開パラメータを前記検証用データ公開装置に送信し、
前記検証用データ公開装置は、前記秘密分散システム内において、前記検証用データ及び前記公開パラメータを公開する、秘密分散システム。
【請求項７】
請求項６に記載の秘密分散システムであって、
前記公開パラメータは、ｑ＝（ｐ−１）／２が素数となるような素数ｐと、ｐを法とした有限体の位数ｑの異なる元であるｇ１∈ＧＦ（ｐ）及びｇ２∈ＧＦ（ｐ）と、を含み、
前記第１乱数群は、乱数Ｒ０，・・・，Ｒｎ−２（Ｒｊ∈｛０，１｝ｄ(０≦ｊ≦ｎ−２)）を含み、
前記第２乱数群は、乱数ａ∈ＧＦ（ｑ）及び乱数ｂ∈ＧＦ（ｑ）を含み、
前記第１の値は、前記乱数を結合したＲ＝Ｒ０｜｜・・・｜｜Ｒｎ−２であり、
前記第１の関数は、Ｆ(Ｘ)＝ｈＳ＋ｈＲＸ  ｍｏｄ  ｑであり（但し、ｈｓは前記秘密データのハッシュ値であり、ｈＲは、前記第１の値Ｒのハッシュ値である）、
前記第２の関数は、Ｆ’(Ｘ)＝ａ＋ｂＸ  ｍｏｄ  ｑであり、
前記秘密分散装置は、
前記秘密データＳ∈｛０，１｝ｄ（ｎ−１）を、それぞれ長さｄのｎ−１個のデータＳ１，・・・，Ｓｎ−１に分割し、
Ｄ（ｉ，ｊ）＝Ｓ（ｉ−ｊ  ｍｏｄ  ｎ）ｘｏｒ  Ｒｊ（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−２、但しＳ０∈｛０｝ｄ）を、各（ｉ，ｊ）について計算し、
各Ｄ（ｉ，ｊ）を各ｉについて連結したＤ’（ｉ）＝Ｄ（ｉ，０）｜｜・・・｜｜Ｄ（ｉ，ｎ−２）を前記部分分散データとして生成し、
前記部分分散データＤ’（ｉ）（０≦ｉ≦ｎ−１）それぞれに対して、前記付加分散データＤ（ｉ，ｎ−１）＝Ｆ(ｈＤ’（ｉ）)及びＤ（ｉ，ｎ）＝Ｆ’(ｈＤ’（ｉ）)を計算して、前記付加分散データと当該部分分散データを結合したＤ（ｉ）＝Ｄ’（ｉ）｜｜Ｄ（ｉ，ｎ−１）｜｜Ｄ（ｉ，ｎ）を、前記分散データとして生成し、
Ｇ１＝ｐｏｗ(ｇ１，ｈＳ）×ｐｏｗ(ｇ２，ａ）ｍｏｄ  ｐを前記第２の値として算出し、
Ｇ２＝ｐｏｗ(ｇ１，ｈＲ）×ｐｏｗ(ｇ２，ｂ）ｍｏｄ  ｐを前記第３の値として算出する、秘密分散システム。
【請求項８】
請求項６に記載の秘密分散システムであって、
前記秘密分散装置は、
復元対象の第１秘密データから生成された第１分散データと、第２分散データと、をそれぞれ異なる前記保管装置から受信し、
前記第１分散データと前記第２分散データとから前記第１秘密データの復元処理を実行し、
前記復元処理において、
前記第１分散データ及び第２分散データそれぞれから前記付加分散データを削除して、部分分散データを取得し、
前記第１分散データの部分分散データ及び前記第２分散データの部分分散データそれぞれを分割し、
前記第１分散データの部分分散データの分割後のデータと、前記第２分散データの部分分散データの分割後のデータと、の排他的論理和に基づいて、前記第１秘密データの復元分割データを生成し、
前記復元分割データを結合して、前記第１秘密データを復元する、秘密分散システム。
【請求項９】
請求項８に記載の秘密分散システムであって、
前記秘密分散装置は、
前記第１分散データ及び前記第２分散データそれぞれに対して、当該分散データに対応する付加分散データと、前記検証用データに含まれる前記第２の値及び前記第３の値と、に基づいて、当該分散データが正しいデータであるか否かを判定する検証処理を行い、
前記第１分散データ及び前記第２分散データの双方が正しいデータであると判定した場合、前記復元処理を実行し、
前記第１分散データ及び前記第２分散データの少なくとも一方が正しいデータでないと判定した場合、前記第１分散データ及び前記第２分散データ以外の前記第１秘密データの分散データを保持している保管装置から、前記第１秘密データの第３分散データを取得し、前記第３分散データに対して前記検証処理を行う、秘密分散システム。
【請求項１０】
請求項８に記載の秘密分散システムであって、
前記秘密分散装置は、
前記分割した後の第１分散データ及び前記分割した後の第２分散データと、前記復元分割データと、の排他的論理和に基づいて、前記第１秘密データの分散データの生成に用いられた前記第１乱数群の乱数を復元し、
前記復元した乱数から算出した前記第１の値の前記所定のハッシュ関数によるハッシュ値と、前記復元した第１秘密データの前記所定のハッシュ関数によるハッシュ値と、に基づいて、前記復元した第１秘密データが正しいデータであるか否かを判定する、秘密分散システム。
【請求項１１】
請求項６に記載の秘密分散システムであって、
前記保管装置は、
前記検証用データ公開装置から、前記検証用データを取得し、
受信した分散データに対応する付加分散データと、前記検証用データに含まれる前記第２の値及び前記第３の値と、に基づいて、当該分散データが正しいデータであるか否かを判定する検証処理を行う、秘密分散システム。
【請求項１２】
秘密分散装置による秘密分散方法であって、
前記秘密分散装置は、プロセッサと記憶装置とを備え、
前記記憶装置は、秘密データと、公開パラメータと、を保持し、
前記秘密分散方法は、
前記プロセッサが、前記秘密データを分割し、
前記プロセッサが、前記分割した秘密データと、複数の乱数からなる第１乱数群と、の排他的論理和に基づいて、複数の部分分散データを生成し、
前記プロセッサが、前記秘密データの所定のハッシュ関数によるハッシュ値と、前記第１乱数群の乱数から得られる第１の値の前記所定のハッシュ関数によるハッシュ値と、前記複数の部分分散データそれぞれの前記所定のハッシュ関数によるハッシュ値と、を算出し、
前記プロセッサが、前記複数の部分分散データそれぞれについて、前記秘密データのハッシュ値と前記第１の値のハッシュ値とを係数又は定数項として有する第１の関数に当該部分分散データを代入して得られる値と、前記第１乱数群に含まれない乱数からなる第２乱数群の乱数を係数又は定数項として有する第２の関数に当該部分分散データを代入して得られる値と、を含む付加分散データを、当該部分分散データに付加して分散データを生成し、
前記プロセッサが、前記分散データそれぞれを異なる出力先へと出力し、
前記プロセッサが、前記公開パラメータと前記秘密データのハッシュ値と前記第２乱数群に含まれる第１乱数とに基づいて算出される第２の値と、前記公開パラメータと前記第１の値のハッシュ値と前記第２乱数群に含まれる第２乱数とに基づいて算出される第３の値と、を前記分散データの検証用データに含める、秘密分散方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散装置、秘密分散システム、及び秘密分散方法に関する。
【背景技術】
【０００２】
秘密分散法の代表例として、Ｓｈａｍｉｒが考案した（ｋ，ｎ）閾値秘密分散法がある。Ｓｈａｍｉｒの（ｋ，ｎ）閾値秘密分散法は、秘密情報（元データ）を、意味を成さないｎ個の分散データに分散し、ｎ個の分散データのうちｋ個以上の分散データを集めると秘密情報（元データ）を復元可能な手法である。
【０００３】
しかし、Ｓｈａｍｉｒの（ｋ，ｎ）閾値秘密分散法は、秘密情報の分散処理や復元処理を、複雑な処理である多項式補間により実現するため、大量のデータを秘密分散化するのには、多くの計算量を要する。
【０００４】
そこで、簡単な処理である排他的論理和演算のみで実現される（２，ｎ）秘密分散方式の背景技術として特開２００７−１２４０３２号公報（特許文献１）がある。この公報には、「保存部１１の秘密情報Ｓを分割してｎ−１個の第１分割秘密データＫ（１），…，Ｋ（ｊ），…，Ｋ（n-1）を生成し、ゼロ値からなる分割秘密データＫ（０）を生成し、各分割秘密データと例えば同一サイズのｎ−１個の乱数データＲ（０），…，Ｒ（ｉ），…，Ｒ（n-2）を生成し、分割秘密データＫ（０），…，Ｋ（n-1）及び乱数データＲ（０），…，Ｒ（n-2）に基づいて、ｎ（ｎ−１）個の分散部分データＤ（ｊ，ｉ）＝Ｋ（ｊ−ｉ(mod ｎ)）(+)Ｒ（ｉ）を算出し（(+)は排他的論理和）、互いに同一の行番号ｊを有する分散部分データＤ（ｊ，０）〜Ｄ（ｊ，n-2）を有するｎ個の分散情報Ｄ（０），…，Ｄ（ｊ），…，Ｄ（n-1）を個別にｎ個の記憶装置に配布する。このうち、任意の２個の分散情報Ｄ（ｉ），Ｄ（ｊ）に基づいて、秘密情報Ｓを復元できる。」と記載されている（要約参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−１２４０３２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、特許文献１に記載の技術は、分散データが壊れている場合や、故意に第三者が正しい分散データを改竄した場合等において、分散データが正しいものであるかを判断することができない。そこで本発明の一態様は、秘密分散において、正しいデータであることを確認可能な分散データを、少ない計算量で生成することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明の一態様は、以下の構成を採用する。秘密分散装置は、プロセッサと記憶装置とを備え、前記記憶装置は、秘密データと、公開パラメータと、を保持し、前記プロセッサは、前記秘密データを分割し、前記分割した秘密データと、複数の乱数からなる第１乱数群と、の排他的論理和に基づいて、複数の部分分散データを生成し、前記秘密データの所定のハッシュ関数によるハッシュ値と、前記第１乱数群の乱数から得られる第１の値の前記所定のハッシュ関数によるハッシュ値と、前記複数の部分分散データそれぞれの前記所定のハッシュ関数によるハッシュ値と、を算出し、前記複数の部分分散データそれぞれについて、前記秘密データのハッシュ値と前記第１の値のハッシュ値とを係数又は定数項として有する第１の関数に当該部分分散データを代入して得られる値と、前記第１乱数群に含まれない乱数からなる第２乱数群の乱数を係数又は定数項として有する第２の関数に当該部分分散データを代入して得られる値と、を含む付加分散データを、当該部分分散データに付加して分散データを生成し、前記分散データそれぞれを異なる出力先へと出力し、前記公開パラメータと前記秘密データのハッシュ値と前記第２乱数群に含まれる第１乱数とに基づいて算出される第２の値と、前記公開パラメータと前記第１の値のハッシュ値と前記第２乱数群に含まれる第２乱数とに基づいて算出される第３の値と、を前記分散データの検証用データに含める、秘密分散装置。
【発明の効果】
【０００８】
本発明の一態様によれば、秘密分散において、正しいデータであることを確認可能な分散データを、少ない計算量で生成することができる。
【０００９】
上記した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００１０】
【図１】実施例１における秘密分散システムの全体構成例を示すブロック図である。
【図２】実施例１における計算機の構成例を示すブロック図である。
【図３】実施例１における秘密データ分散の全体処理の一例を示すシーケンス図である
【図４】実施例１における秘密分散システム全体による復元化処理の一例を示すシーケンス図である。
【図５】実施例１における秘密情報の分散化処理の詳細の一例を示すフローチャートである。
【図６】実施例１における各保管サーバによる分散データの保管処理の一例を示すフローチャートである。
【図７】実施例１におけるクライアント装置による復元化処理の詳細の一例を示すフローチャートである。
【図８】実施例１における保管サーバ装置に配布される分散データの各ブロックの値を示すテーブルである。
【図９】実施例１における保管サーバ装置に保管された分散データから付加分散データを削除して得られる部分分散データの各ブロックの値を示すテーブルである。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態を図面に基づいて詳細に説明する。本実施形態において、同一の構成には原則として同一の符号を付け、繰り返しの説明は省略する。なお、本実施形態は本発明を実現するための一例に過ぎず、本発明の技術的範囲を限定するものではないことに注意すべきである。
【実施例１】
【００１２】
＜システム構成＞
図１は、秘密分散システムの全体構成例を示すブロック図である。この図は、秘密分散システムの全体構成例と共に、秘密分散システムに含まれる各装置の機能構成例も示している。
【００１３】
秘密分散システム１は、例えば、クライアント装置１０と、検証用データ公開装置３０と、複数（本実施例ではｎ台とする）の保管サーバ装置２０ｉ（ｉ＝１，２，・・・，ｎ−１）と、を含み、これらは互いにインターネット等のネットワーク４０を介して接続されている。
【００１４】
つまり、秘密分散システム１は、クライアント装置１０と保管サーバ装置２０ｉと検証用データ公開装置３０が、インターネット等のネットワーク４０を介して通信可能に接続されて構成されたコンピュータネットワークシステムである。尚、複数の保管サーバ装置２０ｉは、一部又は全部が同一の組織によって運用されてもよいし、また、全部が異なる組織によって運用されてもよい。
【００１５】
なお、以下、保管サーバ装置２０１〜２０ｎ−１及び保管サーバ装置２０１〜２０ｎ−１に含まれる各部を特に区別する必要がない場合には、保管サーバ装置２０という記載のように添え字を省略するか、保管サーバ装置２０ｉという記載のように一般化して記載する。
【００１６】
クライアント装置１０は、例えば、通信部１０１、制御部１０２、入出力部１０３、分散データ生成部１０４、データ復元部１０５、及び乱数生成部１０６を含む。通信部１０１は、他の装置との通信を行う。制御部１０２は、クライアント装置１０の全体制御を行う。入出力部１０３は、クライアント装置１０への指示及びデータ等の入力、並びにクライアント装置１０からの指示及びデータ等の出力を行う。
【００１７】
分散データ生成部１０４は、後述する秘密情報を分散化して分散データＤ（ｉ）を生成し、分散データＤ（ｉ）を、それぞれ、保管サーバ装置２０ｉに配布する。つまり、クライアント装置１０は、秘密情報を分散する秘密情報分散装置として機能する。また、後述する検証用データ及び公開パラメータを生成して、検証用データ公開装置３０に配布する。データ復元部１０５は、保管サーバ装置２０から必要な数の（本実施例では、改竄及び破損等していない２つの正常な）分散化データを収集して元の秘密情報を復元する。
【００１８】
乱数生成部１０６は、分散データ生成部１０４等からの指示に応じて乱数を生成する。また、クライアント装置１０は、秘密情報１０７を保持する。秘密情報１０７は、分散化による秘匿対象のデータであり、分散化される前の元データである。
【００１９】
各保管サーバ装置２０ｉは、通信部２０１ｉ、保存部２０２ｉ、及び検証部２０４ｉを含む。通信部２０１ｉは他の装置との通信を行う。保存部２０２ｉは、通信部２０１ｉを介して受信した分散データ（Ｄ（ｉ））２０３ｉを保持する。検証部２０４ｉは受信した分散データが改竄されていないか又は破損していないか等を検証する。
【００２０】
検証用データ公開装置３０は、通信部３０１ｉ、及び保存部３０２ｉを含む。通信部３０１ｉは他の装置との通信を行う。保存部３０２ｉは、例えば、通信部３０１ｉを介して受信した後述する検証用データ（（Ｇ１，Ｇ２））３０３、及び後述する公開パラメータ（（ｐ，ｇ１，ｇ２））３０４を保持する。検証用データ３０３及び公開パラメータ３０４は、秘密分散システム１内で公開され、クライアント装置１０及び保管サーバ装置２０ｉによる分散データの改竄検知処理、並びにクライアント装置１０による秘密情報の復元処理等に用いられる。
【００２１】
図２は、計算機５０の構成例を示すブロック図である。クライアント装置１０、保管サーバ装置２０、及び検証用データ公開装置３０は、それぞれ、例えば、図２に示す計算機によって構成される。計算機５０は、例えば、通信装置５０１、入力装置５０２、メモリ５０３、補助記憶装置５０４、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０５、及び出力装置５０６を含み、これらはバス５０７等の内部通信線を介して互いに接続されている。
【００２２】
ＣＰＵ５０５は、プロセッサを含み、メモリ５０３に格納されたプログラムを実行する。メモリ５０３は、不揮発性の記憶素子であるＲＯＭ及び揮発性の記憶素子であるＲＡＭを含む。ＲＯＭは、不変のプログラム（例えば、ＢＩＯＳ）などを格納する。ＲＡＭは、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のような高速かつ揮発性の記憶素子であり、プロセッサが実行するプログラム及びプログラムの実行時に使用されるデータを一時的に格納する。
【００２３】
補助記憶装置５０４は、例えば、磁気記憶装置（ＨＤＤ）、フラッシュメモリ（ＳＳＤ）等の大容量かつ不揮発性の記憶装置であり、ＣＰＵ５０５が実行するプログラム及びプログラムの実行時に使用されるデータを格納する。すなわち、プログラムは、補助記憶装置５０４から読み出されて、メモリ５０３にロードされて、ＣＰＵ５０５によって実行される。
【００２４】
計算機５０は、入力インターフェース及び出力インターフェースを有してもよい。入力インターフェースは、キーボードやマウスなどの入力装置５０２が接続され、オペレータからの入力を受けるインターフェースである。出力インターフェースは、液晶表示装置や有機ＥＬ（Ｅｌｅｃｔｒｏ  Ｌｕｍｉｎｅｓｃｅｎｃｅ）ディスプレイ装置やプリンタなどの出力装置５０６が接続され、プログラムの実行結果をオペレータが視認可能な形式で出力するインターフェースである。
【００２５】
通信装置５０１は、所定のプロトコルに従って、他の装置との通信を制御するネットワークインターフェース装置である。例えば、クライアント装置１０の通信部１０１、保管サーバ装置２０の通信部２０１、及び検証用データ公開装置３０の通信部３０１は、それぞれ通信装置５０１によって構成される。
【００２６】
ＣＰＵ５０５が実行するプログラムは、リムーバブルメディア（ＣＤ−ＲＯＭ、フラッシュメモリなど）又はネットワーク４０を介して計算機５０に提供され、非一時的記憶媒体である不揮発性の補助記憶装置５０４に格納される。このため、計算機５０は、リムーバブルメディアからデータを読み込むインターフェースを有するとよい。
【００２７】
秘密分散システム１に含まれる各装置は、物理的に一つの計算機上で、又は、論理的又は物理的に構成された複数の計算機上で構成される計算機システムであり、同一の計算機上で別個のスレッドで動作してもよく、複数の物理的計算機資源上に構築された仮想計算機上で動作してもよい。
【００２８】
例えば、クライアント装置１０の制御部１０２、分散データ生成部１０４、データ復元部１０５、乱数生成部１０６は、ＣＰＵ５０５が実行するプログラムにより実現される。具体的には、例えば、ＣＰＵ５０５は、メモリ５０３にロードされた制御プログラムに従って動作することで、制御部１０２として機能し、メモリ５０３にロードされた分散データ生成プログラムに従って動作することで、分散データ生成部１０４として機能する。保管サーバ装置２０の検証部２０４についても同様である。
【００２９】
例えば、保管サーバ装置２０の保存部２０２ｉ、及び検証用データ公開装置３０の保存部３０２それぞれは、メモリ５０３又は補助記憶装置５０４に含まれる記憶領域の一部によって構成される。また、例えば、秘密情報１０７は、クライアント装置１０のメモリ５０３又は補助記憶装置５０４に格納されている。
【００３０】
なお、本実施形態において、秘密分散システム１に含まれる各装置が使用する情報は、データ構造に依存せずどのようなデータ構造で表現されていてもよい。例えば、テーブル、リスト、データベース又はキューから適切に選択したデータ構造体が、情報を格納することができる。
【００３１】
＜処理手順例＞
以下、本実施例における処理の一例について説明する。以下で説明する秘密分散処理に対応する各種動作は、秘密分散システム１を構成する各装置、即ちクライアント装置１０、保管サーバ装置２０ｉ、及び検証用データ公開装置３０それぞれがメモリ５０３等にロードして実行するプログラムによって実現される。
【００３２】
まず、分散化処理について図３、図５、図６、及び図８を用いて説明する。図３は、秘密データ分散の全体処理の一例を示すシーケンス図である。図３の処理は、例えば、クライアント装置１０のユーザからの指示（分散化化対象の秘密情報を示す情報を含む）を契機として開始する。
【００３３】
まず、クライアント装置１０の分散データ生成部１０４は、公開パラメータ（ｐ，ｇ１，ｇ２）を生成し（Ｓ１０）、通信部１０１は、当該公開パラメータを検証用データ公開装置３０に送信する（Ｓ１１）。なお、公開パラメータは、後述する秘密情報の復元処理に用いられるため、分散データ生成部１０４は、生成した公開パラメータをクライアント装置１０の補助記憶装置５０４に格納してもよい。
【００３４】
検証用データ公開装置３０は、受信した公開パラメータ（ｐ，ｇ１，ｇ２）を公開パラメータ３０４として保存部３０２に保管すると共に、クライアント装置１０及び保管サーバ装置２０に対して、公開パラメータ３０４を秘密分散システム１内で公開する（Ｓ１２）。つまり、クライアント装置１０、及び保管サーバ装置２０それぞれは、検証用データ公開装置３０に対して公開パラメータ３０４の取得を要求することにより、検証用データ公開装置３０から公開パラメータ３０４を取得することができる。
【００３５】
尚、値ｐは、ｑ＝（ｐ−１）／２が素数となるような十分大きな素数（例えばｐは１０２４ｂｉｔ以上の素数）とする。また、値ｇ１，ｇ２は、ｐを法とした有限体の位数ｑの異なる元、即ちｇ１，ｇ２∈ＧＦ（ｐ）、ｏｒｄ（ｇ１）＝ｏｒｄ（ｇ２）＝ｑである。なお、異なる秘密情報に、同一の公開パラメータ（ｐ，ｇ１，ｇ２）が用いられてもよいし、秘密情報ごとに公開パラメータ（ｐ，ｇ１，ｇ２）が異なってもよい。
【００３６】
クライアント装置１０の分散データ生成部１０４は、秘密情報１０７（以後、必要に応じて、秘密情報Ｓと記す）を分散化する（Ｓ２０）。図５を用いてステップＳ２０の分散化処理の詳細を説明する。
【００３７】
図５は、ステップＳ２０の秘密情報の分散化処理の詳細の一例を示すフローチャートである。尚、ここでは秘密情報Ｓのデータ長は、ｄ×（ｎ−１）であるものとする（ｄは１以上の所定の自然数）。仮に秘密情報Ｓのデータ長がｎ−１で割り切れない時は、分散データ生成部１０４は、秘密情報Ｓに対してパディング処理をすることによってデータ長をｎ−１で割り切れるように調整した値を、改めて秘密情報Ｓに決定する。
【００３８】
まず、分散データ生成部１０４は、秘密情報Ｓ∈｛０，１｝ｄ（ｎ−１）を分散化する（Ｓ２０１）。具体的には、例えば、分散データ生成部１０４は、秘密情報Ｓをｎ−１個のブロックに単純に分割する（Ｓ２０１）。尚、ここでは、秘密情報ＳをＳ＝Ｓ１｜｜・・・｜｜Ｓｎ−１とし（記号“｜｜”は、データの連結を示す）、分割された各ブロックをＳ１，・・・，Ｓｎ−１と記す。また、分散データ生成部１０４は、新たにＳ０∈｛０｝ｄを生成する。
【００３９】
次に、分散データ生成部１０４は、秘密情報、乱数、及び部分分散データのハッシュ値を算出する（Ｓ２０２）。具体的には、まず、乱数生成部１０６は、データ長がｄであるｎ−１個の乱数Ｒ０，・・・，Ｒｎ−２を、例えば互いに独立（即ち、選択された乱数間に所定の規則性がないように）かつランダムに選ぶ（ｉ．ｅ．，Ｒｉ∈｛０，１｝ｄ）。そして、分散データ生成部１０４は、Ｄ（ｉ，ｊ）＝Ｓ（ｉ−ｊ  ｍｏｄ  ｎ）ｘｏｒ  Ｒｊ（０≦ｉ≦ｎ−１，０≦ｊ≦ｎ−２）を、各（ｉ，ｊ）について計算する。
【００４０】
分散データ生成部１０４は、秘密情報Ｓ＝Ｓ１｜｜・・・｜｜Ｓｎ−１と乱数Ｒ＝Ｒ０｜｜・・・｜｜Ｒｎ−２のハッシュ値を計算する。また、分散データ生成部１０４は、各Ｄ（ｉ，ｊ）を各ｉについて連結した部分分散データＤ’（ｉ）＝Ｄ（ｉ，０）｜｜・・・｜｜Ｄ（ｉ，ｎ−２），（０≦ｉ≦ｎ−１）を生成する。
【００４１】
分散データ生成部１０４は、各部分分散データＤ’（ｉ）＝Ｄ（ｉ，０）｜｜・・・｜｜Ｄ（ｉ，ｎ−２），（０≦ｉ≦ｎ−１）のハッシュ値を計算する。尚、ここでは、出力長ｄ’（例えば、ｄ’は、２５６ｂｉｔ程度）のハッシュ関数をＨ（）で表し、Ｈ（Ｓ）＝ｈＳ、Ｈ（Ｒ）＝ｈＲ、Ｈ（Ｄ’（ｉ））＝ｈＤ’（ｉ），（０≦ｉ≦ｎ−１）とする。
【００４２】
このハッシュ関数は、例えば、クライアント装置１０及び保管サーバ装置２０ｉの補助記憶装置５０４に予め格納されていてもよいし、検証用データ公開装置３０によって秘密分散システム１内で公開されていてもよい。
【００４３】
次に、乱数生成部１０６は、乱数ａ，ｂ∈ＧＦ（ｑ）をさらに選び、分散データ生成部１０４は、２つの一次式、Ｆ(Ｘ)＝ｈＳ＋ｈＲＸ  ｍｏｄ  ｑ及びＦ’(Ｘ)＝ａ＋ｂＸ  ｍｏｄ  ｑを生成する（Ｓ２０３）。
【００４４】
次に、分散データ生成部１０４は、付加分散データＤ（ｉ，ｎ−１）＝Ｆ(ｈＤ’（ｉ）)＝ｆｉ及びＤ（ｉ，ｎ）＝Ｆ’(ｈＤ’（ｉ）)＝ｆ’ｉを計算する（Ｓ２０４）。
【００４５】
次に、分散データ生成部１０４は、検証用データとして、Ｇ１＝ｐｏｗ(ｇ１，ｈＳ）×ｐｏｗ(ｇ２，ａ）ｍｏｄ  ｐ、Ｇ２＝ｐｏｗ(ｇ１，ｈＲ）×ｐｏｗ(ｇ２，ｂ）ｍｏｄ  ｐを生成し（Ｓ３０）、（Ｇ１，Ｇ２）を検証用データとして検証用データ公開装置３０に送信する（Ｓ３１）。尚、関数ｐｏｗ（）は指数関数を示し、ｐｏｗ(ａ，ｂ）＝ａｂを意味する。
【００４６】
そして、検証用データ公開装置３０は、受信した（Ｇ１，Ｇ２）を検証用データ３０３として保管すると共に、クライアント装置１０、及び保管サーバ装置２０ｉに対して、当該検証用データ（Ｇ１，Ｇ２）を秘密分散システム１内で公開する（Ｓ３２）。分散データ生成部１０４は、部分分散データと付加分散データを連結した分散データＤ（ｉ）＝Ｄ’（ｉ）｜｜Ｄ（ｉ，ｎ−１）｜｜Ｄ（ｉ，ｎ），（０≦ｉ≦ｎ−１）を、それぞれ、保管サーバ装置２０ｉに配布する（Ｓ４０）。
【００４７】
図３の説明に戻る。続いて、各保管サーバ装置２０ｉは、検証用データ公開装置３０から検証用データ（Ｇ１，Ｇ２）及び公開パラメータ（ｐ，ｇ１，ｇ２）を取得し、自身が保管する分散データＤ（ｉ）２０３ｉの正当性を検証し（Ｓ５０）、分散データＤ（ｉ）を管理する（Ｓ６０）。
【００４８】
図６は、ステップＳ５０及びステップＳ６０における、各保管サーバ装置２０ｉによる分散データの保管処理の一例を示すフローチャートである。各保管サーバ装置２０ｉは、クライアント装置１０から、部分分散データと付加分散データを連結したデータである分散データＤ（ｉ）＝Ｄ’（ｉ）｜｜Ｄ（ｉ，ｎ−１）｜｜Ｄ（ｉ，ｎ），（０≦ｉ≦ｎ−１）を受信する（ステップＳ４０１）。
【００４９】
図８は、保管サーバ装置２０に配布される分散データの各ブロックの値を示すテーブルである。図８は、ｎ＝５の場合の例を示す。テーブルのｍ行目かつｌ列目のセルの値は、ｉ＝ｍにおけるＤ（ｉ）を長さｄのブロック長に分割した場合のｌ番目のブロックの値を示す。
【００５０】
まず、ステップＳ５０の検証処理の詳細を説明する。検証部２０４は、検証用データ公開装置３０から検証用データ（Ｇ１，Ｇ２）及び公開パラメータ（ｐ，ｇ１，ｇ２）を取得する（Ｓ５０１）。検証部２０４ｉは、分散データＤ（ｉ）＝Ｄ’（ｉ）｜｜Ｄ（ｉ，ｎ−１）＝ｆｉ｜｜Ｄ（ｉ，ｎ）＝ｆ’ｉから部分分散データと付加分散データを取り出し、部分分散データＤ’（ｉ）のハッシュ値Ｈ（Ｄ’（ｉ））＝ｈＤ’（ｉ）を計算する（Ｓ５０２）。
【００５１】
続いて、ステップＳ６０における管理処理について説明する。検証部２０４ｉは、ｐｏｗ(ｇ１，ｆｉ）×ｐｏｗ(ｇ２，ｆ’ｉ）≡Ｇ１×ｐｏｗ(Ｇ２，ｈＤ’（ｉ））ｍｏｄ  ｐとなるかを確認する（Ｓ５０３）。検証部２０３ｉがステップＳ５０３における数式が成り立つと判定した場合（Ｓ５０３：ｙｅｓ）、保管サーバ装置２０ｉは、受信した分散データは正しいデータであるものとしてＤ（ｉ）２０３ｉを保管する（Ｓ６０１）。
【００５２】
一方、検証部２０４ｉはステップＳ５０３における数式が成り立たないと判定した場合（Ｓ５０３：ｎｏ）、ＥＲＲＯＲとして処理する（Ｓ６０２）。具体的には、例えば、検証部２０４ｉは、ＥＲＲＯＲを、保管サーバ装置２０ｉの出力装置５０６に出力する。また、例えば、検証部２０４ｉは、クライアント装置１０に通知してもよい。この場合、例えば、クライアント装置１０は、分散データＤ（ｉ）を単に再送信する、又は分散データＤ（ｉ）を再生成した上で、保管サーバ装置２０ｉに再送信し、保管サーバ装置２０ｉは、再受信した分散データＤ（ｉ）を再検証する。
【００５３】
以下、ステップＳ５０３における数式の成否を判定することによって、受信した分散データが正しい値であるか否かを判定できる理由について説明する。前述した定義より、Ｇ１＝ｐｏｗ(ｇ１，ｈＳ）×ｐｏｗ(ｇ２，ａ）ｍｏｄ  ｐ、Ｇ２＝ｐｏｗ(ｇ１，ｈＲ）×ｐｏｗ(ｇ２，ｂ）ｍｏｄ  ｐ、Ｆ(Ｘ)＝ｈＳ＋ｈＲＸ  ｍｏｄ  ｑ、Ｆ’(Ｘ)＝ａ＋ｂＸ  ｍｏｄ  ｑ、Ｆ(ｈＤ’（ｉ）)＝ｆｉ、Ｆ’(ｈＤ’（ｉ）)＝ｆ’ｉであることから、
（ステップＳ５０３の数式の右辺）
≡Ｇ１×ｐｏｗ(Ｇ２，ｈＤ’（ｉ））  ｍｏｄ  ｐ
≡｛ｐｏｗ（ｇ１-，ｈｓ）×ｐｏｗ（ｇ２，ａ）｝×｛ｐｏｗ（ｐｏｗ（ｇ１，ｈＲ）×ｐｏｗ（ｇ２，ｂ）），ｈＤ’（ｉ）)｝  ｍｏｄ  ｐ
≡ｐｏｗ（ｇ１，ｈｓ＋ｈＲｈＤ’（ｉ））×ｐｏｗ（ｇ２，ａ＋ｂｈＤ’（ｉ））  ｍｏｄ  ｐ
≡ｐｏｗ（ｇ１，Ｆ（ｈＤ’（ｉ））×ｐｏｗ（ｇ２，Ｆ’（ｈＤ’（ｉ））  ｍｏｄ  ｐ
≡ｐｏｗ(ｇ１，ｆｉ）×ｐｏｗ(ｇ２，ｆ’ｉ）
≡（ステップＳ５０３の数式の左辺）
である。
【００５４】
従って、正しい公開パラメータ及び検証用データを取得した保管サーバ装置２０ｉであれば、ステップＳ５０３における数式の成否を確認することにより、受信した分散データが正しい値であるか否かを判定することができる。
【００５５】
次に、復元化処理について図４、図７、及び図９を用いて説明する。図４は、秘密分散システム１全体による復元化処理の一例を示すシーケンス図である。図４の処理は、例えば、クライアント装置１０のユーザからの指示（復元化対象の秘密情報を示す情報を含む）を契機として開始する。まず、クライアント装置１０は、２つの保管サーバ装置２０それぞれから、分散データＤ（ｉ）を取得する（ステップＳ７０）。
【００５６】
具体的には、例えば、クライアント装置１０のデータ復元部１０５は、例えばランダムに選択した２つの保管サーバ装置２０に対して、分散データＤ（ｉ）の送信指示を出す。当該２つの保管サーバ装置２０それぞれは、自身が保持する分散データＤ（ｉ）をクライアント装置１０に対して送信する（ステップＳ７１）。
【００５７】
また、クライアント装置１０は、検証用データ公開装置３０から、検証値データ（Ｇ１，Ｇ２）を取得する（ステップＳ８０）。具体的には、例えば、クライアント装置１０のデータ復元部１０５は、検証用データ公開装置３０に対して、検証値データ（Ｇ１，Ｇ２）の送信指示を出す。検証用データ公開装置３０は、（Ｇ１，Ｇ２）をクライアント装置１０に対して送信する（ステップＳ８１）。
【００５８】
なお、クライアント装置１０は、検証用パラメータ生成時に検証用パラメータをクライアント装置１０内に保存しなかった場合は、ステップＳ８０〜Ｓ８１において、検証用パラメータをさらに検証用データ公開装置３０から取得する。続いて、クライアント装置１０のデータ復元部１０５は、取得した分散データＤ（ｉ）の正当性を確認しつつ、秘密情報Ｓを復元する（ステップＳ９０）。
【００５９】
図７は、クライアント装置１０による復元化処理の詳細の一例を示すフローチャートである。図７は、ステップＳ７０における分散データ取得処理、ステップＳ９０における秘密情報の復元処理の詳細を示す。
【００６０】
まず、ステップＳ７０の詳細について説明する。クライアント装置１０のデータ復元部１０５は、ｎ−１個の保管サーバ装置２０の内、未選択の（即ち後述するステップＳ９０３及びステップＳ９０５の判定対象となっていない）保管サーバ装置２０があるか否かを判定する（Ｓ７０１）。データ復元部１０５は、未選択の保管サーバ装置２０が、ないと判定した場合（Ｓ７０１：ｎｏ）、ＥＲＲＯＲを返す（Ｓ９０６）。具体的には、例えば、データ復元部１０５は、ＥＲＲＯＲを、クライアント装置１０の出力装置５０６に出力する。
【００６１】
データ復元部１０５は、未選択の保管サーバ装置２０があると判定した場合（Ｓ７０１：ｙｅｓ）、未選択の保管サーバ装置２０を１つ選択し、選択した保管サーバ装置２０に対して、分散データＤ（ｉ）の送信指示を出し、当該保管サーバ装置２０から、分散データＤ（ｉ）を取得する（Ｓ７０２）。
【００６２】
続いて、前述したように、クライアント装置１０は、検証用データ公開装置３０から、検証値データ（Ｇ１，Ｇ２）を取得する（ステップＳ８０）。なお、クライアント装置１０が検証値データ（Ｇ１，Ｇ２）を取得済みの場合は、ステップＳ８０は省略されてもよい。
【００６３】
次に、ステップＳ９０の詳細について説明する。クライアント装置１０のデータ復元部１０５は、取得した分散データＤ（ｉ）＝Ｄ’（ｉ）｜｜Ｄ（ｉ，ｎ−１）＝ｆｉ｜｜Ｄ（ｉ，ｎ）＝ｆ’ｉそれぞれに対して、部分分散データＤ’（ｉ）のハッシュ値Ｈ（Ｄ’（ｉ））＝ｈＤ’（ｉ）を計算する（Ｓ９０１）。
【００６４】
そして、データ復元部１０５は、生成したハッシュ値Ｈ（Ｄ’（ｉ））＝ｈＤ’（ｉ）に対して、ｐｏｗ(ｇ１，ｆｉ）×ｐｏｗ(ｇ２，ｆ’ｉ）≡Ｇ１×ｐｏｗ(Ｇ２，ｈＤ’（ｉ））ｍｏｄ  ｐとなるかを確認する（Ｓ９０２）。データ復元部１０５は、ステップＳ９０２における数式が成り立たないと判定した場合（Ｓ９０２：ｎｏ）、ステップＳ７０１に戻り、新たな分散データを選択する。
【００６５】
なお、ステップＳ９０２の数式の検証は、ステップＳ５０３と同様である。つまり、ステップＳ９０２における検証が実行されることにより、保管処理から復元までの間のいずれかのタイミングにおける分散データの改竄（及び破損等）を検知し、ひいては改竄された分散データを用いた復元処理を実行せずに済む。なお、分散データの改竄検知処理は、保管処理時（ステップＳ５０１〜Ｓ５０３）又は復元処理時（ステップＳ９０１〜Ｓ９０２）の一方のタイミングのみで実行されてもよい。
【００６６】
そして、データ復元部１０５は、ステップＳ９０２の数式が成立する分散データを２つ収集済みであるか否かを判定する（Ｓ９０３）。データ復元部１０５は、ステップＳ９０２の数式が成立する分散データをまだ２つ収集していない場合には（Ｓ９０３：ｎｏ）、ステップＳ７０１に戻り、新たな分散データを選択する。
【００６７】
データ復元部１０５は、ステップＳ９０２の数式が成立する２つの分散データを収集済みであると判定した場合（Ｓ９０３：ｙｅｓ）、その２つの分散データを用いて、秘密情報Ｓを復元する（Ｓ９０４）。
【００６８】
以下、ステップＳ９０４の詳細について説明する。ここでは、ステップＳ９０２の数式が成立する２つの分散データをそれぞれＤ（ｉ）＝Ｄ’（ｉ）｜｜Ｄ（ｉ，ｎ−１）＝ｆｉ｜｜Ｄ（ｉ，ｎ）＝ｆ’ｉ、Ｄ（ｊ）＝Ｄ’（ｊ）｜｜Ｄ（ｊ，ｎ−１）＝ｆｊ｜｜Ｄ（ｊ，ｎ）＝ｆ’ｊとする。
【００６９】
まず、データ復元部１０５は、分散データＤ（ｉ）及びＤ（ｊ）に対して、それぞれ、後ろ２ｄ’長のデータ、即ち、付加分散データであるＤ（ｉ，ｎ−１）＝ｆｉ｜｜Ｄ（ｉ，ｎ）＝ｆ’ｉ及びＤ（ｊ，ｎ−１）＝ｆｊ｜｜Ｄ（ｊ，ｎ）＝ｆ’ｊを削除して得られる残りのデータである部分分散データＤ’（ｉ）＝Ｄ（ｉ，０）｜｜・・・｜｜Ｄ（ｉ，ｎ−２）及びＤ’（ｊ）＝Ｄ（ｊ，０）｜｜・・・｜｜Ｄ（ｊ，ｎ−２）、をデータ長ｄのブロックに分割する。
【００７０】
つまり、部分分散データＤ’（ｉ）に対するデータ長ｄの各ブロックは、Ｄ（ｉ，０），・・・，Ｄ（ｉ，ｎ−２）であり、部分分散データＤ’（ｊ）に対するデータ長ｄの各ブロックはＤ（ｊ，０），・・・，Ｄ（ｊ，ｎ−２）である。
そして、データ復元部１０５は、ｒ＝ｊ−ｉ  ｍｏｄ  ｎに対して、以下の場合に分けてＳ１，・・・，Ｓｎ−１を求める。
【００７１】
Ｃａｓｅ１：Ｄ（ｉ，ｉ）がＤ（ｉ，ｌ）に含まれる時（但し０≦ｌ≦ｎ−２）、終了条件１を満たすまで以下を繰返す。但し終了条件１は、ｉ−ｋｒ＝ｎ−１（１≦ｋ≦ｎ−１）。
ｋ＝１：Ｓｒ＝Ｄ（ｉ，ｉ）ｘｏｒ  Ｄ（ｊ，ｉ）ｘｏｒ  Ｓ０，
ｋ＝２：Ｓｒ＋ｒ＝Ｄ（ｉ，ｉ−ｒ）ｘｏｒ  Ｄ（ｊ，ｉ−ｒ）ｘｏｒ  Ｓｒ，
・・・
ｋ＝ｎ−１：Ｓ（ｎ−１）ｒ＝Ｄ（ｉ，ｉ−（ｎ−２）ｒ）ｘｏｒ  Ｄ（ｊ，ｉ−（ｎ−２）ｒ）ｘｏｒ  Ｓ（ｎ−２）ｒ
【００７２】
Ｃａｓｅ２：Ｄ（ｊ，ｊ）がＤ（ｊ，ｌ）に含まれる時、終了条件２を満たすまで以下を繰返す。但し終了条件２は以下。ｊ＋ｋｒ＝ｎ−１（１≦ｋ≦ｎ−１）。
ｋ＝１：Ｓ−ｒ＝Ｄ（ｉ，ｊ）ｘｏｒ  Ｄ（ｊ，ｊ）ｘｏｒ  Ｓ０，
ｋ＝２：Ｓ−r−ｒ＝Ｄ（ｉ，ｊ＋ｒ）ｘｏｒ  Ｄ（ｊ，ｊ＋ｒ）ｘｏｒ  Ｓ−ｒ，
・・・
ｋ＝ｎ−１：Ｓ−（ｎ−１）ｒ＝Ｄ（ｉ，ｊ＋（ｎ−２）ｒ）ｘｏｒ  Ｄ（ｊ，ｉ＋（ｎ−２）ｒ）ｘｏｒ  Ｓ−（ｎ−２）ｒ
【００７３】
尚、Ｃａｓｅ１、及びＣａｓｅ２における演算子±はｍｏｄ  ｎの演算を示す。以下、上述したＣａｓｅ１、及びＣａｓｅ２におけるＳ１，・・・，Ｓｎ−１の算出処理の具体例を説明する。
【００７４】
図９は、保管サーバ装置２０に保管された分散データから付加分散データを削除して得られる部分分散データの各ブロックの値を示すテーブルである。図９は、ｎ＝５の場合の例を示す。従って、図９は、図８のテーブルからｊ＝４の列とｊ＝５の列が削除されたテーブルであるテーブルである。
【００７５】
図９のテーブルは５行×４列の表であるため、対角成分のうちＤ（４，４）を含まない。選択された２つの分散データがＤ（４）を含む場合と、含まない場合と、において、Ｃａｓｅ１及びＣａｓｅ２の該当有無が異なる。
【００７６】
ここで、例えば、ｉ＝４，ｊ＝０の例、即ちＤ（４）とＤ（０）とが選択された例を説明しする。まず、ｒ＝ｊ−ｉ  ｍｏｄ  ５＝０−４＝−４である。Ｄ（４，４）は、Ｄ（４，ｌ）＝｛Ｄ（４，０），Ｄ（４，１），Ｄ（４，２），Ｄ（４，３）｝に含まれないため、本例はＣａｓｅ１には該当しない。
また、Ｄ（０，０）は、Ｄ（０，ｌ）＝｛Ｄ（０，０），Ｄ（０，１），Ｄ（０，２），Ｄ（０，３）｝に含まれるため、本例はＣａｓｅ２に該当する。
【００７７】
ｋ＝１：Ｓ−（−４）＝Ｄ（４，０）  ｘｏｒ  Ｄ（０，０）  ｘｏｒ  Ｓ０＝Ｓ４であり、終了条件２については、０＋１（−４）＝−４＝１≠４であるため、満たされない。
【００７８】
ｋ＝２：Ｓ−（−４）−（−４）＝Ｄ（４，１））  ｘｏｒ  Ｄ（０，１）  ｘｏｒ  Ｓ４＝Ｓ３であり、終了条件２については、０＋２（−４）＝−８＝２≠４であるため、満たされない。
【００７９】
ｋ＝３：Ｓ−３（−４）＝Ｄ（４，２）  ｘｏｒ  Ｄ（０，２）  ｘｏｒ  Ｓ３＝Ｓ２であり、終了条件２については、０＋３（−４）＝−１２＝３≠４であるため、満たされない。
【００８０】
ｋ＝４：Ｓ−４（−４）＝Ｄ（４，３）  ｘｏｒ  Ｄ（０，３）  ｘｏｒ  Ｓ２＝Ｓ１であり、終了条件２については、０＋４（−４）＝−１６＝４＝４であり、満たされるため、Ｃａｓｅ２の計算が終了する。これにより、Ｃａｓｅ２からＳ１、Ｓ２、Ｓ３、Ｓ４の全てが算出された。
【００８１】
次に、ここで、例えば、ｉ＝３，ｊ＝０の例、即ちＤ（３）とＤ（０）とが選択された例を説明する。まずｒ＝ｊ−ｉ  ｍｏｄ  ５  ＝０−３＝−３である。Ｄ（３，３）はＤ（３，ｌ）＝｛Ｄ（３，０），Ｄ（３，１），Ｄ（３，２），Ｄ（３，３）｝に含まれるため、本例はＣａｓｅ１に該当する。
【００８２】
ｋ＝１：Ｓ（−３）＝Ｄ（３，３）  ｘｏｒ  Ｄ（０，３）  ｘｏｒ  Ｓ０＝Ｓ２であり、終了条件１については、３−１（−３）＝６＝１≠４であり、満たされない。
【００８３】
ｋ＝２：Ｓ（−３）＋（−３）＝Ｄ（３，１）  ｘｏｒ  Ｄ（０，１）  ｘｏｒ  Ｓ２＝Ｓ４であり、終了条件１については、３−２（−３）＝９＝４＝４であり、満たされるため、Ｃａｓｅ１の計算が終了する。
また、Ｄ（０，０）も、Ｄ（０，ｌ）＝｛Ｄ（０，０），Ｄ（０，１），Ｄ（０，２），Ｄ（０，３）｝に含まれるため、本例はＣａｓｅ２にも該当する。
【００８４】
ｋ＝１：Ｓ−（−３）＝Ｄ（３，０）  ｘｏｒ  Ｄ（０，０）  ｘｏｒ  Ｓ０＝Ｓ３であり、終了条件２については、０＋１（−３）＝−３＝２≠４であるため、満たされない。
【００８５】
ｋ＝２：Ｓ−（−３）−（−３）＝Ｄ（３，２））  ｘｏｒ  Ｄ（０，２）  ｘｏｒ  Ｓ３＝Ｓ１であり、終了条件２については、０＋２（−３）＝−６＝２＝４であり、満たされるため、Ｃａｓｅ２の計算が終了する。これにより、Ｃａｓｅ１及びＣａｓｅ２からＳ１、Ｓ２、Ｓ３、Ｓ４の全てが算出された。
つまり、どの分散データの組み合わせが選択されば場合であってもＳ１，Ｓ２，Ｓ３，Ｓ４を計算することができる。
【００８６】
続いて、データ復元部１０５は、Ｃａｓｅ１及び／又はＣａｓｅ２により出力されるＳ１，・・・，Ｓｎ−１を連結することで復元された秘密情報である復元データＳ’＝Ｓ１｜｜・・・｜｜Ｓｎ−１を復元する。尚、ここでは復元されたデータと元データとを区別する為に復元された秘密情報を復元データＳ’と記す。
【００８７】
データ復元部１０５は、ステップＳ９０４で復元データＳ’＝Ｓ１｜｜・・・｜｜Ｓｎ−１を復元したら、ｆｉ−Ｈ（Ｒ’）ｈＤ’（ｉ）＝Ｈ（Ｓ’）であるかを確認する（Ｓ９０５）。尚、Ｒ’とは以下の処理によって復元される乱数データである。
【００８８】
データ復元部１０５は、Ｒｊ＝Ｄ（ｉ，ｊ）ｘｏｒＳ（ｉ−ｊ  ｍｏｄ  ｎ）（０≦ｊ≦ｎ−２）を計算し、出力されるＲ０，・・・，Ｒｎ−２を連結することで乱数データＲ’＝Ｒ０｜｜・・・｜｜Ｒｎ−２を復元する。
【００８９】
そして、データ復元部１０５は、Ｄ（ｉ，ｎ−１）＝ｆｉと、Ｈ（Ｄ’（ｉ））＝ｈＤ’（ｉ）と、復元したＳ’，Ｒ’から、前述したようにステップＳ９０５における数式ｆｉ−Ｈ（Ｒ’）×ｈＤ’（ｉ）＝Ｈ（Ｓ’）が成立するか否かを判定する。
【００９０】
データ復元部１０５がステップＳ９０５の数式が成り立つと判定した場合（Ｓ９０５：ｙｅｓ）、復元データＳ’は秘密情報Ｓと同一であり、復元データＳ’を出力して復元化処理を終了する。データ復元部１０５がステップＳ９０５の数式が成り立たないと判定した場合（Ｓ９０５：ｎｏ）、復元データＳ’は秘密情報Ｓと同一ではないため、ステップＳ７０１に戻る。
【００９１】
以下、ステップＳ９０５における数式の成否を判定することによって、復元の成否を判定できる理由について説明する。前述した定義より、Ｆ(ｈＤ’（ｉ）)＝ｆｉ、Ｆ(Ｘ)＝ｈＳ＋ｈＲＸ  ｍｏｄ  ｑであることから、（ステップＳ９０５の左辺）＝ｆｉ−Ｈ（Ｒ’）×ｈＤ’（ｉ）＝Ｆ（ｈＤ’（ｉ））−Ｈ（Ｒ’）×ｈＤ’（ｉ）-＝ｈＳ＋ｈＲｈＤ’（ｉ）−Ｈ（Ｒ’）×ｈＤ’（ｉ）である。従って、ｈＳ＝Ｈ（Ｓ’）及びｈＲ＝Ｈ（Ｒ’）が成立すれば、即ちＳのハッシュ値とＳ’のハッシュ値とが等しく、かつＲのハッシュ値とＲ’のハッシュ値とが等しければ、（ステップＳ９０５の左辺）＝（ステップＳ９０５の右辺）が成立する。つまり、（ステップＳ９０５の左辺）＝（ステップＳ９０５の右辺）が成立すれば極めて高い確率でＳとＳ’は等しいことがいえる。
【００９２】
以上、本実施例の秘密情報分散システムによれば、ステップＳ５０３又はステップＳ９０２の検証処理を行うことで、分散データ保管時又は秘密情報復元時に、分散データＤ（ｉ）の改竄及び破損等を、少ない計算量で検知することができる。また、分散データを生成するための計算量も少ない。
【００９３】
尚、検証用データ（Ｇ１，Ｇ２）は、Ｈ（Ｓ）＝ｈＳ，Ｈ（Ｒ）＝ｈＲの値を知っている者のみが生成することできる値であるため、分散データを生成した者以外は、正しい検証用データ（Ｇ１，Ｇ２）を生成することはできない。
【００９４】
また、各分散データＤ（ｉ）（０≦ｉ≦ｎ−１）に対して、検証用データ（Ｇ１，Ｇ２）は、同一である為、ステップＳ５０３又はステップＳ９０２の検証処理をパスした各分散データＤ（ｉ）（０≦ｉ≦ｎ−１）は、同一の秘密情報Ｓを分散した物であることも、少ない計算量で確認できる。また、秘密情報を復元するための計算量も少ない。
【００９５】
さらに検証用データ（Ｇ１，Ｇ２）は、秘密情報Ｓの改竄検知機能も有するデータであるので、ステップＳ９０５の検証処理を行うことで、復元データＳ’は、秘密情報Ｓ（元データ）と一致していることも確認することができる。
【００９６】
なお、本発明は上記した実施例に限定されるものではなく、様々な変形例が含まれる。例えば、上記した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに限定されるものではない。また、ある実施例の構成の一部を他の実施例の構成に置き換えることも可能であり、また、ある実施例の構成に他の実施例の構成を加えることも可能である。また、各実施例の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【００９７】
また、上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することによりソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の記録装置、又は、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に置くことができる。
【００９８】
また、制御線や情報線は説明上必要と考えられるものを示しており、製品上必ずしも全ての制御線や情報線を示しているとは限らない。実際には殆ど全ての構成が相互に接続されていると考えてもよい。
【符号の説明】
【００９９】
１  秘密分散システム、１０  クライアント装置、２０  保管サーバ装置、３０  検証用データ公開装置、５０  計算機、１０４  分散データ生成部、１０５  データ復元部、１０６  乱数生成部、１０７  秘密情報、２０３  分散データ、３０３  検証用データ、３０４  公開パラメータ、５０１  通信装置、５０２  入力装置、５０３  メモリ、５０４  補助記憶装置、５０５  ＣＰＵ、５０６  出力装置
【図１】
2020064245.tif 000003
【図２】
2020064245.tif 000004
【図３】
2020064245.tif 000005
【図４】
2020064245.tif 000006
【図５】
2020064245.tif 000007
【図６】
2020064245.tif 000008
【図７】
2020064245.tif 000009
【図８】
2020064245.tif 000010
【図９】
2020064245.tif 000011