説明

分散情報検証システム、分散情報検証方法、検証情報生成方法およびプログラム

【課題】巨大な拡大体上の秘密情報を、任意の小規模な有限体上で分散および復元し、加算と離散対数の準同型性を利用しながら分散情報の正当性を検証可能とする。
【解決手段】分散情報生成装置は、秘密情報を、複数の秘密情報に分割し、有限体GF(q)上で演算を行い、分散情報を生成し、秘密情報復元装置は、分散情報検証装置における検証結果が正当である場合に、複数の分散情報を分割し、有限体GF(q)上で演算を行い、秘密情報を復元する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、巨大な拡大体上の秘密情報を、任意の小規模な有限体上で分散および復元し、加算と離散対数の準同型性を利用しながら分散情報の正当性を検証可能とする分散情報検証システム、分散情報検証方法、検証情報生成方法およびプログラムに関する。
【背景技術】
【0002】
近年、情報セキュリティの重要性が高まるにつれ、情報の盗難対策と紛失対策が重要な課題となっている。このようなことから、非特許文献1に示されるような(k、n)閾値秘密分散法は、情報の秘匿と紛失によるリスクの回避を同時に実現する手法として、注目を浴びている。ここで、(k、n)閾値秘密分散は、機密情報をn個の分散情報に分散し、そのうち任意のk個の分散情報が集まれば、復元できることを意味する。
【0003】
ここで、広く用いられている従来手法として、1979年に提案されたShamirの(k、n)閾値法(例えば、非特許文献1参照。)がある。この方式は、秘密情報を素体GF(p)上の要素として演算することにより実現される。なお、このとき、pは素数である。
【0004】
また、非特許文献2において、Karninは、非特許文献1に示す素体上で構成されるShamirの秘密分散法を、有限体GF(q)のm次拡大体GF(q)上での秘密分散法へと一般化し、管理者数やコンピュータ上への実装の面で、柔軟な構成を実現している。ここで、素体・拡大体とは抽象代数学において特定の演算規則を満たす集合のことを示す。
【0005】
つまり、非特許文献1および2の手法では、秘密情報をそれぞれ素体・拡大体の要素としてとらえ、その素体・拡大体上での演算を行うことにより分散・復元を実現する。その際の最大分散数は「素体・拡大体の要素数マイナス1」となる。このため、非特許文献1および非特許文献2の手法では、分散する数が大きいほど、あるいは秘密情報の大きさが大きいほど、より大きな素体・拡大体上での演算が必要となるが、一般的に、巨大な素体上・拡大体上での演算はコンピュータ上で低速であるという問題がある。
【0006】
一方、2007年に提案された、排他的論理和(Exclusive−OR、XOR)を用いて、高速に分散情報の生成・秘密情報の復元を可能とする(k、n)閾値法がある(例えば、非特許文献3あるいは4を参照。)。これらの高速(k、n)閾値法は、単純に高速動作するだけではなく、非特許文献1および2と同様に、情報理論的安全性が保証され、分散情報のデータ長が秘密情報のデータ長と等しいという特長を持つ。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】A.Shamir,‘‘How to share a secret,’’Communication of the ACM,vol.22,no.11,pp.612―613,1979.
【非特許文献2】E.D.Karnin,J.W. Greene, M. E. Hellman,``On Secret Sharing Systems,’’IEEE Transaction on Information Theory,vol.29,no.1,pp.35―49
【非特許文献3】J.Kurihara,S.Kiyomoto,K.Fukushima,T.Tanaka,``A new (k,n)−threshold secret sharing scheme and its extension,’’Proceeding of ISC‘08,Lecture Note in Computer Science,vol.5222,pp.455−470,2008,Springer−Verlag.
【非特許文献4】藤井吉弘,栃窪孝也,保坂範和,多田美奈子,加藤岳久,``排他的論理和を用いた(k、n)しきい値法の構成法,’’電子情報通信学会技術研究報告,vol.107,no.44,情報セキュリティ、ISSN0913−5685、ISEC2007−5.
【非特許文献5】P.Feldman,’’ A practical scheme for non−interactive verifiable secret sharing,’’Proceeding of IEEE FOCS,pp.427−437,1987.
【非特許文献6】T.P.Pedersen,’’Non−interactive and information−theoretic secure verifiable secret sharing,’’ Proceeding of CRYPTO ’91, Lecture Note in Computer Science, vol.576,pp.129−140,1991. Springer−Verlag.
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかしながら、非特許文献3あるいは4の手法は、位数2の素体GF(q)上で実行されるため、非特許文献1および2をベースとした閾値暗号などの「加算と離散対数の準同型性」を利用するアプリケーションに適用することは難しいという問題がある。そのため、非特許文献1の手法に基づいた「分散情報の正当性(正しく秘密情報から生成された分散情報であるか)」を検証可能とする検証可能秘密分散法への拡張が困難であるといった問題があった(例えば、非特許文献5および6参照)。
【0009】
そこで、本発明は、上述の課題に鑑みてなされたものであり、巨大な拡大体上の秘密情報を、任意の小規模な有限体上で分散および復元し、加算と離散対数の準同型性を利用しながら分散情報の正当性を検証可能とする分散情報検証システム、分散情報検証方法、検証情報生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【0011】
(1)本発明は、分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムであって、前記分散情報生成装置は、秘密情報を、複数の秘密情報に分割し、有限体GF(q)上で演算を行い、分散情報を生成し、前記秘密情報復元装置は、前記分散情報検証装置における検証結果が正当である場合に、複数の分散情報を分割し、有限体GF(q)上で演算を行い、秘密情報を復元することを特徴とする分散情報検証システムを提案している。
【0012】
この発明によれば、分散情報生成装置は、秘密情報を、複数の秘密情報に分割し、有限体GF(q)上で演算を行い、分散情報を生成し、秘密情報復元装置は、分散情報検証装置における検証結果が正当である場合に、複数の分散情報を分割し、有限体GF(q)上で演算を行い、秘密情報を復元する。したがって、例えば、伝送路上で、何者かによって、分散情報が改竄されたり、あるいは、伝送路上でエラーが発生して、分散情報が別の分散情報に書き換わるような状況にあっても、分散情報の正当性を確認して、秘密情報の復元を行うため、正しい秘密情報を確実に復元することができる。
【0013】
(2)本発明は、分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、該生成された検証情報を格納する検証情報サーバと、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムであって、前記分散情報生成装置は、秘密情報を、複数の秘密情報に分割し、有限体GF(q)上で演算を行い、分散情報を生成し、前記秘密情報復元装置は、前記検証情報サーバから読み出した検証情報に対して、前記分散情報検証装置における検証を行い、検証結果が正当である場合に、複数の分散情報を分割し、有限体GF(q)上で演算を行い、秘密情報を復元することを特徴とする分散情報検証システムを提案している。
【0014】
この発明によれば、分散情報生成装置は、秘密情報を、複数の秘密情報に分割し、有限体GF(q)上で演算を行い、分散情報を生成し、秘密情報復元装置は、検証情報サーバから読み出した検証情報に対して、分散情報検証装置における検証を行い、検証結果が正当である場合に、複数の分散情報を分割し、有限体GF(q)上で演算を行い、秘密情報を復元する。したがって、例えば、伝送路上で、何者かによって、分散情報が改竄されたり、あるいは、伝送路上でエラーが発生して、分散情報が別の分散情報に書き換わるような状況にあっても、分散情報の正当性を確認して、秘密情報の復元を行うため、正しい秘密情報を確実に復元することができる。
【0015】
(3)本発明は、(1)または(2)の分散情報検証システムについて、前記分散情報生成装置が、拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割する分割手段と、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成する乱数生成手段と、有限体GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成するコンパニオン行列生成手段と、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力する演算手段と、該出力された部分分散情報を連結して分散情報を生成する連結手段と、分散情報の各管理者に、前記生成した分散情報を送信する送信手段と、を備えたことを特徴とする分散情報検証システムを提案している。なお、ここで、コンパニオン行列とは、m次原始多項式f(x)を数1のように表したときに、このf(x)に対応する数2に示すようなm行m列のバイナリ行列をいう。
【0016】
【数1】

