(57)【特許請求の範囲】
【請求項１】
排他的論理和演算を用いた（ｋ、ｎ）閾値分散法による分散情報生成装置であって、
素数と巡回群との性質を用いて、２つの乱数を重複しないように排他的論理和演算を行う第１の排他的論理和演算器と、
秘密情報を入力し、これを分割して部分秘密情報を生成する分割器と、
オールゼロからなるダミー情報を生成するダミー情報生成器と、
素数と巡回群との性質を用いて、該ダミー情報及び前記部分秘密情報のうち、２つの情報を重複しないように排他的論理和演算を行う第２の排他的論理和演算器と、
該第１の排他的論理和演算器において演算された情報と該第２の排他的論理和演算器で演算された情報との排他的論理和演算を行い、部分分散情報を出力する第３の排他的論理和演算器と、
該出力された部分分散情報を連結し、分散情報を出力する連結器と、
該出力された分散情報を管理者に送信する送信手段と、
を備えたことを特徴とする分散情報生成装置。
【請求項２】
前記分割器に入力される秘密情報のビット長と前記連結器から出力される分散情報のビット長とが等しいことを特徴とする請求項１に記載の分散情報生成装置。
【請求項３】
請求項１または請求項２に記載された分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、
分散情報を受信する受信手段と、
該受信した分散情報を分割して部分分散情報を生成する分散情報分割手段と、
該分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する行列生成手段と、
該行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元する部分秘密情報復元部と、
該復元された部分秘密情報を連結して秘密情報を出力する連結器と、
を備えたことを特徴とする秘密情報復元装置。
【請求項４】
分割器、ダミー情報生成器、乱数発生器、部分分散情報生成器、及び連結送信手段を備え、排他的論理和演算を用いた（ｋ、ｎ）閾値分散法による分散情報生成装置における分散情報生成方法であって、
前記分割器が、秘密情報Ｋをｎｐ−１個の部分秘密情報に分割する第１のステップと、
前記ダミー情報生成器が、ダミー秘密情報Ｋ0∈{0}ｄを生成する第２のステップと、
前記乱数発生器が、Ｎｐ個ずつの乱数Ｒ１ｌ、・・・、Ｒｋ-１ｌ（0≦ｌ≦ｎｐ-１）の計（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
前記部分分散情報生成器が、部分分散情報を数１を用いて生成する第４のステップと、
前記連結送信手段が、Ｓ（ｉ，0）、・・・、Ｓ（ｉ，ｎｐ-２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉに配布する第５のステップと、
を有することを特徴とする分散情報生成方法。
【数１】
0005191751.tif 000012
【請求項５】
分散情報分割手段、第１の行列生成手段、第２の行列生成手段、部分秘密情報復元手段、及び連結器を備え、請求項４に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元装置における秘密情報復元方法であって、
前記分散情報分割手段が、それぞれの分散情報を部分分散情報に分割し、数２のようなｋ（ｎｐ-１）個の部分分散情報を得る第１のステップと、
前記第１の行列生成手段が、前記部分分散情報の構成により、数３を満たすｋ（ｎｐ-１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
前記第２の行列生成手段が、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ  Ｉ]を変形し、行列[Ｍ´  Ｉ´]を得る第３のステップと、
前記部分秘密情報復元手段が、該生成したI´の第（ｋ-１）（ｎｐ-１）＋１行目からｋ（ｎｐ-１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
前記連結器が、すべての部分秘密情報を連結し、元の秘密情報Ｋを復元する第５のステップと、
を有することを特徴とする秘密情報復元方法。
【数２】
0005191751.tif 000013
【数３】
0005191751.tif 000014
【請求項６】
分割器、ダミー情報生成器、乱数発生器、部分分散情報生成器、及び連結送信手段を備え、排他的論理和演算を用いた（ｋ、ｎ）閾値分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、
前記分割器が、秘密情報Ｋをｎｐ−１個の部分秘密情報に分割する第１のステップと、
前記ダミー情報生成器が、ダミー秘密情報Ｋ0∈{0}ｄを生成する第２のステップと、
前記乱数発生器が、Ｎｐ個ずつの乱数Ｒ１ｌ、・・・、Ｒｋ-１ｌ（0≦ｌ≦ｎｐ-１）の計（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップと、
前記部分分散情報生成器が、部分分散情報を数４を用いて生成する第４のステップと、
前記連結送信手段が、Ｓ（ｉ，0）、・・・、Ｓ（ｉ，ｎｐ-２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉに配布する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数４】
0005191751.tif 000015
【請求項７】
分散情報分割手段、第１の行列生成手段、第２の行列生成手段、部分秘密情報復元手段、及び連結器を備え、請求項６に記載されたプログラムにより生成された分散情報から秘密情報を復元する秘密情報復元装置における秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
前記分散情報分割手段が、それぞれの分散情報を部分分散情報に分割し、数５のようなｋ（ｎｐ-１）個の部分分散情報を得る第１のステップと、
前記第１の行列生成手段が、前記部分分散情報の構成により、数６を満たすｋ（ｎｐ-１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップと、
前記第２の行列生成手段が、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ  Ｉ]を変形し、行列[Ｍ´  Ｉ´]を得る第３のステップと、
前記部分秘密情報復元手段が、該生成したI´の第（ｋ-１）（ｎｐ-１）＋１行目からｋ（ｎｐ-１）行目を用いて、全部の部分秘密情報を復元する第４のステップと、
前記連結器が、すべての部分秘密情報を連結し、元の秘密情報Ｋを復元する第５のステップと、
をコンピュータに実行させるためのプログラム。
【数５】
0005191751.tif 000016
【数６】
0005191751.tif 000017
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＸＯＲを用いた（ｋ、ｎ）閾値分散法により分散情報を生成する分散情報生成装置、分散情報生成方法および散情報から秘密情報を復元する秘密情報復元装置、秘密情報復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献１に示されるような（ｋ，ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｋ，ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｋ個の分散情報が集まれば、復元できることを意味する。
【０００３】
しかしながら、非特許文献１に示されている（ｋ，ｎ）閾値秘密分散法は、情報の分散、復元時に、（ｋ−１）次の多項式を処理する必要があり、その計算量が膨大になる。
【０００４】
これに対して、ＸＯＲを用いて、（ｋ，ｎ）閾値秘密分散法を構築することにより、高速に情報の分散および復元を可能とする方式が開示されている（例えば、非特許文献２および３参照。）。この非特許文献２および３で開示された方法は、その構造において等価なものであり、単純に高速動作を行うだけでなく、非特許文献１と同様に、完全な情報論理的安全性が保証されており、分散情報のデータ長が秘密情報のデータ長と等しいという特徴を有している。
【０００５】
また、非特許文献３に記載の方法はｋ個の分散情報から秘密情報を復元する際に、秘密情報のみならず分散情報を構成する乱数も復元可能であるという特徴があり、非特許文献２に記載の方法は、ｋが３以上の場合には、秘密情報は復元されるが、乱数に関しては、復元不可能という特徴がある。
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎ．ＡＣＭ，  ｖｏｌ．２２  ｎｏ．１１  ｐｐ．６１２−６１３，  １９７９．
【非特許文献２】Ｊ．Ｋｕｒｉｈａｒａ、Ｓ．Ｋｉｙｏｍｏｔｏ、Ｋ．Ｆｕｋｕｓｈｉｍａ、Ｔ．Ｔａｎａｋａ、“Ａ  Ｆａｓｔ  （４、ｎ）−Ｔｈｒｅｓｈｏｌｄ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ  Ｕｓｉｎｇ  Ｅｘｃｌｕｓｉｖｅ−ＯＲ  Ｏｐｅｒａｔｉｏｎ  ａｎｄ  ｉｔｓ  Ｅｘｔｅｎｓｉｏｎ  ｔｏ  （ｋ、ｎ）−Ｔｈｒｅｓｈｏｌｄ  Ｓｃｈｅｍｅｓ”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−４
【非特許文献３】藤井吉弘、栃窪孝也、保坂範和、多田美奈子、加藤岳久、“排他的論理和を用いた（ｋ、ｎ）しきい値法の構成法”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−５
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、あらゆる秘密分散法を実装する際には、乱数生成器の使用が必須である。理想的な乱数である真正乱数の生成器は、例えば、物理現象を利用するインターフェースが必要であるなど、コスト的・回路規模的に巨大なものとなる。このため、計算機上で秘密分散法を実装する場合、「擬似」乱数生成器（Ｐｓｅｕｄｏ
Ｒａｎｄｏｍ Ｎｕｍｂｅｒ Ｇｅｎｅｒａｔｏｒ；ＰＲＮＧ）と呼ばれる、計算アルゴリズムによる乱数生成器を使用するのが一般的である。
【０００７】
一般に、秘密分散法の安全性は、実装された乱数生成器に依存する。そのため、ＰＲＮＧによる秘密分散法では、ＰＲＮＧそのものの危殆化が、安全性において最も大きな問題と言える。
【０００８】
一方で、あらゆるＰＲＮＧは攻撃の対象とされている。例えば、ＰＲＮＧの出力した乱数から、乱数生成種（ＳＥＥＤ）を逆算するなどの攻撃が知られている。従来の攻撃手法では、ＳＥＥＤの逆算などに多大な計算量と時間がかかるために、「現状、安全である」と判断されているＰＲＮＧでも、計算機能力の向上に伴って危殆化するといった問題がある。また、新たに、画期的な攻撃手法が発明されば、すぐさま安全性が保証されなくなるという問題もある。
【０００９】
そこで、本発明は、上述の課題に鑑みてなされたものであり、乱数の情報そのものを攻撃者に与えないことにより、ＰＲＮＧによる秘密分散法の安全性を維持する分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【００１１】
（１）本発明は、排他的論理和演算を用いた（ｋ、ｎ）閾値分散法による分散情報生成装置であって、素数と巡回群との性質を用いて、２つの乱数を重複しないように排他的論理和演算を行う第１の排他的論理和演算器（例えば、図２のＸＯＲ演算器２２ａから２２ｎに相当）と、秘密情報を入力し、これを分割して部分秘密情報を生成する分割器（例えば、図１の分割器１１に相当）と、オールゼロからなるダミー情報を生成するダミー情報生成器（例えば、図１のダミー情報生成器１２に相当）と、素数と巡回群との性質を用いて、該ダミー情報及び前記部分秘密情報のうち、２つの情報を重複しないように排他的論理和演算を行う第２の排他的論理和演算器（例えば、図２のＸＯＲ演算器２１に相当）と、該第１の排他的論理和演算器において演算された情報と該第２の排他的論理和演算器で演算された情報との排他的論理和演算を行い、部分分散情報を出力する第３の排他的論理和演算器（例えば、図２のＸＯＲ演算器２３に相当）と、該出力された部分分散情報を連結し、分散情報を出力する連結器（例えば、図１の連結器１６に相当）と、該出力された分散情報を管理者に送信する送信手段（例えば、図１の送信装置１７に相当）と、を備えたことを特徴とする分散情報生成装置を提案している。
【００１２】
この発明によれば、第１の排他的論理和演算器は、素数と巡回群との性質を用いて、２つの乱数を重複しないように排他的論理和演算を行う。分割器は、秘密情報を入力し、これを分割して部分秘密情報を生成する。ダミー情報生成器は、オールゼロからなるダミー情報を生成し、第２の排他的論理和演算器は、素数と巡回群との性質を用いて、ダミー情報及び部分秘密情報のうち、２つの情報を重複しないように排他的論理和演算を行う。第３の排他的論理和演算器は、第１の排他的論理和演算器において演算された情報と第２の排他的論理和演算器で演算された情報との排他的論理和演算を行い、部分分散情報を出力する。そして、連結器が、出力された部分分散情報を連結し、分散情報を出力するとともに、送信手段が、出力された分散情報を管理者に送信する。したがって、秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、高速に分散情報を生成する処理が可能となる。
【００１３】
（２）本発明は、（１）の分散情報生成装置について、前記分割器に入力される秘密情報のビット長と前記連結器から出力される分散情報のビット長とが等しいことを特徴とする分散情報生成装置を提案している。
【００１４】
この発明によれば、分割器に入力される秘密情報のビット長と連結器から出力される分散情報のビット長とが等しい。したがって、情報理論的安全性を十分に保障する分散情報生成装置を構築することができる。
【００１５】
（３）本発明は、（１）または（２）に記載された分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、分散情報を受信する受信手段（例えば、図４の受信機３１に相当）と、該受信した分散情報を分割して部分分散情報を生成する分散情報分割手段（例えば、図４の分散情報分割部３２に相当）と、該分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する行列生成手段（例えば、図４の行列生成部３３に相当）と、該行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元する部分秘密情報復元部（例えば、図４の秘密情報復元部３４に相当）と、該復元された部分秘密情報を連結して秘密情報を出力する連結器（例えば、図４の連結部３５に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１６】
この発明によれば、受信手段は、分散情報を受信する。分散情報分割手段は、受信した分散情報を分割して部分分散情報を生成する。行列生成手段は、分散情報のインデックス番号を用いて、すべての部分秘密情報を復元するための部分分散情報の組み合わせ情報を生成する。そして、部分秘密情報復元部が、行列生成手段において生成された部分分散情報の組み合わせ情報に基づいて、入力した部分分散情報を組み合わせて排他的論理和演算を行って、部分秘密情報を復元し、連結器が、復元された部分秘密情報を連結して秘密情報を出力する。したがって、秘密情報復元装置における秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、秘密情報の復元処理を高速に行うことが可能となる。
【００１７】
（４）本発明は、分割器、ダミー情報生成器、乱数発生器、部分分散情報生成器、及び連結送信手段を備え、排他的論理和演算を用いた（ｋ、ｎ）閾値分散法による分散情報生成装置における分散情報生成方法であって、前記分割器が、秘密情報Ｋをｎｐ−１個の部分秘密情報に分割する第１のステップ（例えば、図３のステップＳ１０１に相当）と、前記ダミー情報生成器が、ダミー秘密情報Ｋ0∈{0}ｄを生成する第２のステップ（例えば、図３のステップＳ１０２に相当）と、前記乱数発生器が、Ｎｐ個ずつの乱数Ｒ１ｌ、・・・、Ｒｋ-１ｌ（0≦ｌ≦ｎｐ-１）の計（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップ（例えば、図３のステップＳ１０３に相当）と、前記部分分散情報生成器が、部分分散情報を数１を用いて生成する第４のステップ（例えば、図３のステップＳ１０４に相当）と、前記連結送信手段が、Ｓ（ｉ，0）、・・・、Ｓ（ｉ，ｎｐ-２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉに配布する第５のステップ（例えば、図３のステップＳ１０５に相当）と、を有することを特徴とする分散情報生成方法を提案している。
【００１８】
この発明によれば、秘密情報Ｋをｎｐ−１個の部分秘密情報に分割し、ダミー秘密情報Ｋ0∈{0}ｄを生成する。次に、Ｎｐ個ずつの乱数Ｒ１ｌ、・・・、Ｒｋ-１ｌ（0≦ｌ≦ｎｐ-１）の計（ｋ-１）ｎｐ個の乱数をすべて独立に生成し、部分分散情報を数１を用いて生成する。そして、Ｓ（ｉ，0）、・・・、Ｓ（ｉ，ｎｐ-２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉに配布する。したがって、秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、高速に分散情報を生成する処理が可能となる。
【００１９】
（５）本発明は、分散情報分割手段、第１の行列生成手段、第２の行列生成手段、部分秘密情報復元手段、及び連結器を備え、（４）に記載された分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元装置における秘密情報復元方法であって、前記分散情報分割手段が、それぞれの分散情報を部分分散情報に分割し、数２のようなｋ（ｎｐ-１）個の部分分散情報を得る第１のステップ（例えば、図５のステップＳ２０１に相当）と、前記第１の行列生成手段が、前記部分分散情報の構成により、数３を満たすｋ（ｎｐ-１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップ（例えば、図５のステップＳ２０２に相当）と、前記第２の行列生成手段が、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ  Ｉ]を変形し、行列[Ｍ´  Ｉ´]を得る第３のステップ（例えば、図５のステップＳ２０３に相当）と、前記部分秘密情報復元手段が、該生成したI´の第（ｋ-１）（ｎｐ-１）＋１行目からｋ（ｎｐ-１）行目を用いて、全部の部分秘密情報を復元する第４のステップ（例えば、図５のステップＳ２０４に相当）と、前記連結器が、すべての部分秘密情報を連結し、元の秘密情報Ｋを復元する第５のステップ（例えば、図５のステップＳ２０５に相当）と、を有することを特徴とする秘密情報復元方法を提案している。
【００２０】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、数２のようなｋ（ｎｐ-１）個の部分分散情報を得る。次に、部分分散情報の構成により、数３を満たすｋ（ｎｐ-１）×ｋｎｐ−１バイナリ行列Ｍを生成し、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ  Ｉ]を変形し、行列[Ｍ´  Ｉ´]を得る。そして、生成したI´の第（ｋ-1）（ｎｐ-１）＋１行目からｋ（ｎｐ-1）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報Kを復元する。したがって、秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、秘密情報の復元処理を高速に行うことが可能となる。
【００２１】
（６）本発明は、分割器、ダミー情報生成器、乱数発生器、部分分散情報生成器、及び連結送信手段を備え、排他的論理和演算を用いた（ｋ、ｎ）閾値分散法による分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、前記分割器が、秘密情報Ｋをｎｐ−１個の部分秘密情報に分割する第１のステップ（例えば、図３のステップＳ１０１に相当）と、前記ダミー情報生成器が、ダミー秘密情報Ｋ0∈{0}ｄを生成する第２のステップ（例えば、図３のステップＳ１０２に相当）と、前記乱数発生器が、Ｎｐ個ずつの乱数Ｒ１ｌ、・・・、Ｒｋ-１ｌ（0≦ｌ≦ｎｐ-１）の計（ｋ-１）ｎｐ個の乱数をすべて独立に生成する第３のステップ（例えば、図３のステップＳ１０３に相当）と、前記部分分散情報生成器が、部分分散情報を数４を用いて生成する第４のステップ（例えば、図３のステップＳ１０４に相当）と、前記連結送信手段が、Ｓ（ｉ，0）、・・・、Ｓ（ｉ，ｎｐ-２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉに配布する第５のステップ（例えば、図３のステップＳ１０５に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２２】
この発明によれば、秘密情報Ｋをｎｐ−１個の部分秘密情報に分割し、ダミー秘密情報Ｋ0∈{0}ｄを生成する。次に、Ｎｐ個ずつの乱数Ｒ１ｌ、・・・、Ｒｋ-１ｌ（0≦ｌ≦ｎｐ-１）の計（ｋ-１）ｎｐ個の乱数をすべて独立に生成し、部分分散情報を数４を用いて生成する。そして、Ｓ（ｉ，0）、・・・、Ｓ（ｉ，ｎｐ-２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉに配布する。したがって、秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、高速に分散情報を生成する処理が可能となる。
【００２３】
（７）本発明は、分散情報分割手段、第１の行列生成手段、第２の行列生成手段、部分秘密情報復元手段、及び連結器を備え、（６）に記載されたプログラムにより生成された分散情報から秘密情報を復元する秘密情報復元装置における秘密情報復元方法をコンピュータに実行させるためのプログラムであって、前記分散情報分割手段が、それぞれの分散情報を部分分散情報に分割し、数５のようなｋ（ｎｐ-１）個の部分分散情報を得る第１のステップ（例えば、図５のステップＳ２０１に相当）と、前記第１の行列生成手段が、前記部分分散情報の構成により、数６を満たすｋ（ｎｐ-１）×ｋｎｐ−１バイナリ行列Ｍを生成する第２のステップ（例えば、図５のステップＳ２０２に相当）と、前記第２の行列生成手段が、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ  Ｉ]を変形し、行列[Ｍ´  Ｉ´]を得る第３のステップ（例えば、図５のステップＳ２０３に相当）と、前記部分秘密情報復元手段が、該生成したI´の第（ｋ-１）（ｎｐ-１）＋１行目からｋ（ｎｐ-１）行目を用いて、全部の部分秘密情報を復元する第４のステップ（例えば、図５のステップＳ２０４に相当）と、前記連結器が、すべての部分秘密情報を連結し、元の秘密情報Ｋを復元する第５のステップ（例えば、図５のステップＳ２０５に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００２４】
この発明によれば、それぞれの分散情報を部分分散情報に分割し、数５のようなｋ（ｎｐ-１）個の部分分散情報を得る。次に、部分分散情報の構成により、数６を満たすｋ（ｎｐ-１）×ｋｎｐ−１バイナリ行列Ｍを生成し、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ  Ｉ]を変形し、行列[Ｍ´  Ｉ´]を得る。そして、生成したI´の第（ｋ-１）（ｎｐ-１）＋１行目からｋ（ｎｐ-１）行目を用いて、全部の部分秘密情報を復元し、すべての部分秘密情報を連結し、元の秘密情報Ｋを復元する。したがって、秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、秘密情報の復元処理を高速に行うことが可能となる。
【発明の効果】
【００２５】
本発明によれば、分散情報の生成および秘密情報の復元において、排他的論理和演算を用いていることから、従来の非特許文献１のような多項式補間を用いた閾値秘密分散法に比べて、高速に分散情報の生成および秘密情報の復元を行うことができるという効果がある。
【００２６】
また、閾値ｋの値に関わらず、秘密情報の復元時に乱数を一意に求めることが不可能であることから、乱数に関する情報が一切漏洩しない。このため、例えば、ある秘密情報を復元する権限を持つ者が悪意を持った攻撃者であったとしても、その攻撃者は秘密情報を復元することは出来ても乱数情報を一切手に入れることが出来ない。これにより、乱数生成器にＰＲＮＧを用いた場合でも、乱数情報を利用した閾値秘密分散法のＰＲＮＧへの攻撃を困難にするという効果がある。
【発明を実施するための最良の形態】
【００２７】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２８】
＜分散情報生成装置の構成＞
図１および図２を用いて、本実施形態に係る分散情報生成装置の構成について説明する。
本実施形態に係る分散情報生成装置は、図１に示すように、分割器１１と、ダミー情報生成器１２と、部分分散情報生成器１３と、ｋ−１個からなる乱数生成器１４と、連結器１６と、送信装置１７とから構成されている。
【００２９】
分割器１１は、秘密情報Ｋを入力し、これを（ｎｐ−１）個の部分秘密情報Ｋｑに分割する。ダミー情報生成器１２は、オールゼロからなるダミー部分秘密情報Ｋ０を生成する。生成されたダミー部分秘密情報Ｋ０及び部分秘密情報Ｋｑは、部分分散情報生成器１３に送られる。
【００３０】
乱数発生器１４は、互いに独立な乱数Ｒを発生している。そして、同様な乱数発生器１４をｋ−１個備えている。乱数発生器１４からの乱数Ｒは、部分分散情報生成器１３に送られる。
【００３１】
部分分散情報生成器１３は、ダミー部分秘密情報Ｋ０及び（ｎｐ−１）個の部分秘密情報Ｋｑと、乱数発生器１４からの乱数Ｒとを用いて、排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する。なお、部分分散情報生成器１３の詳細な構成については、後述する。連結器１６は、部分分散情報生成器１３から出力される部分分散情報をグループごとにバイナリ連結し、ｎ個の分散情報Ｓｉを生成する。送信装置１７は、生成されたｎ個の分散情報Ｓｉを、管理者Ｐｉにセキュアに送信する。
【００３２】
なお、秘密情報を（ｎｐ−１）個に等分割する必要がある。但し、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３３】
＜部分分散情報生成器の構成＞
本実施形態に係る部分分散情報生成器の構成について説明する。
本実施形態に係る部分分散情報生成器は、図２に示すように、ＸＯＲ演算器２１と、ＸＯＲ演算器２２ａから２２ｎと、ＸＯＲ演算器２３とから構成されている。
【００３４】
ＸＯＲ演算器２１は、素数と巡回群の性質を用いて、互いに重複しない部分秘密情報のペアについてＸＯＲ演算を実行する。ＸＯＲ演算器２２ａから２２ｎは、素数と巡回群の性質を用いて、互いに重複しない乱数のペアについてＸＯＲ演算を実行する。ＸＯＲ演算器２３は、ＸＯＲ演算器２１およびＸＯＲ演算器２２ａから２２ｎにおいて、ＸＯＲ演算されたものについて、さらに、素数と巡回群の性質を用いて、組み合わせを決定し、ＸＯＲ演算を実行して、部分分散情報を生成する。こうした、一連の処理により、複数の部分分散情報が生成される。
【００３５】
＜分散情報生成装置および秘密情報復元装置の処理＞
次に、分散情報生成装置の処理について、更に、詳述する。ここでは、分散情報生成装置の処理および秘密情報復元装置の処理について説明する前に、本明細書中で使用する演算子及び記号について、以下のように、定義する。
【００３６】
【数１】
0005191751.tif 000002
【００３７】
＜分散情報生成装置の処理＞
先ず、分散情報生成装置の処理について図３を用いて説明する。分散情報生成装置では、以下の手順に従って分散処理を行って、（ｋ，ｎ）閾値秘密分散法が実現される。
【００３８】
なお、前述したように、秘密情報Ｋは、（ｎｐ−１）個に等分割する必要があり、ｎｐは分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合には、ｎｐ＞ｎを満たす素数ｎｐを用いた（ｋ、ｎｐ）閾値秘密分散法の分散情報を、ｎ個用いることで、（ｋ，ｎ）閾値法を実現する。
【００３９】
（ステップ１）
秘密情報Ｋを（ｎｐ−１）個の部分秘密情報Ｋｑに分割する（ステップＳ１０１）。
【００４０】
【数２】
0005191751.tif 000003
【００４１】
（ステップ２）
ダミーの部分秘密情報Ｋ０∈{０}ｄを生成する（ステップＳ１０２）。
【００４２】
（ステップ３）
ｎｐ個ずつの乱数Ｒｌ０、・・・、Ｒｌｋ−1（０≦ｌ≦ｎｐ−１）の計（ｋ−１）ｎｐ個の乱数を全て独立に生成する（ステップＳ１０３）。
【００４３】
（ステップ４）
ＸＯＲ演算により、以下のように部分分散情報Ｓ（ｉ，ｍ）を生成する（ステップＳ１０４）。
【００４４】
【数３】
0005191751.tif 000004
【００４５】
なお、数３内のペアのＸＯＲ演算である数４、ダミー秘密情報を含む部分秘密情報のＸＯＲ演算である数５は、事前に計算を行っていてもよい。このとき、個々の要素（乱数、部分秘密情報）のインデックスは、素数ｎｐを法としているため、巡回群（加法群）を形成しており、これを利用してペアを決定しているため、ペアは互いに重複することはない。
【００４６】
【数４】
0005191751.tif 000005
【００４７】
【数５】
0005191751.tif 000006
【００４８】
（ステップ５）
部分分散情報Ｓ（ｉ、０）、・・・、Ｓ（ｉ，ｎｐ−２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉへセキュアに配付する（ステップＳ１０５）。
【００４９】
【数６】
0005191751.tif 000007
【００５０】
ここで、１人の管理者に配布されるビット数は、Ｋのビット数と等しくなる。これにより、情報理論的安全性を十分に保障する分散情報生成装置を構築することができる。
【００５１】
以上、本実施形態に係る分散情報生成装置によれば、秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、高速に分散情報を生成する処理が可能となる。
【００５２】
＜秘密情報復元装置の構成＞
上記の分散情報の生成処理を踏まえて、本発明の秘密情報復元装置について説明する。本実施形態に係る秘密情報復元装置は、図４に示すように、受信機３１と、分散情報分割部３２と、行列生成部３３と、部分秘密情報復元部３４と、連結部３５とから構成されている。
【００５３】
受信機３１は、各管理者Ｐｉから例えば、ｋ個（ｋは正の整数）の分散情報を受信する。分散情報分割部３２は、受信機３１が受信したｋ個（ｋは正の整数）の分散情報を入力し、ｋ（ｎｐ−１）個（ｎｐは、正の素数）の部分分散情報を生成する。行列生成部３３は、例えば、ｋ個の分散情報に対応するインデックス番号ｔ０、ｔ１、・・・、ｔｋ−１（０≦ｔ０、ｔ１、・・・、ｔｋ−１≦ｋ−１）を入力し、部分秘密情報Ｋ１、・・・、Ｋｎｐ−１を復元するための部分分散情報の組み合わせを示す行列を生成する。部分秘密情報復元部３４は、行列生成部３３において生成された行列を部分分散情報に適用して、部分秘密情報を復元する。連結部３５は、復元した部分秘密情報を連結して元の秘密情報Ｋを生成する。
【００５４】
＜秘密情報復元装置の処理＞
次に、図５を用いて、本実施形態に係る秘密情報復元装置の処理について説明する。
まず、分散情報分割部３２にｋ個の分散情報が入力され、数７に示すようなｋ（ｎｐ−１）個の部分分散情報が生成されて、部分秘密情報復元部３４に出力される（ステップＳ２０１）。一方、行列生成部３３には、ｋ個の分散情報についてのインデックス番号が入力される。
【００５５】
【数７】
0005191751.tif 000008
【００５６】
そして、行列生成部３３では、部分分散情報の構成により、数８を満たすようなｋ（ｎｐ−１）×ｋｎｐ−１のバイナリ行列Ｍが生成される（ステップＳ２０２）。このとき、Ｋ0は、オールゼロであることにより、ＸＯＲ演算しても値が一切変化しないため、Ｋ0については、考慮しない。
【００５７】
【数８】
0005191751.tif 000009
【００５８】
次に、行列生成部３３は、ガウスの消去法あるいはガウスジョルダンの消去法等を用いて、行列[Ｍ  Ｉ]を変形し、行列[Ｍ´  Ｉ´]を得る（ステップＳ２０３）。このとき、Ｉは、（ｋ−１）（ｎｐ−１）×ｋ（ｎｐ−１）の単位行列である。
【００５９】
さらに、部分秘密情報復元部３４内のＸＯＲ演算部は、生成したI´の第（ｋ−１）（ｎｐ−１）＋１行目からｋ（ｎｐ−１）行目を用いて、数９に示す全部の部分秘密情報を復元する（ステップＳ２０４）。ここで、Ｉ´１、．．．．、Ｉ´ｎｐ-１は、それぞれＩ´の第（ｋ−１）（ｎｐ−１）＋１行目、．．．．、ｋ（ｎｐ-1）行目を表す。
【００６０】
【数９】
0005191751.tif 000010
【００６１】
そして、連結器３５において、すべての部分秘密情報を連結して、元の秘密情報Ｋを復元する（ステップＳ２０５）。
【００６２】
【数１０】
0005191751.tif 000011
【００６３】
したがって、本実施形態によれば、秘密情報復元装置における秘密情報の復元時において、一切の乱数を一意に復元することが不可能となる。また、排他的論理和演算を用いていることから、秘密情報の復元処理を高速に行うことが可能となる。
【００６４】
なお、分散情報生成装置および秘密情報復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを分散情報生成装置および秘密情報復元装置に読み込ませ、実行することによって本発明の分散情報生成装置および秘密情報復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００６５】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００６６】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００６７】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００６８】
【図１】ＸＯＲを用いた（ｋ、ｎ）閾値法における分散情報生成装置の構成を例示した図である。
【図２】本実施形態に係る部分分散情報生成器の構成図である。
【図３】本実施形態に係る分散情報生成装置の処理フローである。
【図４】本実施形態に係る秘密情報復元装置の構成図である。
【図５】本実施形態に係る秘密情報復元処理のフローである。
【符号の説明】
【００６９】
１１・・・分割器
１２・・・ダミー情報生成器
１３・・・部分分散情報生成器
１４・・・乱数発生器
１６・・・連結器
１７・・・送信装置
２１、２２ａ〜２２ｎ、２３・・・ＸＯＲ演算器
３１・・・受信機
３２・・・分散情報分割部
３３・・・行列生成部
３４・・・部分秘密情報復元部
３５・・・連結部
【図１】
0005191751.tif 000018
【図２】
0005191751.tif 000019
【図３】
0005191751.tif 000020
【図４】
0005191751.tif 000021
【図５】
0005191751.tif 000022