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