【0017】
【数2】

【0018】
この発明によれば、分割手段は、拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割する。乱数生成手段は、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成する。コンパニオン行列生成手段は、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列とそのコンパニオン行列の累乗とを生成する。演算手段は、生成されたコンパニオン行列とそのコンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力する。連結手段は、その出力された部分分散情報を連結して分散情報を生成する。送信手段は、分散情報の各管理者に、生成した分散情報を送信する。したがって、大規模な拡大体上の秘密情報を任意の有限体上に分割して、演算を行うため、加算と離散対数の準同型性を利用したアプリケーションにも容易に適用することができる。
【0019】
(4)本発明は、(3)の分散情報検証システムについて、前記検証情報生成装置が、素数uを生成する素数生成手段と、乗法群GF(u)(=Zu)の生成元gを生成する生成元生成手段と、該生成した生成元gと前記分散情報生成装置の分割手段により得られる部分秘密情報と前記乱数生成手段により生成される乱数とを演算して、検証情報を生成する検証情報生成手段と、を備えることを特徴とする分散情報検証システムを提案している。
【0020】
この発明によれば、検証情報生成装置の素数生成手段は、素数uを生成する。生成元生成手段は、乗法群GF(u)(=Zu)の生成元gを生成する。検証情報生成手段は、その生成した生成元gと分散情報生成装置の分割手段により得られる部分秘密情報と分散情報生成装置の乱数生成手段により生成される乱数とを演算して、検証情報を生成する。したがって、生成元gと分散情報生成装置の分割手段により得られる部分秘密情報と分散情報生成装置の乱数生成手段により生成される乱数とを演算することにより、比較的簡易な演算で検証情報を生成することができる。
【0021】
(5)本発明は、(4)の分散情報検証システムについて、前記分散情報検証装置が、前記分散情報をm個の部分分散情報に分割する第1の分割手段と、該分割されたm個の部分分散情報と前記生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する第2の演算手段と、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成する第2のコンパニオン行列生成手段と、前記検証情報と前記生成されたコンパニオン行列とを演算し、前記検証情報を変換する変換手段と、該変換された検証情報と前記第2の演算手段による演算結果とが、GF(u)上で等しいか否かを検証する検証手段と、を備えたことを特徴とする分散情報検証システムを提案している。
【0022】
この発明によれば、分散情報検証装置の第2の分割手段は、分散情報をm個の部分分散情報に分割する。第2の演算手段は、その分割されたm個の部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する。第2のコンパニオン行列生成手段は、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列とそのコンパニオン行列の累乗とを生成する。変換手段は、検証情報と生成されたコンパニオン行列とを演算し、検証情報を変換する。検証手段は、その変換された検証情報と第2の演算手段による演算結果とが、GF(u)上で等しいか否かを検証する。したがって、分割されたm個の部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算した演算結果と変換された検証情報とが、GF(u)上ですべて等しいか否かにより、検証を行うため、比較的簡易な演算で、分散情報が正当であるか否かを検証することができる。
【0023】
(6)本発明は、(3)の分散情報検証システムについて、前記秘密情報復元装置が、k個の分散情報を受信する受信手段と、該受信したk個の分散情報を分割して、km個の部分分散情報を出力する分割手段と、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と、前記受信した分散情報のインデックスとを用いて分散情報の生成行列を生成する行列生成手段と、該生成した生成行列の逆行列を導出する行列演算手段と、該導出した逆行列の構成に基づいて定まる組み合わせに応じて、前記部分分散情報を有限体GF(q)上において演算し、m個の部分秘密情報を出力する演算手段と、該出力された部分秘密情報を連結して秘密情報を出力する連結手段と、を備えることを特徴とする分散情報検証システムを提案している。
【0024】
この発明によれば、受信手段は、k個の分散情報を受信する。分割手段は、その受信したk個の分散情報を分割して、km個の部分分散情報を出力する。行列生成手段は、有限体GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と、受信した分散情報のインデックスとを用いて分散情報の生成行列を生成する。行列演算手段は、その生成した生成行列の逆行列を導出する。演算手段は、その導出した逆行列の構成に基づいて定まる組み合わせに応じて、部分分散情報を有限体GF(q)上において演算し、m個の部分秘密情報を出力する。連結手段は、その出力された部分秘密情報を連結して秘密情報を出力する。したがって、任意の有限体上で復元のための演算処理を行うことから、加算と離散対数の準同型性を利用したアプリケーションにも容易に適用することができる。
【0025】
(7)本発明は、分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムにおける分散情報検証方法であって、前記分散情報生成装置は、秘密情報を、複数の秘密情報に分割する第1のステップと、該分割した秘密情報に有限体GF(q)上で演算を行い、分散情報を生成する第2のステップと、を備え、前記秘密情報復元装置は、前記分散情報検証装置における検証結果が正当である場合に、複数の分散情報を分割する第3のステップと、該分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する第4のステップと、を備えることを特徴とする分散情報検証方法を提案している。
【0026】
この発明によれば、分散情報生成装置は、秘密情報を、複数の秘密情報に分割し、その分割した秘密情報に有限体GF(q)上で演算を行い、分散情報を生成する。一方、秘密情報復元装置は、分散情報検証装置における検証結果が正当である場合に、複数の分散情報を分割し、その分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する。したがって、例えば、伝送路上で、何者かによって、分散情報が改竄されたり、あるいは、伝送路上でエラーが発生して、分散情報が別の分散情報に書き換わるような状況にあっても、分散情報の正当性を確認して、秘密情報の復元を行うため、正しい秘密情報を確実に復元することができる。
【0027】
(8)本発明は、分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、該生成された検証情報を格納する検証情報サーバと、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムにおける分散情報の検証方法であって、前記分散情報生成装置は、秘密情報を、複数の秘密情報に分割する第1のステップと、該分割した秘密情報に有限体GF(q)上で演算を行い、分散情報を生成する第2のステップと、を備え、前記秘密情報復元装置は、前記検証情報サーバから前記検証情報読み出す第3のステップと、前記検証情報サーバから読み出した検証情報に対して、前記分散情報検証装置における検証を行う第4のステップと、該検証結果が正当である場合に、複数の分散情報を分割する第5のステップと、該分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する第6のステップと、を備えたことを特徴とする分散情報検証方法を提案している。
【0028】
この発明によれば、分散情報生成装置は、秘密情報を、複数の秘密情報に分割し、その分割した秘密情報に有限体GF(q)上で演算を行い、分散情報を生成する。一方、秘密情報復元装置は、検証情報サーバから検証情報読み出し、検証情報サーバから読み出した検証情報に対して、分散情報検証装置における検証を行って、その検証結果が正当である場合に、複数の分散情報を分割し、その分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する。したがって、例えば、伝送路上で、何者かによって、分散情報が改竄されたり、あるいは、伝送路上でエラーが発生して、分散情報が別の分散情報に書き換わるような状況にあっても、分散情報の正当性を確認して、秘密情報の復元を行うため、正しい秘密情報を確実に復元することができる。
【0029】
(9)本発明は、拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報の検証情報を生成する検証情報生成方法であって、素数uを生成する第1のステップと、乗法群GF(u)(=Zu)の生成元gを生成する第2のステップと、該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、検証情報を生成する第3のステップと、を備えることを特徴とする検証情報生成方法を提案している。
【0030】
この発明によれば、素数uを生成し、乗法群GF(u)(=Zu)の生成元gを生成して、その生成した生成元gと部分秘密情報と乱数とを演算して、検証情報を生成する。したがって、生成元gと分散情報生成装置の分割手段により得られる部分秘密情報と分散情報生成装置の乱数生成手段により生成される乱数とを演算することにより、比較的簡易な演算で検証情報を生成することができる。
【0031】
(10)本発明は、拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報について、素数uを生成するとともに、乗法群GF(u)(=Zu)の生成元gを生成し、該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、生成された検証情報を用いて、分散情報を検証する分散情報検証方法であって、前記分散情報をm個の部分分散情報に分割する第1のステップと、該分割されたm個の部分分散情報と前記生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する第2のステップと、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成する第3のステップと、前記検証情報と前記生成されたコンパニオン行列とを演算し、前記検証情報を変換する第4のステップと、該変換された検証情報と前記第3のステップにおける演算結果とが、GF(u)上で等しいか否かを検証する第5のステップと、を備えたことを特徴とする分散情報検証方法を提案している。
【0032】
この発明によれば、分散情報をm個の部分分散情報に分割し、その分割されたm個の部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する。そして、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列とそのコンパニオン行列の累乗とを生成し、検証情報と生成されたコンパニオン行列とを演算し、検証情報を変換して、その変換された検証情報と部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算した演算結果とが、GF(u)上で等しいか否かを検証する。したがって、分割されたm個の部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算した演算結果と変換された検証情報とが、GF(u)上ですべて等しいか否かにより、検証を行うため、比較的簡易な演算で、分散情報が正当であるか否かを検証することができる。
【0033】
(11)本発明は、拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報の検証情報を生成する検証情報生成方法をコンピュータに実行させるためのプログラムであって、素数uを生成する第1のステップと、乗法群GF(u)(=Zu)の生成元gを生成する第2のステップと、該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、検証情報を生成する第3のステップと、をコンピュータに実行させるためのプログラムを提案している。
【0034】
この発明によれば、素数uを生成し、乗法群GF(u)(=Zu)の生成元gを生成して、その生成した生成元gと部分秘密情報と乱数とを演算して、検証情報を生成する。したがって、生成元gと分散情報生成装置の分割手段により得られる部分秘密情報と分散情報生成装置の乱数生成手段により生成される乱数とを演算することにより、比較的簡易な演算で検証情報を生成することができる。
【0035】
(12)本発明は、拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報について、素数uを生成するとともに、乗法群GF(u)(=Zu)の生成元gを生成し、該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、生成された検証情報を用いて、分散情報を検証する分散情報検証方法をコンピュータに実行させるためのプログラムであって、前記分散情報をm個の部分分散情報に分割する第1のステップと、該分割されたm個の部分分散情報と前記生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する第2のステップと、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成する第3のステップと、前記検証情報と前記生成されたコンパニオン行列とを演算し、前記検証情報を変換する第4のステップと、該変換された検証情報と前記第3のステップにおける演算結果とが、GF(u)上で等しいか否かを検証する第5のステップと、をコンピュータに実行させるためのプログラムを提案している。
【0036】
この発明によれば、分散情報をm個の部分分散情報に分割し、その分割されたm個の部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する。そして、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列とそのコンパニオン行列の累乗とを生成し、検証情報と生成されたコンパニオン行列とを演算し、検証情報を変換して、その変換された検証情報と部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算した演算結果とが、GF(u)上で等しいか否かを検証する。したがって、分割されたm個の部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算した演算結果と変換された検証情報とが、GF(u)上ですべて等しいか否かにより、検証を行うため、比較的簡易な演算で、分散情報が正当であるか否かを検証することができる。
【発明の効果】
【0037】
本発明によれば、巨大な拡大体上の秘密情報を、任意の小規模な有限体上で分散・復元し、しかも、分散情報の正当性を簡易な演算で検証することができるという効果がある。したがって、例えば、伝送路上で何者かに分散情報が改ざんされた場合や伝送路でエラーが発生して分散情報が書き換わったというような状況が起こった場合でも、別経路で検証情報を入手することにより、分散情報の改ざんやエラーを容易に検知することができるという効果がある。
【図面の簡単な説明】
【0038】
【図1】本発明の第1の実施形態に係る分散情報検証システムの構成を示す図である。
【図2】本発明の第1の実施形態に係る分散情報生成装置の構成を示す図である。
【図3】本発明の第1の実施形態に係る検証情報生成装置の構成を示す図である。
【図4】本発明の第1の実施形態に係る検証情報生成装置の処理フローを示す図である。
【図5】本発明の第1の実施形態に係る秘密情報復元装置の構成を示す図である。
【図6】本発明の第1の実施形態に係る分散情報検証装置の処理フローを示す図である。
【図7】本発明の第1の実施形態に係る分散情報検証装置の構成を示す図である。
【図8】本発明の第1の実施形態に係る分散情報検証システムの処理フローを示す図である。
【図9】本発明の第2の実施形態に係る分散情報検証システムの構成を示す図である。
【図10】本発明の第2の実施形態に係る分散情報検証システムの処理フローを示す図である。
【発明を実施するための形態】
【0039】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【0040】
<第1の実施形態>
図1から図8を用いて、本発明の第1の実施形態について説明する。
【0041】
<分散情報検証システムの構成>
本実施形態に係る分散情報検証システムは、図1に示すように、分散情報生成装置100と、検証情報生成装置200と、秘密情報復元装置300と、分散情報検証装置400とから構成されている。
【0042】
本実施形態に係る分散情報検証システムは、秘密情報復元装置300が分散情報から秘密情報の復元を行う前に、分散情報検証装置400により、分散情報の正当性を確認した上で、分散情報が正当である場合に、秘密情報の復元を実行するものである。これにより、例えば、伝送路上で、何者かによって、分散情報が改竄されたり、あるいは、伝送路上でエラーが発生して、分散情報が別の分散情報に書き換わるような状況にあっても、正しい秘密情報を確実に復元することができる。
【0043】
ここで、分散情報生成装置100は、拡大体GF(q)の秘密情報に対して、GF(q)上で演算を行い、分散情報を生成する。検証情報生成装置200は、分散情報生成装置100において、分割された秘密情報と生成する乱数とに基づいて、検証情報を生成する。秘密情報復元装置300は、受信した分散情報に対して、GF(q)上で演算を行い、秘密情報を復元する。分散情報検証装置400は、検証情報生成装置200が生成した検証情報に所定の演算を実行した演算結果と、分散情報生成装置100が生成した分散情報に所定の演算を実行した演算結果とがすべて等しいか否かを検証することにより、分散情報の正当性を検証する。なお、上記の各装置の詳細については、後述する。
【0044】
<分散情報生成装置の構成>
図2を用いて、本実施形態に係る分散情報生成装置の構成について説明する。
【0045】
本実施形態に係る分散情報生成装置は、図1に示すように、分割器1と、乱数生成器2と、コンパニオン行列生成器3と、GF(q)演算器4と、連結器5a〜5nと、送信器6とから構成されている。
【0046】
分割器1は、拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、分割した部分秘密情報をGF(q)演算器4に出力する。乱数生成器2は、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成し、生成した乱数をGF(q)演算器4に出力する。
【0047】
コンパニオン行列生成器3は、パラメータk、n、mの値に応じて、有限体GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列とそのコンパニオン行列の累乗とをそれぞれqm−1個の行列を生成し、GF(q)演算器4に出力する。
【0048】
GF(q)演算器4は、入力されたコンパニオン行列とそのコンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、部分秘密情報と乱数とを有限体GF(q)上で演算し、mn個(nは、正の整数)の部分分散情報をn個の連結器5a〜5nに出力する。
【0049】
連結器5a〜5nは、それぞれ、GF(q)演算器4から入力されたm個の部分分散情報を連結して分散情報を生成し、送信器6に出力する。送信器6は、入力した分散情報を分散情報の各管理者に送信して、配布する。
【0050】
<分散情報生成装置の処理>
本実施形態に係る分散情報生成装置の処理について説明する。なお、説明にあたって用いる記号を数3のように、定義する。
【0051】
【数3】

