(57)【要約】【課題】任意のビット列を標数３の有限体上で定義された楕円曲線E(GF(3m)):y2=x3-x+b上の点へ高速に変換する。【解決手段】変換部１０５が任意のビット列ID∈{0,1}*を有限体GF(3m)の元y∈GF(3m)に変換し、有限体演算部１０６がt=y2-b∈GF(3m)を計算し、１／３トレース写像演算部１０８がtを入力とする１／３トレース写像C(t)を計算し、有限体演算部１０９がx=C(t)3-C(t)∈GF(3m)を計算して楕円曲線E(GF(3m)):y2=x3-x+bのx座標（x∈GF(3m)）を求める。【選択図】図１
2010164796.tif 000002
【特許請求の範囲】
【請求項１】
任意のビット列を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する変換演算装置であって、前記mが2≡m mod 3を満たす正の整数であり、
任意のビット列を格納する記憶部と、
前記記憶部から読み出した前記ビット列を有限体GF(3m)の元y∈GF(3m)に変換する変換部と、
前記変換部で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行う第１有限体演算部と、
前記第１有限体演算部で得られたtを用い、
【数２３】
2010164796.tif 000026
の演算を行う１／３トレース写像演算部と、
前記１／３トレース写像演算部で得られたC(t)を用い、x=C(t)3-C(t)∈GF(3m)の演算を行う第２有限体演算部と、
前記第２有限体演算部で得られたxと、前記変換部で得られた元yとを出力する出力部と、を有し、
前記１／３トレース写像演算部で用いられるtは、
【数２４】
2010164796.tif 000027
を満たし、
前記出力部で出力される元yは、Tr(y2-b)=0を満たす、
ことを特徴とする変換演算装置。
【請求項２】
任意のビット列を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する変換演算装置であって、前記mが1≡m mod 3を満たす正の整数であり、
任意のビット列を格納する記憶部と、
前記記憶部から読み出した前記ビット列を有限体GF(3m)の元y∈GF(3m)に変換する変換部と、
前記変換部で得られた元yを用い、t=y2-b∈GF(3m)の演算を行う第１有限体演算部と、
前記第１有限体演算部で得られたtを用い、
【数２５】
2010164796.tif 000028
の演算を行う１／３トレース写像演算部と、
前記第１有限体演算部で得られたtと、それに対応するC(t)とを用い、x=t-C(t)3+C(t)∈GF(3m)の演算を行う第２有限体演算部と、
前記第２有限体演算部で得られたxと、前記変換部で得られた元yとを出力する出力部と、を有し、
前記１／３トレース写像演算部で用いられるtは、
【数２６】
2010164796.tif 000029
を満たし、
前記出力部で出力される元yは、Tr(y2-b)=0を満たす、
ことを特徴とする変換演算装置。
【請求項３】
請求項１又は２の変換演算装置であって、
前記１／３トレース写像演算部、及び前記第２有限体演算部の少なくとも一方は、
有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算とを行う演算部である、
ことを特徴とする変換演算装置。
【請求項４】
任意のビット列を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する変換演算装置であって、前記mが1≡m mod 3を満たす正の整数であり、
任意のビット列を格納する記憶部と、
前記記憶部から読み出した前記ビット列を有限体GF(3m)の元y∈GF(3m)に変換する変換部と、
前記変換部での変換で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行う第１有限体演算部と、
前記第１有限体演算部で得られたtを用い、
【数２７】
2010164796.tif 000030
の演算を行う１／２トレース写像演算部と、
前記１／２トレース写像演算部で得られたH(t)を用い、
【数２８】
2010164796.tif 000031
の演算を行う１／３トレース写像演算部と、
前記１／３トレース写像演算部で得られたC(H(t))を用い、x=C(H(t))3-C(H(t))∈GF(3m)の演算を行う第２有限体演算部と、
前記第２有限体演算部で得られたxと、前記変換部で得られた元yとを出力する出力部と、を有し、
前記１／２トレース写像演算部で用いられるtは、
【数２９】
2010164796.tif 000032
を満たし、
前記出力部で出力される元yは、Tr(y2-b)=0を満たす、
ことを特徴とする変換演算装置。
【請求項５】
請求項４の変換演算装置であって、
前記１／２トレース写像演算部、前記１／３トレース写像演算部、及び前記第２有限体演算部の少なくとも一部は、
有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算とを行う演算部である、
ことを特徴とする変換演算装置。
【請求項６】
任意のビット列を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する変換演算方法であって、前記mが2≡m mod 3を満たす正の整数であり、
(a) 変換部が、記憶部から読み出したビット列を有限体GF(3m)の元y∈GF(3m)に変換するステップと、
(b) 第１有限体演算部が、前記ステップ(a)で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行うステップと、
(c) 演算制御部が、ステップ(b)で得られたtが
【数３０】
2010164796.tif 000033
を満たすか否かを判定し、満たさない場合に前記ステップ(a)における変換方法を変更して前記ステップ(a)(b)を再び実行させるステップと、
(d) １／３トレース写像演算部が、前記ステップ(c)でTr(t)=0を満たすと判定されたtを用い、
【数３１】
2010164796.tif 000034
の演算を行うステップと、
(e) 第２有限体演算部が、前記ステップ(d)で得られたC(t)を用い、x=C(t)3-C(t)∈GF(3m)の演算を行うステップと、
(f) 出力部が、前記ステップ(e)で得られたxと、前記ステップ(c)でTr(t)=0を満たすと判定されたtを算出するために前記ステップ(b)で用いられた元yとを出力するステップと、
を有する変換演算方法。
【請求項７】
任意のビット列を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する変換演算方法であって、前記mが1≡m mod 3を満たす正の整数であり、
(a) 変換部が、記憶部から読み出したビット列を有限体GF(3m)の元y∈GF(3m)に変換するステップと、
(b) 第１有限体演算部が、前記ステップ(a)で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行うステップと、
(c) 演算制御部が、ステップ(b)で得られたtが
【数３２】
2010164796.tif 000035
を満たすか否かを判定し、満たさない場合に前記ステップ(a)における変換方法を変更して前記ステップ(a)(b)を再び実行させるステップと、
(d) １／３トレース写像演算部が、前記ステップ(c)でTr(t)=0を満たすと判定されたtを用い、
【数３３】
2010164796.tif 000036
の演算を行うステップと、
(e) 第２有限体演算部が、前記ステップ(c)でTr(t)=0を満たすと判定されたtと、それに対応する前記ステップ(d)で得られたC(t)とを用い、x=t-C(t)3+C(t)∈GF(3m)の演算を行うステップと、
(f) 出力部が、前記ステップ(e)で得られたxと、前記ステップ(c)でTr(t)=0を満たすと判定されたtを算出するために前記ステップ(b)で用いられた元yとを出力するステップと、
を有する変換演算方法。
【請求項８】
任意のビット列を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する変換演算方法であって、前記mが1≡m mod 3を満たす正の整数であり、
(a) 変換部が、記憶部から読み出したビット列を有限体GF(3m)の元y∈GF(3m)に変換するステップと、
(b) 第１有限体演算部が、前記ステップ(a)で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行うステップと、
(c) 演算制御部が、ステップ(b)で得られたtが
【数３４】
2010164796.tif 000037
を満たすか否かを判定し、満たさない場合に前記ステップ(a)における変換方法を変更して前記ステップ(a)(b)を再び実行させるステップと、
(d) １／２トレース写像演算部が、前記ステップ(c)でTr(t)=0を満たすと判定されたtを用い、
【数３５】
2010164796.tif 000038
の演算を行うステップと、
(e) １／３トレース写像演算部が、前記ステップ(d)で得られたH(t)を用い、
【数３６】
2010164796.tif 000039
の演算を行うステップと、
(f) 第２有限体演算部が、前記ステップ(e)で得られたC(H(t))を用い、x=C(H(t))3-C(H(t))∈GF(3m)の演算を行うステップと、
(g) 出力部が、前記ステップ(f)で得られたxと、前記ステップ(c)でTr(t)=0を満たすと判定されたtを算出するために前記ステップ(b)で用いられた元yとを出力するステップと、
を有する変換演算方法。
【請求項９】
請求項１から５の何れかの変換演算装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項９のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に、任意のビット列を標数３の有限体上で定義された楕円曲線上の点へ変換する技術に関する。
【背景技術】
【０００２】
情報通信技術に不可欠な技術として公開鍵暗号技術が知られている。しかし、ＲＳＡなどの公開鍵暗号は、公開鍵の管理が煩雑で管理コストが高いといった問題がある。近年、このような問題を解決する技術として任意のビット列であるID∈{0,1}*を公開鍵として用いるＩＤベース暗号が提案された（例えば、非特許文献１参照）。
【０００３】
ＩＤベース暗号では、任意のビット列であるID∈{0,1}*を楕円曲線上の点に変換し、この楕円曲線上でペアリング演算や楕円スカラー倍演算などを行って暗号化処理や秘密鍵生成処理を行う。近年、ペアリング演算を高速に行える楕円曲線として、標数３の有限体GF(3m)上で定義された超特異（Supersingular）楕円曲線が注目されている。
【０００４】
任意のビット列であるID∈{0,1}*を有限体GF(3m)上で定義された楕円曲線E(GF(3m)):y2=x3-x+b(b=±1)上の点に変換するための従来方法として、非特許文献２に示す方法がある。以下に非特許文献２に示す方法を説明する。
【０００５】
＜ステップＳ１＞ MFG（マスク生成関数）などのハッシュ関数を用い、任意のビット列であるID∈{0,1}*を有限体GF(3m)上の元に変換し、それを楕円曲線E(GF(3m)):y2=x3-x+bのx座標とする（x∈GF(3m)）。
＜ステップＳ２＞ステップＳ１で得られたx∈GF(3m)を楕円曲線E(GF(3m)):y2=x3-x+bの右辺に代入してy2∈GF(3m)を求める。
＜ステップＳ３＞ステップＳ２で得られたy2∈GF(3m)の平方根を以下のように算出し(［ステップＳ３ａ］〜［ステップＳ３ｄ］、y∈GF(3m)を求める。ただし、k=(m-1)/2=(kν-1,...k0)2であり、kν-1,...k0は、kを２進表記した際の各桁のビット値{0,1}を示す。
［ステップＳ３ａ］s=c=x3-x+b∈GF(3m)とする。
［ステップＳ３ｂ］i=ν-2から0までの各iについて、以下の《ステップＳ３ｂａ》及び《ステップＳ３ｂｂ》の処理を実行する。
《ステップＳ３ｂａ》t=sとする。
《ステップＳ３ｂｂ》
ki=1ならば、
【０００６】
【数１】
2010164796.tif 000003
s=c・t∈GF(3m)            …(2)
の演算を行い、
ki=0ならば、
【数２】
2010164796.tif 000004
s=c・t∈GF(3m)            …(4)
の演算を行う。
【０００７】
［ステップＳ３ｃ］
c=c・s6∈GF(3m)      …(5)
の演算を行う。
［ステップＳ３ｄ］cをy∈GF(3m)とする。
＜ステップＳ４＞（x,y）∈E(GF(3m))を出力する。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】D. Boneh and M. Franklin, "Identify-based encryption from the Weil pairing", CRYTPO 2001. LNCS, vol. 2139, pp. 213-229, Springer, 2001.
【非特許文献２】Barreto,P.S.L.M., Kim,H.Y., Lynn,B., Scott,M. "Efficient algorithms for pairing-based cryptosystems", CRYPTO 2002. LNCS, vol.2442, pp.354-368, Springer, Heidelberg (2002).
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、非特許文献２の方法では、《ステップＳ３ｂａ》及び《ステップＳ３ｂｂ》からなる繰り返し処理において、演算コストが高い有限体GF(3m)上での乗算を複数回行う必要がある。よって、非特許文献２の方法では高速な演算が困難である。
【００１０】
本発明はこのような点に鑑みてなされたものであり、任意のビット列を標数３の有限体上で定義された楕円曲線上の点へ高速に変換することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では、任意のビット列を有限体GF(3m)の元y∈GF(3m)に変換し、トレース写像の変形演算を用い、元y∈GF(3m)に対応する標数3の有限体GF(3m)上で定義された楕円曲線E(GF(3m)):y2=x3-x+bのx座標（x∈GF(3m)）を求める。このトレース写像の変形演算は、有限体GF(3m)上のフロベニウス写像と加算演算によって実現でき、高速な演算が可能である。
【００１２】
本発明の第１態様では、変換部が任意のビット列を有限体GF(3m)の元y∈GF(3m)に変換し、第１有限体演算部が変換部で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行い、１／３トレース写像演算部が、第１有限体演算部で得られたtを用い、
【００１３】
【数３】
2010164796.tif 000005
の演算を行い、第２有限体演算部が１／３トレース写像演算部で得られたC(t)を用い、x=C(t)3-C(t)∈GF(3m)の演算を行い、出力部が第２有限体演算部で得られたxと、変換部で得られた元y)とを出力する。なお、第１態様は、mが2≡m mod 3を満たす正の整数である場合に適用され、１／３トレース写像演算部で用いられるt∈GF(3m)は、
【００１４】
【数４】
2010164796.tif 000006
を満たし、出力部で出力される元yは、Tr(y2-b)=0を満たす。
【００１５】
本発明の第２態様では、変換部が任意のビット列を有限体GF(3m)の元y∈GF(3m)に変換し、第１有限体演算部が変換部での変換で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行い、１／２トレース写像演算部が第１有限体演算部で得られたtを用い、
【００１６】
【数５】
2010164796.tif 000007
の演算を行い、１／３トレース写像演算部が１／２トレース写像演算部で得られたH(t)を用い、
【００１７】
【数６】
2010164796.tif 000008
の演算を行い、第２有限体演算部が１／３トレース写像演算部で得られたC(H(t))を用い、x=C(H(t))3-C(H(t))∈GF(3m)の演算を行い、出力部が第２有限体演算部で得られたxと、変換部で得られた元yとを出力する。なお、第３態様は、mが1≡m mod 3を満たす正の整数である場合に適用され、１／２トレース写像演算部で用いられるtは、式(7)を満たし、出力部で出力される元yは、Tr(y2-b)=0を満たす。
【００１８】
本発明の第３態様では、変換部が任意のビット列を有限体GF(3m)の元y∈GF(3m)に変換し、第１有限体演算部が変換部で得られた元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行い、１／３トレース写像演算部が第１有限体演算部で得られたtを用い、式(6)の演算を行い、第２有限体演算部が第１有限体演算部で得られたtと、それに対応するC(t)とを用い、x=t-C(t)3+C(t)∈GF(3m)の演算を行い、出力部が第２有限体演算部で得られたxと、変換部で得られた元yとを出力する。なお、第２態様は、mが1≡m mod 3を満たす正の整数である場合に適用され、１／３トレース写像演算部で用いられるtは、式(7)を満たし、出力部で出力される元yは、Tr(y2-b)=0を満たす。
【発明の効果】
【００１９】
本発明では、任意のビット列を標数３の有限体上で定義された楕円曲線上の点へ高速に変換することができる。
【図面の簡単な説明】
【００２０】
【図１】第１実施形態の変換演算装置の機能構成を説明するためのブロック図である。
【図２】第１実施形態の変換演算方法を説明するためのフローチャートである。
【図３】第２実施形態の変換演算装置の機能構成を説明するためのブロック図である。
【図４】第２実施形態の変換演算方法を説明するためのフローチャートである。
【図５】第３実施形態の変換演算装置の機能構成を説明するためのブロック図である。
【図６】第３実施形態の変換演算方法を説明するためのフローチャートである。
【図７】第４実施形態の変換演算装置の機能構成を説明するためのブロック図である。
【図８】第４実施形態の変換演算方法を説明するためのフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施形態を説明する。
〔記号・用語の定義〕
まず、各実施形態で使用する記号・用語を定義する。
【００２２】
＜有限体GF(q)の標数＞
有限体GF(q)（位数qの有限体）の任意の元a∈GF(q)に対して0=z・aを満たす最小の正の整数zを有限体GF(q)の標数と呼ぶ。有限体GF(q)が有限体GF(p)（素体）のm次拡大である場合（GF(q)=GF(pm)、pは素数）、有限体GF(q)の標数はpとなる。すなわち、有限体GF(3m)の標数は3である。なお、本形態の場合、mは正の整数である。また、素体である有限体GF(p)の演算は、例えば、pを法とする剰余演算を用いることによって容易に構成できる。例えば、有限体GF(p)の加算をa+b mod pとし、有限体GF(p)の乗算をa・b mod pとすることで有限体GF(p)上の演算が実現できる。
【００２３】
＜有限体GF(3m)＞
有限体GF(3m)は、有限体GF(3)を基礎体としたm次拡大である。有限体GF(3m)の元u∈GF(3m)を表現するために、有限体GF(3)の元の組ωi∈GF(3)(i=0,...,m-1)を用いることができる。そのための代表的な方法は、
【００２４】
【数７】
2010164796.tif 000009
と表現する方法である。ここで、δiは有限体GF(3m)の元δi∈GF(3m)であり、有限体GF(3)mと有限体GF(3m)とが１対１対応するような特別な組み合わせであるとする。このような性質を持つδi∈GF(3m)を基底と呼ぶ。基底δi∈GF(3m)の一例は、有限体GF(3)の元を係数とするm次の既約多項式f(x)の根x∈GF(3m)（f(x)=0を満たすx）に対するδi=xiである。
【００２５】
また、
【数８】
2010164796.tif 000010
で定義される有限体GF(3m)の元u1，u2∈GF(3m)の加算u1+u2∈GF(3m)は以下のように計算できる。なお、（ω1,i,+ω2,i）は有限体GF(3)上の演算である。
【００２６】
【数９】
2010164796.tif 000011
また、有限体GF(3m)の元u1，u2∈GF(3m)の乗算u1・u2∈GF(3m)は以下のように計算できる。なお、係数ω1,i, ω2,iについての演算は有限体GF(3)上の演算である。
【００２７】
【数１０】
2010164796.tif 000012
＜有限体GF(3m)上で定義された楕円曲線E(GF(3m))＞
有限体GF(q)上で定義された楕円曲線E(GF(q))は、アフィン（affine）座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6（a1,a2,a3,a4,a6∈GF(q)）  …(15)
を満たす点(x,y)（x,y∈GF(q)）の集合に無限遠点と呼ばれる特別な点Ｏを付加したものである。楕円曲線E(q)上の任意の２点に対して楕円加算と呼ばれる二項演算及び楕円曲線E(q)上の任意の１点に対して楕円逆元と呼ばれる単項演算がそれぞれ定義できる。また、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できることはよく知られている。本形態では、有限体GF(3m)上で定義された
y2=x3-x+b    …(16)
を満たす点(x,y)（x,y∈GF(3m)）の集合に無限遠点Ｏを付加した楕円曲線E(GF(3m))を扱う。
【００２８】
＜有限体のフロベニウス写像＞
二項定理によれば、
【数１１】
2010164796.tif 000013
が成立する。右辺の各項の係数は、二項係数と呼ばれる定数で、i≠0かつi≠3の場合、必ず3の倍数となる。δ,θ∈GF(3m)である場合、δ,θ∈GF(3m)に3の倍数（標数の倍数）を乗じた値は0と同値であるから、
(δ+θ)3=δ3+θ3      …(18)
が成立する。さらに、c∈GF(3)なるcに関して、c3＝cが成立する。
【００２９】
一般に、δ1,δ2,...,δn∈GF(3m)を不定元とする任意のGF(3)係数有利式f(δ1,δ2,...,δn)に対して、
f(δ1,δ2,...,δn)3=ｆ（δ13,δ23,...,δn3）      …(19)
が成立する。従って、式(10)は
【００３０】
【数１２】
2010164796.tif 000014
のように変形できる。従って事前に
【数１３】
2010164796.tif 000015
を満たす有限体GF(3)の元cij∈GF(3)が求められていれば、
【００３１】
【数１４】
2010164796.tif 000016
によって、元の基底δiを用いたu3∈GF(3m)の表現が得られる。即ち、m個の元の組ωi∈GF(3)(i=0,...,m-1)を要素とするベクトル(ωi)に、元cij∈GF(3)を要素とする行列(cij)を掛けるだけでu3∈GF(3m)を表現するベクトルが得られる。また、行列(cij)n(nは1以上の整数)を事前に求めておけば、ベクトル(ωi)に行列(cij)nを掛けるだけで、uｓ∈GF(3m)（s=3n）を表現するベクトルを求めることができる。さらに、行列(cij)が簡単になるような特別な基底が存在し、そのような基底を採用した場合、uｓ∈GF(3m)の演算コストはGF(3m)上の乗算と比較して無視できるほどに小さくなることが知られている。このようにu∈GF(3m)からus∈GF(3m)への写像を計算する関数を３ｎ乗フロベニウス写像と呼ぶ。
【００３２】
＜有限体GF(3m)でのトレース写像＞
任意のt∈GF(3m)に対する有限体GF(3m)でのトレース写像を
【数１５】
2010164796.tif 000017
と定義する。式(23)に示すように、トレース写像Tr(t)は、有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算のみによって計算できる。
【００３３】
＜１／２トレース写像＞
任意のt∈GF(3m)に対する有限体GF(3m)での１／２トレース写像を
【数１６】
2010164796.tif 000018
と定義する。式(24)に示すように、１／２トレース写像H(t)は、有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算のみによって計算できる。
【００３４】
また、式(24)より
【数１７】
2010164796.tif 000019
となる。また、任意のt∈GF(3m)は、
【数１８】
2010164796.tif 000020
を満たすため、式(23)(26)を用い、式(25)は、
H(t)+H(t3)=Tr(t)+t      …(27)
と変形できる。
【００３５】
＜有限体GF(3m)での１／３トレース写像＞
任意のt∈GF(3m)に対する有限体GF(3m)での１／３トレース写像を
【数１９】
2010164796.tif 000021
と定義する。式(28)に示すように、１／３トレース写像C(t)は、有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算のみによって計算できる。
【００３６】
また、r=m mod 3=1のとき、式(28)より、
【数２０】
2010164796.tif 000022
となる。さらに、式(23)(26)を用い、式(29)は
C(t)+C(t3)+C(t9)=Tr(t)+t+t3      …(30)
と変形できる。
【００３７】
同様に、r=m mod 3=2のとき、式(28)より、
【数２１】
2010164796.tif 000023
となる。さらに、式(23)(26)を用い、式(31)は
C(t)+C(t3)+C(t9)=Tr(t)+t      …(32)
と変形できる。
【００３８】
〔原理〕
次に、本形態の原理を説明する。
本形態では、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する（式(16)）。
【００３９】
そのために、まず、任意のビット列ID∈{0,1}*を有限体GF(3m)の元y∈GF(3m)に変換し、得られた元y∈GF(3m)を用い、
t=y2-b ∈GF(3m)       …(33)
の演算を行う。この場合、式(16)より、
t=x3-x ∈GF(3m)       …(34)
となる。
【００４０】
ここで、r=m mod 3=2であってTr(t)=0である場合、式(32)より
C(t)+C(t3)+C(t9)=t ∈GF(3m)      …(35)
であり、有限体GF(3m)上の演算（式(13)(14)参照）であることを考慮すると、式(35)は、
(C(t)3-C(t))3-(C(t)3-C(t))=t ∈GF(3m)      …(36)
と変形できる。式(34)(36)より、
x=C(t)3-C(t) ∈GF(3m)       …(37)
であることが分かる。従って、r=m mod 3=2であってTr(t)=0である場合に式(37)を計算することで、曲線y2=x3-x+b上のx座標が求まり、楕円曲線y2=x3-x+b上の点(x,y)が定まることが分かる。
【００４１】
一方、r=m mod 3=1であってTr(t)=0である場合、式(30)より
C(t)+C(t3)+C(t9)=t+t3∈GF(3m)        …(38)
であり、t=H(t)とすると、
C(H(t))+C(H(t)3)+C(H(t)9)=H(t)+H(t)3∈GF(3m)        …(39)
である。また、式(19)(27)より、式(39)は、
C(H(t))+C(H(t)3)+C(H(t)9)=t ∈GF(3m)        …(40)
と変形でき、有限体GF(3m)上の演算（式(13)(14)参照）であることを考慮すると、式(40)は、
(C(H(t))3-C(H(t)))3-(C(H(t))3-C(H(t)))=t∈GF(3m)      …(41)
と変形できる。式(34)(41)より、
x=C(H(t))3-C(H(t)) ∈GF(3m)       …(42)
であることが分かる。従って、r=m mod 3=1であってTr(t)=0である場合に式(42)を計算することで、曲線y2=x3-x+b上のx座標が求まり、楕円曲線y2=x3-x+b上の点(x,y)が定まることが分かる。
【００４２】
また、r=m mod 3=1であってTr(t)=0である場合、式(27)においてt=C(t)とし、式(19)を考慮すると、
H(C(t))+H(C(t))3=C(t) ∈GF(3m)      …(43)
を満たすことが分かる。また、式(24)(28)より、
【００４３】
【数２２】
2010164796.tif 000024
を満たす。式(44)を用いると、式(43)は、
C(H(t))+C(H(t))3=C(t) ∈GF(3m)      …(45)
と変形でき、さらに
-C(H(t))-C(H(t))3=-C(t) ∈GF(3m)      …(46)
と変形できる。式(45)の両辺からC(H(t))3を引くと、
-C(H(t))-C(H(t))3-C(H(t))3=-C(t)-C(H(t))3∈GF(3m)      …(47)
となる。有限体GF(3m)上の演算（式(13)(14)参照）では、-C(H(t))3∈GF(3m)は2・C(H(t))3∈GF(3m)と等価であるため、式(47)は、
4・C(H(t))3-C(H(t))=-C(H(t))3-C(t) ∈GF(3m)      …(48)
と変形でき、4・C(H(t))3∈GF(3m)はC(H(t))3∈GF(3m)と等価であるため、さらに
C(H(t))3-C(H(t))=-C(H(t))3-C(t) ∈GF(3m)      …(49)
と変形できる。
【００４４】
また、式(19)を考慮すると式(40)は、
C(H(t))9+C(H(t))3=t-C(H(t)) ∈GF(3m)     …(50)
と変形でき、式(44)を用いると式(50)は、
H(C(t))9+H(C(t))3=t-C(H(t)) ∈GF(3m)     …(51)
と変形できる。また、式(43)より、
C(t3)=H(C(t3))+H(C(t3))3∈GF(3m)      …(52)
となり、式(19)を考慮すると式(52)は、
C(t)3=H(C(t))3+H(C(t))9∈GF(3m)      …(53)
と変形でき、さらに式(50)よって式(53)は、
C(t)3=C(H(t))9+C(H(t))3=t-C(H(t)) ∈GF(3m)     …(54)
と変形できる。ここで、式(54)を用いると、
C(t)3+C(t)-t=t-C(H(t))+C(t)-t=-C(H(t))+C(t) ∈GF(3m)     …(55)
となり、式(45)を用いると式(55)は、
C(t)3+C(t)-t=-C(H(t))+C(H(t))+C(H(t))3=C(H(t))3∈GF(3m)     …(56)
と変形できる。この式(56)を用いると式(49)は、
C(H(t))3-C(H(t))=-(C(t)3+C(t)-t)-C(t) ∈GF(3m)     …(57)
と変形できる。
【００４５】
さらに、有限体GF(3m)上の演算（式(13)(14)参照）では、-2・C(H(t))3∈GF(3m)はC(H(t))3∈GF(3m)と等価であることを考慮すると、式(57)は、
C(H(t))3-C(H(t))=-(C(t)3+C(t)-t)-C(t)=t-C(t)3+C(t) ∈GF(3m)     …(58)
と変形できる。従って、式(42)を参照すると、r=m mod 3=1であってTr(t)=0である場合に式(58)を計算することでも、曲線y2=x3-x+b上のx座標が求まり、楕円曲線y2=x3-x+b上の点(x,y)が定まることが分かる。
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。
【００４６】
本形態は、mが2≡m mod 3を満たす正の整数である場合に、式(37)を用い、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する形態である。
【００４７】
＜構成＞
図１は、第１実施形態の変換演算装置１の機能構成を説明するためのブロック図である。
図１に示すように、本形態の変換演算装置１は、制御部１０１、一時メモリ１０２、入力部１０３、記憶部１０４、変換部１０５、有限体演算部１０６，１０９（「第１，２有限体演算部」に相当）、演算制御部１０７、１／３トレース写像演算部１０８、及び出力部１１０を有する。
【００４８】
変換演算装置１は、ＣＰＵ(central processing unit)，ＲＡＭ(random-access memory)，ＲＯＭ(read-only memory)等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。すなわち、一時メモリ１０２や記憶部１０４は、例えば、ＲＡＭ、磁気記録装置、光磁気記録媒体やそれらの少なくとも一部の結合によって構成される記憶領域である。変換部１０５、有限体演算部１０６，１０９、演算制御部１０７及び１／３トレース写像演算部１０８は、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。また、入力部１０３は、例えば、キーボードなどのユーザインタフェースや、データの入力を受け付ける入力ポートや、他の処理部から出力されたデータの入力処理を行う処理部（ＣＰＵに所定のプログラムが読み込まれて構成される処理部）などである。また、出力部１１０は、データを出力する出力ポートや、データを他の処理部に転送するための処理部（ＣＰＵに所定のプログラムが読み込まれて構成される処理部）などである。なお、変換演算装置１は、制御部１０１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１０２に格納され、その他の演算処理の際に読み出されて利用される。
【００４９】
＜変換演算方法＞
次に、本形態の変換演算方法を説明する。
図２は、第１実施形態の変換演算方法を説明するためのフローチャートである。以下、この図を用いて本形態の変換演算方法を説明する。本形態では、mが2≡m mod 3を満たす正の整数であることを前提にする。
【００５０】
まず、入力部１０３に任意のビット列ID∈{0,1}*が入力され、記憶部１０４に格納される（ステップＳ１０１）。次に、制御部１０１がw=0とし、wを一時メモリ１０２に格納する（ステップＳ１０２）。次に、変換部１０５が、記憶部１０４からビット列ID∈{0,1}*を読み出し、一時メモリ１０２からwを読み出し、記憶部１０４から読み出したビット列ID∈{0,1}*を有限体GF(3m)の元y=G(ID)+w ∈GF(3m)に変換する（ステップＳ１０３）。本形態では、ここで、関数G(ID)は、任意のビット列ID∈{0,1}*を有限体GF(3m)の元に変換する関数である。このような関数G(ID)は、ハッシュ関数などを用いて容易に構成できる。以下に関数G(ID)の一例を示す。
【００５１】
［関数G(ID)の一例］
(1)入力されたビット列ID∈{0,1}*に対してstr=MGF(ID,L)(ただし、L=2・floor(log23m))を求める。なお、MGF(ID,L)は、マスク生成関数であり、ハッシュ関数演算を繰り返し行うことで、任意のビット列ID∈{0,1}*からビット長Ｌのビット値strを生成する関数である（例えば、「RSA Laboratories, “PKCS #1 v2.1: RSA Encryption Standard,” draft 2, January 5, 2001.」など参照）。また、floor(・)はフロア関数であり、・以下の最大の整数を出力する。すなわち、この例では、log23m以下の最大の整数を２倍したものをLとする。
【００５２】
(2)d=BitStringtoInteger(str)を求める。なお、BitStringtoInteger(・)は、ビット列・を整数に変換する関数である。
(3)dを３進展開し、各項の係数が{0,1,2}の多項式d3を生成する。
(4)d3 mod f(x)を求め、その演算値を出力する。なお、f(x)は、有限体GF(3)の元を係数とするm次の既約多項式である（［関数G(ID)の一例］の説明終わり）。
【００５３】
次に、有限体演算部１０６にステップＳ１０３で得られた元y∈GF(3m)が入力され、有限体演算部１０６は、この元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行う（ステップＳ１０４）。次に、演算制御部１０７に、ステップＳ１０４で生成されたt∈GF(3m)入力され、式(23)に示したトレース写像Tr(t)を計算し、Tr(t)=0を満たすか否かを判定する（ステップＳ１０５）。
【００５４】
ここで、Tr(t)=0を満たさないと判定された場合、演算制御部１０７は、ステップＳ１０３における変換方法を変更してステップＳ１０３〜Ｓ１０５の各処理を再び実行させる。本形態の例では、演算制御部１０７が一時メモリ１０２から読み出したwからw+1を求め、求めたw+1を新たなwとして一時メモリ１０２に格納し、処理をステップＳ１０３に戻す（ステップＳ１０６）。
【００５５】
一方、ステップＳ１０５においてTr(t)=0を満たすと判定された場合、Tr(t)=0を満たすと判定されたtが１／３トレース写像演算部１０８に入力される。１／３トレース写像演算部１０８は、ステップＳ１０５でTr(t)=0を満たすと判定されたtを用い、式(28)に示した１／３トレース写像の演算を行ってC(t)∈GF(3m)を求める（ステップＳ１０７）。１／３トレース写像演算部１０８は、有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算のみによってC(t)∈GF(3m)を計算できる。次に、有限体演算部１０９にステップＳ１０７で得られたC(t)が入力され、有限体演算部１０９は、ステップＳ１０７で得られたC(t)を用い、x=C(t)3-C(t)∈GF(3m)の演算を行う（ステップＳ１０８／式(37)参照）。なお、C(t)3∈GF(3m)は、有限体GF(3m)の元u∈GF(3m)を元u3∈GF(3m)へ写像する３乗フロベニウス写像によって計算できる。
【００５６】
次に、出力部１１０が、ステップＳ１０８で得られたx∈GF(3m)と、ステップＳ１０５でTr(t)=0を満たすと判定されたtを算出するためにステップＳ１０４で用いられた元y∈GF(3m)とを出力する（ステップＳ１０９）。
【００５７】
＜本形態の特徴＞
mが2≡m mod 3を満たす正の整数である場合に、本形態の処理を行うことにより、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換することができ、その演算コストは非特許文献２の方法よりも低い。
【００５８】
具体的には、k=(m-1)/2=(kν-1,...k0)2のハミングウエイト（0以外の要素数）をhw(k)とすると、非特許文献２の方法で必要な有限体GF(3m)上の乗算回数はν+hw(k)回であり、３乗算回数はm-1回である。これに対し、本形態の方法で必要な有限体GF(3m)上の乗算回数は１回であり、３乗算回数はm-1回である。このように、本形態の方法では、演算コストが大きい乗算の回数を非特許文献２の方法に比べて大幅に削減できる。また、非特許文献２の方法ではmの値が大きくなるほど乗算回数が増加するが、本形態の方法はmの値に拘わらず１回である。そのため、従来の非特許文献２の方法では、楕円曲線y2=x3-x+b上で構成される楕円曲線暗号の安全性を向上させるためにmの値（通常、m≧97、具体的にはm=97,167,193,239,353,509などが用いられる）を大きくするほど乗算回数が増加するのに対し、本形態の方法では乗算回数が増加しない。
【００５９】
また、本形態では、yから楕円曲線y2=x3-x+b上のx座標を求めるステップＳ１０７、Ｓ１０８の演算は、有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算のみによって実現できる。このように演算コストが小さい３ｎ乗フロベニウス写像を用いることで、全体の演算コストを大幅に削減できる。なお、ステップＳ１０７、Ｓ１０８の演算の少なくとも一方の３乗算に３ｎ乗フロベニウス写像を用いない構成であってもよい。
【００６０】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。
本形態は、mが1≡m mod 3を満たす正の整数である場合に、式(42)を用い、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する形態である。なお、以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【００６１】
＜構成＞
図３は、第２実施形態の変換演算装置２の機能構成を説明するためのブロック図である。
図３に示すように、本形態の変換演算装置２は、制御部１０１、一時メモリ１０２、入力部１０３、記憶部１０４、変換部１０５、有限体演算部１０６，２０９（「第１，２有限体演算部」に相当）、演算制御部１０７、１／３トレース写像演算部２０８、１／２トレース写像演算部２１１、及び出力部１１０を有する。
【００６２】
変換演算装置２は、ＣＰＵ，ＲＡＭ，ＲＯＭ等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。例えば、有限体演算部２０９、１／２トレース写像演算部２１１、及び１／３トレース写像演算部２０８は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、変換演算装置２は、制御部１０１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１０２に格納され、その他の演算処理の際に読み出されて利用される。
【００６３】
＜変換演算方法＞
次に、本形態の変換演算方法を説明する。
図４は、第２実施形態の変換演算方法を説明するためのフローチャートである。以下、この図を用いて本形態の変換演算方法を説明する。本形態では、mが1≡m mod 3を満たす正の整数であることを前提にする。
【００６４】
まず、第１実施形態で説明したステップＳ１０１〜Ｓ１０６の処理が実行される。ここで、ステップＳ１０５においてTr(t)=0を満たすと判定された場合、Tr(t)=0を満たすと判定されたtが１／２トレース写像演算部２１１に入力される。１／２トレース写像演算部２１１は、ステップＳ１０５でTr(t)=0を満たすと判定されたtを用い、式(24)に示した１／２トレース写像の演算を行ってH(t)∈GF(3m)を求める（ステップＳ２０６）。次に、ステップＳ２０６で得られたH(t)が１／３トレース写像演算部２０８に入力される。１／３トレース写像演算部２０８は、ステップＳ２０６で得られたH(t)を用い、式(28)に示した１／３トレース写像の演算を行ってC(H(t))∈GF(3m)を求める（ステップＳ２０７）。１／３トレース写像演算部２０８は、有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算のみによってC(H(t))∈GF(3m)を計算できる。
【００６５】
次に、有限体演算部２０９にステップＳ２０７で得られたC(H(t))が入力され、有限体演算部２０９は、ステップＳ２０７で得られたC(H(t))を用い、x=C(H(t))3-C(H(t))∈GF(3m)の演算を行う（ステップＳ２０８／式(42)参照）。なお、C(H(t))3∈GF(3m)は、有限体GF(3m)の元u∈GF(3m)を元u3∈GF(3m)へ写像する３乗フロベニウス写像によって計算できる。
【００６６】
次に、出力部１１０が、ステップＳ２０８で得られたx∈GF(3m)と、ステップＳ１０５でTr(t)=0を満たすと判定されたtを算出するためにステップＳ１０４で用いられた元y∈GF(3m)とを出力する（ステップＳ１０９）。
【００６７】
＜本形態の特徴＞
mが1≡m mod 3を満たす正の整数である場合に、本形態の処理を行うことにより、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換することができ、その演算コストは非特許文献２の方法よりも低い。
【００６８】
具体的には、非特許文献２の方法で必要な有限体GF(3m)上の乗算回数はν+hw(k)回であり、３乗算回数はm-1回である。これに対し、本形態の方法で必要な有限体GF(3m)上の乗算回数は１回であり、３乗算回数は2m-1回である。このように、本形態の方法では、演算コストが大きい乗算の回数を非特許文献２の方法に比べて大幅に削減できる。なお、前述のように、３乗算は３ｎ乗フロベニウス写像を用いることで小さな演算コストで計算できる。また、非特許文献２の方法ではmの値が大きくなるほど演算コストが大きな乗算の回数が増加するが、本形態の方法での乗算回数はmの値に拘わらず１回である。そのため、従来の非特許文献２の方法では、楕円曲線y2=x3-x+b上で構成される楕円曲線暗号の安全性を向上させるためにmの値を大きくするほど乗算回数が増加するのに対し、本形態の方法では乗算回数が増加しない。
【００６９】
〔第３実施形態〕
次に、本発明の第３実施形態を説明する。
本形態は、mが1≡m mod 3を満たす正の整数である場合に、式(58)を用い、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する形態である。なお、以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【００７０】
＜構成＞
図５は、第３実施形態の変換演算装置３の機能構成を説明するためのブロック図である。
図５に示すように、本形態の変換演算装置３は、制御部１０１、一時メモリ１０２、入力部１０３、記憶部１０４、変換部１０５、有限体演算部１０６，３０９（「第１，２有限体演算部」に相当）、演算制御部１０７、１／３トレース写像演算部１０８、及び出力部１１０を有する。
【００７１】
変換演算装置３は、ＣＰＵ，ＲＡＭ，ＲＯＭ等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。例えば、有限体演算部３０９は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、変換演算装置３は、制御部１０１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１０２に格納され、その他の演算処理の際に読み出されて利用される。
【００７２】
＜変換演算方法＞
次に、本形態の変換演算方法を説明する。
図６は、第３実施形態の変換演算方法を説明するためのフローチャートである。以下、この図を用いて本形態の変換演算方法を説明する。本形態では、mが1≡m mod 3を満たす正の整数であることを前提にする。
【００７３】
まず、第１実施形態で説明したステップＳ１０１〜Ｓ１０７の処理が実行される。次に、有限体演算部３０９に、ステップＳ１０５でTr(t)=0を満たすと判定されたtと、それに対応するステップＳ１０７で得られたC(t)とが入力され、有限体演算部３０９は、これらを用い、x=t-C(t)3+C(t)∈GF(3m)の演算を行う（ステップＳ３０８／式(58)参照）。なお、C(t)3∈GF(3m)は、有限体GF(3m)の元u∈GF(3m)を元u3∈GF(3m)へ写像する3乗フロベニウス写像によって計算できる。
【００７４】
次に、出力部１１０が、ステップＳ３０８で得られたx∈GF(3m)と、ステップＳ１０５でTr(t)=0を満たすと判定されたtを算出するためにステップＳ１０４で用いられた元y∈GF(3m)とを出力する（ステップＳ１０９）。
【００７５】
＜本形態の特徴＞
mが1≡m mod 3を満たす正の整数である場合に、本形態の処理を行うことにより、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換することができ、その演算コストは非特許文献２の方法よりも低い。
【００７６】
具体的には、非特許文献２の方法で必要な有限体GF(3m)上の乗算回数はν+hw(k)回であり、３乗算回数はm-1回である。これに対し、本形態の方法で必要な有限体GF(3m)上の乗算回数は１回であり、３乗算回数はm回である。このように、本形態の方法では、演算コストが大きい乗算の回数を非特許文献２の方法に比べて大幅に削減できる。なお、前述のように、３乗算は３ｎ乗フロベニウス写像を用いることで小さな演算コストで計算できる。また、非特許文献２の方法ではmの値が大きくなるほど乗算回数が増加するが、本形態の方法はmの値に拘わらず１回である。そのため、従来の非特許文献２の方法では、楕円曲線y2=x3-x+b上で構成される楕円曲線暗号の安全性を向上させるためにmの値を大きくするほど乗算回数が増加するのに対し、本形態の方法では乗算回数が増加しない。
【００７７】
〔第４実施形態〕
次に、本発明の第４実施形態を説明する。
本形態は、第１，３実施形態の組み合わせであり、mが正の整数である場合に、式(58)又は式(37)を用い、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換する形態である。なお、以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【００７８】
＜構成＞
図７は、第４実施形態の変換演算装置４の機能構成を説明するためのブロック図である。
図７に示すように、本形態の変換演算装置４は、制御部１０１、一時メモリ１０２、入力部１０３、記憶部１０４、変換部１０５、有限体演算部１０６（「第１有限体演算部」に相当）、演算制御部１０７、１／３トレース写像演算部１０８、有限体演算部１０９，４０９（「第２有限体演算部」に相当）、条件分岐部４１１、及び出力部１１０を有する。
【００７９】
変換演算装置４は、ＣＰＵ，ＲＡＭ，ＲＯＭ等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。例えば、有限体演算部４０９及び条件分岐部４１１は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、変換演算装置４は、制御部１０１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１０２に格納され、その他の演算処理の際に読み出されて利用される。
【００８０】
＜変換演算方法＞
次に、本形態の変換演算方法を説明する。
図８は、第４実施形態の変換演算方法を説明するためのフローチャートである。以下、この図を用いて本形態の変換演算方法を説明する。本形態では、mが正の整数であることを前提にする。
【００８１】
まず、入力部１０３に任意のビット列ID∈{0,1}*とmと入力され、記憶部１０４に格納される（ステップＳ４０１）。次に、制御部１０１がw=0とし、wを一時メモリ１０２に格納する（ステップＳ１０２）。次に、変換部１０５が、記憶部１０４からビット列ID∈{0,1}*とmを読み出し、一時メモリ１０２からwを読み出し、記憶部１０４から読み出したビット列ID∈{0,1}*を有限体GF(3m)の元y=G(ID)+w ∈GF(3m)に変換する（ステップＳ４０３）。
【００８２】
次に、有限体演算部１０６にステップＳ４０３で得られた元y∈GF(3m)とmが入力され、有限体演算部１０６は、この元y∈GF(3m)を用い、t=y2-b∈GF(3m)の演算を行う（ステップＳ４０４）。次に、演算制御部１０７に、ステップＳ４０４で生成されたt∈GF(3m)とmが入力され、式(23)に示したトレース写像Tr(t)を計算し、Tr(t)=0を満たすか否かを判定する（ステップＳ４０５）。
【００８３】
ここで、Tr(t)=0を満たさないと判定された場合、演算制御部１０７は、ステップＳ４０３における変換方法を変更してステップＳ４０３〜Ｓ４０５の各処理を再び実行させる。本形態の例では、演算制御部１０７が一時メモリ１０２から読み出したwからw+1を求め、求めたw+1を新たなwとして一時メモリ１０２に格納し、処理をステップＳ４０３に戻す（ステップＳ１０６）。
【００８４】
一方、ステップＳ４０５においてTr(t)=0を満たすと判定された場合、Tr(t)=0を満たすと判定されたtとmが１／３トレース写像演算部１０８に入力される。１／３トレース写像演算部１０８は、ステップＳ４０５でTr(t)=0を満たすと判定されたtとmを用い、式(28)に示した１／３トレース写像の演算を行ってC(t)∈GF(3m)を求める（ステップＳ４０７）。１／３トレース写像演算部１０８は、有限体GF(3m)の元u∈GF(3m)を元us∈GF(3m)（s=3n，nは1以上の整数）へ写像する３ｎ乗フロベニウス写像と、有限体GF(3m)上での加算のみによってC(t)∈GF(3m)を計算できる。次に、有限体演算部１０９にステップＳ１０７で得られたC(t)とmが入力され、有限体演算部１０９は、これらを用い、x=C(t)3-C(t)∈GF(3m)の演算を行う（ステップＳ４０８／式(37)参照）。なお、C(t)3∈GF(3m)は、有限体GF(3m)の元u∈GF(3m)を元u3∈GF(3m)へ写像する3乗フロベニウス写像によって計算できる。
【００８５】
次に、条件分岐部４１１に、ステップＳ４０８で得られたxとmとが入力され、条件分岐部４１１が1≡m mod 3を満たすか否かを判定する（ステップＳ４０９）。ここで、1≡m mod 3を満たさないと判定された場合、次に、出力部１１０が、ステップＳ４０８で得られたx∈GF(3m)と、ステップＳ４０５でTr(t)=0を満たすと判定されたtを算出するためにステップＳ４０４で用いられた元y∈GF(3m)とを出力する（ステップＳ１０９）。
【００８６】
一方、1≡m mod 3を満たすと判定された場合、有限体演算部４０９にステップＳ４０８で得られたxとmとが入力され、有限体演算部４０９がt-x∈GF(3m)の演算を行い、その演算結果を新たなx∈GF(3m)とする（ステップＳ４１０）。そして、出力部１１０が、ステップＳ４１０で得られたx∈GF(3m)と、ステップＳ４０５でTr(t)=0を満たすと判定されたtを算出するためにステップＳ４０４で用いられた元y∈GF(3m)とを出力する（ステップＳ１０９）。
【００８７】
＜本形態の特徴＞
mが1≡m mod 3又は2≡m mod 3を満たす正の整数である場合に、本形態の処理を行うことにより、任意のビット列ID∈{0,1}*を、標数3の有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換することができ、その演算コストは非特許文献２の方法よりも低い。
【００８８】
なお、本形態では、第１，３実施形態を組み合わせ、1≡m mod 3を満たすか否かによって、第３実施形態の方法（1≡m mod 3の場合）又は第１実施形態の方法（2≡m mod 3の場合）をとることとした。しかし、第１，２実施形態を組み合わせ、1≡m mod 3を満たすか否かによって、第２実施形態の方法（1≡m mod 3の場合）又は第１実施形態の方法（2≡m mod 3の場合）をとることにしてもよい。
【００８９】
〔シミュレーション結果〕
次に、シミュレーション結果を示す。以下では、第４実施形態で説明した方法の演算時間を例示する。
【表１】
2010164796.tif 000025
【００９０】
表１は、各m=97,167,193,239,353,509の有限体GF(3m)上での各演算時間（μsec）を示している。ここで、加算，乗算，３乗算に対応する各演算時間は、それぞれ、有限体GF(3m)上での加算，乗算，３乗算の各１回分の演算時間を示す。なお、３乗算は３ｎ乗フロベニウス写像を用いた演算である。また、従来法に対応する各演算時間は、非特許文献２の方法で任意のビット列を有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換するための演算時間を示す。また、提案法に対応する各演算時間は、第４実施形態で説明した方法で任意のビット列を有限体GF(3m)上で定義された楕円曲線y2=x3-x+b上の点(x,y)に変換するための演算時間を示す。また、用いた次数mと既約多項式f(x)=xm+xτ+2は、(m,τ)={(97,12),(167,96),(193,12),(239,24),(353,142),(509,358)}であり、それらの根x∈GF(3m)を用いて前述のように各基底（δi=xi）を定めた。また、本実装には、Ｃ言語，GCC4.2.2-03オプションを用い、計算時間の測定には、AMD Opteron processor(2.2 GHz)をLinux/x86_64上で動作させた。また、表１の各演算時間は、各演算を1,000,000回以上行ってその平均を求めたものである。実装にはSSEなどの拡張命令は使用していない。表１に示すように、提案法は、どの次数においても従来法よりも1.5倍程度高速に変換演算ができることが分かる。
【００９１】
〔その他の変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００９２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００９３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００９６】
本発明の利用分野としては、例えば、楕円曲線上のペアリング演算を利用するＩＤベース暗号分野やその他の楕円曲線分野も例示できる。
【符号の説明】
【００９７】
１〜４  変換演算装置
【図１】
2010164796.tif 000040
【図２】
2010164796.tif 000041
【図３】
2010164796.tif 000042
【図４】
2010164796.tif 000043
【図５】
2010164796.tif 000044
【図６】
2010164796.tif 000045
【図７】
2010164796.tif 000046
【図８】
2010164796.tif 000047