(57)【特許請求の範囲】
【請求項１】
秘密情報を分割して部分秘密情報を生成する秘密情報分割器と、該秘密情報分割器が生成した所定数の部分秘密情報と所定数の乱数とを入力し、該所定数の部分秘密情報と所定数の乱数との排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成器と、該生成された部分分散情報を結合して分散情報を生成する結合器とを備えた分散情報生成装置であって、
前記秘密情報分割器が、前記秘密情報を前記部分分散情報生成器に入力する所定値ｎｐ―１個（ｎｐは分散数ｎ以上の素数）よりもＬ個多い部分秘密情報に分割し、
該余剰のＬ個の秘密情報を前記所定数の乱数の一部として前記部分分散情報生成器に入力することを特徴とする分散情報生成装置。
【請求項２】
前記Ｌは、前記乱数の所定数よりも小さい正の整数からなる変数であることを特徴とする請求項１に記載の分散情報生成装置。
【請求項３】
前記請求項１または２に記載の分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、
閾値ｋ個（ｋは分散数ｎ以下の正の整数）の分散情報を入力し、該入力した分散情報を分割して部分分散情報を生成する分散情報分割器と、
該部分分散情報を入力してｎｐ―１（ｎｐは分散数ｎ以上の素数）個の部分秘密情報を復元する第１の復元器と、
該部分分散情報を入力してＬ個の部分秘密情報を復元する第２の復元器と、
前記第１の復元器および第２の復元器により復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する連結器と、
を備えたことを特徴とする秘密情報復元装置。
【請求項４】
秘密情報を分割して部分秘密情報を生成する秘密情報分割器と、該秘密情報分割器が生成した所定数の部分秘密情報と所定数の乱数を入力し、該所定数の部分秘密情報と所定数の乱数との排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成器と、該生成された部分分散情報を結合して分散情報を生成する結合器とを備えた分散情報生成装置における分散情報生成方法であって、
秘密情報を部分分散情報生成器に入力する所定値ｎｐ―１個（ｎｐは分散数ｎ以上の素数）よりもＬ個多い部分秘密情報に分割する第１のステップと、
余剰のＬ個の秘密情報を前記所定数の乱数の一部として部分分散情報生成器に入力する第２のステップと、
前記ｎｐ―１個の部分秘密情報と前記Ｌ個の部分秘密情報および乱数とのＸＯＲ演算により、部分分散情報を生成する第３のステップと、
生成した部分分散情報を連結して、分散情報を生成する第４のステップと、
を備えることを特徴とする分散情報生成方法。
【請求項５】
前記請求項４の分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、
閾値ｋ個（ｋは分散数ｎ以下の正の整数）の分散情報を入力し、該入力した分散情報を分割して部分分散情報を生成する第１のステップと、
該部分分散情報を入力してｎｐ―１個（ｎｐは分散数ｎ以上の素数）の部分秘密情報を復元する第２のステップと、
該部分分散情報を入力してＬ個の部分秘密情報を復元する第３のステップと、
前記第２のステップおよび第３のステップにおいて復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する第４のステップと、
を備えたことを特徴とする秘密情報復元方法。
【請求項６】
秘密情報を分割して部分秘密情報を生成する秘密情報分割器と、該秘密情報分割器が生成した所定数の部分秘密情報と所定数の乱数を入力し、該所定数の部分秘密情報と所定数の乱数との排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成器と、該生成された部分分散情報を結合して分散情報を生成する結合器とを備えた分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、
秘密情報を部分分散情報生成器に入力する所定値ｎｐ―１個（ｎｐは分散数ｎ以上の素数）よりもＬ個多い部分秘密情報に分割する第１のステップと、
余剰のＬ個の秘密情報を前記所定数の乱数の一部として部分分散情報生成器に入力する第２のステップと、
前記ｎｐ―１個の部分秘密情報と前記Ｌ個の部分秘密情報および乱数とのＸＯＲ演算により、部分分散情報を生成する第３のステップと、
生成した部分分散情報を連結して、分散情報を生成する第４のステップと、
をコンピュータに実行させるためのプログラム。
【請求項７】
前記請求項４の分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、
閾値ｋ個（ｋは分散数ｎ以下の正の整数）の分散情報を入力し、該入力した分散情報を分割して部分分散情報を生成する第１のステップと、
該部分分散情報を入力してｎｐ―１個（ｎｐは分散数ｎ以上の素数）の部分秘密情報を復元する第２のステップと、
該部分分散情報を入力してＬ個の部分秘密情報を復元する第３のステップと、
前記代２のステップおよび第３のステップにおいて復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する第４のステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散情報のデータサイズに自由度を有する分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラムに関する。
【背景技術】
【０００２】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献１に示されるような（ｋ，ｎ）閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、（ｋ，ｎ）閾値秘密分散は、機密情報をｎ個の分散情報に分散し、そのうち任意のｋ個の分散情報が集まれば、復元できることを意味する。
【０００３】
非特許文献１に記載の技術は、情報の分散・復元時にｋ−１次の多項式を処理する必要があり、その計算量の大きさが実際のアプリケーションに適用する際の問題となる点があったが、これに対して、排他的論理和（Ｅｘｃｌｕｓｉｖｅ−ＯＲ、ＸＯＲ）を用いて（ｋ、ｎ）閾値秘密分散法を構成することで、高速に情報の分散・復元を可能とする方式も提案されている（非特許文献２および３参照）。これらの高速（ｋ、ｎ）閾値秘密分散法は、単純に高速動作するだけではなく、非特許文献１に記載の技術と同様に、完全な情報理論的安全性が保証され、分散情報のデータ長が秘密情報のデータ長と等しいという特長を持っている。
【０００４】
また、非特許文献１に記載された技術の拡張方式として、非特許文献４に示されるような安全性をわずかに劣化させる代わりに分散情報のサイズを大幅に削減できるランプ型閾値秘密分散法とよばれる手法も知られている。
【非特許文献１】Ａ．Ｓｈａｍｉｒ，“Ｈｏｗ  ｔｏ  Ｓｈａｒｅ  ａ  Ｓｅｃｒｅｔ，”Ｃｏｍｍｕｎ．ＡＣＭ，  ｖｏｌ．２２  ｎｏ．１１  ｐｐ．６１２−６１３，  １９７９．
【非特許文献２】Ｊ．Ｋｕｒｉｈａｒａ、Ｓ．Ｋｉｙｏｍｏｔｏ、Ｋ．Ｆｕｋｕｓｈｉｍａ、Ｔ．Ｔａｎａｋａ、“Ａ  Ｆａｓｔ  （４、ｎ）−Ｔｈｒｅｓｈｏｌｄ  Ｓｅｃｒｅｔ  Ｓｈａｒｉｎｇ  Ｓｃｈｅｍｅ  Ｕｓｉｎｇ  Ｅｘｃｌｕｓｉｖｅ−ＯＲ  Ｏｐｅｒａｔｉｏｎ  ａｎｄ  ｉｔｓ  Ｅｘｔｅｎｓｉｏｎ  ｔｏ  （ｋ、ｎ）−Ｔｈｒｅｓｈｏｌｄ  Ｓｃｈｅｍｅｓ”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−４
【非特許文献３】藤井吉弘、栃窪孝也、保坂範和、多田美奈子、加藤岳久、“排他的論理和を用いた（ｋ、ｎ）しきい値法の構成法”、電子情報通信学会技術研究報告、ｖｏｌ．１０７、Ｎｏ．４４、情報セキュリティ、ＩＳＳＮ０９１３−５６８５、ＩＳＥＣ２００７−５
【非特許文献４】山本博資、“（ｋ，Ｌ，ｎ）閾値秘密分散システム”、電子通信学会論文誌、ｖｏｌ．Ｊ６８−Ａ、ｎｏ．９、ｐｐ．９４５−９５２、１９８５年９月
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述の非特許文献２および３に開示された技術においては、安全かつ高速に分散情報の配布を実現できるものの、分散情報のデータサイズに自由度がないために、ストレージやメモリの容量に負荷を与えたり、通信トラフィックに影響を及ぼすといった問題がある。また、上述の非特許文献４に開示された技術では、非特許文献１に開示された技術をその基礎としているために、分散情報のデータサイズには、比較的自由度があるものの、分散情報の生成や配布に関して、膨大な計算量が必要となるために、動作が低速であるといった問題があった。
【０００６】
そこで、本発明は、上述の課題に鑑みてなされたものであり、安全かつ高速な処理が可能であるとともに、分散情報のサイズに自由度を持たせて、そのサイズを削減することができる分散情報生成装置、秘密情報復元装置、分散情報生成方法、秘密情報復元方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記の課題を解決するために以下の事項を提案している。
（１）本発明は、秘密情報を分割して部分秘密情報を生成する秘密情報分割器（例えば、図１の秘密情報分割器１１に相当）と、該秘密情報分割器が生成した所定数の部分秘密情報と所定数の乱数とを入力し、該所定数の部分秘密情報と所定数の乱数との排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成器（例えば、図１の部分分散情報生成器１３に相当）と、該生成された部分分散情報を結合して分散情報を生成する結合器（例えば、図１の連結器１４に相当）とを備えた分散情報生成装置であって、前記秘密情報分割器が、前記秘密情報を前記部分分散情報生成器に入力する所定値ｎｐ―１個（ｎｐは分散数ｎ以上の素数）よりもＬ個多い部分秘密情報に分割し、該余剰のＬ個の秘密情報を前記所定数の乱数の一部として前記部分分散情報生成器に入力することを特徴とする分散情報生成装置を提案している。
【０００８】
この発明によれば、秘密情報を分割して部分秘密情報を生成する秘密情報分割器と、秘密情報分割器が生成した所定数の部分秘密情報と所定数の乱数を入力し、該所定数の部分秘密情報と所定数の乱数との排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成器と、生成された部分分散情報を結合して分散情報を生成する結合器とを備えた分散情報生成装置において、秘密情報分割器が、秘密情報を部分分散情報生成器に入力する所定値ｎｐ―１個よりもＬ個多い部分秘密情報に分割し、該余剰のＬ個の秘密情報を所定数の乱数の一部として部分分散情報生成器に入力する。したがって、部分分散情報生成器に入力する所定値をｎｐ−１とすれば、生成される分散情報のサイズは、元の秘密情報のサイズの（ｎｐ−１）／（ｎｐ−１＋Ｌ）倍となり、分散情報のサイズを削減することができる。
【０００９】
（２）本発明は、（１）の分散情報生成装置について、前記Ｌは、前記乱数の所定数よりも小さい正の整数からなる変数であることを特徴とする分散情報生成装置を提案している。
【００１０】
この発明によれば、Ｌは、乱数の所定数よりも小さい正の整数からなる変数である。したがって、上記関係式（ｎｐ−１）／（ｎｐ−１＋Ｌ）より、Ｌの値をコントロールすることにより、分散情報のサイズに自由度を持たせ、そのサイズを細かく設定することができる。
【００１１】
（３）本発明は、前記請求項１または２に記載の分散情報生成装置により生成された分散情報から秘密情報を復元する秘密情報復元装置であって、閾値ｋ個（ｋは分散数ｎ以下の正の整数）の分散情報を入力し、該入力した分散情報を分割して部分分散情報を生成する分散情報分割器（例えば、図３の分散情報分割器２１に相当）と、該部分分散情報を入力してｎｐ―１個（ｎｐは分散数ｎ以上の素数）の部分秘密情報を復元する第１の復元器（例えば、図３の第１の部分秘密情報復元器２２に相当）と、該部分分散情報を入力してＬ個の部分秘密情報を復元する第２の復元器（例えば、図３の第２の部分秘密情報復元器２３に相当）と、前記第１の復元器および第２の復元器により復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する連結器（例えば、図３の連結器２４に相当）と、を備えたことを特徴とする秘密情報復元装置を提案している。
【００１２】
この発明によれば、分散情報分割器が、分散情報を入力し、入力した分散情報を分割して部分分散情報を生成し、第１の復元器が、部分分散情報を入力してｎｐ―１個の部分秘密情報を復元し、第２の復元器が、部分分散情報を入力してＬ個の部分秘密情報を復元する。そして、連結器が、第１の復元器および第２の復元器により復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する。したがって、分散情報のサイズを細かく設定しつつ、秘密情報を安全かつ高速に復元することができる。
【００１３】
（４）本発明は、秘密情報を分割して部分秘密情報を生成する秘密情報分割器と、該秘密情報分割器が生成した所定数の部分秘密情報と所定数の乱数を入力し、該所定数の部分秘密情報と所定数の乱数との排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成器と、該生成された部分分散情報を結合して分散情報を生成する結合器とを備えた分散情報生成装置における分散情報生成方法であって、秘密情報を部分分散情報生成器に入力する所定値ｎｐ―１個（ｎｐは分散数ｎ以上の素数）よりもＬ個多い部分秘密情報に分割する第１のステップ（例えば、図２のステップＳ１０１に相当）と、余剰のＬ個の秘密情報を前記所定数の乱数の一部として部分分散情報生成器に入力する第２のステップ（例えば、図２のステップＳ１０２に相当）と、前記ｎｐ―１個の部分秘密情報と前記Ｌ個の部分秘密情報および乱数とのＸＯＲ演算により、部分分散情報を生成する第３のステップ（例えば、図２のステップＳ１０３に相当）と、生成した部分分散情報を連結して、分散情報を生成する第４のステップ（例えば、図２のステップＳ１０４に相当）と、を備えることを特徴とする分散情報生成方法を提案している。
【００１４】
この発明によれば、秘密情報を部分分散情報生成器に入力する所定値ｎｐ―１個よりもＬ個多い部分秘密情報に分割し、余剰のＬ個の秘密情報を所定数の乱数の一部として部分分散情報生成器に入力する。そして、ｎｐ―１個の部分秘密情報とＬ個の部分秘密情報および乱数とのＸＯＲ演算により、部分分散情報を生成し、生成した部分分散情報を連結して、分散情報を生成する。したがって、部分分散情報生成器に入力する所定値をｎｐ−１とすれば、生成される分散情報のサイズは、元の秘密情報のサイズの（ｎｐ−１）／（ｎｐ−１＋Ｌ）倍となり、分散情報のサイズを削減することができる。
【００１５】
（５）本発明は、前記請求項４の分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法であって、閾値ｋ個（ｋは分散数ｎ以下の正の整数）の分散情報を入力し、該入力した分散情報を分割して部分分散情報を生成する第１のステップ（例えば、図４のステップＳ２０１に相当）と、該部分分散情報を入力してｎｐ―１個（ｎｐは分散数ｎ以上の素数）の部分秘密情報を復元する第２のステップ（例えば、図４のステップＳ２０２に相当）と、該部分分散情報を入力してＬ個の部分秘密情報を復元する第３のステップ（例えば、図４のステップＳ２０３に相当）と、前記第２のステップおよび第３のステップにおいて復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する第４のステップ（例えば、図４のステップＳ２０４に相当）と、を備えたことを特徴とする秘密情報復元方法を提案している。
【００１６】
この発明によれば、分散情報を入力し、入力した分散情報を分割して部分分散情報を生成し、部分分散情報を入力してｎｐ―１個の部分秘密情報を復元する。一方、部分分散情報を入力してＬ個の部分秘密情報を復元する。そして、復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する。したがって、分散情報のサイズを細かく設定しつつ、秘密情報を安全かつ高速に復元することができる。
【００１７】
（６）本発明は、秘密情報を分割して部分秘密情報を生成する秘密情報分割器と、該秘密情報分割器が生成した所定数の部分秘密情報と所定数の乱数を入力し、該所定数の部分秘密情報と所定数の乱数との排他的論理和（ＸＯＲ）演算により、部分分散情報を生成する部分分散情報生成器と、該生成された部分分散情報を結合して分散情報を生成する結合器とを備えた分散情報生成装置における分散情報生成方法をコンピュータに実行させるためのプログラムであって、秘密情報を部分分散情報生成器に入力する所定値ｎｐ―１個（ｎｐは分散数ｎ以上の素数）よりもＬ個多い部分秘密情報に分割する第１のステップ（例えば、図２のステップＳ１０１に相当）と、余剰のＬ個の秘密情報を前記所定数の乱数の一部として部分分散情報生成器に入力する第２のステップ（例えば、図２のステップＳ１０２に相当）と、前記ｎｐ―１個の部分秘密情報と前記Ｌ個の部分秘密情報および乱数とのＸＯＲ演算により、部分分散情報を生成する第３のステップ（例えば、図２のステップＳ１０３に相当）と、生成した部分分散情報を連結して、分散情報を生成する第４のステップ（例えば、図２のステップＳ１０４に相当）と、をコンピュータに実行させるためのプログラムを提案している。
【００１８】
この発明によれば、秘密情報を部分分散情報生成器に入力する所定値ｎｐ―１個よりもＬ個多い部分秘密情報に分割し、余剰のＬ個の秘密情報を所定数の乱数の一部として部分分散情報生成器に入力する。そして、ｎｐ―１個の部分秘密情報とＬ個の部分秘密情報および乱数とのＸＯＲ演算により、部分分散情報を生成し、生成した部分分散情報を連結して、分散情報を生成する。したがって、部分分散情報生成器に入力する所定値をｎｐ−１とすれば、生成される分散情報のサイズは、元の秘密情報のサイズの（ｎｐ−１）／（ｎｐ−１＋Ｌ）倍となり、分散情報のサイズを削減することができる。
【００１９】
（７）本発明は、前記請求項４の分散情報生成方法により生成された分散情報から秘密情報を復元する秘密情報復元方法をコンピュータに実行させるためのプログラムであって、閾値ｋ個（ｋは分散数ｎ以下の正の整数）の分散情報を入力し、該入力した分散情報を分割して部分分散情報を生成する第１のステップと、該部分分散情報を入力してｎｐ―１個（ｎｐは分散数ｎ以上の素数）の部分秘密情報を復元する第２のステップと、該部分分散情報を入力してＬ個の部分秘密情報を復元する第３のステップと、前記第２のステップおよび第３のステップにおいて復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する第４のステップと、をコンピュータに実行させるためのプログラムを提案している。
【００２０】
この発明によれば、分散情報を入力し、入力した分散情報を分割して部分分散情報を生成し、部分分散情報を入力してｎｐ―１個の部分秘密情報を復元する。一方、部分分散情報を入力してＬ個の部分秘密情報を復元する。そして、復元されたｎｐ―１＋Ｌ個の部分秘密情報を連結して秘密情報を生成する。したがって、分散情報のサイズを細かく設定しつつ、秘密情報を安全かつ高速に復元することができる。
【発明の効果】
【００２１】
本発明によれば、セキュアかつ破壊耐性を有した分散データ管理方式を用いることにより、高速かつ安全な動作で、ストレージ使用量・メモリ容量・データ通信量の削減を可能とすることができるという効果がある。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２３】
＜分散情報生成装置の構成＞
図１を用いて、本実施形態に係る分散情報生成装置の構成について説明する。
本実施形態に係る分散情報生成装置は、図１に示すように、秘密情報分割器１１と、乱数生成器１２ａ、・・・、１２ｎと、部分分散情報生成器１３と、連結器１４と、送信器１５とから構成され、部分分散情報生成器１３は、部分秘密情報入力部１３ａと、乱数入力部１３ｂとを備えている。
【００２４】
秘密情報分割器１１は、秘密情報を入力し、入力した秘密情報を所定数（ｎｐ−１）（ｎｐは分散数ｎ以上の素数）よりもＬ個多い、（ｎｐ−１＋Ｌ）個の部分秘密情報に分割し、分割した（ｎｐ−１）個の部分秘密情報を部分分散情報生成器１３の部分秘密情報入力部１３ａに、Ｌ個の部分秘密情報を部分分散情報生成器１３の乱数入力部１３ｂに入力する。なお、Ｌは、乱数の所定数よりも小さい正の整数からなる変数であり、Ｌをコントロールすることにより、分散情報のサイズに自由度を持たせ、そのサイズを細かく設定することができる。
【００２５】
乱数生成器１２ａ、・・・、１２ｎは、互いに独立な乱数を発生し、部分分散情報生成器１３の乱数入力部１３ｂに入力する。なお、乱数生成器１２ａ・・・、１２ｎが生成する乱数の数と秘密情報分割器１１から入力される部分秘密情報の数Ｌとをあわせた数は、従来のＸＯＲを用いた（ｋ，ｎ）閾値分散法（例えば、非特許文献３参照）における乱数の数に相当する。
【００２６】
部分分散情報生成器１３は、部分秘密情報入力部１３ａから入力したｎｐ−１個の部分秘密情報と乱数入力部１３ｂから入力した乱数あるいはＬ個の部分秘密情報との排他的論理和（ＸＯＲ）演算を実行し、部分分散情報を生成する。連結器１４は、部分分散情報生成器１３において生成された部分分散情報を連結して分散情報を生成し、送信器１５は、連結部１４において生成された分散情報を所定のｎ人（ｎは正の整数）管理者に送信する。
【００２７】
＜分散情報生成装置の処理＞
図２を用いて、本実施形態に係る分散情報生成装置の処理について説明する。
【００２８】
（ステップＳ１０１）
秘密情報Ｋを（ｎｐ−１＋Ｌ）個（ｎｐは分散数ｎ以上の素数）の部分秘密情報Ｋｑに分割する。なお、数１において、「｜｜」は、ビット列の結合を示す。
【００２９】
【数１】
0005065795.tif 000002
【００３０】
（ステップＳ１０２）
部分秘密情報Ｋｑのうち、（ｎｐ−１）個の部分秘密情報を部分分散情報生成器１３の部分秘密情報入力部１３ａに入力し、残りのＬ個の部分秘密情報を部分分散情報生成器１３の乱数入力部１３ｂに入力する。
【００３１】
（ステップＳ１０３）
部分分散情報生成器１３の部分秘密情報入力部１３ａに入力された（ｎｐ−１）個の部分秘密情報Ｋ１、・・・、Ｋｎｐ−１と、乱数入力部１２ａ、・・・、１２ｎに入力した乱数ＲｔｌおよびＬ個の部分秘密情報Ｋｎｐ、・・・、Ｋｎｐ＋Ｌ−１（適宜、乱数入力部に応じてＲｔｌへ表示は変化している）とのＸＯＲ演算により、以下のように部分分散情報Ｓ（ｉ，ｍ）を生成する。
【００３２】
【数２】
0005065795.tif 000003
【００３３】
（ステップＳ１０４）
部分分散情報Ｓ（ｉ、０）、・・・、Ｓ（ｉ，ｎｐ−２）を連結して分散情報Ｓｉを生成し、管理者Ｐｉへセキュアに配付する。
【００３４】
【数３】
0005065795.tif 000004
【００３５】
したがって、本実施形態に係る分散情報生成装置によれば、生成される分散情報のサイズは、元の秘密情報のサイズの（ｎｐ−１）／（ｎｐ−１＋Ｌ）倍となり、分散情報のサイズを削減することができる。また、Ｌが、変数であることから、上記関係式（ｎｐ−１）／（ｎｐ−１＋Ｌ）より、Ｌの値をコントロールすることによって、分散情報のサイズに自由度を持たせ、そのサイズを細かく設定することができる。
【００３６】
なお、ここで、秘密情報は（ｎｐ−１＋Ｌ）個に等分割する必要がある。但し、ｎｐは、分散数ｎについてｎｐ≧ｎを満たす素数である。そのため、希望する分散数ｎが合成数である場合にはｎｐ＞ｎを満たす素数ｎｐを用いて、前述の処理によって生成できるｎｐ個の分散情報のうちのｎ個を用いることで、分散情報のサイズを削減した（ｋ，ｎ）閾値法（ランプ型（ｋ，ｎ）閾値法）を実現する。
【００３７】
＜秘密情報復元装置の構成＞
図３を用いて、本実施形態に係る秘密情報復元装置の構成について説明する。
本実施形態に係る秘密情報復元装置は、図３に示すように、分散情報分割器２１と、第１の部分秘密情報復元器２２と、第２の部分秘密情報復元器２３と、連結器２４とから構成されている。
【００３８】
分散情報分割器２１は、ｋ個（ｋは分散数ｎ以下の正の整数）の分散情報を入力し、これを部分分散情報に分割して、第１の部分秘密情報復元器２２および第２の部分秘密情報復元器２３に入力する。第１の部分秘密情報復元器２２は、入力した部分分散情報に排他的論理和（ＸＯＲ）演算を実行し、乱数を消去して、（ｎｐ−１）個（ｎｐは分散数ｎ以上の素数）の部分秘密情報を連結器２４に対して出力する。また、第２の部分秘密情報復元器２３は、入力した部分秘密情報を組み合わせ、正規の（ｎｐ−１）個の部分秘密情報と正規の乱数とに対して排他的論理和（ＸＯＲ）演算を実行して、これらを消去し、Ｌ個の部分秘密情報を連結器２４に対して出力する。連結器２４は、入力した（ｎｐ−１）個の部分秘密情報、Ｌ個の部分秘密情報の計（ｎｐ−１＋Ｌ）個の部分秘密情報を連結して、秘密情報を復元する。
【００３９】
＜秘密情報復元装置の処理＞
図４を用いて、本実施形態に係る分散情報生成装置の処理について説明する。
【００４０】
（ステップＳ２０１）
それぞれの分散情報Ｓｉ０、・・・、Ｓｉｋ−１を部分分散情報に分割する。（ｋは分散数ｎ以下の正の整数、ｎｐは分散数ｎ以上の素数）
【００４１】
【数４】
0005065795.tif 000005
【００４２】
（ステップＳ２０２、Ｓ２０３）
第１の部分秘密情報復元器２２において、（ｎｐ−１）個の部分秘密情報Ｋ１、Ｋ２、・・・、Ｋｎｐ−１を復元し、第２の部分秘密情報復元器２３においてＬ個の部分秘密情報Ｋｎｐ、・・・、Ｋｎｐ−１+Ｌを復元する。
【００４３】
（ステップＳ２０４）
全ての部分秘密情報を連結し、元の秘密情報Ｋを復元する。
【００４４】
【数５】
0005065795.tif 000006
【００４５】
したがって、本実施形態に係る秘密情報復元装置によれば、分散情報のサイズを細かく設定しつつ、秘密情報を安全かつ高速に復元することができる。また、分散情報のサイズに自由度を持たせることができることから、ストレージやメモリの容量を削減し、通信インフラを有効に使用することができる。
【００４６】
＜実施例＞
以下、一例として、（３，５）閾値法を基本とし、Ｌ＝２として構成した分散情報のサイズを削減したＸＯＲを用いた閾値秘密分散法（ランプ型閾値法）の分散・復元方法を示す。なお、説明の前に、説明で用いる記号を数６のように定義する。
【００４７】
【数６】
0005065795.tif 000007
【００４８】
表１に、（３，５）閾値法を基にし、ｎｐ＝ｎ＝５、ｋ＝３、Ｌ＝２としたランプ型閾値法の分散情報の構成の一例を示す。表１においては、従来の（３，５）閾値法で乱数Ｒ01Ｒ11、としていた部分を、部分秘密情報Ｋ4、Ｋ5に置き換えることで実現している。この結果、各分散情報のそれぞれのサイズを秘密情報の２／３に削減している。
【００４９】
【表１】
0005065795.tif 000008
【００５０】
部分分散情報生成装置においては、表１に従って、各部分分散情報が生成される。このとき、例えば、Ｓ0、Ｓ１、Ｓ２より全ての部分秘密情報を復元する場合、第１の秘密情報復元器２２および第２の秘密情報復元器２３では、以下の組み合わせのＸＯＲ演算が実行され、部分秘密情報が復元される。まず、以下は通常通りの部分秘密情報の復元演算である。
【００５１】
【数７】
0005065795.tif 000009
【００５２】
さらに、乱数と置き換えて部分分散情報を構成するＬ＝２個の部分秘密情報は、次の演算により復元される。
【００５３】
【数８】
0005065795.tif 000010
最終的に復元された部分秘密情報は以下のように連結されて秘密情報として出力される。
【００５４】
【数９】
0005065795.tif 000011
【００５５】
なお、分散情報生成装置および秘密情報復元装置の処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを分散情報生成装置および秘密情報復元装置に読み込ませ、実行することによって本発明の分散情報生成装置および秘密情報復元装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００５６】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００５７】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００５８】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００５９】
【図１】本実施形態に係る分散情報生成装置の構成図である。
【図２】本実施形態に係る分散情報生成装置の処理フローである。
【図３】本実施形態に係る秘密情報復元装置の構成図である。
【図４】本実施形態に係る秘密情報復元装置の処理フローである。
【符号の説明】
【００６０】
１１・・・秘密情報分割器、１２ａ、・・・、１２ｎ・・・乱数生成器、１３・・・部分分散情報生成器、１３ａ・・・部分秘密情報入力部、１３ｂ・・・乱数入力部、１４・・・連結器、１５・・・送信器、２１・・・分散情報分割器、２２・・・第１の部分秘密情報復元器、２３・・・第２の部分秘密情報復元器、２４・・・連結器、
【図１】
0005065795.tif 000012
【図２】
0005065795.tif 000013
【図３】
0005065795.tif 000014
【図４】
0005065795.tif 000015