【0052】
まず、分割器1にdmビットの秘密情報s∈GF(q)を入力して、s、s、・・・・、sm−1∈GF(q)のm個の部分秘密情報に分割する。このとき、秘密情報ベクトルsは、数4のように表される。
【0053】
【数4】

【0054】
次に、乱数生成器2を用いて、(k−1)m個の乱数r、・・・・、rm−1、・・・・、rk−2、・・・・、rk−2m−1∈GF(q)を生成する。このとき、乱数ベクトルr(h=0、1、・・・・、k−2)は、数5のように表される。
【0055】
【数5】

【0056】
また、コンパニオン行列生成器3にパラメータmを入力して、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列Cとそのコンパニオン行列の累乗とを生成する。
【0057】
GF(q)演算器4において、コンパニオン行列Cとそのコンパニオン行列の累乗とを用いて、部分分散情報を数6により生成する。
【0058】
【数6】

【0059】
ここで、iは、数7のように定義される。また、数6において、すべての演算は、有限体GF(q)上で実行される。また、部分分散情報ベクトルwの構成は、数8のように表される。
【0060】
【数7】

【0061】
【数8】

【0062】
次に、それぞれの連結器5a〜5nにおいて、wの要素(部分分散情報)を数9のように連結して分散情報wを生成し、送信器6がセキュアな伝送路を介して、管理者Pに分散情報wを送信する。
【0063】
【数9】

