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