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