(57)【特許請求の範囲】
【請求項１】
一方向性関数を計算する一方向性関数演算方法において、
予め一時記憶手段に、Ｒ１，…，Ｒ４∈Ｅ［Ｌ］（但し、Ｅ［Ｌ］は、Ｌを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合）を記憶するための領域を確保しておき、
固有値計算手段において、フロベニウス写像の固有値λ１，λ２∈Ｚ／ＬＺを求めておき、
入力手段において、Ｒ∈Ｅ［Ｌ］を入力し、
スカラー倍設定手段において、
【数１】
0004752176.tif 000081
として予め求めておき、
フロベニウス写像計算手段において、フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を前記一時記憶手段に格納しておき、
楕円スカラー倍計算手段において、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を前記一時記憶手段に格納しておき、
楕円減算手段において、前記一時記憶手段から前記計算結果Ｒ１と前記計算結果Ｒ２を取得してＲ１−Ｒ２を計算し、計算結果Ｒ３を前記一時記憶手段に格納しておき、
前記楕円スカラー倍計算手段において、Ｒ３のスカラー倍
【数２】
0004752176.tif 000082
を計算して、計算結果Ｒ４を前記一時記憶手段に格納し、
最終的に、出力手段により、前記一時記憶手段からＲ４を読み出して出力することを特徴とする一方向性関数演算方法。
【請求項２】
一方向性関数を計算する一方向性関数計算方法において、
一時記憶手段に、Ｒ１，…，Ｒ３∈Ｅ［Ｌ］(但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合)を確保するための領域を確保しておき、
固有値計算手段において、フロベニウス写像の固有値λ２∈Ｚ／ＬＺを求めておき、
入力手段において、Ｒ∈Ｅ［Ｌ］を入力し、
フロベニウス写像計算手段において、フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を前記一時記憶手段に格納し、
楕円スカラー倍計算手段において、前記固有値計算手段で求められた前記固有値λ２を取得して、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を前記一時記憶手段に格納し、
楕円減算手段において、前記一時記憶手段から前記計算結果Ｒ１と前記計算結果Ｒ２を取得して、Ｒ１−Ｒ２を行い、計算結果Ｒ３を前記一時記憶手段に格納し、
最終的に、出力手段により、前記一時記憶手段からＲ３を読み出して出力することを特徴とする一方向性関数演算方法。
【請求項３】
有限体上定義された非超特異楕円曲線の有理点群が、同じ位数を持つ2つの巡回群の直積群を含む場合に、該楕円曲線上で定義される一方向性関数を計算する一方向性関数計算方法において、
一時記憶手段に、楕円曲線上の点を格納する領域Ｒ１，０以上ｍ以下の整数を格納可能な領域ｉを確保しておき、
初期値設定手段において、
前記Ｒ１に楕円曲線上の無限遠点Ｏを設定し、前記領域ｉに0を設定し、
入力手段において、
楕円曲線Ｅ［Ｌ］（Ｅ［Ｌ］（但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合））上の点Ｒを取得し、
フロベニウス写像計算手段により、
フロベニウス写像φｉＲを計算し、その計算結果と前記点Ｒ１とを楕円加算計算手段に入力し、その計算結果を前記領域Ｒ１に格納し、前記領域ｉのカウントをｉ＋１とし、ｉ≧ｍ（ｍは１以上の整数）になるまで当該処理を繰り返し、
最終的に、
【数３】
0004752176.tif 000083
と一致する楕円曲線上の点の値を、前記領域Ｒ１から読み出し、出力手段により出力することを特徴とする一方向性関数演算方法。
【請求項４】
前記楕円加算計算手段において、
前記ｍの加算連鎖ｎ0＝１，ｎｉ＝ｎｊ＋ｎｋ，（ｊ，ｋ＜ｉ），ｎｃ＝ｍ（但し、ｃはｍの加算連鎖の長さ）とし、
前記領域ｉのカウントをｉ＋１とし、
前記加算連鎖に従って前記領域ｉに対するｊ、ｋ＜ｉを決定し、
【数４】
0004752176.tif 000084
【数５】
0004752176.tif 000085
である）とする加算連鎖を用いた一方向性関数計算を用いる請求項３記載の一方向性関数演算方法。
【請求項５】
一方向性関数を計算する一方向性関数演算装置であって、
予め、Ｒ１，…，Ｒ４∈Ｅ［Ｌ］(但し、Ｅ［Ｌ］は、Ｌを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合）を記憶するための領域が確保された一時記憶手段と、
フロベニウス写像の固有値λ１，λ２∈Ｚ／ＬＺを求めておく固有値計算手段と、
スカラー倍
【数６】
0004752176.tif 000086
として予め求めておくスカラー倍設定手段と、
Ｒ∈Ｅ［Ｌ］を入力する入力手段と、
フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を前記一時記憶手段に格納するフロベニウス写像計算手段と、
前記固有値計算手段から前記固有値を取得し、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を前記一時記憶手段に格納する楕円スカラー倍計算手段と、
前記一時記憶手段から前記計算結果Ｒ１と前記計算結果Ｒ２を取得し、Ｒ１−Ｒ２を計算し、計算結果Ｒ３を前記一時記憶手段に格納する楕円減算手段と、
前記スカラー倍設定手段から前記λΔを取得し、Ｒ３のスカラー倍
【数７】
0004752176.tif 000087
を計算して、計算結果Ｒ４を前記一時記憶手段に格納する第２の楕円スカラー倍計算手段と、
最終的に、前記一時記憶手段からＲ４を読み出して出力する出力手段と、を有することを特徴とする一方向性関数演算装置。
【請求項６】
一方向性関数を計算する一方向性関数計算装置であって、
一時記憶手段に、Ｒ１，…，Ｒ３∈Ｅ［Ｌ］(但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合) を格納するための領域が確保される一時記憶手段と、
予め、フロベニウス写像の固有値λ２∈Ｚ／ＬＺを求める固有値計算手段と、
Ｒ∈Ｅ［Ｌ］を入力する入力手段と、
フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を前記一時記憶手段に格納するフロベニウス写像計算手段と、
前記固有値計算手段で求められた前記固有値λ２を取得して、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を前記一時記憶手段に格納する楕円スカラー倍計算手段と、
前記一時記憶手段から前記計算結果Ｒ１と前記計算結果Ｒ２を取得して、Ｒ１−Ｒ２を行い、計算結果Ｒ３を前記一時記憶手段に格納する楕円減算手段と、
最終的に、前記一時記憶手段からＲ３を読み出して出力する出力手段と、を有することを特徴とする一方向性関数演算装置。
【請求項７】
有限体上定義された非超特異楕円曲線の有理点群が、同じ位数を持つ2つの巡回群の直積群を含む場合に、該楕円曲線上で定義される一方向性関数を計算する一方向性関数計算装置であって、
楕円曲線上の点を格納する領域Ｒ１，０以上ｍ以下の整数を格納可能な領域ｉを確保しておく一時記憶手段と、
楕円曲線Ｅ［Ｌ］（Ｅ［Ｌ］（但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合））上の点Ｒ１に楕円曲線上の無限遠点Ｏを設定し、前記領域ｉに0を設定する初期値設定手段と、
楕円曲線上の点Ｒを取得する入力手段と、
フロベニウス写像φｉＲを計算し、その計算結果と前記点Ｒ１とを楕円加算計算手段に入力し、その出力結果を前記領域Ｒ１に格納し、前記領域ｉのカウントをｉ＋１とし、ｉ≧ｍ（ｍは１以上の整数）になるまで当該処理を繰り返すフロベニウス写像計算手段と、
最終的に、
【数８】
0004752176.tif 000088
と一致する楕円曲線上の点の値を、前記領域Ｒ１から読み出し、出力する出力手段と、
を有することを特徴とする一方向性関数演算装置。
【請求項８】
前記楕円加算計算手段は、
前記ｍの加算連鎖ｎ0＝１，ｎｉ＝ｎｊ＋ｎｋ，（ｊ，ｋ＜ｉ），ｎｃ＝ｍ（但し、ｃはｍの加算連鎖の長さ）とし、
前記領域ｉのカウントをｉ＋１とし、
前記加算連鎖に従って前記領域ｉに対するｊ、ｋ＜ｉを決定し、
【数９】
0004752176.tif 000089
【数１０】
0004752176.tif 000090
である）とする加算連鎖を用いた一方向性関数計算を用いる請求項７記載の一方向性関数演算装置。
【請求項９】
コンピュータを、
請求項５乃至８記載の一方向性関数演算装置の各手段として機能させるための一方向性関数演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一方向性関数演算方法及び装置及びプログラムに係り、特に、公衆電気通信網における計算量理論に基づく、情報セキュリティのための一方向性関数演算方法及び装置及びプログラムに関する。
【０００２】
近年、公衆電話通信網の発達に伴い、情報セキュリティ技術に注目が集まっている。情報セキュリティ技術は、情報理論に基づくものや、計算可能性理論に基づくものなど、様々な背景技術に基づき構成され得るが、中でも計算量理論に基づくものが効率等の面から最も実用的と考えられており、現在盛んに研究が行われている。本発明では、この計算量理論に基づく情報セキュリティ技術に関するものである。
【背景技術】
【０００３】
ある多項式時間で計算可能な関数に対して、いかなる効率の良いアルゴリズムを用いても、無視できる確率でしかその逆関数を計算することができないならば、その関数は一方向であるという。現在、一方向性関数の存在は、証明されておらず、暗号学あるいは計算機科学における未解決な問題とされている。従って、厳密な意味での一方向性関数は現在知られていないが、一方向性関数の候補としてＲＳＡ法、Ｒａｂｉｎ法、離散対数に基づく方法などが良く知られている(例えば、非特許文献１〜４参照)。
【非特許文献１】Oded Goldreich,『FOUNDATION OF CRYTOGRAPHY』出版  CAMBRIDGE UNIVERSITY PRESS,ISBN0-521-79172-3
【非特許文献２】イアン・Ｆ・プラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート著、鈴木治郎＝訳、『楕円曲線暗号』、ｐ．１１２，出版  ピアソン・エドュケーション、ISBN4-89471-431-0
【非特許文献３】Alfred.J.Menezes,『ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS』pp.61-81,出版KLUWER ACADEMIC PUBLISHERS, ISBN0-7923-9368-6
【非特許文献４】Knuth,『The Art of Computer Programming』VOLUME 2 Seminumerical Altorithms Third Edition, p.465,出版 Addition Wesley,ISBN0-201-89684-2
【発明の開示】
【発明が解決しようとする課題】
【０００４】
一方向性関数は、計算量理論に基づく、情報セキュリティ技術を構成する上で、中核的な役割を担っており、現代の暗号認証技術にとって欠かせない存在であると考えられている。従って、新しい一方向性関数の発明は、計算量理論に基づくあらゆる情報セキュリティ技術に応用することが可能で、重要な技術的課題と考えることができる。
【０００５】
本発明は、楕円ＤＨ判定問題の困難性に帰着可能な一方向性関数を構成することが可能な一方向性関数演算方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
図１は、本発明の原理を説明するための図である。
【０００７】
本発明（請求項１）は、一方向性関数を計算する一方向性関数演算方法において、
予め一時記憶手段に、Ｒ１，…，Ｒ４∈Ｅ［Ｌ］（但し、Ｅ［Ｌ］は、Ｌを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合）を記憶するための領域を確保しておき（ステップ１）、
固有値計算手段において、フロベニウス写像の固有値λ１，λ２∈Ｚ／ＬＺを求めておき（ステップ２）、
入力手段において、Ｒ∈Ｅ［Ｌ］を入力し、
スカラー倍設定手段において、
【０００８】
【数１１】
0004752176.tif 000002
として予め求めておき（ステップ３）、
フロベニウス写像計算手段において、フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を一時記憶手段に格納しておき（ステップ４）、
楕円スカラー倍計算手段において、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を一時記憶手段に格納しておき（ステップ５）、
楕円減算手段において、一時記憶手段から計算結果Ｒ１と計算結果Ｒ２を取得してＲ１−Ｒ２を計算し、計算結果Ｒ３を一時記憶手段に格納しておき（ステップ６）、
楕円スカラー倍計算手段において、Ｒ３のスカラー倍
【０００９】
【数２６】
0004752176.tif 000003
を計算して、計算結果Ｒ４を一時記憶手段に格納し（ステップ７）、
最終的に、出力手段により、一時記憶手段からＲ４を読み出して出力する（ステップ８）。
【００１０】
本発明（請求項２）は、一方向性関数を計算する一方向性関数計算方法において、
一時記憶手段に、Ｒ１，…，Ｒ３∈Ｅ［Ｌ］(但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合)を確保するための領域を確保しておき、
固有値計算手段において、フロベニウス写像の固有値λ２∈Ｚ／ＬＺを求めておき、
入力手段において、Ｒ∈Ｅ［Ｌ］を入力し、
フロベニウス写像計算手段において、フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を一時記憶手段に格納し、
楕円スカラー倍計算手段において、固有値計算手段で求められた固有値λ２を取得して、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を一時記憶手段に格納し、
楕円減算手段において、一時記憶手段から計算結果Ｒ１と計算結果Ｒ２を取得して、Ｒ１−Ｒ２を行い、計算結果Ｒ３を一時記憶手段に格納し、
最終的に、出力手段により、一時記憶手段からＲ３を読み出して出力する。
【００１１】
本発明（請求項３）は、  有限体上定義された非超特異楕円曲線の有理点群が、同じ位数を持つ2つの巡回群の直積群を含む場合に、該楕円曲線上で定義される一方向性関数を計算する一方向性関数計算方法において、
一時記憶手段に、楕円曲線上の点を格納する領域Ｒ１，０以上ｍ以下の整数を格納可能な領域ｉを確保しておき、
初期値設定手段において、
Ｒ１に楕円曲線上の無限遠点Ｏを設定し、領域ｉに0を設定し、
入力手段において、
楕円曲線Ｅ［Ｌ］（Ｅ［Ｌ］（但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合））上の点Ｒを取得し、
フロベニウス写像計算手段により、
フロベニウス写像φｉＲを計算し、その計算結果と点Ｒ１とを楕円加算計算手段に入力し、その計算結果を領域Ｒ１に格納し、領域ｉのカウントをｉ＋１とし、ｉ≧ｍ（ｍは１以上の整数）になるまで当該処理を繰り返し、
最終的に、
【数１２】
0004752176.tif 000004
と一致する楕円曲線上の点の値を、領域Ｒ１から読み出し、出力手段により出力する。
【００１２】
スカラー倍Ｚ／ＬＺの係数特性多項式を分解体上で、
φ2−ｔφ＋ｑ＝（φ−λ1）（φ−λ２）
と分解し（但し、λ1、λ２はフロベニウス写像φの固有値）、
λ1，λ２∈Ｚ／ＬＺで、かつ、λ1≠λ２のときの線形空間Ｅ［Ｌ］の線形変換
【数２７】
0004752176.tif 000005
を、
【数２８】
0004752176.tif 000006
と定義し、任意の点Ｅ［Ｌ］上の点に対して、
【数２９】
0004752176.tif 000007
なるＥ［Ｌ］上の点Ｐ，Ｑが存在し（点ＲはＲ＝Ｐ＋Ｑ）、線形空間Ｅ［Ｌ］の線形変換
【数３０】
0004752176.tif 000008
による象
【数３１】
0004752176.tif 000009
を、フロベニウス写像φの固有値λ1に関する固有空間とし、該固有空間への射影になる線形変換
【数３２】
0004752176.tif 000010
（但し、固有値は1、及びｑmod L、λ1＝1、λ２＝ｑmod Lとする）
であるトレースマップを適用し、フロベニウス写像φによりＲ１＋φｉＲとして、その結果Ｒ1を一時記憶手段に格納し、ｉ＋1とし、ｉ≧ｍ（ｍは0以上の整数）になるまで当該処理を繰り返し、
最終的に、出力手段から計算結果Ｒ１を一時記憶手段から読み出して出力する。
【００１３】
本発明（請求項４）は、楕円加算計算手段において、
ｍの加算連鎖ｎ0＝１，ｎｉ＝ｎｊ＋ｎｋ，（ｊ，ｋ＜ｉ），ｎｃ＝ｍ（但し、ｃはｍの加算連鎖の長さ）とし、
領域ｉのカウントをｉ＋１とし、
加算連鎖に従って領域ｉに対するｊ、ｋ＜ｉを決定し、
【数１３】
0004752176.tif 000011
【数１４】
0004752176.tif 000012
である）とする加算連鎖を用いた一方向性関数計算を用いる。
【００１４】
図２は、本発明の原理構成図である。
【００１５】
本発明（請求項５）は、一方向性関数を計算する一方向性関数演算装置であって、
予め、Ｒ１，…，Ｒ４∈Ｅ［Ｌ］(但し、Ｅ［Ｌ］は、Ｌを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合）を記憶するための領域が確保された一時記憶手段２５０と、
フロベニウス写像の固有値λ１，λ２∈Ｚ／ＬＺを求めておく固有値計算手段２１０と、
スカラー倍
【００１６】
【数１５】
0004752176.tif 000013
として予め求めておくスカラー倍設定手段２２０と、
Ｒ∈Ｅ［Ｌ］を入力する入力手段と２３０、
フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を一時記憶手段に格納するフロベニウス写像計算手段２４０と、
固有値計算手段２１０から固有値を取得し、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を一時記憶手段２５０に格納する楕円スカラー倍計算手段２６０と、
一時記憶手段２５０から計算結果Ｒ１と計算結果Ｒ２を取得し、Ｒ１−Ｒ２を計算し、計算結果Ｒ３を一時記憶手段２５０に格納する楕円減算手段２７０と、
スカラー倍設定手段２２０からλΔを取得し、Ｒ３のスカラー倍
【００１７】
【数３４】
0004752176.tif 000014
を計算して、計算結果Ｒ４を一時記憶手段に格納する第２の楕円スカラー倍計算手段と、
最終的に、一時記憶手段２５０からＲ４を読み出して出力する出力手段２８０と、を有する
【００１８】
本発明（請求項６）は、一方向性関数を計算する一方向性関数計算装置であって、
一時記憶手段に、Ｒ１，…，Ｒ３∈Ｅ［Ｌ］(但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合) を格納するための領域が確保される一時記憶手段と、
予め、フロベニウス写像の固有値λ２∈Ｚ／ＬＺを求める固有値計算手段と、
Ｒ∈Ｅ［Ｌ］を入力する入力手段と、
フロベニウス写像φにより、楕円曲線上の点φＲを計算し、計算結果Ｒ１を一時記憶手段に格納するフロベニウス写像計算手段と、
固有値計算手段で求められた固有値λ２を取得して、点Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を一時記憶手段に格納する楕円スカラー倍計算手段と、
一時記憶手段から計算結果Ｒ１と計算結果Ｒ２を取得して、Ｒ１−Ｒ２を行い、計算結果Ｒ３を一時記憶手段に格納する楕円減算手段と、
最終的に、一時記憶手段からＲ３を読み出して出力する出力手段と、を有する。
【００１９】
本発明（請求項７）は、有限体上定義された非超特異楕円曲線の有理点群が、同じ位数を持つ2つの巡回群の直積群を含む場合に、該楕円曲線上で定義される一方向性関数を計算する一方向性関数計算装置であって、
楕円曲線上の点を格納する領域Ｒ１，０以上ｍ以下の整数を格納可能な領域ｉを確保しておく一時記憶手段と、
楕円曲線Ｅ［Ｌ］（Ｅ［Ｌ］（但し、Ｅ［Ｌ］はＬを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒの内、ＬＲ＝Ｏ（但し、Ｏは無限遠点）を満たすＲの集合））上の点Ｒ１に楕円曲線上の無限遠点Ｏを設定し、領域ｉに0を設定する初期値設定手段と、
楕円曲線上の点Ｒを取得する入力手段と、
フロベニウス写像φｉＲを計算し、その計算結果と点Ｒ１とを楕円加算計算手段に入力し、その出力結果を領域Ｒ１に格納し、領域ｉのカウントをｉ＋１とし、ｉ≧ｍ（ｍは１以上の整数）になるまで当該処理を繰り返すフロベニウス写像計算手段と、
最終的に、
【数１６】
0004752176.tif 000015
と一致する楕円曲線上の点の値を、領域Ｒ１から読み出し、出力する出力手段と、
を有する。
【００２１】
本発明（請求項８）の楕円加算計算手段は、
ｍの加算連鎖ｎ0＝１，ｎｉ＝ｎｊ＋ｎｋ，（ｊ，ｋ＜ｉ），ｎｃ＝ｍ（但し、ｃはｍの加算連鎖の長さ）とし、
領域ｉのカウントをｉ＋１とし、
加算連鎖に従って領域ｉに対するｊ、ｋ＜ｉを決定し、
【数１７】
0004752176.tif 000016
【数１８】
0004752176.tif 000017
である）とする加算連鎖を用いた一方向性関数計算を用いる。
【００２４】
本発明（請求項９）は、コンピュータを、
請求項５乃至８記載の一方向性関数演算装置の各手段として機能させるための一方向性関数演算プログラム。
【００２５】
【数４１】
0004752176.tif 000018
として予め求めておくステップと、
Ｒ∈Ｅ［Ｌ］を入力させるステップと、
フロベニウス写像φにより、φＲを計算し、計算結果Ｒ１を一時記憶手段に格納するステップと、
Ｒのスカラー倍λ２Ｒを計算し、計算結果Ｒ２を一時記憶手段に格納するステップと、
一時記憶手段から計算結果Ｒ１と計算結果Ｒ２を取得してＲ１−Ｒ２を計算し、計算結果Ｒ３を一時記憶装置に格納するステップと、
Ｒ３のスカラー倍
【００２６】
【数４２】
0004752176.tif 000019
を計算して、計算結果Ｒ４を一時記憶手段に格納するステップと、
最終的に、一時記憶手段からＲ４を読み出して出力させるステップと、を実行する。
【００２７】
本発明は、一方向性関数を計算する一方向性関数計算プログラムであって、
一時記憶手段に、Ｒ１，…，Ｒ３∈Ｅ［Ｌ］(但し、Ｅ［Ｌ］は楕円曲線上のねじれ点全体、Ｌは素数)を確保しておくステップと、
フロベニウス写像の固有値λ２∈Ｚ／ＬＺを予め求めるステップと、
入力手段において、Ｒ∈Ｅ［Ｌ］を入力させるステップと、
フロベニウス写像φＲを計算し、計算結果Ｒ１を一時記憶手段に格納するステップと、
固定値λ２を取得して、楕円スカラー倍λ２Ｒを計算し、計算結果Ｒ２を一時記憶手段に格納するステップと、
一時記憶手段から計算結果Ｒ１と計算結果Ｒ２を取得して、Ｒ１−Ｒ２を行い、計算結果Ｒ３を一時記憶手段に格納するステップと、
最終的に、一時記憶手段からＲ３を読み出して出力させるステップと、を実行する。
【発明の効果】
【００３２】
本発明によれば、楕円ＤＨ判定問題の困難性に帰着可能な一方向性関数を構成することができる。
【発明を実施するための最良の形態】
【００３３】
以下、図面と共に、本発明の実施の形態について説明する。
【００３４】
構成及び動作の説明に先立ち、楕円曲線、有限体のフロベニウス写像、楕円曲線のフロベニウス写像、フロベニウス写像の固有空間と射影について説明する。
【００３５】
（１）楕円曲線：
一般に、体Ｋ上定義された楕円曲線とは、ａ１，ａ２，ａ３，ａ４，ａ６∈Ｋとして、等式
Ｅ：ｙ２＋ａ１ｘｙ＋ａ３ｙ＝ｘ３＋ａ２ｘ２＋ａ４ｘ＋ａ５        （１）
を満たす点（ｘ，ｙ）の集合に無限遠点と呼ばれる特別の点Ｏを付加したものである。楕円曲線上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ有限回のＫの体演算により定義でき、以下の性質を持つことにより、楕円曲線は、楕円加算に関して群をなす。
【００３６】
−楕円曲線上の任意の２点Ｒ１，Ｒ２に対してＲ１＋Ｒ２は楕円曲線上の点である。
【００３７】
−楕円曲線上の任意の３点Ｒ１，Ｒ２，Ｒ３に対し、
Ｒ１＋（Ｒ２＋Ｒ３）＝（Ｒ１＋Ｒ２）＋Ｒ３（結合律）
−Ｏに関して、楕円曲線上の任意の点Ｒ１に対し、
Ｒ１＋Ｏ＝Ｏ＋Ｒ１＝Ｒ１（単位元の存在）
−楕円曲線上の任意の点Ｒ１に対し、逆元(−Ｒ１)が存在して
Ｒ１＋（−Ｒ１）＝（−Ｒ１）＋Ｒ１＝Ｏ（逆元の存在）
さらに、楕円加算は以下の性質を持つ。
【００３８】
−楕円曲線上の任意の２点Ｒ１，Ｒ２に対してＲ１＋Ｒ２＝Ｒ２＋Ｒ１である（交換律）。
【００３９】
楕円曲線上の一点Ｒがあれば、楕円加算を用いて２Ｒ＝Ｒ＋Ｒなる楕円曲線上の点２Ｒを作ることができる。同様に、また、任意の正整数ｋに対して(−ｋ)Ｒ＝ｋ（−Ｒ）及び、０Ｒ＝Ｏと定義すると、結局任意の整数ｋに対して、ｋＲを定義することができる。整数ｋと点Ｒから点ｋＲを求めることを楕円スカラー倍と呼ぶ。また、二項演算“−”を
Ｒ１−Ｒ２＝Ｒ１＋（−Ｒ２）
として定義し、楕円減算と呼ぶ。特に、Ｋが有限体でＫ上の点、あるいは、Ｋの有限次拡大上の点Ｒが楕円曲線（１）上の点であるとき、Ｒは、有限巡回群を生成し、これを用いて暗号系や署名系を構成することがしばしば行われる。このような暗号系や署名系は、楕円加算や楕円スカラー倍が効率的に計算可能な楕円曲線を用いる。Ｌを素数とし、有限体上定義された楕円曲線Ｅ上の点Ｒのうち、ＬＲ＝Ｏを満たすＲの集合をＥ［Ｌ］とする。Ｅ［Ｌ］に関して以下の性質が成り立つことにより、Ｅ［Ｌ］は、楕円加算を加法とし、楕円スカラー倍をスカラー倍とするＺ／ＬＺ上線形空間である。
【００４０】
楕円加算に関して、
−Ｅ［Ｌ］上の任意の２点Ｒ１，Ｒ２に対して楕円加算Ｒ１＋Ｒ２はＥ［Ｌ］上の点である。
【００４１】
−楕円加算の結合律は、Ｅ［Ｌ］上でも成立する。
【００４２】
−楕円加算の交換律は、Ｅ［Ｌ］上でも成立する。
【００４３】
−Ｏは、Ｅ［Ｌ］上の点であり、Ｅ［Ｌ］上の任意の点Ｒ１に対してＯ＋Ｒ１＝Ｒ１ある性質を持つ。
【００４４】
−Ｅ［Ｌ］上の任意の点Ｒ１に対して逆元（−Ｒ１）は、Ｅ［Ｌ］上に唯一存在する。
【００４５】
楕円スカラー倍演算に関して
−Ｅ［Ｌ］上の任意の点Ｒ１及び体Ｚ／ＬＺの任意の元ｋ１に対し、楕円スカラー倍ｋ１Ｒ１は、Ｅ［Ｌ］上の点である。
【００４６】
−Ｅ［Ｌ］上の任意の点Ｒ１及びＺ／ＬＺ上の任意の２元ｋ１、ｋ２に対し、（ｋ１＋ｋ２）Ｒ１＝ｋ１Ｒ１＋ｋ２Ｒ２。
【００４７】
−Ｅ［Ｌ］上の任意の２点Ｒ１，Ｒ２及び体Ｚ／ＬＺ上の任意の元ｋ１に対し、ｋ１（Ｒ１＋Ｒ２）＝ｋ１Ｒ１＋ｋ１Ｒ２。
【００４８】
−Ｅ［Ｌ］上の任意の点Ｒ１及び体Ｚ／ＬＺ上の任意の２元ｋ１，ｋ２に対し、（ｋ１、ｋ２）Ｒ１＝ｋ１（ｋ２Ｒ１）。
【００４９】
−Ｅ［Ｌ］上の任意の点Ｒ１及び体Ｚ／ＬＺの乗法単位元１に対し、１Ｒ１Ｒ２。
【００５０】
（２）有限体のフロベニウス写像：
ｑを素数またはその冪とする。有限体ＧＦ（ｑｍ）上の元ｘを表現するのに、有限体ＧＦ（ｑ）上のｍ個の元の組ｘｉ，（０≦ｉ＜ｍ）を用いることができる。ｍ個のｘｉ∈ＧＦ（ｑ），（０≦ｉ＜ｍ）の組をＧＦ（ｑｍ）上の元を対応させる代表的な方法は、ｍ個のαｉ∈ＧＦ（ｑｍ），（０≦ｉ＜ｍ）の組を使って、
【００５１】
【数１９】
0004752176.tif 000020
なる対応をとることである。この時、αｉ，（０≦ｉ＜ｍ）は、ＧＦ（ｑ）ｍとＧＦ（ｑｍ）とで１対１対応が取れるような特別な組み合わせでなくてはならない。このような性質を持つαｉ（０≦ｉ＜ｍ）を基底と呼ぶ。とこで、二項定理によれば、
【００５２】
【数２０】
0004752176.tif 000021
である。右辺の各項の係数
【００５３】
【数２１】
0004752176.tif 000022
は、二項係数と呼ばれる定数で、ｉ≠０かつｉ≠ｑの場合、必ずｑの倍数となる。α，β∈ＧＦ（ｑｍ）の時は、ｑの整数倍は０と同値であるから、
（α＋β）ｑ＝αｑ＋βｑ
が成立する。さらに、ｃ∈ＧＦ（ｑ）なるｃに関してｃｑ＝ｃが成立する。一般に、α１，α２，…，αｎを不定元とする任意のＧＦ（ｑ）係数有理式ｆ（α１，α２，…，αｎ）に対して、
【００５４】
【数２２】
0004752176.tif 000023
が成立する。従って、
【００５５】
【数２３】
0004752176.tif 000024
なるとき、
【００５６】
【数２４】
0004752176.tif 000025
である。従って事前に、
【００５７】
【数２５】
0004752176.tif 000026
なるｃｉｊ∈ＧＦ（ｑ）が計算してあれば、
【００５８】
【数２６】
0004752176.tif 000027
によって、元の基底αｉを使ったｘｑの表現
【００５９】
【数２７】
0004752176.tif 000028
を求めることができる。すなわち、ｘ∈ＧＦ（ｑｍ）を表現するベクトル（ｘｉ）に行列（ｃｉｊ）をかけるだけでｘｑを表現するベクトルが得られる。この演算コストは一般には、ＧＦ（ｑｍ）上の乗算１回分の演算コストと略等しい。また、行列（ｃｉｊ）ｎ，（ｎ＝２，３，…）を事前に求めておけば、行列（ｃｉｊ）をかけるだけで、
【００６０】
【数２８】
0004752176.tif 000029
を表現するベクトルが得られる。あるいは、（ｃｉｊ）−１を事前に求めておけば、（ｃｉｊ）−１をかけるだけで、ｘ１／ｑを表現するベクトルが得られる。従って一般の整数ｎに対して、
【００６１】
【数２９】
0004752176.tif 000030
の演算コストは、一般にＧＦ（ｑｍ）上の演算１回分の演算コストに等しい。さらに、行列（ｃｉｊ）が簡単になるようにな、特別な基底が存在し、そのような基底を採用した場合、
【００６２】
【数３０】
0004752176.tif 000031
の演算コストはＧＦ（ｑｍ）上の乗算と比較して、無視できるほど小さい。ＧＦ（ｑｍ）上の元ｘからｘｑへの写像をフロベニウス写像と呼ぶ。また、整数ｎに関して、ｘから
【００６３】
【数３１】
0004752176.tif 000032
への写像をｑｎ乗フロベニウス写像と呼ぶ。
【００６４】
（３）楕円曲線のフロベニウス写像：
ｍを整数、ｑを素数またはその冪とする。有限体ＧＦ（ｑ）上定義された楕円曲線
Ｅ／ＧＦ（ｑ）：ｙ２＋ａ１ｘｙ＋ａ３ｙ＝ｘ３＋ａ２ｘ２＋ａ４ｘ＋ａ６    （３）
（但し、ａ１，ａ２，ａ３，ａ４，ａ５∈ＧＦ（ｑ）とする）。上のＧＦ（ｑｍ）有理点Ｒに対して、
【００６５】
【数３２】
0004752176.tif 000033
なるφを楕円曲線のフロベニウス写像と呼ぶ。有限体のフロベニウス写像の（２）式の性質により、点Ｒが楕円曲線Ｅ／ＧＦ（ｑ）上の点であるなら、点φＲも楕円曲線Ｅ／ＧＦ（ｑ）上の点である。一般に、Ｅ／ＧＦ（ｑ）上の点の楕円加算及び楕円スカラー倍演算は、与えられる点の座標に関するＧＦ（ｑ）係数有理写像で与えられる。従って有限体のフロベニウス写像の（２）式の性質により以下の性質が成り立つので、フロベニウス写像φは、線形空間Ｅ［Ｌ］の線形変換である。
【００６６】
−楕円曲線のフロベニウス写像は、Ｅ／ＧＦ（ｑ）上の自己準同型写像である。即ち、
φ（Ｒ１＋Ｒ２）≒（φＲ１）＋（φＲ２）
−楕円スカラー倍と楕円曲線のフロベニウス写像は可換である。即ち、
φ（ｋＲ）＝ｋ（φＲ）
−特に、Ｅ［Ｌ］上の点はフロベニウス写像によりＥ［Ｌ］上の点に移る。即ち、
【００６７】
【数３３】
0004752176.tif 000034
ｎを整数として、一般にｑｎ乗フロベニウス写像φｎは、
【００６８】
【数４３】
0004752176.tif 000035
と定義されるが、上記のことは、ｑｎ乗フロベニウス写像φｎでも同様に成立する。
【００６９】
（４）  フロベニウス写像の固有空間と射影：
参考文献「イアン・Ｆ・ブラケ，ガディエル・セロッシ，ナイジェル・Ｐ・スマート＝著、鈴木次郎＝訳，『楕円曲線暗号』、ｐ１１２出版，ピアソン・エデュケーション、ISBN4-89471-431-0」にあるように、フロベニウス写像φは、上記（３）式上の任意のＧＦ（ｑｍ）有理点Ｒに対して、
（φ２−ｔφ＋ｑ）Ｒ＝Ｏ                      （４）
を満たす。（但し、ｔは、ｑ，ａ１，ａ２，ａ３，ａ４，ａ６によって一意に決定される整数）φに関する多項式φ２−ｔφ＋ｑを特性多項式と呼ぶ。考える楕円曲線をＥ［Ｌ］（但し、Ｌは素数）に限定すると、スカラー倍はＺ／ＬＺで考えればよい。
【００７０】
Ｚ／ＬＺ係数の特性多項式では、分解体上で、
φ２−ｔφ＋ｑ＝（φ−λ1）（φ−λ２）
と分解でき、λ１、λ２をフロベニウス写像φの固有値と呼ぶ。以下、λ１、λ２∈Ｚ／ＬＺで、かつ、λ１≠λ２なる時を考える。線形空間Ｅ［Ｌ］の線形変換
【００７１】
【数３５】
0004752176.tif 000036
を
【００７２】
【数３６】
0004752176.tif 000037
と定義すると、任意のＥ［Ｌ］上の点Ｒに対して、
【００７３】
【数３７】
0004752176.tif 000038
なるＥ［Ｌ］上の点Ｐ，Ｑが存在し、点Ｒは、
Ｒ＝Ｐ＋Ｑ                                          （７）
と一意に分解できる。線形空間Ｅ［Ｌ］の線形変換
【００７４】
【数３８】
0004752176.tif 000039
による像
【００７５】
【数３９】
0004752176.tif 000040
を、フロベニウス写像φの固有値λ１に関する固有空間とよび、固有空間
【００７６】
【数４０】
0004752176.tif 000041
上の任意の点Ｐに関して、
φＰ＝λ１Ｐ
が成立する。Ｅ［Ｌ］から固有空間
【００７７】
【数４１】
0004752176.tif 000042
への準同型写像を
【００７８】
【数４２】
0004752176.tif 000043
への射影と呼ぶ。線形変換
【００７９】
【数４３】
0004752176.tif 000044
は、
【００８０】
【数４４】
0004752176.tif 000045
への射影である。同様に、
【００８１】
【数４５】
0004752176.tif 000046
による像
【００８２】
【数４６】
0004752176.tif 000047
を、フロベニウス写像φの固有値λ２に関する固有空間と呼び、固有空間
【００８３】
【数４７】
0004752176.tif 000048
上の任意の点Ｑに関して
φＱ＝λ２Ｑ
が成立する。Ｅ［Ｌ］から固有空間
【００８４】
【数４８】
0004752176.tif 000049
への準同型写像を
【００８５】
【数４９】
0004752176.tif 000050
への射影と呼ぶ。線形変換
【００８６】
【数５０】
0004752176.tif 000051
は、
【００８７】
【数５１】
0004752176.tif 000052
への射影である。上記の（７）式の分解をフロベニウス写像φの固有空間に関する固有分解と呼ぶ。固有空間は、それぞれ、位数Ｌの巡回群となり、
【００８８】
【数５２】
0004752176.tif 000053
である。一般に、ｑｎ乗フロベニウス写像φｎに関してもＥ［Ｌ］に関するＺ／ＬＺ係数の特性多項式
（φｎ）２−ｔｎ（φｎ）＋ｑｎ＝（φｎ−λ１ｎ）（φｎ−λ２ｎ）
（ｔｎは、ｔ，ｎ，ｑによって決まる整数）を考えることにより、固有値、固有空間、固有分解、射影等を構成できる。本発明をｑｎ乗フロベニウス写像φｎを使っても実現できるので、以降、フロベニウス写像φと云った場合、単なるｑ乗フロベニウス写像だけでなく、ｑｎ乗フロベニウス写像も含むものとする。
【００８９】
（５）ペアリング：
μLを楕円曲線の定義体Kの代数閉体上の乗法単位元１のL乗根の作る乗法群とする。参考文献「Alfred J.Menezes,『ELLIPTIC CUEVE PUBLIC KEY CEYPTOSYSTEMS』pp.61-81, 出版KLUWER ACADEMIC PUBLISHERS,ISBN0-7923-9368-6にあるように、ペアリングｅLとは、
ｅＬ：E[L]×E[L]→μＬ
なる関数で、以下の性質を持つ。
【００９０】
−Ｅ［Ｌ］上の任意の点Ｒ１に対して、ｅＬ（Ｒ１，Ｒ１）＝１．
−Ｅ［Ｌ］上の任意の２点Ｒ１，Ｒ２に対して、ｅＬ（Ｒ１，Ｒ２）
＝ｅＬ（Ｒ２，Ｒ１）−１
−Ｅ［Ｌ］上の任意の３点Ｒ１，Ｒ２，Ｒ３に対して、
ｅＬ（Ｒ１＋Ｒ２，Ｒ３）＝ｅＬ（Ｒ４，Ｒ３）ｅＬ（Ｒ２，Ｒ３）であり、
ｅＬ（Ｒ１，Ｒ２＋Ｒ３）＝ｅＬ（Ｒ１，Ｒ２）ｅＬ（Ｒ１，Ｒ３）
−Ｅ［Ｌ］上の任意の点Ｒ１に対して、ｅＬ（Ｒ１，Ｏ）＝１さらに、
Ｅ［Ｌ］上のある点Ｒ１がＥ［Ｌ］上の全ての点Ｒ２に対して、ｅＬ（Ｒ１，Ｒ２）＝１を満たすなら、Ｒ１＝Ｏ．
（６）  射影を用いた一方向性関数：
以下、Ｌが十分大きいとして、Ｅ［Ｌ］に関して、フロベニウス写像φの固有値λ１、λ２がλ１，λ２∈Ｚ／ＬＺでかつλ１≠λ２なる場合を考える固有空間
【００９１】
【数５３】
0004752176.tif 000054
の任意の生成元Ｐ及び固有空間
【００９２】
【数５４】
0004752176.tif 000055
の任意の生成元Ｑを用いて、Ｅ［Ｌ］上の任意の点Ｒは、ｋ１，ｋ２∈Ｚ／ＬＺとして、
Ｒ＝ｋ１Ｐ＋ｋ２Ｑ
と書ける。Ｒによって生成される巡回群（Ｒ）上の任意の点Ｒ１から、固有空間
【００９３】
【数５５】
0004752176.tif 000056
あるいは、固有空間
【００９４】
【数５６】
0004752176.tif 000057
への射影は、各々、前述の（５）、（６）式に従って、楕円加算、楕円逆元、楕円スカラー倍、フロベニウス写像を用いて、効率的に計算することができる。一方、ｋ１≠０かつｋ２≠０なる時、Ｒ１の射影
【００９５】
【数５７】
0004752176.tif 000058
あるいは、
【００９６】
【数５８】
0004752176.tif 000059
のどちらか一方からＲ１を求めることは、楕円曲線Ｅが特別な場合を除いて、一般には困難であると考えられる。この一方向性関数に関して次のことがわかる。
【００９７】
−ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）に関して、Ｅ（ＧＦ（ｑ））をＥ／ＧＦ（ｑ）のＧＦ（ｑ）有理点とし、Ｅ（ＧＦ（ｑｍ））をＥ／ＧＦ（ｑ）のＧＦ（ｑｍ）有理点とする。Ｌ│＃Ｅ（ＧＦ（ｑ））でかつ、
【００９８】
【数５９】
0004752176.tif 000060
とし、Ｌ２│＃Ｅ（ＧＦ（ｑｍ））とする。このとき、λ１＝１及び、λ２＝ｑmod Ｌとできる。ｍは、Ｌに比べて十分小さいとする。このとき、例えば、前述の参考文献記載の方法のように、効率的に計算可能なペアリングｅＬが存在する。
【００９９】
−上記のような楕円曲線に関して、固有空間
【０１００】
【数６０】
0004752176.tif 000061
または、固有空間の
【０１０１】
【数６１】
0004752176.tif 000062
のどちらか一方から巡回群（Ｒ）への同型写像で、単一の有理写像で記述できるものは存在しない。
【０１０２】
−上記のような楕円曲線に関して、固有空間
【０１０３】
【数６２】
0004752176.tif 000063
から巡回群（Ｒ）への同型写像が効率的に計算可能であると仮定すると、上記ペアリングｅＬを用いてＥ（ＧＦ（ｑ））の位数Ｌの部分群に対する楕円ＤＨ判定問題が効率的に計算可能となる。現在、非超特異楕円曲線の十分大きい素数位数部分群での楕円ＤＨ判定問題は効率的に計算することは困難であるという暗号学的仮定は広く信じられており、本発明の一方向性が破られれば楕円ＤＨ判定問題を利用した情報セキュリティ技術に対して新たな制約条件が必要となる。
【０１０４】
−上記のような楕円曲線に関してＥ［Ｌ］上のＯ以外の任意の点Ｒ１が生成する巡回群（Ｒ１）及び、Ｅ［Ｌ］上の任意の点Ｒ２に対して、Ｒ２∈＜Ｒ１＞であるか否かを判定する問題は上記ペアリングｅＬを用いて、効率的に判定可能で例えば以下のようになる。
【０１０５】
（６−１）第１の実施の形態／部分群上判定方法：
図３は、本発明の第１の実施の形態における部分群上元判定装置の構成を示す。同図に示す部分群上元判定装置１００は、Ｒ１，Ｒ２∈Ｅ［Ｌ］，Ｒ１≠Ｏを入力する入力部１１０、ペアリング計算部１２０、一時記憶部１３０、判定部１４０及びＲ２∈＜Ｒ１＞の真理値（∈{ＴＲＵＥ，ＦＡＬＳＥ}を出力する出力部１５０から構成される。
【０１０６】
図４は、本発明の第１の実施の形態における部分群上元判定方法のフローチャートである。
【０１０７】
まず、準備として、一時記憶領域としてｔ∈μＬを一時記憶部１３０に確保する(ステップ１０１)。
【０１０８】
入力部１１０からＲ１，Ｒ２∈Ｅ［Ｌ］，Ｒ１≠Ｏを入力する(ステップ１０２)。
【０１０９】
ペアリング計算部１２０において、ペアリングｔ←ｅＬ（Ｒ１、Ｒ２）を計算する(ステップ１０３)。
【０１１０】
判定部１４０において、ｔ＝１であれば(ステップ１０４)出力部１５０よりＴＲＵＥを出力して終了し(ステップ１０５)、ｔ≠１であれば（ステップ１０４）出力部１５０よりＦＡＬＳＥを出力して終了する(ステップ１０６)。
【０１１１】
（６−２）第２の実施の形態／一方向性関数計算方法：
上記のＥ［Ｌ］上の任意の点Ｒに対して、その射影、例えば、
【０１１２】
【数６３】
0004752176.tif 000064
を計算するためには、前述の（５）式に従って、以下の処理を行う。
【０１１３】
図５は、本発明の第２の実施の形態における一方向性関数計算装置の構成を示す。同図に示す一方向性関数計算装置２００は、Ｒ∈Ｅ［Ｌ］を入力する入力部２３０、固定値計算部２１０、スカラー値設定部２２０、フロベニウス写像計算部２４０、一時記憶部２５０、楕円スカラー倍計算部２６０、楕円減算部２７０、出力部２８０から構成される。
【０１１４】
図６は、本発明の第２の実施の形態における一方向性関数計算方法のフローチャートである。
【０１１５】
まず、準備処理として、一時記憶Ｒ１，・・Ｒ４∈Ｅ［Ｌ］を予め一時記憶部２５０に確保しておく(ステップ２０１)。さらに、固定値計算部２１０において、固有値λ２∈Ｚ／ＬＺを予め求めておく(ステップ２０２)。また、スカラー値設定部２２０において、
【０１１６】
【数６４】
0004752176.tif 000065
を、
【０１１７】
【数６５】
0004752176.tif 000066
として予め求めておく(ステップ２０３)。
【０１１８】
入力部２３０より、
【０１１９】
【数６６】
0004752176.tif 000067
を入力し(ステップ２０４)、フロベニウス写像計算部２４０において、フロベニウス写像Ｒ１←φＲを計算し、一時記憶部２５０に格納し(ステップ２０５)、楕円スカラー倍計算部２６０において、楕円スカラー倍Ｒ２←λ２Ｒを計算し、一時記憶部２５０に格納し(ステップ２０６)。楕円減算部２７０において、楕円減算Ｒ３←Ｒ１−Ｒ２を計算し、一時記憶部２５０に格納し(ステップ２０７)、再度楕円スカラー倍計算部２６０において、楕円スカラー倍
【０１２０】
【数６７】
0004752176.tif 000068
を計算し、一時記憶部２５０に格納する(ステップ２０８)。最後に、出力部２８０は、一時記憶部２５０に格納されているＲ４を出力する(ステップ２０９)。
【０１２１】
（６−３）第３の実施の形態／一方向性関数計算方法：
上記の（６−２）の一方向性関数計算方法の演算コストは、フロベニウス写像１回、楕円減算１回、楕円スカラー倍２回、であり、演算コストの大部分を占めるのは、楕円スカラー倍２回の部分である。ところで、ｋ≠０なる任意のｋ∈Ｚ／ＬＺに対して、線形演算
【０１２２】
【数６８】
0004752176.tif 000069
も固有空間
【０１２３】
【数６９】
0004752176.tif 000070
への射影であるから、上記の一方向性を持つ。従って、ｋ＝λ１−λ２等としておけば、上記の（６−２）の楕円スカラー倍の演算を１回分削減できる。
【０１２４】
図７は、本発明の第３の実施の形態における一方向性関数計算装置の構成を示す。同図に示す一方向性関数計算装置３００は、Ｒ∈Ｅ［Ｌ］を入力する入力部３３０、固有値計算部３１０、フロベニウス写像計算部３４０、一時記憶部３５０、楕円スカラー倍計算部３６０、楕円減算部３７０、及び出力部３８０から構成される。
【０１２５】
図８は、本発明の第３の実施の形態における一方向性関数計算方法のフローチャートである。
【０１２６】
まず、準備処理として、一時記憶領域として、Ｒ１，…Ｒ３∈Ｅ［Ｌ］を予め一時記憶部３５０に確保しておく(ステップ３０１)。次に、固有値計算部３１０において、λ２∈Ｚ／ＬＺを予め求めておく(ステップ３０２)。
【０１２７】
入力部３１０より、Ｒ∈Ｅ［Ｌ］を入力し(ステップ３０３)、フロベニウス写像計算部３４０においてフロベニウス写像Ｒ１←φＲを計算し、Ｒ１を一時記憶部３５０に格納する(ステップ３０４)。
【０１２８】
楕円スカラー倍計算部３６０において、楕円スカラー倍Ｒ２←λ２Ｒを計算し、Ｒ２を一時記憶部３５０に格納する(ステップ３０５)。
【０１２９】
楕円減算部３７０において、楕円減算Ｒ３←Ｒ１−Ｒ２を計算し、Ｒ３を一時記憶部３５０に格納する(ステップ３０６)。
【０１３０】
最後に、出力部３８０が一時記憶部３５０に格納されているＲ３を出力する(ステップ３０７)。
【０１３１】
（６−４）第４の実施の形態／トレースマップを用いた一方向性関数計算方法：
上記の（６−３）の一方向性関数の演算コストは、フロベニウス写像１回、楕円減算１回、楕円スカラー倍１回であり、依然として楕円スカラー倍１回と同程度の演算コストが必要である。ところで、楕円曲線Ｅ／ＧＦ（ｑ）がＬ２│＃Ｅ（ＧＦ（ｑ））でかつＬ２│＃Ｅ（ＧＦ（ｑｍ））なる場合、特性多項式は、
φ２−ｔφ＋ｑ＝(φ−１)(φ−ｑ)  （mod  Ｌ）
と分解できる。即ち、固有値は１及びｑ mod  Ｌである。λ１＝１、λ２＝ｑmodＬとすると、線形変換
【０１３２】
【数７０】
0004752176.tif 000071
は、固有空間
【０１３３】
【数７１】
0004752176.tif 000072
への射影になる。線形変換をトレースマップと呼ぶ。一般に、ｍ＜Ｌであるが、ｍがlog2Lに比べて小さいとき以下の一方向性関数計算方法は、一方向性関数計算方法（６−３）より高速である。
【０１３４】
図９は、本発明の第４の実施の形態における一方向性関数計算装置の構成を示す。同図に示す一方向性関数計算装置４００は、Ｒ∈Ｅ［Ｌ］を入力する入力部４１０、初期値設定部４２０、一時記憶部４３０、点計算部４４０、出力部４５０から構成される。
【０１３５】
図１０は、本発明の第４の実施の形態における一方向性関数計算方法のフローチャートである。
【０１３６】
まず、準備処理として、一時記憶領域Ｒ１∈Ｅ［Ｌ］、ｉ∈{０，…，ｍ}を一時記憶部４３０に確保する(ステップ４０１)。
【０１３７】
初期値設定部４２０において、一時記憶部４３０のＲ１←Ｏ，ｉ←０とする(ステップ４０２)。
【０１３８】
次に、点計算部４４０において、Ｒ１←Ｒ１＋φｉＲとし(ステップ４０３)、Ｒ１を一時記憶部４３０に格納し(ステップ４０４)、ｉ←ｉ＋１とする(ステップ４０５)。ここで、ｉ＜ｍであれば、再度ステップ４０３の処理を行い(ステップ４０６)、ｉ≧ｍであれば、出力部４５０は、一時記憶部４３０に格納されているＲ１を出力して終了する(ステップ４０７)。
【０１３９】
（６−５）第５の実施の形態／加算連鎖を用いた一方向関数計算：
本実施の形態では、計算可能な拡大における一般的なｍ（〜log２Ｌ）に関して、トレースマップをより効率よく計算する方法を考える。一般の正整数ｎに対して
【０１４０】
【数７２】
0004752176.tif 000073
とするなら、上記の第４の実施の形態における、一方向性関数計算方法と同様の方法で、Ｔｎ（Ｒ）を計算するとｎ−１回の楕円加算が発生し、これが演算の律速段階となる。いま仮に、ｃを正整数としてｎ＝２ｃだったとすると、
【０１４１】
【数７３】
0004752176.tif 000074
と書くことができる。この時、
【０１４２】
【数７４】
0004752176.tif 000075
のような演算方法を用いると、ｃ回即ち、log２ｎ回の楕円加算でＴｎ（Ｒ）を計算することができる。このような計算法は、例え、ｎが２の冪でなかったとしても一般に構成することが可能であり、例えば、次のように構成する。
【０１４３】
ｉ，ｊ，ｋを整数として整数(１＝)ｎ０，…ｎｃ（＝ｎ）を
ｎ０＝１，  ｎｉ＝ｎｊ＋ｎｋ，  （ｊ，ｋ＜ｉ）
とする。整数列ｎ０，…，ｎｃをｎの加算連鎖と呼ぶ。ｎの加算連鎖を用いてＴｎ（Ｒ）の計算を次のように実行することができる。まず、ｎの加算連鎖ｎ０，…，ｎｃを考える。加算連鎖のｎｉ＝ｎｊ＋ｎｋ，（ｊ，ｋ＜ｉ）なるｉ，ｊ，ｋの対応に従って、ｉ＝０，…，ｃに対して、
【０１４４】
【数７５】
0004752176.tif 000076
なる演算により、Ｒ０，…，Ｒｃを求める。このとき、
【０１４５】
【数７６】
0004752176.tif 000077
が成立する。
【０１４６】
【数７７】
0004752176.tif 000078
であるから、Ｒｃが求めるＴｎ（Ｒ）となる。ｎの最短の加算連鎖の長さｃは、例えば、２進計算法等を用いることによって最悪でもｃ≦２log２ｎに抑えることができる。即ち、Ｒｃも最悪２log２ｎ回程度の楕円加算で求めることができる。Ｔｎ（Ｒ）を効率よく求めたいなら、効率の良いｎの加算連鎖を与えればよい。参考文献「Knuth著『The Art of Computer Programming』VOLUME 2 Seminumerical Algorithms Third Edition,p.465出版 Addison Wesley,ISBN0-201-89684-2」には、１以上１００以下の整数の加算回数に関する最適加算連鎖のツリー図が掲載されている。そのような加算連鎖を用いることによって、Ｔｎ（Ｒ）の計算を最適化できる。
【０１４７】
この方法を使って、トレースマップを用いた一方向性関数を以下のように計算することができる。
【０１４８】
図１１は、本発明の第５の実施の形態における一方向性関数計算装置の構成を示す。同図に示す一方向性関数計算装置５００は、Ｒ∈Ｅ［Ｌ］を入力する入力部５１０、初期値設定部５２０、一時記憶部５３０、加算連鎖計算部５４０、出力部５５０から構成される。
【０１４９】
図１２は、本発明の第５の実施の形態における一方向性関数計算方法のフローチャートである。
【０１５０】
まず、準備処理として、使用するｍの加算連鎖ｎ０＝１，ｎｉ＝ｎｊ＋ｎｋ，  （ｊ，ｋ＜ｉ），ｎｃ＝ｍを決めておく(ステップ５０１)。但し、必ずしも最適な加算連鎖を用いる必要はない。例えば、２進計算法を用いることができる。
【０１５１】
また、一時記憶領域Ｒ０，…，Ｒｃ∈Ｅ［Ｌ］，ｉ∈{０，…，ｃ}を予め一時記憶部５３０に確保しておく(ステップ５０２)。
【０１５２】
初期値設定部５２０において、一時記憶部５３０に対して、Ｒ０←Ｒ，ｉ←０を設定する(ステップ５０３)。
【０１５３】
入力部５１０からＲ∈Ｅ［Ｌ］を入力する(ステップ５０４)。
【０１５４】
加算連鎖計算部５４０は、ｉ←ｉ＋１とし(ステップ５０５)、ステップ５０１で予め決められた加算連鎖に従って、ｉに対応するｊ，ｋ＜ｉを決定し、
【０１５５】
【数７８】
0004752176.tif 000079
とし、計算結果Ｒｉを一時記憶部５３０に格納する(ステップ５０６)。
【０１５６】
ここで、ｉ＜ｃであれば(ステップ５０７)、ステップ５０５以降の処理を繰り返し、ｉ≧ｃであれば、出力部５５０において、一時記憶部５３０からＲｃを読み出して出力するステップ５０８）。
【０１５７】
（６−６）第６の実施の形態／一方向性関数計算方法：
前述の第５の実施の形態の一方向性関数計算方法で必要とされた一時記憶領域Ｒ０，…，Ｒｃは、加算連鎖によっては必ずしもｃ＋１個必要な訳ではない。工夫により、一時記憶領域を削減することができる。加算連鎖の数列自体も、動作中に決定することが可能である。本実施の形態では、例えば、２進計算法を用いる場合について説明する。
【０１５８】
図１３は、本発明の第６の実施の形態における一方向性関数計算装置の構成を示す。同図に示す一方向性関数計算装置６００は、Ｒ∈Ｅ［Ｌ］を入力する入力部６１０、初期値設定部６２０、一時記憶部６３０、加算連鎖計算部６４０、出力部６５０から構成される。
【０１５９】
図１４は、本発明の第６の実施の形態における一方向性関数計算方法のフローチャートを示す。
【０１６０】
まず、準備処理として、使用するｍの加算連鎖は２進計算法とし、ｍの２進展開ｍｉ∈{０，１}を、
【０１６１】
【数７９】
0004752176.tif 000080
とする（ステップ６０１）。但し、ｍｃ＝１とする。
【０１６２】
また、一時記憶領域Ｒ０∈Ｅ［Ｌ］、ｉ∈{０，…，ｃ}，ｊ∈{１，…，ｍ}を予め一時記憶部６３０に確保しておく(ステップ６０２)。
【０１６３】
初期値設定部６２０において、一時記憶部６２０の値をＲ０←Ｒ，ｊ←１、ｉ←ｃとする(ステップ６０３)。
【０１６４】
入力部６１０からＲ∈Ｅ［Ｌ］を入力する(ステップ６０４)。
【０１６５】
加算連鎖計算部６４０は、ｉ←ｉ−１とし(ステップ６０５)、Ｒ０←φｊＲ０＋Ｒ０，ｊ←ｊ＋１とし(ステップ６０６)、ｍｉ＝１であれば(ステップ６０７)、加算連鎖計算部６０４は、Ｒ０←φＲ０＋Ｒ、ｊ←ｊ＋１とし(ステップ６０８)、ｉ＞０であれば(ステップ６０９)、ステップ６０５に移行し、ｉ≦０であれば(ステップ６０９)、出力部６５０において、一時記憶部６３０から最終的なＲ０を読み出して、出力する(ステップ６１０)。
【０１６６】
ｍが２進数で表現されている場合、上記のステップ６０６の前半でのｊの値は、その時点でのｉの値を使って、ｍの先頭からｃ−１ビットを符号なし整数として見て決定してもよいし、その場合、ステップ６０３、６０６、６０７でｊの値を設定する必要はなく、一時記憶領域としてｊを確保することもない。
【０１６７】
本発明は、上記の第１の実施の形態から第６の実施の形態における動作をプログラムとして構築し、一方向性関数計算装置、及び、部分群上元判定装置として利用されるコンピュータの記憶手段にインストールし、ＣＰＵ等の制御手段により実行させる、または、ネットワークを介して流通させることも可能である。
【０１６８】
また、構築されたプログラムを、一方向性関数計算装置、部分群上元判定装置として利用されるコンピュータに接続されたハードディスク装置や、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、実施する際に、これらのコンピュータにインストールすることも可能である。
【０１６９】
また、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１７０】
本発明は、計算量理論に基づく情報セキュリティ技術に適用することが可能である。
【図面の簡単な説明】
【０１７１】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の第１の実施の形態における部分群上元判定装置の構成図である。
【図４】本発明の第１の実施の形態における部分群上元判定方法のフローチャートである。
【図５】本発明の第２の実施の形態における一方向性関数計算装置の構成図である。
【図６】本発明の第２の実施の形態における一方向性関数計算方法のフローチャートである。
【図７】本発明の第３の実施の形態における一方向性関数計算装置の構成図である。
【図８】本発明の第３の実施の形態における一方向性関数計算方法のフローチャートである。
【図９】本発明の第４の実施の形態における一方向性関数計算装置の構成図である。
【図１０】本発明の第４の実施の形態における一方向性関数計算方法のフローチャートである。
【図１１】本発明の第５の実施の形態における一方向性関数計算装置の構成図である。
【図１２】本発明の第５の実施の形態における一方向性関数計算方法のフローチャートである。
【図１３】本発明の第６の実施の形態における一方向性関数計算装置の構成図である。
【図１４】本発明の第６の実施の形態における一方向性関数計算方法のフローチャートである。
【符号の説明】
【０１７２】
１００  部分群上元判定装置
１１０  入力部
１２０  ペアリング計算部
１３０  一時記憶部
１４０  判定部
１５０  出力部
２００  一方向性関数計算装置
２１０  固定値計算部
２２０  スカラー倍設定部
２３０  入力部
２４０  フロベニウス写像計算部
２５０  一時記憶部
２６０  楕円スカラー倍計算部
２７０  楕円減算部
２８０  出力部
３００  一方向性関数計算装置
３１０  固有値計算部
３３０  入力部
３４０  フロベニウス写像計算部
３５０  一時記憶部
３６０  楕円スカラー倍計算部
３７０  楕円減算部
３８０  出力部
４００  一方向性関数計算装置
４１０  入力部
４２０  初期値設定部
４３０  一時記憶部
４４０  点計算部
４５０  出力部
５００  一方向性関数計算装置
５１０  入力部
５２０  初期値設定部
５３０  一時記憶部
５４０  加算連鎖計算部
５５０  出力部
６００  一方向性関数計算装置
６１０  入力部
６２０  初期値設定部
６３０  一時記憶部
６４０  加算連鎖計算部
６５０  出力部
【図１】
0004752176.tif 000091
【図２】
0004752176.tif 000092
【図３】
0004752176.tif 000093
【図４】
0004752176.tif 000094
【図５】
0004752176.tif 000095
【図６】
0004752176.tif 000096
【図７】
0004752176.tif 000097
【図８】
0004752176.tif 000098
【図９】
0004752176.tif 000099
【図１０】
0004752176.tif 000100
【図１１】
0004752176.tif 000101
【図１２】
0004752176.tif 000102
【図１３】
0004752176.tif 000103
【図１４】
0004752176.tif 000104