【0064】
したがって、本実施形態に係る分散情報生成装置によれば、大規模な拡大体上の秘密情報を任意の有限体上に分割して、演算を行うため、加算と離散対数の準同型性を利用したアプリケーションにも容易に適用することができる。
【0065】
<検証情報生成装置の構成>
本実施形態に係る検証情報生成装置は、図3に示すように、素数u生成器11と、生成元g生成器12と、GF(u)(=Zu)演算器(検証用情報生成器)13と、送信器14とから構成されている。
【0066】
ここで、素数u生成器11は、素数uを生成する。生成元g生成器12は、乗法群GF(u)(=Zu)の生成元gを生成する。GF(u)(=Zu)演算器(検証用情報生成器)13は、その生成した生成元gと分散情報生成装置100の分割器1により得られる部分秘密情報と分散情報生成装置100の乱数生成器2により生成される乱数とを演算して、検証情報を生成する。
【0067】
<検証情報生成装置の処理>
次に、図4を用いて、検証情報生成装置の処理について説明する。
【0068】
まず、p|u―1を満たす素数を生成する(ステップS101)。次に、位数pの乗法Zuの生成元g∈Zを決定する(ステップS102)。
【0069】
そして、km個の検証用情報c、・・・・、cm−1、・・・・、ck−1、・・・・、ck−1m−1を以下数10のように生成する(ステップS103)。
【0070】
【数10】

