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