(57)【要約】  有理点群の埋め込み次数を１とした場合において、有理点情報を圧縮・復元する有理点情報圧縮装置、有理点情報圧縮方法、及び有理点情報圧縮プログラムを提供する。標数Pの有限体Fp上で定義された楕円曲線上の有理点のなす加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち加法群の部分群をG1=E(Fp)[r], G2=E(Fp)[r]として、有理点P∈G1, Q∈G2を送信する際にR=P+Qとして有理点Rに圧縮し、受信先で、有理点Rから有理点P,Qを分解・復元することにより、送受信に伴うデータ長を短縮する。
2012046805.tif 000002
【特許請求の範囲】
【請求項１】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、
有理点P∈G1及び有理点Q∈G2の情報を送受信するCPU及び記憶手段を備えた有理点情報圧縮装置において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUは、
有理点P’を入力して前記記憶手段に記憶する入力手段と、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段と、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、
前記有理点P及び前記有理点Qから有理点R＝P+Qを演算する第1演算手段と、
前記有理点Rから有理点P及び有理点Qを演算する第2演算手段と、
を有する有理点情報圧縮装置。
【請求項２】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy), ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[λ1][ψ+λ1]R=[-2]P, Q=R-P  を用いて行う請求項１に記載の有理点情報圧縮装置。
【請求項３】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1+1][ψ+λ1 +1]R=[-3]P, Q=R-P  を用いて行う請求項１に記載の有理点情報圧縮装置。
【請求項４】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1-1][ψ+λ1 -1]R=[-3]P, Q=R-P  を用いて行う請求項１に記載の有理点情報圧縮装置。
【請求項５】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、
有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機で行う情報圧縮方法において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを入力手段として機能させて、有理点P’を入力して前記記憶手段に記憶する入力ステップと、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定するステップと、
前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P) またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、
前記電子計算機のCPUを第1演算手段として機能させて、前記有理点P及び前記有理点Qから有理点R=P+Qを演算する第1演算ステップと、
前記電子計算機のCPUを第2演算手段として機能させて、前記有理点Rから有理点P及び有理点Qを演算する第2演算ステップと、
を有する有理点情報圧縮方法。
【請求項６】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy), ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記第２演算ステップは、前記有理点P, 前記有理点Qの演算を、それぞれ
[λ1][ψ+λ1]R=[-2]P, Q=R-P  を用いて行う請求項５に記載の有理点情報圧縮方法。
【請求項７】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算ステップは、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1+1][ψ+λ1 +1]R=[-3]P, Q=R-P  を用いて行う請求項５に記載の有理点情報圧縮方法。
【請求項８】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算ステップは、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1-1][ψ+λ1 -1]R=[-3]P, Q=R-P  を用いて行う請求項５に記載の有理点情報圧縮方法。
【請求項９】
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、
有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機に行わせる有理点情報圧縮プログラムにおいて、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを
有理点P’を入力して前記記憶手段に記憶する入力手段、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P)またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、
前記有理点P及び前記有理点Qから有理点R=P+Qを演算する第1演算手段、
前記有理点Rから有理点P及び有理点Qを演算する第2演算手段、
として機能させる有理点情報圧縮プログラム。
【請求項１０】
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r) を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy), ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[λ1][ψ+λ1]R=[-2]P, Q=R-P  を用いて行う請求項９に記載の有理点情報圧縮プログラム。
【請求項１１】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1+1][ψ+λ1 +1]R=[-3]P, Q=R-P  を用いて行う請求項９に記載の有理点情報圧縮プログラム。
【請求項１２】
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1-1][ψ+λ1-1]R=[-3]P, Q=R-P  を用いて行う請求項９に記載の有理点情報圧縮プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線暗号、ペアリング暗号における有理点情報圧縮装置、有理点情報圧縮方法及び有理点情報圧縮プログラムに関する。特に有理点群の埋め込み次数を１とした場合の、楕円曲線暗号、ペアリング暗号における有理点情報圧縮装置、有理点情報圧縮方法及び有理点情報圧縮プログラムに関する。
【背景技術】
【０００２】
昨今、インターネットなどの電気通信回線を利用した情報ネットワーク技術が高度に発展し、インターネットによって様々な情報を取得するだけでなく、インターネットバンキングや行政機関への電子申請などのような各種のサービスが提供されてきている。【０００３】
このようなサービスを利用する場合には、サービスの利用者が成りすましや架空の人間などではなく、適正な利用者であることを確認するための認証処理が必要であり、信頼性の高い認証方法として、公開鍵と秘密鍵を用いる公開鍵暗号をベースとした電子認証技術がよく利用されている。【０００４】
しかしながら、公開鍵暗号方式の電子認証では、公開鍵及び秘密鍵が漏洩した場合には直ちに公開鍵と秘密鍵を変更する必要がある。このため、公開鍵及び秘密鍵の管理を慎重に行わなければならず、また、必要に応じて新たな公開鍵と秘密鍵の設定登録作業が生じるという煩雑さがある。このため、最近では、利用者の氏名やメールアドレスのように利用者特有のIDを用いて電子認証を行うIDベース暗号が用いられることが多くなっている。【０００５】
また、電子認証を行う認証装置によって利用者の個人認証を行った場合には、認証装置に利用者ごとの履歴が蓄積されることとなる。この履歴情報自体が利用者の個人情報であるため、最近では、この履歴情報が漏洩することによる個人情報の漏洩のおそれが指摘されている。【０００６】
そこで、認証装置では利用者の個人情報を利用して認証を行うのではなく、複数の利用者をひとまとまりのグループとして、このグループに所属していることを示すグループ署名を用いることにより、利用者を特定することなく認証を行うことによって、認証装置に個人情報が蓄積されることなく認証を可能としたグループ署名技術が提案されている。【０００７】
国家UNS戦略プログラムにおいても、プライバシを保護しつつユーザ認証を行うことのできる匿名認証技術の重要性、必要性が取り上げられている。
UNS:Universal Communications、New Generation Networks、Security and safety【０００８】
このようなIDベース暗号やグループ署名等を簡便に実現するための数学的な土台としてペアリング暗号がある。ペアリングとは、楕円曲線上で定義される２入力１出力の関数であり、入力は楕円曲線上の２つの有理点、出力は有限体の元が用いられている。このペアリングは２入力に対して双線形性を持つ。例えば、Pを素体Fp上で定義される楕円曲線上の有理点、Qをk次拡大体Fpk上で定義される楕円曲線上の有理点として、PとQを入力して拡大体F*pkの元ｚが出力されるとき、a倍のPとｂ倍のQを入力するとｚのab乗が出力される。ペアリング暗号では、この双線形性を利用して暗号システムを構築する。なお、ここで「ｋ」を埋め込み次数と呼び「F*pk」は、位数がpｋである有限体（拡大体）から単位元０を除いた乗法群を表わす。【０００９】
楕円曲線上の有理点とは、楕円曲線ｙ２＝ｘ３+ax＋ｂを満たす有限体Fqの元の座標（x,y）の組をいう。この集合に無限遠点Oを加えたものは加法群を成し、E(Fq)と表わす。すなわち、楕円曲線上の2つの有理点P、Qを通る直線が楕円曲線と交わる点のｘ軸を対称とした点をRとすれば、P+Q=Rが成立する。この演算を楕円加算と呼ぶ。PとQが同一点の場合はPを通る接線が楕円曲線と交わる点のｘ軸を対称とした点をRとすれば、P＋P=2P=Rが成立する。この演算を楕円２乗算と呼ぶ。ペアリング暗号及び楕円暗号の安全性の根拠は楕円曲線上の離散対数問題の求解困難性に基づいている。素因数分解の困難性を安全性の根拠とするRSA暗号等と比べ、はるかに短い鍵長で同等の暗号強度（安全性強度）を実現できる。【００１０】
ディジタルグループ署名では、グループに所属する個人ユーザのアクセス権の認証処理を行う際に、アクセス権が失効している個人ユーザを除外するためのペアリング演算を行った後に所定の個人ユーザのペアリング演算を行って認証処理を行うことにより、個人ユーザごとのアクセス権の発行または失効の属性変更に柔軟に対応可能としている。【００１１】
したがって、例えば、10,000人の個人ユーザで構成されるグループのディジタルグループ署名の場合、アクセス権が失効している個人ユーザが100人いれば、100回のペアリング演算が必要となっており、現時点での一般的な電子計算機による1回のペアリング演算に約0.1秒を要していることから、100回のペアリング演算には約10秒を要することとなってしまうため、実用上、個人ユーザの数が制限されることとなって、広く利用されるものとはなっていなかった。【００１２】
そこで、ペアリング演算の演算速度を向上させることによりディジタルグループ署名の実用性を向上させるために、例えば、ペアリング演算として楕円曲線上で定義されるTateペアリング演算法を用い、演算負荷を低減させて高速化を図る技術が提案されている。【００１３】
このように、これまでペアリングを用いた暗号方式（IDベース暗号、グループ署名等）は数多く提案されているが、その多くは、160ビット以上の素数位数を持つペアリング曲線（ペアリングに効率のよい楕円曲線）を用いるものである。本発明者らはこれまで、土台の数学的構造から、拡大体における計算、楕円曲線暗号の計算、ペアリング計算について出願を行なってきた。そのいずれもが、素数位数のペアリング暗号を効率化するものである。【００１４】
一方、近年、有理点群の埋め込み次数が１で2000ビットを超える合成数位数を持つペアリング曲線を用いるものが提案されており、また新たなアプリケーションも提案されている（例えば、非特許文献１参照。）。【００１５】
素数位数のペアリング暗号を効率化するこれまでの手法は、本発明がターゲットとする大きな合成数位数のペアリングに対して即座に適用できるものではない。言い換えれば、合成数位数のペアリング曲線は埋め込み次数が１となるなど特殊な状況におかれるため、これを考慮した新たな高速化手法を提案する必要性がでてきた。埋め込み次数を１とする理由は、ペアリング暗号の暗号強度を必要十分に確保するための強度と効率のバランスを図るのに最も適しているのが埋め込み次数１だからである。埋め込み次数を大きくした場合は暗号強度が十分すぎ、また実現する上での効率が悪くなる。【００１６】
このようなペアリング暗号または楕円曲線暗号のプロトコルでは、複数の有理点の情報をネットワークで送受信することとなる。例えば、有理点Pと有理点Qを送信するなどである。これらの有理点を個別に送れば、合成数位数が2000ビットとすると、標数は4000ビットとなり、有理点P,Qのｘ座標、y座標を考えると、４倍の16000ビットを送信することとなる。【００１７】
電子認証システムでは、大量のユーザリストが送受信され、ペアリング計算時間とともに、これら多数の有理点情報を含むユーザリストのネットワーク上での送受信時間が問題となっている。【００１８】
これに対し、上記の例で、もし有理点P及びQのペアに対し、R=P+Qという楕円加算して圧縮した有理点Rを送信し、受信先で元の有理点P及びQを復元できれば、その送信する情報量はこのペア当たり半分の8000ビットで済むことになる。【００１９】
有理点の圧縮方法については、例えば、非特許文献２、特許文献１などが知られている。特許文献１では、有限体Fq及び拡大体Fqk上の有理点2点を楕円加算して圧縮し、受信先で射影により元の有理点を復元する方法等が開示されている。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開2008-178035号公報
【非特許文献】
【００２１】
【非特許文献１】D. Boneh, K. Rubin and A. Silverberg, “Finding Composite Order Ordinary Elliptic Curves Using the Cock-Pinch method”
【非特許文献２】Ian F.Blake et al, “Advances in Elliptic Curve Cryptography”
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかしながら、本発明が対象とする有理点群の埋め込み次数が１の場合、有理点P及びQを圧縮して有理点Rを送信し、受信先でこれを分解・復元する方法は、これまで知られていなかった。【００２３】
本発明者らは、このような現状に鑑み、有理点の情報圧縮を効率的に行うべく研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００２４】
本発明の有理点情報圧縮装置では、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、
有理点P∈G1及び有理点Q∈G2の情報を送受信するCPU及び記憶手段を備えた有理点情報圧縮装置において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUは、
有理点P’を入力して前記記憶手段に記憶する入力手段と、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段と、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P)またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、
前記有理点P及び前記有理点Qから有理点R＝P+Qを演算する第1演算手段と、
前記有理点Rから有理点P及び有理点Qを演算する第2演算手段と、
を有することとした。【００２５】
さらに本発明の有理点情報圧縮装置では、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy), ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[λ1][ψ+λ1]R=[-2]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００２６】
本発明の有理点情報圧縮装置では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1+1][ψ+λ1 +1]R=[-3]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００２７】
さらに本発明の有理点情報圧縮装置では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12-λ1+1≡0(mod r)、λ22-λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1-1][ψ+λ1 -1]R=[-3]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００２８】
本発明の有理点情報圧縮方法では、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、
有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機で行う情報圧縮方法において、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを入力手段として機能させて、有理点P’を入力して前記記憶手段に記憶する入力ステップと、
前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定するステップと、
前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P)またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、
前記電子計算機のCPUを第1演算手段として機能させて、前記有理点P及び前記有理点Qから有理点R=P+Qを演算する第1演算ステップと、
前記電子計算機のCPUを第2演算手段として機能させて、前記有理点Rから有理点P及び有理点Qを演算する第2演算ステップと、
を有することとした。【００２９】
さらに本発明の有理点情報圧縮方法では、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy), ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記第２演算ステップは、前記有理点P, 前記有理点Qの演算を、それぞれ
[λ1][ψ+λ1]R=[-2]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００３０】
さらに本発明の有理点情報圧縮方法では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算ステップは、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1+1][ψ+λ1 +1]R=[-3]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００３１】
さらに本発明の有理点情報圧縮方法では、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算ステップは、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1-1][ψ+λ1 -1]R=[-3]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００３２】
本発明の有理点情報圧縮プログラムでは、
標数ｐの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をE(Fp)とし、合成数位数ｒを持つ有理点の集合すなわち前記加法群の部分群をG1=E(Fp)[r]、G2=E(Fp)[r]として、
有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機に行わせる有理点情報圧縮プログラムにおいて、
前記加法群E(Fp)は、埋め込み次数を１とし、
前記電子計算機のCPUを
有理点P’を入力して前記記憶手段に記憶する入力手段、
前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、
λ1P=ψ(P)、λ２Q=ψ(Q)  （λ1≠λ２は整数）を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段、
前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψ(P)またはψ(Q)を演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、
前記有理点P及び前記有理点Qから有理点R=P+Qを演算する第1演算手段、
前記有理点Rから有理点P及び有理点Qを演算する第2演算手段、
として機能させることとした。【００３３】
さらに本発明の有理点情報圧縮プログラムでは、
前記楕円曲線は、 E:y2 = x3 +ax, a∈Fp, 4|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 4|(r-1) を満たし、
前記整数λ1、λ2は、λ12+1≡0(mod r)、λ22+1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (-x,ζy), ζ4=1, ζ,ζ2(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[λ1][ψ+λ1]R=[-2]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００３４】
さらに本発明の有理点情報圧縮プログラムでは、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 3|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1+1][ψ+λ1 +1]R=[-3]P, Q=R-P  を用いて行うことにも特徴を有するものである。【００３５】
さらに本発明の有理点情報圧縮プログラムでは、
前記楕円曲線は、 E:y2 = x3 +b, b∈Fp, 6|(p-1) であり、
前記合成数位数ｒは、r|#E(Fp), 3|(r-1) を満たし、
前記整数λ1、λ2は、λ12+λ1+1≡0(mod r)、λ22+λ2 +1≡0(mod r)を満たし、
前記自己準同型写像は、ψ:E(Fp)[r] → E(Fp)[r]、
(x,y) → (εx,-y),ε3=1,ε(≠1)∈Fp  であり、
前記第2演算手段は、前記有理点P, 前記有理点Qの演算を、それぞれ
[2λ1-1][ψ+λ1 -1]R=[-3]P, Q=R-P  を用いて行うことにも特徴を有するものである。
【発明の効果】
【００３６】
本発明によれば、有理点P,Qの情報を送信する時に有理点Pと有理点Qの楕円加算を行い求めた有理点Rの情報を送信し、受信先で有理点Rの情報を分解し有理点P,Qの情報を復元することとなり、送受信する有理点の情報量を半分に圧縮することができる。この分解復元に要する計算は、有理点のペアあたり、おおよそスカラー倍算1回分である。このことにより、インターネット等のネットワークを介して有理点情報を送受信する際の効率化を図ることができる。
【図面の簡単な説明】
【００３７】
【図１】本発明の実施形態にかかる情報圧縮装置の概略模式図である。
【図２】本発明の実施形態にかかるクライアント装置上の情報圧縮装置の全体構成を例示したブロック図である。
【図３】本発明の実施形態にかかる認証サーバ上の情報圧縮装置の全体構成を例示したブロック図である。
【図４】本発明の実施形態にかかる有理点部分群特定部の機能構成を例示した図である。
【図５】本発明の実施形態にかかる有理点情報復元部の機能構成を例示した図である。
【図６】本発明の実施形態にかかる有理点情報復元プログラムのフローチャートである。
【図７】本発明の実施形態にかかる有理点部分群特定部プログラムのフローチャートである。
【発明を実施するための形態】
【００３８】
本発明の成果を適用できるようなペアリング曲線は、以下のような条件を満たす必要がある。まず、標数ｐの有限体Fp上で定義される楕円曲線を、
E/Fp: y2 = x3 +ax +b, a∈Fp b∈Fpとし、
E(Fp):標数ｐの有限体Fp上で定義される楕円曲線の有理点が成す加法群、
ｒ：E(Fp)の位数#E(Fp)を割り切る合成数、
E[r]：位数が合成数ｒである有理点の集合、
ψ:有理点に対する自己準同型写像、
ｔ：フロベニウス写像のトレース、
[j]：有理点をｊ倍する写像、
G：G=E[r]∩Ker(ψ-λ)、（λは整数）を満たす有理点の集合、と定義する。
また、ｘ｜ｙは、ｘがｙを割り切ることを表わすものとする。
【００３９】
楕円曲線の生成にはCM（Complex Multiplication）法が知られている。標数ｐ、フロベニウス自己準同型写像のトレースｔ、判別式Dによる次式のようなCM方程式において、判別式D=1,3の場合を考える。
4p=t2-Ds2 (1)
この時、ペアリング曲線の式はそれぞれ以下のように与えられる。
Ea: y2 = x3 +ax, a∈Fp   (D=1) (2a)
Eb: y2 = x3 +b, b∈Fp (D=3) (2b)
本発明者らは、大きな合成数位数に対してこのようなペアリング曲線を生成する簡便な生成法を提案済みである。上記のペアリング曲線上の有理点が、簡単な自己準同型写像ψ（即ち有理点をP、整数をλとして、ψ(P)=λP）を持つためには、パラメータの条件がある。これには、以下に示すように、自己準同型写像の周期３，４，６に対応して3次、4次、6次の3つの場合がある。この自己準同型写像はスカラー倍算、ペアリングに用いる他、本発明では、この自己準同型写像を有理点情報の圧縮・復元に用いる。以下に、パラメータの条件及びその写像を示す。
【００４０】
＜3次の場合＞
楕円曲線のパラメータが、3|(p-1), E: y2 =x3 +b, b∈Fp, D=3の場合、
r|#E(Fp), 3|(r-1)  を満たす合成数ｒに対して、次式を満足するある整数λ3が存在する。
λ3２+λ3 +1≡0 (mod r) (3)
また、以下に示す周期３の自己準同型写像ψ３が与えられる。
【数１】
2012046805.tif 000003
このような合成数ｒを位数として持つ有理点をP∈E(Fp)[r]とすれば、3次の場合、[λ3]P=ψ3(P)の関係を用いることで後述の有理点情報圧縮の効率化を図っている。
【００４１】
しかしながら、有理点群の埋め込み次数が１の場合、一般の有理点P’∈E(Fp)[r]に対しては、[λ3]P’=ψ３(P’)は成り立たない。上述したように、これを満たすような有理点の割合は1／ｒ＝1／22000  であり、簡便にそのような有理点及び有理点部分群を準備できる必要がある。
【００４２】
本発明では、本発明者らが発見した以下の性質を用いる。
まず、任意の有理点P’∈E(Fp)[r]は次式を満たす。
[(ψ３-λ3)( ψ３ +λ3  +1)]P’=O   (5)
ここで、Oは、無限遠点を示す。以下の記述においても同様である。
すなわち、ランダムに生成した有理点P’∈E(Fp)[r]を(ψ３ +λ3  +1)倍し、
P=[ψ３ +λ3  +1]P’ (6)
とすることにより、その有理点Pは[λ3]P= ψ３(P)を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1  とする。また逆に、
Q=[ψ３ -λ3]P’   (7)
とすれば、[λ3  +1]Q= -ψ３(Q)を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2  とする。これらG1  及びG2 を用いて後述の有理点情報の圧縮・復元を実現することができる。
【００４３】
＜関係式の導出法の説明＞
3次の場合の式(5)の導出について以下に説明する。
まず、任意の有理点P’∈E(Fp)[r]は、E(Fp)のフロベニウス写像のトレースｔ及びフロベニウス写像φを用いて、次式を満たすことが知られている。
φ:(x,y)→(xp,yp)
(φ2 -tφ+[p])P’= O (8)
同様に、P’をE(Fp)と同型な群を内包する拡大体上ツイスト曲線E’(Fp３)に写像した有理点P~を考えれば、E’(Fｐ)のフロベニウス写像のトレースをt’として次式を満たす。
(φ2 -t’φ+[p])P~= O (9)
ここで、ツイスト曲線は、E’:y2 = x3+bv-2,b∈Fｐで与えられ、ｖはFｐの３乗非剰余な元であり、P~は、P’=(x,y)として以下で与えられる。
P~ = (xv2/3,yv) (10)
ここで、上式を写像ψ: P’∈E(Fp)→P~∈E’(Fp3)とすれば、式(9)は次式のように変形できる。
{（ψ-1φ2ψ）-t’(ψ-1φψ）+[p]}P’= O (11)
そしてこの場合、ψ-1φψ=ψ3が成り立つので次式を得る。
(ψ32-t’ψ3+[p])P’= O (12)
上式に対して、有理点群の埋め込み次数が１であることからｐ≡1 (mod r)であり、加えてこれに用いる楕円曲線をt’≡-1(3次)、0(4次)、1(6次) (mod r) となるように生成していることから、P’∈E(Fp)[r] （位数ｒの有理点）とすれば、３次のときには次式を得る。
(ψ32 ＋ψ3+[1])P’= O (13)
一方で3次の場合には、式(3)を満たすような整数λ3も存在し、すなわちψ32 ＋ψ3+1≡0(mod r)を、ψ3を変数とするような方程式と考えれば、その解の１つがψ3となる。したがって、式(5)のような因数分解された関係式が得られる。
【００４４】
＜4次の場合＞
同様に、楕円曲線のパラメータが、4|(p-1), E: y2=x3+ax, a∈Fp, D=1の場合、
r|#E(Fp), 4|(r-1)  を満たす合成数ｒに対して、次式を満足するある整数λ4が存在する。
λ42+1≡0 (mod r) (14)
また、以下に示す周期４の自己準同型写像ψ4が与えられる。
【数２】
2012046805.tif 000004
このような合成数ｒを位数として持つ有理点をP∈E(Fp)[r]とすれば、４次の場合、[λ4]P=ψ4(P)の関係を用いることで後述の有理点情報圧縮の効率化を図っている。
【００４５】
本発明では、本発明者らが発見した以下の性質を用いる。
まず、任意の有理点P’∈E(Fp)[r]は次式を満たす。
[(ψ4-λ4)( ψ4 +λ4)]P’= O (16)
すなわち、ランダムに生成した有理点P’∈E(Fp)[r]を(ψ4 +λ4  )倍し、
P=[ψ4 +λ4]P’ (17)
とすることにより、その有理点Pは[λ4]P= ψ4(P)を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1  とする。また逆に、
Q=[ψ4 -λ4]P’   (18)
とすれば、[λ4]Q= -ψ4(Q)を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2  とする。これらG1  及びG2 を用いて後述の有理点情報の圧縮・復元を実現することができる。
【００４６】
4次の場合の式(16)の導出については、3次の場合と同様であるので説明は省略する。
【００４７】
＜６次の場合＞
さらに同様に、楕円曲線のパラメータが、6|(p-1), E: y2 =x3+b, b∈Fp, D=3の場合、
r|#E(Fp), 3|(r-1)  を満たす合成数ｒに対して、次式を満足するλ6が存在する。
λ62-λ6 +1≡0 (mod r) (19)
また、以下に示す周期６の自己準同型写像ψ6が与えられる。
【数３】
2012046805.tif 000005
このような位数ｒを持つ有理点をP∈E(Fp)[r]とし、6次の場合、[λ6]P=ψ6(P)の関係を用いることで後述の有理点情報圧縮の効率化を図っている。
【００４８】
本発明では、本発明者らが発見した以下の性質を用いる。
まず、任意の有理点P’∈E(Fp)[r]は次式を満たす。
[(ψ6-λ6)( ψ6 +λ6 -1)]P’= O (22)
すなわち、ランダムに生成した有理点P’∈E(Fp)[r]を(ψ6 +λ6 -1)倍し、
P=[ψ6 +λ6 -1]P’ (23)
とすることにより、その有理点Pは[λ6]P= ψ6(P)を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1  とする。また逆に、
Q=[ψ6 -λ6]P’   (24)
とすれば、[λ6 -1]Q= -ψ6(Q)を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2  とする。これらG1  及びG2 を用いて後述の有理点情報の圧縮・復元を実現することができる。
【００４９】
6次の場合の式(22)の導出についても、3次の場合と同様であるので説明は省略する。
【００５０】
本発明の有理点情報の圧縮装置、圧縮方法及び圧縮プログラムでは、有理点群の埋め込み次数が１の場合において、有理点部分群G1、G2を特定し、2つの有理点P∈G1、Q∈G2 を送信する際に有理点P,Qを楕円加算して圧縮した有理点Rを送信している。受信先での元の有理点情報P,Qへの分解・復元は、上述のG1、 G２の特性を利用して行う。以下に4次、3次、及び6次の場合について説明する。いずれもスカラー倍算1回程度の計算で、有理点情報を分解・復元できる。
【００５１】
＜4次の場合＞
まず、有理点P,  Qは次式を満たす。
[λ4]P=ψ4(P), [λ4]Q=-ψ4(Q) (25)
すなわち、言い換えればそれぞれ次式を満たす。
[ψ4-λ4]P=O, [ψ4+λ4]Q=O (26)
したがって、受信データR=P+Qに対して、例えば、[ψ4+λ4]倍算を施せば、
[ψ4+λ4]R=[ψ4+λ4](P+Q)
=[ψ4+λ4]P+[ψ4+λ4]Q
=[ψ4+λ4]P+ O
=ψ4(P)+[λ4]P
=[λ4]P+[λ4]P
=2[λ4]P
となり、両辺にλ4  を乗じて、r=λ42+1≡0を適用すれば次式を得る。
[λ4][ψ4+λ4]R=2[λ42]P=[-2]P
これに[-2-1mod r]倍算を施せばPを得ることができる。Qは、Q=R-Pにより求めることができる。このようにスカラー倍算1回くらいの計算量で分解・復元ができるため、情報圧縮してデータを送信することの効率化を図ることができる。
【００５２】
<3次の場合＞
まず、有理点P,  Qは次式を満たす。
[λ3]P=ψ3(P), [λ3+1]Q=-ψ3(Q) (27)
すなわち、言い換えればそれぞれ次式を満たす。
[ψ3-λ3]P= O, [ψ3+λ3+1]Q= O (28)
したがって、受信データR=P+Qに対して、例えば[ψ3+λ3+1]倍算を施せば、
[ψ3+λ3+1]R=[ψ3+λ3+1](P+Q)
=[ψ3+λ3+1]P+[ψ3+λ3+1]Q 
=[ψ3+λ3+1]P+ O
=ψ3(P)+[λ3]P+P
=[2λ3+1]P
となり、両辺に[2λ3+1] を乗じて、r=λ32+λ3+1≡0 を適用すれば次式を得る。
[2λ3+1][ψ3+λ3+1]R=[2λ3+1]2P
=[4λ32+4λ3+1]P
=[-3]P (29)
これに[-3-1mod r]倍算を施せばPを得ることができる。Qは、Q=R-P  により求めることができる。このようにスカラー倍算1回くらいの計算量で分解・復元ができるため、情報圧縮してデータを送信することの効率化を図ることができる。
【００５３】
<6次の場合＞
まず、有理点P,  Qは 次式を満たす。
[λ6]P=ψ6(P), [λ6-1]Q=-ψ6(Q) (30)
すなわち、言い換えればそれぞれ次式を満たす。
[ψ6-λ6]P= O, [ψ6+λ6-1]Q= O (31)
したがって、受信データR=P+Qに対して、例えば[ψ6+λ6-1]倍算を施せば、
[ψ6+λ6-1]R=[ψ6+λ6-1](P+Q)
=[ψ6+λ6-1]P+[ψ6+λ6-1]Q 
=[ψ6+λ6-1]P+ O
=ψ6(P)+[λ6]P-P
=[2λ6-1]P (32)
となり、両辺に[2λ6-1] を乗じて、r=λ62-λ6+1≡0 を適用すれば次式を得る。
[2λ6-1][ψ6+λ6-1]R=[2λ6-1]2P
=[4λ62-4λ6+1]P
=[-3]P (33)
これに[-3-1mod r]倍算を施せばPを得ることができる。Qは、Q=R-P  により求めることができる。このようにスカラー倍算1回くらいの計算量で分解・復元ができるため、情報圧縮してデータを送信することの効率化を図ることができる。
【００５４】
上述したように、4次の場合には、2-1 倍算が、3次及び6次の場合は、3-1倍算が必要となる。これらのスカラー倍算は通常のスカラー倍算よりも効率よく求めることができる。
【００５５】
＜2-1 倍算＞
まず、r=λ42+1 に注意すれば、2-1mod r は、次式で求めることができる。ここで、λ4 が偶整数であることに注意する。
2-1=(r+1)/2
=(λ42+2)/2
=λ4・(λ4/2)+1
すなわち、有理点Tに対する2-1 倍算は、以下のようになる。
[2-1]T=[λ4・(λ4/2)+1]T
=ψ4([λ4/2]T)+T
すなわち、実質的には、λ4/2 程度の計算量で求められ、これはrのビットサイズの約半分なので計算コストは通常のスカラー倍算の半分になる。
【００５６】
＜3-1 倍算＞
3次の場合の3-1 倍算は、r=λ32+λ3+1 に注意すれば以下のように求まる。
3-1=(2r+1)/3
=(2λ32+2λ3+3)/3
=(2λ3(λ3+1)+3)/3
=λ3・2(λ3+1)/3+1
ただしこの場合、λ3+1 は、３の倍数であることが条件である。
すなわち、有理点Tに対する3-1 倍算は、以下のようになる。
[3-1]T=[λ3・2(λ3+1)/3+1]T
=ψ3([2(λ3+1)/3]T)+T
すなわち、実質的には、λ3・2/3 程度の計算量で求められ、これはrのビットサイズの約半分なので計算コストは通常のスカラー倍算の半分になる。
【００５７】
6次の場合の3-1倍算は、r=λ62-λ6+1 に注意すれば以下のように求まる。
3-1=(2r+1)/3
=(2λ62-2λ6+3)/3
=(2λ6(λ6-1)+3)/3
=λ6・2(λ6-1)/3+1
ただしこの場合、λ6-1 は、３の倍数であることが条件である。
すなわち、有理点Tに対する3-1 倍算は、以下のようになる。
[3-1]T=[λ6・2(λ6-1)/3+1]T
=ψ6([2(λ6-1)/3]T)+T
すなわち、実質的には、λ6・2/3 程度の計算量で求められ、これはrのビットサイズの約半分なので計算コストは通常のスカラー倍算の半分になる。
【００５８】
以下において、本発明の実施形態について、図を用いて説明する。
図１は、本発明の実施形態にかかる有理点情報圧縮装置の概略模式図である。
図２は、本発明の実施形態にかかるクライアント装置上の有理点情報圧縮装置100の全体構成を例示したブロック図である。
図3は、本発明の実施形態にかかる認証サーバ上の有理点情報圧縮装置200の全体構成を例示したブロック図である。
まず、図1、図2、及び図3を用いてこの形態の全体について説明し、次にその詳細について説明する。
なお、本実施形態では、所要の電子計算機で構成された認証サーバ及びクライアント装置によってディジタルグループ署名の認証処理を行う際に、与えられたペアリング曲線から上述した有理点部分群を特定するプログラム、及び有理点情報を復元するプログラム部分についてのみ説明する。なお、有理点部分群の特定及び有理点情報復元の演算は、認証サーバまたは、クライアント装置で実行される場合に限定されるものではなく、少なくともCPUなどの演算手段及び記憶手段を備えた装置であれば、どのような装置であってもよい。
【００５９】
図１に示すように、認証サーバまたはクライアント装置を構成する電子計算機10は、演算処理を実行するCPU11と有理点部分群特定プログラム、有理点情報復元プログラム、ペアリング演算プログラムなどの各種プログラム、及びこれらのプログラムで使用するデータなどを記憶したハードディスクなどの記憶装置12と、これらのプログラムを展開して実行可能とするとともに、これらプログラムの実行にともなって生成されたデータを一時的に記憶するRAMなどで構成されたメモリ装置13を備えている。図１中、14はバスである。
【００６０】
また、認証サーバを構成する電子計算機10は、インターネットなどの電気通信回線20に接続され、この電気通信回線20に接続されたクライアント装置30から送信されたディジタルグループ署名の署名データを受信可能としている。図１中、15は電子計算機10の入出力部である。
【００６１】
図２に、クライアント装置上の有理点情報圧縮装置100を示す。図２に示すように、有理点情報圧縮装置100は、有理点部分群特定部110と、認証データ生成部120と、有理点情報圧縮部130と、入出力部140とを有する。
まず、ディジタルグループ署名データ（認証データ）を生成するクライアント装置では、与えられたペアリング曲線から有理点部分群G1、G2を特定する（有理点部分群特定部110）。次に、署名データを生成し（認証データ生成部120）、署名データを構成する有理点P∈G1及びQ∈G2のペアを楕円加算して有理点Rに圧縮する（有理点情報圧縮部130）。全てのペアについて圧縮した後、署名データを入出力部140より、認証サーバに向け送信する。
【００６２】
図３に、認証サーバ上の有理点情報圧縮装置200を示す。図３に示すように、有理点情報圧縮装置200は、入出力部210と、有理点情報復元部220と、認証処理部230と、認証結果データ生成部240と、有理点情報圧縮部250と、入出力部260とを有する。
認証サーバを構成する電子計算機10では、クライアント装置30からディジタルグループ署名の署名データが送信されると、入出力部210を経由して署名データを受信し、受信した署名データをメモリ装置13に一旦記憶し、有理点情報復元プログラムを起動して元の有理点のペアの情報を復元した後（有理点情報復元部220）、ペアリング演算プログラムを起動して、ペアリング演算を実行している(認証処理部230)。
その後、認証結果のデータを生成し（認証結果データ生成部240）、有理点のペアの情報を圧縮し（有理点情報圧縮部250）、入出力部260を経由してクライアント装置に向け送信している。
【００６３】
次に、本実施形態の詳細について図を用いて説明する。
＜有理点部分群の特定＞
【００６４】
図４は図１で示した装置で所定のプログラムを実行させることにより実現される有理点部分群特定部110の機能構成を例示した図である。
図７は有理点部分群特定部の処理を行う有理点部分群特定プログラムのフローチャートである。
電子計算機10では、起動した有理点部分群特定プログラムによって、図７に示すフローチャートに基づいて効率的な自己準同型写像を可能とする有理点部分群を特定している。すなわち、入力された、有理点群が埋め込み次数１の一般の有理点を特定の有理点部分群内の有理点に変換している。この場合電子計算機10は有理点部分群特定手段として機能する。以下では、3次の場合について説明する。
【００６５】
ステップ  T1（有理点入力部111）では、外部から与えられ入力手段により記憶手段に記憶された一般の有理点P’を読み出している。
ステップ  T2（定数演算部112）では、あらかじめレジスタ119に記憶された有限体の標数ｐ及び合成数位数ｒとを用いて、式（３）で示したλ2＋λ＋１≡０ (mod r)となるλ及び、式（４ｂ）で示したε3≡1 (mod p)となるε(≠1)を演算し設定している。
ステップ  T3（自己準同型写像演算部113）では、式（４ｂ）のψ(P’)：(x,y)→(εx,y)として、P’のｘ座標値ｘをε倍し、ψ(P’)を求めている。
ステップ  T4（有理点演算部114）では、式（６）のP=ψ(P’)+(λ+1)P’を計算している。
ステップ  T5（判定部115）では、P=O  (無限遠点)  かどうかを判定している。
P=O  の場合は、2つの部分群を特定できないのでエラー・リターンしている（発生確率は、1/22000程度である。）。
ステップ  T6 (有理点演算部114)では、式（７）のQ=ψ(P’)+(-λ)P’を計算している。
ステップ  T7(判定部115)では、Q=O  （無限遠点）かどうかを判定している。
Q=O  の場合は2つの部分群を特定できないのでエラー・リターンしている（発生確率は、1/22000程度である。）。
ステップ T8では、P、Qを記憶手段に記憶している。Pの集合が有理点部分群G1となり、Qの集合が有理点部分群G2となる。
【００６６】
本実施形態では、3次の場合について説明したが、4次,及び6次の場合も、λ、ψ(P’)、εまたはζ、P、Qがそれぞれ
4次では、式(14)：λ2+1≡0 (mod r)、 
式(15b)：ψ(P’):(x,y)→(-x,ζy), (ζ４=1, ζ,ζ2(≠1)∈Fp)、
式(17）：P=ψ(P’) +λP’、
式(18)：Q=ψ(P’) +(-λ)P’
となり、
6次では、式(19)：λ2-λ+1≡0 (mod r)、 
式(20b)：ψ(P’):(x,y)→(εx,-y), (ε3=1, ε(≠1)∈Fp)、
式(23)：P=ψ(P’) +(λ-1)P’、 
式(24)：Q=ψ(P’) +(-λ)P’
となるだけであり、同様に有理点部分群を特定することができる（説明は省略する。）。
【００６７】
＜有理点情報の圧縮＞
有理点P∈G1, Q∈G2の圧縮はこれらの有理点を楕円加算して有理点Rとすることにより行う。これにより、有理点のデータ長は半分となる。
【００６８】
＜有理点情報の復元＞
図５は図１で示した装置で所定のプログラムを実行させることにより実現される有理点情報復元部220の機能構成を例示した図である。
図６は有理点情報復元部の処理を行う有理点復元プログラムのフローチャートである（4次の場合）。
電子計算機10では、起動した有理点復元プログラムによって、図６に示すフローチャートに基づいて有理点Rから有理点P, Qを求めている。この場合電子計算機10は第2演算手段として機能する。以下では、４次の場合について説明する。
【００６９】
まず、有理点Rを入力し、メモリ手段13に記憶する。（ステップ  S1、パラメータ入力部221）
次に、
T1=[λ4][ψ4+λ4]R
を計算する。（ステップ  S2、レジスタ229、定数演算部222、自己準同型写像演算部224）
次に、
P=-[2-1]T1
を計算する。(ステップS3、2-1演算部223、有理点演算部225)
次に、
Q=R-P
を計算する。(ステップS4、有理点演算部225)
【００７０】
2-1倍算は、具体的には、以下のアルゴリズムを実行している。
［表１］4次の場合の2-1倍算アルゴリズム
入力：λ4、T1∈G1
出力：[2-1]T1
1. T←[λ4/2]T1
2. T←ψ4(T)+T1
3. Return T
すなわち、ステップ１では、有理点T1の[λ4/2]倍算を実行し、Tに代入している。ステップ２では、ステップ１で求めたTの自己準同型写像ψ4を実行し、有理点T1を加算してTに代入している。ステップ３では戻り値をTとしてリターンしている。
【００７１】
4次の場合の有理点の復元は、具体的には、以下のアルゴリズムを実行している。
［表２］4次の場合有理点復元アルゴリズム
入力：λ4、R=P+Q, P∈G1, Q∈G2
出力：P, Q
1. T1←ψ4(R)
2. T1←[λ4]T1-R
3. P← -[2-1]T1
4. Q←R-P
5. Return P, Q
すなわち、ステップ1では、有理点Rの自己準同型写像ψ4を実行し、T1に代入している。ステップ２では、有理点T1の[λ4]倍算を実行し、次に-Rを楕円加算してT1に代入している。ステップ３では、［表１］のアルゴリズムを実行し、符号をマイナスにしてPを求めている。ステップ４では、Rと-Pを楕円加算してQを求めている。ステップ5では、P, Qを戻り値としてリターンしている。
【００７２】
次に3次の場合について説明する。
3次の場合の3-1倍算は、具体的には、以下のアルゴリズムを実行している。
［表３］３次の場合の3-1倍算アルゴリズム
入力：λ3、T1∈G1
出力：[3-1]T1
1. T←[2(λ3+1)/3]T1
2. T←ψ3(T)+T1
3. Return T
すなわち、ステップ１では、有理点T1の[2(λ3+1)/3]倍算を実行し、Tに代入している。ステップ２では、ステップ１で求めたTの自己準同型写像ψ3を実行し、有理点T1を加算してTに代入している。ステップ３では戻り値をTとしてリターンしている。
【００７３】
3次の場合の有理点の復元は、具体的には、以下のアルゴリズムを実行している。
［表４］3次の場合有理点復元アルゴリズム
入力：λ3、R=P+Q, P∈G1, Q∈G2
出力：P, Q
1. T1←ψ3(R)
2. T2←2T1+R
3. T2←[λ3]T2
4. T1←T2+T1-R
5. P← -[3-1]T1
6. Q←R-P
7. Return P, Q
すなわち、ステップ1では、有理点Rの自己準同型写像ψ3を行い、T1に代入している。ステップ２では、有理点T1の2倍算を実行し、次にRを楕円加算してT2に代入している。ステップ３では、有理点T2の[λ3]倍算を行いT2に代入している。ステップ4では、T2, T1,-Rを楕円加算してT1に代入している。ステップ5では、［表３］のアルゴリズムを実行し、符号をマイナスにしてPを求めている。ステップ６では、Rと-Pを楕円加算してQを求めている。ステップ7では、P, Qを戻り値としてリターンしている。
【００７４】
次に６次の場合について説明する。
6次の場合の3-1倍算は、具体的には、以下のアルゴリズムを実行している。
［表５］６次の場合の3-1倍算アルゴリズム
入力：λ6、T1∈G1
出力：[3-1]T1
1. T←[2(λ6-1)/3]T1
2. T←ψ6(T)+T1
3. Return T
すなわち、ステップ１では、有理点T1の[2(λ6-1)/3]倍算を実行し、Tに代入している。ステップ２では、ステップ１で求めたTの自己準同型写像ψ6を実行し、有理点T1を加算してTに代入している。ステップ３では戻り値をTとしてリターンしている。
【００７５】
6次の場合の有理点の復元は、具体的には、以下のアルゴリズムを実行している。
［表6］6次の場合の有理点復元アルゴリズム
入力：λ6、R=P+Q, P∈G1, Q∈G2
出力：P, Q
1. T1←ψ6(R)
2. T2←2T1-R
3. T2←[λ6]T2
4. T1←T2-T1-R
5. P← -[3-1]T1
6. Q←R-P
7. Return P, Q
すなわち、ステップ1では、有理点Rの自己準同型写像ψ6を実行し、T1に代入している。ステップ２では、有理点T1の2倍算を実行し、次に-Rを楕円加算してT2に代入している。ステップ３では、有理点T2の[λ6]倍算を行いT2に代入している。ステップ4では、T2, -T1, -Rを楕円加算してT1に代入している。ステップ5では、［表５］のアルゴリズムを実行し、符号をマイナスにしてPを求めている。ステップ６では、Rと-Pを楕円加算してQを求めている。ステップ7では、P, Qを戻り値としてリターンしている。
【符号の説明】
【００７６】
10  電子計算機
11  CPU
12  記憶装置
13  メモリ装置
14  バス
15  入出力部
20  電気通信回線
30  クライアント装置
100  有理点情報圧縮装置
110  有理点部分群特定部
111  有理点入力部
112  定数演算部
113  自己準同型写像演算部
114  有理点演算部
115  判定部
119  レジスタ
120  認証データ生成部
130  有理点情報圧縮部
140  入出力部
200  有理点情報圧縮装置
210  入出力部
220  有理点情報復元部
221  パラメータ入力部
222  定数演算部
223  2-1演算部
224  自己準同型写像演算部
225  有理点演算部
229  レジスタ
230  認証処理部
240  認証結果データ生成部
250  有理点情報圧縮部
260  入出力部
【図１】
2012046805.tif 000006
【図２】
2012046805.tif 000007
【図３】
2012046805.tif 000008
【図４】
2012046805.tif 000009
【図５】
2012046805.tif 000010
【図６】
2012046805.tif 000011
【図７】
2012046805.tif 000012
【国際調査報告】
2012046805.tif 000013
2012046805.tif 000014
2012046805.tif 000015
2012046805.tif 000016