【0071】
ここで、すべての要素は素体Zu上で演算される。上記数10の演算により、すべての部分秘密情報および乱数は、離散対数によって秘匿される。そして、生成元g∈Zuおよび検証用情報c、・・・・、ck−1は、各管理者に送付する、あるいは、公開情報として公開される。
【0072】
<検証情報検証装置の構成>
本実施形態に係る検証情報検証装置は、図5に示すように、コンパニオン行列生成器21と、GF(u)(=Zu)演算器(検証用情報変換器)22と、分割器23と、GF(u)(=Zu)演算器24と、合同検証器25とから構成されている。
【0073】
ここで、分割器23は、分散情報をm個の部分分散情報に分割する。GF(u)(=Zu)演算器24は、その分割されたm個の部分分散情報と生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する。
【0074】
コンパニオン行列生成器21は、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列とそのコンパニオン行列の累乗とを生成する。GF(u)(=Zu)演算器24は、検証情報と生成されたコンパニオン行列とを演算し、検証情報を変換する。合同検証器25は、その変換された検証情報とGF(u)(=Zu)演算器24による演算結果とが、GF(u)上で等しいか否かを検証する。
【0075】
<検証情報検証装置の処理>
図6を用いて、検証情報検証装置の処理について、説明する。
まず、数11に示す演算★を数12の演算を行うものとして、定義する。
【0076】
【数11】

【0077】
【数12】

【0078】
ここで、aは、数13に示すとおりであり、bは、数14に示すとおりである。
【0079】
【数13】

【0080】
【数14】

【0081】
次に、数15に示す演算●を数16に示すように、演算★をベクトル内部で並列に行うものとして定義する。
【0082】
【数15】

【0083】
【数16】

【0084】
ここで、bは、数17に示すとおりである。さらに、次の要素間の乗算を並列に行う演算を数18の演算を行うものとして、定義する。
【0085】
【数17】

【0086】
【数18】

【0087】
ここで、dは、数20に示すとおりである。これらの演算を用いて、分散情報の正当性を以下の手順で検証することができる。
【0088】
【数19】

