(57)【特許請求の範囲】
【請求項１】
秘密データを（３，２，４）ランプ型閾値秘密分散により４個の分割データに分割して、４個の前記分割データをそれぞれ異なる記憶装置に分散保管するデータ分割装置であって、
前記秘密データから抽出した長さＳの単位秘密データを長さＳ／６の６個の秘密部分データに分割し、
長さＳ／６の３個の乱数部分データを生成し、
前記秘密部分データ、前記乱数部分データ、および前記秘密部分データのうちの１個以上と前記乱数部分データのうちの１個から分割部分データを生成するためのＸＯＲ演算を定義した分割行列に基づいて、１２個の前記分割部分データを生成し、
それぞれ異なる前記乱数部分データを含むＸＯＲ演算により生成された３個の前記分割部分データを連結して４種類の長さＳ／２の単位分割データを生成し、
前記単位分割データを種類毎に連結して４個の分割データを生成する分割処理部を有することを特徴とするデータ分割装置。
【請求項２】
請求項１に記載のデータ分割装置において、
３個の前記分割データのそれぞれから抽出した長さＳ／２の前記単位分割データから３個の前記分割部分データをそれぞれ抽出し、
前記分割データの種類の組み合わせに対応した前記分割行列の部分行列に対する逆行列である復元行列に基づく、抽出した前記分割部分データのＸＯＲ演算により、６個の前記秘密部分データを生成し、
生成した前記秘密部分データを連結して長さＳの前記単位秘密データを生成し、
生成した前記単位秘密データを連結して前記秘密データを生成する復元処理部を有することを特徴とするデータ分割装置。
【請求項３】
請求項２に記載のデータ分割装置において、
前記分割行列により定義された、前記秘密部分データ（ｓ１〜ｓ６）のうちの１個以上と前記乱数部分データ（ｒ１〜ｒ３）のうちの１個から、１２個の前記分割部分データを生成するためのＸＯＲ演算の式は、
ａ１＝ｒ１＋ｓ１＋ｓ２
ａ２＝ｒ２＋ｓ３＋ｓ４
ａ３＝ｒ３＋ｓ５＋ｓ６
ｂ１＝ｒ１＋ｓ３＋ｓ５
ｂ２＝ｒ２＋ｓ１＋ｓ３＋ｓ５＋ｓ６
ｂ３＝ｒ３＋ｓ２＋ｓ４＋ｓ６
ｃ１＝ｒ１＋ｓ３＋ｓ４＋ｓ６
ｃ２＝ｒ２＋ｓ２＋ｓ３＋ｓ４＋ｓ５
ｃ３＝ｒ３＋ｓ１＋ｓ３＋ｓ３＋ｓ５＋ｓ６
ｄ１＝ｒ１＋ｓ１＋ｓ２＋ｓ３＋ｓ５
ｄ２＝ｒ２＋ｓ１＋ｓ４＋ｓ５＋ｓ６
ｄ３＝ｒ３＋ｓ２＋ｓ４＋ｓ５
で表され、ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３の各３個の前記分割部分データをそれぞれ連結して、Ａ〜Ｄの４種類の前記単位部分データを生成することを特徴とするデータ分割装置。
【請求項４】
請求項３に記載のデータ分割装置において、
前記復元行列に基づく、前記分割部分データから前記秘密部分データを生成するためのＸＯＲ演算の式は、前記分割データの種類がＡ、Ｂ、Ｃの場合は、
ｓ１＝ａ２＋ｂ１＋ｂ２＋ｃ１
ｓ２＝ａ１＋ａ２＋ａ３＋ｂ１＋ｃ２＋ｃ３
ｓ３＝ａ１＋ｂ２＋ｃ１＋ｃ２
ｓ４＝ａ２＋ａ３＋ｂ３＋ｃ２
ｓ５＝ａ１＋ａ３＋ｂ１＋ｃ３
ｓ６＝ａ１＋ａ２＋ｂ３＋ｃ１＋ｃ２＋ｃ３
で表され、前記分割データの種類がＡ、Ｂ、Ｄの場合は、
ｓ１＝ａ１＋ａ３＋ｂ１＋ｂ２＋ｂ３＋ｄ２
ｓ２＝ａ１＋ａ３＋ｂ２＋ｂ３＋ｄ１＋ｄ２
ｓ３＝ａ１＋ａ２＋ａ３＋ｂ１＋ｂ２＋ｄ３
ｓ４＝ａ１＋ａ２＋ａ３＋ｂ１＋ｄ２＋ｄ３
ｓ５＝ａ２＋ａ３＋ｂ１＋ｂ２＋ｄ１＋ｄ３
ｓ６＝ａ２＋ａ３＋ｂ１＋ｂ２＋ｂ３＋ｄ１
で表され、前記分割データの種類がＡ、Ｃ、Ｄの場合は、
ｓ１＝ａ１＋ａ２＋ａ３＋ｃ２＋ｃ３＋ｄ１
ｓ２＝ａ１＋ｃ１＋ｃ３＋ｄ３
ｓ３＝ａ２＋ｃ１＋ｃ２＋ｃ３＋ｄ１＋ｄ３
ｓ４＝ａ１＋ｃ１＋ｃ２＋ｄ２
ｓ５＝ａ１＋ａ２＋ｃ１＋ｃ２＋ｃ３＋ｄ３
ｓ６＝ａ３＋ｃ２＋ｃ３＋ｄ２
で表され、前記分割データの種類がＢ、Ｃ、Ｄの場合は、
ｓ１＝ｂ３＋ｃ１＋ｃ２＋ｃ３＋ｄ１＋ｄ２
ｓ２＝ｂ１＋ｂ３＋ｃ１＋ｃ２＋ｃ３＋ｄ２
ｓ３＝ｂ１＋ｂ２＋ｂ３＋ｃ１＋ｄ２＋ｄ３
ｓ４＝ｂ１＋ｂ３＋ｃ１＋ｄ３
ｓ５＝ｂ２＋ｃ１＋ｃ２＋ｄ１
ｓ６＝ｂ２＋ｂ３＋ｃ１＋ｃ２＋ｄ１＋ｄ３
で表され、ｓ１〜ｓ６の６個の前記秘密部分データを連結して前記単位部分データを生成することを特徴とするデータ分割装置。
【請求項５】
請求項３に記載のデータ分割装置において、
前記分割処理部は、前記分割行列に基づくＸＯＲ演算の式において、
ｔ１＝ｓ３＋ｓ４
ｔ２＝ｓ１＋ｓ２
ｔ３＝ｓ３＋ｓ５
ｔ４＝ｓ５＋ｓ６
ｔ５＝ｒ３＋ｓ２＋ｓ４
ｔ６＝ｔ２＋ｔ３
ｔ７＝ｒ２＋ｓ１＋ｔ４
の各式を分割中間式として、前記各分割中間式の値を予め算出しておき、前記分割行列に基づくＸＯＲ演算の際に、前記分割中間式と一致する部分に前記分割中間式の値を代入することを特徴とするデータ分割装置。
【請求項６】
請求項４に記載のデータ分割装置において、
前記復元処理部は、前記復元行列に基づくＸＯＲ演算の式において、前記分割データの種類がＡ、Ｂ、Ｃの場合は、
ｗ１＝ｂ２＋ｃ１
ｗ２＝ａ３＋ｂ１
ｗ３＝ａ１＋ｃ３
ｗ４＝ａ２＋ｃ２
ｗ５＝ｗ３＋ｗ４
の各式を復元中間式とし、前記分割データの種類がＡ、Ｂ、Ｄの場合は、
ｘ１＝ａ１＋ａ３
ｘ２＝ａ２＋ｂ１
ｘ３＝ｂ２＋ｂ３＋ｄ２＋ｘ１
ｘ４＝ｄ３＋ｘ１＋ｘ２
ｘ５＝ａ３＋ｂ２＋ｄ１＋ｘ２
の各式を復元中間式とし、前記分割データの種類がＡ、Ｃ、Ｄの場合は、
ｙ１＝ａ２＋ｃ２
ｙ２＝ａ３＋ｃ３
ｙ３＝ｃ２＋ｄ２
ｙ４＝ａ１＋ｃ１
ｙ５＝ｃ３＋ｄ３
の各式を復元中間式とし、前記分割データの種類がＢ、Ｃ、Ｄの場合は、
ｚ１＝ａ１＋ａ３
ｚ２＝ａ２＋ｂ１
の各式を復元中間式として、前記各復元中間式の値を予め算出しておき、前記復元行列に基づくＸＯＲ演算の際に、前記復元中間式と一致する部分に前記復元中間式の値を代入することを特徴とするデータ分割装置。
【請求項７】
秘密データを（３，２，４）ランプ型閾値秘密分散により４個の分割データに分割するデータ分割装置として機能するよう、コンピュータに処理を実行させるデータ分割プログラムであって、
前記コンピュータの分割処理部に、
入力された前記秘密データから抽出した長さＳの単位秘密データを長さＳ／６の６個の秘密部分データに分割するステップと、
長さＳ／６の３個の乱数部分データを生成するステップと、
予め保持されている、前記秘密部分データのうちの１個以上と前記乱数部分データのうちの１個から分割部分データを生成するためのＸＯＲ演算を定義した分割行列を読み込み、読み込んだ前記分割行列と、前記秘密部分データおよび前記乱数部分データとに基づいて、１２個の前記分割部分データを生成するステップと、
それぞれ異なる前記乱数部分データを含むＸＯＲ演算により生成された３個の前記分割部分データを連結して４種類の長さＳ／２の単位分割データを生成するステップと、
前記単位分割データを種類毎に連結して４個の分割データを生成するステップと、を実行させ、
前記コンピュータの分散管理部に、
前記分割データをそれぞれ異なる記憶装置へ出力するステップを実行させることを特徴とするデータ分割プログラム。
【請求項８】
請求項７に記載のデータ分割プログラムにおいて、
前記コンピュータの復元処理部に、
入力された３個の前記分割データのそれぞれから抽出した長さＳ／２の前記単位分割データから３個の前記分割部分データをそれぞれ抽出するステップと、
前記分割データの種類の組み合わせを特定するステップと、
予め保持されている、前記分割データの種類の組み合わせに対応した前記分割行列の部分行列に対する逆行列である復元行列を読み込み、読み込んだ前記復元行列に基づく、抽出した前記分割部分データのＸＯＲ演算により、６個の前記秘密部分データを生成するステップと、
生成した前記秘密部分データを連結して長さＳの前記単位秘密データを生成するステップと、
生成した前記単位秘密データを連結して前記秘密データを生成して出力するステップとを実行させることを特徴とするデータ分割プログラム。
【請求項９】
請求項８に記載のデータ分割プログラムにおいて、
前記分割行列により定義された、前記秘密部分データ（ｓ１〜ｓ６）のうちの１個以上と前記乱数部分データ（ｒ１〜ｒ３）のうちの１個から、１２個の前記分割部分データを生成するためのＸＯＲ演算の式は、
ａ１＝ｒ１＋ｓ１＋ｓ２
ａ２＝ｒ２＋ｓ３＋ｓ４
ａ３＝ｒ３＋ｓ５＋ｓ６
ｂ１＝ｒ１＋ｓ３＋ｓ５
ｂ２＝ｒ２＋ｓ１＋ｓ３＋ｓ５＋ｓ６
ｂ３＝ｒ３＋ｓ２＋ｓ４＋ｓ６
ｃ１＝ｒ１＋ｓ３＋ｓ４＋ｓ６
ｃ２＝ｒ２＋ｓ２＋ｓ３＋ｓ４＋ｓ５
ｃ３＝ｒ３＋ｓ１＋ｓ３＋ｓ３＋ｓ５＋ｓ６
ｄ１＝ｒ１＋ｓ１＋ｓ２＋ｓ３＋ｓ５
ｄ２＝ｒ２＋ｓ１＋ｓ４＋ｓ５＋ｓ６
ｄ３＝ｒ３＋ｓ２＋ｓ４＋ｓ５
で表され、前記コンピュータに、ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３の各３個の前記分割部分データをそれぞれ連結して、Ａ〜Ｄの４種類の前記単位部分データを生成させることを特徴とするデータ分割プログラム。
【請求項１０】
請求項９に記載のデータ分割プログラムにおいて、
前記復元行列に基づく、前記分割部分データから前記秘密部分データを生成するためのＸＯＲ演算の式は、前記分割データの種類がＡ、Ｂ、Ｃの場合は、
ｓ１＝ａ２＋ｂ１＋ｂ２＋ｃ１
ｓ２＝ａ１＋ａ２＋ａ３＋ｂ１＋ｃ２＋ｃ３
ｓ３＝ａ１＋ｂ２＋ｃ１＋ｃ２
ｓ４＝ａ２＋ａ３＋ｂ３＋ｃ２
ｓ５＝ａ１＋ａ３＋ｂ１＋ｃ３
ｓ６＝ａ１＋ａ２＋ｂ３＋ｃ１＋ｃ２＋ｃ３
で表され、前記分割データの種類がＡ、Ｂ、Ｄの場合は、
ｓ１＝ａ１＋ａ３＋ｂ１＋ｂ２＋ｂ３＋ｄ２
ｓ２＝ａ１＋ａ３＋ｂ２＋ｂ３＋ｄ１＋ｄ２
ｓ３＝ａ１＋ａ２＋ａ３＋ｂ１＋ｂ２＋ｄ３
ｓ４＝ａ１＋ａ２＋ａ３＋ｂ１＋ｄ２＋ｄ３
ｓ５＝ａ２＋ａ３＋ｂ１＋ｂ２＋ｄ１＋ｄ３
ｓ６＝ａ２＋ａ３＋ｂ１＋ｂ２＋ｂ３＋ｄ１
で表され、前記分割データの種類がＡ、Ｃ、Ｄの場合は、
ｓ１＝ａ１＋ａ２＋ａ３＋ｃ２＋ｃ３＋ｄ１
ｓ２＝ａ１＋ｃ１＋ｃ３＋ｄ３
ｓ３＝ａ２＋ｃ１＋ｃ２＋ｃ３＋ｄ１＋ｄ３
ｓ４＝ａ１＋ｃ１＋ｃ２＋ｄ２
ｓ５＝ａ１＋ａ２＋ｃ１＋ｃ２＋ｃ３＋ｄ３
ｓ６＝ａ３＋ｃ２＋ｃ３＋ｄ２
で表され、前記分割データの種類がＢ、Ｃ、Ｄの場合は、
ｓ１＝ｂ３＋ｃ１＋ｃ２＋ｃ３＋ｄ１＋ｄ２
ｓ２＝ｂ１＋ｂ３＋ｃ１＋ｃ２＋ｃ３＋ｄ２
ｓ３＝ｂ１＋ｂ２＋ｂ３＋ｃ１＋ｄ２＋ｄ３
ｓ４＝ｂ１＋ｂ３＋ｃ１＋ｄ３
ｓ５＝ｂ２＋ｃ１＋ｃ２＋ｄ１
ｓ６＝ｂ２＋ｂ３＋ｃ１＋ｃ２＋ｄ１＋ｄ３
で表され、前記コンピュータに、ｓ１〜ｓ６の６個の前記秘密部分データを連結して前記単位部分データを生成させることを特徴とするデータ分割プログラム。
【請求項１１】
請求項９に記載のデータ分割プログラムにおいて、
前記コンピュータに、前記分割行列に基づくＸＯＲ演算により前記分割部分データを生成するステップの前に、前記分割行列に基づくＸＯＲ演算の式において、
ｔ１＝ｓ３＋ｓ４
ｔ２＝ｓ１＋ｓ２
ｔ３＝ｓ３＋ｓ５
ｔ４＝ｓ５＋ｓ６
ｔ５＝ｒ３＋ｓ２＋ｓ４
ｔ６＝ｔ２＋ｔ３
ｔ７＝ｒ２＋ｓ１＋ｔ４
の各式を分割中間式として、前記各分割中間式の値を予め算出しておくステップを実行させ、
前記分割行列に基づくＸＯＲ演算により前記分割部分データを生成するステップにおいて、前記分割中間式と一致する部分に前記分割中間式の値を代入することを特徴とするデータ分割プログラム。
【請求項１２】
請求項１０に記載のデータ分割プログラムにおいて、
前記コンピュータに、前記復元行列に基づくＸＯＲ演算により前記秘密部分データを生成するステップの前に、前記復元行列に基づくＸＯＲ演算の式において、前記分割データの種類がＡ、Ｂ、Ｃの場合は、
ｗ１＝ｂ２＋ｃ１
ｗ２＝ａ３＋ｂ１
ｗ３＝ａ１＋ｃ３
ｗ４＝ａ２＋ｃ２
ｗ５＝ｗ３＋ｗ４
の各式を復元中間式とし、前記分割データの種類がＡ、Ｂ、Ｄの場合は、
ｘ１＝ａ１＋ａ３
ｘ２＝ａ２＋ｂ１
ｘ３＝ｂ２＋ｂ３＋ｄ２＋ｘ１
ｘ４＝ｄ３＋ｘ１＋ｘ２
ｘ５＝ａ３＋ｂ２＋ｄ１＋ｘ２
の各式を復元中間式とし、前記分割データの種類がＡ、Ｃ、Ｄの場合は、
ｙ１＝ａ２＋ｃ２
ｙ２＝ａ３＋ｃ３
ｙ３＝ｃ２＋ｄ２
ｙ４＝ａ１＋ｃ１
ｙ５＝ｃ３＋ｄ３
の各式を復元中間式とし、前記分割データの種類がＢ、Ｃ、Ｄの場合は、
ｚ１＝ａ１＋ａ３
ｚ２＝ａ２＋ｂ１
の各式を復元中間式として、前記各復元中間式の値を予め算出しておくステップを実行させ、
前記復元行列に基づくＸＯＲ演算により前記秘密部分データを生成するステップにおいて、前記復元中間式と一致する部分に前記復元中間式の値を代入することを特徴とするデータ分割プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子データを秘匿化する技術に関し、特に、重要データを秘密分散技術により複数の非重要データに分割して秘匿化する際のデータ分割装置およびデータ分割プログラムに適用して有効な技術に関するものである。
【背景技術】
【０００２】
情報システムを有する企業等においては、情報漏洩などの情報セキュリティ事故を防止するため、機密性の高いデータなどの重要なデータを保護する手段を講じる必要がある。これに対し、これらを実現するための様々な手段も提案されている。【０００３】
重要データを保護するための手段として、例えば、企業等が重要データをセキュリティ対策が多重に施されたデータセンターに保管することが考えられる。しかしながら、外部からアクセス可能なプライベートなデータセンターを独自に構築・運用するのは技術面・コスト面等で多大な負荷を要し、容易に実現できるものではない。【０００４】
これに対して第三者が運用してサービスとして外部に提供しているデータセンターを利用することも考えられる。しかし、第三者が運用管理するデータセンターに自社の重要データを保管することはセキュリティ面で高いリスクが伴う。ましてや近年利用が拡大しているクラウドコンピューティング環境における仮想データセンターや仮想サーバに重要データを保管することは非常にリスクが高いことから、重要データを取り扱う業務を行う情報システムをクラウドコンピューティング環境を利用して構築するということがなかなか普及しない一因ともなっている。【０００５】
一方、重要データを保管する際に、データを秘匿化したり改竄を防止したりする手段を講じて保管することも行われている。一般的には、暗号鍵を用いて重要データを暗号化して保管することが行われているが、この場合、暗号化されたデータには重要データの情報が全て含まれている。従って、例えば暗号化データが第三者に取得されたような場合、何らかの理由で当該第三者に暗号鍵も取得、解読された場合は容易に重要データが復元されてしまう。また、暗号鍵を取得されなくとも、暗号鍵が有限長であることから、理論上は有限回数の試行によって暗号化されたデータから重要データが復元されてしまう可能性を有する。【０００６】
これに対し、重要データを強固に秘匿化する手法として、いわゆる秘密分散の技術も用いられている。秘密分散では、重要データを、それだけでは意味のない（重要データを復元・推測できない）複数の非重要データに分割・分散することで、一部の非重要データが第三者に取得された場合でも、第三者による重要データの復元を理論上も不可能とすることができる。【０００７】
秘密分散の手法としては種々のものが提案されているが、例えば、非特許文献１に記載されているような（ｋ，ｎ）閾値秘密分散の手法が従来から用いられている。（ｋ，ｎ）閾値秘密分散では、秘匿すべき秘密データを、ｎ個の分割データに分割する。このｎ個の分割データのうち、少なくともｋ個（ｋ≦ｎ）以上を集めることにより、これらの分割データから秘密データを復元することができる。一方で、集めた分割データの数がｋ個未満の場合は、これらの分割データから秘密データを復元したり内容を推測したりする（秘密データに関する情報を得る）ことができないというものである。【０００８】
従って、例えばいくつかの分割データが第三者により不正に集められたような場合であっても、その数がｋ個未満である場合には秘密データが復元・推測されることがなく、秘密データを強固に秘匿化することができる。また、例えばいくつかの分割データが毀損・滅失等したような場合であっても、その数が（ｎ−ｋ）個以下である（ｋ個以上の分割データが残っている）場合には秘密データを復元することができるため、秘密データの可用性を高めることもできる。【０００９】
この（ｋ，ｎ）閾値秘密分散の手法では、一般的に、多項式演算や剰余演算を用いて秘密データの分割や復元の演算が行われる。しかしながら、これらの演算をコンピュータでの情報処理によって行う場合、演算負荷が大きくなってしまうため、秘密データのデータ量が大きくなるとＣＰＵ（Central Processing Unit）のリソースを大量に消費し、処理性能が悪化するという問題を有している。これに対し、（ｋ，ｎ）閾値秘密分散の処理を、コンピュータでのビット演算に適したビット単位の排他的論理和（eXclusive OR：以下では「ＸＯＲ」と記載し、「＋」の演算子で表す）演算により実現するという手法も提案されている。【００１０】
例えば、特開２０１１−４１３２６号公報（特許文献１）には、元データ（秘密データ）を所定の長さ毎に区切って、複数の元部分データ（秘密部分データ）を生成し、複数の秘密部分データの各々に対応して、秘密データと同じ長さの乱数または秘密データより短い長さの乱数を前記所定の長さ毎に区切って、複数の乱数部分データを生成し、所定の定義式に基づく、秘密部分データと乱数部分データとの排他的論理和演算を行い、複数の分割データを生成することにより、比較的簡単な処理により秘密データを効率的に分割する技術が開示されている。【００１１】
さらに、一般的な（ｋ，ｎ）閾値秘密分散の手法では、秘密データのサイズと、秘密分散を行って生成されたｎ個の各分割データのサイズとがそれぞれ同じとなるため、秘密分散を行った後のｎ個の分割データ全体のデータ量は、秘密データのデータ量のｎ倍となってしまい、データを保管する際の記憶容量やネットワーク帯域などのリソースを浪費してしまうという問題も有している。これに対し、実システムでの利用を考慮して、秘密分散によって生成される分割データのデータ量を小さくするための技術も提案されている。【００１２】
例えば、非特許文献２に記載されているような、いわゆるランプ型と呼ばれる（ｋ，Ｌ，ｎ）閾値秘密分散の手法が提案されている。ランプ型の秘密分散法では、データの秘匿性に対する安全性の条件を緩める代わりに、生成されたｎ個の各分割データのサイズをそれぞれ秘密データのサイズの１／Ｌに縮小することができる。すなわち、ｎ個の分割データ全体のデータ量を、（ｋ，ｎ）閾値秘密分散の場合の１／Ｌに縮小することができる。【００１３】
なお、ランプ型の秘密分散の場合、ｎ個の分割データのうち、少なくともｋ個以上を集めることにより秘密データを復元することができる点は、（ｋ，ｎ）閾値秘密分散の場合と同様である。一方で、集められた分割データの数が（ｋ−Ｌ）個以下（１≦Ｌ≦ｋ）である場合には秘密データが復元・推測されることはないものの、ｋ個未満であっても（ｋ−Ｌ）個より多い数の分割データが集められた場合には、部分的に秘密データの情報が得られてしまうという特性を有し、この点で（ｋ，ｎ）閾値秘密分散とは異なる。なお、Ｌ＝１の場合は、（ｋ，ｎ）閾値秘密分散と同じことになる（いわゆるパーフェクト型）。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２０１１−４１３２６号公報
【非特許文献】
【００１５】
【非特許文献１】A.Shamir、“How to Share a Secret”、Communications of the ACM、vol.22、No.11、pp.612-613、1979
【非特許文献２】山本博資、“（ｋ，Ｌ，ｎ）しきい値秘密分散システム”、電子通信学会論文誌、vol.168-A、No.9、pp.945-952、1985
【発明の概要】
【発明が解決しようとする課題】
【００１６】
近年、ノート型ＰＣ（Personal Computer）やタブレット型ＰＣ、いわゆるスマートフォンなどの携帯可能な情報処理端末が広く利用されるに従って、これらの端末自体の盗難や紛失等に伴う情報漏洩のリスクが高まっている。これに対して、端末内の重要データを含むデータを外部のサーバ等に保管することで端末の紛失等に伴う情報漏洩のリスクを低減することが考えられる。このとき、重要データをそのまま外部のサーバ等に保管するのではなく、例えば、上述した秘密分散の技術を利用して重要データを非重要データに分割・分散して分割データとし、これを外部のサーバ等に分散保管することで、例えば、クラウドコンピューティング環境における仮想データセンターや仮想サーバなどに保管するような場合においても情報漏洩のリスクを低減させることが可能である。【００１７】
しかしながら、これらの携帯端末では、デスクトップ型のＰＣ等に比べて演算処理能力に余裕がないことが通常であり、また、分割データを保管する先のサーバ等にアクセスするためのネットワークについても、無線通信など、帯域幅に余裕がないものであることが多い。従って、秘密分散の処理には、特に効率的かつ高速な処理が求められ、また、生成される分割データのデータ量も小さいものであることが求められる。【００１８】
この点、上述の特許文献１に記載された技術では、秘密部分データと乱数部分データとのＸＯＲ演算により複数の分割データを生成することで、処理の効率化・高速化を図るとともに、ランプ型の閾値秘密分散ではないものの、ｎ個の分割データ全体のデータ量を一般的な（ｋ，ｎ）閾値秘密分散法の場合よりも小さくすることが可能である。【００１９】
特許文献１に記載された技術では、ＸＯＲ演算の対象として、複数の秘密部分データの各々に対応して、原則として秘密データと同じ長さの乱数から秘密部分データと同じ長さに区切った秘密部分データと同数の乱数部分データを必要とする。一方で、秘密データより短い長さの乱数に対しては、同様に秘密部分データと同じ長さに区切って乱数部分データを生成した上で、足りない分は既に生成されている乱数部分データを再利用することで、複数の秘密部分データの各々に対応させるものとしている。このとき、生成される分割データの１つを乱数部分データのみからなるようにし、当該分割データを生成する際に、再利用している乱数部分データの保持を省略して重複を回避することで、乱数部分データのみからなる分割データのデータ量を小さくすることを可能とする。【００２０】
しかしながら、特許文献１に記載された手法では、ｎ個の分割データ全体でのデータ量は小さくなるものの、実際にサイズが小さくなるのは乱数部分データのみからなる１つの分割データのみであり、他の分割データのサイズは秘密データと同じサイズとなる。従って、全体でのデータ量の縮小効果はそれほど大きくならず、また、他の分割データについては送信・保管する際のリソースの消費量が全く削減されないことになる。また、乱数部分データのみからなる分割データがサイズから識別可能となってしまうというリスクが生じるなど、実システムでの利用に際しては課題を有する。【００２１】
一方で、上述したランプ型の（ｋ，Ｌ，ｎ）閾値秘密分散の手法によれば、安全性の条件は若干緩められるものの、ｎ個の各分割データのサイズを１／Ｌに縮小して、全体でのデータ量を１／Ｌに縮小することができる。また、実際の演算処理についても、秘密データを分割したデータと乱数とのＸＯＲ演算とすることにより、コンピュータでの演算処理による分割データの生成を効率化・高速化する手法が提案されている。【００２２】
しかしながら、ＸＯＲ演算により（ｋ，Ｌ，ｎ）閾値秘密分散を行う際の具体的な計算方法（実際の計算式）としては種々のものが考えられ、計算式次第で処理性能は大きく変わる。また、秘密データから秘密分散により分割データを生成する際の処理性能だけでなく、複数の分割データから秘密データを復元する際の処理性能についても合わせて、全体としての処理の効率化・高速化が求められる。【００２３】
そこで本発明の目的は、秘密データを（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散によりｎ個の分割データに分割して秘匿化する際、およびｋ個以上の分割データから（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散により秘密データを復元する際のＸＯＲ演算の処理を全体として効率化および高速化することを可能とするデータ分割装置およびデータ分割プログラムを提供することにある。本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００２４】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、以下のとおりである。【００２５】
本発明の代表的な実施の形態によるデータ分割装置は、秘密データを（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散によりｎ個の分割データに分割して、ｎ個の前記分割データをそれぞれ異なる記憶装置に分散保管するデータ分割装置であって、以下の特徴を有するものである。【００２６】
すなわち、データ分割装置は、前記秘密データから抽出した長さＳの単位秘密データを複数の秘密部分データに分割し、前記秘密部分データと同じ長さで、前記秘密部分データの数の半数の乱数部分データを生成し、前記秘密部分データ、前記乱数部分データ、および前記秘密部分データのうちの１個以上と前記乱数部分データのうちの１個から分割部分データを生成するためのＸＯＲ演算を定義した分割行列に基づいて、複数の前記分割部分データを生成し、それぞれ異なる前記乱数部分データを含むＸＯＲ演算により生成された複数の前記分割部分データを連結してｎ種類の長さＳ／Ｌの単位分割データを生成し、前記単位分割データを種類毎に連結してｎ個の分割データを生成する分割処理部を有することを特徴とする。【００２７】
また、本発明は、コンピュータを上記のようなデータ分割装置として機能させるプログラムにも適用することができる。
【発明の効果】
【００２８】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。【００２９】
本発明の代表的な実施の形態によれば、秘密データを（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散によりｎ個の分割データに分割して秘匿化する際、およびｋ個以上の分割データから（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散により秘密データを復元する際のＸＯＲ演算の処理を全体として効率化および高速化することが可能となる。
【図面の簡単な説明】
【００３０】
【図１】本発明の一実施の形態であるデータ分割装置の構成例について概要を示した図である。
【図２】本発明の一実施の形態における秘密データから秘密分散により分割データを生成する分割処理の流れの例について概要を示したフローチャートである。
【図３】本発明の一実施の形態における秘密データから（３，２，４）ランプ型閾値秘密分散により４つの分割データを生成する処理の例について概要を示した図である。
【図４】本発明の一実施の形態における秘密部分データと乱数部分データから分割部分データを算出する際の例について概要を示した図である。
【図５】本発明の一実施の形態における分割データから秘密分散により秘密データを生成する復元処理の流れの例について概要を示したフローチャートである。
【図６】本発明の一実施の形態における３つの分割データから（３，２，４）ランプ型閾値秘密分散により秘密データを生成する処理の例について概要を示した図である。
【図７】本発明の一実施の形態における分割データ（ａ、ｂ、ｃ）から秘密データを復元するために用いる復元行列を分割行列から得る処理の例を示した図である。
【図８】本発明の一実施の形態における分割データ（ａ、ｂ、ｄ）から秘密データを復元するために用いる復元行列を分割行列から得る処理の例を示した図である。
【図９】本発明の一実施の形態における分割データ（ａ、ｃ、ｄ）から秘密データを復元するために用いる復元行列を分割行列から得る処理の例を示した図である。
【図１０】本発明の一実施の形態における分割データ（ｂ、ｃ、ｄ）から秘密データを復元するために用いる復元行列を分割行列から得る処理の例を示した図である。
【図１１】本発明の一実施の形態における分割部分データ（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３）から秘密部分データを算出する際の例について概要を示した図である。
【図１２】本発明の一実施の形態における分割部分データ（ａ１〜ａ３、ｂ１〜ｂ３、ｄ１〜ｄ３）から秘密部分データを算出する際の例について概要を示した図である。
【図１３】本発明の一実施の形態における分割部分データ（ａ１〜ａ３、ｃ１〜ｃ３、ｄ１〜ｄ３）から秘密部分データを算出する際の例について概要を示した図である。
【図１４】本発明の一実施の形態における分割部分データ（ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）から秘密部分データを算出する際の例について概要を示した図である。
【発明を実施するための形態】
【００３１】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一部には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００３２】
本発明の一実施の形態であるデータ分割装置は、秘密データを（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散によりｎ個の分割データに分割して、これらの分割データをそれぞれ異なるサーバ等の記憶装置に分散保管するものである。これにより、分割データの紛失・盗難・不正取得等に対する秘密データの秘匿性を高めるとともに、分割データの毀損・滅失等に対する秘密データの可用性を高めることを可能とする。また、ランプ型の秘密分散を用いることから、安全性の条件は若干緩められるものの、ｎ個の各分割データのサイズを１／Ｌに縮小して、全体でのデータ量を（ｋ，ｎ）閾値秘密分散の場合と比べて１／Ｌに縮小する。これにより、各分割データを送信・保管する際のネットワーク帯域や記憶領域などのリソース使用量を低減させる。
【００３３】
また、本実施の形態では、（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散において、処理を効率化・高速化してＣＰＵリソースの使用量を低減させるため、公知の技術と同様に、コンピュータでのビット演算に適するよう、秘密データを分割した秘密部分データと、これと同じ長さの乱数部分データとのＸＯＲ演算に基づいて分割データを生成する。さらに、本実施の形態では、具体的に、（３，２，４）ランプ型閾値秘密分散において、ＸＯＲ演算を行うための計算式および計算手順を調整して、秘密データから秘密分散により複数の分割データを生成する際、および複数の分割データから秘密データを復元する際の処理性能を全体として向上させる。
【００３４】
＜システム構成＞
図１は、本発明の一実施の形態であるデータ分割装置の構成例について概要を示した図である。データ分割装置１００は、例えば、ユーザが利用するＰＣや携帯端末などの情報処理端末、もしくはこれら複数の情報処理端末が接続されるファイルサーバ等、ユーザにより秘密分散の対象の秘密データ４００が作成され、もしくはこれを保持する一般的なコンピュータ機器からなる。
【００３５】
データ分割装置１００は、インターネット等のネットワーク３００を介して複数のサーバ２００に接続可能となっている。サーバ２００の数は、（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散におけるｎ個（本実施の形態では（３，２，４）ランプ型閾値秘密分散であるため４個）以上であることが望ましい。これらのサーバ２００は、それぞれ、データ分割装置１００によって秘密データ４００から秘密分散により生成されネットワーク３００を介して送信されてきた分割データ４１０を、ＨＤＤ（Hard Disk Drive）等の記憶装置に保管することができるファイルサーバやストレージ機器等からなる。
【００３６】
データ分割装置１００は、上述した機能を実現するため、例えば、図示しないＯＳ（Operating System）上で稼働するソフトウェアプログラムとして実装される分割処理部１１０、分散管理部１２０、復元処理部１３０、およびインタフェース部１４０などの各部を有する。
【００３７】
分割処理部１１０は、例えば、後述するインタフェース部１４０を介してユーザからセキュアな保管を指示された秘密データ４００から、後述するＸＯＲによる演算式を定義した分割行列１１１、および分割中間式１１２に基づいて、所定の手順に従って（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散（本実施の形態では（３，２，４）ランプ型閾値秘密分散）により各サーバ２００に分散保管するｎ個（本実施の形態では４個）の分割データ４１０を生成する。また、上記のＸＯＲによる演算の際に用いる乱数を生成する乱数生成部１１３を有する。なお、乱数生成の手法は特に限定されず、所定の長さ以上の乱数を生成することができるものであれば、任意の公知の技術を用いることができる。
【００３８】
分散管理部１２０は、例えば、分割処理部１１０により秘密データ４００から生成された各分割データ４１０について、設定情報１２２の設定内容に基づく所定の条件に従って各サーバ２００に送信して分散保管するとともに、各分割データ４１０がいずれのサーバ２００に保管されているかの対応に係る情報を分散状況１２１に記録して管理する。設定情報１２２には、例えば、分散保管先となる各サーバ２００に対するアクセス情報（ＩＰアドレスやホスト名等）、ｎ個（本実施の形態では４個）より多数のサーバ２００が存在する場合にｎ個のサーバ２００を選択するための基準や条件（例えばサーバ２００の優先順位や順序付けされたリスト、ローテーションする際の方法等）などを予め設定しておくことができる。
【００３９】
また、分散管理部１２０は、後述する復元処理部１３０による秘密データ４００の復元の際に、復元処理部１３０からの要求に基づいて、分散状況１２１の内容、および設定情報１２２の設定内容に基づく所定の条件に従って、各サーバ２００から、秘密データ４００を復元するためのｍ個の分割データ４１０を収集して復元処理部１３０に受け渡す。
【００４０】
なお、収集する分割データ４１０の個数ｍの値は、秘密データ４００を復元するために必要な分割データ４１０の数ｋ以上である必要があり、また、ｎ個全ての分割データ４１０を収集するものとしてもよい（すなわちｋ≦ｍ≦ｎ。本実施の形態ではｍ＝３もしくは４）。設定情報１２２には、例えば、ｍの値や、ｍ＜ｎである場合に、対象となるｍ個のサーバ２００を選択するための基準や条件、障害等により対象のサーバ２００から分割データ４１０を取得できなかった場合の代替となるサーバ２００の決定方法などを予め設定しておくことができる。
【００４１】
なお、サーバ２００の障害等により、分割データ４１０の分散保管時にｎ個の分割データ４１０のうちいずれかを各サーバ２００に保管できなかった場合や、分割データ４１０の収集時にｋ個以上収集できなかった場合は、ユーザに対してエラーを応答するようにしてもよい。また、各サーバ２００との間で分割データ４１０の送受信を行う際に、データ分割装置１００および各サーバ２００がそれぞれ分割データ４１０に対して所定の暗号化を施した上で送受信することで、情報漏洩のリスクをさらに低減させるようにしてもよい。
【００４２】
復元処理部１３０は、例えば、インタフェース部１４０を介してユーザから参照や編集等の利用を指示された秘密データ４００について、これを復元するために必要な数以上の分割データ４１０を分散管理部１２０に要求して取得する。さらに、取得した分割データ４１０から、後述するＸＯＲによる演算式を定義した復元行列１３１、および復元中間式１３２に基づいて、所定の手順に従って（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散（本実施の形態では（３，２，４）ランプ型閾値秘密分散）により秘密データ４００を復元する。
【００４３】
インタフェース部１４０は、データ分割装置１００（もしくはデータ分割装置１００に対する図示しないクライアント端末）における画面表示等のユーザインタフェースやデータの送受信などの入出力機能を有する。ユーザは、例えば、一般的なＯＳが有するファイル管理用の画面等を利用して、データ分割装置１００の機能を利用することができる。
【００４４】
例えば、ファイル管理用の画面においてユーザが重要データを特定のフォルダ等にドラッグ＆ドロップなどの簡易な操作により移動する。これをトリガとして、分割処理部１１０および分散管理部１２０によって、自動的に当該重要データを秘密データ４００としてｎ個（本実施の形態では４個）の分割データ４１０を生成し、各分割データ４１０をユーザに意識させずに各サーバ２００に分散保管することができる。なお、このとき秘密データ４００はデータ分割装置１００（およびデータ分割装置１００に対するユーザのクライアント端末）から削除するが、ファイル管理用の画面上では、ユーザに意識させないよう、例えば、秘密データ４００に対応するダミーファイル等を作成して残しておく。
【００４５】
また、例えば、ユーザは、ファイル管理用の画面において特定のフォルダにて管理されている秘密データ４００のダミーファイル等に対して操作を行うことで、秘密データ４００に対する参照や編集等の操作を行うことができる。すなわち、ダミーファイル等に対する操作をトリガとして、分散管理部１２０および復元処理部１３０によって、ダミーファイル等に対応する秘密データ４００について、自動的に各サーバ２００からｍ個（ｋ≦ｍ≦ｎ、本実施の形態では３個もしくは４個）の分割データ４１０を収集し、秘密データ４００を復元してユーザに利用可能とすることができる。
【００４６】
＜処理フロー（分割処理）＞
図２は、データ分割装置１００の分割処理部１１０における、秘密データ４００から秘密分散により分割データ４１０を生成する分割処理の流れの例について概要を示したフローチャートである。なお、本実施の形態では、上述したように、（３，２，４）ランプ型閾値秘密分散により秘密分散処理を行うものとする。また、図３は、秘密データ４００から（３，２，４）ランプ型閾値秘密分散により４個の分割データ４１０を生成する処理の例について概要を示した図である。
【００４７】
インタフェース部１４０を介してユーザから秘密分散の対象となる重要データが指定されると、分割処理部１１０は、まず、当該重要データを秘密データ４００とし、秘密データ４００の先頭から所定の長さＳの単位秘密データを抽出する（Ｓ０１）。この単位秘密データは、ＸＯＲ演算による秘密分散処理を行う際の処理単位となるデータであり、本実施の形態では、長さＳは６の倍数ビットの任意の長さであるものとする。なお、秘密データ４００の長さがＳに満たない場合は、例えば、秘密データ４００に対してＳに満たない分をゼロ等の所定のデータでパディングして長さＳの単位秘密データを得るものとする。
【００４８】
次に、抽出した単位秘密データ４０１を分割して秘密部分データを６個生成する（Ｓ０２）。具体的には、図３に示すように、秘密データ４００から抽出した長さＳの単位秘密データ４０１を６等分して、長さＳ／６の秘密部分データ４０２を６個（ｓ１〜ｓ６）生成する。
【００４９】
さらに、乱数生成部１１３により、秘密部分データ４０２と同じ長さ（Ｓ／６）の乱数部分データ４０３を秘密部分データ４０２の数の半数である３個生成する（Ｓ０３）。具体的には、図３に示すように、秘密部分データ４０２と同じ長さＳ／６の乱数部分データ４０３を３個（ｒ１〜ｒ３）生成する。乱数部分データ４０３の生成に際しては、例えば、乱数生成部１１３がｒ１〜ｒ３の３個をそれぞれ個別に生成してもよいし、乱数生成部１１３がＳ／２より長い乱数を１個生成して、分割処理部１１０がこれを区切ってＳ／６の長さの乱数を３個抽出するようにしてもよい。
【００５０】
次に、後述する分割部分データを生成するためのＸＯＲ演算を行う際に用いるために予め定義された複数の分割中間式１１２のそれぞれについて、秘密部分データ４０２（ｓ１〜ｓ６）と乱数部分データ４０３（ｒ１〜ｒ３）に基づいてＸＯＲ演算を行って値を算出しておく（Ｓ０４）。この分割中間式１１２は、後述する分割部分データを生成するためのＸＯＲ演算の全体において、複数回繰り返し現れるＸＯＲ演算の式を分割中間式１１２として抽出したものである。この分割中間式１１２の値を予め計算して保持しておき、後述する分割行列１１１に基づくＸＯＲ演算の際に計算結果を利用することで、内容が重複するＸＯＲ演算を極力廃し、処理の効率化・高速化を図る。なお、分割中間式１１２の詳細については後述する。
【００５１】
次に、秘密部分データ４０２（ｓ１〜ｓ６）と乱数部分データ４０３（ｒ１〜ｒ３）に基づいて、分割行列１１１に定義された内容に基づいてＸＯＲ演算を行い、１２個の分割部分データ４１２を生成する（Ｓ０５）。具体的には、図３に示すように、ＸＯＲ演算を定義した分割行列１１１と、乱数部分データ４０３（ｒ１〜ｒ３）および秘密部分データ４０２（ｓ１〜ｓ６）を要素とする９行１列の秘密データ行列１１４との乗算によって、それぞれが長さＳ／６の１２個の分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を得る。
【００５２】
すなわち、分割行列１１１と秘密データ行列１１４との乗算によって得られる以下の各式によって１２個の分割部分データ４１２を得る。
【００５３】
ａ１＝ｒ１＋ｓ１＋ｓ２                    …式１
ａ２＝ｒ２＋ｓ３＋ｓ４                    …式２
ａ３＝ｒ３＋ｓ５＋ｓ６                    …式３
ｂ１＝ｒ１＋ｓ３＋ｓ５                    …式４
ｂ２＝ｒ２＋ｓ１＋ｓ３＋ｓ５＋ｓ６        …式５
ｂ３＝ｒ３＋ｓ２＋ｓ４＋ｓ６              …式６
ｃ１＝ｒ１＋ｓ３＋ｓ４＋ｓ６              …式７
ｃ２＝ｒ２＋ｓ２＋ｓ３＋ｓ４＋ｓ５        …式８
ｃ３＝ｒ３＋ｓ１＋ｓ３＋ｓ３＋ｓ５＋ｓ６  …式９
ｄ１＝ｒ１＋ｓ１＋ｓ２＋ｓ３＋ｓ５        …式１０
ｄ２＝ｒ２＋ｓ１＋ｓ４＋ｓ５＋ｓ６        …式１１
ｄ３＝ｒ３＋ｓ２＋ｓ４＋ｓ５              …式１２
なお、上記各式における演算子の“＋”はＸＯＲを意味する。また、実際の計算の際には、後述するように、上記各式において各分割中間式１１２と一致するＸＯＲ演算の部分に、ステップＳ０４で予め計算しておいた各分割中間式１１２の値を代入することで、全体でのＸＯＲ演算の数を低減させる。
【００５４】
次に、１２個の分割部分データ４１２から４個（４種類）の単位分割データを生成する（Ｓ０６）。具体的には、図３に示すように、ａ１〜ａ３の分割部分データ４１２を連結して、長さＳ／２の単位分割データ４１１ａを生成する。同様に、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３の分割部分データ４１２をそれぞれ連結して、単位分割データ４１１ｂ〜ｄを生成する。次に、生成した４個の単位分割データ４１１をそれぞれ対応する種類の分割データ４１０の末尾等に連結する（Ｓ０７）。具体的には、図３に示すように、長さＳ／２の単位分割データ４１１ａ〜ｄを、それぞれ分割データＡ（４１０ａ）〜分割データＤ（４１０ｄ）の末尾に連結する。なお、連結すべき分割データ４１０が存在しない場合は、各単位分割データ４１１自身をそれぞれ分割データ４１０とする。
【００５５】
なお、各分割データ４１０には、自身が分割データＡ（４１０ａ）、分割データＢ（４１０ｂ）、分割データＣ（４１０ｃ）、もしくは分割データＤ（４１０ｄ）のいずれの種類であるかを識別する情報をヘッダ等に付加するものとする。これにより、復元時に取得した各分割データ４１０について、これを構成する単位分割データ４１１が、ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、もしくはｄ１〜ｄ３のいずれの分割部分データ４１２により構成されているのかをヘッダ等の情報から知ることができる。この他にも、例えば、ステップＳ０１において、秘密データ４００の長さがＳに満たないためにゼロ等のデータをパディングして単位秘密データ４０１を抽出した場合の、末尾の単位秘密データ４０１の有効な長さの情報などを付加してもよい。
【００５６】
その後、秘密データ４００にまだ処理していない残部があるか否かを判定し（Ｓ０８）、残部がある場合にはステップＳ０１に戻って上記の一連の処理を秘密データ４００に残部がなくなるまで繰り返す。秘密データ４００に未処理の残部がない場合は、分割処理を終了する。
【００５７】
なお、図３に示した分割行列１１１を用いて上記の処理により得られる４個の分割データ４１０（分割データＡ〜Ｄ）は、（３，２，４）ランプ型閾値秘密分散の要件を満たすものである。すなわち、各分割データ４１０を構成する各単位分割データ４１１のそれぞれからは、秘密データ４００を構成する単位秘密データ４０１の情報（ｓ１〜ｓ６の秘密部分データ４０２の情報）を全く得ることはできない。
【００５８】
例えば、第三者が、分割データＡ（４１０ａ）を取得した場合、これを構成する単位分割データ４１１ａからはａ１〜ａ３の分割部分データ４１２の情報を得ることができる。仮に、これらの分割部分データ４１２が、上記の式１〜式３の３個の式から生成されたものであることを当該第三者が知ったとしても、式１〜式３からなる、ｒ１〜ｒ３、およびｓ１〜ｓ６を変数とする連立方程式を解くことはできない。
【００５９】
また、式１〜式３からなる連立方程式からは、乱数成分であるｒ１〜ｒ３を消去することができないため、ｓ１〜ｓ６の秘密部分データ４０２のいずれの情報（解）も得ることができない（すなわち、正規化した情報エントロピーは１である）。従って、秘密データ４００（ｓ１〜ｓ６の秘密部分データ４０２からなる単位秘密データ４０１）の秘匿性は保たれる。これは、分割データＢ（４１０ｂ）〜分割データＤ（４１０ｄ）の各分割データ４１０についても同様である。
【００６０】
換言すれば、４個の異なる単位分割データ４１１（例えば、単位分割データ４１１ａ）をそれぞれ構成する３個の分割部分データ４１２（例えば、ａ１〜ａ３）をそれぞれ得るための３個の計算式（例えば、上記の式１〜式３）において、各式が、「１個または相異なる２個以上の秘密部分データ４０２（ｓ１〜ｓ６）と１個または相異なる２個以上の乱数部分データ４０３（ｒ１〜ｒ３）のＸＯＲ演算」として表されるように分割行列１１１を構成すれば、各分割データ４１０（単位分割データ４１１）は乱数データと同等の乱数性を有することになるため、１個の分割データ４１０からは秘密データ４００（単位秘密データ４０１）の情報を得ることはできないことになる。なお、本実施の形態では、３個の各計算式がそれぞれ互いに異なる１個の乱数部分データ４０３のみ（例えば、式１はｒ１のみ、式２はｒ２のみ、式３はｒ３のみ）を有するものとしている。
【００６１】
一方、３個の異なる分割データ４１０があれば、秘密データ４００を復元することができる。すなわち、３個の異なる分割データ４１０を構成する各単位分割データ４１１からは、秘密データ４００を構成する単位秘密データ４０１の情報（ｓ１〜ｓ６の秘密部分データ４０２の情報）の全てを得ることができる。例えば、ユーザが分割データＡ（４１０ａ）、分割データＢ（４１０ｂ）、分割データＣ（４１０ｃ）の３個の分割データ４１０を集めた場合、上記と同様に、式１〜式９の９個の独立した式からなる連立方程式が得られることになる。これを解くことにより、ｒ１〜ｒ３、およびｓ１〜ｓ３の９個の変数の情報（解）を得ることができ、ｓ１〜ｓ６の秘密部分データ４０２の情報から単位秘密データ４０１および秘密データ４００を復元することができる（すなわち、正規化した情報エントロピーはゼロである）。
【００６２】
なお、２個の異なる分割データ４１０がある場合には、秘密データ４００の情報の一部を得ることが可能である。例えば、ユーザが分割データＡ（４１０ａ）、分割データＢ（４１０ｂ）の２個の分割データ４１０を集めた場合、上記と同様に、式１〜式６の６個の式からなる連立方程式が得られることになる。この連立方程式では、ｒ１〜ｒ３、ｓ１〜ｓ６の全ての情報（解）を得ることはできないが、例えば、式１と式４、式２と式５、式３と式６によりそれぞれ乱数成分であるｒ１〜ｒ３を消去することができるため、ｓ１〜ｓ６の間の関係を簡易な一次式として得ることができる。理論上は、これらの式からｓ１〜ｓ６のうち半分の情報を得ることが可能である（正規化した情報エントロピーは０．５である）。
【００６３】
本実施の形態では、図３に示した（３，２，４）ランプ型閾値秘密分散での分割処理に用いる分割行列１１１は、後述する分割データ４１０からの秘密データ４００の復元処理に用いる復元行列１３１と合わせて、分割・復元の秘密分散処理全体でのＸＯＲ演算の数が少なくなるよう調整している。具体的には、分割行列１１１として成立し得る行列の各パターン（およびこれに対して得られる復元行列１３１）について、後述する中間式による影響も考慮して、分割・復元の秘密分散処理全体でのＸＯＲ演算の数を解析し、数が少なくなる、すなわち全体として処理効率のよいパターンを得た。図３に示した分割行列１１１は、上記の手順により得た調整された分割行列１１１である。
【００６４】
さらに本実施の形態では、図２のステップＳ０５において上記の式１〜式１２に基づいて分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を算出する際に実行されるＸＯＲ演算（式１〜式１２における“＋”演算子）の回数が少なくなるよう、分割中間式１１２を利用する。すなわち、上記の式１〜式１２において複数回繰り返し現れるＸＯＲ演算の式を予め分割中間式１１２として定義しておき、図２のステップＳ０４において、各分割中間式１１２の値を予め計算しておく。その後、ステップＳ０５で式１〜式１２におけるＸＯＲ演算により分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を算出する際に、各分割中間式１１２と一致する部分については、予め計算された分割中間式１１２の計算結果を利用することで、重複するＸＯＲ演算を極力廃し、処理の効率化・高速化を図る。
【００６５】
＜分割中間式＞
図４は、秘密部分データ４０２（ｓ１〜ｓ６）と乱数部分データ４０３（ｒ１〜ｒ３）から分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を算出する際の例について概要を示した図である。図４の上段の図は、図３に示した分割行列１１１の内容を模式的に表として示しており、表の行・列は、図３に示した分割行列１１１の行・列に対応している。各行で、“１”が立っている列に対応する要素（例えば、１行目の場合はｒ１、ｓ１、およびｓ２）についてＸＯＲ演算する（例えば、１行目の場合はｒ１＋ｓ１＋ｓ２）ことで、各行に対応する分割部分データ４１２（例えば、１行目の場合はａ１）を得ることができることを示している。すなわち、図４に示す分割行列１１１の表の各行は、それぞれ上記の式１〜式１２に示したＸＯＲ演算の内容を示している。
【００６６】
ここで、本実施の形態では、図４の下段に示すように、ｔ１〜ｔ７の７個の分割中間式１１２を定義しており、これらはそれぞれ“１”が立っている列（図４の上段に示す分割行列１１１の列に対応する）により、以下の式の演算を表している。
【００６７】
ｔ１＝ｓ３＋ｓ４          …式１３
ｔ２＝ｓ１＋ｓ２          …式１４
ｔ３＝ｓ３＋ｓ５          …式１５
ｔ４＝ｓ５＋ｓ６          …式１６
ｔ５＝ｒ３＋ｓ２＋ｓ４    …式１７
ｔ６＝ｔ２＋ｔ３          …式１８
ｔ７＝ｒ２＋ｓ１＋ｔ４    …式１９
また、上記のｔ１〜ｔ７の分割中間式１１２を用いることにより、上記の式１〜式１２がそれぞれ以下の式により簡略化されることを表している。
【００６８】
ａ１＝ｒ１＋ｔ２                …式１’
ａ２＝ｒ２＋ｔ１                …式２’
ａ３＝ｒ３＋ｔ４                …式３’
ｂ１＝ｒ１＋ｔ３                …式４’
ｂ２＝ｓ３＋ｔ７                …式５’
ｂ３＝ｓ６＋ｔ５                …式６’
ｃ１＝ｒ１＋ｓ６＋ｔ１          …式７’
ｃ２＝ｒ２＋ｓ２＋ｓ５＋ｔ１    …式８’
ｃ３＝ｒ３＋ｓ６＋ｔ６          …式９’
ｄ１＝ｒ１＋ｔ６                …式１０’
ｄ２＝ｓ４＋ｔ７                …式１１’
ｄ３＝ｓ５＋ｔ５                …式１２’
ここで、簡略化する前の上記の式１〜式１２では、２入力のＸＯＲ演算の数（すなわち“＋”演算子の数）は３８個であるが、上記の式１’〜式１２’（および分割中間式１１２である式１３〜式１９）では、ＸＯＲ演算の数は２５個に大きく低減されている（低減率３４．２％）。従って、分割行列１１１に基づくＸＯＲ演算を直接実行する（上記の式１〜式１２）よりも、分割中間式１１２（上記の式１３〜式１９）を予め計算した上で、分割中間式１１２を利用して分割行列１１１に基づくＸＯＲ演算を実行する（上記の式１’〜式１２’）ことで、ＸＯＲ演算に係る処理の効率化・高速化することができる。
【００６９】
なお、分割行列１１１の内容を調整することで、分割処理時のＸＯＲ演算の数を２５個からさらに低減させることも可能であるが、この場合は、後述する復元処理時のＸＯＲ演算の回数が増え、分割・復元の処理全体としてはＸＯＲ演算の数は必ずしも最小とはならない。分割・復元の処理全体として考えた場合に、解析により処理効率がよい（ＸＯＲ演算の数が少ない）ものとして得られたものが、図３に示した分割行列１１１である。
【００７０】
＜処理フロー（復元処理）＞
図５は、データ分割装置１００の復元処理部１３０における、分割データ４１０から秘密分散により秘密データ４００を生成する復元処理の流れの例について概要を示したフローチャートである。なお、本実施の形態では、上述したように、（３，２，４）ランプ型閾値秘密分散により秘密分散処理を行うものとする。また、図６は、３個の分割データ４１０から（３，２，４）ランプ型閾値秘密分散により秘密データ４００を生成（復元）する処理の例について概要を示した図である。
【００７１】
まず、復元処理の前処理として、インタフェース部１４０を介してユーザから参照や編集等の利用を行う重要データ、すなわち復元の対象となる重要データが指定されると、復元処理部１３０は、この重要データを秘密データ４００として、これを復元するために必要な数以上（本実施の形態では３個以上）の分割データ４１０を分散管理部１２０に要求して取得する。
【００７２】
図６の例では、分割データ４１０ａ、４１０ｂ、４１０ｃの３個の分割データ４１０を復元に用いる場合を示している。これには、分散管理部１２０を介して分割データ４１０ａ、４１０ｂ、４１０ｃの３個の分割データ４１０を取得し、これらを復元に用いる場合、および、分散管理部１２０を介して４個全ての分割データ４１０を取得し、そのうちの分割データ４１０ａ、４１０ｂ、４１０ｃの３個を復元に用いる場合が含まれる。
【００７３】
復元処理部１３０は、３個の分割データ４１０を取得すると、まず、３個の分割データ４１０の先頭からそれぞれ所定の長さＳ／２の単位分割データ４１１（ａ、ｂ、ｃ）を抽出する（Ｓ１１）。この単位分割データ４１１は、ＸＯＲ演算による秘密分散処理を行う際の処理単位となるデータである。次に、抽出した各単位分割データ４１１について、それぞれいずれの種類のものであるかを特定する（Ｓ１２）。図６の例では、各分割データ４１０（ａ、ｂ、ｃ）から抽出した各単位分割データ４１１（ａ、ｂ、ｃ）について、ヘッダ等に付加された情報等に基づき、それぞれが単位分割データ４１１ａ、４１１ｂ、４１１ｃ（もしくは単位分割データ４１１ｄ）のいずれであるかを特定する。
【００７４】
次に、抽出した各単位分割データ４１１からそれぞれ、３個の分割部分データ４１２を抽出する（Ｓ１３）。具体的には、図６に示すように、長さＳ／２の３個の単位分割データ４１１（ａ、ｂ、ｃ）をそれぞれ３等分して、長さＳ／６の分割部分データ４１２を３個ずつ（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３）生成する。
【００７５】
次に、後述する秘密部分データ４０２を生成するためのＸＯＲ演算を行う際に用いるために、ステップＳ１２で特定した各単位分割データ４１１の種類の組み合わせ毎に定義された複数の復元中間式１３２のそれぞれについて、ステップＳ１３で抽出した分割部分データ４１２に基づいてＸＯＲ演算を行って値を算出しておく（Ｓ１４）。この復元中間式１３２は、上記の分割中間式１１２と同様に、後述する秘密部分データ４０２を生成するためのＸＯＲ演算の全体において、複数回繰り返し現れるＸＯＲ演算の式を復元中間式１３２として抽出したものである。この復元中間式１３２の値を予め計算して保持しておき、復元行列１３１に基づくＸＯＲ演算の際に計算結果を利用することで、内容が重複するＸＯＲ演算を極力廃し、処理の効率化・高速化を図る。なお、復元中間式１３２の詳細については後述する。
【００７６】
次に、ステップＳ１３で抽出した分割部分データ４１２に基づいて、ステップＳ１２で特定した各単位分割データ４１１の種類の組み合わせ毎に定義された復元行列１３１に定義された内容に従ってＸＯＲ演算を行い、６個の秘密部分データ４０２を生成する（Ｓ１５）。具体的には、図６に示すように、単位分割データ４１１の種類の組み合わせ（図６の例では、ａ、ｂ、ｃの３個の単位分割データ４１１）毎にＸＯＲ演算を定義した復元行列１３１（図６の例では復元行列１３１ａ）と、分割部分データ４１２（図６の例ではａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３）を要素とする９行１列の分割データ行列１３３ａとの乗算によって、それぞれが長さＳ／６の６個の秘密部分データ４０２（ｓ１〜ｓ６）を得る。
【００７７】
すなわち、図６の例に示すように、分割データ４１０ａ、４１０ｂ、４１０ｃの３個の分割データ４１０に基づく場合は、復元行列１３１ａと、分割データ行列１３３ａとの乗算によって得られる以下の各式によって６個の秘密部分データ４０２を得る。
【００７８】
ｓ１＝ａ２＋ｂ１＋ｂ２＋ｃ１                …式２０
ｓ２＝ａ１＋ａ２＋ａ３＋ｂ１＋ｃ２＋ｃ３    …式２１
ｓ３＝ａ１＋ｂ２＋ｃ１＋ｃ２                …式２２
ｓ４＝ａ２＋ａ３＋ｂ３＋ｃ２                …式２３
ｓ５＝ａ１＋ａ３＋ｂ１＋ｃ３                …式２４
ｓ６＝ａ１＋ａ２＋ｂ３＋ｃ１＋ｃ２＋ｃ３    …式２５
なお、上記の行列の乗算からは、乱数部分データ４０３（ｒ１〜ｒ３）も得ることができるが、秘密データ４００の復元に際しては不要であるため処理を省略する。また、分割処理時と同様に、実際の計算の際には、後述するように、式２０〜式２５の各式において各復元中間式１３２と一致するＸＯＲ演算の部分に、ステップＳ１４で予め計算しておいた各復元中間式１３２の値を代入することで、全体でのＸＯＲ演算の数を低減させる。
【００７９】
次に、６個の秘密部分データ４０２から単位秘密データ４０１を生成する（Ｓ１６）。具体的には、図６に示すように、ｓ１〜ｓ６の秘密部分データ４０２を連結して、長さＳの単位秘密データ４０１を生成する。次に、生成した単位秘密データ４０１を秘密データ４００の末尾等に連結する（Ｓ１７）。具体的には、図６に示すように、長さＳの単位秘密データ４０１を秘密データ４００の末尾に連結する。なお、連結すべき秘密データ４００が存在しない場合は、単位秘密データ４０１自身を秘密データ４００とする。
【００８０】
その後、各分割データ４１０にまだ処理していない残部があるか否かを判定し（Ｓ１８）、残部がある場合にはステップＳ１１に戻って上記の一連の処理を各分割データ４１０に残部がなくなるまで繰り返す。各分割データ４１０に未処理の残部がない場合は、復元処理を終了する。
【００８１】
なお、上述した手順によって、図６に示したような復元行列１３１に基づいて得られる秘密データ４００（ｓ１〜ｓ６の秘密部分データ４０２からなる単位秘密データ４０１）は、元の重要データの内容と同じものである。これは、ステップＳ１２で特定した各単位分割データ４１１の種類の組み合わせ毎に定義された複数の復元行列１３１が、上記の分割行列１１１における当該組み合わせに係る部分から求められた逆行列であるためである。
【００８２】
図７は、分割データ４１０（ａ、ｂ、ｃ）から秘密データ４００を復元するために用いる復元行列１３１ａを分割行列１１１から得る処理の例を示した図である。復元行列１３１ａを得るためには、図７の上段に示すように、分割行列１１１のうち、復元の際に用いられる分割データ４１０（ａ、ｂ、ｃ）に対応する行、すなわちこれに対応する分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３）を得ることができる９行（図中の網掛け部分）を抽出して、図７の下段左側に示すような９行９列の部分行列を得る。
【００８３】
この部分行列から、例えば掃き出し法などにより、図７の下段右側に示すような逆行列を求める。この逆行列が復元行列１３１ａとなる。なお、分割行列１１１における要素の値の“１”は、数値の１ではなくＸＯＲの対象となる要素を決定するビットを示している。従って、例えば掃き出し法を用いて逆行列を求める際に、手順の課程での減算処理により要素の値が−１になった場合でも“１”として取り扱うことにより、復元行列１３１を得ることができる。
【００８４】
同様に、図８は、分割データ４１０（ａ、ｂ、ｄ）から秘密データ４００を復元するために用いる復元行列１３１ｂを分割行列１１１から得る処理の例を示した図である。図８の上段に示すように、分割行列１１１のうち、復元の際に用いられる分割データ４１０（ａ、ｂ、ｄ）に対応する行、すなわちこれに対応する分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｄ１〜ｄ３）を得ることができる９行（図中の網掛け部分）を抽出して、図８の下段左側に示すような９行９列の部分行列を得る。この部分行列から求めた逆行列が復元行列１３１ｂとなる。
【００８５】
同様に、図９は、分割データ４１０（ａ、ｃ、ｄ）から秘密データ４００を復元するために用いる復元行列１３１ｃを分割行列１１１から得る処理の例を示した図である。図９の上段に示すように、分割行列１１１のうち、復元の際に用いられる分割データ４１０（ａ、ｃ、ｄ）に対応する行、すなわちこれに対応する分割部分データ４１２（ａ１〜ａ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を得ることができる９行（図中の網掛け部分）を抽出して、図９の下段左側に示すような９行９列の部分行列を得る。この部分行列から求めた逆行列が復元行列１３１ｃとなる。
【００８６】
同様に、図１０は、分割データ４１０（ｂ、ｃ、ｄ）から秘密データ４００を復元するために用いる復元行列１３１ｄを分割行列１１１から得る処理の例を示した図である。図１０の上段に示すように、分割行列１１１のうち、復元の際に用いられる分割データ４１０（ｂ、ｃ、ｄ）に対応する行、すなわちこれに対応する分割部分データ４１２（ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を得ることができる９行（図中の網掛け部分）を抽出して、図１０の下段左側に示すような９行９列の部分行列を得る。この部分行列から求めた逆行列が復元行列１３１ｄとなる。
【００８７】
＜復元中間式＞
図１１は、分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３）から秘密部分データ４０２（ｓ１〜ｓ６）を算出する際の例について概要を示した図である。上述の図４と同様に、図１１の上段の図は、図７に示した復元行列１３１ａの内容を模式的に表として示しており、表の行・列は、図７に示した復元行列１３１ａの行・列に対応している。
【００８８】
ここで、本実施の形態では、図１１の下段に示すように、ｗ１〜ｗ５の５個の復元中間式１３２ａを定義しており、これらはそれぞれ“１”が立っている列（図１１の上段に示す復元行列１３１ａの列に対応する）により、以下の式の演算を表している。
【００８９】
ｗ１＝ｂ２＋ｃ１    …式２６
ｗ２＝ａ３＋ｂ１    …式２７
ｗ３＝ａ１＋ｃ３    …式２８
ｗ４＝ａ２＋ｃ２    …式２９
ｗ５＝ｗ３＋ｗ４    …式３０
また、上記のｗ１〜ｗ５の復元中間式１３２ａを用いることにより、上記の式２０〜式２５がそれぞれ以下の式により簡略化されることを表している。
【００９０】
ｓ１＝ａ２＋ｂ１＋ｗ１    …式２０’
ｓ２＝ｗ２＋ｗ５          …式２１’
ｓ３＝ａ１＋ｃ２＋ｗ１    …式２２’
ｓ４＝ａ３＋ｂ３＋ｗ４    …式２３’
ｓ５＝ｗ２＋ｗ３          …式２４’
ｓ６＝ｂ３＋ｃ１＋ｗ５    …式２５’
ここで、簡略化する前の上記の式２０〜式２５では、２入力のＸＯＲ演算の数は２２個であるが、上記の式２０’〜式２５’（および復元中間式１３２ａである式２６〜式３０）では、ＸＯＲ演算の数は１５個に大きく低減されている（低減率３１．８％）。従って、復元行列１３１ａに基づくＸＯＲ演算を直接実行する（上記の式２０〜式２５）よりも、復元中間式１３２ａを予め計算した上で（上記の式２６〜式３０）、復元中間式１３２ａを利用して復元行列１３１ａに基づくＸＯＲ演算を実行する（上記の式２０’〜式２５’）ことで、ＸＯＲ演算に係る処理の効率化・高速化することができる。
【００９１】
同様に、図１２は、分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｄ１〜ｄ３）から秘密部分データ４０２（ｓ１〜ｓ６）を算出する際の例について概要を示した図である。図１２の上段の図は、図８に示した復元行列１３１ｂの内容を模式的に表として示しており、表の行・列は、図８に示した復元行列１３１ｂの行・列に対応している。ここで、本実施の形態では、図１２の下段に示すように、ｘ１〜ｘ５の５個の復元中間式１３２ｂを定義しており、これらはそれぞれ“１”が立っている列（図１２の上段に示す復元行列１３１ｂの列に対応する）により、以下の式の演算を表している。
【００９２】
ｘ１＝ａ１＋ａ３                …式３１
ｘ２＝ａ２＋ｂ１                …式３２
ｘ３＝ｂ２＋ｂ３＋ｄ２＋ｘ１    …式３３
ｘ４＝ｄ３＋ｘ１＋ｘ２          …式３４
ｘ５＝ａ３＋ｂ２＋ｄ１＋ｘ２    …式３５
また、上記のｘ１〜ｘ５の復元中間式１３２ｂを用いることにより、復元行列１３１ｂと、分割部分データ４１２（ａ１〜ａ３、ｂ１〜ｂ３、ｄ１〜ｄ３）を要素とする分割データ行列との乗算によって６個の秘密部分データ４０２（ｓ１〜ｓ６）を得る式（記載は省略）が、それぞれ以下の簡略化された式によって表されることを示している。
【００９３】
ｓ１＝ｂ１＋ｘ３    …式３６’
ｓ２＝ｄ１＋ｘ３    …式３７’
ｓ３＝ｂ２＋ｘ４    …式３８’
ｓ４＝ｄ２＋ｘ４    …式３９’
ｓ５＝ｄ３＋ｘ５    …式４０’
ｓ６＝ｂ３＋ｘ５    …式４１’
ここで、簡略化する前では、ＸＯＲ演算の数は３０個であるが、上記の式３６’〜式４１’（および復元中間式１３２ｂである式３１〜式３５）では、ＸＯＲ演算の数は１６個に大きく低減されている（低減率４６．６％）。
【００９４】
同様に、図１３は、分割部分データ４１２（ａ１〜ａ３、ｃ１〜ｃ３、ｄ１〜ｄ３）から秘密部分データ４０２（ｓ１〜ｓ６）を算出する際の例について概要を示した図である。図１３の上段の図は、図９に示した復元行列１３１ｃの内容を模式的に表として示しており、表の行・列は、図９に示した復元行列１３１ｃの行・列に対応している。ここで、本実施の形態では、図１３の下段に示すように、ｙ１〜ｙ５の５個の復元中間式１３２ｃを定義しており、これらはそれぞれ“１”が立っている列（図１３の上段に示す復元行列１３１ｃの列に対応する）により、以下の式の演算を表している。
【００９５】
ｙ１＝ａ２＋ｃ２    …式４２
ｙ２＝ａ３＋ｃ３    …式４３
ｙ３＝ｃ２＋ｄ２    …式４４
ｙ４＝ａ１＋ｃ１    …式４５
ｙ５＝ｃ３＋ｄ３    …式４６
また、上記のｙ１〜ｙ５の復元中間式１３２ｃを用いることにより、復元行列１３１ｃと、分割部分データ４１２（ａ１〜ａ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を要素とする分割データ行列との乗算によって６個の秘密部分データ４０２（ｓ１〜ｓ６）を得る式（記載は省略）が、それぞれ以下の簡略化された式によって表されることを示している。
【００９６】
ｓ１＝ａ１＋ｄ１＋ｙ１＋ｙ２    …式４７’
ｓ２＝ｙ４＋ｙ５                …式４８’
ｓ３＝ｃ１＋ｄ１＋ｙ１＋ｙ５    …式４９’
ｓ４＝ｙ３＋ｙ４                …式５０’
ｓ５＝ｓ２＋ｙ１                …式５１’
ｓ６＝ｙ２＋ｙ３                …式５２’
ここで、簡略化する前では、ＸＯＲ演算の数は２４個であるが、上記の式４７’〜式５２’（および復元中間式１３２ｃである式４２〜式４６）では、ＸＯＲ演算の数は１５個に大きく低減されている（低減率３７．５％）。
【００９７】
同様に、図１４は、分割部分データ４１２（ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）から秘密部分データ４０２（ｓ１〜ｓ６）を算出する際の例について概要を示した図である。図１４の上段の図は、図１０に示した復元行列１３１ｄの内容を模式的に表として示しており、表の行・列は、図１０に示した復元行列１３１ｄの行・列に対応している。ここで、本実施の形態では、図１４の下段に示すように、ｚ１〜ｚ２の２個の復元中間式１３２ｄを定義しており、これらはそれぞれ“１”が立っている列（図１４の上段に示す復元行列１３１ｄの列に対応する）により、以下の式の演算を表している。
【００９８】
ｚ１＝ａ１＋ａ３    …式５３
ｚ２＝ａ２＋ｂ１    …式５４
また、上記のｚ１〜ｚ２の復元中間式１３２ｄを用いることにより、復元行列１３１ｄと、分割部分データ４１２（ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１〜ｄ３）を要素とする分割データ行列との乗算によって６個の秘密部分データ４０２（ｓ１〜ｓ６）を得る式（記載は省略）が、それぞれ以下の簡略化された式によって表されることを示している。
【００９９】
ｓ１＝ｄ１＋ｚ２                …式５５’
ｓ２＝ｂ１＋ｚ２                …式５６’
ｓ３＝ｂ２＋ｄ２＋ｓ４          …式５７’
ｓ４＝ｂ１＋ｄ３＋ｚ１          …式５８’
ｓ５＝ｂ２＋ｃ１＋ｃ２＋ｄ１    …式５９’
ｓ６＝ｂ３＋ｄ３＋ｓ５          …式６０’
ここで、簡略化する前では、ＸＯＲ演算の数は２６個であるが、上記の式５５’〜式６０’（および復元中間式１３２ｄである式５３〜式５４）では、ＸＯＲ演算の数は１５個に大きく低減されている（低減率４２．３％）。
【０１００】
なお、本実施の形態では、（３，２，４）ランプ型閾値秘密分散を用いる場合における、調整された分割行列１１１や分割中間式１１２、および復元行列１３１や復元中間式１３２について具体的に説明したが、（３，２，４）型に限らず、他の（ｋ，Ｌ，ｎ）型の場合であっても同様の思想で分割行列１１１や復元行列１３１を求め、また、分割中間式１１２や復元中間式１３２を定義してＸＯＲ演算の数を低減させ、処理を効率化・高速化させることが可能である。
【０１０１】
以上に説明したように、本発明の一実施の形態であるデータ分割装置１００およびデータ分割装置１００上で稼働するデータ分割プログラムによれば、秘密データ４００を（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散によりｎ個の分割データ４１０に分割して、これらの分割データ４１０をそれぞれ異なるサーバ２００等に分散保管する。これにより、分割データ４１０の紛失・盗難・不正取得等に対する秘密データ４００の秘匿性を高めるとともに、分割データ４１０の毀損・滅失等に対する秘密データ４００の可用性を高めることが可能となる。
【０１０２】
また、ランプ型の秘密分散を用いることから、安全性の条件は若干緩められるものの、ｎ個の各分割データ４１０のサイズを１／Ｌに縮小して、全体でのデータ量を（ｋ，ｎ）閾値秘密分散の場合と比べて１／Ｌに縮小する。これにより、各分割データ４１０を送信・保管する際のネットワーク３００の帯域や記憶領域などのリソース使用量を低減させることが可能となる。
【０１０３】
また、（ｋ，Ｌ，ｎ）ランプ型閾値秘密分散において、コンピュータでのビット演算に適するよう、ＸＯＲ演算により秘密分散処理を行う。すなわち、秘密データ４００を分割した秘密部分データ４０２のうちの１個以上と、秘密部分データ４０２と同じ長さで秘密部分データ４０２の半数の乱数部分データ４０３のうちの１個とのＸＯＲ演算に基づいて複数の分割部分データ４１２を生成し、それぞれ異なる乱数部分データ４０３を含むＸＯＲ演算により生成された複数の分割部分データ４１２を連結して単位分割データ４１１および分割データ４００を生成する。これにより、秘密分散処理を効率化・高速化することが可能となる。
【０１０４】
さらに、本実施の形態では、具体的に（３，２，４）ランプ型閾値秘密分散において、ＸＯＲ演算を行うための計算式（分割行列１１１、および復元行列１３１）を調整し、また、中間式（分割中間式１１２、および復元中間式１３２）を用いて計算手順を調整することで、ＸＯＲ演算の数を大きく低減させる（上述の分割中間式および復元中間式の例では中間式による低減率は平均すると４０．２％）ことを実現している。これにより、秘密データ４００から（３，２，４）ランプ型閾値秘密分散により複数の分割データ４１０を生成し、また複数の分割データ４１０から秘密データ４００を復元することを実際に可能とし、さらにそれらの際の処理性能を全体として向上させることが可能となる。
【０１０５】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【０１０６】
本発明は、重要データを秘密分散技術により複数の非重要データに分割して秘匿化する際のデータ分割装置およびデータ分割プログラムに利用可能である。
【符号の説明】
【０１０７】
１００…データ分割装置、１１０…分割処理部、１１１…分割行列、１１２…分割中間式、１１３…乱数生成部、１１４…秘密データ行列、１２０…分散管理部、１２１…分散状況、１２２…設定情報、１３０…復元処理部、１３１、１３１ａ〜ｄ…復元行列、１３２、１３２ａ〜ｄ…復元中間式、１３３ａ…分割データ行列、１４０…インタフェース部、
２００…サーバ、
３００…ネットワーク、
４００…秘密データ、４０１…単位秘密データ、４０２…秘密部分データ、４０３…乱数部分データ、４１０、４１０ａ〜ｄ…分割データ、４１１、４１１ａ〜ｄ…単位分割データ、４１２…分割部分データ。
【図１】
0005530025.tif 000002
【図２】
0005530025.tif 000003
【図３】
0005530025.tif 000004
【図４】
0005530025.tif 000005
【図５】
0005530025.tif 000006
【図６】
0005530025.tif 000007
【図７】
0005530025.tif 000008
【図８】
0005530025.tif 000009
【図９】
0005530025.tif 000010
【図１０】
0005530025.tif 000011
【図１１】
0005530025.tif 000012
【図１２】
0005530025.tif 000013
【図１３】
0005530025.tif 000014
【図１４】
0005530025.tif 000015