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