(57)【要約】【課題】安全かつ少ない演算量で楕円曲線上の等分点からなる群上の元を標本する。【解決手段】有限体上で定義された第１楕円曲線の位数がｎであり、当該有限体の拡大体上で定義された第２楕円曲線の位数がｍ×ｎ＞ｎであり、αがｍと互いに素な整数であり、入力された拡大体の元を第２楕円曲線上の対応点へ写し、当該対応点の楕円α×ｍ倍点を第２楕円曲線上のｎ等分点として得る。【選択図】図１
2016126227.tif 000002
【特許請求の範囲】
【請求項１】
有限体上で定義された第１楕円曲線の位数がｎであり、前記有限体の拡大体上で定義された第２楕円曲線の位数がｍ×ｎ＞ｎであり、αがｍと互いに素な整数であり、
入力された前記拡大体の元を前記第２楕円曲線上の対応点へ写す写像部と、
前記対応点の楕円α×ｍ倍点を前記第２楕円曲線上のｎ等分点として得る楕円倍算部と、
を有する標本装置。
【請求項２】
請求項１の標本装置であって、
α＝１である標本装置。
【請求項３】
請求項１または２の標本装置であって、
α≠１であり、
前記楕円倍算部は、前記第２楕円曲線上のフロベニウス写像を用いて前記第２楕円曲線上の楕円α×ｍ倍点を得、
前記第２楕円曲線上のフロベニウス写像を用いて前記第２楕円曲線上の楕円α×ｍ倍点を得るための演算量は、前記第２楕円曲線上の楕円ｍ倍算の演算量よりも小さい、標本装置。
【請求項４】
請求項１から３の何れかの標本装置であって、
前記第１および第２楕円曲線がＢＮ曲線であり、
ｎ＝３６ｕ４＋３６ｕ３＋１８ｕ２＋６ｕ＋１であり、
ｍ＝３６ｕ４＋３６ｕ３＋３０ｕ２＋６ｕ＋１であり、
ｕが整数の媒介変数である標本装置。
【請求項５】
請求項４の標本装置であって、
前記楕円倍算部は、前記第２楕円曲線上のフロベニウス写像ψを用いた演算６ｕ−ψ３＋３ψ２−ψまたは前記演算６ｕ−ψ３＋３ψ２−ψに変更可能な前記フロベニウス写像ψを用いた演算によって、前記第２楕円曲線上の楕円α×ｍ倍点を得る、標本装置。
【請求項６】
請求項４または５の標本装置であって、
前記拡大体の元がｔであり、（ｘ０，ｙ０）が無限遠点を除く前記第２楕円曲線上のｘ０ｙ０≠０なる任意の点であり、ξが１の原始３乗根であり、ｇ（ｘ）＝ｘ３＋ｂ’であり、ｂ’が前記拡大体の元であり、χ（−ｔ）＝−χ（ｔ）およびχ（０）＝１を満たし、
【数５】
2016126227.tif 000007
であり、
前記写像部は、
ｔ＝０であれば、（ｘ１（ｔ），χ（ｔ）ｇ（ｘ１（ｔ））１／２）を前記対応点とし、
１＋ｔ２＝０であれば、（ｘ３（ｔ），χ（ｔ）ｇ（ｘ３（ｔ））１／２）を前記対応点とし、
ｔ≠０かつ１＋ｔ２≠０であれば、ｇ（ｘｊ（ｔ））１／２が前記拡大体の元となる最小のｊ∈｛１，２，３｝についての（ｘｊ（ｔ），χ（ｔ）ｇ（ｘｊ（ｔ））１／２）を前記対応点とする、標本装置。
【請求項７】
有限体上で定義された第１楕円曲線の位数がｎであり、前記有限体の拡大体上で定義された第２楕円曲線の位数がｍ×ｎであり、ｍ×ｎ＞ｎであり、αがｍと互いに素な整数であり、
写像部が、入力された前記拡大体の元を前記第２楕円曲線上の対応点へ写す写像ステップと、
楕円倍算部が、前記対応点の楕円α×ｍ倍点を前記第２楕円曲線上のｎ等分点として得る楕円倍算ステップと、
を有する標本方法。
【請求項８】
請求項１から６の何れかの標本装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上の点からなる特定の群上の元を標本する技術に関する。
【背景技術】
【０００２】
楕円曲線暗号において、平文やハッシュ値といった任意の文字列をどのように楕円曲線上の点へ写すかという問題について長い間関心が注がれてきた。重要なpairing-friendly楕円曲線の一つにBarreto-Naehrig曲線（ＢＮ曲線）がある（例えば、非特許文献１等参照）。代数閉体上では、同型となる次の２つの楕円曲線によってＢＮ曲線が定義される。
Ｅ／Ｆｐ：ｙ２＝ｘ３＋ｂ
Ｅ’／Ｆρ：ｙ２＝ｘ３＋ｂ’
ただし、Ｅ／Ｆｐは位数ｐ（ただしｐは素数）の有限体Ｆｐ上で定義された楕円曲線であり、Ｅ’／Ｆρは位数ρ＝ｐ２の有限体Ｆρ（Ｆｐを基礎体とした拡大体）上で定義された楕円曲線である。Ｅ／Ｆｐの位数を＃Ｅ／Ｆｐと表記し、Ｅ’／Ｆρの位数を＃Ｅ’／Ｆρと表記する。また、Ｅ／Ｆｐのｎ等分点の集合をＥ／Ｆｐ［ｎ］と表記し、Ｅ’／Ｆρのｎ等分点の有限集合をＥ’／Ｆρ［ｎ］と表記する。これらの有限集合Ｅ／Ｆｐ［ｎ］およびＥ’／Ｆρ［ｎ］はそれぞれ郡をなし、それぞれを以下のように表記する。
Ｇ１＝Ｅ／Ｆｐ［ｎ］
Ｇ２＝Ｅ’／Ｆρ［ｎ］
【０００３】
非特許文献２には、有限体上の任意の元をＢＮ曲線上に写すアルゴリズムＦ’が開示されている。Ｅ／Ｆｐ全体がＧ１＝Ｅ／Ｆｐ［ｎ］となるように楕円曲線Ｅ／Ｆｐを設定しておけば、アルゴリズムＦ’を用いて任意の元に対応する群Ｇ１上の元を標本できる。
【０００４】
ここで強識別不可能性と許容符号化の概念を説明する。
＜強識別不可能性＞
暗号学的理想原始関数ｈへの神託照会が許されるチューリング機械Ｃに関し、Ｃの理想原始関数Ｈへの神託照会が許される実行時間ｔｓのｈの模倣器Ｓが存在し、どのような最大実行時間ｔＤ，最大照会回数ｑＤの識別器Ｄに対しても以下を満たすならば、ＣｈはＨと（ｔＤ，ｔｓ，ｑＤ，ε）−強識別不可能であるという。
【数１】
2016126227.tif 000003
ただし、｜β｜はβの絶対値を表し、Ｐｒ［γ］は事象γの確率を表し、Ｄβ，γは識別器Ｄがβ，γを照会して１と判別する事象を表し、ＣｈおよびＳＨはｈを照会するＣおよびＨを照会するＳをそれぞれ表し、εは安全変数ｋの関数値を表す。多項式限度のｔＤ，ｔｓ，ｑＤに対してεが無視可能関数であるならば、ＣｈはＨと強識別不可能であるという。
【０００５】
＜許容符号化＞
Ｗ，Ｕを有限集合とする。次の３つの性質を満たす関数Ｆ：Ｗ→Ｕをε−許容符号化という。
［計算可能性］Ｆは確定多項式時間で計算可能である。
［正規性］Ｗ上で一様に分布する確率変数ｗに対するＦ（ｗ）がＵ上の一様分布とε−統計的識別不可能である。
［標本可能性］あらゆるｕ∈Ｕに対して効率的な乱択アルゴリズムＩが存在し、入力ｕに対してアルゴリズムＩが出力するＩ（ｕ）の分布がＦ−１（ｕ）とε−統計的識別不可能である。
なお、βがγとε−統計的識別不可能とは、無視可能関数εについてβとγとの間の統計的距離がε未満であることを意味する。また「β→γ」はβをγに写す（写像する）ことを意味する。
【０００６】
＜定理＞
次のような定理が成り立つ。ｈ：｛０，１｝＊→Ｗがランダムオラクル（暗号学的理想原始関数）であり、Ｆ：Ｗ→Ｕがε−許容符号化であるとする。ｔＩをアルゴリズムＩの最大実行時間とし、ｔｓ＝２ｑＤ・ｔＩとし、ε’＝４ｑＤ・εとする。このときＦ（ｈ（・））：｛０，１｝＊→Ｕはランダムオラクル（理想原始関数）Ｈ：｛０，１｝＊→Ｕと（ｔＤ，ｔｓ，ｑＤ，ε’）−強識別不可能である。
【０００７】
＜アルゴリズムＦ’の安全性＞
しかし、前述したアルゴリズムＦ’の出力には明らかな分布の偏りがあるため、上記のランダムオラクルｈを使ってＦ’（ｈ（・））を構成しても、εを無視可能関数とすることができない。すなわち、アルゴリズムＦ’は正規性および標本可能性を持たず、ε−許容符号化とはならない。そのため、アルゴリズムＦ’は上述の定理に基づく安全性を持たない。
【０００８】
この問題を解決するため、非特許文献２では、ｈ１，ｈ２をランダムオラクルとした次のようなアルゴリズムＦ”：｛０，１｝＊→Ｅ（Ｆｑ）が提案されている。
Ｆ”：ｘ→Ｆ’（ｈ１（ｘ））＋Ｆ’（ｈ２（ｘ））
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Paulo S. L. M. Barreto1 and Michael. Naehrig, “Pairing-Friendly Elliptic Curves of Prime Order,” In B. Preneel and S. E. Tavares, editors, Selected Areas in Cryptography, 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11-12, 2005, Revised Selected Papers, Volume 3897 of Lecture Notes in Computer Science, pages 319-331, Springer, 2005.
【非特許文献２】P. Fouque and M. Tibouchi, “Indifferentiable hashing to barreto-naehrig curves,” In A. Hevia and G. Neven, editors, Progress in Cryptography, LATINCRYPT 2012 - 2nd International Conference on Cryptography and Information Security in Latin America, Santiago, Chile, October 7-10, 2012, Proceedings, Volume 7533 of Lecture Notes in Computer Science, pages 1-17, Springer, 2012.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述のアルゴリズムＦ”ではＦ’を２回計算する必要があり、計算量が多い。
【００１１】
本発明の課題は、安全かつ少ない演算量で楕円曲線上の等分点からなる群上の元を標本する技術を提供することである。
【課題を解決するための手段】
【００１２】
有限体上で定義された第１楕円曲線の位数がｎであり、当該有限体の拡大体上で定義された第２楕円曲線の位数がｍ×ｎ＞ｎであり、αがｍと互いに素な整数であり、入力された拡大体の元を第２楕円曲線上の対応点へ写し、当該対応点の楕円α×ｍ倍点を第２楕円曲線上のｎ等分点として得る。
【発明の効果】
【００１３】
本発明では、安全かつ少ない演算量で楕円曲線上の等分点からなる群上の元を標本できる。
【図面の簡単な説明】
【００１４】
【図１】図１Ａは実施形態の標本装置の機能構成を例示したブロック図である。図１Ｂは写像部の機能構成を例示したブロック図である。
【図２】図２は実施形態の楕円倍算部を例示したブロック図である。
【図３】図３Ａは実施形態の標本方法を例示したフロー図である。図３Ｂは実施形態の写像部の処理を例示したフロー図である。
【図４】図４は実施形態の楕円倍算部の処理を例示したブロック図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態を説明する。
［概要］
まず実施形態の概要を説明する。
有限体上で定義された第１楕円曲線の位数がｎであり、有限体の拡大体上で定義された第２楕円曲線の位数がｍ×ｎ＞ｎであり、αがｍと互いに素な整数であるとする。ｎ，ｍ，αは正の整数である。各実施形態では、入力された当該拡大体の元を当該第２楕円曲線上の対応点へ写し、当該対応点の楕円α×ｍ倍点を第２楕円曲線上のｎ等分点として得る。このように得られる第２楕円曲線上のｎ等分点は、それぞれ第２楕円曲線上のｍ個の互いに異なる対応点に対応する。すなわち、上述の楕円α×ｍ倍算は、第２楕円曲線上の互いに異なるｍ個の対応点を同一のｎ等分点に写す。そのため、拡大体の元を第２楕円曲線上の対応点へ写すアルゴリズムに分布の偏りがあったとしても、最終的に得られるｎ等分点の偏りは小さくなり、安全性が向上する。特に大数の法則に従う場合には、正規性および標本可能性を満たし、良く知られた効率的な楕円倍算の手法を用いれば計算可能性も満たす。そのため、ε−許容符号化の要件を満たし、本形態の方式は全体としてランダムオラクルと（ｔＤ，ｔｓ，ｑＤ，ε’）−強識別不可能となる。また、拡大体の元を第２楕円曲線上の対応点へ写すための計算は１回だけでよく、非特許文献２に開示された方式よりも計算量が少ない。以上より、安全かつ少ない演算量で楕円曲線上の等分点からなる群上の元を標本できる。
【００１６】
αはｍと互いに素であるため、第２楕円曲線上での対応点の楕円α×ｍ倍算は、当該対応点の楕円ｍ倍算を行い、さらに第２楕円曲線のｎ等分点からなる群上でα倍算することと等しい。そのため、α≠１であったとしても、対応点の楕円α×ｍ倍点は第２楕円曲線のｎ等分点からなる群の何れかの元となる。そのため、α＝１であってもよいし、α≠１であってもよい。通常の楕円倍算ではα＝１の場合の方がα≠１の場合よりも演算量が小さい。一方、α≠１とした場合でも、第２楕円曲線上のフロベニウス写像を用いて楕円α×ｍ倍点を得ることで、通常の第２楕円曲線上の楕円ｍ倍算よりも演算量を小さくできる場合もある。例えば、第１および第２楕円曲線がＢＮ曲線であり、ｎ＝３６ｕ４＋３６ｕ３＋１８ｕ２＋６ｕ＋１であり、ｍ＝３６ｕ４＋３６ｕ３＋３０ｕ２＋６ｕ＋１であり、ｕが整数の媒介変数である場合、第２楕円曲線上のフロベニウス写像ψを用いた演算６ｕ−ψ３＋３ψ２−ψによって第２楕円曲線上の楕円α×ｍ倍点を得てもよい。この演算量は、通常の楕円倍算を行って楕円ｍ倍点を得るよりも少ない。また、フロベニウス写像ψはψ４−ψ２＋１＝０の関係を満たす。そのため、この関係を用いて６ｕ−ψ３＋３ψ２−ψに変更可能な他の演算によって、第２楕円曲線上の楕円α×ｍ倍点を得てもよい。その他、α＝１とし、第２楕円曲線上のフロベニウス写像を用いて楕円α×ｍ倍点を得てもよい。
【００１７】
［第１実施形態］
次に第１実施形態を説明する。
本形態では、第１および第２楕円曲線が以下のＢＮ曲線である場合を例示する。
Ｅ／Ｆｐ：ｙ２＝ｘ３＋ｂ
Ｅ’／Ｆρ：ｙ２＝ｘ３＋ｂ’
ただし、Ｅ／Ｆｐは位数ｐの有限体Ｆｐ上で定義された楕円曲線（第１楕円曲線）であり、Ｅ’／Ｆρは位数ρ＝ｐ２の有限体Ｆρ（Ｆｐを基礎体とした拡大体）上で定義された楕円曲線（第２楕円曲線）である。ｘおよびｙは変数（座標値）であり、ｂ∈Ｆｐおよびｂ’∈Ｆρは定数である。Ｅ／Ｆｐの位数を＃Ｅ／Ｆｐと表記し、Ｅ’／Ｆρの位数を＃Ｅ’／Ｆρと表記する。ｎ＝＃Ｅ／Ｆｐとし、ｍ＝（＃Ｅ’／Ｆρ）／（＃Ｅ／Ｆｐ）とし、ｕを整数の媒介変数とすると、ｐ，ｎ，ｍは以下の関係を満たす。
ｐ＝３６ｕ４＋３６ｕ３＋２４ｕ２＋６ｕ＋１
ｎ＝３６ｕ４＋３６ｕ３＋１８ｕ２＋６ｕ＋１
ｍ＝３６ｕ４＋３６ｕ３＋３０ｕ２＋６ｕ＋１
このようなｍは位数の余因数と呼ばれ、＃Ｅ’／Ｆρ＝ｍ×ｎ＞ｎとなる。ｐは素数であり、ｎおよびｍは素数であってもよいし、素数以外の正整数であってもよい。
【００１８】
＜構成＞
図１Ａに例示するように、本形態の標本装置１は、入力部１１と写像部１２と楕円倍算部１３と出力部１４とメモリ１５を有する。図１Ｂに例示するように、本形態の写像部１２は、第１判定部１２１と第２判定部１２２と第３判定部１２３と出力部１２４を有する。標本装置１は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。以降では説明を省略するが、標本装置１の各部に入出力される情報は、メモリ１５に格納され、必要に応じて読み出される。
【００１９】
＜処理＞
図３Ａを用いて本形態の処理を説明する。
まず、有限体Ｆρ（拡大体）の任意の元ｔ∈Ｆρが入力部１１に入力され、写像部１２に送られる（ステップＳ１１）。写像部１２は、送られた元ｔに対して後述するアルゴリズムｆを適用し、元ｔを楕円曲線Ｅ’／Ｆρ上の対応点ｆ（ｔ）＝（ｔｘ，ｔｙ）∈Ｅ’／Ｆρへ写す。得られた対応点ｆ（ｔ）は楕円倍算部１３に送られる（ステップＳ１２）。楕円倍算部１３は、送られた対応点ｆ（ｔ）に対し、楕円曲線Ｅ’／Ｆρ上の楕円ｍ倍算（ｖｘ，ｖｙ）＝［ｍ］ｆ（ｔ）∈Ｅ’／Ｆρを行う。楕円曲線Ｅ’／Ｆρの位数＃Ｅ’／Ｆρはｎ×ｍであるため、対応点ｆ（ｔ）の楕円ｍ倍点（ｖｘ，ｖｙ）は＃Ｅ’／Ｆρ上のｎ等分点となる。＃Ｅ’／Ｆρ上のｎ等分点からなる有限集合＃Ｅ’／Ｆρ［ｎ］は群（本形態では巡回群）をなし、（ｖｘ，ｖｙ）はその群の元（ｖｘ，ｖｙ）∈＃Ｅ’／Ｆρ［ｎ］となる（ステップＳ１３）。元（ｖｘ，ｖｙ）は出力部１４に送られ、出力部１４は元（ｖｘ，ｖｙ）を出力する（ステップＳ１４）。
【００２０】
≪アルゴリズムｆの詳細の例示≫
アルゴリズムｆの詳細を例示する。無限遠点Ｏを除く楕円曲線Ｅ’／Ｆρ上のｘ０ｙ０≠０なる任意の点を（ｘ０，ｙ０）∈（Ｅ’／Ｆρ）＼Ｏとし、１の原始３乗根をξとする。この場合、元ｔ∈Ｆρに対して以下のｘ１（ｔ），ｘ２（ｔ），ｘ３（ｔ）∈Ｆρのうち、最低１つは楕円曲線Ｅ’／Ｆρ上のｘ座標となる。
【数２】
2016126227.tif 000004
【００２１】
写像部１２は、元ｔに次のアルゴリズムｆを適用することで楕円曲線Ｅ’／Ｆρ上の対応点ｆ（ｔ）を得る（図３Ｂ）。まず、写像部１２の第１判定部１２１（図１Ｂ）に元ｔが入力され、第１判定部１２１がｔ＝０∈Ｆρであるかを判定する（ステップＳ１２１）。ｔ＝０であれば、第１判定部１２１はｉ：＝１に設定し（ステップＳ１２２）、処理をステップＳ１２６に進める。ただし、「β：＝γ」は「βをγとする（γをβに代入する）こと」を意味する。ｔ≠０であれば、元ｔが第２判定部１２２に入力され、第２判定部１２２が１＋ｔ２＝０∈Ｆρであるかを判定する（ステップＳ１２３）。１＋ｔ２＝０であれば、第２判定部１２２はｉ：＝３に設定し（ステップＳ１２４）、処理をステップＳ１２６に進める。１＋ｔ２≠０であれば、元ｔが第３判定部１２３に入力され、第３判定部１２３はｇ（ｘｊ（ｔ））１／２が有限体Ｆρの元となるようなｊ∈｛１，２，３｝のうち最小のｊをｉに設定し、処理をステップＳ１２６に進める。ただし、ｇ（ｘ）＝ｘ３＋ｂ’である（ステップＳ１２５）。ステップＳ１２６では、出力部１２４が
【数３】
2016126227.tif 000005
を楕円曲線Ｅ’／Ｆρ上の対応点ｆ（ｔ）として出力する。ただし、χ：Ｆρ→｛−１，１｝は、任意の元ｔ∈Ｆρに対してχ（−ｔ）＝−χ（ｔ）となり、χ（０）＝１となる関数である（ステップＳ１２６）。
【００２２】
＜本形態の特徴＞
本形態の方式では、有限体Ｆρの元ｔを楕円曲線Ｅ’／Ｆρ上の対応点ｆ（ｔ）へ写すアルゴリズムｆの計算回数は１回だけでよく、演算速度が非特許文献２に開示された方式のおよそ２倍となる。また、ＢＮ曲線上での効率的な楕円倍算方式が存在するため、本形態の方式は計算可能性を満たす。さらに以下の理由により、正規性および標本可能性も満たす。従って、本形態の方式はランダムオラクルと（ｔＤ，ｔｓ，ｑＤ，ε’）−強識別不可能である。
【００２３】
≪正規性≫
ステップＳ１３の楕円ｍ倍算は、楕円曲線Ｅ’／Ｆρ上のｍ個の互いに異なる対応点ｆ（ｔ）＝（ｔｘ，ｔｙ）を同一のｎ等分点に写す。ｍは十分に大きく、この演算によって得られるｎ等分点からなる有限集合Ｅ’／Ｆρ［ｎ］は大数の法則に従う。そのため、アルゴリズムｆの個々の出力ｆ（ｔ）の分布に偏りがあったとしても、この楕円ｍ倍算によって得られるｎ等分点の分布の偏りはほとんど無視でき、一様分布とε−統計的識別不可能となる。そのため、本形態の方式は正規性を満たす。
【００２４】
≪標本可能性≫
以下のアルゴリズムにより、有限集合Ｅ’／Ｆρ［ｎ］の任意の元Λ∈Ｅ’／Ｆρ［ｎ］を、それに対応する有限体Ｆρの元ｔ∈Ｆρに写すことができる。
入力：Λ∈Ｅ’／Ｆρ［ｎ］
出力：ｔ∈Ｆρ
手続：
１−１）楕円曲線Ｅ’／Ｆρ上のｍ等分点からなる有限集合Ｅ’／Ｆρ［ｍ］の任意の元Γ∈Ｅ’／Ｆρ［ｍ］を選択する。
１−２）Ω＝Λ＋Γ∈Ｅ’／Ｆρを計算する。
１−３）有限体Ｆρの元を要素とする集合Ｌ＝Ｉ’（Ω）を計算する。
１−４）集合｛１，・・・，ｄ｝（ｄは正の整数）から任意の元μ∈｛１，・・・，ｄ｝を選択する。
１−５）μ≦＃Ｌなら集合Ｌの任意の元ｔ∈Ｌを出力して終了する。ただし、＃Ｌは集合Ｌの位数である。
１−６）μ≦＃Ｌでないなら「１−１」に戻る。
【００２５】
Ｉ’（Ω）としては、例えば、以下のようなアルゴリズムを用いることができる。
入力：Ω＝（ｘ，ｙ）∈Ｅ’／Ｆρ
出力：Ｌ⊂Ｆρ
手続：
２−１）Ｌを空集合にする。
２−２）ｔに関する方程式（ｘ−ξ２ｘ０）ｔ２＋（ｘ−ξｘ０）＝０が有限体Ｆρ上に根を持つなら、ｙ＝χ（ｔ）ｇ（ｔ）１／２を満たす方の根をｔ１とし、Ｌ：＝Ｌ∪｛ｔ１｝とする。
２−３）ｔに関する方程式（ｘ−ξｘ０）ｔ２＋（ｘ−ξ２ｘ０）＝０が有限体Ｆρ上に根を持つなら、ｙ＝χ（ｔ）ｇ（ｔ）１／２を満たす方の根をｔ２とし、ｇ（ｘ１（ｔ２））１／２∈Ｆρでないならば、Ｌ：＝Ｌ∪｛ｔ２｝とする。
２−４）ｔに関する方程式
【数４】
2016126227.tif 000006
が有限体Ｆρ上に４つの根を持つなら、ｙ＝χ（ｔ）ｇ（ｔ）１／２を満たす２つの根をｔ３，ｔ４とし、有限体Ｆρ上に２つの根を持つなら、ｙ＝χ（ｔ）ｇ（ｔ）１／２を満たす方の根をｔ３とする。ｔ３が存在し、ｇ（ｘ１（ｔ３））１／２∈Ｆρでなく、かつ、ｇ（ｘ２（ｔ３））１／２∈Ｆρでないならば、Ｌ：＝Ｌ∪｛ｔ３｝とする。ｔ４が存在し、ｇ（ｘ１（ｔ４））１／２∈Ｆρでなく、かつ、ｇ（ｘ２（ｔ４））１／２∈Ｆρでないならば、Ｌ：＝Ｌ∪｛ｔ４｝とする。
２−５）Ｌを出力する。
【００２６】
上述のアルゴリズムＩ’（Ω）は、入力値Ωによっては出力されるＬが空集合となる場合がある。そのため、アルゴリズムＩ’（Ω）自身は乱択アルゴリズムＩとε−統計的識別不可能ではない。しかしながら、各Λ∈Ｅ’／Ｆρはｍ個のＥ’／Ｆρの元Ωの何れかとされ、ｍは十分に大きい。そのため、大数の法則に従い、１−１）〜１−６）のアルゴリズムは乱択アルゴリズムＩとε−統計的識別不可能となり、本形態の方式は標本可能性を満たす。
【００２７】
なお、本形態のステップＳ１３では楕円ｍ倍算（ｖｘ，ｖｙ）＝［ｍ］ｆ（ｔ）∈Ｅ’／Ｆρを行ったが、これに代えて楕円α×ｍ倍算（ｖｘ，ｖｙ）＝［α×ｍ］ｆ（ｔ）∈Ｅ’／Ｆρを行ってもよい。
【００２８】
［第２実施形態］
楕円曲線Ｅ’／Ｆρには、楕円曲線Ｅ’／Ｆρ上の演算を高速に行うことができるフロベニウス写像と呼ばれる線形演算ψ：Ｅ’／Ｆρ→Ｅ’／Ｆρが存在する。ＢＮ曲線の設定ではあるｆ１，ｆ２∈Ｆρが存在し、
ψ：（Ｘ，Ｙ）→（ｆ１Ｘ*，ｆ２Ｙ*）
と計算できる。ただし、（Ｘ，Ｙ）は楕円曲線Ｅ’／Ｆρ上の点であり、Ｘ*，Ｙ*はそれぞれＸ，ＹのＦρ上共役である。ψ４−ψ２＋１＝０の関係を満たす。本形態では、このフロベニウス写像ψを用いて楕円曲線Ｅ’／Ｆρ上の楕円α×ｍ倍点（ｖｘ，ｖｙ）を得る。以下では第１実施形態との相違点を中心に説明し、既述の事項については同じ参照番号を流用して説明を省略する。
【００２９】
＜構成＞
図１Ａに例示するように、本形態の標本装置２は、入力部１１と写像部１２と楕円倍算部２３と出力部１４とメモリ１５を有する。標本装置２は、前述のコンピュータが所定のプログラムを実行することで構成される装置であってもよいし、電子回路を用いて一部またはすべての処理部が構成される装置であってもよい。
【００３０】
＜処理＞
図３Ａを用いて本形態の処理を説明する。本形態では、第１実施形態で説明したステップＳ１１，Ｓ１２の処理が実行され、ステップＳ１３に代えて以下のステップＳ２３の処理が実行され、その後、第１実施形態で説明したステップＳ１４の処理が実行される。ステップＳ２３の処理を説明する。
【００３１】
≪ステップＳ２３≫
楕円倍算部２３は、送られた対応点ｆ（ｔ）に対し、フロベニウス写像ψを用いて楕円曲線Ｅ’／Ｆρ上の楕円α×ｍ倍点［α×ｍ］ｆ（ｔ）∈Ｅ’／Ｆρを得て出力する。α＝１であってもよいし、α≠１であってもよく、フロベニウス写像ψを用いた楕円α×ｍ倍点［α×ｍ］ｆ（ｔ）の演算方法に限定はない。本形態の楕円曲線Ｅ’／Ｆρは位数ｎ×ｍの巡回群をなし、フロベニウス写像ψの固有値λに関する固有空間となる（巡回群をなす楕円曲線に共通）。この場合、点Θ∈Ｅ’／Ｆρにフロベニウス写像ψを作用させることと、楕円曲線Ｅ’／Ｆρ上で点Θを楕円λ倍算することとが等しくなる（ψΘ＝λΘ）。ここで固有値λに関する関数ｃ（λ）がｃ（λ）≠０ （ｍｏｄ ｎ）およびｃ（λ）＝０ （ｍｏｄ ｍ）を満たすのであれば、点Θの楕円ｃ（λ）倍算は点Θのα×ｍ倍算となる。このようなｃ（λ）のλをψに置換した形で表現される演算を対応点ｆ（ｔ）に作用させることが、フロベニウス写像ψを用いた楕円α×ｍ倍点［α×ｍ］ｆ（ｔ）を得るための演算Φである。ただし、フロベニウス写像ψを用いた楕円α×ｍ倍点［α×ｍ］ｆ（ｔ）の演算に必要な演算量が通常のｆ（ｔ）の楕円ｍ倍算の演算量よりも小さくなることが望ましい。例えば、楕円倍算部２３は、以下のような演算Φによって楕円α×ｍ倍点［α×ｍ］ｆ（ｔ）を得ることが望ましい。
Φ：Ｔ→（６ｕ−ψ３＋３ψ２−ψ）Ｔ    （１）
ただし、Ｔ∈Ｅ’／Ｆρであり、Ｔ＝ｆ（ｔ）とすることで楕円α×ｍ倍点［α×ｍ］ｆ（ｔ）を計算できる。
【００３２】
≪Ｔ→（６ｕ−ψ３＋３ψ２−ψ）Ｔの演算例≫
図２に例示するように、式（１）の演算を行う楕円倍算部２３は、演算部２３０〜２３８および出力部２３９を有する。この場合、図４に例示するように、演算部２３０は入力されたｆ（ｔ）をＴに代入し（Ｔ：＝ｆ（ｔ）∈Ｅ’／Ｆρ），得たＴを出力する（ステップＳ２３０）。演算部２３１は、入力されたＴをＲに代入し（Ｒ：＝Ｔ）、得たＲを出力する（ステップＳ２３１）。演算部２３２はＴを入力としてＱ：＝（６ｕ）Ｔを得て出力する（ステップＳ２３２）。演算部２３３はＲを入力としてＲ：＝ψＲを得て出力する（ステップＳ２３３）。演算部２３４はＱを入力としてＱ：＝Ｑ−Ｒを得て出力する（ステップＳ２３４）。演算部２３５はＲを入力としてＲ：＝ψＲを得て出力する（ステップＳ２３５）。演算部２３６はＱを入力としてＱ：＝Ｑ＋３Ｒを得て出力する（ステップＳ２３６）。演算部２３７はＲを入力としてＲ：＝ψＲを得て出力する（ステップＳ２３７）。演算部２３８はＱを入力としてＱ：＝Ｑ−Ｒを得て出力する（ステップＳ２３８）。出力部２３９はＱを出力する（ステップＳ２３９）。
【００３３】
＜本形態の特徴＞
本形態では、フロベニウス写像ψを用いて楕円曲線Ｅ’／Ｆρ上の楕円α×ｍ倍点［α×ｍ］ｆ（ｔ）を計算するため、第１実施形態の方式よりも高速化できる場合がある。例えば、式（１）の方法を用いた場合には、第１実施形態の方式に比べて約４倍の高速化が実現できる。
【００３４】
［その他の変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、前述した１−１）〜１−６）の各処理をそれぞれ実行する処理部３１−１〜３１−６を備え、入力Λから出力ｔを得る装置を構成してもよい。このような装置は、前述のコンピュータが所定のプログラムを実行することで構成される装置であってもよいし、電子回路を用いて一部またはすべての処理部が構成される装置であってもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００３５】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００３６】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００３８】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【００３９】
本発明は、例えばＩＤベース暗号方式や関数暗号方式等の楕円曲線を用いた暗号方式において、有限体上の任意値を楕円曲線上の点に安全かつ高速にマッピングするために利用できる。
【符号の説明】
【００４０】
１，２  標本装置
【図１】
2016126227.tif 000008
【図２】
2016126227.tif 000009
【図３】
2016126227.tif 000010
【図４】
2016126227.tif 000011