(57)【要約】【課題】ＸＯＲを用いることで高速演算が可能であり、然も、一般的な（ｋ，ｎ）閾値秘密分散法を構成できる分散情報生成装置等を提供する。【解決手段】ｋ個の分散情報をｋ（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分分散情報に分割し、分割した部分分散情報をベクトル表現に変換する。そして、変換したベクトルに基づいて、行列を生成し、生成した行列に対して、行列演算によって部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求め、求めたＸＯＲ演算の組み合わせを部分分散情報に適用して、部分秘密情報を復元し、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。【選択図】図２
2008262040.tif 000002
【特許請求の範囲】
【請求項１】
ｋ個の分散情報をｋ（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分分散情報に分割する分割手段と、
該分割した部分分散情報をベクトル表現に変換する変換手段と、
該変換したベクトルに基づいて、行列を生成する行列生成手段と、
該生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める行列演算手段と、
該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する復元手段と、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段と、
を備えたことを特徴とする秘密情報復元装置。
【請求項２】
秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する分割手段と、
ダミー部分秘密情報を生成するダミー情報生成手段と、
互いに独立な乱数Ｒを発生するｋ−１個の乱数発生手段と、
ダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成手段と、
前記部分分散情報を連結してｎ個の分散情報を生成する連結手段と、
該生成した分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加するヘッダ情報付加手段と、
を備えたことを特徴とする分散情報生成装置。
【請求項３】
分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離して取得するヘッダ情報取得手段と、
該取得したヘッダ情報に基づいて、行列を生成する行列生成手段と、
前記分散情報を部分分散情報に分割する分割手段と、
前記生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める行列演算手段と、
該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する復元手段と、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段と、
を備えたことを特徴とする秘密情報復元装置。
【請求項４】
秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する分割手段と、
ダミー部分秘密情報を生成するダミー情報生成手段と、
互いに独立な乱数Ｒを発生するｋ−１個の乱数発生手段と、
ダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成手段と、
該生成した部分分散情報に該部分分散情報をベクトル表現に変換したヘッダ情報を付加するヘッダ情報付加手段と、
前記ヘッダ情報が付加された部分分散情報を連結してｎ個の分散情報を生成する連結手段と、
を備えたことを特徴とする分散情報生成装置。
【請求項５】
部分分散情報をベクトル表現に変換したヘッダ情報が付加された部分分散情報を連結した分散情報を該ヘッダ情報が付加された部分分散情報に分割する分割手段と、
該分割したヘッダ情報が付加された部分分散情報に基づいて、行列を生成する行列生成手段と、
該生成した行列に対する行列演算を実行し、ヘッダ情報を伴った部分秘密情報を演算する演算手段と、
該演算結果から前記ヘッダ情報を除去する除去手段と、
該ヘッダ情報が除去された部分秘密情報を連結して秘密情報Ｋを生成する連結手段と、
を備えたことを特徴とする秘密情報復元装置。
【請求項６】
ｋ個の分散情報をｋ（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分分散情報に分割する第１のステップと、
該分割した部分分散情報をベクトル表現に変換する第２のステップと、
該変換したベクトルに基づいて、行列を生成する第３のステップと、
該生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第４のステップと、
該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第５のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第６のステップと、
を備えたことを特徴とする秘密情報復元方法。
【請求項７】
秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、
生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、
前記部分分散情報を連結してｎ個の分散情報を生成する第３のステップと、
該生成した分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、
を備えたことを特徴とする分散情報生成方法。
【請求項８】
分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離して取得する第１のステップと、
該取得したヘッダ情報に基づいて、行列を生成する第２のステップと、
前記分散情報を部分分散情報に分割する第３のステップと、
前記生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第３のステップと、
該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第４のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第５のステップと、
を備えたことを特徴とする秘密情報復元方法。
【請求項９】
秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、
生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、
該生成した部分分散情報に該部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、
前記ヘッダ情報が付加された部分分散情報を連結してｎ個の分散情報を生成する第４のステップと、
を備えたことを特徴とする分散情報生成方法。
【請求項１０】
部分分散情報をベクトル表現に変換したヘッダ情報が付加された部分分散情報を連結した分散情報を該ヘッダ情報が付加された部分分散情報に分割する第１のステップと、
該分割したヘッダ情報が付加された部分分散情報に基づいて、行列を生成する第２のステップと、
該生成した行列に対する行列演算を実行し、ヘッダ情報を伴った部分秘密情報を復元する第３のステップと、
該演算結果から前記ヘッダ情報を除去する第４のステップと、
該ヘッダ情報が除去された部分秘密情報を連結して秘密情報Ｋを生成する第５のステップと、
を備えたことを特徴とする秘密情報復元方法。
【請求項１１】
コンピュータに、
ｋ個の分散情報をｋ（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分分散情報に分割する第１のステップと、
該分割した部分分散情報をベクトル表現に変換する第２のステップと、
該変換したベクトルに基づいて、行列を生成する第３のステップと、
該生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第４のステップと、
該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第５のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第６のステップと、
を実行させるためのプログラム。
【請求項１２】
コンピュータに、
秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、
生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、
前記部分分散情報を連結してｎ個の分散情報を生成する第３のステップと、
該生成した分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、
を実行させるためのプログラム。
【請求項１３】
コンピュータに、
分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離して取得する第１のステップと、
該取得したヘッダ情報に基づいて、行列を生成する第２のステップと、
前記分散情報を部分分散情報に分割する第３のステップと、
前記生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第３のステップと、
該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第４のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第５のステップと、
を実行させるためのプログラム。
【請求項１４】
コンピュータに、
秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、
生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、
該生成した部分分散情報に該部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、
前記ヘッダ情報が付加された部分分散情報を連結してｎ個の分散情報を生成する第４のステップと、
を実行させるためのプログラム。
【請求項１５】
コンピュータに、
部分分散情報をベクトル表現に変換したヘッダ情報が付加された部分分散情報を連結した分散情報を該ヘッダ情報が付加された部分分散情報に分割する第１のステップと、
該分割したヘッダ情報が付加された部分分散情報に基づいて、行列を生成する第２のステップと、
該生成した行列に対する行列演算を実行し、ヘッダ情報を伴った部分秘密情報を復元する第３のステップと、
該演算結果から前記ヘッダ情報を除去する第４のステップと、
該ヘッダ情報が除去された部分秘密情報を連結して秘密情報Ｋを生成する第５のステップと、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機密情報を保護するための分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献１に示されるような（ｋ，ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｋ，ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｋ個の分散情報が集まれば、復元できることを意味する。
【０００３】
しかしながら、非特許文献１に示されている（ｋ，ｎ）閾値秘密分散法は、情報の分散、復元時に、（ｋ−１）次の多項式を処理する必要があり、その計算量が膨大になる。そこで、非特許文献２に示されるように、排他的論理和（ＸＯＲ）を用いて高速に分散、復元可能な（２，ｎ）閾値秘密分散法が提案されている。
【０００４】
一方、閾値２以外のＸＯＲを用いた閾値秘密分散法として、非特許文献３において、（３，ｎ）閾値秘密分散法が提案されている。しかしながら、閾値４以上のＸＯＲを用いた閾値秘密分散法については、未だに提案されていない。また、非特許文献４でもＸＯＲあるいは加法演算を用いて高速に分散、復元可能な（ｋ，ｎ）閾値秘密分散法が提案されているが、秘密情報のデータ長に比べて、分散情報のデータ長が数倍大きくなり、効率が悪い。更に、特許文献１では、（ｋ，ｎ）閾値秘密分散法が提案されているが、ｋより少ない個数の分散情報が手に入ったときでも、秘密情報が復元されてしまうことがあり、閾値秘密分散法としての一般性を満たしていない。
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎ．ＡＣＭ，  ｖｏｌ．２２  ｎｏ．１１  ｐｐ．６１２−６１３，  １９７９．
【非特許文献２】藤井吉弘，多田美奈子，保坂範和，栃窪孝也，加藤岳久，“高速な（２，ｎ）閾値法の構成法とシステムへの応用，”ＣＳＳ２００５予稿集，２００５．
【非特許文献３】栗原淳，清本晋作，福島和英，田中俊昭，“ＸＯＲを用いた（３，ｎ）閾値秘密分散法，ＳＣＩＳ２００７予稿集，２００７．
【非特許文献４】椎名信行，岡本健，岡本栄司，“１−ｏｕｔ−ｏｆ−ｎ証明からｋ−ｏｕｔ−ｏｆ−ｎ証明への引き上げ方法”ＳＣＩＳ２００４予稿集，２００４．
【特許文献１】特開２００６−１８８５０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述のように、非特許文献１に示されている（ｋ，ｎ）閾値秘密分散法は、演算量が膨大になるという問題がある。また、非特許文献４に示されている方式は、分散情報のデータ長が秘密情報の数倍大きくなるという問題がある。そこで、ＸＯＲを用いて高速演算が可能であり、しかも、分散情報のデータ長が秘密情報のデータ長と等しくなるような、効率の良い閾値秘密分散法が要望されるが、ＸＯＲを用いた一般的な（ｋ，ｎ）閾値秘密分散法については、未だに提案されていないのが現状である。
【０００６】
そこで、本発明は、上述の課題を鑑みてなされたものであり、ＸＯＲを用いることで高速演算が可能であり、秘密情報と分散情報のデータ長が等しく、しかも、一般的な（ｋ，ｎ）閾値秘密分散法を構成できる分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述の課題を解決するために、本発明は、以下の事項を提案している。
（１）本発明は、ｋ個の分散情報をｋ（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分分散情報に分割する分割手段と、該分割した部分分散情報をベクトル表現に変換する変換手段と、該変換したベクトルに基づいて、行列を生成する行列生成手段と、該生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める行列演算手段と、該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する復元手段と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段と、を備えたことを特徴とする秘密情報復元装置を提案している。
【０００８】
（２）本発明は、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する分割手段と、ダミー部分秘密情報を生成するダミー情報生成手段と、互いに独立な乱数Ｒを発生するｋ−１個の乱数発生手段と、ダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成手段と、前記部分分散情報を連結してｎ個の分散情報を生成する連結手段と、該生成した分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加するヘッダ情報付加手段と、を備えたことを特徴とする分散情報生成装置を提案している。
【０００９】
（３）本発明は、分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離して取得するヘッダ情報取得手段と、該取得したヘッダ情報に基づいて、行列を生成する行列生成手段と、前記分散情報を部分分散情報に分割する分割手段と、前記生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める行列演算手段と、該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する復元手段と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１０】
（４）本発明は、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する分割手段と、ダミー部分秘密情報を生成するダミー情報生成手段と、互いに独立な乱数Ｒを発生するｋ−１個の乱数発生手段と、ダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成手段と、該生成した部分分散情報に該部分分散情報をベクトル表現に変換したヘッダ情報を付加するヘッダ情報付加手段と、前記ヘッダ情報が付加された部分分散情報を連結してｎ個の分散情報を生成する連結手段と、を備えたことを特徴とする分散情報生成装置を提案している。
【００１１】
（５）本発明は、部分分散情報をベクトル表現に変換したヘッダ情報が付加された部分分散情報を連結した分散情報を該ヘッダ情報が付加された部分分散情報に分割する分割手段と、該分割したヘッダ情報が付加された部分分散情報に基づいて、行列を生成する行列生成手段と、該生成した行列に対する行列演算を実行し、ヘッダ情報を伴った部分秘密情報を演算する演算手段と、該演算結果から前記ヘッダ情報を除去する除去手段と、該ヘッダ情報が除去された部分秘密情報を連結して秘密情報Ｋを生成する連結手段と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１２】
（６）本発明は、ｋ個の分散情報をｋ（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分分散情報に分割する第１のステップと、該分割した部分分散情報をベクトル表現に変換する第２のステップと、該変換したベクトルに基づいて、行列を生成する第３のステップと、該生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第４のステップと、該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第５のステップと、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第６のステップと、を備えたことを特徴とする秘密情報復元方法を提案している。
【００１３】
（７）本発明は、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、前記部分分散情報を連結してｎ個の分散情報を生成する第３のステップと、該生成した分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、を備えたことを特徴とする分散情報生成方法を提案している。
【００１４】
（８）本発明は、分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離して取得する第１のステップと、該取得したヘッダ情報に基づいて、行列を生成する第２のステップと、前記分散情報を部分分散情報に分割する第３のステップと、前記生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第３のステップと、該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第４のステップと、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第５のステップと、を備えたことを特徴とする秘密情報復元方法を提案している。
【００１５】
（９）本発明は、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、該生成した部分分散情報に該部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、前記ヘッダ情報が付加された部分分散情報を連結してｎ個の分散情報を生成する第４のステップと、を備えたことを特徴とする分散情報生成方法を提案している。
【００１６】
（１０）本発明は、部分分散情報をベクトル表現に変換したヘッダ情報が付加された部分分散情報を連結した分散情報を該ヘッダ情報が付加された部分分散情報に分割する第１のステップと、該分割したヘッダ情報が付加された部分分散情報に基づいて、行列を生成する第２のステップと、該生成した行列に対する行列演算を実行し、ヘッダ情報を伴った部分秘密情報を復元する第３のステップと、該演算結果から前記ヘッダ情報を除去する第４のステップと、該ヘッダ情報が除去された部分秘密情報を連結して秘密情報Ｋを生成する第５のステップと、を備えたことを特徴とする秘密情報復元方法を提案している。
【００１７】
（１１）本発明は、コンピュータに、ｋ個の分散情報をｋ（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分分散情報に分割する第１のステップと、該分割した部分分散情報をベクトル表現に変換する第２のステップと、該変換したベクトルに基づいて、行列を生成する第３のステップと、該生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第４のステップと、該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第５のステップと、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第６のステップと、を実行させるためのプログラムを提案している。
【００１８】
（１２）本発明は、コンピュータに、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、前記部分分散情報を連結してｎ個の分散情報を生成する第３のステップと、該生成した分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、を実行させるためのプログラムを提案している。
【００１９】
（１３）本発明は、コンピュータに、分散情報に該分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離して取得する第１のステップと、該取得したヘッダ情報に基づいて、行列を生成する第２のステップと、前記分散情報を部分分散情報に分割する第３のステップと、前記生成した行列に対する行列演算を実行して、前記部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める第３のステップと、該求めたＸＯＲ演算の組み合わせを前記部分分散情報に適用して、部分秘密情報を復元する第４のステップと、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第５のステップと、を実行させるためのプログラムを提案している。
【００２０】
（１４）本発明は、コンピュータに、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割する第１のステップと、生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する第２のステップと、該生成した部分分散情報に該部分分散情報をベクトル表現に変換したヘッダ情報を付加する第３のステップと、前記ヘッダ情報が付加された部分分散情報を連結してｎ個の分散情報を生成する第４のステップと、を実行させるためのプログラムを提案している。
【００２１】
（１５）本発明は、コンピュータに、部分分散情報をベクトル表現に変換したヘッダ情報が付加された部分分散情報を連結した分散情報を該ヘッダ情報が付加された部分分散情報に分割する第１のステップと、該分割したヘッダ情報が付加された部分分散情報に基づいて、行列を生成する第２のステップと、該生成した行列に対する行列演算を実行し、ヘッダ情報を伴った部分秘密情報を復元する第３のステップと、該演算結果から前記ヘッダ情報を除去する第４のステップと、該ヘッダ情報が除去された部分秘密情報を連結して秘密情報Ｋを生成する第５のステップと、を実行させるためのプログラムを提案している。
【発明の効果】
【００２２】
本発明によれば、排他的論理和（ＸＯＲ）を用いて、一般的な（ｋ，ｎ）閾値秘密分散法を構成できる。このため、分散、復元がＸＯＲ演算で行えることから、高速処理が可能になるという効果がある。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施形態について図面を参照しながら説明する。
【００２４】
＜第１の実施形態＞
本実施形態は、秘密情報を（ｋ，ｎ）閾値法で分散、復元するものである。図１は、本実施形態の分散情報の生成、配布装置の概要を示す機能ブロック図である。
【００２５】
図１において、秘密情報Ｋは分割器１１に送られ、（ｎｐ−１）個の部分秘密情報Ｋｑに分割される。また、ダミー情報生成器１２でダミー部分秘密情報Ｋ０が生成される。ダミー部分秘密情報Ｋ０及び部分秘密情報Ｋｑは、部分分散情報生成器１３に送られる。
【００２６】
また、乱数発生器１４は、互いに独立な乱数Ｒを発生している。そして、同様な乱数発生器１４をｋ−１個備えている。乱数発生器１４からの乱数Ｒは、部分分散情報生成器１３に送られる。
【００２７】
部分分散情報生成器１３では、ダミー部分秘密情報Ｋ０及び（ｎｐ−１）個の部分秘密情報Ｋｑと、乱数発生器１４からの乱数Ｒとを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報が生成される。この部分分散情報が連結器１６により連結されて、ｎ個の分散情報Ｓｉが生成される。この分散情報Ｓｉは、送信装置１７により、管理者Ｐｉにセキュアに送信される。
【００２８】
本実施形態では、一般的な分散数ｎの（ｋ，ｎ）閾値秘密分散法により、秘密情報Ｋを分散数ｎの分散情報Ｓｉに分散できる。また、分散に必要な演算は、排他的論理和（ＸＯＲ）であるため、高速な演算が行える。
【００２９】
なお、本発明では、秘密情報を（ｎｐ−１）個に等分割する必要がある。但し、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３０】
本実施形態の閾値秘密分散法について、更に、詳述する。先ず、本実施形態の閾値秘密分散法を説明するに先立ち、本明細書中で使用する演算子及び記号について、以下のように、定義する。
【００３１】
【数１】
2008262040.tif 000003
【００３２】
先ず、分散処理方法について説明する。本実施形態の閾値秘密分散法では、以下の手順に従って分散処理を行って、（ｋ，ｎ）閾値秘密分散法が実現される。
【００３３】
なお、前述したように、本発明では、秘密情報Ｋを（ｎｐ−１）個に等分割する必要があり、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値秘密分散法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３４】
（ステップ１）
秘密情報Ｋを（ｎｐ−１）個のｄビットごとの部分秘密情報Ｋ１、…、Ｋｎｐ−１に分割する。
【００３５】
【数２】
2008262040.tif 000004
【００３６】
（ステップ２）
ｄビットの「０」の列であるダミーの部分秘密情報Ｋ０を生成する。
【００３７】
（ステップ３）
計（ｋ−１）ｎｐ−１個のｄビットの乱数Ｒｌ０、Ｒｌ１、・・・、Ｒｎｐ−２０、Ｒｌ１、・・・、Ｒｎｐ−２１、・・・、Ｒ０ｋ−２、Ｒ１ｋ−２、・・・、Ｒｎｐ−１ｋ−２を全て独立に生成する。
【００３８】
（ステップ４）
ＸＯＲ演算により、以下のように部分分散情報Ｓ（ｉ，ｍ）を生成する。
【００３９】
【数３】
2008262040.tif 000005
【００４０】
（ステップ５）
部分分散情報Ｓ（ｉ、０）、・・・、Ｓ（ｉ，ｎｐ−２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉへセキュアに配付する。
【００４１】
【数４】
2008262040.tif 000006
【００４２】
以上のステップにより構成される部分分散情報の構成表は、表１のようになる。また、１人の管理者に配布されるビット数は、Ｋのビット数と等しくなる。
【００４３】
【表１】
2008262040.tif 000007
【００４４】
次に、復元法について説明する。復元は、図２に示す復元器２１を使って行われる。これは、ｋ入力１出力の装置であり、ｋ＋１人以上の管理者が集まったときは、そのうちの任意のｋ人の管理者から分散情報を得て、その装置に入力することになる。つまり、表１に示す部分分散情報の構成により、収集した部分分散情報から部分秘密情報の復元を行う。これによって、ｋ個の分散情報のいかなる組み合わせであっても、すべての部分秘密情報を復元することができる。
【００４５】
図２に示すように、具体的な構成は、分散情報分割部２１と、ベクトル表現変換部２２と、行列生成部２３と、行列演算部２４と、部分秘密情報復元部２５と、連結部２６とからなっている。
【００４６】
分散情報分割部２１には、ｋ個の分散情報（Ｓｉ０、・・・、Ｓｉｋ−１）が入力され、ｋ（ｎｐ−１）個の部分分散情報に分割される。分割されたｋ（ｎｐ−１）個の部分分散情報は、ベクトル表現変換部２２において、ベクトル表現に変換され、これが行列生成部２３に入力されて行列が生成される。生成された行列は、行列演算部２４において、行列演算が実行されて、部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせが求められる。部分秘密情報復元部２５は、行列演算部２４における演算結果に基づいて、部分秘密情報を復元し、復元された部分秘密情報が連結部２６において連結されて秘密情報Ｋが生成される。
【００４７】
以下、この復元処理の手順について、より具体的に説明する。前提として、ｋ人の相異なる管理者Ｐｉ０，・・・Ｐｉｋ−１が集まっているとし、ｋ個の分散情報をＳｉ０、・・・、Ｓｉｋ−１（ｉ０、・・・、ｉｋ−１は全て互いに相違）とする。
【００４８】
（ステップ１）
それぞれの分散情報Ｓｉ０、・・・、Ｓｉｋ−１を部分分散情報に分割する。すなわち、以下のｋ（ｎｐ−１）個の部分分散情報が得られる。
【００４９】
【数５】
2008262040.tif 000008
【００５０】
（ステップ２）
全ての部分分散情報の構成要素を数６のようなｋ・ｎｐ−２ビットのベクトルで表現する。数６は部分分散情報Ｓ（ｉｔ、ｍ）に対するベクトル表現Ｖ（ｉｔ、ｍ）である。Ｓ（ｉｔ、ｍ）の構成要素（部分秘密情報、乱数）に対応する部分のみが、「１」となり、これ以外は、「０」となる。即ち、ベクトルの各ビットと各構成要素は、以下のように対応する。ここで、Ｋ０は、ｄビットの「０」の列であるダミー情報であるため、ベクトル表現時において、考慮する必要はない。
（Ｋ１、Ｋ２、・・・、Ｋｎｐ−１、Ｒ００、Ｒｌ０、・・・、Ｒｎｐ−２０、Ｒｌ１、・・・、Ｒｎｐ−１１、・・・、Ｒ０ｋ−２、Ｒ１ｋ−２、・・・、Ｒｎｐ−１ｋ−２）
【００５１】
【数６】
2008262040.tif 000009
【００５２】
（ステップ３）
全ての部分分散情報に関する構成要素のベクトル表現を各行とした行列を生成する。この行列を用いて、左辺に部分分散情報のｋ（ｎｐ−１）行の縦ベクトル、右辺にベクトル表現によるバイナリのｋ（ｎｐ−１）行、ｋ・ｎｐ−２列の行列とｋ・ｎｐ−２行の縦ベクトルＸ（ｋ，ｎ）との積とした数７の等式を得る。
【００５３】
【数７】
2008262040.tif 000010
【００５４】
（ステップ４）
次に、数７の右辺の行列に対して、ＸＯＲ演算と行基本変形のみを用いた行列演算を実行し、左辺を右辺に合わせて変形して、数８を得る。これにより、右辺の行列部は行列演算により変形され、左辺は右辺の変形を得るためのＸＯＲ演算の組み合わせを示すことになる。なお、右辺の各行ごとにＸＯＲ演算の組み合わせは異なる。なお、この例では、行列演算の手法として、ガウス・ジョルダンの消去法を用いている。
【００５５】
【数８】
2008262040.tif 000011
【００５６】
（ステップ５）
さらに、数８の左辺の第１行からｎｐ−１行目までに示される部分分散情報のＸＯＲ演算を実行する。これにより、それぞれの行番号に対応して、Ｋ１、Ｋ２、・・・、Ｋｎ−１の全ての部分秘密情報が得られる。なお、数８の左辺の演算実行は行列演算を実行してＸＯＲ演算式を求めた後に実行する以外にも、行列演算の実行中に行われるＸＯＲ演算による行基本変形に対応して部分分散情報のＸＯＲ演算を逐次的に行うことも可能である。この場合は、行列演算が終了したときに、同時に全ての部分秘密情報が求まる。
【００５７】
（ステップ６）
全ての部分秘密情報を連結し、元の秘密情報Ｋを復元する。
【００５８】
【数９】
2008262040.tif 000012
【００５９】
したがって、本実施形態によれば、ＸＯＲを用いることで高速演算が可能であり、秘密情報と分散情報のデータ長が等しく、しかも、一般的な（ｋ，ｎ）閾値秘密分散法を構成できる。
【００６０】
＜第２の実施形態＞
本実施形態は、図３に示すように、生成した分散情報に部分分散情報に関する構成要素のベクトル表現をヘッダ情報として付加することにより、分散情報のインデックスや構成要素の管理テーブルが無くても、秘密情報の復元を可能とする方式である。
【００６１】
本実施形態に係る分散情報生成装置は、図４に示すように、第１の実施形態に係る分散情報生成装置に対して、連結器１６と送信装置１７との間に、ヘッダ情報埋め込み部１８を設けた構成となっている。ここで、ヘッダ情報埋め込み部１８は、分散情報にこの分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加する。
【００６２】
具体的な処理手順は、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割し、生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する。そして、部分分散情報を連結してｎ個の分散情報を生成し、生成した分散情報にこの分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加する。
【００６３】
一方、本実施形態に係る秘密情報復元装置は、図５に示すように、分散情報分割部２１と、行列生成部２３と、行列演算部２４と、部分秘密情報復元部２５と、連結部２６と、ヘッダ情報取得部２７とから構成されている。
【００６４】
ここで、ヘッダ情報取得部２７は、分散情報にこの分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離して取得する。行列生成部２３は、ヘッダ情報取得部２７が取得したヘッダ情報に基づいて、行列を生成する。分散情報分割部２１は、ヘッダ情報を除去した分散情報を部分分散情報に分割する。
【００６５】
行列演算部２４は、行列生成部２３が生成した行列に対する行列演算を実行して、部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める。部分秘密情報復元部２５は、行列演算部２４で求めたＸＯＲ演算の組み合わせを部分分散情報に適用して、部分秘密情報を復元する。連結部２６は、部分秘密情報復元部２５において復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。
【００６６】
具体的な処理手順は、分散情報にこの分散情報を構成する部分分散情報をベクトル表現に変換したヘッダ情報を付加した情報からヘッダ情報を分離し、取得したヘッダ情報に基づいて、行列を生成する。次に、ヘッダ情報を除去した分散情報を部分分散情報に分割し、生成した行列に対し、行列演算を実行して、部分分散情報に対する排他的論理和（ＸＯＲ）演算の組み合わせを求める。そして、求めたＸＯＲ演算の組み合わせを部分分散情報に適用して、部分秘密情報を復元し、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。
【００６７】
したがって、本実施形態によれば、生成した分散情報に部分分散情報に関する構成要素のベクトル表現をヘッダ情報として付加することにより、分散情報のインデックスや構成要素の管理テーブルが無くても、秘密情報の復元を行うことができる。
【００６８】
＜第３の実施形態＞
本実施形態は、図６に示すように、生成した部分分散情報にその構成要素のベクトル表現をヘッダ情報として付加して分散情報を生成することにより、分散情報のインデックスや構成要素の管理テーブルが無くても、秘密情報の復元を可能とする方式である。
【００６９】
本実施形態に係る分散情報生成装置は、図８に示すように、第１の実施形態に係る分散情報生成装置に対して、部分分散情報生成器と連結器１６との間に、ヘッダ情報埋め込み部１９を設けた構成となっている。ここで、ヘッダ情報埋め込み部１８は、部分分散情報にこの部分分散情報をベクトル表現に変換したヘッダ情報を付加する。
【００７０】
具体的な処理は、秘密情報Ｋを、（ｎｐ−１）個（ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数）の部分秘密情報に分割し、生成したダミー部分秘密情報及び部分秘密情報と、乱数とを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する。そして、生成した部分分散情報に部分分散情報をベクトル表現に変換したヘッダ情報を付加し、ヘッダ情報が付加された部分分散情報を連結してｎ個の分散情報を生成する。
【００７１】
一方、本実施形態に係る秘密情報復元装置は、図９に示すように、分散情報分割部２１と、行列生成部２３と、行列演算部２４と、連結部２６と、ヘッダ情報除去部２８とから構成されている。
【００７２】
ここで、分散情報分割部２１は、部分分散情報をベクトル表現に変換したヘッダ情報が付加された部分分散情報を連結した分散情報をそのヘッダ情報が付加された部分分散情報に分割する。行列生成部２３は、分割したヘッダ情報が付加された部分分散情報に基づいて、行列を生成する。行列演算部２４は、生成した行列に対する行列演算を実行し、ヘッダ情報を伴った部分秘密情報を復元する。ヘッダ情報除去部２８は、演算結果からヘッダ情報を除去し、連結部２６は、ヘッダ情報が除去された部分秘密情報を連結して秘密情報Ｋを生成する。
【００７３】
具体的な処理としては、図７に示すように、ヘッダ情報を付加した部分分散情報のバイナリ列をベクトルとして扱い、これに対して、行列演算を実行して、秘密情報を逐次復元する。そして、行列演算の実行が終了した後に、第１行から第ｎｐ−１行を取り出し、ヘッダ情報を除去することにより、全ての部分秘密情報Ｋ１、・・・、ＫｎＰ−１が復元される。
【００７４】
したがって、本実施形態によれば、生成した分散情報に部分分散情報に関する構成要素のベクトル表現をヘッダ情報として付加することにより、分散情報のインデックスや構成要素の管理テーブルが無くても、秘密情報の復元を行うことができる。また、復元装置の構成を簡略化することができる。
【００７５】
＜実施例１＞
具体例として、（３，５）閾値秘密分散法を構成したときの復元例について説明する。（３，５）閾値秘密分散法における秘密情報復元器は、表２に示す部分分散情報の構成表を参照することにより、部分分散情報Ｋ１、Ｋ２、Ｋ３、Ｋ４の復元を行う。
【００７６】
【表２】
2008262040.tif 000013
【００７７】
この復元例では、管理者Ｐ０、Ｐ１、Ｐ２の３人の管理者が集まった場合を考える。
【００７８】
（ステップ１）
それぞれの分散情報を分割し、以下、数１０に示す部分秘密情報を得る。
【００７９】
【数１０】
2008262040.tif 000014
【００８０】
（ステップ２）
次に、構成要素の管理テーブルより、それぞれの部分分散情報の構成要素のベクトル表現を得る。分散情報のヘッダとして埋め込まれていたものをあらかじめ取り出していた場合は、その情報よりベクトル表現を得る。
【００８１】
（ステップ３）
ベクトル表現を各行に配置した行列を生成する。生成した行列は以下、数１１の式を満たす。
【００８２】
【数１１】
2008262040.tif 000015
【００８３】
（ステップ４）
上記数１１の式の右辺の行列部に行列演算を実行し、右辺を左辺に合わせて変形して以下の数１２の式を得る。なお、この例では、行列演算の手法として、ガウス・ジョルダンの消去法を用いている。
【００８４】
【数１２】
2008262040.tif 000016
【００８５】
（ステップ５）
上記数１２の左辺第１行から第４行までを実行することにより、下記、数１３のように各行番号に対応して全ての部分秘密情報が復元される。
【００８６】
【数１３】
2008262040.tif 000017
【００８７】
（ステップ６）
最後に、復元された部分秘密情報を連結して、元の秘密情報Ｋを数１４のように復元する。
【００８８】
【数１４】
2008262040.tif 000018
【００８９】
＜実施例２＞
次に、他の具体例として、部分分散情報のヘッダ情報として、この部分分散情報の構成要素に関するベクトル表現を付加した場合の復元方法について説明する。なお、本実施例では、表３に構成表を示す（４，５）閾値法を用いる。
【００９０】
【表３】
2008262040.tif 000019
【００９１】
この復元例では、管理者Ｐ０、Ｐ１、Ｐ２、Ｐ３の４人の管理者が集まった場合を考える。
【００９２】
（ステップ１）
それぞれの分散情報を分割し、ヘッダ情報が付加された部分分散情報を得る。
【００９３】
（ステップ２）
ヘッダ情報の付加された部分分散情報を各行に配置した、数１５に示すようなバイナリの行列を生成する。なお、以下において、ヘッダ情報と部分分散情報とはバイナリで単純に連結されている。
【数１５】
2008262040.tif 000020
【００９４】
（ステップ３）
上記、数１５に示す行列に対する行列演算を実行し、以下、数１６に示すような行列を得る。なお、この例では、行列演算の手法として、ガウス・ジョルダンの消去法を用いている。
【００９５】
【数１６】
2008262040.tif 000021
【００９６】
（ステップ４）
上記、数１６に示す行列の第１行から第４行までを取り出し、ヘッダ情報を除去することにより、全ての部分秘密情報が数１７に示すように、復元される。
【００９７】
【数１７】
2008262040.tif 000022
【００９８】
（ステップ５）
最後に、復元された部分秘密情報を連結して、元の秘密情報Ｋを数１８のように復元する。
【００９９】
【数１８】
2008262040.tif 000023
【０１００】
以上説明したように、本実施形態では、高速に分散情報の生成、秘密情報の復元が可能なＸＯＲを用いた（ｋ，ｎ）閾値秘密分散法を基本とする秘密分散システムが実現できる。
【０１０１】
なお、上述の秘密分散及び復元処理は、コンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを記録装置に読み込ませ、実行することによって本発明の制御を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【０１０２】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【０１０３】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１０４】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【０１０５】
なお、本発明は、企業内等で扱われる機密データをセキュアに処理するのに用いることができる。
【図面の簡単な説明】
【０１０６】
【図１】第１の実施形態に係る分散情報生成装置の機能ブロック図である。
【図２】第１の実施形態に係る秘密情報復元装置の機能ブロック図である。
【図３】第２の実施形態に係る分散情報の構成を示した図である。
【図４】第２の実施形態に係る分散情報生成装置の機能ブロック図である。
【図５】第２の実施形態に係る秘密情報復元装置の機能ブロック図である。
【図６】第３の実施形態に係る分散情報の構成を示した図である。
【図７】第３の実施形態に係る行列の構成を示した図である。
【図８】第３の実施形態に係る分散情報生成装置の機能ブロック図である。
【図９】第３の実施形態に係る秘密情報復元装置の機能ブロック図である。
【符号の説明】
【０１０７】
１１・・・分割器、１２・・・ダミー秘密情報生成器、１３・・・部分分散情報生成器
１４、１５・・・乱数発生器、１６・・・連結器、１７・・・送信装置、１８、１９・・・ヘッダ情報埋め込み部、２１・・・分散情報分割部、２２・・・ベクトル表現変換部、２３・・・行列生成部、２４・・・行列演算部、２５・・・部分秘密情報復元部、２６・・・連結部、２７・・・ヘッダ情報取得部、２８・・・ヘッダ情報除去部、
【図１】
2008262040.tif 000024
【図２】
2008262040.tif 000025
【図３】
2008262040.tif 000026
【図４】
2008262040.tif 000027
【図５】
2008262040.tif 000028
【図６】
2008262040.tif 000029
【図７】
2008262040.tif 000030
【図８】
2008262040.tif 000031
【図９】
2008262040.tif 000032