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