【0089】
つまり、管理者pは、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列とそのコンパニオン行列の累乗とを生成し(ステップS201)、検証情報と生成されたコンパニオン行列とを用いて、数20に示す演算を実行してvを得る(ステップS202)。
【0090】
【数20】

【0091】
次に、管理者pは、分散情報wを分割し(ステップS203)、m−1個の部分分散情報w(i、0)、・・・・、w(i、m−1)を生成し、この部分分散情報と乗法群GF(u)(=Zu)の生成元gとを演算し(ステップS204)、数21に示すe(i、j)を生成する。なお、jは、j=0、1、・・・、m−1である。
【0092】
【数21】

【0093】
そして、管理者Piは、数22の等式が、j=0、1、・・・、m−1のすべてのjについて成立するか否かを検証する(ステップS205)。このとき、数22がすべてのjについて成立するときに、wが正当に分散されたものであることを検証することができる。
【0094】
【数22】

【0095】
<秘密情報復元装置の構成>
図7を用いて、本実施形態に係る秘密情報復元装置の構成について説明する。
【0096】
本実施形態に係る秘密情報復元装置は、図7に示すように、受信器31と、行列生成器32と、分割器33a〜33nと、行列演算器34と、GF(q)演算器35と、連結器36とから構成されている。
【0097】
受信器31は、k人の管理人からk個の分散情報を受信し、受信したk個の分散情報をそれぞれの分割器33a〜33nに出力する。それぞれの分割器33a〜33nは、入力したk個の分散情報を分割して、km個の部分分散情報をGF(q)演算器35に出力する。
【0098】
行列生成器32は、入力したパラメータmの値に応じて、有限体GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と、受信した分散情報のインデックスとを用いて分散情報の生成行列を生成し、行列演算器34に出力する。
【0099】
行列演算器34は、入力した生成行列の逆行列を導出し、GF(q)演算器35に出力する。GF(q)演算器35は、入力された逆行列の構成に基づいて定まる組み合わせに応じて、部分分散情報を有限体GF(q)上において演算し、m個の部分秘密情報を連結器36に出力する。連結器36は、入力された部分秘密情報を連結して秘密情報を出力する。
【0100】
<秘密情報復元装置の処理>
次に、本実施形態に係る秘密情報復元装置の処理について説明する。
なお、説明にあたって用いる記号を分散情報生成装置での説明と同様に定義する。
【0101】
まず、受信器31は、wt0、wt1、・・・・、wtk−1のk個の分散情報を管理者Pから受信し、分割器33a〜33nに出力する。次に、それぞれの分割器33a〜33nにおいて、入力した分散情報wをm個の部分分散情報w(i、0)、・・・・、w(i、m−1)∈GF(q)へと分割し、km個の部分分散情報をGF(q)演算器35に出力する。なお、i=t、・・・・、tk−1である。また、このとき、部分分散情報ベクトルwは、数10のように定義される。
【0102】
【数23】

【0103】
一方、有限体GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と、前記受信した分散情報のインデックスとを用いて分散情報の生成行列を生成し、その生成した生成行列の逆行列を導出する。
【0104】
具体的には、数24に示すkm×2km行列(G|Ikm)を入力した分散情報のインデックスおよびコンパニオン行列Cから導出する。
【0105】
【数24】

【0106】
数24において、Ikmは、km行km列の単位行列を示し、Gを生成行列と呼ぶ。ここで、ガウスの消去法を(G|Ikm)上において実行することにより、数25に示す行列を得る。
【0107】
【数25】

【0108】
数25において、Gauss()は、有限体GF(q)上のガウスの消去法を実行する関数とする。この際、Mは、Gに対する逆行列となる。なお、上記のように、ガウスの消去法を利用する例について説明したが、LU分解などの他のアルゴリズムを用いることもできる。
【0109】
次に、導出した逆行列の構成に基づいて定まる組み合わせに応じて、部分分散情報を有限体GF(q)上において演算し、m個の部分秘密情報を出力する。具体的には、逆行列Mを用いて、数13に示す演算を有限体GF(q)上において実行することにより、すべての部分秘密情報および乱数を復元することができる。数26において、sは、数27に、rは、数28に示されるように定義される。
【0110】
【数26】

【0111】
【数27】

【0112】
【数28】

【0113】
そして、出力された部分秘密情報を連結して、数29に示すような秘密情報sを出力する。
【0114】
【数29】

