リスト生成装置、リスト生成方法およびリスト生成プログラム
【課題】スカラ倍算の計算コストを抑え、リストを生成する処理を高速化すること。
【解決手段】リスト生成装置１００ａでは、スカラ値生成部１４０が、ランダム関数部１４１から今まで出力された値の合計値を求め、合計値に基づいて楕円曲線上の点に対応する生成元を冪乗する。そして、スカラ倍算計算部１５０は、スカラ値生成部１４０の算出結果と、固定点テーブルとを基にして、初期値Ｇ０をスカラ倍算することでＧｉ＋１を求める。すなわち、スカラ倍算を行う楕円曲線上の点はＧ０で固定されるため、リスト生成装置１００ａは、スカラ倍算を固定点テーブルの各点の加算によって求めることができ、スカラ倍算にかかる計算コストを削減することができる。
【解決手段】リスト生成装置１００ａでは、スカラ値生成部１４０が、ランダム関数部１４１から今まで出力された値の合計値を求め、合計値に基づいて楕円曲線上の点に対応する生成元を冪乗する。そして、スカラ倍算計算部１５０は、スカラ値生成部１４０の算出結果と、固定点テーブルとを基にして、初期値Ｇ０をスカラ倍算することでＧｉ＋１を求める。すなわち、スカラ倍算を行う楕円曲線上の点はＧ０で固定されるため、リスト生成装置１００ａは、スカラ倍算を固定点テーブルの各点の加算によって求めることができ、スカラ倍算にかかる計算コストを削減することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リスト生成装置、リスト生成方法およびリスト生成プログラムに関する。
【背景技術】
【０００２】
近年、ネットショッピングやネットバンキングが普及している。ネットショッピングやネットバンキングにおいて通信を行う場合には、情報漏洩などを防止するために、共通鍵暗号などの暗号技術が利用されている。
【０００３】
公開鍵暗号は、対になる２つの鍵を使ってデータの暗号化、復号をおこなう方式である。すなわち、送信者は受信者によって公開されている公開鍵でメッセージを暗号化して送信する。これに対して、受信者は、暗号化されたメッセージを秘密鍵で復号する。公開鍵は、メッセージを暗号化するための鍵であり、秘密鍵は、公開鍵により暗号化された情報を復号するための鍵である。公開鍵で暗号化された情報は、対の秘密鍵でのみ復号することができる。
【０００４】
この公開鍵暗号は、公開鍵を公開しても安全性を確保できるように、数学的に難しいとされている問題に基づいて設計されている。例えば、公開鍵暗号は、離散対数問題に基づいて設計される。この離散対数問題は、ｐ個の元からなる可換群の生成元Ｇ、α∈Ｚｐとした場合に、Ｇ、Ｇαからαを求めるというものである。
【０００５】
また、上記離散対数問題に補助情報ｄを加え、Ｇ、Ｇα、
【数１】
からαを求めるという補助情報付きの離散対数問題がある。この補助情報付きの離散対数問題を解くアルゴリズムとして、Cheonらの論文では、決定的アルゴリズムと確率的アルゴリズムとが示されている。ｄは、位数ｒから１を減算した値の約数に対応する。
【０００６】
このうち決定的アルゴリズムは、計算量が膨大であるため、この決定的アルゴリズムを用いて離散対数問題を解くことは現実的に難しい。このため、Cheonらは、「Pollard's kangaroo algorithm」を適用することで計算量を削減した確率的アルゴリズムを提案している。この確率的アルゴリズムは、上記離散対数問題に対してだけではなく、楕円曲線上の離散対数問題にも適用されている。楕円曲線上の離散対数問題を楕円曲線離散対数問題と表記する。楕円曲線離散対数問題は、楕円曲線上の３点Ｇ、Ｇ１＝αＧ、Ｇｄ＝αｄＧから未知数αを求める問題である。
【０００７】
この確率的アルゴリズムでは、Ｇ、Ｇｄから検索したｋ１と、Ｇ、Ｇ１から検索したｋ２とを用いて未知数αを求める。ここで、確率的アルゴリズムが、ｋ１、ｋ２を求める場合には、楕円曲線上の特徴点（distinguished point）を収集したリストが利用される。確率的アルゴリズムにおいてリストを生成する場合には、ランダムウォーク関数に楕円曲線上の点を順次代入した値に基づいて、楕円曲線上の点を順次スカラ倍算することで特徴点を求める。
【０００８】
なお、ランダムウォーク関数を利用してリストを作成するためには、膨大な繰り返し処理が必要となる。このため従来では、リストを作成する場合の初期点を多数設定することで、複数のコンピュータで並列処理を行い、リストを作成する場合の処理負荷を分散させている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平１１−２８８２１５号公報
【特許文献２】特開２００３−２８８０１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
コンピュータがリストを生成する場合には、楕円曲線上の点に対してスカラ倍算を実行する必要があり、このスカラ倍算の計算コストが非常に大きいものとなる。このため、スカラ倍算の計算コストを抑え、リストを生成する処理を高速化することが求められる。
【００１１】
開示の技術は、上記に鑑みてなされたものであって、スカラ倍算の計算コストを抑え、リストを生成する処理を高速化することができるリスト生成装置、リスト生成方法およびリスト生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本願の開示するリスト生成装置は、楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルと、前記楕円曲線上の点に対してランダムウォーク関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する疑似ランダム関数適用部と、前記記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成部と、前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出部と、前記点算出部が算出した各点を収集し、リストを生成するリスト生成部とを備えたことを要件とする。
【発明の効果】
【００１３】
本願の開示するリスト生成装置の一つの態様によれば、スカラ倍算の計算コストを抑え、リストを生成する処理を高速化することという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】図１は、Cheonらの確率的アルゴリズムの処理手順を示すフローチャートである。
【図２】図２は、従来の衝突検出処理の処理手順を示すフローチャートである。
【図３】図３は、従来のリスト生成処理の処理手順を示すフローチャートである。
【図４】図４は、確率的アルゴリズムを並列処理する場合の処理手順を示すフローチャート（１）である。
【図５】図５は、確率的アルゴリズムを並列処理する場合の処理手順を示すフローチャート（２）である。
【図６】図６は、従来のリスト生成装置の構成を示す図である。
【図７】図７は、従来のリスト生成装置の処理手順を示すフローチャートである。
【図８】図８は、従来の固定点テーブルのデータ構造の一例を示す図である。
【図９】図９は、本実施例にかかるシステムの構成を示す図である。
【図１０】図１０は、リスト生成装置の構成を示す図である。
【図１１】図１１は、固定点テーブルのデータ構造の一例を示す図である。
【図１２】図１２は、各スカラ倍算計算部が算出するＧｉ＋１が同じことを説明するための図である。
【図１３】図１３は、本実施例にかかるリスト生成装置の処理手順を示すフローチャートである。
【図１４】図１４は、本実施例にかかるシステムの処理手順を示すフローチャート（１）である。
【図１５】図１５は、本実施例にかかるシステムの処理手順を示すフローチャート（２）である。
【図１６】図１６は、固定点テーブルを生成する処理手順を示すフローチャートである。
【図１７】図１７は、リスト生成プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１５】
まず、本願の開示する暗号鍵解読装置における技術を説明するうえで前提となる技術を図面を利用して説明する。
【００１６】
まず、補助情報付きの楕円曲線離散対数問題を解くCheonらの確率的アルゴリズムの処理手順について説明する。図１は、Cheonらの確率的アルゴリズムの処理手順を示すフローチャートである。
【００１７】
図１に示すように、確率的アルゴリズムでは、Ｅ、Ｇ、Ｇ１、Ｇｄ、ｌｅｎを取得する（ステップＳ１０）。ここで、Ｅは、楕円曲線の各種パラメータである。Ｇ、Ｇ１、Ｇｄは、楕円曲線上の点であり、Ｇ１＝αＧ、Ｇｄ＝αｄＧとする。ｌｅｎは、リストを生成する場合に利用する閾値である。ｌｅｎは、楕円曲線の点Ｇの位数ｒの４乗根程度の値が設定される。
【００１８】
確率的アルゴリズムでは、Ｚｒの生成元ζを生成し（ステップＳ１１）、ｓおよびｓ’を設定する（ステップＳ１２）。ステップＳ１２において、ｓは「（ｒ−１）／ｄ」により算出される。また、ｓ’はｄに対応する。
【００１９】
確率的アルゴリズムでは、Ｅ、Ｇ、Ｇｄ、ｓ、ｓ’、ζ、ｌｅｎを基にして、衝突検出処理を実行することでｋ１を得る（ステップＳ１３）。また、確率的アルゴリズムでは、Ｅ、Ｇ、Ｇ１、ｓ、ｓ’、ζ、ｌｅｎを基にして、衝突検出処理を実行することでｋ２を得る（ステップＳ１４）。
【００２０】
確率的アルゴリズムでは、ｋ１、ｋ２を基にしてαを算出し（ステップＳ１５）、αを出力する（ステップＳ１６）。ステップＳ１５において、αは、「
【数２】
」により算出される。
【００２１】
次に、図１のステップＳ１３およびステップＳ１４に示した衝突検出処理の処理手順について説明する。図２は、従来の衝突検出処理の処理手順を示すフローチャートである。図２のフローチャートでは、Ｇ０、Ｇ’０を用いて説明する。図１の確率的アルゴリズムにおいて、Ｅ、Ｇ、Ｇｄ、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、Ｇ０は、Ｇに対応し、Ｇ’０はＧｄに対応する。これに対して、Ｅ、Ｇ、Ｇ１、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、Ｇ０は、Ｇに対応し、Ｇ’０はＧ１に対応する。
【００２２】
図２に示すように、衝突検出処理では、Ｅ、Ｇ０、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ１を得る（ステップＳ２０）。衝突検出処理では、Ｅ、Ｇ’０、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ２を得る（ステップＳ２１）。
【００２３】
衝突検出処理では、ｌｉｓｔ１とｌｉｓｔ２とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ２２）。衝突検出処理では、インデックスｖ、ｕを基にして、ｋを算出し（ステップＳ２３）、ｋを出力する（ステップＳ２４）。ステップＳ２３においてｋは、「
【数３】
」によって算出される。
【００２４】
なお、上記ｋを算出する式において、ｆｓは疑似ランダム関数である。たとえばｆｓは、楕円曲線上の点Ｇ＝（ｘ、ｙ）が与えられた時に、ｘ ｍｏｄ ｓを返す関数である。また、ランダムウォーク関数Ｆｓは、楕円曲線の点Ｇを他の楕円曲線上の点に写像する関数で、「
【数４】
」によって定義される。
【００２５】
例えば、Ｅ、Ｇ、Ｇｄ、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、上記ｋを算出する式により、ｋ１が求められる。これに対して、Ｅ、Ｇ、Ｇ１、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、上記ｋを算出する式により、ｋ２が求められる。
【００２６】
次に、図２のステップＳ２０およびステップＳ２１に示したリスト生成処理の処理手順について説明する。図３は、従来のリスト生成処理の処理手順を示すフローチャートである。図３に示すように、リスト生成処理では、ｉの値を初期値に設定し（ステップＳ３０）、Ｇｉ＋１の値を算出する（ステップＳ３１）。ステップＳ３１において、Ｇｉ＋１は、「
【数５】
」によって算出される。
【００２７】
リスト生成処理では、Ｇｉ＋１の値が特徴点（distinguished point）であるか否かを判定する（ステップＳ３２）。ステップＳ３２において、リスト生成処理では、Ｇｉ＋１の値の一部が所定の値となっている場合は、楕円曲線の点Ｇｉ＋１の値が特徴点であると判定する。
【００２８】
リスト生成処理では、Ｇｉ＋１の値が特徴点ではないと判定した場合には（ステップＳ３２，Ｎｏ）、ステップＳ３４に移行する。一方、リスト生成処理では、Ｇｉ＋１の値が特徴点であると判定した場合には（ステップＳ３２，Ｙｅｓ）、ｌｉｓｔにＧｉ＋１の値を登録する（ステップＳ３３）。
【００２９】
リスト生成処理では、ｉの値に１を加算し（ステップＳ３４）、ｉの値がｌｅｎよりも大きいか否かを判定する（ステップＳ３５）。リスト生成処理では、ｉの値がｌｅｎ以下の場合には（ステップＳ３５，Ｎｏ）、ステップＳ３１に移行する。一方、リスト生成処理では、ｉの値がｌｅｎよりも大きい場合には（ステップＳ３５，Ｙｅｓ）、処理を終了する。
【００３０】
ステップＳ３３において、リスト生成処理では、インデックスｉと、Ｇｉ＋１の値とを対応付けて、ｌｉｓｔに登録するものとする。また、Ｅ、Ｇ０、ζｓ’、ｌｅｎを基にしてリスト生成処理を実行する場合には、上記ｌｉｓｔは、ｌｉｓｔ１に対応する。この場合、ｌｉｓｔのインデックスｉは、ｌｉｓｔ１のインデックスｖに対応する。
【００３１】
また、Ｅ、Ｇ’０、ζｓ’、ｌｅｎを基にしてリスト生成処理を実行する場合には、上記ｌｉｓｔは、ｌｉｓｔ２に対応する。この場合、ｌｉｓｔのインデックスｉは、ｌｉｓｔ２のインデックスｕに対応する。
【００３２】
現在の楕円曲線離散対数問題では、安全性を確保するために、楕円曲線の点の位数ｒは２１６０が利用されている。したがって、上記確率的アルゴリズムを実行する場合には、ｌｅｎは２４０程度の値が指定される。ｌｅｎの値が２４０に指定されると、図３に示したリスト生成処理を、２４０回繰り返し実行する必要があり、計算量が膨大なものとなる。
【００３３】
図１〜図３に示したアルゴリズムは、複数のコンピュータ０〜ｎによって並列処理することで高速化を図ることができる。例えば、複数のコンピュータ０〜ｎは、ネットワークを介して相互に接続されており、協働して並列処理を実行する。この並列処理では、複数のコンピュータ１〜ｎがそれぞれｌｉｓｔを生成し、コンピュータ０が各ｌｉｓｔを収集する。コンピュータ０は、各ｌｉｓｔを利用して、未知数αを算出する。
【００３４】
図４および図５は、確率的アルゴリズムを並列処理する場合の処理手順を示すフローチャートである。なお、図４のステップＳ４０〜Ｓ４３の処理、図５のステップＳ５０〜Ｓ５２、Ｓ５９〜Ｓ６２の処理は、コンピュータ０が実行する処理とする。図４のステップＳ４４の処理は、コンピュータ１〜ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図４のステップＳ４７の処理は、コンピュータｎ／４〜ｎ／２がそれぞれｌｉｓｔを生成する処理とする。図５のステップＳ５３の処理は、コンピュータｎ／２〜３ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図５のステップＳ５６の処理は、コンピュータ３ｎ／４〜ｎがそれぞれｌｉｓｔを生成する処理とする。
【００３５】
図４に示すように、並列処理では、Ｅ、Ｇ、Ｇ１、Ｇｄ、ｌｅｎを取得し（ステップＳ４０）、生成元ζを生成する（ステップＳ４１）。また、並列処理では、ｓおよびｓ’を算出し（ステップＳ４２）、ｉの値を初期値に設定する（ステップＳ４３）。
【００３６】
並列処理では、Ｅ、Ｇｉ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ１を得る（ステップＳ４４）。並列処理では、ｉの値に１を加算し（ステップＳ４５）、ｉの値がｎ／４よりも大きいか否かを判定する（ステップＳ４６）。ｉの値がｎ／４以下の場合には（ステップＳ４６，Ｎｏ）、ステップＳ４４に移行する。
【００３７】
一方、ｉの値がｎ／４よりも大きい場合には（ステップＳ４６，Ｙｅｓ）、並列処理では、Ｅ、Ｇｉｄ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ２を得る（ステップＳ４７）。並列処理では、ｉの値に１を加算し（ステップＳ４８）、ｉの値がｎ／２よりも大きいか否かを判定する（ステップＳ４９）。ｉの値がｎ／２以下の場合には（ステップＳ４９，Ｎｏ）、ステップＳ４７に移行する。
【００３８】
一方、ｉの値がｎ／２よりも大きい場合には（ステップＳ４９，Ｙｅｓ）、並列処理では、ｌｉｓｔ１とｌｉｓｔ２とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ５０）。
【００３９】
並列処理では、ｋ１を算出する（ステップＳ５１）。ｋ１は、「
【数３】
」によって算出される。並列処理では、ｓおよびｓ’を設定する（ステップＳ５２）。ｓはｄに対応する。ｓ’は「（ｒ−１）／ｄ」により算出される。
【００４０】
並列処理では、Ｅ、Ｇｉ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ３を得る（ステップＳ５３）。並列処理では、ｉの値に１を加算し（ステップＳ５４）、ｉの値が３ｎ／４よりも大きいか否かを判定する（ステップＳ５５）。ｉの値が３ｎ／４以下の場合には（ステップＳ５５，Ｎｏ）、ステップＳ５３に移行する。
【００４１】
一方、ｉの値が３ｎ／４よりも大きい場合には（ステップＳ５５，Ｙｅｓ）、並列処理では、Ｅ、Ｇ１ｉ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ４を得る（ステップＳ５６）。並列処理では、ｉの値に１を加算し（ステップＳ５７）、ｉの値がｎより大きいか否かを判定する（ステップＳ５８）。ｉの値がｎ以下の場合には（ステップＳ５８，Ｎｏ）、ステップＳ５６に移行する。
【００４２】
一方、ｉの値がｎよりも大きい場合には（ステップＳ５８，Ｙｅｓ）、並列処理では、ｌｉｓｔ３とｌｉｓｔ４とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ５９）。
【００４３】
並列処理では、ｋ２を算出する（ステップＳ６０）。ｋ２は「
【数３】
」によって算出される。並列処理では、ｋ１およびｋ２を基にしてαを算出し（ステップＳ６１）、αを出力する（ステップＳ６２）。
【００４４】
図４および図５に示した処理手順によってコンピュータ０〜ｎが並列処理を実行することで、リストを生成する処理負荷を分散させることができる。
【００４５】
次に、図３に示したリスト生成処理を実行するリスト生成装置の構成について説明する。図６は、従来のリスト生成装置の構成を示す図である。図６に示すように、このリスト生成装置は、入力部１１、繰り返し判定部１２、記憶部１３、スカラ値生成部１４、スカラ倍算計算部１５、特徴点判定部１６、点出力部１７を有する。
【００４６】
入力部１１は、リストを作成するためのパラメータを受け付け、受け付けたパラメータを繰り返し判定部１２、スカラ値生成部１４、スカラ倍算計算部１５に出力する処理部である。入力部１１は、キーボードなどの入力装置からパラメータを受け付けても良いし、他の装置と情報通信を行ってパラメータを取得しても良い。
【００４７】
パラメータには、Ｅ、Ｇ０、ζｓ’、ｌｅｎが含まれる。入力部１１は、パラメータのうち、Ｅ、Ｇ０をスカラ倍算計算部１５に出力し、Ｅ、ζｓ’をスカラ値生成部１４に出力する。また、入力部１１は、ｌｅｎを繰り返し判定部１２に出力する。
【００４８】
繰り返し判定部１２は、ＧｉからＧｉ＋１を計算する回数をカウントする処理部である。繰り返し判定部１２は、ＧｉからＧｉ＋１が計算された回数をどのようにカウントしてもよい。例えば、繰り返し判定部１２は、スカラ倍算計算部１５が、Ｇｉ＋１の計算結果を出力する度に、計算回数をカウントする。
【００４９】
繰り返し判定部１２は、カウントした計算回数が、ｌｅｎを超えた場合に、リスト生成処理を終了すると判定する。例えば、繰り返し判定部１２は、リスト生成処理を終了すると判定した場合には、スカラ値生成部１４およびスカラ倍算計算部１５を制御して、処理を終了させる。
【００５０】
記憶部１３は、スカラ倍算計算部１５の算出結果を記憶する記憶部である。
【００５１】
スカラ値生成部１４は、Ｇｉから
【数６】
を算出する処理部である。図６に示すように、スカラ値生成部１４は、ランダム関数部１４ａおよび冪乗余剰計算部１４ｂを有する。
【００５２】
ランダム関数部１４ａは、Ｇｉからｆｓ（Ｇｉ）を算出する処理部である。例えば、ｆｓは楕円曲線上の点Ｇ＝（ｘ、ｙ）が与えられた場合に、「ｘ ｍｏｄ ｓ」を返す関数である。ランダム関数部１４ａは、ｆｓ（Ｇｉ）を冪乗余剰計算部１４ｂに出力する。なお、ランダム関数部１４ａは、Ｇｉの初期値となるＧ０を、入力部１１から取得する。また、ランダム関数部１４ａは、初期値以外のＧｉの値を記憶部１３から取得する。
【００５３】
冪乗余剰計算部１４ｂは、ｆｓ（Ｇｉ）とζｓ’とを取得して、
【数６】
を算出する処理部である。冪乗余剰計算部１４ｂは、
【数６】
をスカラ倍算計算部１５に出力する。
【００５４】
スカラ倍算計算部１５は、Ｇｉと
【数６】
とを取得して、Ｇｉ＋１を計算する処理部である。スカラ倍算計算部１５は、Ｇｉ＋１を「
【数５】
」によって計算する。スカラ倍算計算部１５は、Ｇｉ＋１を記憶部１３に記憶する。また、スカラ倍算計算部１５は、Ｇｉ＋１を特徴点判定部１６に出力する。
【００５５】
特徴点判定部１６は、Ｇｉ＋１が特徴点であるか否かを判定する処理部である。例えば、特徴点判定部１６は、Ｇｉ＋１の値の一部が所定の値となっている場合に、Ｇｉ＋１を特徴点であると判定する。特徴点判定部１６は、特徴点と判定したＧｉ＋１を点出力部１７に出力する。
【００５６】
点出力部１７は、特徴点と判定されたＧｉ＋１をテーブルに登録することで、ｌｉｓｔを生成する処理部である。点出力部１７は、ｌｉｓｔの情報を外部装置に出力する。
【００５７】
次に、図６に示したリスト生成装置１０の処理手順について説明する。図７は、従来のリスト生成装置の処理手順を示すフローチャートである。図７に示すように、リスト生成装置１０は、ｉの値を初期値に設定し（ステップＳ７０）、ランダム関数にＧｉを入力し、入力結果ｆｓ（Ｇｉ）を得る（ステップＳ７１）。
【００５８】
リスト生成装置１０は、冪乗余剰計算を実行する（ステップＳ７２）。冪乗余剰計算を実行することで、
【数６】
が得られる。リスト生成装置１０は、スカラ倍算計算を実行し、Ｇｉ＋１を得る（ステップＳ７３）。
【００５９】
リスト生成装置１０は、Ｇｉ＋１が特徴点であるか否かを判定する（ステップＳ７４）。リスト生成装置１０は、Ｇｉ＋１が特徴点ではない場合には（ステップＳ７４，Ｎｏ）、ステップＳ７６に移行する。
【００６０】
一方、リスト生成装置１０は、Ｇｉ＋１が特徴点の場合には（ステップＳ７４，Ｙｅｓ）、Ｇｉ＋１をｌｉｓｔに登録する（ステップＳ７５）。リスト生成装置１０は、ｉに１を加算し（ステップＳ７６）、ｉの値がｌｅｎよりも大きいか否かを判定する（ステップＳ７７）。リスト生成装置１０は、ｉの値がｌｅｎよりも大きい場合には（ステップＳ７７，Ｙｅｓ）、処理を終了する。一方、リスト生成装置１０は、ｉの値がｌｅｎ以下の場合には（ステップＳ７７，Ｎｏ）、ステップＳ７１に移行する。
【００６１】
リスト生成装置１０がｌｉｓｔを生成する場合に実行する各種計算のうち、図７のスカラ倍算計算が主要な計算となる。このため、スカラ倍算計算を高速化することができれば、リスト生成装置１０がｌｉｓｔを生成する処理を高速化することができる。
【００６２】
スカラ倍算計算を高速化する手法として、固定点テーブル法と呼ばれる技術が存在する。この固定点テーブル法は、予め複数のスカラ倍算計算を実行して、固定点テーブルに計算結果を格納しておく。そして、固定点テーブル法は、新たにスカラ倍算計算を実行する場合には、固定点テーブルに格納された計算結果を加算することで、スカラ倍算計算を実行する。
【００６３】
具体的に、固定点テーブル法について説明する。図８は、従来の固定点テーブルのデータ構造の一例を示す図である。図８に示すように、この固定点テーブルでは、１列目の数値を２倍、３倍した値が格納されている。例えば、１行目では、１Ｇ、２Ｇ、３Ｇが格納されている。２行目では、４Ｇ、８Ｇ、１２Ｇが格納されている。３行目では、１６Ｇ、３２Ｇ、４８Ｇが格納されている。４行目では、６４Ｇ、１２８Ｇ、１９２Ｇが格納されている。５行目では、２５６Ｇ、５１２Ｇ、７６８Ｇが格納されている。固定点テーブルの各Ｇは、全て同じ点である。
【００６４】
例えば、固定点テーブル法が、１０Ｇを算出する場合について説明する。この場合、固定点テーブル法では、図８の１行目２列目に格納された２Ｇと、２行目２列目に格納された８Ｇとを楕円加算することで、１０Ｇを算出する。１０とＧとをスカラ倍算するよりも、２Ｇと８Ｇとを楕円加算する方が、計算コストが少ない。このため、固定点テーブル法を用いてリスト生成処理を実行することができれば、ｌｉｓｔを生成する処理を高速化することができる。
【００６５】
しかし、固定点テーブル法を用いる場合には、スカラ倍算を行う楕円曲線上の点Ｇが常に同じ値であるという制限がある。例えば、固定点テーブル法では、１０Ｇ１を、２Ｇ１と８Ｇ１との楕円加算で算出することができるが、１０Ｇ２を、２Ｇ１と８Ｇ１との楕円加算で算出することができない。
【００６６】
図６に示したスカラ倍算計算部１５が、スカラ倍算計算を実行する場合には、楕円曲線上の点Ｇが毎回更新される。このため、従来のリスト生成装置１０は、固定点テーブル法を利用して、スカラ倍算計算を高速化することができなかった。
【実施例】
【００６７】
次に、本実施例について説明する。図９は、本実施例にかかるシステムの構成を示す図である。図９に示すように、このシステムは、リスト生成装置１００ａ〜１００ｎと、暗号鍵解析装置２００とを有する。リスト生成装置１００ａ〜１００ｎおよび暗号鍵解析装置２００は、ネットワーク５０を介して相互に接続される。
【００６８】
リスト生成装置１００ａ〜１００ｎは、ランダムウォーク関数と楕円曲線上の点Ｇとを基にして、リスト（ｌｉｓｔ）を生成する処理部である。リスト生成装置１００ａ〜１００ｎは、リストを暗号鍵解析装置２００に送信する。
【００６９】
暗号鍵解析装置２００は、リスト生成装置１００ａ〜１００ｎからリストを収集し、各リストを基にして、補助情報付き楕円曲線離散対数問題を解くことで、暗号鍵を解析する装置である。この暗号鍵解析装置２００は、上記のコンピュータ０に対応する装置であり、図１に示した処理手順によって、補助情報付き楕円曲線離散対数問題を解くものとする。
【００７０】
次に、リスト生成装置１００ａの構成について説明する。その他のリスト生成装置の構成は、リスト生成装置１００ａの構成と同様である。図１０は、リスト生成装置の構成を示す図である。図１０に示すように、このリスト生成装置１００ａは、入力部１１０、繰り返し判定部１２０、記憶部１３０、スカラ倍算計算部１５０、特徴点判定部１６０、点出力部１７０を有する。
【００７１】
入力部１１０は、リストを作成するためのパラメータを受け付け、受け付けたパラメータを繰り返し判定部１２０、スカラ値生成部１４０、スカラ倍算計算部１５０に出力する処理部である。入力部１１０は、キーボードなどの入力装置からパラメータを受け付けても良いし、他の装置と情報通信を行ってパラメータを取得しても良い。
【００７２】
パラメータには、Ｅ、Ｇ０、ζｓ’、ｌｅｎが含まれる。Ｅ、Ｇ０、ζｓ’、ｌｅｎに関する説明は、上記と同様である。入力部１１０は、パラメータのうち、Ｅ、Ｇ０をスカラ倍算計算部１５０に出力し、Ｅ、ζｓ’をスカラ値生成部１４０に出力する。また、入力部１１０は、ｌｅｎを繰り返し判定部１２０に出力する。
【００７３】
繰り返し判定部１２０は、ＧｉからＧｉ＋１を計算する回数をカウントする処理部である。繰り返し判定部１２０は、ＧｉからＧｉ＋１が計算された回数をどのようにカウントしてもよい。例えば、繰り返し判定部１２０は、スカラ倍算計算部１５０が、Ｇｉ＋１の計算結果を出力する度に、計算回数をカウントする。
【００７４】
繰り返し判定部１２０は、カウントした計算回数が、ｌｅｎを超えた場合に、リスト生成処理を終了すると判定する。例えば、繰り返し判定部１２０は、リスト生成処理を終了すると判定した場合には、スカラ値生成部１４０およびスカラ倍算計算部１５０を制御して、処理を終了させる。
【００７５】
記憶部１３０は、スカラ倍算計算部１５０の計算結果を記憶する記憶部である。
【００７６】
スカラ値生成部１４０は、Ｇｉから
【数７】
を算出する処理部である。図１０に示すように、スカラ値生成部１４０は、ランダム関数部１４１、加算部１４２、加算結果格納部１４３、冪乗余剰計算部１４４を有する。
【００７７】
ランダム関数部１４１は、Ｇｉからｆｓ（Ｇｉ）を算出する処理部である。例えば、ｆｓは楕円曲線上の点Ｇ＝（ｘ、ｙ）が与えられた場合に、「ｘ ｍｏｄ ｓ」を返す関数である。ランダム関数部１４１は、ｆｓ（Ｇｉ）を加算部１４２に出力する。なお、ランダム関数部１４１は、Ｇｉの初期値となるＧ０を、入力部１１０から取得する。また、ランダム関数部１４１は、初期値以外のＧｉの値を記憶部１３０から取得する。
【００７８】
加算部１４２は、ｆｓ（Ｇｉ）の値を順次加算し、加算結果ａｉを冪乗余剰計算部１４４に出力する処理部である。また、加算部１４２は、加算結果ａｉを加算結果格納部１４３に記憶する。加算結果格納部１４３は、加算結果ａｉを記憶する記憶部である。加算結果格納部１４３は、加算結果ａｉの初期値ａ０として０を記憶する。
【００７９】
具体的に、加算部１４２は、「ａｉ＝ａｉ−１＋ｆｓ（Ｇｉ）」によりａｉを算出する。すなわち、加算部１４２は、ランダム関数部１４１から取得したｆｓ（Ｇｉ）と、加算結果格納部１４３に記憶されたａｉ−１とを加算することで、ａｉを算出する。
【００８０】
冪乗余剰計算部１４４は、ａｉとζｓ’とを取得して、
【数７】
を算出する処理部である。冪乗余剰計算部１４４は、
【数７】
をスカラ倍算計算部１５に出力する。
【００８１】
スカラ倍算計算部１５０は、Ｇ０と
【数７】
とを取得し、固定テーブル法を利用して、Ｇｉ＋１を計算する処理部である。スカラ倍算計算部１５０は、Ｇｉ＋１を「
【数８】
」によって計算する。ここで、
【数８】
に着目すると、Ｇｉ＋１のｉの値が順次変化し、Ｇ２、Ｇ３、・・・Ｇｌｅｎを算出する場合でも、スカラ倍算計算部１５０は、楕円曲線上の点Ｇ０を固定したままで、「
【数７】
」倍すればよい。つまり、スカラ倍算計算部１５０は、固定テーブル法を利用して、スカラ倍算を算出することが可能となる。
【００８２】
スカラ倍算計算部１５０は、固定点テーブルを保持している。図１１は、固定点テーブルのデータ構造の一例を示す図である。図１１に示すように、この固定点テーブルでは、１列目の数値を２倍、３倍した値が格納されている。例えば、１行目では、１Ｇ０、２Ｇ０、３Ｇ０が格納されている。２行目では、４Ｇ０、８Ｇ０、１２Ｇ０が格納されている。３行目では、１６Ｇ０、３２Ｇ０、４８Ｇ０が格納されている。４行目では、６４Ｇ０、１２８Ｇ０、１９２Ｇ０が格納されている。５行目では、２５６Ｇ０、５１２Ｇ０、７６８Ｇ０が格納されている。固定点テーブルの各Ｇ０は、全て楕円曲線上の同じ点である。
【００８３】
スカラ倍算計算部１５０は、固定点テーブルに記憶された各値を組あわせてスカラ倍算「
【数８】
」実行する。例えば、「
【数７】
」の値が「１０」の場合には、スカラ倍算計算部１５０は、図１１の１行目２列目に格納された２Ｇ０と、２行目２列目に格納された８Ｇ０とを楕円加算することで、１０Ｇ０を算出する。
【００８４】
スカラ倍算計算部１５０は、算出結果となるＧｉ＋１を記憶部１３０に記憶する。また、スカラ倍算計算部１５０は、Ｇｉ＋１を特徴点判定部１６０に出力する。
【００８５】
ところで、スカラ倍算計算部１５０が算出するＧｉ＋１と、図６に示したスカラ倍算計算部１５が算出するＧｉ＋１は同じものである。図１２は、各スカラ倍算計算部が算出するＧｉ＋１が同じであることを説明するための図である。ここでは簡単のため、Ｇ２を算出する場合について説明する。
【００８６】
図１２の１ａは、
【数５】
のｉに１を代入したものである。図１２の１ａは、２ａのように置き換えることができる。２ａ部分のａ１は、冪乗余剰計算部１４４が出力する算出結果である。そして、２ａは、３ａのように置き換えることができる。３ａは、
【数８】
のｉに１を代入したものである。つまり、スカラ倍算計算部１５０が算出するＧｉ＋１と、図６に示したスカラ倍算計算部１５が算出するＧｉ＋１は同じものである。しかし、スカラ倍算計算部１５０は、Ｇ０が固定されているので、固定点テーブル法を利用することができる。
【００８７】
スカラ倍算計算部１５０は、固定点テーブルを入力部１１０から取得する。または、スカラ倍算計算部１５０自身が、固定点テーブルを生成してもよい。例えば、スカラ倍算計算部１５０は、楕円曲線上の同一の点同士を加算する処理を繰り返し実行することで、点のスカラ値を順次算出し、算出結果を固定点テーブルに格納する。例えば、加算対象となる楕円曲線上の点は、管理者などによって指定される。
【００８８】
図１０の説明に戻る。特徴点判定部１６０は、Ｇｉ＋１が特徴点であるか否かを判定する処理部である。例えば、特徴点判定部１６０は、Ｇｉ＋１の値の一部が所定の値となっている場合に、Ｇｉ＋１を特徴点であると判定する。特徴点判定部１６０は、特徴点と判定したＧｉ＋１を点出力部１７０に出力する。
【００８９】
点出力部１７０は、特徴点と判定されたＧｉ＋１をテーブルに登録することで、ｌｉｓｔを生成する処理部である。点出力部１７０は、ｌｉｓｔの情報を暗号鍵解析装置２００に送信する。
【００９０】
次に、本実施例にかかるリスト生成装置１００ａの処理手順について説明する。図１３は、本実施例にかかるリスト生成装置の処理手順を示すフローチャートである。図１３に示すように、リスト生成装置１００ａは、ｉの値を初期値に設定し（ステップＳ１０１）、ランダム関数にＧｉを入力して、入力結果ｆｓ（Ｇｉ）を得る（ステップＳ１０２）。
【００９１】
リスト生成装置１００ａは、加算処理を実行する（ステップＳ１０３）。ステップＳ１０３において、リスト生成装置１００ａは、ランダム関数部１４１から出力されるｆｓ（Ｇｉ）と、加算結果格納部１４３に記憶されるａｉ−１とを加算することで、加算処理を実行する。
【００９２】
リスト生成装置１００ａは、冪乗余剰計算を実行する（ステップＳ１０４）。ステップＳ１０４において、リスト生成装置１００ａが冪乗余剰計算を実行することで、
【数７】
が得られる。リスト生成装置１００ａは、固定点テーブルを利用して、スカラ倍算計算を実行し、Ｇｉ＋１を得る（ステップＳ１０５）。
【００９３】
リスト生成装置１００ａは、Ｇｉ＋１が特徴点であるか否かを判定する（ステップＳ１０６）。リスト生成装置１００ａは、Ｇｉ＋１が特徴点ではない場合には（ステップＳ１０６，Ｎｏ）、ステップＳ１０８に移行する。
【００９４】
一方、リスト生成装置１００ａは、Ｇｉ＋１が特徴点の場合には（ステップＳ１０６，Ｙｅｓ）、Ｇｉ＋１をｌｉｓｔに登録する（ステップＳ１０７）。リスト生成装置１００ａは、ｉに１を加算し（ステップＳ１０８）、ｉの値がｌｅｎよりも大きいか否かを判定する（ステップＳ１０９）。リスト生成装置１００ａは、ｉの値がｌｅｎよりも大きい場合には（ステップＳ１０９，Ｙｅｓ）、ｌｉｓｔを暗号鍵解析装置２００に出力する（ステップＳ１１０）。一方、リスト生成装置１００ａは、ｉの値がｌｅｎ以下の場合には（ステップＳ１０９，Ｎｏ）、ステップＳ１０２に移行する。
【００９５】
次に、本実施例にかかるシステムの処理手順について説明する。図１４および図１５は、本実施例にかかるシステムの処理手順を示すフローチャートである。なお、図１４のステップＳ２００〜Ｓ２０３の処理、図１５のステップＳ２１０〜Ｓ２１２、ステップＳ２１０〜Ｓ２２２の処理は、暗号鍵解析装置２００が実行する処理とする。図１４のステップＳ２０４の処理は、リスト生成装置１００ａ〜Ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図１４のステップＳ２０７の処理は、リスト生成装置Ｎ／４〜Ｎ／２がそれぞれｌｉｓｔを生成する処理とする。図１５のステップＳ２１３の処理は、リスト生成装置Ｎ／２〜３Ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図１５のステップＳ２１６の処理は、リスト生成装置３Ｎ／４〜１００ｎがそれぞれｌｉｓｔを生成する処理とする。
【００９６】
暗号鍵解析装置２００は、Ｅ、Ｇ、Ｇ、Ｇｄ、ｌｅｎを取得し（ステップＳ２００）、生成元ζを生成する（ステップＳ２０１）。暗号鍵解析装置２００は、ｓおよびｓ’を算出する（ステップＳ２０２）。ステップＳ２０２において、暗号鍵解析装置２００は、ｓ＝（ｒ−１）／ｄ、ｓ’＝ｄによって、ｓおよびｓ’を算出する。
【００９７】
ｉの値を初期値に設定し（ステップＳ２０３）、リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ１を得る（ステップＳ２０４）。ｉの値に１を加算し（ステップＳ２０５）、ｉの値がＮ／４より大きいか否かを判定する（ステップＳ２０６）。
【００９８】
ｉの値がＮ／４以下の場合には（ステップＳ２０６，Ｎｏ）、ステップＳ２０４に移行する。ｉの値がＮ／４より大きい場合には（ステップＳ２０６，Ｙｅｓ）、各リスト生成装置１００は、ｌｉｓｔ１を暗号鍵解析装置２００に送信する（ステップＳ２０７）。
【００９９】
リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ２を得る（ステップＳ２０８）。ｉの値に１を加算し（ステップＳ２０９）、ｉの値がＮ／２より大きいか否かを判定する。
【０１００】
ｉの値がＮ／２以下の場合には（ステップＳ２１０，Ｎｏ）、ステップＳ２０８に移行する。一方、ｉの値がＮ／２より大きい場合には（ステップＳ２１０，Ｙｅｓ）、各リスト生成装置１００は、ｌｉｓｔ２を暗号鍵解析装置２００に送信する（ステップＳ２１１）。
【０１０１】
図１５の説明に移行する。暗号鍵解析装置２００は、ｌｉｓｔ１とｌｉｓｔ２とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ２１２）。暗号鍵解析装置２００は、ｋ１を算出する（ステップＳ２１３）。ステップＳ２１３において、暗号鍵解析装置２００は、
【数３】
に基づいて、ｋ１を算出するものとする。
【０１０２】
暗号鍵解析装置２００は、ｓおよびｓ’を算出する（ステップＳ２１４）。ステップＳ２１４において、暗号鍵解析装置２００は、ｓ＝ｄ、ｓ’＝（ｒ−１）／ｄによって、ｓおよびｓ’を算出する。
【０１０３】
リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ３を得る（ステップＳ２１５）。ｉの値に１を加算し（ステップＳ２１６）、ｉの値が３Ｎ／４より大きいか否かを判定する（ステップＳ２１７）。
【０１０４】
ｉの値が３Ｎ／４以下の場合には（ステップＳ２１７，Ｎｏ）、ステップＳ２１５に移行する。一方、ｉの値が３Ｎ／４より大きい場合には（ステップＳ２１７，Ｙｅｓ）、リスト生成装置１００は、ｌｉｓｔ３を暗号鍵解析装置２００に送信する（ステップＳ２１８）。
【０１０５】
リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ４を得る（ステップＳ２１９）。ｉの値に１を加算し（ステップＳ２２０）、ｉの値がＮより大きいか否かを判定する（ステップＳ２２１）。
【０１０６】
ｉの値がＮ以下の場合には（ステップＳ２２１，Ｎｏ）、ステップＳ２１９に移行する。一方、ｉの値がＮより大きい場合には（ステップＳ２２１，Ｙｅｓ）、ｌｉｓｔ４を暗号鍵解析装置に送信する（ステップＳ２２２）。暗号鍵解析装置２００は、ｌｉｓｔ３とｌｉｓｔ４とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ２２３）。
【０１０７】
暗号鍵解析装置２００は、ｋ２を算出する（ステップＳ２２４）。ステップＳ２２４において、暗号鍵解析装置２００は、
【数３】
に基づいて、ｋ２を算出するものとする。暗号鍵解析装置２００は、ｋ１とｋ２とを基にしてαを算出し（ステップＳ２２５）、αを出力する（ステップＳ２２６）。ステップＳ２２５において、暗号鍵解析装置２００は、
【数２】
に基づいて、αを算出するものとする。
【０１０８】
図１４のステップ２０４、Ｓ２０８、図１５のステップ２１５、Ｓ２１９に示したリスト生成処理は、図１３に示した処理手順に対応する。
【０１０９】
次に、リスト生成装置１００ａが、固定点テーブルを生成する場合の処理手順について説明する。図１６は、固定点テーブルを生成する処理手順を示すフローチャートである。図１６に示すように、リスト生成装置１００ａは、Ｇとｂｉｔとを取得し（ステップＳ３００）、Ｇ’’にＧの値を設定する（ステップＳ３０１）。ここで、ｂｉｔは、固定点テーブルの行の数を決める閾値である。
【０１１０】
リスト生成装置１００ａは、ｉの値を初期値に設定し（ステップＳ３０２）、Ｇ’にＧ’’の値を設定する（ステップＳ３０３）。リスト生成装置１００ａは、ｊの値を初期値に設定し（ステップＳ３０４）、固定点テーブルのｉ行目、ｊ列目にＧ’’の値を格納する（ステップＳ３０５）。
【０１１１】
リスト生成装置１００ａは、Ｇ’’とＧ’とを加算した値でＧ’’の値を更新し（ステップＳ３０６）、ｊの値に１を加算する（ステップＳ３０７）。リスト生成装置１００ａは、ｊの値が３より大きいか否かを判定する（ステップＳ３０８）。
【０１１２】
リスト生成装置１００ａは、ｊの値が３以下の場合には（ステップＳ３０８，Ｎｏ）、ステップＳ３０５に移行する。一方、リスト生成装置１００ａは、ｊの値が３より大きい場合には（ステップＳ３０８，Ｙｅｓ）、ｉの値に１を加算する（ステップＳ３０９）。
【０１１３】
リスト生成装置１００ａは、ｉの値がｂｉｔより大きいか否かを判定する（ステップＳ３１０）。リスト生成装置１００ａは、ｉの値がｂｉｔ以下の場合には（ステップＳ３１０，Ｎｏ）、ステップＳ３０３に移行する。一方、リスト生成装置１００ａは、ｉの値がｂｉｔよりも大きい場合には（ステップＳ３１０，Ｙｅｓ）、処理を終了する。
【０１１４】
次に、本実施例にかかるリスト生成装置１００ａの効果について説明する。リスト生成装置１００ａでは、ランダム関数部１４１から出力された値と、加算結果格納部１４３に格納された値とを加算した値を基にして生成元を冪乗し、冪乗結果と楕円曲線上の点の初期値Ｇ０とをスカラ倍算することで、ＧｉからＧｉ＋１を算出する。このような方法で、リスト生成装置１００ａがＧｉ＋１を算出すれば、スカラ倍算を実行する場合の楕円曲線上の点は常に初期値Ｇ０で固定される。このため、リスト生成装置１００ａはスカラ倍算を、固定点テーブルの各点の加算によって求めることができ、スカラ倍算にかかる計算コストを削減することができる。
【０１１５】
具体的に、楕円曲線の点の位数ｒ＝２１６０とし、固定点テーブルの生成法におけるｎ進数展開の変数を２１６とする。この場合に、リスト生成装置１００ａは、従来の確率的アルゴリズムによってリストを生成する場合よりも、２１倍速くリストを生成することができる。また、ｎ進数展開の変数を４とした場合には、リスト生成装置１００ａは、従来の確率的アルゴリズムによってリストを生成する場合よりも、２．５倍速くリストを生成することができる。上記効果の前提として、冪乗余剰およびランダムウォーク関数の計算コストは、楕円スカラ倍算の計算コストに比べて十分小さいものとする。また、リストの長さｌｅｎ＝ｒ１／４とし、楕円加算の計算コストを（４ｌｏｇ２ｒ）／３とし、楕円スカラ倍算の計算コストを（６４０／３）とする。また、コンピュータを２１０台利用して並列処理を実行した場合には、図１３〜図１６に示した処理を実行することで、図４、図５に示した従来の処理と比較して、計算コストを１／１３６５に削減することができる。
【０１１６】
また、リスト生成装置１１０ａは、スカラ倍算計算部１５０が生成した点を全てリストに登録するのではなく、特徴点のみをリストに登録する。このため、リストのデータ量を削減することができる。
【０１１７】
ところで、図１０に示したリスト生成装置１００ａの構成は一例であり、リスト生成装置１００ａは、必ずしも図１０に示した各処理部を全て有していなくてもよい。例えば、リスト生成装置１００ａは、固定点テーブル、疑似ランダム関数適用部、スカラ値生成部、点算出部、リスト生成部を有していればよい。
【０１１８】
固定点テーブルは、楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶するものである。この固定点テーブルは、スカラ倍算計算部１５０が保持する固定点テーブルに対応する。疑似ランダム関数適用部は、楕円曲線上の点に対してランダムウォーク関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する処理部である。この疑似ランダム関数適用部は、ランダム関数部１４１に対応する。
【０１１９】
スカラ値生成部は、記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成する処理部である。スカラ値生成部は、スカラ値生成部１４０に対応する。点算出部は、固定点テーブルに記憶された各値のうち、スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、楕円曲線上の点から該楕円曲線上の次の点を算出する処理部である。この点算出部は、スカラ倍算計算部１５０に対応する。リスト生成部は、点算出部が算出した各点を収集しリストを生成する処理部である。リスト生成部は、特徴点判定部１６０、点出力部１７０に対応する。
【０１２０】
なお、上記の実施例で説明したリスト生成装置１００ａの各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図１７を用いて、上記の実施例で説明したリスト生成装置１００ａと同様の機能を有するリスト生成プログラムを実行するコンピュータの一例を説明する。図１７は、リスト生成プログラムを実行するコンピュータを示す図である。
【０１２１】
同図に示すように、リスト生成装置１００ａとしてコンピュータ４００は、入出力制御部４１０、ＨＤＤ（Hard Disk Drive）４２０、ＲＡＭ（Random Access Memory）４３０およびＣＰＵ（Central Processing Unit）４４０を有する。各装置４１０〜４４０は、バス４５０で接続して構成される。
【０１２２】
ここで、入出力制御部４１０は、各種情報の入出力を制御する。ＨＤＤ４２０は、ＣＰＵ４４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ４３０は、各種情報を一時的に記憶する。ＣＰＵ４４０は、各種演算処理を実行する。
【０１２３】
そして、ＨＤＤ４２０には、リスト生成システムデータがあらかじめ記憶されている。このリスト生成システムデータは、図１０に示したリスト生成装置１００ａの各処理部と同様の機能を発揮するリスト生成プログラムを含む。また、リスト生成システムデータは、処理に必要な各種パラメータを含むリスト生成用データを含む。なお、このリスト生成システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【０１２４】
そして、ＣＰＵ４４０が、このリスト生成システムデータをＨＤＤ４２０から読み出してＲＡＭ４３０に展開することにより、リスト生成システムデータはリスト生成システムとして機能するようになる。このリスト生成システムにはリスト生成プロセスが含まれる。
【０１２５】
すなわち、リスト生成システムやそれに搭載されたリスト生成プロセスは、リスト生成用データをＨＤＤ４２０から読み出して、ＲＡＭ４３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【０１２６】
なお、リスト生成システム及びリスト生成プロセスは、図１０に示した各機能部において実行される処理に対応する。例えば、リスト生成プロセスは、繰り返し判定部１２０、スカラ値生成部１４０、スカラ倍算計算部１５０、特徴点判定部１６０、点出力部１７０に対応する。
【０１２７】
なお、上記したリスト生成プログラムについては、必ずしも最初からＨＤＤ４２０に記憶させておく必要はない。
【０１２８】
例えば、コンピュータ４００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１２９】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１３０】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、リスト生成装置１００ａ〜１００ｎと、暗号鍵解析装置２００の機能を統合し、単一の装置で、リスト生成や、暗号鍵の解析を実行してもよい。
【０１３１】
なお、図１０に示した各処理部１２０、１４０〜１７０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、各処理部１２０、１４０〜１７０は、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。また、図１０に示した記憶部１３０は、例えば、ＲＡＭ、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【０１３２】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１３３】
（付記１）楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルと、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する疑似ランダム関数適用部と、
前記記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成部と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出部と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成部と
を備えたことを特徴とするリスト生成装置。
【０１３４】
（付記２）楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成部を更に備えたことを特徴とする付記１に記載のリスト生成装置。
【０１３５】
（付記３）前記リスト生成部は、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする付記１または２に記載のリスト生成装置。
【０１３６】
（付記４）楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータが、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用ステップと、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成ステップと、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出ステップと、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成ステップと
を含んだことを特徴とするリスト生成方法。
【０１３７】
（付記５）楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成ステップを更に含んだことを特徴とする付記４に記載のリスト生成方法。
【０１３８】
（付記６）前記リスト生成ステップは、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする付記４または５に記載のリスト生成方法。
【０１３９】
（付記７）楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータに、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用手順と、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成手順と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出手順と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成手順と
を実行させることを特徴とするリスト生成プログラム。
【０１４０】
（付記８）楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成手順を更にコンピュータに実行させることを特徴とする付記７に記載のリスト生成プログラム。
【０１４１】
（付記９）前記リスト生成手順は、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする付記７または８に記載のリスト生成プログラム。
【符号の説明】
【０１４２】
１００ リスト生成装置
１１０ 入力部
１２０ 繰り返し判定部
１３０ 記憶部
１４０ スカラ値生成部
１５０ スカラ倍算計算部
１６０ 特徴点判定部
１７０ 点出力部
【技術分野】
【０００１】
本発明は、リスト生成装置、リスト生成方法およびリスト生成プログラムに関する。
【背景技術】
【０００２】
近年、ネットショッピングやネットバンキングが普及している。ネットショッピングやネットバンキングにおいて通信を行う場合には、情報漏洩などを防止するために、共通鍵暗号などの暗号技術が利用されている。
【０００３】
公開鍵暗号は、対になる２つの鍵を使ってデータの暗号化、復号をおこなう方式である。すなわち、送信者は受信者によって公開されている公開鍵でメッセージを暗号化して送信する。これに対して、受信者は、暗号化されたメッセージを秘密鍵で復号する。公開鍵は、メッセージを暗号化するための鍵であり、秘密鍵は、公開鍵により暗号化された情報を復号するための鍵である。公開鍵で暗号化された情報は、対の秘密鍵でのみ復号することができる。
【０００４】
この公開鍵暗号は、公開鍵を公開しても安全性を確保できるように、数学的に難しいとされている問題に基づいて設計されている。例えば、公開鍵暗号は、離散対数問題に基づいて設計される。この離散対数問題は、ｐ個の元からなる可換群の生成元Ｇ、α∈Ｚｐとした場合に、Ｇ、Ｇαからαを求めるというものである。
【０００５】
また、上記離散対数問題に補助情報ｄを加え、Ｇ、Ｇα、
【数１】
からαを求めるという補助情報付きの離散対数問題がある。この補助情報付きの離散対数問題を解くアルゴリズムとして、Cheonらの論文では、決定的アルゴリズムと確率的アルゴリズムとが示されている。ｄは、位数ｒから１を減算した値の約数に対応する。
【０００６】
このうち決定的アルゴリズムは、計算量が膨大であるため、この決定的アルゴリズムを用いて離散対数問題を解くことは現実的に難しい。このため、Cheonらは、「Pollard's kangaroo algorithm」を適用することで計算量を削減した確率的アルゴリズムを提案している。この確率的アルゴリズムは、上記離散対数問題に対してだけではなく、楕円曲線上の離散対数問題にも適用されている。楕円曲線上の離散対数問題を楕円曲線離散対数問題と表記する。楕円曲線離散対数問題は、楕円曲線上の３点Ｇ、Ｇ１＝αＧ、Ｇｄ＝αｄＧから未知数αを求める問題である。
【０００７】
この確率的アルゴリズムでは、Ｇ、Ｇｄから検索したｋ１と、Ｇ、Ｇ１から検索したｋ２とを用いて未知数αを求める。ここで、確率的アルゴリズムが、ｋ１、ｋ２を求める場合には、楕円曲線上の特徴点（distinguished point）を収集したリストが利用される。確率的アルゴリズムにおいてリストを生成する場合には、ランダムウォーク関数に楕円曲線上の点を順次代入した値に基づいて、楕円曲線上の点を順次スカラ倍算することで特徴点を求める。
【０００８】
なお、ランダムウォーク関数を利用してリストを作成するためには、膨大な繰り返し処理が必要となる。このため従来では、リストを作成する場合の初期点を多数設定することで、複数のコンピュータで並列処理を行い、リストを作成する場合の処理負荷を分散させている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平１１−２８８２１５号公報
【特許文献２】特開２００３−２８８０１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
コンピュータがリストを生成する場合には、楕円曲線上の点に対してスカラ倍算を実行する必要があり、このスカラ倍算の計算コストが非常に大きいものとなる。このため、スカラ倍算の計算コストを抑え、リストを生成する処理を高速化することが求められる。
【００１１】
開示の技術は、上記に鑑みてなされたものであって、スカラ倍算の計算コストを抑え、リストを生成する処理を高速化することができるリスト生成装置、リスト生成方法およびリスト生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本願の開示するリスト生成装置は、楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルと、前記楕円曲線上の点に対してランダムウォーク関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する疑似ランダム関数適用部と、前記記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成部と、前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出部と、前記点算出部が算出した各点を収集し、リストを生成するリスト生成部とを備えたことを要件とする。
【発明の効果】
【００１３】
本願の開示するリスト生成装置の一つの態様によれば、スカラ倍算の計算コストを抑え、リストを生成する処理を高速化することという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】図１は、Cheonらの確率的アルゴリズムの処理手順を示すフローチャートである。
【図２】図２は、従来の衝突検出処理の処理手順を示すフローチャートである。
【図３】図３は、従来のリスト生成処理の処理手順を示すフローチャートである。
【図４】図４は、確率的アルゴリズムを並列処理する場合の処理手順を示すフローチャート（１）である。
【図５】図５は、確率的アルゴリズムを並列処理する場合の処理手順を示すフローチャート（２）である。
【図６】図６は、従来のリスト生成装置の構成を示す図である。
【図７】図７は、従来のリスト生成装置の処理手順を示すフローチャートである。
【図８】図８は、従来の固定点テーブルのデータ構造の一例を示す図である。
【図９】図９は、本実施例にかかるシステムの構成を示す図である。
【図１０】図１０は、リスト生成装置の構成を示す図である。
【図１１】図１１は、固定点テーブルのデータ構造の一例を示す図である。
【図１２】図１２は、各スカラ倍算計算部が算出するＧｉ＋１が同じことを説明するための図である。
【図１３】図１３は、本実施例にかかるリスト生成装置の処理手順を示すフローチャートである。
【図１４】図１４は、本実施例にかかるシステムの処理手順を示すフローチャート（１）である。
【図１５】図１５は、本実施例にかかるシステムの処理手順を示すフローチャート（２）である。
【図１６】図１６は、固定点テーブルを生成する処理手順を示すフローチャートである。
【図１７】図１７は、リスト生成プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１５】
まず、本願の開示する暗号鍵解読装置における技術を説明するうえで前提となる技術を図面を利用して説明する。
【００１６】
まず、補助情報付きの楕円曲線離散対数問題を解くCheonらの確率的アルゴリズムの処理手順について説明する。図１は、Cheonらの確率的アルゴリズムの処理手順を示すフローチャートである。
【００１７】
図１に示すように、確率的アルゴリズムでは、Ｅ、Ｇ、Ｇ１、Ｇｄ、ｌｅｎを取得する（ステップＳ１０）。ここで、Ｅは、楕円曲線の各種パラメータである。Ｇ、Ｇ１、Ｇｄは、楕円曲線上の点であり、Ｇ１＝αＧ、Ｇｄ＝αｄＧとする。ｌｅｎは、リストを生成する場合に利用する閾値である。ｌｅｎは、楕円曲線の点Ｇの位数ｒの４乗根程度の値が設定される。
【００１８】
確率的アルゴリズムでは、Ｚｒの生成元ζを生成し（ステップＳ１１）、ｓおよびｓ’を設定する（ステップＳ１２）。ステップＳ１２において、ｓは「（ｒ−１）／ｄ」により算出される。また、ｓ’はｄに対応する。
【００１９】
確率的アルゴリズムでは、Ｅ、Ｇ、Ｇｄ、ｓ、ｓ’、ζ、ｌｅｎを基にして、衝突検出処理を実行することでｋ１を得る（ステップＳ１３）。また、確率的アルゴリズムでは、Ｅ、Ｇ、Ｇ１、ｓ、ｓ’、ζ、ｌｅｎを基にして、衝突検出処理を実行することでｋ２を得る（ステップＳ１４）。
【００２０】
確率的アルゴリズムでは、ｋ１、ｋ２を基にしてαを算出し（ステップＳ１５）、αを出力する（ステップＳ１６）。ステップＳ１５において、αは、「
【数２】
」により算出される。
【００２１】
次に、図１のステップＳ１３およびステップＳ１４に示した衝突検出処理の処理手順について説明する。図２は、従来の衝突検出処理の処理手順を示すフローチャートである。図２のフローチャートでは、Ｇ０、Ｇ’０を用いて説明する。図１の確率的アルゴリズムにおいて、Ｅ、Ｇ、Ｇｄ、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、Ｇ０は、Ｇに対応し、Ｇ’０はＧｄに対応する。これに対して、Ｅ、Ｇ、Ｇ１、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、Ｇ０は、Ｇに対応し、Ｇ’０はＧ１に対応する。
【００２２】
図２に示すように、衝突検出処理では、Ｅ、Ｇ０、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ１を得る（ステップＳ２０）。衝突検出処理では、Ｅ、Ｇ’０、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ２を得る（ステップＳ２１）。
【００２３】
衝突検出処理では、ｌｉｓｔ１とｌｉｓｔ２とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ２２）。衝突検出処理では、インデックスｖ、ｕを基にして、ｋを算出し（ステップＳ２３）、ｋを出力する（ステップＳ２４）。ステップＳ２３においてｋは、「
【数３】
」によって算出される。
【００２４】
なお、上記ｋを算出する式において、ｆｓは疑似ランダム関数である。たとえばｆｓは、楕円曲線上の点Ｇ＝（ｘ、ｙ）が与えられた時に、ｘ ｍｏｄ ｓを返す関数である。また、ランダムウォーク関数Ｆｓは、楕円曲線の点Ｇを他の楕円曲線上の点に写像する関数で、「
【数４】
」によって定義される。
【００２５】
例えば、Ｅ、Ｇ、Ｇｄ、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、上記ｋを算出する式により、ｋ１が求められる。これに対して、Ｅ、Ｇ、Ｇ１、ｓ、ｓ’、ζ、ｌｅｎを基にして衝突検出処理を実行する場合には、上記ｋを算出する式により、ｋ２が求められる。
【００２６】
次に、図２のステップＳ２０およびステップＳ２１に示したリスト生成処理の処理手順について説明する。図３は、従来のリスト生成処理の処理手順を示すフローチャートである。図３に示すように、リスト生成処理では、ｉの値を初期値に設定し（ステップＳ３０）、Ｇｉ＋１の値を算出する（ステップＳ３１）。ステップＳ３１において、Ｇｉ＋１は、「
【数５】
」によって算出される。
【００２７】
リスト生成処理では、Ｇｉ＋１の値が特徴点（distinguished point）であるか否かを判定する（ステップＳ３２）。ステップＳ３２において、リスト生成処理では、Ｇｉ＋１の値の一部が所定の値となっている場合は、楕円曲線の点Ｇｉ＋１の値が特徴点であると判定する。
【００２８】
リスト生成処理では、Ｇｉ＋１の値が特徴点ではないと判定した場合には（ステップＳ３２，Ｎｏ）、ステップＳ３４に移行する。一方、リスト生成処理では、Ｇｉ＋１の値が特徴点であると判定した場合には（ステップＳ３２，Ｙｅｓ）、ｌｉｓｔにＧｉ＋１の値を登録する（ステップＳ３３）。
【００２９】
リスト生成処理では、ｉの値に１を加算し（ステップＳ３４）、ｉの値がｌｅｎよりも大きいか否かを判定する（ステップＳ３５）。リスト生成処理では、ｉの値がｌｅｎ以下の場合には（ステップＳ３５，Ｎｏ）、ステップＳ３１に移行する。一方、リスト生成処理では、ｉの値がｌｅｎよりも大きい場合には（ステップＳ３５，Ｙｅｓ）、処理を終了する。
【００３０】
ステップＳ３３において、リスト生成処理では、インデックスｉと、Ｇｉ＋１の値とを対応付けて、ｌｉｓｔに登録するものとする。また、Ｅ、Ｇ０、ζｓ’、ｌｅｎを基にしてリスト生成処理を実行する場合には、上記ｌｉｓｔは、ｌｉｓｔ１に対応する。この場合、ｌｉｓｔのインデックスｉは、ｌｉｓｔ１のインデックスｖに対応する。
【００３１】
また、Ｅ、Ｇ’０、ζｓ’、ｌｅｎを基にしてリスト生成処理を実行する場合には、上記ｌｉｓｔは、ｌｉｓｔ２に対応する。この場合、ｌｉｓｔのインデックスｉは、ｌｉｓｔ２のインデックスｕに対応する。
【００３２】
現在の楕円曲線離散対数問題では、安全性を確保するために、楕円曲線の点の位数ｒは２１６０が利用されている。したがって、上記確率的アルゴリズムを実行する場合には、ｌｅｎは２４０程度の値が指定される。ｌｅｎの値が２４０に指定されると、図３に示したリスト生成処理を、２４０回繰り返し実行する必要があり、計算量が膨大なものとなる。
【００３３】
図１〜図３に示したアルゴリズムは、複数のコンピュータ０〜ｎによって並列処理することで高速化を図ることができる。例えば、複数のコンピュータ０〜ｎは、ネットワークを介して相互に接続されており、協働して並列処理を実行する。この並列処理では、複数のコンピュータ１〜ｎがそれぞれｌｉｓｔを生成し、コンピュータ０が各ｌｉｓｔを収集する。コンピュータ０は、各ｌｉｓｔを利用して、未知数αを算出する。
【００３４】
図４および図５は、確率的アルゴリズムを並列処理する場合の処理手順を示すフローチャートである。なお、図４のステップＳ４０〜Ｓ４３の処理、図５のステップＳ５０〜Ｓ５２、Ｓ５９〜Ｓ６２の処理は、コンピュータ０が実行する処理とする。図４のステップＳ４４の処理は、コンピュータ１〜ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図４のステップＳ４７の処理は、コンピュータｎ／４〜ｎ／２がそれぞれｌｉｓｔを生成する処理とする。図５のステップＳ５３の処理は、コンピュータｎ／２〜３ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図５のステップＳ５６の処理は、コンピュータ３ｎ／４〜ｎがそれぞれｌｉｓｔを生成する処理とする。
【００３５】
図４に示すように、並列処理では、Ｅ、Ｇ、Ｇ１、Ｇｄ、ｌｅｎを取得し（ステップＳ４０）、生成元ζを生成する（ステップＳ４１）。また、並列処理では、ｓおよびｓ’を算出し（ステップＳ４２）、ｉの値を初期値に設定する（ステップＳ４３）。
【００３６】
並列処理では、Ｅ、Ｇｉ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ１を得る（ステップＳ４４）。並列処理では、ｉの値に１を加算し（ステップＳ４５）、ｉの値がｎ／４よりも大きいか否かを判定する（ステップＳ４６）。ｉの値がｎ／４以下の場合には（ステップＳ４６，Ｎｏ）、ステップＳ４４に移行する。
【００３７】
一方、ｉの値がｎ／４よりも大きい場合には（ステップＳ４６，Ｙｅｓ）、並列処理では、Ｅ、Ｇｉｄ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ２を得る（ステップＳ４７）。並列処理では、ｉの値に１を加算し（ステップＳ４８）、ｉの値がｎ／２よりも大きいか否かを判定する（ステップＳ４９）。ｉの値がｎ／２以下の場合には（ステップＳ４９，Ｎｏ）、ステップＳ４７に移行する。
【００３８】
一方、ｉの値がｎ／２よりも大きい場合には（ステップＳ４９，Ｙｅｓ）、並列処理では、ｌｉｓｔ１とｌｉｓｔ２とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ５０）。
【００３９】
並列処理では、ｋ１を算出する（ステップＳ５１）。ｋ１は、「
【数３】
」によって算出される。並列処理では、ｓおよびｓ’を設定する（ステップＳ５２）。ｓはｄに対応する。ｓ’は「（ｒ−１）／ｄ」により算出される。
【００４０】
並列処理では、Ｅ、Ｇｉ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ３を得る（ステップＳ５３）。並列処理では、ｉの値に１を加算し（ステップＳ５４）、ｉの値が３ｎ／４よりも大きいか否かを判定する（ステップＳ５５）。ｉの値が３ｎ／４以下の場合には（ステップＳ５５，Ｎｏ）、ステップＳ５３に移行する。
【００４１】
一方、ｉの値が３ｎ／４よりも大きい場合には（ステップＳ５５，Ｙｅｓ）、並列処理では、Ｅ、Ｇ１ｉ、ζｓ’、ｌｅｎを基にして、リスト生成処理を実行することで、ｌｉｓｔ４を得る（ステップＳ５６）。並列処理では、ｉの値に１を加算し（ステップＳ５７）、ｉの値がｎより大きいか否かを判定する（ステップＳ５８）。ｉの値がｎ以下の場合には（ステップＳ５８，Ｎｏ）、ステップＳ５６に移行する。
【００４２】
一方、ｉの値がｎよりも大きい場合には（ステップＳ５８，Ｙｅｓ）、並列処理では、ｌｉｓｔ３とｌｉｓｔ４とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ５９）。
【００４３】
並列処理では、ｋ２を算出する（ステップＳ６０）。ｋ２は「
【数３】
」によって算出される。並列処理では、ｋ１およびｋ２を基にしてαを算出し（ステップＳ６１）、αを出力する（ステップＳ６２）。
【００４４】
図４および図５に示した処理手順によってコンピュータ０〜ｎが並列処理を実行することで、リストを生成する処理負荷を分散させることができる。
【００４５】
次に、図３に示したリスト生成処理を実行するリスト生成装置の構成について説明する。図６は、従来のリスト生成装置の構成を示す図である。図６に示すように、このリスト生成装置は、入力部１１、繰り返し判定部１２、記憶部１３、スカラ値生成部１４、スカラ倍算計算部１５、特徴点判定部１６、点出力部１７を有する。
【００４６】
入力部１１は、リストを作成するためのパラメータを受け付け、受け付けたパラメータを繰り返し判定部１２、スカラ値生成部１４、スカラ倍算計算部１５に出力する処理部である。入力部１１は、キーボードなどの入力装置からパラメータを受け付けても良いし、他の装置と情報通信を行ってパラメータを取得しても良い。
【００４７】
パラメータには、Ｅ、Ｇ０、ζｓ’、ｌｅｎが含まれる。入力部１１は、パラメータのうち、Ｅ、Ｇ０をスカラ倍算計算部１５に出力し、Ｅ、ζｓ’をスカラ値生成部１４に出力する。また、入力部１１は、ｌｅｎを繰り返し判定部１２に出力する。
【００４８】
繰り返し判定部１２は、ＧｉからＧｉ＋１を計算する回数をカウントする処理部である。繰り返し判定部１２は、ＧｉからＧｉ＋１が計算された回数をどのようにカウントしてもよい。例えば、繰り返し判定部１２は、スカラ倍算計算部１５が、Ｇｉ＋１の計算結果を出力する度に、計算回数をカウントする。
【００４９】
繰り返し判定部１２は、カウントした計算回数が、ｌｅｎを超えた場合に、リスト生成処理を終了すると判定する。例えば、繰り返し判定部１２は、リスト生成処理を終了すると判定した場合には、スカラ値生成部１４およびスカラ倍算計算部１５を制御して、処理を終了させる。
【００５０】
記憶部１３は、スカラ倍算計算部１５の算出結果を記憶する記憶部である。
【００５１】
スカラ値生成部１４は、Ｇｉから
【数６】
を算出する処理部である。図６に示すように、スカラ値生成部１４は、ランダム関数部１４ａおよび冪乗余剰計算部１４ｂを有する。
【００５２】
ランダム関数部１４ａは、Ｇｉからｆｓ（Ｇｉ）を算出する処理部である。例えば、ｆｓは楕円曲線上の点Ｇ＝（ｘ、ｙ）が与えられた場合に、「ｘ ｍｏｄ ｓ」を返す関数である。ランダム関数部１４ａは、ｆｓ（Ｇｉ）を冪乗余剰計算部１４ｂに出力する。なお、ランダム関数部１４ａは、Ｇｉの初期値となるＧ０を、入力部１１から取得する。また、ランダム関数部１４ａは、初期値以外のＧｉの値を記憶部１３から取得する。
【００５３】
冪乗余剰計算部１４ｂは、ｆｓ（Ｇｉ）とζｓ’とを取得して、
【数６】
を算出する処理部である。冪乗余剰計算部１４ｂは、
【数６】
をスカラ倍算計算部１５に出力する。
【００５４】
スカラ倍算計算部１５は、Ｇｉと
【数６】
とを取得して、Ｇｉ＋１を計算する処理部である。スカラ倍算計算部１５は、Ｇｉ＋１を「
【数５】
」によって計算する。スカラ倍算計算部１５は、Ｇｉ＋１を記憶部１３に記憶する。また、スカラ倍算計算部１５は、Ｇｉ＋１を特徴点判定部１６に出力する。
【００５５】
特徴点判定部１６は、Ｇｉ＋１が特徴点であるか否かを判定する処理部である。例えば、特徴点判定部１６は、Ｇｉ＋１の値の一部が所定の値となっている場合に、Ｇｉ＋１を特徴点であると判定する。特徴点判定部１６は、特徴点と判定したＧｉ＋１を点出力部１７に出力する。
【００５６】
点出力部１７は、特徴点と判定されたＧｉ＋１をテーブルに登録することで、ｌｉｓｔを生成する処理部である。点出力部１７は、ｌｉｓｔの情報を外部装置に出力する。
【００５７】
次に、図６に示したリスト生成装置１０の処理手順について説明する。図７は、従来のリスト生成装置の処理手順を示すフローチャートである。図７に示すように、リスト生成装置１０は、ｉの値を初期値に設定し（ステップＳ７０）、ランダム関数にＧｉを入力し、入力結果ｆｓ（Ｇｉ）を得る（ステップＳ７１）。
【００５８】
リスト生成装置１０は、冪乗余剰計算を実行する（ステップＳ７２）。冪乗余剰計算を実行することで、
【数６】
が得られる。リスト生成装置１０は、スカラ倍算計算を実行し、Ｇｉ＋１を得る（ステップＳ７３）。
【００５９】
リスト生成装置１０は、Ｇｉ＋１が特徴点であるか否かを判定する（ステップＳ７４）。リスト生成装置１０は、Ｇｉ＋１が特徴点ではない場合には（ステップＳ７４，Ｎｏ）、ステップＳ７６に移行する。
【００６０】
一方、リスト生成装置１０は、Ｇｉ＋１が特徴点の場合には（ステップＳ７４，Ｙｅｓ）、Ｇｉ＋１をｌｉｓｔに登録する（ステップＳ７５）。リスト生成装置１０は、ｉに１を加算し（ステップＳ７６）、ｉの値がｌｅｎよりも大きいか否かを判定する（ステップＳ７７）。リスト生成装置１０は、ｉの値がｌｅｎよりも大きい場合には（ステップＳ７７，Ｙｅｓ）、処理を終了する。一方、リスト生成装置１０は、ｉの値がｌｅｎ以下の場合には（ステップＳ７７，Ｎｏ）、ステップＳ７１に移行する。
【００６１】
リスト生成装置１０がｌｉｓｔを生成する場合に実行する各種計算のうち、図７のスカラ倍算計算が主要な計算となる。このため、スカラ倍算計算を高速化することができれば、リスト生成装置１０がｌｉｓｔを生成する処理を高速化することができる。
【００６２】
スカラ倍算計算を高速化する手法として、固定点テーブル法と呼ばれる技術が存在する。この固定点テーブル法は、予め複数のスカラ倍算計算を実行して、固定点テーブルに計算結果を格納しておく。そして、固定点テーブル法は、新たにスカラ倍算計算を実行する場合には、固定点テーブルに格納された計算結果を加算することで、スカラ倍算計算を実行する。
【００６３】
具体的に、固定点テーブル法について説明する。図８は、従来の固定点テーブルのデータ構造の一例を示す図である。図８に示すように、この固定点テーブルでは、１列目の数値を２倍、３倍した値が格納されている。例えば、１行目では、１Ｇ、２Ｇ、３Ｇが格納されている。２行目では、４Ｇ、８Ｇ、１２Ｇが格納されている。３行目では、１６Ｇ、３２Ｇ、４８Ｇが格納されている。４行目では、６４Ｇ、１２８Ｇ、１９２Ｇが格納されている。５行目では、２５６Ｇ、５１２Ｇ、７６８Ｇが格納されている。固定点テーブルの各Ｇは、全て同じ点である。
【００６４】
例えば、固定点テーブル法が、１０Ｇを算出する場合について説明する。この場合、固定点テーブル法では、図８の１行目２列目に格納された２Ｇと、２行目２列目に格納された８Ｇとを楕円加算することで、１０Ｇを算出する。１０とＧとをスカラ倍算するよりも、２Ｇと８Ｇとを楕円加算する方が、計算コストが少ない。このため、固定点テーブル法を用いてリスト生成処理を実行することができれば、ｌｉｓｔを生成する処理を高速化することができる。
【００６５】
しかし、固定点テーブル法を用いる場合には、スカラ倍算を行う楕円曲線上の点Ｇが常に同じ値であるという制限がある。例えば、固定点テーブル法では、１０Ｇ１を、２Ｇ１と８Ｇ１との楕円加算で算出することができるが、１０Ｇ２を、２Ｇ１と８Ｇ１との楕円加算で算出することができない。
【００６６】
図６に示したスカラ倍算計算部１５が、スカラ倍算計算を実行する場合には、楕円曲線上の点Ｇが毎回更新される。このため、従来のリスト生成装置１０は、固定点テーブル法を利用して、スカラ倍算計算を高速化することができなかった。
【実施例】
【００６７】
次に、本実施例について説明する。図９は、本実施例にかかるシステムの構成を示す図である。図９に示すように、このシステムは、リスト生成装置１００ａ〜１００ｎと、暗号鍵解析装置２００とを有する。リスト生成装置１００ａ〜１００ｎおよび暗号鍵解析装置２００は、ネットワーク５０を介して相互に接続される。
【００６８】
リスト生成装置１００ａ〜１００ｎは、ランダムウォーク関数と楕円曲線上の点Ｇとを基にして、リスト（ｌｉｓｔ）を生成する処理部である。リスト生成装置１００ａ〜１００ｎは、リストを暗号鍵解析装置２００に送信する。
【００６９】
暗号鍵解析装置２００は、リスト生成装置１００ａ〜１００ｎからリストを収集し、各リストを基にして、補助情報付き楕円曲線離散対数問題を解くことで、暗号鍵を解析する装置である。この暗号鍵解析装置２００は、上記のコンピュータ０に対応する装置であり、図１に示した処理手順によって、補助情報付き楕円曲線離散対数問題を解くものとする。
【００７０】
次に、リスト生成装置１００ａの構成について説明する。その他のリスト生成装置の構成は、リスト生成装置１００ａの構成と同様である。図１０は、リスト生成装置の構成を示す図である。図１０に示すように、このリスト生成装置１００ａは、入力部１１０、繰り返し判定部１２０、記憶部１３０、スカラ倍算計算部１５０、特徴点判定部１６０、点出力部１７０を有する。
【００７１】
入力部１１０は、リストを作成するためのパラメータを受け付け、受け付けたパラメータを繰り返し判定部１２０、スカラ値生成部１４０、スカラ倍算計算部１５０に出力する処理部である。入力部１１０は、キーボードなどの入力装置からパラメータを受け付けても良いし、他の装置と情報通信を行ってパラメータを取得しても良い。
【００７２】
パラメータには、Ｅ、Ｇ０、ζｓ’、ｌｅｎが含まれる。Ｅ、Ｇ０、ζｓ’、ｌｅｎに関する説明は、上記と同様である。入力部１１０は、パラメータのうち、Ｅ、Ｇ０をスカラ倍算計算部１５０に出力し、Ｅ、ζｓ’をスカラ値生成部１４０に出力する。また、入力部１１０は、ｌｅｎを繰り返し判定部１２０に出力する。
【００７３】
繰り返し判定部１２０は、ＧｉからＧｉ＋１を計算する回数をカウントする処理部である。繰り返し判定部１２０は、ＧｉからＧｉ＋１が計算された回数をどのようにカウントしてもよい。例えば、繰り返し判定部１２０は、スカラ倍算計算部１５０が、Ｇｉ＋１の計算結果を出力する度に、計算回数をカウントする。
【００７４】
繰り返し判定部１２０は、カウントした計算回数が、ｌｅｎを超えた場合に、リスト生成処理を終了すると判定する。例えば、繰り返し判定部１２０は、リスト生成処理を終了すると判定した場合には、スカラ値生成部１４０およびスカラ倍算計算部１５０を制御して、処理を終了させる。
【００７５】
記憶部１３０は、スカラ倍算計算部１５０の計算結果を記憶する記憶部である。
【００７６】
スカラ値生成部１４０は、Ｇｉから
【数７】
を算出する処理部である。図１０に示すように、スカラ値生成部１４０は、ランダム関数部１４１、加算部１４２、加算結果格納部１４３、冪乗余剰計算部１４４を有する。
【００７７】
ランダム関数部１４１は、Ｇｉからｆｓ（Ｇｉ）を算出する処理部である。例えば、ｆｓは楕円曲線上の点Ｇ＝（ｘ、ｙ）が与えられた場合に、「ｘ ｍｏｄ ｓ」を返す関数である。ランダム関数部１４１は、ｆｓ（Ｇｉ）を加算部１４２に出力する。なお、ランダム関数部１４１は、Ｇｉの初期値となるＧ０を、入力部１１０から取得する。また、ランダム関数部１４１は、初期値以外のＧｉの値を記憶部１３０から取得する。
【００７８】
加算部１４２は、ｆｓ（Ｇｉ）の値を順次加算し、加算結果ａｉを冪乗余剰計算部１４４に出力する処理部である。また、加算部１４２は、加算結果ａｉを加算結果格納部１４３に記憶する。加算結果格納部１４３は、加算結果ａｉを記憶する記憶部である。加算結果格納部１４３は、加算結果ａｉの初期値ａ０として０を記憶する。
【００７９】
具体的に、加算部１４２は、「ａｉ＝ａｉ−１＋ｆｓ（Ｇｉ）」によりａｉを算出する。すなわち、加算部１４２は、ランダム関数部１４１から取得したｆｓ（Ｇｉ）と、加算結果格納部１４３に記憶されたａｉ−１とを加算することで、ａｉを算出する。
【００８０】
冪乗余剰計算部１４４は、ａｉとζｓ’とを取得して、
【数７】
を算出する処理部である。冪乗余剰計算部１４４は、
【数７】
をスカラ倍算計算部１５に出力する。
【００８１】
スカラ倍算計算部１５０は、Ｇ０と
【数７】
とを取得し、固定テーブル法を利用して、Ｇｉ＋１を計算する処理部である。スカラ倍算計算部１５０は、Ｇｉ＋１を「
【数８】
」によって計算する。ここで、
【数８】
に着目すると、Ｇｉ＋１のｉの値が順次変化し、Ｇ２、Ｇ３、・・・Ｇｌｅｎを算出する場合でも、スカラ倍算計算部１５０は、楕円曲線上の点Ｇ０を固定したままで、「
【数７】
」倍すればよい。つまり、スカラ倍算計算部１５０は、固定テーブル法を利用して、スカラ倍算を算出することが可能となる。
【００８２】
スカラ倍算計算部１５０は、固定点テーブルを保持している。図１１は、固定点テーブルのデータ構造の一例を示す図である。図１１に示すように、この固定点テーブルでは、１列目の数値を２倍、３倍した値が格納されている。例えば、１行目では、１Ｇ０、２Ｇ０、３Ｇ０が格納されている。２行目では、４Ｇ０、８Ｇ０、１２Ｇ０が格納されている。３行目では、１６Ｇ０、３２Ｇ０、４８Ｇ０が格納されている。４行目では、６４Ｇ０、１２８Ｇ０、１９２Ｇ０が格納されている。５行目では、２５６Ｇ０、５１２Ｇ０、７６８Ｇ０が格納されている。固定点テーブルの各Ｇ０は、全て楕円曲線上の同じ点である。
【００８３】
スカラ倍算計算部１５０は、固定点テーブルに記憶された各値を組あわせてスカラ倍算「
【数８】
」実行する。例えば、「
【数７】
」の値が「１０」の場合には、スカラ倍算計算部１５０は、図１１の１行目２列目に格納された２Ｇ０と、２行目２列目に格納された８Ｇ０とを楕円加算することで、１０Ｇ０を算出する。
【００８４】
スカラ倍算計算部１５０は、算出結果となるＧｉ＋１を記憶部１３０に記憶する。また、スカラ倍算計算部１５０は、Ｇｉ＋１を特徴点判定部１６０に出力する。
【００８５】
ところで、スカラ倍算計算部１５０が算出するＧｉ＋１と、図６に示したスカラ倍算計算部１５が算出するＧｉ＋１は同じものである。図１２は、各スカラ倍算計算部が算出するＧｉ＋１が同じであることを説明するための図である。ここでは簡単のため、Ｇ２を算出する場合について説明する。
【００８６】
図１２の１ａは、
【数５】
のｉに１を代入したものである。図１２の１ａは、２ａのように置き換えることができる。２ａ部分のａ１は、冪乗余剰計算部１４４が出力する算出結果である。そして、２ａは、３ａのように置き換えることができる。３ａは、
【数８】
のｉに１を代入したものである。つまり、スカラ倍算計算部１５０が算出するＧｉ＋１と、図６に示したスカラ倍算計算部１５が算出するＧｉ＋１は同じものである。しかし、スカラ倍算計算部１５０は、Ｇ０が固定されているので、固定点テーブル法を利用することができる。
【００８７】
スカラ倍算計算部１５０は、固定点テーブルを入力部１１０から取得する。または、スカラ倍算計算部１５０自身が、固定点テーブルを生成してもよい。例えば、スカラ倍算計算部１５０は、楕円曲線上の同一の点同士を加算する処理を繰り返し実行することで、点のスカラ値を順次算出し、算出結果を固定点テーブルに格納する。例えば、加算対象となる楕円曲線上の点は、管理者などによって指定される。
【００８８】
図１０の説明に戻る。特徴点判定部１６０は、Ｇｉ＋１が特徴点であるか否かを判定する処理部である。例えば、特徴点判定部１６０は、Ｇｉ＋１の値の一部が所定の値となっている場合に、Ｇｉ＋１を特徴点であると判定する。特徴点判定部１６０は、特徴点と判定したＧｉ＋１を点出力部１７０に出力する。
【００８９】
点出力部１７０は、特徴点と判定されたＧｉ＋１をテーブルに登録することで、ｌｉｓｔを生成する処理部である。点出力部１７０は、ｌｉｓｔの情報を暗号鍵解析装置２００に送信する。
【００９０】
次に、本実施例にかかるリスト生成装置１００ａの処理手順について説明する。図１３は、本実施例にかかるリスト生成装置の処理手順を示すフローチャートである。図１３に示すように、リスト生成装置１００ａは、ｉの値を初期値に設定し（ステップＳ１０１）、ランダム関数にＧｉを入力して、入力結果ｆｓ（Ｇｉ）を得る（ステップＳ１０２）。
【００９１】
リスト生成装置１００ａは、加算処理を実行する（ステップＳ１０３）。ステップＳ１０３において、リスト生成装置１００ａは、ランダム関数部１４１から出力されるｆｓ（Ｇｉ）と、加算結果格納部１４３に記憶されるａｉ−１とを加算することで、加算処理を実行する。
【００９２】
リスト生成装置１００ａは、冪乗余剰計算を実行する（ステップＳ１０４）。ステップＳ１０４において、リスト生成装置１００ａが冪乗余剰計算を実行することで、
【数７】
が得られる。リスト生成装置１００ａは、固定点テーブルを利用して、スカラ倍算計算を実行し、Ｇｉ＋１を得る（ステップＳ１０５）。
【００９３】
リスト生成装置１００ａは、Ｇｉ＋１が特徴点であるか否かを判定する（ステップＳ１０６）。リスト生成装置１００ａは、Ｇｉ＋１が特徴点ではない場合には（ステップＳ１０６，Ｎｏ）、ステップＳ１０８に移行する。
【００９４】
一方、リスト生成装置１００ａは、Ｇｉ＋１が特徴点の場合には（ステップＳ１０６，Ｙｅｓ）、Ｇｉ＋１をｌｉｓｔに登録する（ステップＳ１０７）。リスト生成装置１００ａは、ｉに１を加算し（ステップＳ１０８）、ｉの値がｌｅｎよりも大きいか否かを判定する（ステップＳ１０９）。リスト生成装置１００ａは、ｉの値がｌｅｎよりも大きい場合には（ステップＳ１０９，Ｙｅｓ）、ｌｉｓｔを暗号鍵解析装置２００に出力する（ステップＳ１１０）。一方、リスト生成装置１００ａは、ｉの値がｌｅｎ以下の場合には（ステップＳ１０９，Ｎｏ）、ステップＳ１０２に移行する。
【００９５】
次に、本実施例にかかるシステムの処理手順について説明する。図１４および図１５は、本実施例にかかるシステムの処理手順を示すフローチャートである。なお、図１４のステップＳ２００〜Ｓ２０３の処理、図１５のステップＳ２１０〜Ｓ２１２、ステップＳ２１０〜Ｓ２２２の処理は、暗号鍵解析装置２００が実行する処理とする。図１４のステップＳ２０４の処理は、リスト生成装置１００ａ〜Ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図１４のステップＳ２０７の処理は、リスト生成装置Ｎ／４〜Ｎ／２がそれぞれｌｉｓｔを生成する処理とする。図１５のステップＳ２１３の処理は、リスト生成装置Ｎ／２〜３Ｎ／４がそれぞれｌｉｓｔを生成する処理とする。図１５のステップＳ２１６の処理は、リスト生成装置３Ｎ／４〜１００ｎがそれぞれｌｉｓｔを生成する処理とする。
【００９６】
暗号鍵解析装置２００は、Ｅ、Ｇ、Ｇ、Ｇｄ、ｌｅｎを取得し（ステップＳ２００）、生成元ζを生成する（ステップＳ２０１）。暗号鍵解析装置２００は、ｓおよびｓ’を算出する（ステップＳ２０２）。ステップＳ２０２において、暗号鍵解析装置２００は、ｓ＝（ｒ−１）／ｄ、ｓ’＝ｄによって、ｓおよびｓ’を算出する。
【００９７】
ｉの値を初期値に設定し（ステップＳ２０３）、リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ１を得る（ステップＳ２０４）。ｉの値に１を加算し（ステップＳ２０５）、ｉの値がＮ／４より大きいか否かを判定する（ステップＳ２０６）。
【００９８】
ｉの値がＮ／４以下の場合には（ステップＳ２０６，Ｎｏ）、ステップＳ２０４に移行する。ｉの値がＮ／４より大きい場合には（ステップＳ２０６，Ｙｅｓ）、各リスト生成装置１００は、ｌｉｓｔ１を暗号鍵解析装置２００に送信する（ステップＳ２０７）。
【００９９】
リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ２を得る（ステップＳ２０８）。ｉの値に１を加算し（ステップＳ２０９）、ｉの値がＮ／２より大きいか否かを判定する。
【０１００】
ｉの値がＮ／２以下の場合には（ステップＳ２１０，Ｎｏ）、ステップＳ２０８に移行する。一方、ｉの値がＮ／２より大きい場合には（ステップＳ２１０，Ｙｅｓ）、各リスト生成装置１００は、ｌｉｓｔ２を暗号鍵解析装置２００に送信する（ステップＳ２１１）。
【０１０１】
図１５の説明に移行する。暗号鍵解析装置２００は、ｌｉｓｔ１とｌｉｓｔ２とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ２１２）。暗号鍵解析装置２００は、ｋ１を算出する（ステップＳ２１３）。ステップＳ２１３において、暗号鍵解析装置２００は、
【数３】
に基づいて、ｋ１を算出するものとする。
【０１０２】
暗号鍵解析装置２００は、ｓおよびｓ’を算出する（ステップＳ２１４）。ステップＳ２１４において、暗号鍵解析装置２００は、ｓ＝ｄ、ｓ’＝（ｒ−１）／ｄによって、ｓおよびｓ’を算出する。
【０１０３】
リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ３を得る（ステップＳ２１５）。ｉの値に１を加算し（ステップＳ２１６）、ｉの値が３Ｎ／４より大きいか否かを判定する（ステップＳ２１７）。
【０１０４】
ｉの値が３Ｎ／４以下の場合には（ステップＳ２１７，Ｎｏ）、ステップＳ２１５に移行する。一方、ｉの値が３Ｎ／４より大きい場合には（ステップＳ２１７，Ｙｅｓ）、リスト生成装置１００は、ｌｉｓｔ３を暗号鍵解析装置２００に送信する（ステップＳ２１８）。
【０１０５】
リスト生成装置１００は、リスト生成処理を実行することで、ｌｉｓｔ４を得る（ステップＳ２１９）。ｉの値に１を加算し（ステップＳ２２０）、ｉの値がＮより大きいか否かを判定する（ステップＳ２２１）。
【０１０６】
ｉの値がＮ以下の場合には（ステップＳ２２１，Ｎｏ）、ステップＳ２１９に移行する。一方、ｉの値がＮより大きい場合には（ステップＳ２２１，Ｙｅｓ）、ｌｉｓｔ４を暗号鍵解析装置に送信する（ステップＳ２２２）。暗号鍵解析装置２００は、ｌｉｓｔ３とｌｉｓｔ４とを比較して、衝突が発生する場合のインデックスｖ、ｕを判定する（ステップＳ２２３）。
【０１０７】
暗号鍵解析装置２００は、ｋ２を算出する（ステップＳ２２４）。ステップＳ２２４において、暗号鍵解析装置２００は、
【数３】
に基づいて、ｋ２を算出するものとする。暗号鍵解析装置２００は、ｋ１とｋ２とを基にしてαを算出し（ステップＳ２２５）、αを出力する（ステップＳ２２６）。ステップＳ２２５において、暗号鍵解析装置２００は、
【数２】
に基づいて、αを算出するものとする。
【０１０８】
図１４のステップ２０４、Ｓ２０８、図１５のステップ２１５、Ｓ２１９に示したリスト生成処理は、図１３に示した処理手順に対応する。
【０１０９】
次に、リスト生成装置１００ａが、固定点テーブルを生成する場合の処理手順について説明する。図１６は、固定点テーブルを生成する処理手順を示すフローチャートである。図１６に示すように、リスト生成装置１００ａは、Ｇとｂｉｔとを取得し（ステップＳ３００）、Ｇ’’にＧの値を設定する（ステップＳ３０１）。ここで、ｂｉｔは、固定点テーブルの行の数を決める閾値である。
【０１１０】
リスト生成装置１００ａは、ｉの値を初期値に設定し（ステップＳ３０２）、Ｇ’にＧ’’の値を設定する（ステップＳ３０３）。リスト生成装置１００ａは、ｊの値を初期値に設定し（ステップＳ３０４）、固定点テーブルのｉ行目、ｊ列目にＧ’’の値を格納する（ステップＳ３０５）。
【０１１１】
リスト生成装置１００ａは、Ｇ’’とＧ’とを加算した値でＧ’’の値を更新し（ステップＳ３０６）、ｊの値に１を加算する（ステップＳ３０７）。リスト生成装置１００ａは、ｊの値が３より大きいか否かを判定する（ステップＳ３０８）。
【０１１２】
リスト生成装置１００ａは、ｊの値が３以下の場合には（ステップＳ３０８，Ｎｏ）、ステップＳ３０５に移行する。一方、リスト生成装置１００ａは、ｊの値が３より大きい場合には（ステップＳ３０８，Ｙｅｓ）、ｉの値に１を加算する（ステップＳ３０９）。
【０１１３】
リスト生成装置１００ａは、ｉの値がｂｉｔより大きいか否かを判定する（ステップＳ３１０）。リスト生成装置１００ａは、ｉの値がｂｉｔ以下の場合には（ステップＳ３１０，Ｎｏ）、ステップＳ３０３に移行する。一方、リスト生成装置１００ａは、ｉの値がｂｉｔよりも大きい場合には（ステップＳ３１０，Ｙｅｓ）、処理を終了する。
【０１１４】
次に、本実施例にかかるリスト生成装置１００ａの効果について説明する。リスト生成装置１００ａでは、ランダム関数部１４１から出力された値と、加算結果格納部１４３に格納された値とを加算した値を基にして生成元を冪乗し、冪乗結果と楕円曲線上の点の初期値Ｇ０とをスカラ倍算することで、ＧｉからＧｉ＋１を算出する。このような方法で、リスト生成装置１００ａがＧｉ＋１を算出すれば、スカラ倍算を実行する場合の楕円曲線上の点は常に初期値Ｇ０で固定される。このため、リスト生成装置１００ａはスカラ倍算を、固定点テーブルの各点の加算によって求めることができ、スカラ倍算にかかる計算コストを削減することができる。
【０１１５】
具体的に、楕円曲線の点の位数ｒ＝２１６０とし、固定点テーブルの生成法におけるｎ進数展開の変数を２１６とする。この場合に、リスト生成装置１００ａは、従来の確率的アルゴリズムによってリストを生成する場合よりも、２１倍速くリストを生成することができる。また、ｎ進数展開の変数を４とした場合には、リスト生成装置１００ａは、従来の確率的アルゴリズムによってリストを生成する場合よりも、２．５倍速くリストを生成することができる。上記効果の前提として、冪乗余剰およびランダムウォーク関数の計算コストは、楕円スカラ倍算の計算コストに比べて十分小さいものとする。また、リストの長さｌｅｎ＝ｒ１／４とし、楕円加算の計算コストを（４ｌｏｇ２ｒ）／３とし、楕円スカラ倍算の計算コストを（６４０／３）とする。また、コンピュータを２１０台利用して並列処理を実行した場合には、図１３〜図１６に示した処理を実行することで、図４、図５に示した従来の処理と比較して、計算コストを１／１３６５に削減することができる。
【０１１６】
また、リスト生成装置１１０ａは、スカラ倍算計算部１５０が生成した点を全てリストに登録するのではなく、特徴点のみをリストに登録する。このため、リストのデータ量を削減することができる。
【０１１７】
ところで、図１０に示したリスト生成装置１００ａの構成は一例であり、リスト生成装置１００ａは、必ずしも図１０に示した各処理部を全て有していなくてもよい。例えば、リスト生成装置１００ａは、固定点テーブル、疑似ランダム関数適用部、スカラ値生成部、点算出部、リスト生成部を有していればよい。
【０１１８】
固定点テーブルは、楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶するものである。この固定点テーブルは、スカラ倍算計算部１５０が保持する固定点テーブルに対応する。疑似ランダム関数適用部は、楕円曲線上の点に対してランダムウォーク関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する処理部である。この疑似ランダム関数適用部は、ランダム関数部１４１に対応する。
【０１１９】
スカラ値生成部は、記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成する処理部である。スカラ値生成部は、スカラ値生成部１４０に対応する。点算出部は、固定点テーブルに記憶された各値のうち、スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、楕円曲線上の点から該楕円曲線上の次の点を算出する処理部である。この点算出部は、スカラ倍算計算部１５０に対応する。リスト生成部は、点算出部が算出した各点を収集しリストを生成する処理部である。リスト生成部は、特徴点判定部１６０、点出力部１７０に対応する。
【０１２０】
なお、上記の実施例で説明したリスト生成装置１００ａの各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図１７を用いて、上記の実施例で説明したリスト生成装置１００ａと同様の機能を有するリスト生成プログラムを実行するコンピュータの一例を説明する。図１７は、リスト生成プログラムを実行するコンピュータを示す図である。
【０１２１】
同図に示すように、リスト生成装置１００ａとしてコンピュータ４００は、入出力制御部４１０、ＨＤＤ（Hard Disk Drive）４２０、ＲＡＭ（Random Access Memory）４３０およびＣＰＵ（Central Processing Unit）４４０を有する。各装置４１０〜４４０は、バス４５０で接続して構成される。
【０１２２】
ここで、入出力制御部４１０は、各種情報の入出力を制御する。ＨＤＤ４２０は、ＣＰＵ４４０による各種処理の実行に必要な情報を記憶する。ＲＡＭ４３０は、各種情報を一時的に記憶する。ＣＰＵ４４０は、各種演算処理を実行する。
【０１２３】
そして、ＨＤＤ４２０には、リスト生成システムデータがあらかじめ記憶されている。このリスト生成システムデータは、図１０に示したリスト生成装置１００ａの各処理部と同様の機能を発揮するリスト生成プログラムを含む。また、リスト生成システムデータは、処理に必要な各種パラメータを含むリスト生成用データを含む。なお、このリスト生成システムデータを適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【０１２４】
そして、ＣＰＵ４４０が、このリスト生成システムデータをＨＤＤ４２０から読み出してＲＡＭ４３０に展開することにより、リスト生成システムデータはリスト生成システムとして機能するようになる。このリスト生成システムにはリスト生成プロセスが含まれる。
【０１２５】
すなわち、リスト生成システムやそれに搭載されたリスト生成プロセスは、リスト生成用データをＨＤＤ４２０から読み出して、ＲＡＭ４３０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【０１２６】
なお、リスト生成システム及びリスト生成プロセスは、図１０に示した各機能部において実行される処理に対応する。例えば、リスト生成プロセスは、繰り返し判定部１２０、スカラ値生成部１４０、スカラ倍算計算部１５０、特徴点判定部１６０、点出力部１７０に対応する。
【０１２７】
なお、上記したリスト生成プログラムについては、必ずしも最初からＨＤＤ４２０に記憶させておく必要はない。
【０１２８】
例えば、コンピュータ４００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１２９】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておく。そして、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１３０】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、リスト生成装置１００ａ〜１００ｎと、暗号鍵解析装置２００の機能を統合し、単一の装置で、リスト生成や、暗号鍵の解析を実行してもよい。
【０１３１】
なお、図１０に示した各処理部１２０、１４０〜１７０は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）や、ＦＰＧＡ（Field Programmable Gate Array）などの集積装置に対応する。または、各処理部１２０、１４０〜１７０は、ＣＰＵやＭＰＵ（Micro Processing Unit）等の電子回路に対応する。また、図１０に示した記憶部１３０は、例えば、ＲＡＭ、ＲＯＭ（Read Only Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子、またはハードディスク、光ディスクなどの記憶装置に対応する。
【０１３２】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１３３】
（付記１）楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルと、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する疑似ランダム関数適用部と、
前記記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成部と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出部と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成部と
を備えたことを特徴とするリスト生成装置。
【０１３４】
（付記２）楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成部を更に備えたことを特徴とする付記１に記載のリスト生成装置。
【０１３５】
（付記３）前記リスト生成部は、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする付記１または２に記載のリスト生成装置。
【０１３６】
（付記４）楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータが、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用ステップと、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成ステップと、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出ステップと、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成ステップと
を含んだことを特徴とするリスト生成方法。
【０１３７】
（付記５）楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成ステップを更に含んだことを特徴とする付記４に記載のリスト生成方法。
【０１３８】
（付記６）前記リスト生成ステップは、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする付記４または５に記載のリスト生成方法。
【０１３９】
（付記７）楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータに、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用手順と、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成手順と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出手順と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成手順と
を実行させることを特徴とするリスト生成プログラム。
【０１４０】
（付記８）楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成手順を更にコンピュータに実行させることを特徴とする付記７に記載のリスト生成プログラム。
【０１４１】
（付記９）前記リスト生成手順は、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする付記７または８に記載のリスト生成プログラム。
【符号の説明】
【０１４２】
１００ リスト生成装置
１１０ 入力部
１２０ 繰り返し判定部
１３０ 記憶部
１４０ スカラ値生成部
１５０ スカラ倍算計算部
１６０ 特徴点判定部
１７０ 点出力部
【特許請求の範囲】
【請求項１】
楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルと、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する疑似ランダム関数適用部と、
前記記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成部と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出部と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成部と
を備えたことを特徴とするリスト生成装置。
【請求項２】
楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成部を更に備えたことを特徴とする請求項１に記載のリスト生成装置。
【請求項３】
前記リスト生成部は、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする請求項１または２に記載のリスト生成装置。
【請求項４】
楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータが、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用ステップと、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成ステップと、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出ステップと、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成ステップと
を含んだことを特徴とするリスト生成方法。
【請求項５】
楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータに、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用手順と、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成手順と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出手順と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成手順と
を実行させることを特徴とするリスト生成プログラム。
【請求項１】
楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルと、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶部に記憶する疑似ランダム関数適用部と、
前記記憶部に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成部と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出部と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成部と
を備えたことを特徴とするリスト生成装置。
【請求項２】
楕円曲線上の同一の点同士の加算を繰り返し実行することで、点のスカラ倍算を実行し、スカラ倍算の実行結果を前記固定点テーブルに格納する固定点テーブル生成部を更に備えたことを特徴とする請求項１に記載のリスト生成装置。
【請求項３】
前記リスト生成部は、前記点算出部が算出した値のうち、所定の特徴を有する点を収集することで、前記リストを生成することを特徴とする請求項１または２に記載のリスト生成装置。
【請求項４】
楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータが、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用ステップと、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成ステップと、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出ステップと、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成ステップと
を含んだことを特徴とするリスト生成方法。
【請求項５】
楕円曲線上の所定の点をそれぞれ異なるスカラ値によってスカラ倍算した値を複数記憶する固定点テーブルを有するコンピュータに、
前記楕円曲線上の点に対して疑似ランダム関数を用いることで前記楕円曲線上の点を算出し、算出した点を記憶装置に記憶する疑似ランダム関数適用手順と、
前記記憶装置に記憶された点の値を合計し、合計した値に基づいてスカラ値を生成するスカラ値生成手順と、
前記固定点テーブルに記憶された各値のうち、前記スカラ値に対応する値の組あわせを判定し、判定した各値を加算することで、前記楕円曲線上の点から該楕円曲線上の次の点を算出する点算出手順と、
前記点算出部が算出した各点を収集し、リストを生成するリスト生成手順と
を実行させることを特徴とするリスト生成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１２−３２６５０（Ｐ２０１２−３２６５０Ａ）
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願番号】特願２０１０−１７２８９９（Ｐ２０１０−１７２８９９）
【出願日】平成２２年７月３０日（２０１０．７．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年２月１６日（２０１２．２．１６）
【国際特許分類】
【出願日】平成２２年７月３０日（２０１０．７．３０）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、独立行政法人情報通信研究機構、「適切な暗号技術を選択可能とするための新しい暗号技術の評価手法 〜暗号の技術評価に関する研究開発〜」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]