(57)【特許請求の範囲】
【請求項１】
裁定装置と、署名装置と、検証装置とを含む検証可能暗号化署名システムであって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、MをZpの元、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとして、
上記裁定装置は、
Zp＊の元βを選び、裁定者公開鍵apk:=ζ:=gβおよび裁定者復号鍵ask:=βを出力する裁定者鍵生成部を含み、
上記署名装置は、
群Gの元v,v1,v2,w,u,hおよびZpの元a1,a2,b,αを選び、τ1:=vv1a1, τ2:=vv2a2を計算し、検証鍵VK:=(gb,ga1,ga2,gba1,gba2,τ1,τ2,τ1b,τ2b,w,u,h,e(g,g)αa1b)、署名鍵SK:=(VK,gα,gαa1,v,v1,v2)を出力する鍵生成部と、
Zpの元r1, r2, z1, z2, tagkを用いて、r:=r1+r2とし、σ1:=gαa1vr, σ2:=g-αv1rgz1, σ3:=(gb)-z1, σ4:=v2rgz2, σ5:=(gb)-z2, σ6:=(gb)r2, σ7:=gr1, σ8:=(uMwtagkh)r1を計算し、Zpの元ρ1,ρ2,ρ4を選び、K1:=σ1・ζρ1, K1':=gρ1, K1^:=(gb)ρ1, K2:=σ2・ζρ2, K2':=gρ2, K2^:=(gba1)ρ2, K3:=σ3, K4:=σ4・ζρ4, K4':=gρ4, K4^:=(gba2)ρ4, K5:=σ5, K6:=σ6, K7:=σ7, K8:=σ8を計算し、検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K1',K2',K4',K1^,K2^,K4^,tagk)を出力する署名生成部を含み、
上記検証装置は、
Zpの元s1,s2,t,tagcを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算し、tagc-tagk≠0を確認し、θ:=1/(tagc-tagk)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・e(V3,K3)・(e(V4,K4)/e(ζs2,K4^))・e(V5,K5)=e(V6,K6)・e(V7,K7)・(e(E1,K7)/e(E2,K8))θ・(e(g,g)αa1b)s2が成立することを確認したとき且つそのときに限り検証成功を表す検証結果を出力する検証部を含む
検証可能暗号化署名システム。
【請求項２】
請求項１に記載の検証可能暗号化署名システムであって、
上記裁定装置は、さらに、
Zpの元s1,s2,t,tagcを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算し、tagc-tagk≠0を確認し、θ:=1/(tagc-tagk)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・e(V3,K3)・(e(V4,K4)/e(ζs2,K4^))・e(V5,K5)=e(V6,K6)・e(V7,K7)・(e(E1,K7)/e(E2,K8))θ・(e(g,g)αa1b)s2が成立することを確認し、この確認ができた場合に、σ1:=K1・(K1')-β, σ2:=K2・(K2')-β, σ3:=K3, σ4:=K4・(K4')-β, σ5:=K5, σ6:=K6, σ7:=K7, およびσ8:=K8を計算し、Zpの元z1',z2',r'を選び、σ1':=σ1, σ2':=σ2・gz1', σ3':=σ3・(gb)-z1', σ4':=σ4・gz2', σ5':=σ5・(gb)-z2', σ6':=σ6・(gb)-r', σ7':=σ7・gr', およびσ8':=σ8・(uMwtagkh)r'を計算し、署名σ':=(σ1',σ2',σ3',σ4',σ5',σ6',σ7',σ8',tagk)を出力する復元部を含む
ことを特徴とする検証可能暗号化署名システム。
【請求項３】
裁定装置と、署名装置と、検証装置とを含む検証可能暗号化署名システムにおける検証可能暗号化署名方法であって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、MをZpの元、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとして、
上記裁定装置の裁定者鍵生成部が、Zp＊の元βを選び、裁定者公開鍵apk:=ζ:=gβおよび裁定者復号鍵ask:=βを出力する裁定者鍵生成ステップと、
上記署名装置の鍵生成部が、群Gの元v,v1,v2,w,u,hおよびZpの元a1,a2,b,αを選び、τ1:=vv1a1, τ2:=vv2a2を計算し、検証鍵VK:=(gb,ga1,ga2,gba1,gba2,τ1,τ2,τ1b, τ2b,w,u,h,e(g,g)αa1b)、署名鍵SK:=(VK,gα,gαa1,v,v1,v2)を出力する鍵生成ステップと、
上記署名装置の署名生成部が、Zpの元r1, r2, z1, z2, tagkを用いて、r:=r1+r2とし、σ1:=gαa1vr, σ2:=g-αv1rgz1, σ3:=(gb)-z1, σ4:=v2rgz2, σ5:=(gb)-z2, σ6:=(gb)r2, σ7:=gr1, σ8:=(uMwtagkh)r1を計算し、Zpの元ρ1,ρ2,ρ4を選び、K1:=σ1・ζρ1, K1':=gρ1, K1^:=(gb)ρ1, K2:=σ2・ζρ2, K2':=gρ2, K2^:=(gba1)ρ2, K3:=σ3, K4:=σ4・ζρ4, K4':=gρ4, K4^:=(gba2)ρ4, K5:=σ5, K6:=σ6, K7:=σ7, K8:=σ8を計算し、検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K1',K2',K4',K1^,K2^,K4^,tagk)を出力する署名生成ステップと、
上記検証装置の検証部が、Zpの元s1,s2,t,tagcを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算し、tagc-tagk≠0を確認し、θ:=1/(tagc-tagk)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・e(V3,K3)・(e(V4,K4)/e(ζs2,K4^))・e(V5,K5)=e(V6,K6)・e(V7,K7)・(e(E1,K7)/e(E2,K8))θ・(e(g,g)αa1b)s2が成立することを確認したとき且つそのときに限り検証成功を表す検証結果を出力する検証ステップを有する
検証可能暗号化署名方法。
【請求項４】
請求項３に記載の検証可能暗号化署名方法であって、さらに、
上記裁定装置の復元部が、Zpの元s1,s2,t,tagcを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算し、tagc-tagk≠0を確認し、θ:=1/(tagc-tagk)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・e(V3,K3)・(e(V4,K4)/e(ζs2,K4^))・e(V5,K5)=e(V6,K6)・e(V7,K7)・(e(E1,K7)/e(E2,K8))θ・(e(g,g)αa1b)s2が成立することを確認し、この確認ができた場合に、σ1:=K1・(K1')-β, σ2:=K2・(K2')-β, σ3:=K3, σ4:=K4・(K4')-β, σ5:=K5, σ6:=K6, σ7:=K7, およびσ8:=K8を計算し、Zpの元z1',z2',r'を選び、σ1':=σ1, σ2':=σ2・gz1', σ3':=σ3・(gb)-z1', σ4':=σ4・gz2', σ5':=σ5・(gb)-z2', σ6':=σ6・(gb)-r', σ7':=σ7・gr', およびσ8':=σ8・(uMwtagkh)r'を計算し、署名σ':=(σ1',σ2',σ3',σ4',σ5',σ6',σ7',σ8',tagk)を出力する復元ステップを含む
ことを特徴とする検証可能暗号化署名方法。
【請求項５】
請求項１または請求項２に記載の検証可能暗号化署名システムにおいて用いられる上記裁定装置。
【請求項６】
請求項１または請求項２に記載の検証可能暗号化署名システムにおいて用いられる上記署名装置。
【請求項７】
請求項１または請求項２に記載の検証可能暗号化署名システムにおいて用いられる上記検証装置。
【請求項８】
請求項５に記載の裁定装置、請求項６に記載の署名装置、請求項７に記載の検証装置のいずれかとしてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、電気通信システムで利用される、暗号化された状態で検証可能なディジタル署名技術（検証可能暗号化署名技術）に関する。
【背景技術】
【０００２】
これまでにいくつかの安全な検証可能暗号化署名技術が提案されてきた。
【０００３】
非特許文献１に開示された方式は検証鍵のサイズが非常に小さい方式であるが、その安全性はランダムオラクルモデルという非現実的なモデルでしか証明できないため、安全性に信頼がおけない。
【０００４】
非特許文献２に開示された方式は標準的な暗号学仮定に基づき、かつ標準モデルという現実的なモデルで安全性が証明されているが、検証鍵のサイズがセキュリティパラメータのサイズに比例して大きくなるという欠点がある。
【０００５】
非特許文献３に開示された方式は標準モデルで安全性が証明され、検証鍵のサイズが小さい方式であるが、安全性の根拠と成る暗号学仮定が非標準的なものであるため、安全性に信頼がおけない。
【０００６】
なお、標準モデルやランダムオラクルモデル、暗号の安全性などについては、例えば非特許文献４が参考になる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In EUROCRYPT, volume 2656 of Lecture Notes in Computer Science, pages 416-432. Springer, 2003.
【非特許文献２】S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters. Sequential Aggregate Signatures and Multisignatures Without Random Oracles. In EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 465-485. Springer, 2006.
【非特許文献３】M. Ruckert and D. Schroder. Security of Verifiably Encrypted Signatures and a Construction without Random Oracles. In Pairing, volume 5671 of Lecture Notes in Computer Science, pages 17-34. Springer, 2009.
【非特許文献４】森山大輔、西巻陵、岡本龍明共著、「公開鍵暗号の数理−シリーズ応用数理第２巻−」、初版、共立出版株式会社、２０１１年３月、pp.23-31, pp.94-95. ISBN:978-4-320-01951-5.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
既存方式では、標準モデルで安全なものは、標準的な暗号学的仮定しか用いないが検証鍵のサイズがセキュリティパラメータのサイズに依存して大きくなる方式か、検証鍵のサイズが小さいが非標準的な（より信頼のおけない）暗号学仮定を必要とする方式しかなかった。
【０００９】
そこで本発明は、標準的な暗号学仮定に基づき且つ検証鍵のサイズがセキュリティパラメータのサイズに依存しない検証可能暗号化署名技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の検証可能暗号化署名技術は、次のとおりである。本発明によると、検証可能暗号化署名システムは、裁定装置と、署名装置と、検証装置とを含む。pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、MをZpの元、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとする。そして、裁定装置の裁定者鍵生成部が、Zp＊の元βを選び、裁定者公開鍵apk:=ζ:=gβおよび裁定者復号鍵ask:=βを出力する[裁定者鍵生成処理]。署名装置の鍵生成部は、群Gの元v,v1,v2,w,u,hおよびZpの元a1,a2,b,αを選び、τ1:=vv1a1, τ2:=vv2a2を計算し、検証鍵VK:=(gb,ga1,ga2,gba1,gba2,τ1,τ2,τ1b,τ2b,w,u,h,e(g,g)αa1b)、署名鍵SK:=(VK,gα,gαa1,v,v1,v2)を出力する[鍵生成処理]。また、署名装置の署名生成部は、Zpの元r1, r2, z1, z2, tagkを用いて、r:=r1+r2とし、σ1:=gαa1vr, σ2:=g-αv1rgz1, σ3:=(gb)-z1, σ4:=v2rgz2, σ5:=(gb)-z2, σ6:=(gb)r2, σ7:=gr1, σ8:=(uMwtagkh)r1を計算し、Zpの元ρ1,ρ2,ρ4を選び、K1:=σ1・ζρ1, K1':=gρ1, K1^:=(gb)ρ1, K2:=σ2・ζρ2, K2':=gρ2, K2^:=(gba1)ρ2, K3:=σ3, K4:=σ4・ζρ4, K4':=gρ4, K4^:=(gba2)ρ4, K5:=σ5, K6:=σ6, K7:=σ7, K8:=σ8を計算し、検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K1',K2',K4',K1^,K2^,K4^,tagk)を出力する[署名生成処理]。そして、検証装置の検証部は、Zpの元s1,s2,t,tagcを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算し、tagc-tagk≠0を確認し、θ:=1/(tagc-tagk)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・e(V3,K3)・(e(V4,K4)/e(ζs2,K4^))・e(V5,K5)=e(V6,K6)・e(V7,K7)・(e(E1,K7)/e(E2,K8))θ・(e(g,g)αa1b)s2が成立することを確認したとき且つそのときに限り検証成功を表す検証結果を出力する[検証処理]。
【００１１】
さらに、裁定装置の復元部が、Zpの元s1,s2,t,tagcを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算し、tagc-tagk≠0を確認し、θ:=1/(tagc-tagk)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・e(V3,K3)・(e(V4,K4)/e(ζs2,K4^))・e(V5,K5)=e(V6,K6)・e(V7,K7)・(e(E1,K7)/e(E2,K8))θ・(e(g,g)αa1b)s2が成立することを確認し、この確認ができた場合に、σ1:=K1・(K1')-β, σ2:=K2・(K2')-β, σ3:=K3, σ4:=K4・(K4')-β, σ5:=K5, σ6:=K6, σ7:=K7, およびσ8:=K8を計算し、Zpの元z1',z2',r'を選び、σ1':=σ1, σ2':=σ2・gz1', σ3':=σ3・(gb)-z1', σ4':=σ4・gz2', σ5':=σ5・(gb)-z2', σ6':=σ6・(gb)-r', σ7':=σ7・gr', およびσ8':=σ8・(uMwtagkh)r'を計算し、署名σ':=(σ1',σ2',σ3',σ4',σ5',σ6',σ7',σ8',tagk)を出力する[復元処理]も含みえる。
【発明の効果】
【００１２】
本発明に拠れば、詳細は後述の実施形態に譲るが、署名鍵の要素数を若干増やすもののその代わりに検証鍵の要素数を大きく減らす、署名鍵が複数の群要素からなる署名技術を元に、署名を暗号化する際に、署名鍵が関係する署名の要素だけではなく、署名鍵が直接関係しない署名の乱数要素も裁定者公開鍵で暗号化することによって、検証鍵のサイズがセキュリティパラメータのサイズに依存しないものとなっており、また、安全性が標準的な暗号学的仮定のみに基づている。
【図面の簡単な説明】
【００１３】
【図１】実施形態の検証可能暗号化署名システムを示す図。
【図２】実施形態における検証可能暗号化署名の処理手順を示す図。
【図３】実施形態に関わる検証可能暗号化署名システムの構成要素であるシステムパラメータ生成装置、裁定装置、署名装置、検証装置の機能構成を示す図。
【発明を実施するための形態】
【００１４】
本発明の実施形態を説明する前に、いくつかの基本的事項について説明する。
まず、記法について説明する。
或る有限集合Sについて、r ←U S は、集合Sから要素rを一様ランダムに選択することを表す。
或る確率的多項式時間アルゴリズムAについて、a ←R A(x) は、アルゴリズムAはxを入力とし、乱数を用いて動作し、aを出力することを表す。
或る値a,bについて、a:=bは、aにbを代入する、または、aをbで定義することを表す。いずれであるかは文意から明らかであるから特に断らない。
【００１５】
［ペアリング］
双線型性を満たすペアリングと呼ばれる演算は有限体上で定義された楕円曲線上の有理点と無限遠点を元とする群構造として定義される。なお、楕円曲線上の群は通常、加法群であるが、慣習に従い乗法群として記述することにする。詳しくは例えば参考文献１を参照されたい。
（参考文献１）D. Boneh and M. K. Franklin. Identity-Based Encryption from theWeil Pairing. In CRYPTO’01, volume 2139 of Lecture Notes in Computer Science, pages 213-229. Springer, 2001.
【００１６】
GとGTを位数pの群とする。Zを整数全体を表す集合とする。ここでpは十分に大きい素数である。この二つの群G，GTの間の双線型写像e:G×G→GTは以下の性質を満たす。
双線型性：
任意のg,h∈Gおよび任意のa,b∈Zに対してe(ga,hb)=e(g,h)abが成立する。
非退化性：
e(g,g)≠1を満たすgが存在する。つまり、もしgがGの生成元ならばe(g,g)はGTの生成元である。
計算可能性：
任意のg,h∈Gに対して，e(g,h)は効率的に（つまり多項式時間で）計算可能である。
【００１７】
［暗号学的仮定］
素数位数pの巡回群Gを考える。gを群Gの生成元とする。BMSetupを、セキュリティパラメータλを入力として(p,G,GT,e,g)を生成する、双線型写像についての標準的な群生成アルゴリズムとする。
【００１８】
［判定線形問題］
Zpをpを法とするZの剰余類環として、ArβDLIN(1λ)を、Γ:=(p,G,GT,e,g) ←R BMsetup(1λ)を生成し、f,h ←U G, x,y ←U Zpを選び、Q0:=gx+y、Q1 ←U Gとして(Γ,f,h,g,fx,hy,Qβ)を出力するアルゴリズムとする。β∈｛0,1｝である。判定線形問題とは、(Γ,f,h,g,fx,hy,Qβ) ←R ArβDLIN(1λ)が与えられたときにβ∈｛0,1｝を予想する問題である。この優位性は式（１）で定義される。
AdvADLIN(λ)=|Pr[A(I)→1|I←Ar0DLIN(1λ)]-Pr[A(I)→1|I←Ar1DLIN(1λ)]|    （１）
【００１９】
［判定線形仮定］
判定線形仮定が成立しているとは、判定線形問題が困難である、つまり、どのような攻撃者Aに対しても式（１）で表されるAdvADLIN(λ)が無視できることをいう。
【００２０】
次に、本発明が基づくWaters署名について概説する（参考文献２）。λはセキュリティパラメータを表す。BMSetupは1λを入力とし(p,G,GT,e,g)を出力する標準的なアルゴリズムである。pはλビットの素数、G,GTはそれぞれ素数位数pの巡回乗法群、gは群Gの生成元、eは双線形写像を表す。
（参考文献２）B. Waters. Dual System Encryption: Realizing Fully Secure IBE and HIBE under Simple Assumptions. In CRYPTO’09, volume 5677 of Lecture Notes in Computer Science, pages 619-636. Springer, 2009. full version available from http://eprint.iacr.org/2009/385.
【００２１】
W.Gen(1λ,Γ)：
セキュリティパラメータλを入力とし、Γ:=(p,G,GT,e,g) ←R BMsetup(1λ)を生成し、生成元v,v1,v2,w,u,h ←U Gおよびa1,a2,b,α ←U Zpを選び、τ1:=vv1a1, τ2:=vv2a2を計算し、検証鍵VK:=(Γ,gb,ga1,ga2,gba1,gba2,τ1,τ2,τ1b,τ2b,w,u,h,e(g,g)αa1b)、署名鍵SK:=(VK,gα,gαa1,v,v1,v2)を出力する。
【００２２】
W.Sign(SK,M)：
平文M∈Zpと署名鍵SKを入力とし、r1, r2, z1, z2, tagk ←U Zpを選び、r:=r1+r2とし、σ1:=gαa1vr, σ2:=g-αv1rgz1, σ3:=(gb)-z1, σ4:=v2rgz2, σ5:=(gb)-z2, σ6:=(gb)r2, σ7:=gr1, σ8:=(uMwtagkh)r1を計算して、署名sig:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を出力する。
【００２３】
W.Vrfy(VK,sig,M)：
検証鍵VK,平文M，署名sigを入力とし、s1,s2,t,tagc ←U Zpを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算する。以下を満たすとき且つそのときに限り検証成功を表す情報（例えば1という値）を出力する。ただし、θ:=1/(tagc-tagk)とする。
tagc-tagk≠0およびe(V1,σ1)・e(V2,σ2)・e(V3,σ3)・e(V4,σ4)・e(V5,σ5)=e(V6,σ6)・e(V7,σ7)・(e(E1,σ7)／e(E2,σ8))θ・(e(g,g)αa1b)s2
【００２４】
《実施形態》
［検証可能暗号化署名システム］
実施形態の検証可能暗号化署名システム１は、図１に示すように、システムパラメータ生成装置５００、裁定装置１００、署名装置２００、検証装置３００を含んで構成される。これらの各装置は、例えばインターネットなどの通信網５を経由して、相互に通信可能とされている。なお、後述のシステムパラメータが予め決まっていれば十分なので、システムパラメータ生成装置５００は検証可能暗号化署名システム１の必須の構成要素ではなく、図示しない装置によって生成された当該システムパラメータが検証可能暗号化署名システム１に提供されていれば足りる。形態によっては、裁定装置１００がシステムパラメータ生成装置５００を兼ねることも許容される。
【００２５】
本発明の検証可能暗号化署名システムは、ユーザなどの数に応じて一つまたは複数の署名装置２００と一つまたは複数の検証装置３００を含みえるが、本発明の理解を容易にするため、後述の実施形態では、検証可能暗号化署名システム１は、１個の裁定装置１００と１個の署名装置２００と１個の検証装置３００を含むとする。
【００２６】
検証可能暗号化署名システム１における処理を、図２を参照しながら叙述する。各装置の機能構成については、図３を参照されたい。
【００２７】
システムパラメータ生成装置５００のシステムパラメータ生成部５０１は、既述の暗号学的仮定の下、セキュリティパラメータλを入力とし、システム全体に共通なシステムパラメータ、つまり双線形写像のパラメータΓ:=(p,G,GT,e,g) ←R BMsetup(1λ)を出力する（ステップＳ１）。
【００２８】
システムパラメータ生成装置５００の送信部５０８は、パラメータΓを各装置１００，２００，３００に送信する。
【００２９】
裁定装置１００の受信部１０９は、パラメータΓを受信する。パラメータΓは裁定装置１００の図示しない記憶部に記憶される。裁定装置１００の裁定者鍵生成部１０１は、裁定者公開鍵および裁定者復号鍵を以下のように生成する。システムパラメータ生成装置５００から受信したΓ:=(p,G,GT,e,g)を入力とし、β ←U Zp＊を選び、裁定者公開鍵apk:=ζ:=gβおよび裁定者復号鍵ask:=βを出力する（ステップＳ２）。Zp＊=Zp-{0}である。
【００３０】
裁定装置１００の送信部１０８は、裁定者公開鍵apkを各装置２００，３００に送信する。裁定者公開鍵apkおよび裁定者復号鍵askも裁定装置１００の図示しない記憶部に記憶される。
【００３１】
署名装置２００の受信部２０９は、パラメータΓと裁定者公開鍵apkを受信する。パラメータΓと裁定者公開鍵apkは署名装置２００の図示しない記憶部に記憶される。
【００３２】
署名装置２００の鍵生成部２０１は、システムパラメータ生成装置５００から受信したΓ:=(p,G,GT,e,g)を入力とし、群の元v,v1,v2,w,u,h ←U Gおよびa1,a2,b,α ←U Zpを選び、τ1:=vv1a1, τ2:=vv2a2を計算し、検証鍵VK:=(gb,ga1,ga2,gba1,gba2,τ1,τ2,τ1b,τ2b,w,u,h,e(g,g)αa1b)、署名鍵SK:=(VK,gα,gαa1,v,v1,v2)を出力する（ステップＳ３）。なお、これは上述のWaters署名の鍵生成と同一である。検証鍵VKおよび署名鍵SKも署名装置２００の図示しない記憶部に記憶される。
【００３３】
署名装置２００の署名生成部２０２は、署名鍵SK、平文Mおよび裁定装置１００の裁定者公開鍵apkを入力とし、例えば図示しない乱数生成装置あるいは署名装置２００に含まれる乱数生成部によって生成された乱数を用いて、検証可能暗号化署名を生成する。具体的には下記のとおりである。署名生成部２０２は、乱数r1, r2, z1, z2, tagk ←U Zpを選び、r:=r1+r2とし、σ1:=gαa1vr, σ2:=g-αv1rgz1, σ3:=(gb)-z1, σ4:=v2rgz2, σ5:=(gb)-z2, σ6:=(gb)r2, σ7:=gr1, σ8:=(uMwtagkh)r1を計算し、乱数ρ1,ρ2,ρ4 ←U Zpを選び、K1:=σ1・ζρ1, K1':=gρ1, K1^:=(gb)ρ1, K2:=σ2・ζρ2, K2':=gρ2, K2^:=(gba1)ρ2, K3:=σ3, K4:=σ4・ζρ4, K4':=gρ4, K4^:=(gba2)ρ4, K5:=σ5, K6:=σ6, K7:=σ7, K8:=σ8を計算し、ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K1',K2',K4',K1^,K2^,K4^,tagk)を出力する（ステップＳ４）。送信部２０８は、検証鍵VKと平文Mと検証可能暗号化署名ωを検証装置３００に送信する。
【００３４】
検証装置３００は、検証可能暗号化署名ωが署名装置２００が正しく生成した署名の裁定者公開鍵apkによる正しい暗号文であることを検証する検証部３０１と、送信部３０８と、受信部３０９を備えている。検証装置３００の受信部２０９は、パラメータΓと検証鍵VKと平文Mと検証可能暗号化署名ωを受信する。パラメータΓと検証鍵VKと平文Mと検証可能暗号化署名ωは検証装置３００の図示しない記憶部に記憶される。
【００３５】
検証処理は次のとおりである。検証装置３００の検証部３０１は、検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K1',K2',K4',K1^,K2^,K4^,tagk)、平文M、検証鍵VKおよび裁定者公開鍵apkを入力とし、乱数s1,s2,t,tagc ←U Zpを選び、s:=s1+s2とし、V1:=(gb)s, V2:=(gba1)s1, V3:=(ga1)s1, V4:=(gba2)s2, V5:=(ga2)s2, V6:=τ1s1τ2s2, V7:=(τ1b)s1(τ2b)s2w-t, E1:=(uMwtagch)t, E2:=gtを計算し、tagc-tagk≠0を確認し、θ:=1/(tagc-tagk)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・e(V3,K3)・(e(V4,K4)/e(ζs2,K4^))・e(V5,K5)=e(V6,K6)・e(V7,K7)・(e(E1,K7)/e(E2,K8))θ・(e(g,g)αa1b)s2が成立することを確認したとき且つそのときに限り検証結果resultに検証成功を表す情報（例えば1という値）を代入して検証結果resultを出力する（ステップＳ５）。検証部３０１は、どれか一つでも成立しないときは、検証結果resultに検証失敗を表す情報（例えば0という値）を代入して検証結果resultを出力する。
【００３６】
検証可能暗号化署名技術によると、裁定装置１００は、署名装置２００が裁定者公開鍵apkを用いて暗号化する前の署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を復元することができる。以下、この処理について説明する。
【００３７】
検証装置３００は、署名装置２００が裁定者公開鍵apkを用いて暗号化する前の署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を必要とする場合、送信部３０８によって、署名装置２００からの検証可能暗号化署名ωと検証鍵VKと平文Mを裁定装置１００に送信する。
【００３８】
裁定装置１００は、さらに、検証可能暗号化署名ωの暗号化を解除して通常の署名を復元する復元部１０２を備えている。検証装置３００から受信した検証可能暗号化署名ωと検証鍵VKと平文Mは裁定装置１００の図示しない記憶部に記憶される。裁定装置１００の復元部１０２が検証可能暗号化署名ωの暗号化を解除する処理は次のとおりである。復元部１０２は、裁定者公開鍵apk、裁定者復号鍵ask、検証鍵VK、検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K1',K2',K4',K1^,K2^,K4^,tagk)、平文Mを入力とし、まず検証装置３００による検証処理と同じ処理を行って検証可能暗号化署名ωが正しい暗号化署名であることを検証し（上記ステップＳ５の処理を参照のこと）、その検証が正しい場合に、σ1:=K1・(K1')-β, σ2:=K2・(K2')-β, σ3:=K3, σ4:=K4・(K4')-β, σ5:=K5, σ6:=K6, σ7:=K7, およびσ8:=K8を計算し、乱数z1',z2',r' ←U Zpを選び、σ1':=σ1, σ2':=σ2・gz1', σ3':=σ3・(gb)-z1', σ4':=σ4・gz2', σ5':=σ5・(gb)-z2', σ6':=σ6・(gb)-r', σ7':=σ7・gr', およびσ8':=σ8・(uMwtagkh)r'を計算し、σ':=(σ1',σ2',σ3',σ4',σ5',σ6',σ7',σ8',tagk)として、σ'を署名として出力する（ステップＳ６）。なお、署名装置２００による処理が正当である場合σ'=σである。復元部１０２は、検証に失敗した場合はσ'を求めない（なお、裁定装置１００が検証装置３００に対して検証に失敗したことを表す情報を送信するようにしてもよい）。送信部１０８は、平文Mと復元された署名σ'を検証装置３００に送信する。
【００３９】
表１に本発明と従来技術との比較を示す。なおCDHは計算Diffie-Hellman (computational Diffie-Hellman)仮定を、ROMはランダムオラクルモデルを意味する。接頭辞q-が付されたq-strong DH extraction 仮定は暗号の分野でq仮定と呼ばれる仮定に分類され、標準的な暗号学的仮定であるCDH仮定、DDH（判定Diffie-Hellman）仮定、DLIN（判定線形）仮定に比べて安全性の根拠に信頼がおけない。表１から分かるように、まず、非特許文献１に開示される方式または非特許文献３に開示される方式によると、検証鍵のサイズや検証可能暗号化署名のサイズが本発明よりも小さいと評価できるが、これは、暗号学的安全性への信頼が弱い仮定やモデルを前提としているからであり、非特許文献１に開示される方式と非特許文献３に開示される方式は本発明と本質的に相違する。非特許文献２に開示される方式によると、暗号学的に安全であると考えられる仮定やモデルを前提としている点では本発明と相違するものではないが、本発明と異なり、検証鍵のサイズがセキュリティパラメータのサイズに依存する。セキュリティパラメータのサイズλは、一般的に１２よりも十分に大きく設定されるから、本発明は、検証鍵のサイズがセキュリティパラメータのサイズに依存しないというにとどまらず、検証鍵のサイズが十分に小さい検証可能暗号化署名方式であると評価できる。
【表１】
0005683512.tif 000002
【００４０】
＜補記＞
検証可能暗号化署名システムに含まれうるハードウェアエンティティ（システムパラメータ生成装置、裁定装置、署名装置、検証装置）は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００４１】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するＲＡＭやレジスタなどの記憶装置を単に「記憶部」とした。
【００４２】
ハードウェアエンティティでは、外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（例えば、システムパラメータ生成部、裁定者鍵生成部、鍵生成部、署名生成部、検証部、復元部など）を実現する。
【００４３】
各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成24年1月13日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈http://www.math.tu-berlin.de/~kant/kash.html〉［平成24年1月13日検索］を参照のこと。）。
また、この点に関する文献として、参考文献Ａを挙げることができる。
（参考文献Ａ）H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【００４４】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００４５】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００４６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００４７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005683512.tif 000003
【図２】
0005683512.tif 000004
【図３】
0005683512.tif 000005