秘密情報分散装置、秘密情報分散プログラム、秘密情報分散方法、秘密情報復元装置、秘密情報復元プログラム、秘密情報復元方法、及び秘密情報分散復元システム
【課題】楕円曲線暗号の通信路を介した秘密情報の分散や復元に際して、楕円曲線上の離散対数問題を解かずに秘密分散共有を実現でき、かつその際の演算の効率化を図ることができる秘密情報分散装置、秘密情報分散プログラム、秘密情報分散方法、秘密情報復元装置、秘密情報復元プログラム、秘密情報復元方法、及び秘密情報分散復元システムを提供すること。
【解決手段】秘密情報分散復元システム１に係る部分情報生成サーバー２は、通信路Ｗにのせるために公知の方法にて数値変換された秘密情報ｓを楕円曲線上の点Ｌとする座標処理演算部５と、点Ｌを基に秘密情報ｓを楕円曲線上のｎ個の点に部分情報として分散させる分散演算部６と、を備えている。
【解決手段】秘密情報分散復元システム１に係る部分情報生成サーバー２は、通信路Ｗにのせるために公知の方法にて数値変換された秘密情報ｓを楕円曲線上の点Ｌとする座標処理演算部５と、点Ｌを基に秘密情報ｓを楕円曲線上のｎ個の点に部分情報として分散させる分散演算部６と、を備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密情報分散装置、秘密情報分散プログラム、秘密情報分散方法、秘密情報復元装置、秘密情報復元プログラム、秘密情報復元方法、及び秘密情報分散復元システムに関する。
【背景技術】
【０００２】
外部に漏れてはならない重要なデータや秘密にすべき暗号鍵などは、記憶装置の故障や破壊攻撃等から守るためにコピーを作成する必要がある。しかし、コピーを多く作りすぎると、今度は逆に漏洩のリスクが増加してしまう。このように、相反する二つのリスクを解消するため、近年、秘密情報を複数の部分情報に分散して、元の情報がわからないようにして保存する秘密分散共有法が提案されている。
【０００３】
これによれば、個々の部分情報からは元の情報を一切類推することができないので、暗号化するのと同じように情報漏えいを防止することが可能となる。さらに、復元に必要な部分情報の個数（しきい値）をあらかじめ設定することにより、すべての部分情報を集めなくても復元することが可能となる（ｋ，ｎ）しきい値法と呼ばれる方法が提案されている。この方法によれば、秘密情報ｓをｎ個に分散したとき、ｋ−１（ｋは１＜ｋ＜ｎとなる自然数）個以下の部分情報がわかってもｓについては何もわからないが、ｋ個以上集めれば秘密情報ｓを復元することができる。
【０００４】
この（ｋ，ｎ）しきい値法の実現方法としては、ＳｈａｍｉｒやＢｌａｋｌｅｙの方法が知られている。このうち、Ｓｈａｍｉｒの方法は、有限素体上の多項式の補間を使うことによって実現されている。一方、楕円曲線暗号の研究開発（例えば、特許文献１参照。）が進み、今後は楕円曲線暗号系を使った情報通信機器（特に、小型化されたデバイス）などが増えることが予想される。
【０００５】
この場合、公開情報として、有限体Ｆｐ＾２（ｐは素数）上の楕円曲線Ｅ（Ｆｐ＾２）：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ（ただし、ｑを素数とするとき、この楕円曲線の位数は＃Ｅ（Ｆｐ＾２）＝ｑ）、Ｇ∈Ｅ（Ｆｐ＾２）とする。このとき、∀α∈Ｅ（Ｆｐ＾２）に対して、∃ｔ∈Ｚ／ｑＺ（Ｚは自然数の集合）となる。なお、“＾”はべき乗を表す。
【０００６】
まず、多項式生成ステップ（Ｓ１）では、数値処理された秘密情報ｓに対して、多項式ｆ（ｘ）＝ｓ＋ａ１×ｘ＋・・・＋ａｋ−１×ｘ＾（ｋ−１）を作成する。
【０００７】
次に、分散ステップ（Ｓ２）では、楕円曲線Ｅ（Ｆｐ＾２）上の点としてｎ個の部分情報Ｖｉ＝［ｆ（ｉ）＊Ｇ］を作成する（ｉ＝１〜ｎ）。ここで、“＊”は、楕円曲線上における倍数演算（ｆ（ｉ）個のＧの加算）を表す（以下、同様）。つまり、部分情報を楕円曲線Ｅ（Ｆｐ＾２）におけるＧの倍数で表示する。こうして分散された情報のそれぞれを部分情報の管理者に送信する。
【０００８】
情報を復元する際には、補間ステップ（Ｓ３）にて、部分情報Ｖｉ（ｉ＝１〜ｋ）を持ち寄り、ラグランジュの補間法によってｆ（ｘ）を復元する。
【０００９】
復元ステップ（Ｓ４）では、ｆ（０）＝ｓより［ｓ］＊Ｇを算出する。なお、補間ステップ（Ｓ３）及び復元ステップ（Ｓ４）にて直接ｆ（０）＝ｓを求めて［ｓ］＊Ｇを算出してもよい。こうして、Ｇ及び［ｓ］＊Ｇからｓを算出できれば秘密情報を復元することができる。
【特許文献１】特開２０００−２８４６９０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述のＳｈａｍｉｒの方法では、部分情報を楕円曲線上の点として逐次分散、すなわち、部分情報の数だけ楕円曲線Ｅ（Ｆｐ＾２）の点のＸ座標とする計算を逐次行っている。そのため、ｘのＦｐ＾２上での平方根を求めるアルゴリズムがその都度必要になる。また、上記復元ステップ（Ｓ４）を行う際、楕円曲線上の離散対数問題を解く必要が生じてしまう。
【００１１】
本発明は上記事情に鑑みて成されたものであり、楕円曲線暗号の通信路を介した秘密情報の分散及び復元に際して、楕円曲線上の離散対数問題を解かずに秘密分散共有を実現でき、かつその際の演算の効率化を図ることができる秘密情報分散装置、秘密情報分散プログラム、秘密情報分散方法、秘密情報復元装置、秘密情報復元プログラム、秘密情報復元方法、及び秘密情報分散復元システムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、上記課題を解決するため、以下の手段を採用する。
本発明に係る秘密情報分散装置は、数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、を備えていることを特徴とする。
【００１３】
また、本発明に係る秘密情報分散装置は、前記秘密情報分散装置であって、前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、を備えていることを特徴とする。
【００１４】
また、本発明に係る秘密情報分散プログラムは、コンピュータを前記秘密情報分散装置として機能させることを特徴とする。
【００１５】
また、本発明に係る秘密情報分散方法は、数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理ステップと、前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散ステップと、を備えていることを特徴とする。
【００１６】
また、本発明に係る秘密情報分散方法は、前記秘密情報分散方法であって、前記分散ステップが、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成ステップと、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散ステップと、を備えていることを特徴とする。
【００１７】
また、本発明に係る秘密情報復元装置は、前記秘密情報分散装置によって前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元部を備えていることを特徴とする。
【００１８】
また、本発明に係る秘密情報復元装置は、前記秘密情報復元装置であって、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、を備えていることを特徴とする。
【００１９】
また、本発明に係る秘密情報復元プログラムは、コンピュータを前記秘密情報復元装置として機能させることを特徴とする。
【００２０】
また、本発明に係る秘密情報復元方法は、前記秘密情報分散方法によって前記ｎ個に分散された前記部分情報のうちのｋ個から前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元ステップを備えていることを特徴とする。
【００２１】
また、本発明に係る秘密情報復元方法は、前記秘密情報復元方法であって、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散ステップにて、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、前記復元ステップが、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出ステップと、［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元ステップと、を備えていることを特徴とする。
【００２２】
また、本発明に係る秘密情報分散復元システムは、ｎ個に分散された秘密情報をｋ個（ｋは１＜ｋ＜ｎとなる自然数）の部分情報から復元する秘密分散復元システムであって、数値変換された前記秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から前記点Ｌを前記楕円曲線上の点として復元し、前記楕円曲線の元として前記秘密情報を取り出す復元部と、を備えていることを特徴とする。
【００２３】
また、本発明に係る秘密情報分散復元システムは、前記秘密情報分散復元システムであって、前記分散演算部が、定数項を有しない（ｋ−１）次の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、を備え、前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、を備えていることを特徴とする。
【発明の効果】
【００２４】
本発明によれば、楕円曲線暗号の通信路を介した秘密情報の分散及び復元にかかる演算時間を大幅に短縮させることができる。
【発明を実施するための最良の形態】
【００２５】
本発明に係る一実施形態について、図１及び図２を参照して説明する。
本実施形態に係る秘密情報分散復元システム１は、図１に示すように、秘密情報ｓをｎ個の部分情報に分散させる部分情報生成サーバー（秘密情報分散装置）２と、分散された部分情報のうちのｋ個から秘密情報ｓを復元する（ｎ−１）個の携帯端末装置（秘密情報復元装置）３Ａ及び１つのセキュアサーバー（秘密情報復元装置）３Ｂと、を備えている。
【００２６】
この秘密情報分散復元システム１は、公開情報として上述と同様、有限体Ｆｐ＾２（ｐは素数）上の楕円曲線Ｅ（Ｆｐ＾２）：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ（ただし、ｑを素数とするとき、この楕円曲線の位数は＃Ｅ（Ｆｐ＾２）＝ｑ）、Ｇ∈Ｅ（Ｆｐ＾２）とする通信路Ｗを介して情報の送受信を行う。このとき、∀α∈Ｅ（Ｆｐ＾２）に対して、∃ｔ∈Ｚ／ｑＺ（Ｚは自然数の集合）となる（α＝ｔ＊Ｇが成立）。
【００２７】
部分情報生成サーバー２は、通信路Ｗにのせるために公知の方法にて数値変換された秘密情報ｓを楕円曲線上の点Ｌとする座標処理演算部５と、点Ｌを基に秘密情報ｓを楕円曲線上のｎ個の点に部分情報として分散させる分散演算部６と、を備えている。この部分情報生成サーバー２は、例えば、図示しないマイクロプロセッサ、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ハードディスク、キーボード、ディスプレィを備えている。ハードディスクには、コンピュータプログラムが記憶されている。また、上述の公開情報はＲＯＭに記憶される。
【００２８】
座標処理演算部５は、秘密情報ｓが楕円曲線Ｅ（Ｆｐ＾２）上の所定の点のＸ座標となるように処理を行う。すなわち、楕円曲線Ｅ（Ｆｐ＾２）上でＧをｔ回（ｔは自然数）加算したものがＬとなるようにする（Ｌ＝ｔ＊Ｇ）。
【００２９】
分散演算部６は、分散用多項式ｆ（ｘ）を生成する分散用多項式生成部６Ａと、分散用多項式ｆ（ｘ）に基づき秘密情報ｓを分散させる情報分散部６Ｂと、をさらに備えている。
【００３０】
分散用多項式生成部６Ａは、式（１）に示す定数項を有しない（ｋ−１）次の分散用多項式ｆ（ｘ）を生成する。
【００３１】
【数１】
【００３２】
ここで、ａ１，・・・ａｎ∈Ｚ／ｑＺとする。
【００３３】
情報分散部６Ｂは、ｘ＝１〜ｎに対してｆ（１）〜ｆ（ｎ）を算出し、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する。ここでの“＋”は、楕円曲線上での加算を示す。得られた部分情報Ｖｉは、通信路Ｗを介して部分情報の各分散管理者に１つずつ送信される。
【００３４】
座標処理演算部５及び分散演算部６は、図示しないハードディスクに記憶されている前記コンピュータプログラムが図示しないマイクロプロセッサにより実行されて、その機能を達成する。
【００３５】
一方、携帯端末装置３Ａ及びセキュアサーバー３Ｂは、部分情報生成サーバー２によってｎ個に分散された部分情報のうちのｋ個から楕円曲線Ｅ（Ｆｐ＾２）上の点として点Ｌを復元して秘密情報ｓを取り出す復元部７をそれぞれ備えている。この携帯端末装置３Ａ及びセキュアサーバー３Ｂも、例えば、図示しないマイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスク、キーボード、ディスプレィを備えている。そして、ハードディスクには、コンピュータプログラムが記憶されている。また、上述の公開情報はＲＯＭに記憶される。
【００３６】
復元部７は、部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の補間係数を算出する補間係数算出部７Ａと、秘密情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上の点ＬのＸ座標として復元する情報復元部７Ｂと、を備えている。
【００３７】
補間係数算出部７Ａは、集まったｋ個の部分情報Ｖｉｊ（ｊ＝１〜ｋ）から式（２）に示す多項式補間の係数の計算を行う。
【００３８】
【数２】
【００３９】
情報復元部７Ｂは、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係が成立することを利用して、式（２）を用いて式（３）を算出し、楕円曲線Ｅ（Ｆｐ＾２）上の点ＬのＸ座標として秘密情報ｓを復元する。
【００４０】
【数３】
【００４１】
補間係数算出部７Ａ及び情報復元部７Ｂは、図示しないハードディスクに記憶されている前記コンピュータプログラムが図示しないマイクロプロセッサにより実行されて、その機能を達成する。
【００４２】
次に、秘密情報分散方法及び秘密情報復元方法について、図２を用いながら、秘密情報として鍵情報ｓをｎ人の分散管理者で共有する場合を例として説明する。
この方法は、数値変換された秘密情報である鍵情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上の点Ｌとする座標処理ステップ（Ｓ０１）と、点Ｌを基に鍵情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上のｎ個の点に分散鍵として分散させる分散ステップ（Ｓ０２）と、ｎ個に分散された分散鍵のうちのｋ個から楕円曲線Ｅ（Ｆｐ＾２）上の点として点Ｌを復元して鍵情報ｓを取り出す復元ステップ（Ｓ０３）と、を備えている。
【００４３】
秘密情報分散方法の分散ステップ（Ｓ０２）は、さらに分散用多項式生成ステップ（Ｓ２１）と、情報分散ステップ（Ｓ２２）と、を備えている。また、秘密情報復元方法の復元ステップ（Ｓ０３）は、さらに補間係数算出ステップ（Ｓ３１）と、情報復元ステップ（Ｓ３２）と、を備えている。
【００４４】
座標処理ステップ（Ｓ０１）は、部分情報生成サーバー２の座標処理演算部５にて、鍵情報ｓが楕円曲線Ｅ（Ｆｐ＾２）上の所定の点のＸ座標となるように処理を行う。
【００４５】
分散用多項式生成ステップ（Ｓ２１）は、部分情報生成サーバー２の分散用多項式生成部６Ａにて、式（１）に示す多項式ｆ（ｘ）を生成する。また、情報分散ステップ（Ｓ２２）は、部分情報生成サーバー２の情報分散部６Ｂにてｆ（１）〜ｆ（ｎ）を計算してから、分散鍵Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する。
【００４６】
そして、通信路Ｗを介して各分散管理者が有する携帯端末装置３Ａ又はセキュアサーバー３Ｂにそれぞれ分散鍵Ｖｉを１つずつ送信する。この際、部分情報生成サーバー２と携帯端末装置３Ａ又はセキュアサーバー３Ｂとをつなぐ通信路Ｗ上では分散鍵Ｖｉが１つずつ送受信される。この段階で分散鍵が盗まれても鍵情報ｓが復元されることはない。
【００４７】
復元ステップ（Ｓ０３）では、例えば、ある分散管理者におけるセキュアサーバー３Ｂにて鍵情報ｓを復元する場合、（ｋ−１）個の携帯端末装置３Ａのそれぞれが有する分散鍵をセキュアサーバー３Ｂ宛に１つずつ送信する。この場合、各携帯端末装置３Ａとセキュアサーバー３Ｂとをつなぐ通信路Ｗ上では１つの分散鍵Ｖｉｊ（ｊ＝１〜ｋの何れか）のみが送受信される。この段階で分散鍵が盗まれても鍵情報ｓが復元されることはない。
【００４８】
そして、補間係数算出ステップ（Ｓ３１）では、セキュアサーバー３Ｂの補間係数算出部７Ａにて、分散鍵Ｖｉｊから式（２）に示す多項式補間の係数の計算を行う。
【００４９】
情報復元ステップ（Ｓ３２）では、セキュアサーバー３Ｂの情報復元部７Ｂにて、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、式（３）に示す［ｆ１（０）］＊Ｇ（ｘ＝０）を算出する。そして、楕円曲線Ｅ（Ｆｐ＾２）上の点ＬのＸ座標として鍵情報ｓを復元する。
【００５０】
この秘密情報分散復元システム１、部分情報生成サーバー２、秘密情報分散プログラム、秘密情報分散方法によれば、秘密情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上の点Ｌとしてから楕円曲線Ｅ（Ｆｐ＾２）上に分散させる。そのため、分散させる情報を１／ｎに軽量化させることができるだけでなく、分散させる際にＦｐ＾２上での平方根を求めるアルゴリズムをｎ回から１回に削減することができる。
【００５１】
また、この秘密情報分散復元システム１、携帯端末装置３Ａ及びセキュアサーバー３Ｂ、秘密情報復元プログラム、秘密情報復元方法によれば、上述のようにして分散させた部分情報を集めて復元する。この際、Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ＝［ｆ１（ｉ）］＊Ｇが成立するので、ｆ１（０）（ｘ＝０）を復元すればよく、楕円曲線上の離散対数問題を解くことなく、秘密情報ｓを復元することができる。
【００５２】
したがって、分散及び復元過程における演算時間を大幅に短縮させることができ、携帯電話機のように容量が比較的小さく制限される携帯端末装置においても秘密分散共有管理を行うことができる。
【００５３】
なお、本発明の技術範囲は上記実施の形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲において種々の変更を加えることが可能である。
例えば、上記実施形態では鍵共有の場合について説明しているが、これに限らず、合意認証といった、役職レベルに応じた鍵の分散管理の場合にも適用できる。また、電子チケットを所有するための権利情報をチケットサーバー等にて分散させ、アプリケーションサーバー等で電子チケットを復元させる場合にも適用できる。
【実施例】
【００５４】
上述の合意認証、電子チケットの場合、本発明によって従来よりも数十倍の速度で秘密情報を分散及び復元することができた。
【図面の簡単な説明】
【００５５】
【図１】本発明の一実施形態に係る秘密情報分散復元システムを示す概要図である。
【図２】本発明の一実施形態に係る秘密情報分散方法及び秘密情報復元方法を示す全体フロー図である。
【符号の説明】
【００５６】
１ 秘密情報分散復元システム
２ 部分情報生成サーバー（秘密情報分散装置）
３Ａ 携帯端末装置（秘密情報復元装置）
３Ｂ セキュアサーバー（秘密情報復元装置）
５ 座標処理演算部
６ 分散演算部
６Ａ 分散用多項式生成部
６Ｂ 情報分散部
７ 復元部
７Ａ 補間係数算出部
７Ｂ 情報復元部
【技術分野】
【０００１】
本発明は、秘密情報分散装置、秘密情報分散プログラム、秘密情報分散方法、秘密情報復元装置、秘密情報復元プログラム、秘密情報復元方法、及び秘密情報分散復元システムに関する。
【背景技術】
【０００２】
外部に漏れてはならない重要なデータや秘密にすべき暗号鍵などは、記憶装置の故障や破壊攻撃等から守るためにコピーを作成する必要がある。しかし、コピーを多く作りすぎると、今度は逆に漏洩のリスクが増加してしまう。このように、相反する二つのリスクを解消するため、近年、秘密情報を複数の部分情報に分散して、元の情報がわからないようにして保存する秘密分散共有法が提案されている。
【０００３】
これによれば、個々の部分情報からは元の情報を一切類推することができないので、暗号化するのと同じように情報漏えいを防止することが可能となる。さらに、復元に必要な部分情報の個数（しきい値）をあらかじめ設定することにより、すべての部分情報を集めなくても復元することが可能となる（ｋ，ｎ）しきい値法と呼ばれる方法が提案されている。この方法によれば、秘密情報ｓをｎ個に分散したとき、ｋ−１（ｋは１＜ｋ＜ｎとなる自然数）個以下の部分情報がわかってもｓについては何もわからないが、ｋ個以上集めれば秘密情報ｓを復元することができる。
【０００４】
この（ｋ，ｎ）しきい値法の実現方法としては、ＳｈａｍｉｒやＢｌａｋｌｅｙの方法が知られている。このうち、Ｓｈａｍｉｒの方法は、有限素体上の多項式の補間を使うことによって実現されている。一方、楕円曲線暗号の研究開発（例えば、特許文献１参照。）が進み、今後は楕円曲線暗号系を使った情報通信機器（特に、小型化されたデバイス）などが増えることが予想される。
【０００５】
この場合、公開情報として、有限体Ｆｐ＾２（ｐは素数）上の楕円曲線Ｅ（Ｆｐ＾２）：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ（ただし、ｑを素数とするとき、この楕円曲線の位数は＃Ｅ（Ｆｐ＾２）＝ｑ）、Ｇ∈Ｅ（Ｆｐ＾２）とする。このとき、∀α∈Ｅ（Ｆｐ＾２）に対して、∃ｔ∈Ｚ／ｑＺ（Ｚは自然数の集合）となる。なお、“＾”はべき乗を表す。
【０００６】
まず、多項式生成ステップ（Ｓ１）では、数値処理された秘密情報ｓに対して、多項式ｆ（ｘ）＝ｓ＋ａ１×ｘ＋・・・＋ａｋ−１×ｘ＾（ｋ−１）を作成する。
【０００７】
次に、分散ステップ（Ｓ２）では、楕円曲線Ｅ（Ｆｐ＾２）上の点としてｎ個の部分情報Ｖｉ＝［ｆ（ｉ）＊Ｇ］を作成する（ｉ＝１〜ｎ）。ここで、“＊”は、楕円曲線上における倍数演算（ｆ（ｉ）個のＧの加算）を表す（以下、同様）。つまり、部分情報を楕円曲線Ｅ（Ｆｐ＾２）におけるＧの倍数で表示する。こうして分散された情報のそれぞれを部分情報の管理者に送信する。
【０００８】
情報を復元する際には、補間ステップ（Ｓ３）にて、部分情報Ｖｉ（ｉ＝１〜ｋ）を持ち寄り、ラグランジュの補間法によってｆ（ｘ）を復元する。
【０００９】
復元ステップ（Ｓ４）では、ｆ（０）＝ｓより［ｓ］＊Ｇを算出する。なお、補間ステップ（Ｓ３）及び復元ステップ（Ｓ４）にて直接ｆ（０）＝ｓを求めて［ｓ］＊Ｇを算出してもよい。こうして、Ｇ及び［ｓ］＊Ｇからｓを算出できれば秘密情報を復元することができる。
【特許文献１】特開２０００−２８４６９０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述のＳｈａｍｉｒの方法では、部分情報を楕円曲線上の点として逐次分散、すなわち、部分情報の数だけ楕円曲線Ｅ（Ｆｐ＾２）の点のＸ座標とする計算を逐次行っている。そのため、ｘのＦｐ＾２上での平方根を求めるアルゴリズムがその都度必要になる。また、上記復元ステップ（Ｓ４）を行う際、楕円曲線上の離散対数問題を解く必要が生じてしまう。
【００１１】
本発明は上記事情に鑑みて成されたものであり、楕円曲線暗号の通信路を介した秘密情報の分散及び復元に際して、楕円曲線上の離散対数問題を解かずに秘密分散共有を実現でき、かつその際の演算の効率化を図ることができる秘密情報分散装置、秘密情報分散プログラム、秘密情報分散方法、秘密情報復元装置、秘密情報復元プログラム、秘密情報復元方法、及び秘密情報分散復元システムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、上記課題を解決するため、以下の手段を採用する。
本発明に係る秘密情報分散装置は、数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、を備えていることを特徴とする。
【００１３】
また、本発明に係る秘密情報分散装置は、前記秘密情報分散装置であって、前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、を備えていることを特徴とする。
【００１４】
また、本発明に係る秘密情報分散プログラムは、コンピュータを前記秘密情報分散装置として機能させることを特徴とする。
【００１５】
また、本発明に係る秘密情報分散方法は、数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理ステップと、前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散ステップと、を備えていることを特徴とする。
【００１６】
また、本発明に係る秘密情報分散方法は、前記秘密情報分散方法であって、前記分散ステップが、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成ステップと、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散ステップと、を備えていることを特徴とする。
【００１７】
また、本発明に係る秘密情報復元装置は、前記秘密情報分散装置によって前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元部を備えていることを特徴とする。
【００１８】
また、本発明に係る秘密情報復元装置は、前記秘密情報復元装置であって、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、を備えていることを特徴とする。
【００１９】
また、本発明に係る秘密情報復元プログラムは、コンピュータを前記秘密情報復元装置として機能させることを特徴とする。
【００２０】
また、本発明に係る秘密情報復元方法は、前記秘密情報分散方法によって前記ｎ個に分散された前記部分情報のうちのｋ個から前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元ステップを備えていることを特徴とする。
【００２１】
また、本発明に係る秘密情報復元方法は、前記秘密情報復元方法であって、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散ステップにて、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、前記復元ステップが、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出ステップと、［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元ステップと、を備えていることを特徴とする。
【００２２】
また、本発明に係る秘密情報分散復元システムは、ｎ個に分散された秘密情報をｋ個（ｋは１＜ｋ＜ｎとなる自然数）の部分情報から復元する秘密分散復元システムであって、数値変換された前記秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から前記点Ｌを前記楕円曲線上の点として復元し、前記楕円曲線の元として前記秘密情報を取り出す復元部と、を備えていることを特徴とする。
【００２３】
また、本発明に係る秘密情報分散復元システムは、前記秘密情報分散復元システムであって、前記分散演算部が、定数項を有しない（ｋ−１）次の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、を備え、前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、を備えていることを特徴とする。
【発明の効果】
【００２４】
本発明によれば、楕円曲線暗号の通信路を介した秘密情報の分散及び復元にかかる演算時間を大幅に短縮させることができる。
【発明を実施するための最良の形態】
【００２５】
本発明に係る一実施形態について、図１及び図２を参照して説明する。
本実施形態に係る秘密情報分散復元システム１は、図１に示すように、秘密情報ｓをｎ個の部分情報に分散させる部分情報生成サーバー（秘密情報分散装置）２と、分散された部分情報のうちのｋ個から秘密情報ｓを復元する（ｎ−１）個の携帯端末装置（秘密情報復元装置）３Ａ及び１つのセキュアサーバー（秘密情報復元装置）３Ｂと、を備えている。
【００２６】
この秘密情報分散復元システム１は、公開情報として上述と同様、有限体Ｆｐ＾２（ｐは素数）上の楕円曲線Ｅ（Ｆｐ＾２）：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ（ただし、ｑを素数とするとき、この楕円曲線の位数は＃Ｅ（Ｆｐ＾２）＝ｑ）、Ｇ∈Ｅ（Ｆｐ＾２）とする通信路Ｗを介して情報の送受信を行う。このとき、∀α∈Ｅ（Ｆｐ＾２）に対して、∃ｔ∈Ｚ／ｑＺ（Ｚは自然数の集合）となる（α＝ｔ＊Ｇが成立）。
【００２７】
部分情報生成サーバー２は、通信路Ｗにのせるために公知の方法にて数値変換された秘密情報ｓを楕円曲線上の点Ｌとする座標処理演算部５と、点Ｌを基に秘密情報ｓを楕円曲線上のｎ個の点に部分情報として分散させる分散演算部６と、を備えている。この部分情報生成サーバー２は、例えば、図示しないマイクロプロセッサ、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ハードディスク、キーボード、ディスプレィを備えている。ハードディスクには、コンピュータプログラムが記憶されている。また、上述の公開情報はＲＯＭに記憶される。
【００２８】
座標処理演算部５は、秘密情報ｓが楕円曲線Ｅ（Ｆｐ＾２）上の所定の点のＸ座標となるように処理を行う。すなわち、楕円曲線Ｅ（Ｆｐ＾２）上でＧをｔ回（ｔは自然数）加算したものがＬとなるようにする（Ｌ＝ｔ＊Ｇ）。
【００２９】
分散演算部６は、分散用多項式ｆ（ｘ）を生成する分散用多項式生成部６Ａと、分散用多項式ｆ（ｘ）に基づき秘密情報ｓを分散させる情報分散部６Ｂと、をさらに備えている。
【００３０】
分散用多項式生成部６Ａは、式（１）に示す定数項を有しない（ｋ−１）次の分散用多項式ｆ（ｘ）を生成する。
【００３１】
【数１】
【００３２】
ここで、ａ１，・・・ａｎ∈Ｚ／ｑＺとする。
【００３３】
情報分散部６Ｂは、ｘ＝１〜ｎに対してｆ（１）〜ｆ（ｎ）を算出し、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する。ここでの“＋”は、楕円曲線上での加算を示す。得られた部分情報Ｖｉは、通信路Ｗを介して部分情報の各分散管理者に１つずつ送信される。
【００３４】
座標処理演算部５及び分散演算部６は、図示しないハードディスクに記憶されている前記コンピュータプログラムが図示しないマイクロプロセッサにより実行されて、その機能を達成する。
【００３５】
一方、携帯端末装置３Ａ及びセキュアサーバー３Ｂは、部分情報生成サーバー２によってｎ個に分散された部分情報のうちのｋ個から楕円曲線Ｅ（Ｆｐ＾２）上の点として点Ｌを復元して秘密情報ｓを取り出す復元部７をそれぞれ備えている。この携帯端末装置３Ａ及びセキュアサーバー３Ｂも、例えば、図示しないマイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスク、キーボード、ディスプレィを備えている。そして、ハードディスクには、コンピュータプログラムが記憶されている。また、上述の公開情報はＲＯＭに記憶される。
【００３６】
復元部７は、部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の補間係数を算出する補間係数算出部７Ａと、秘密情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上の点ＬのＸ座標として復元する情報復元部７Ｂと、を備えている。
【００３７】
補間係数算出部７Ａは、集まったｋ個の部分情報Ｖｉｊ（ｊ＝１〜ｋ）から式（２）に示す多項式補間の係数の計算を行う。
【００３８】
【数２】
【００３９】
情報復元部７Ｂは、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係が成立することを利用して、式（２）を用いて式（３）を算出し、楕円曲線Ｅ（Ｆｐ＾２）上の点ＬのＸ座標として秘密情報ｓを復元する。
【００４０】
【数３】
【００４１】
補間係数算出部７Ａ及び情報復元部７Ｂは、図示しないハードディスクに記憶されている前記コンピュータプログラムが図示しないマイクロプロセッサにより実行されて、その機能を達成する。
【００４２】
次に、秘密情報分散方法及び秘密情報復元方法について、図２を用いながら、秘密情報として鍵情報ｓをｎ人の分散管理者で共有する場合を例として説明する。
この方法は、数値変換された秘密情報である鍵情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上の点Ｌとする座標処理ステップ（Ｓ０１）と、点Ｌを基に鍵情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上のｎ個の点に分散鍵として分散させる分散ステップ（Ｓ０２）と、ｎ個に分散された分散鍵のうちのｋ個から楕円曲線Ｅ（Ｆｐ＾２）上の点として点Ｌを復元して鍵情報ｓを取り出す復元ステップ（Ｓ０３）と、を備えている。
【００４３】
秘密情報分散方法の分散ステップ（Ｓ０２）は、さらに分散用多項式生成ステップ（Ｓ２１）と、情報分散ステップ（Ｓ２２）と、を備えている。また、秘密情報復元方法の復元ステップ（Ｓ０３）は、さらに補間係数算出ステップ（Ｓ３１）と、情報復元ステップ（Ｓ３２）と、を備えている。
【００４４】
座標処理ステップ（Ｓ０１）は、部分情報生成サーバー２の座標処理演算部５にて、鍵情報ｓが楕円曲線Ｅ（Ｆｐ＾２）上の所定の点のＸ座標となるように処理を行う。
【００４５】
分散用多項式生成ステップ（Ｓ２１）は、部分情報生成サーバー２の分散用多項式生成部６Ａにて、式（１）に示す多項式ｆ（ｘ）を生成する。また、情報分散ステップ（Ｓ２２）は、部分情報生成サーバー２の情報分散部６Ｂにてｆ（１）〜ｆ（ｎ）を計算してから、分散鍵Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する。
【００４６】
そして、通信路Ｗを介して各分散管理者が有する携帯端末装置３Ａ又はセキュアサーバー３Ｂにそれぞれ分散鍵Ｖｉを１つずつ送信する。この際、部分情報生成サーバー２と携帯端末装置３Ａ又はセキュアサーバー３Ｂとをつなぐ通信路Ｗ上では分散鍵Ｖｉが１つずつ送受信される。この段階で分散鍵が盗まれても鍵情報ｓが復元されることはない。
【００４７】
復元ステップ（Ｓ０３）では、例えば、ある分散管理者におけるセキュアサーバー３Ｂにて鍵情報ｓを復元する場合、（ｋ−１）個の携帯端末装置３Ａのそれぞれが有する分散鍵をセキュアサーバー３Ｂ宛に１つずつ送信する。この場合、各携帯端末装置３Ａとセキュアサーバー３Ｂとをつなぐ通信路Ｗ上では１つの分散鍵Ｖｉｊ（ｊ＝１〜ｋの何れか）のみが送受信される。この段階で分散鍵が盗まれても鍵情報ｓが復元されることはない。
【００４８】
そして、補間係数算出ステップ（Ｓ３１）では、セキュアサーバー３Ｂの補間係数算出部７Ａにて、分散鍵Ｖｉｊから式（２）に示す多項式補間の係数の計算を行う。
【００４９】
情報復元ステップ（Ｓ３２）では、セキュアサーバー３Ｂの情報復元部７Ｂにて、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、式（３）に示す［ｆ１（０）］＊Ｇ（ｘ＝０）を算出する。そして、楕円曲線Ｅ（Ｆｐ＾２）上の点ＬのＸ座標として鍵情報ｓを復元する。
【００５０】
この秘密情報分散復元システム１、部分情報生成サーバー２、秘密情報分散プログラム、秘密情報分散方法によれば、秘密情報ｓを楕円曲線Ｅ（Ｆｐ＾２）上の点Ｌとしてから楕円曲線Ｅ（Ｆｐ＾２）上に分散させる。そのため、分散させる情報を１／ｎに軽量化させることができるだけでなく、分散させる際にＦｐ＾２上での平方根を求めるアルゴリズムをｎ回から１回に削減することができる。
【００５１】
また、この秘密情報分散復元システム１、携帯端末装置３Ａ及びセキュアサーバー３Ｂ、秘密情報復元プログラム、秘密情報復元方法によれば、上述のようにして分散させた部分情報を集めて復元する。この際、Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ＝［ｆ１（ｉ）］＊Ｇが成立するので、ｆ１（０）（ｘ＝０）を復元すればよく、楕円曲線上の離散対数問題を解くことなく、秘密情報ｓを復元することができる。
【００５２】
したがって、分散及び復元過程における演算時間を大幅に短縮させることができ、携帯電話機のように容量が比較的小さく制限される携帯端末装置においても秘密分散共有管理を行うことができる。
【００５３】
なお、本発明の技術範囲は上記実施の形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲において種々の変更を加えることが可能である。
例えば、上記実施形態では鍵共有の場合について説明しているが、これに限らず、合意認証といった、役職レベルに応じた鍵の分散管理の場合にも適用できる。また、電子チケットを所有するための権利情報をチケットサーバー等にて分散させ、アプリケーションサーバー等で電子チケットを復元させる場合にも適用できる。
【実施例】
【００５４】
上述の合意認証、電子チケットの場合、本発明によって従来よりも数十倍の速度で秘密情報を分散及び復元することができた。
【図面の簡単な説明】
【００５５】
【図１】本発明の一実施形態に係る秘密情報分散復元システムを示す概要図である。
【図２】本発明の一実施形態に係る秘密情報分散方法及び秘密情報復元方法を示す全体フロー図である。
【符号の説明】
【００５６】
１ 秘密情報分散復元システム
２ 部分情報生成サーバー（秘密情報分散装置）
３Ａ 携帯端末装置（秘密情報復元装置）
３Ｂ セキュアサーバー（秘密情報復元装置）
５ 座標処理演算部
６ 分散演算部
６Ａ 分散用多項式生成部
６Ｂ 情報分散部
７ 復元部
７Ａ 補間係数算出部
７Ｂ 情報復元部
【特許請求の範囲】
【請求項１】
数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、
前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、
を備えていることを特徴とする秘密情報分散装置。
【請求項２】
前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、
を備えていることを特徴とする請求項１に記載の秘密情報分散装置。
【請求項３】
コンピュータを請求項１又は２に記載の秘密情報分散装置として機能させることを特徴とする秘密情報分散プログラム。
【請求項４】
数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理ステップと、
前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散ステップと、
を備えていることを特徴とする秘密情報分散方法。
【請求項５】
前記分散ステップが、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成ステップと、
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散ステップと、
を備えていることを特徴とする請求項４に記載の秘密情報分散方法。
【請求項６】
請求項１又は２に記載の秘密情報分散装置によって前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から、前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元部を備えていることを特徴とする秘密情報復元装置。
【請求項７】
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）で表示されることから、前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、
前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、
［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、
を備えていることを特徴とする請求項６に記載の秘密情報復元装置。
【請求項８】
コンピュータを請求項６又は７に記載の秘密情報復元装置として機能させることを特徴とする秘密情報復元プログラム。
【請求項９】
請求項４又は５に記載の秘密情報分散方法によって前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から、前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元ステップを備えていることを特徴とする秘密情報復元方法。
【請求項１０】
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散ステップにて、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、
前記復元ステップが、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出ステップと、
［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元ステップと、
を備えていることを特徴とする請求項９に記載の秘密情報復元方法。
【請求項１１】
ｎ個に分散された秘密情報をｋ個（ｋは１＜ｋ＜ｎとなる自然数）の部分情報から復元する秘密分散復元システムであって、
数値変換された前記秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、
前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、
前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から前記点Ｌを前記楕円曲線上の点として復元し、前記楕円曲線の元として前記秘密情報を取り出す復元部と、
を備えていることを特徴とする秘密情報分散復元システム。
【請求項１２】
前記分散演算部が、定数項を有しない（ｋ−１）次の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、
を備え、
前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、
［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、
を備えていることを特徴とする請求項１１に記載の秘密情報分散復元システム。
【請求項１】
数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、
前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、
を備えていることを特徴とする秘密情報分散装置。
【請求項２】
前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、
を備えていることを特徴とする請求項１に記載の秘密情報分散装置。
【請求項３】
コンピュータを請求項１又は２に記載の秘密情報分散装置として機能させることを特徴とする秘密情報分散プログラム。
【請求項４】
数値変換された秘密情報を楕円曲線上の点Ｌとする座標処理ステップと、
前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散ステップと、
を備えていることを特徴とする秘密情報分散方法。
【請求項５】
前記分散ステップが、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成する分散用多項式生成ステップと、
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散ステップと、
を備えていることを特徴とする請求項４に記載の秘密情報分散方法。
【請求項６】
請求項１又は２に記載の秘密情報分散装置によって前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から、前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元部を備えていることを特徴とする秘密情報復元装置。
【請求項７】
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）で表示されることから、前記分散演算部が、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、
前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、
［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、
を備えていることを特徴とする請求項６に記載の秘密情報復元装置。
【請求項８】
コンピュータを請求項６又は７に記載の秘密情報復元装置として機能させることを特徴とする秘密情報復元プログラム。
【請求項９】
請求項４又は５に記載の秘密情報分散方法によって前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から、前記点Ｌを前記楕円曲線上の点として復元して前記秘密情報を取り出す復元ステップを備えていることを特徴とする秘密情報復元方法。
【請求項１０】
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散ステップにて、定数項を有しない（ｋ−１）次（ｋは１＜ｋ＜ｎとなる自然数）の分散用多項式ｆ（ｘ）を生成するとともに、ｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成したとき、
前記復元ステップが、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出ステップと、
［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元ステップと、
を備えていることを特徴とする請求項９に記載の秘密情報復元方法。
【請求項１１】
ｎ個に分散された秘密情報をｋ個（ｋは１＜ｋ＜ｎとなる自然数）の部分情報から復元する秘密分散復元システムであって、
数値変換された前記秘密情報を楕円曲線上の点Ｌとする座標処理演算部と、
前記点Ｌを基に前記秘密情報を前記楕円曲線上のｎ個の点に部分情報として分散させる分散演算部と、
前記ｎ個に分散された前記部分情報のうちのｋ個（ｋは１＜ｋ＜ｎとなる自然数）から前記点Ｌを前記楕円曲線上の点として復元し、前記楕円曲線の元として前記秘密情報を取り出す復元部と、
を備えていることを特徴とする秘密情報分散復元システム。
【請求項１２】
前記分散演算部が、定数項を有しない（ｋ−１）次の分散用多項式ｆ（ｘ）を生成する分散用多項式生成部と、
前記点Ｌが前記楕円曲線上の所定の点Ｇに対してＬ＝ｔ＊Ｇ（ｔは自然数、＊は楕円曲線上における倍数演算）表示されることから、前記分散用多項式ｆ（ｘ）に対して前記楕円曲線上での加乗算によりｎ個の部分情報Ｖｉ＝Ｌ＋［ｆ（ｉ）］＊Ｇ＝［ｔ＋ｆ（ｉ）］＊Ｇ（ｉ＝１からｎの何れか）を生成する情報分散部と、
を備え、
前記復元部が、前記部分情報Ｖｉから、ｆ１（ｘ）＝ｔ＋ｆ（ｘ）からなる復元用多項式ｆ１（ｘ）の係数を算出する補間係数算出部と、
［ｆ１（０）］＊Ｇ（ｘ＝０）を算出し、［ｆ１（０）］＊Ｇ＝［ｔ＋ｆ（０）］＊Ｇ＝Ｌの関係から、前記秘密情報を前記楕円曲線上の点ＬのＸ座標として復元する情報復元部と、
を備えていることを特徴とする請求項１１に記載の秘密情報分散復元システム。
【図１】
【図２】
【図２】
【公開番号】特開２０１０−９６７８７（Ｐ２０１０−９６７８７Ａ）
【公開日】平成２２年４月３０日（２０１０．４．３０）
【国際特許分類】
【出願番号】特願２００８−２６４７８０（Ｐ２００８−２６４７８０）
【出願日】平成２０年１０月１４日（２００８．１０．１４）
【出願人】（３０５０２７４０１）公立大学法人首都大学東京 (385)
【Ｆターム（参考）】
【公開日】平成２２年４月３０日（２０１０．４．３０）
【国際特許分類】
【出願日】平成２０年１０月１４日（２００８．１０．１４）
【出願人】（３０５０２７４０１）公立大学法人首都大学東京 (385)
【Ｆターム（参考）】
[ Back to top ]