秘密情報復元装置、秘密情報復元方法およびプログラム
【課題】ＸＯＲを用いた（ｋ、ｎ）閾値分散法において、秘密情報の高速な復元を可能とする。
【解決手段】部分分散情報生成手段２１は、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する。行列生成手段２２は、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。復元手段２３は、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、連結手段２４は、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。
【解決手段】部分分散情報生成手段２１は、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する。行列生成手段２２は、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。復元手段２３は、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、連結手段２４は、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元装置、秘密情報復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献１に示されるような（ｋ，ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｋ，ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｋ個の分散情報が集まれば、復元できることを意味する。
【０００３】
しかしながら、非特許文献１に示されている（ｋ，ｎ）閾値秘密分散法は、情報の分散、復元時に、（ｋ−１）次の多項式を処理する必要があり、その計算量が膨大になる。
【０００４】
これに対して、ＸＯＲを用いて、（ｋ，ｎ）閾値秘密分散法を構築することにより、高速に情報の分散および復元を可能とする方式が開示されている（例えば、非特許文献２および３参照。）。この非特許文献２および３で開示された方法は、その構造において等価なものであり、単純に高速動作を行うだけでなく、非特許文献１と同様に、完全な情報論理的安全性が保証されており、分散情報のデータ長が秘密情報のデータ長と等しいという特徴を有している。
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ ｔｏ Ｓｈａｒｅ ａ Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎ．ＡＣＭ， ｖｏｌ．２２ ｎｏ．１１ ｐｐ．６１２−６１３， １９７９．
【非特許文献２】Ｊ．Ｋｕｒｉｈａｒａ、Ｓ．Ｋｉｙｏｍｏｔｏ、Ｋ．Ｆｕｋｕｓｈｉｍａ、Ｔ．Ｔａｎａｋａ、“Ａ Ｆａｓｔ （４、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ Ｓｃｈｅｍｅ Ｕｓｉｎｇ Ｅｘｃｌｕｓｉｖｅ−ＯＲ Ｏｐｅｒａｔｉｏｎ ａｎｄ ｉｔｓ Ｅｘｔｅｎｓｉｏｎ ｔｏ （ｋ、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｃｈｅｍｅｓ”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−４
【非特許文献３】藤井吉弘、栃窪孝也、保坂範和、多田美奈子、加藤岳久、“排他的論理和を用いた（ｋ、ｎ）しきい値法の構成法”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−５
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献２または３に記載された技術では、秘密情報の復元時に、分散情報の生成行列を構成し、その全体に、あるいは行列を分割してブロックごとに、ガウスの消去法や、ＬＵ分解、ガウスジョルダンの消去法など逆行列探索演算を行うことで、秘密情報を復元するための分散情報の組み合わせを探索していた(以降、「事前計算」と呼ぶ)。このとき、事前計算にかかる演算量は生成行列の行数をＲとすると、Ｏ（Ｒ３）、即ち、行列の行数の三乗倍となる。また、生成行列のサイズはｋ、ｎに依存しており、ｋ、ｎが大きければ大きいほど事前計算の演算量が増加していくという問題がある。
【０００６】
また、事前計算では、「探索」の作業、即ち、行列の特定の部分の数値が何であるかを条件判定し、それよって処理を振り分けることが必要となる。これは、条件分岐の多さを意味しており、プログラム・装置等に実装した場合に動作が低速になるという問題がある。例えば、プログラムの場合、等価な処理を行う論理的記述(出来る限り条件分岐をなくした記述)をしたプログラムとｉｆ文記述を多用したプログラムとでは、コンピュータの性質上、前者の方が高速に動作することが知られている。
【０００７】
そこで、本発明は、上述の課題に鑑みてなされたものであり、ＸＯＲを用いた（ｋ、ｎ）閾値分散法において、秘密情報の高速な復元を可能とする秘密情報復元装置、秘密情報復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記の課題を解決するために、以下の事項を提案している。
（１）本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する部分分散情報生成手段（例えば、図２の分散情報分割部２１に相当）と、前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する行列生成手段（例えば、図２の行列生成部２２に相当）と、該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する復元手段（例えば、図２の部分秘密情報復元部２３に相当）と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段（例えば、図２の連結部２４に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【０００９】
この発明によれば、部分分散情報生成手段は、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する。行列生成手段は、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。復元手段は、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、連結手段は、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。したがって、秘密情報を復元するための分散情報の組み合わせを示す行列を機械的に構築することから、従来のように、分散情報の生成行列を構築する必要がなく、さらには分散情報の生成行列内部の要素が何であるかを条件判定して処理を振り分け、生成行列を変形していく、というような逆行列の探索処理が一切必要なく、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみがわかれば、秘密情報を復元するための分散情報の組み合わせ表す行列を生成できる。
【００１０】
（２）本発明は、（１）の秘密情報復元装置について、前記行列生成手段が、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する第１の行列生成器（例えば、図３の行列Ｘ０生成器３１に相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する第２の行列生成器（例えば、図３の行列Ｘ１生成器３２に相当）と、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する第３の行列生成器（例えば、図３の行列Ｘｍ−１生成器３３ａ、３３ｍに相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する第４の行列生成器（例えば、図３の行列Ｘｋ−１生成器３４に相当）と、前記第１の行列生成器から第４の行列生成器において生成された行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する第５の行列生成器（例えば、図３の行列Ｍ生成器３５に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１１】
この発明によれば、行列生成手段が、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する第１の行列生成器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する第２の行列生成器と、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する第３の行列生成器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する第４の行列生成器とを並列に備え、第５の行列生成器が、第１の行列生成器から第４の行列生成器において生成された行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する。したがって、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があるのに対し、本発明においては、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００１２】
（３）本発明は、（１）の秘密情報復元装置について、前記行列生成手段が、単位行列を生成する単位行列生成器（例えば、図８の単位行列生成器４１に相当）と、該生成した単位行列を行基本変形する第１の行基本変形演算器（例えば、図８の行基本変形演算器４２に相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行基本変形演算器において演算された行列を行基本変形する第２の行基本変形演算器（例えば、図８の行基本変形演算器４３に相当）と、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行基本変形演算器において演算された行列を行基本変形する第３の行基本変形演算器（例えば、図８の行基本変形演算器４４ａ、４４ｍに相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行基本変形演算器において演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第４の行基本変形演算器（例えば、図８の行基本変形演算器４５に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１３】
この発明によれば、行列生成手段が、単位行列を生成する単位行列生成器と、生成した単位行列を行基本変形する第１の行基本変形演算器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第１の行基本変形演算器において演算された行列を行基本変形する第２の行基本変形演算器と、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、第２の行基本変形演算器において演算された行列を行基本変形する第３の行基本変形演算器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第３の行基本変形演算器において演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する第４の行基本変形演算器とを備えている。したがって、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００１４】
（４）本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップ（例えば、図４のステップＳ１０１に相当）と、前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップ（例えば、図４のステップＳ１０２からステップＳ１０６に相当）と、該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップ（例えば、図４のステップＳ１０７に相当）と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップ（例えば、図４のステップＳ１０８に相当）と、を備えたことを特徴とする秘密情報復元方法を提案している。
【００１５】
この発明によれば、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成し、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力して、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。そして、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。したがって、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみで、秘密情報を復元するための分散情報の組み合わせ表す行列を生成することができる。
【００１６】
（５）本発明は、（４）の秘密情報復元方法について、前記第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成（例えば、図４のステップＳ１０２に相当）し、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し（例えば、図４のステップＳ１０３に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し（例えば、図４のステップＳ１０４に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し（例えば、図４のステップＳ１０５に相当）、前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する（例えば、図４のステップＳ１０６に相当）ことを特徴とする秘密情報復元方法を提案している。
【００１７】
この発明によれば、第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する。したがって、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があるのに対し、本発明においては、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００１８】
（６）本発明は、（４）の秘密情報復元方法について、前記第２のステップにおいて、単位行列を生成し、該生成した単位行列を行基本変形して、第１の行列を生成し（例えば、図９のステップＳ２０３に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し（例えば、図９のステップＳ２０４に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し（例えば、図９のステップＳ２０５に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する（例えば、図９のステップＳ２０６に相当）ことを特徴とする秘密情報復元方法を提案している。
【００１９】
この発明によれば、第２のステップにおいて、単位行列を生成し、生成した単位行列を行基本変形して、第１の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第１の行列を行基本変形して、第２の行列を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、第２の行列を行基本変形して、第３の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。したがって、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００２０】
（７）本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップ（例えば、図４のステップＳ１０１に相当）と、前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップ（例えば、図４のステップＳ１０２からステップＳ１０６に相当）と、該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップ（例えば、図４のステップＳ１０７に相当）と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップ（例えば、図４のステップＳ１０８に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２１】
この発明によれば、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成し、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力して、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。そして、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。したがって、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみで、秘密情報を復元するための分散情報の組み合わせ表す行列を生成することができる。
【００２２】
（８）本発明は、（７）のプログラムについて、前記第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成（例えば、図４のステップＳ１０２に相当）し、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し（例えば、図４のステップＳ１０３に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し（例えば、図４のステップＳ１０４に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し（例えば、図４のステップＳ１０５に相当）、前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する（例えば、図４のステップＳ１０６に相当）ことを特徴とするプログラムを提案している。
【００２３】
この発明によれば、第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する。したがって、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があるのに対し、本発明においては、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００２４】
（９）本発明は、（７）のプログラムについて、前記第２のステップにおいて、単位行列を生成し、該生成した単位行列を行基本変形して、第１の行列を生成し（例えば、図９のステップＳ２０３に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し（例えば、図９のステップＳ２０４に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し（例えば、図９のステップＳ２０５に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する（例えば、図９のステップＳ２０６に相当）ことを特徴とするプログラムを提案している。
【００２５】
この発明によれば、第２のステップにおいて、単位行列を生成し、生成した単位行列を行基本変形して、第１の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第１の行列を行基本変形して、第２の行列を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、第２の行列を行基本変形して、第３の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。したがって、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【発明の効果】
【００２６】
本発明によれば、事前計算の実装において、条件判定・条件分岐の回数を大幅に削減することができるという効果がある。また、行列の機械的な導出を行うことにより、探索演算を行うことなく、組み合わせを示す行列を一意に決定することができるため、行列導出における理論上の計算量はＯ（１）となり、非常に微小なものとなる。こうしたことから、秘密情報を復元するための分散情報の組み合わせ導出のための演算量を大幅に削減でき、ＸＯＲを用いた高速な（ｋ、ｎ）閾値秘密分散法において、より高速な復元処理が可能となるという効果がある。
【発明を実施するための最良の形態】
【００２７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２８】
まず、本発明の秘密情報復元処理の説明の前に、分散情報の生成について説明する。図１は、分散情報の生成の概要を示す機能ブロック図である。
【００２９】
図１において、秘密情報Ｋは分割器１１に送られ、（ｎｐ−１）個の部分秘密情報Ｋｑに分割される。また、ダミー情報生成器１２でダミー部分秘密情報Ｋ０が生成される。ダミー部分秘密情報Ｋ０及び部分秘密情報Ｋｑは、部分分散情報生成器１３に送られる。
【００３０】
また、乱数発生器１４は、互いに独立な乱数Ｒを発生している。そして、同様な乱数発生器１４をｋ−１個備えている。乱数発生器１４からの乱数Ｒは、部分分散情報生成器１３に送られる。
【００３１】
部分分散情報生成器１３では、ダミー部分秘密情報Ｋ０及び（ｎｐ−１）個の部分秘密情報Ｋｑと、乱数発生器１４からの乱数Ｒとを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報が生成される。この部分分散情報が連結器１６により連結されて、ｎ個の分散情報Ｓｉが生成される。この分散情報Ｓｉは、送信装置１７により、管理者Ｐｉにセキュアに送信される。
【００３２】
なお、秘密情報を（ｎｐ−１）個に等分割する必要がある。但し、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３３】
次に、閾値秘密分散法について、更に、詳述する。先ず、閾値秘密分散法を説明するに先立ち、本明細書中で使用する演算子及び記号について、以下のように、定義する。
【００３４】
【数１】
【００３５】
先ず、分散処理方法について説明する。閾値秘密分散法では、以下の手順に従って分散処理を行って、（ｋ，ｎ）閾値秘密分散法が実現される。
【００３６】
なお、前述したように、秘密情報Ｋは、（ｎｐ−１）個に等分割する必要があり、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値秘密分散法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３７】
（ステップ１）
秘密情報Ｋを（ｎｐ−１）個の部分秘密情報Ｋｑに分割する。
【００３８】
【数２】
【００３９】
（ステップ２）
ダミーの部分秘密情報Ｋ０を生成する。
【００４０】
（ステップ３）
ｎｐ個ずつの乱数Ｒｌ０、・・・、Ｒｌｋ−２の計（ｋ−１）ｎｐ個の乱数を全て独立に生成する。
【００４１】
（ステップ４）
ＸＯＲ演算により、以下のように部分分散情報Ｓ（ｉ，ｍ）を生成する。
【００４２】
【数３】
【００４３】
（ステップ５）
部分分散情報Ｓ（ｉ、０）、・・・、Ｓ（ｉ，ｎｐ−２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉへセキュアに配付する。
【００４４】
【数４】
【００４５】
以上のステップにより構成される部分分散情報の構成表は、表１のようになる。また、１人の管理者に配布されるビット数は、Ｋのビット数と等しくなる。
【００４６】
【表１】
【００４７】
＜秘密情報復元装置の構成＞
上記の分散情報の生成処理を踏まえて、本発明の秘密情報復元装置について説明する。本実施形態に係る秘密情報復元装置は、図２に示すように、分散情報分割部２１と、行列生成部２２と、部分秘密情報復元部２３と、連結部２４とから構成されている。
【００４８】
分散情報分割部２１は、例えば、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する。行列生成部２２は、例えば、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。部分秘密情報復元部２３は、行列生成部２２において生成された行列を部分分散情報に適用して、部分秘密情報を復元する。連結部２４は、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。
【００４９】
また、行列生成部２２は、図３に示すように、行列Ｘ０生成器３１と、行列Ｘ１生成器３２と、行列Ｘｍ−１生成器３３ａ、３３ｍと、行列Ｘｋ−１生成器３４と、行列Ｍ生成器３５とから構成されている。
【００５０】
ここで、行列Ｘ０生成器３１は、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する。行列Ｘ１生成器３２は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する。行列Ｘｍ−１生成器３３ａ、３３ｍは、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する。行列Ｘｋ−１生成器３４は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する。行列Ｍ生成器３５は、行列Ｘ０生成器３１、行列Ｘ１生成器３２、行列Ｘｍ−１生成器３３ａ、３３ｍ、行列Ｘｋ−１生成器３４において生成されたそれぞれの行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列Ｍを生成する。
【００５１】
＜秘密情報復元装置の処理＞
次に、図４から図７を用いて、本実施形態に係る秘密情報復元装置の処理について説明する。
まず、分散情報分割部２１にｋ個の分散情報が入力され、ｋ（ｎｐ−１）個の部分分散情報が生成されて、部分秘密情報復元部２３に出力される（ステップＳ１０１）。一方、行列生成部２２には、ｋ個の分散情報についてのインデックス番号が入力される。
【００５２】
そして、行列Ｘ０生成器３１では、数５に示すようなｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０が生成される（ステップＳ１０２）。なお、数５において、Ｉは、（ｎｐ−１）行（ｎｐ−１）列の単位行列である。
【００５３】
【数５】
【００５４】
行列Ｘ１生成器３２では、数６に示すように、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１が生成される（ステップＳ１０３）。なお、数６において、Ｆｉ２、Ｇｉ２（２≦ｉ≦ｋ−１）は、インデックスの値のみから機械的に生成される（ｎｐ−１）行（ｎｐ−１）列のバイナリ行列であり、具体的には、図５に示すようなアルゴリズムで生成される。
【００５５】
【数６】
【００５６】
行列Ｘｍ−１生成器３３ａ、３３ｍでは、数７に示すように、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１が生成される（ステップＳ１０４）。なお、数７において、Ｆｉｍ、Ｇｉｍ（ｍ≦ｉ≦ｋ−１）は、インデックスの値のみから機械的に生成される（ｎｐ−１）行（ｎｐ−１）列のバイナリ行列であり、具体的には、図６に示すようなアルゴリズムで生成される。
【００５７】
【数７】
【００５８】
行列Ｘｋ−１生成器３４では、数８に示すように、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１が生成される（ステップＳ１０５）。なお、数８において、Ｚは、インデックスの値のみから機械的に生成される（ｎｐ−１）行（ｎｐ−１）列のバイナリ行列であり、具体的には、図７に示すようなアルゴリズムで生成される。
【００５９】
【数８】
【００６０】
そして、行列Ｍ生成器３５において、行列Ｘ０生成器３１の出力Ｘ０、行列Ｘ１生成器３２の出力Ｘ１、行列Ｘｍ−１生成器３３ａ、３３ｍの出力Ｘｍ−１、行列Ｘｋ−１生成器３４の出力Ｘｋ−１を数９に従って乗じ、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列Ｍを生成する（ステップＳ１０６）。
【００６１】
【数９】
【００６２】
生成された行列Ｍは、部分秘密情報復元部２３に入力され、行列Ｍをｋ（ｎｐ−１）個の部分分散情報に適用して、部分秘密情報を復元する（ステップＳ１０７）。そして、連結部２４において、復元された部分秘密情報を連結して秘密情報Ｋを復元する（ステップＳ１０８）。
【００６３】
したがって、本実施形態によれば、秘密情報を復元するための分散情報の組み合わせを示す行列を機械的に構築することから、従来のように、分散情報の生成行列を構築する必要がなく、さらには分散情報の生成行列内部の要素が何であるかを条件判定して処理を振り分け、生成行列を変形していく、というような逆行列の探索処理が一切必要なく、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみがわかれば、秘密情報を復元するための分散情報の組み合わせ表す行列を生成できる。
【００６４】
また、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があったが、上記の方法によれば、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００６５】
＜変形例＞
次に、図８および図９を用いて、上記実施形態の変形例について説明する。
本変形例は、上記の実施形態に対して、行列生成部２２の構成が異なっている。具体的は、本変形例に係る行列生成部は、図８に示すように、単位行列生成器４１と、行基本変形演算器４２と、行基本変形演算器４３と、行基本変形演算器４４ａ、４４ｍと、行基本変形演算器４５とからなり、これらが直列に接続されている。
【００６６】
ここで、単位行列生成器４１は、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列の単位行列を生成する。行基本変形演算器４２は、生成された単位行列を行基本変形し、第１の行列を生成する。行基本変形演算器４３は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４２において演算された第１の行列を行基本変形し、第２の行列を生成する。
【００６７】
行基本変形演算器４４ａ、４４ｍは、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、行基本変形演算器４３において演算された行列を行基本変形し、第３の行列を生成する。行基本変形演算器４５は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４４ａ、４４ｍにおいて演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。
【００６８】
＜秘密情報の復元処理＞
次に、図９を用いて、本変形例における秘密情報の復元処理について説明する。
まず、分散情報分割部２１にｋ個の分散情報が入力され、ｋ（ｎｐ−１）個の部分分散情報が生成されて、部分秘密情報復元部２３に出力される（ステップＳ２０１）。一方、行列生成部２２には、ｋ個の分散情報についてのインデックス番号が入力される。
【００６９】
そして、単位行列生成器４１において、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列の単位行列が生成される（ステップＳ２０２）。行基本変形演算器４２では、生成された単位行列を行基本変形し、第１の行列を生成する（ステップＳ２０３）。行基本変形演算器４３では、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４２において演算された第１の行列を行基本変形し、第２の行列を生成する（ステップＳ２０４）。
【００７０】
行基本変形演算器４４ａ、４４ｍでは、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、行基本変形演算器４３において演算された行列を行基本変形し、第３の行列を生成する（ステップＳ２０５）。行基本変形演算器４５では、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４４ａ、４４ｍにおいて演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する（ステップＳ２０６）。
【００７１】
そして、生成された行列は、部分秘密情報復元部２３に入力され、行列をｋ（ｎｐ−１）個の部分分散情報に適用して、部分秘密情報を復元する（ステップＳ２０７）。さらに、連結部２４において、復元された部分秘密情報を連結して秘密情報Ｋを復元する（ステップＳ２０８）。
【００７２】
したがって、本変形例によれば、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００７３】
なお、秘密情報復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを秘密情報復元装置に読み込ませ、実行することによって本発明の秘密情報復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００７４】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００７５】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００７６】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００７７】
【図１】ＸＯＲを用いた（ｋ、ｎ）閾値法における分散情報生成装置の構成を例示した図である。
【図２】本実施形態に係る秘密情報復元装置の構成図である。
【図３】本実施形態に係る行列生成部の構成図である。
【図４】本実施形態に係る秘密情報復元処理のフローである。
【図５】行列Ｘ１生成器３２において、Ｆｉ２、Ｇｉ２（２≦ｉ≦ｋ−１）を生成するためのアルゴリズムを例示した図である。
【図６】行列Ｘ１生成器３３ａ、３３ｍにおいて、Ｆｉｍ、Ｇｉｍ（ｍ≦ｉ≦ｋ−１）を生成するためのアルゴリズムを例示した図である。
【図７】行列Ｘ１生成器３４において、Ｚを生成するためのアルゴリズムを例示した図である。
【図８】本変形例における行列生成部の構成図である。
【図９】本変形例に係る秘密情報復元処理のフローである。
【符号の説明】
【００７８】
１１・・・分割器、１２・・・ダミー情報生成器、１３・・・部分分散情報生成器、１４・・・乱数発生器、１６・・・連結器、１７・・・送信装置、２１・・・分散情報分割部、２２・・・行列生成部、２３・・・部分秘密情報復元部、２４・・・連結部、３１・・・行列Ｘ０生成器、３２・・・行列Ｘ１生成器、３３ａ、３３ｍ・・・行列Ｘｍ−１生成器、３４・・・行列Ｘｋ−１生成器、３５・・・行列Ｍ生成器、４１・・・単位行列生成器、４２、４３、４４ａ、４４ｍ、４５・・・行基本変形演算器
【技術分野】
【０００１】
本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元装置、秘密情報復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献１に示されるような（ｋ，ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｋ，ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｋ個の分散情報が集まれば、復元できることを意味する。
【０００３】
しかしながら、非特許文献１に示されている（ｋ，ｎ）閾値秘密分散法は、情報の分散、復元時に、（ｋ−１）次の多項式を処理する必要があり、その計算量が膨大になる。
【０００４】
これに対して、ＸＯＲを用いて、（ｋ，ｎ）閾値秘密分散法を構築することにより、高速に情報の分散および復元を可能とする方式が開示されている（例えば、非特許文献２および３参照。）。この非特許文献２および３で開示された方法は、その構造において等価なものであり、単純に高速動作を行うだけでなく、非特許文献１と同様に、完全な情報論理的安全性が保証されており、分散情報のデータ長が秘密情報のデータ長と等しいという特徴を有している。
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ ｔｏ Ｓｈａｒｅ ａ Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎ．ＡＣＭ， ｖｏｌ．２２ ｎｏ．１１ ｐｐ．６１２−６１３， １９７９．
【非特許文献２】Ｊ．Ｋｕｒｉｈａｒａ、Ｓ．Ｋｉｙｏｍｏｔｏ、Ｋ．Ｆｕｋｕｓｈｉｍａ、Ｔ．Ｔａｎａｋａ、“Ａ Ｆａｓｔ （４、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ Ｓｃｈｅｍｅ Ｕｓｉｎｇ Ｅｘｃｌｕｓｉｖｅ−ＯＲ Ｏｐｅｒａｔｉｏｎ ａｎｄ ｉｔｓ Ｅｘｔｅｎｓｉｏｎ ｔｏ （ｋ、ｎ）−Ｔｈｒｅｓｈｏｌｄ Ｓｃｈｅｍｅｓ”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−４
【非特許文献３】藤井吉弘、栃窪孝也、保坂範和、多田美奈子、加藤岳久、“排他的論理和を用いた（ｋ、ｎ）しきい値法の構成法”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−５
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献２または３に記載された技術では、秘密情報の復元時に、分散情報の生成行列を構成し、その全体に、あるいは行列を分割してブロックごとに、ガウスの消去法や、ＬＵ分解、ガウスジョルダンの消去法など逆行列探索演算を行うことで、秘密情報を復元するための分散情報の組み合わせを探索していた(以降、「事前計算」と呼ぶ)。このとき、事前計算にかかる演算量は生成行列の行数をＲとすると、Ｏ（Ｒ３）、即ち、行列の行数の三乗倍となる。また、生成行列のサイズはｋ、ｎに依存しており、ｋ、ｎが大きければ大きいほど事前計算の演算量が増加していくという問題がある。
【０００６】
また、事前計算では、「探索」の作業、即ち、行列の特定の部分の数値が何であるかを条件判定し、それよって処理を振り分けることが必要となる。これは、条件分岐の多さを意味しており、プログラム・装置等に実装した場合に動作が低速になるという問題がある。例えば、プログラムの場合、等価な処理を行う論理的記述(出来る限り条件分岐をなくした記述)をしたプログラムとｉｆ文記述を多用したプログラムとでは、コンピュータの性質上、前者の方が高速に動作することが知られている。
【０００７】
そこで、本発明は、上述の課題に鑑みてなされたものであり、ＸＯＲを用いた（ｋ、ｎ）閾値分散法において、秘密情報の高速な復元を可能とする秘密情報復元装置、秘密情報復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記の課題を解決するために、以下の事項を提案している。
（１）本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する部分分散情報生成手段（例えば、図２の分散情報分割部２１に相当）と、前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する行列生成手段（例えば、図２の行列生成部２２に相当）と、該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する復元手段（例えば、図２の部分秘密情報復元部２３に相当）と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段（例えば、図２の連結部２４に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【０００９】
この発明によれば、部分分散情報生成手段は、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する。行列生成手段は、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。復元手段は、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、連結手段は、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。したがって、秘密情報を復元するための分散情報の組み合わせを示す行列を機械的に構築することから、従来のように、分散情報の生成行列を構築する必要がなく、さらには分散情報の生成行列内部の要素が何であるかを条件判定して処理を振り分け、生成行列を変形していく、というような逆行列の探索処理が一切必要なく、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみがわかれば、秘密情報を復元するための分散情報の組み合わせ表す行列を生成できる。
【００１０】
（２）本発明は、（１）の秘密情報復元装置について、前記行列生成手段が、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する第１の行列生成器（例えば、図３の行列Ｘ０生成器３１に相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する第２の行列生成器（例えば、図３の行列Ｘ１生成器３２に相当）と、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する第３の行列生成器（例えば、図３の行列Ｘｍ−１生成器３３ａ、３３ｍに相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する第４の行列生成器（例えば、図３の行列Ｘｋ−１生成器３４に相当）と、前記第１の行列生成器から第４の行列生成器において生成された行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する第５の行列生成器（例えば、図３の行列Ｍ生成器３５に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１１】
この発明によれば、行列生成手段が、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する第１の行列生成器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する第２の行列生成器と、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する第３の行列生成器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する第４の行列生成器とを並列に備え、第５の行列生成器が、第１の行列生成器から第４の行列生成器において生成された行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する。したがって、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があるのに対し、本発明においては、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００１２】
（３）本発明は、（１）の秘密情報復元装置について、前記行列生成手段が、単位行列を生成する単位行列生成器（例えば、図８の単位行列生成器４１に相当）と、該生成した単位行列を行基本変形する第１の行基本変形演算器（例えば、図８の行基本変形演算器４２に相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行基本変形演算器において演算された行列を行基本変形する第２の行基本変形演算器（例えば、図８の行基本変形演算器４３に相当）と、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行基本変形演算器において演算された行列を行基本変形する第３の行基本変形演算器（例えば、図８の行基本変形演算器４４ａ、４４ｍに相当）と、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行基本変形演算器において演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第４の行基本変形演算器（例えば、図８の行基本変形演算器４５に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１３】
この発明によれば、行列生成手段が、単位行列を生成する単位行列生成器と、生成した単位行列を行基本変形する第１の行基本変形演算器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第１の行基本変形演算器において演算された行列を行基本変形する第２の行基本変形演算器と、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、第２の行基本変形演算器において演算された行列を行基本変形する第３の行基本変形演算器と、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第３の行基本変形演算器において演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する第４の行基本変形演算器とを備えている。したがって、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００１４】
（４）本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップ（例えば、図４のステップＳ１０１に相当）と、前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップ（例えば、図４のステップＳ１０２からステップＳ１０６に相当）と、該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップ（例えば、図４のステップＳ１０７に相当）と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップ（例えば、図４のステップＳ１０８に相当）と、を備えたことを特徴とする秘密情報復元方法を提案している。
【００１５】
この発明によれば、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成し、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力して、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。そして、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。したがって、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみで、秘密情報を復元するための分散情報の組み合わせ表す行列を生成することができる。
【００１６】
（５）本発明は、（４）の秘密情報復元方法について、前記第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成（例えば、図４のステップＳ１０２に相当）し、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し（例えば、図４のステップＳ１０３に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し（例えば、図４のステップＳ１０４に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し（例えば、図４のステップＳ１０５に相当）、前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する（例えば、図４のステップＳ１０６に相当）ことを特徴とする秘密情報復元方法を提案している。
【００１７】
この発明によれば、第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する。したがって、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があるのに対し、本発明においては、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００１８】
（６）本発明は、（４）の秘密情報復元方法について、前記第２のステップにおいて、単位行列を生成し、該生成した単位行列を行基本変形して、第１の行列を生成し（例えば、図９のステップＳ２０３に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し（例えば、図９のステップＳ２０４に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し（例えば、図９のステップＳ２０５に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する（例えば、図９のステップＳ２０６に相当）ことを特徴とする秘密情報復元方法を提案している。
【００１９】
この発明によれば、第２のステップにおいて、単位行列を生成し、生成した単位行列を行基本変形して、第１の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第１の行列を行基本変形して、第２の行列を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、第２の行列を行基本変形して、第３の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。したがって、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００２０】
（７）本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップ（例えば、図４のステップＳ１０１に相当）と、前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップ（例えば、図４のステップＳ１０２からステップＳ１０６に相当）と、該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップ（例えば、図４のステップＳ１０７に相当）と、該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップ（例えば、図４のステップＳ１０８に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２１】
この発明によれば、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成し、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力して、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。そして、生成された行列を部分分散情報に適用して、部分秘密情報を復元し、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。したがって、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみで、秘密情報を復元するための分散情報の組み合わせ表す行列を生成することができる。
【００２２】
（８）本発明は、（７）のプログラムについて、前記第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成（例えば、図４のステップＳ１０２に相当）し、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し（例えば、図４のステップＳ１０３に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し（例えば、図４のステップＳ１０４に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し（例えば、図４のステップＳ１０５に相当）、前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する（例えば、図４のステップＳ１０６に相当）ことを特徴とするプログラムを提案している。
【００２３】
この発明によれば、第２のステップにおいて、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する。したがって、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があるのに対し、本発明においては、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００２４】
（９）本発明は、（７）のプログラムについて、前記第２のステップにおいて、単位行列を生成し、該生成した単位行列を行基本変形して、第１の行列を生成し（例えば、図９のステップＳ２０３に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し（例えば、図９のステップＳ２０４に相当）、前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し（例えば、図９のステップＳ２０５に相当）、前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する（例えば、図９のステップＳ２０６に相当）ことを特徴とするプログラムを提案している。
【００２５】
この発明によれば、第２のステップにおいて、単位行列を生成し、生成した単位行列を行基本変形して、第１の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第１の行列を行基本変形して、第２の行列を生成し、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、第２の行列を行基本変形して、第３の行列を生成し、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。したがって、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【発明の効果】
【００２６】
本発明によれば、事前計算の実装において、条件判定・条件分岐の回数を大幅に削減することができるという効果がある。また、行列の機械的な導出を行うことにより、探索演算を行うことなく、組み合わせを示す行列を一意に決定することができるため、行列導出における理論上の計算量はＯ（１）となり、非常に微小なものとなる。こうしたことから、秘密情報を復元するための分散情報の組み合わせ導出のための演算量を大幅に削減でき、ＸＯＲを用いた高速な（ｋ、ｎ）閾値秘密分散法において、より高速な復元処理が可能となるという効果がある。
【発明を実施するための最良の形態】
【００２７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２８】
まず、本発明の秘密情報復元処理の説明の前に、分散情報の生成について説明する。図１は、分散情報の生成の概要を示す機能ブロック図である。
【００２９】
図１において、秘密情報Ｋは分割器１１に送られ、（ｎｐ−１）個の部分秘密情報Ｋｑに分割される。また、ダミー情報生成器１２でダミー部分秘密情報Ｋ０が生成される。ダミー部分秘密情報Ｋ０及び部分秘密情報Ｋｑは、部分分散情報生成器１３に送られる。
【００３０】
また、乱数発生器１４は、互いに独立な乱数Ｒを発生している。そして、同様な乱数発生器１４をｋ−１個備えている。乱数発生器１４からの乱数Ｒは、部分分散情報生成器１３に送られる。
【００３１】
部分分散情報生成器１３では、ダミー部分秘密情報Ｋ０及び（ｎｐ−１）個の部分秘密情報Ｋｑと、乱数発生器１４からの乱数Ｒとを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報が生成される。この部分分散情報が連結器１６により連結されて、ｎ個の分散情報Ｓｉが生成される。この分散情報Ｓｉは、送信装置１７により、管理者Ｐｉにセキュアに送信される。
【００３２】
なお、秘密情報を（ｎｐ−１）個に等分割する必要がある。但し、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３３】
次に、閾値秘密分散法について、更に、詳述する。先ず、閾値秘密分散法を説明するに先立ち、本明細書中で使用する演算子及び記号について、以下のように、定義する。
【００３４】
【数１】
【００３５】
先ず、分散処理方法について説明する。閾値秘密分散法では、以下の手順に従って分散処理を行って、（ｋ，ｎ）閾値秘密分散法が実現される。
【００３６】
なお、前述したように、秘密情報Ｋは、（ｎｐ−１）個に等分割する必要があり、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値秘密分散法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３７】
（ステップ１）
秘密情報Ｋを（ｎｐ−１）個の部分秘密情報Ｋｑに分割する。
【００３８】
【数２】
【００３９】
（ステップ２）
ダミーの部分秘密情報Ｋ０を生成する。
【００４０】
（ステップ３）
ｎｐ個ずつの乱数Ｒｌ０、・・・、Ｒｌｋ−２の計（ｋ−１）ｎｐ個の乱数を全て独立に生成する。
【００４１】
（ステップ４）
ＸＯＲ演算により、以下のように部分分散情報Ｓ（ｉ，ｍ）を生成する。
【００４２】
【数３】
【００４３】
（ステップ５）
部分分散情報Ｓ（ｉ、０）、・・・、Ｓ（ｉ，ｎｐ−２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉへセキュアに配付する。
【００４４】
【数４】
【００４５】
以上のステップにより構成される部分分散情報の構成表は、表１のようになる。また、１人の管理者に配布されるビット数は、Ｋのビット数と等しくなる。
【００４６】
【表１】
【００４７】
＜秘密情報復元装置の構成＞
上記の分散情報の生成処理を踏まえて、本発明の秘密情報復元装置について説明する。本実施形態に係る秘密情報復元装置は、図２に示すように、分散情報分割部２１と、行列生成部２２と、部分秘密情報復元部２３と、連結部２４とから構成されている。
【００４８】
分散情報分割部２１は、例えば、ｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する。行列生成部２２は、例えば、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。部分秘密情報復元部２３は、行列生成部２２において生成された行列を部分分散情報に適用して、部分秘密情報を復元する。連結部２４は、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。
【００４９】
また、行列生成部２２は、図３に示すように、行列Ｘ０生成器３１と、行列Ｘ１生成器３２と、行列Ｘｍ−１生成器３３ａ、３３ｍと、行列Ｘｋ−１生成器３４と、行列Ｍ生成器３５とから構成されている。
【００５０】
ここで、行列Ｘ０生成器３１は、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する。行列Ｘ１生成器３２は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する。行列Ｘｍ−１生成器３３ａ、３３ｍは、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する。行列Ｘｋ−１生成器３４は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する。行列Ｍ生成器３５は、行列Ｘ０生成器３１、行列Ｘ１生成器３２、行列Ｘｍ−１生成器３３ａ、３３ｍ、行列Ｘｋ−１生成器３４において生成されたそれぞれの行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列Ｍを生成する。
【００５１】
＜秘密情報復元装置の処理＞
次に、図４から図７を用いて、本実施形態に係る秘密情報復元装置の処理について説明する。
まず、分散情報分割部２１にｋ個の分散情報が入力され、ｋ（ｎｐ−１）個の部分分散情報が生成されて、部分秘密情報復元部２３に出力される（ステップＳ１０１）。一方、行列生成部２２には、ｋ個の分散情報についてのインデックス番号が入力される。
【００５２】
そして、行列Ｘ０生成器３１では、数５に示すようなｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０が生成される（ステップＳ１０２）。なお、数５において、Ｉは、（ｎｐ−１）行（ｎｐ−１）列の単位行列である。
【００５３】
【数５】
【００５４】
行列Ｘ１生成器３２では、数６に示すように、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１が生成される（ステップＳ１０３）。なお、数６において、Ｆｉ２、Ｇｉ２（２≦ｉ≦ｋ−１）は、インデックスの値のみから機械的に生成される（ｎｐ−１）行（ｎｐ−１）列のバイナリ行列であり、具体的には、図５に示すようなアルゴリズムで生成される。
【００５５】
【数６】
【００５６】
行列Ｘｍ−１生成器３３ａ、３３ｍでは、数７に示すように、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１が生成される（ステップＳ１０４）。なお、数７において、Ｆｉｍ、Ｇｉｍ（ｍ≦ｉ≦ｋ−１）は、インデックスの値のみから機械的に生成される（ｎｐ−１）行（ｎｐ−１）列のバイナリ行列であり、具体的には、図６に示すようなアルゴリズムで生成される。
【００５７】
【数７】
【００５８】
行列Ｘｋ−１生成器３４では、数８に示すように、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１が生成される（ステップＳ１０５）。なお、数８において、Ｚは、インデックスの値のみから機械的に生成される（ｎｐ−１）行（ｎｐ−１）列のバイナリ行列であり、具体的には、図７に示すようなアルゴリズムで生成される。
【００５９】
【数８】
【００６０】
そして、行列Ｍ生成器３５において、行列Ｘ０生成器３１の出力Ｘ０、行列Ｘ１生成器３２の出力Ｘ１、行列Ｘｍ−１生成器３３ａ、３３ｍの出力Ｘｍ−１、行列Ｘｋ−１生成器３４の出力Ｘｋ−１を数９に従って乗じ、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列Ｍを生成する（ステップＳ１０６）。
【００６１】
【数９】
【００６２】
生成された行列Ｍは、部分秘密情報復元部２３に入力され、行列Ｍをｋ（ｎｐ−１）個の部分分散情報に適用して、部分秘密情報を復元する（ステップＳ１０７）。そして、連結部２４において、復元された部分秘密情報を連結して秘密情報Ｋを復元する（ステップＳ１０８）。
【００６３】
したがって、本実施形態によれば、秘密情報を復元するための分散情報の組み合わせを示す行列を機械的に構築することから、従来のように、分散情報の生成行列を構築する必要がなく、さらには分散情報の生成行列内部の要素が何であるかを条件判定して処理を振り分け、生成行列を変形していく、というような逆行列の探索処理が一切必要なく、単純に分散情報のインデックス番号(それぞれ何番目の分散情報かを示したもの。)のみがわかれば、秘密情報を復元するための分散情報の組み合わせ表す行列を生成できる。
【００６４】
また、従来は、内部での処理手順として生成行列を生成・分割した上で、その一部に対して逆行列探索演算を複数回繰り返す必要があったが、上記の方法によれば、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００６５】
＜変形例＞
次に、図８および図９を用いて、上記実施形態の変形例について説明する。
本変形例は、上記の実施形態に対して、行列生成部２２の構成が異なっている。具体的は、本変形例に係る行列生成部は、図８に示すように、単位行列生成器４１と、行基本変形演算器４２と、行基本変形演算器４３と、行基本変形演算器４４ａ、４４ｍと、行基本変形演算器４５とからなり、これらが直列に接続されている。
【００６６】
ここで、単位行列生成器４１は、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列の単位行列を生成する。行基本変形演算器４２は、生成された単位行列を行基本変形し、第１の行列を生成する。行基本変形演算器４３は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４２において演算された第１の行列を行基本変形し、第２の行列を生成する。
【００６７】
行基本変形演算器４４ａ、４４ｍは、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、行基本変形演算器４３において演算された行列を行基本変形し、第３の行列を生成する。行基本変形演算器４５は、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４４ａ、４４ｍにおいて演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。
【００６８】
＜秘密情報の復元処理＞
次に、図９を用いて、本変形例における秘密情報の復元処理について説明する。
まず、分散情報分割部２１にｋ個の分散情報が入力され、ｋ（ｎｐ−１）個の部分分散情報が生成されて、部分秘密情報復元部２３に出力される（ステップＳ２０１）。一方、行列生成部２２には、ｋ個の分散情報についてのインデックス番号が入力される。
【００６９】
そして、単位行列生成器４１において、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列の単位行列が生成される（ステップＳ２０２）。行基本変形演算器４２では、生成された単位行列を行基本変形し、第１の行列を生成する（ステップＳ２０３）。行基本変形演算器４３では、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４２において演算された第１の行列を行基本変形し、第２の行列を生成する（ステップＳ２０４）。
【００７０】
行基本変形演算器４４ａ、４４ｍでは、インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、行基本変形演算器４３において演算された行列を行基本変形し、第３の行列を生成する（ステップＳ２０５）。行基本変形演算器４５では、インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、行基本変形演算器４４ａ、４４ｍにおいて演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する（ステップＳ２０６）。
【００７１】
そして、生成された行列は、部分秘密情報復元部２３に入力され、行列をｋ（ｎｐ−１）個の部分分散情報に適用して、部分秘密情報を復元する（ステップＳ２０７）。さらに、連結部２４において、復元された部分秘密情報を連結して秘密情報Ｋを復元する（ステップＳ２０８）。
【００７２】
したがって、本変形例によれば、逆行列を複数求めるのではなく、直接、単位行列を変形することにより、組み合わせを示す行列をインデックス番号のみより完全に機械的に求めることができる。
【００７３】
なお、秘密情報復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを秘密情報復元装置に読み込ませ、実行することによって本発明の秘密情報復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００７４】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００７５】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００７６】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００７７】
【図１】ＸＯＲを用いた（ｋ、ｎ）閾値法における分散情報生成装置の構成を例示した図である。
【図２】本実施形態に係る秘密情報復元装置の構成図である。
【図３】本実施形態に係る行列生成部の構成図である。
【図４】本実施形態に係る秘密情報復元処理のフローである。
【図５】行列Ｘ１生成器３２において、Ｆｉ２、Ｇｉ２（２≦ｉ≦ｋ−１）を生成するためのアルゴリズムを例示した図である。
【図６】行列Ｘ１生成器３３ａ、３３ｍにおいて、Ｆｉｍ、Ｇｉｍ（ｍ≦ｉ≦ｋ−１）を生成するためのアルゴリズムを例示した図である。
【図７】行列Ｘ１生成器３４において、Ｚを生成するためのアルゴリズムを例示した図である。
【図８】本変形例における行列生成部の構成図である。
【図９】本変形例に係る秘密情報復元処理のフローである。
【符号の説明】
【００７８】
１１・・・分割器、１２・・・ダミー情報生成器、１３・・・部分分散情報生成器、１４・・・乱数発生器、１６・・・連結器、１７・・・送信装置、２１・・・分散情報分割部、２２・・・行列生成部、２３・・・部分秘密情報復元部、２４・・・連結部、３１・・・行列Ｘ０生成器、３２・・・行列Ｘ１生成器、３３ａ、３３ｍ・・・行列Ｘｍ−１生成器、３４・・・行列Ｘｋ−１生成器、３５・・・行列Ｍ生成器、４１・・・単位行列生成器、４２、４３、４４ａ、４４ｍ、４５・・・行基本変形演算器
【特許請求の範囲】
【請求項１】
ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、
ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する部分分散情報生成手段と、
前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する行列生成手段と、
該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する復元手段と、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段と、
を備えたことを特徴とする秘密情報復元装置。
【請求項２】
前記行列生成手段が、
ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する第１の行列生成器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する第２の行列生成器と、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する第３の行列生成器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する第４の行列生成器と、
前記第１の行列生成器から第４の行列生成器において生成された行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する第５の行列生成器と、
を備えたことを特徴とする請求項１に記載の秘密情報復元装置。
【請求項３】
前記行列生成手段が、
単位行列を生成する単位行列生成器と、
該生成した単位行列を行基本変形する第１の行基本変形演算器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行基本変形演算器において演算された行列を行基本変形する第２の行基本変形演算器と、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行基本変形演算器において演算された行列を行基本変形する第３の行基本変形演算器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行基本変形演算器において演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第４の行基本変形演算器と、
を備えたことを特徴とする請求項１に記載の秘密情報復元装置。
【請求項４】
ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、
ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップと、
前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップと、
該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップと、
を備えたことを特徴とする秘密情報復元方法。
【請求項５】
前記第２のステップにおいて、
ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、
前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成することを特徴とする請求項４に記載の秘密情報復元方法。
【請求項６】
前記第２のステップにおいて、
単位行列を生成し、
該生成した単位行列を行基本変形して、第１の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成することを特徴とする請求項４に記載の秘密情報復元方法。
【請求項７】
ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップと、
前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップと、
該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項８】
前記第２のステップにおいて、
ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、
前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成することを特徴とする請求項７に記載のプログラム。
【請求項９】
前記第２のステップにおいて、
単位行列を生成し、
該生成した単位行列を行基本変形して、第１の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成することを特徴とする請求項７に記載のプログラム。
【請求項１】
ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、
ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する部分分散情報生成手段と、
前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する行列生成手段と、
該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する復元手段と、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する連結手段と、
を備えたことを特徴とする秘密情報復元装置。
【請求項２】
前記行列生成手段が、
ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成する第１の行列生成器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成する第２の行列生成器と、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成する第３の行列生成器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成する第４の行列生成器と、
前記第１の行列生成器から第４の行列生成器において生成された行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成する第５の行列生成器と、
を備えたことを特徴とする請求項１に記載の秘密情報復元装置。
【請求項３】
前記行列生成手段が、
単位行列を生成する単位行列生成器と、
該生成した単位行列を行基本変形する第１の行基本変形演算器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行基本変形演算器において演算された行列を行基本変形する第２の行基本変形演算器と、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行基本変形演算器において演算された行列を行基本変形する第３の行基本変形演算器と、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行基本変形演算器において演算された行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第４の行基本変形演算器と、
を備えたことを特徴とする請求項１に記載の秘密情報復元装置。
【請求項４】
ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、
ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップと、
前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップと、
該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップと、
を備えたことを特徴とする秘密情報復元方法。
【請求項５】
前記第２のステップにおいて、
ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、
前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成することを特徴とする請求項４に記載の秘密情報復元方法。
【請求項６】
前記第２のステップにおいて、
単位行列を生成し、
該生成した単位行列を行基本変形して、第１の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成することを特徴とする請求項４に記載の秘密情報復元方法。
【請求項７】
ＸＯＲを用いた（ｋ、ｎ）閾値分散法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
ｋ個（ｋは正の整数）の前記分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する第１のステップと、
前記ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成する第２のステップと、
該生成された行列を前記部分分散情報に適用して、部分秘密情報を復元する第３のステップと、
該復元した部分秘密情報を連結して元の秘密情報Ｋを生成する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項８】
前記第２のステップにおいて、
ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ０を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘ１を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｍ−１を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値により、ｋ（ｎｐ−１）行ｋ（ｎｐ−１）列のバイナリ行列Ｘｋ−１を生成し、
前記生成されたすべての行列を乗じて部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列Ｍを生成することを特徴とする請求項７に記載のプログラム。
【請求項９】
前記第２のステップにおいて、
単位行列を生成し、
該生成した単位行列を行基本変形して、第１の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第１の行列を行基本変形して、第２の行列を生成し、
前記インデックス番号ｔｍ−２、ｔｍ−１、・・・、ｔｋ−１（ｍ＝３、４、・・・、ｋ−１）の値に基づいて、該第２の行列を行基本変形して、第３の行列を生成し、
前記インデックス番号ｔ０、ｔ１、・・・、ｔｋ−１の値に基づいて、該第３の行列を行基本変形し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための前記部分分散情報の組み合わせを示す行列を生成することを特徴とする請求項７に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００９−２１７６５（Ｐ２００９−２１７６５Ａ）
【公開日】平成２１年１月２９日（２００９．１．２９）
【国際特許分類】
【出願番号】特願２００７−１８２０７０（Ｐ２００７−１８２０７０）
【出願日】平成１９年７月１１日（２００７．７．１１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２１年１月２９日（２００９．１．２９）
【国際特許分類】
【出願日】平成１９年７月１１日（２００７．７．１１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]