【0115】
したがって、本実施形態に係る秘密情報復元装置によれば、任意の有限体上で復元のための演算処理を行うことから、加算と離散対数の準同型性を利用したアプリケーションにも容易に適用することができる。
【0116】
<分散情報検証システムの処理>
図8を用いて、本実施形態に係る分散情報検証システムの処理について、説明する。
まず、分散情報生成装置100が、秘密情報を複数の部分秘密情報に分割し(ステップS301)、有限体GF(q)上で、演算を行い、分散情報を生成し、送信する(ステップS302)。また、このとき、検証情報生成装置200は、検証情報を生成し、これを送信する。
【0117】
秘密情報復元装置300は、分散情報と検証情報とを受信すると、分散情報の正当性を検証するために、検証情報を分散情報検証装置400に送信する。分散情報検証装置400は、受信した検証情報に基づいて、分散情報を検証し、その検証結果を秘密情報復元装置300に送信する。
【0118】
検証結果を受信した秘密情報復元装置300は、その検証結果が正当である場合に、複数の分散情報を分割し(ステップS303)、分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する(ステップS304)。
【0119】
したがって、本実施形態によれば、例えば、伝送路上で、何者かによって、分散情報が改竄されたり、あるいは、伝送路上でエラーが発生して、分散情報が別の分散情報に書き換わるような状況にあっても、分散情報の正当性を確認して、秘密情報の復元を行うため、正しい秘密情報を確実に復元することができる。
【0120】
<第2の実施形態>
図9および図10を用いて、本発明の第2の実施形態について説明する。
なお、本実施形態に係る分散情報検証システムは、図9に示すように、分散情報生成装置100と、検証情報生成装置200と、秘密情報復元装置300と、分散情報検証装置400と、サーバ600とから構成されているが、サーバ600以外の装置の構成は、第1の実施形態と同様であるため、その詳細な説明は、省略する。
【0121】
ここで、サーバ600は、検証情報生成装置200が生成した分散情報の検証情報を例えば、固有のインデックスに対応させて格納する記憶装置である。
【0122】
具体的な処理動作は、まず、分散情報生成装置100が、秘密情報を複数の部分秘密情報に分割し(ステップS401)、有限体GF(q)上で、演算を行い、分散情報を生成し、送信する(ステップS402)。また、このとき、検証情報生成装置200は、検証情報を生成し、これをサーバ600に送信する。
【0123】
秘密情報復元装置300は、サーバ600から固有のインデックスに紐付いた検証情報を読み出し(ステップS403)、読み出した検証情報を分散情報の正当性を検証するために、検証情報を分散情報検証装置400に送信する。分散情報検証装置400は、受信した検証情報に基づいて、分散情報を検証し、その検証結果を秘密情報復元装置300に送信する(ステップS404)。
【0124】
検証結果を受信した秘密情報復元装置300は、その検証結果が正当である場合に、複数の分散情報を分割し(ステップS405)、分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する(ステップS406)。
【0125】
したがって、本実施形態によれば、例えば、伝送路上で、何者かによって、分散情報が改竄されたり、あるいは、伝送路上でエラーが発生して、分散情報が別の分散情報に書き換わるような状況にあっても、分散情報の正当性を確認して、秘密情報の復元を行うため、正しい秘密情報を確実に復元することができる。また、サーバに検証情報を格納することから、古い分散情報についても、同様の効果が期待できる。
【0126】
なお、分散情報検証システムの処理をコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを分散情報生成装置、検証情報生成装置、分散情報復元装置および秘密情報復元装置に読み込ませ、実行することによって本発明の分散情報検証システムを実現することができる。ここでいうコンピュータシステムとは、OSや周辺装置等のハードウェアを含む。
【0127】
また、「コンピュータシステム」は、WWW(World Wide Web)システムを利用している場合であれば、ホームページ提供環境(あるいは表示環境)も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されても良い。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク(通信網)や電話回線等の通信回線(通信線)のように情報を伝送する機能を有する媒体のことをいう。
【0128】
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル(差分プログラム)であっても良い。
【0129】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。例えば、上記の実施形態では、秘密情報復元装置が分散情報の復元に際して、分散情報の正当性を検証する場合について述べたが、分散情報生成装置自らが、生成した分散情報の検証を行ってもよい。
【符号の説明】
【0130】
1・・・分割器
2・・・乱数生成器
3・・・コンパニオン行列生成器
4・・・GF(q)演算器
5a〜5n・・・連結器
6・・・送信器
11・・・素数u生成器
12・・・生成元g生成器
13・・・GF(u)(=Zu)演算器
14・・・送信器
21・・・コンパニオン行列生成器
22・・・GF(u)(=Zu)演算器
23・・・分割器
24・・・合同検証器
31・・・受信器
32・・・行列生成器
33a〜33n・・・分割器
34・・・行列演算器
35・・・GF(q)演算器
36・・・連結器
100・・・分散情報生成装置
200・・・検証情報生成装置
300・・・秘密情報復元装置
400・・・分散情報検証装置
500・・・ネットワーク
600・・・サーバ

【特許請求の範囲】
【請求項1】
分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムであって、
前記分散情報生成装置は、
秘密情報を、複数の秘密情報に分割し、有限体GF(q)上で演算を行い、分散情報を生成し、
前記秘密情報復元装置は、
前記分散情報検証装置における検証結果が正当である場合に、複数の分散情報を分割し、有限体GF(q)上で演算を行い、秘密情報を復元することを特徴とする分散情報検証システム。
【請求項2】
分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、該生成された検証情報を格納する検証情報サーバと、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムであって、
前記分散情報生成装置は、
秘密情報を、複数の秘密情報に分割し、有限体GF(q)上で演算を行い、分散情報を生成し、
前記秘密情報復元装置は、
前記検証情報サーバから読み出した検証情報に対して、前記分散情報検証装置における検証を行い、検証結果が正当である場合に、複数の分散情報を分割し、有限体GF(q)上で演算を行い、秘密情報を復元することを特徴とする分散情報検証システム。
【請求項3】
前記分散情報生成装置が、
拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割する分割手段と、
m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成する乱数生成手段と、
有限体GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成するコンパニオン行列生成手段と、
前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力する演算手段と、
該出力された部分分散情報を連結して分散情報を生成する連結手段と、
分散情報の各管理者に、前記生成した分散情報を送信する送信手段と、
を備えたことを特徴とする請求項1または請求項2に記載の分散情報検証システム。
【請求項4】
前記検証情報生成装置が、
素数uを生成する素数生成手段と、
乗法群GF(u)(=Zu)の生成元gを生成する生成元生成手段と、
該生成した生成元gと前記分散情報生成装置の分割手段により得られる部分秘密情報と前記乱数生成手段により生成される乱数とを演算して、検証情報を生成する検証情報生成手段と、
を備えることを特徴とする請求項3に記載の分散情報検証システム。
【請求項5】
前記分散情報検証装置が、
前記分散情報をm個の部分分散情報に分割する第1の分割手段と、
該分割されたm個の部分分散情報と前記生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する第2の演算手段と、
GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成する第2のコンパニオン行列生成手段と、
前記検証情報と前記生成されたコンパニオン行列とを演算し、前記検証情報を変換する変換手段と、
該変換された検証情報と前記第2の演算手段による演算結果とが、GF(u)上で等しいか否かを検証する検証手段と、
を備えたことを特徴とする請求項4に記載の分散情報検証システム。
【請求項6】
前記秘密情報復元装置が、
k個の分散情報を受信する受信手段と、
該受信したk個の分散情報を分割して、km個の部分分散情報を出力する分割手段と、
GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と、
前記受信した分散情報のインデックスとを用いて分散情報の生成行列を生成する行列生成手段と、
該生成した生成行列の逆行列を導出する行列演算手段と、
該導出した逆行列の構成に基づいて定まる組み合わせに応じて、前記部分分散情報を有限体GF(q)上において演算し、m個の部分秘密情報を出力する演算手段と、
該出力された部分秘密情報を連結して秘密情報を出力する連結手段と、
を備えることを特徴とする請求項3に記載の分散情報検証システム。
【請求項7】
分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムにおける分散情報検証方法であって、
前記分散情報生成装置は、
秘密情報を、複数の秘密情報に分割する第1のステップと、
該分割した秘密情報に有限体GF(q)上で演算を行い、分散情報を生成する第2のステップと、
を備え、
前記秘密情報復元装置は、
前記分散情報検証装置における検証結果が正当である場合に、複数の分散情報を分割する第3のステップと、
該分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する第4のステップと、
を備えることを特徴とする分散情報検証方法。
【請求項8】
分散情報を生成する分散情報生成装置と、前記生成された分散情報を検証するための検証情報を生成する検証情報生成装置と、該生成された検証情報を格納する検証情報サーバと、前記生成された検証情報に基づいて、前記分散情報を検証する分散情報検証装置と、前記分散情報に基づいて、秘密情報を復元する秘密情報復元装置とがネットワークを介して接続されている分散情報検証システムにおける分散情報の検証方法であって、
前記分散情報生成装置は、
秘密情報を、複数の秘密情報に分割する第1のステップと、
該分割した秘密情報に有限体GF(q)上で演算を行い、分散情報を生成する第2のステップと、
を備え、
前記秘密情報復元装置は、
前記検証情報サーバから前記検証情報読み出す第3のステップと、
前記検証情報サーバから読み出した検証情報に対して、前記分散情報検証装置における検証を行う第4のステップと、
該検証結果が正当である場合に、複数の分散情報を分割する第5のステップと、
該分割した分散情報に有限体GF(q)上で演算を行い、秘密情報を復元する第6のステップと、
を備えたことを特徴とする分散情報検証方法。
【請求項9】
拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報の検証情報を生成する検証情報生成方法であって、
素数uを生成する第1のステップと、
乗法群GF(u)(=Zu)の生成元gを生成する第2のステップと、
該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、検証情報を生成する第3のステップと、
を備えることを特徴とする検証情報生成方法。
【請求項10】
拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報について、素数uを生成するとともに、乗法群GF(u)(=Zu)の生成元gを生成し、該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、生成された検証情報を用いて、分散情報を検証する分散情報検証方法であって、
前記分散情報をm個の部分分散情報に分割する第1のステップと、
該分割されたm個の部分分散情報と前記生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する第2のステップと、
GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成する第3のステップと、
前記検証情報と前記生成されたコンパニオン行列とを演算し、前記検証情報を変換する第4のステップと、
該変換された検証情報と前記第3のステップにおける演算結果とが、GF(u)上で等しいか否かを検証する第5のステップと、
を備えたことを特徴とする分散情報検証方法。
【請求項11】
拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報の検証情報を生成する検証情報生成方法をコンピュータに実行させるためのプログラムであって、
素数uを生成する第1のステップと、
乗法群GF(u)(=Zu)の生成元gを生成する第2のステップと、
該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、検証情報を生成する第3のステップと、
をコンピュータに実行させるためのプログラム。
【請求項12】
拡大体GF(q)上の秘密情報(m次元ベクトル)をm(mは、正の整数)個の有限体GF(q)上の部分秘密情報に分割し、m(k−1)個(kは、正の整数)の有限体GF(q)上の乱数を生成するとともに、GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成し、前記生成されたコンパニオン行列と該コンパニオン行列の累乗との構成に基づいて定まる組み合わせに応じて、前記部分秘密情報と生成された乱数とを有限体GF(q)上で演算を行い、mn個(nは、正の整数)の部分分散情報を出力し、該出力された部分分散情報を連結して生成された分散情報について、素数uを生成するとともに、乗法群GF(u)(=Zu)の生成元gを生成し、該生成した生成元gと前記部分秘密情報と前記乱数とを演算して、生成された検証情報を用いて、分散情報を検証する分散情報検証方法をコンピュータに実行させるためのプログラムであって、
前記分散情報をm個の部分分散情報に分割する第1のステップと、
該分割されたm個の部分分散情報と前記生成された乗法群GF(u)(=Zu)の生成元gとをGF(u)上で演算する第2のステップと、
GF(q)[x]上のm次原始多項式f(x)に対応するコンパニオン行列と該コンパニオン行列の累乗とを生成する第3のステップと、
前記検証情報と前記生成されたコンパニオン行列とを演算し、前記検証情報を変換する第4のステップと、
該変換された検証情報と前記第3のステップにおける演算結果とが、GF(u)上で等しいか否かを検証する第5のステップと、
をコンピュータに実行させるためのプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate


【公開番号】特開2011−18218(P2011−18218A)
【公開日】平成23年1月27日(2011.1.27)
【国際特許分類】
【出願番号】特願2009−162851(P2009−162851)
【出願日】平成21年7月9日(2009.7.9)
【出願人】(000208891)KDDI株式会社 (2,700)
【Fターム(参考)】