(57)【特許請求の範囲】
【請求項１】
送信装置と受信装置と署名鍵難読化装置と暗号化署名生成装置を含む暗号化署名システムであって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとして、
上記送信装置は、
群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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成部を含み、
上記署名鍵難読化装置は、
或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すこととして、
cα:=(cα,1,cα,2,cα,3):=Enc(pke,g-α), 
cαa1:=(cαa1,1,cαa1,2,cαa1,3):=Enc(pke,gαa1), 
cv:=(cv,1,cv,2,cv,3):=Enc(pke,v), 
cv1:=(cv1,1,cv1,2,cv1,3):=Enc(pke,v1), および 
cv2:=(cv2,1,cv2,2,cv2,3):=Enc(pke,v2)を計算し、
難読化された暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を生成する暗号化署名鍵生成部を含み、
上記暗号化署名生成装置は、
(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (ただし、η',ψ'はZpの任意の元)と表すこととして、Zpの元r1, r2, z1, z2, tagkを選び、r:=r1+r2として、
１．(cσ1,1,cσ1,2,cσ1,3):=(cαa1,1・cv,1r,cαa1,2・cv,2r,cαa1,3・cv,3r), Cσ1:=(c1,1',c1,2',c1,3'):=ReRand(pke,(cσ1,1,cσ1,2,cσ1,3))
２．(cσ2,1,cσ2,2,cσ2,3):=(cα,1・cv1,1r,cα,2・cv1,2r, cα,3・cv1,3r・gz1), Cσ2:=(c2,1',c2,2',c2,3'):=ReRand(pke,(cσ2,1,cσ2,2,cσ2,3))
３．σ3:=(gb)-z1, Cσ3:=Enc(pke,σ3)
４．(cσ4,1,cσ4,2,cσ4,3):=(cv2,1r,cv2,2r,cv2,3r・gz2), Cσ4:=(c4,1',c4,2',c4,3'):=ReRand(pke,(cσ4,1,cσ4,2,cσ4,3))
５．σ5:=(gb)-z2, Cσ5:=Enc(pke,σ5)
６．σ6:=(gb)r2, Cσ6:=Enc(pke,σ6)
７．σ7:=gr1, Cσ7:=Enc(pke,σ7)
８．σ8:=(uMwtagkh)r1, Cσ8:=Enc(pke,σ8)
９．Cσ9:=Enc(pke,tagk)
を計算して、暗号化署名ctσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)を出力する暗号化署名生成部を含み、
上記受信装置は、さらに、
暗号化署名Cσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)についてCi=(ci,1,ci,2,ci,3) （ただし、i=1，…，9）と分割し、各i（i=1，…，9）について復号鍵dkを用いてσi:=ci,3/(ci,1)(1/xe)(ci,2)(1/ye)を計算し、復号された署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を出力する復号部を含む
難読化された署名鍵を用いた暗号化署名システム。
【請求項２】
調停装置と送信装置と受信装置と検証可能暗号化署名鍵難読化装置と暗号化検証可能暗号化署名生成装置を含む暗号化署名システムであって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成部を含み、
上記検証可能暗号化署名鍵難読化装置は、
或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すことにして、Zpの元ρα,ραa1,ρv,ρv1,ρv2を選び、
(cα,1',cα,2',cα,3'):=Enc(pke,g-α), 
cα:=(cα,1',cα,2',cα,3'・ζρα,gρα,gba1ρα), 
(cαa1,1',cαa1,2',cαa1,3'):=Enc(pke,gαa1), 
cαa1:=(cαa1,1',cαa1,2',cαa1,3'・ζραa1,gραa1,gbραa1), 
(cv,1',cv,2',cv,3'):=Enc(pke,v), 
cv:=(cv,1',cv,2',cv,3'・ζρv,gρv,gbρv), 
(cv1,1',cv1,2',cv1,3'):=Enc(pke,v1), 
cv1:=(cv1,1',cv1,2',cv1,3'・ζρv1,gρv1,gba1ρv1), 
(cv2,1',cv2,2',cv2,3'):=Enc(pke,v2)， 
cv2:=(cv2,1',cv2,2',cv2,3'・ζρv2,gρv2,gba2ρv2)
を計算し、難読化された暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を出力する暗号化署名鍵生成部を含み、
上記暗号化検証可能暗号化署名生成装置は、
(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (ただし、η',ψ'はZpの任意の元)を表すこととして、Zpの元r1, r2, z1, z2, tagkを選び、r:=r1+r2とし、
１．c1,1:=cαa1,1・cv,1r, c1,2:=cαa1,2・cv,2r, K1:=cαa1,3・cv,3r・ζρ1, K1':=cαa1,4・cv,4r・gρ1, K1^:=cαa1,5・cv,5r・(gb)ρ1, C1:=(c1,1',c1,2',c1,3'):=ReRand(pke,(c1,1,c1,2,K1)), C1':=Enc(pke,K1'), C1^:=Enc(pke,K1^).
２．c2,1:=cα,1・cv1,1r, c2,2:=cα,2・cv1,2r, K2:=cα,3・cv1,3r・gz1・ζρ2, K2':=cα,4・cv1,4r・gρ2, K2^:=cα,5・cv1,5r・(gba1)ρ2, C2:=(c2,1',c2,2',c2,3'):=ReRand(pke,(c2,1,c2,2,K2)), C2':=Enc(pke,K2'), C2^:=Enc(pke,K2^).
３．K3:=(gb)-z1・ζρ3,K3':=gρ3,K3^:=(ga1)ρ3, C3:=Enc(pke,σ3), C3':=Enc(pke,K3'), C3^:=Enc(pke,K3')
４．c4,1:=cv2,2r,c4,2:=cv2,3r,K4:=cv2,3r・gz2・ζρ4, K4':=cv2,4r・gρ4, K4^:=cv2,5r・(gba2)ρ4, C4:=(c4,1',c4,2',c4,3'):=ReRand (pke,(c4,1,c4,2,K4)), C4':=Enc(pke,K4'), C4^:=Enc(pke,K4^).
５．K5:=(gb)-z2, C5:=Enc(pke,K5)
６．K6:=(gb)r2, C6:=Enc(pke,K6)
７．K7:=gr1, C7:=Enc(pke,K7)
８．K8:=(uMwtagkh)r1,C8:=Enc(pke,K8) 
９．C9:=Enc(pke,tagk) 
を計算して、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)を出力する暗号化検証可能暗号化署名生成部を含み、
上記受信装置は、さらに、
暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)についてCi=(ci,1',ci,2',ci,3') （ただし、i=1，…，9）と分割し、各i（i=1，…，9）について復号鍵dkを用いてKi:=ci,3'/((ci,1')1/xe(ci,2')1/ye)を計算し、Cj',Cj^についてdk:=(xe,ye)を用いて復号し、復号した検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K1',K2',K3',K4',K1^,K2^,K3^,K4^)を出力する復号部を含む
難読化された署名鍵を用いた暗号化署名システム。
【請求項３】
請求項２に記載の暗号化署名システムであって、
上記受信装置は、さらに、
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-K9≠0を確認し、θ:=1/(tagc-K9)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K3',ga1)=e(g,K3^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・(e(V3,K3)/e(ζs1,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-K9≠0を確認し、θ:=1/(tagc-K9)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K3',ga1)=e(g,K3^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・(e(V3,K3)/e(ζs1,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・(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'，およびtagk:=K9を計算し、署名σ':=(σ1',σ2',σ3',σ4',σ5',σ6',σ7',σ8',tagk)を出力する復元部を含む
ことを特徴とする暗号化署名システム。
【請求項５】
送信装置と受信装置と署名鍵難読化装置を含む署名鍵難読化システムであって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとして、
上記送信装置は、
群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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成部を含み、
上記署名鍵難読化装置は、
或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すこととして、
cα:=(cα,1,cα,2,cα,3):=Enc(pke,g-α),
cαa1:=(cαa1,1,cαa1,2,cαa1,3):=Enc(pke,gαa1),
cv:=(cv,1,cv,2,cv,3):=Enc(pke,v),
cv1:=(cv1,1,cv1,2,cv1,3):=Enc(pke,v1), および
cv2:=(cv2,1,cv2,2,cv2,3):=Enc(pke,v2)を計算し、
難読化された暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を生成する暗号化署名鍵生成部を含む
署名鍵難読化システム。
【請求項６】
調停装置と送信装置と受信装置と検証可能暗号化署名鍵難読化装置を含む署名鍵難読化システムであって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成部を含み、
上記検証可能暗号化署名鍵難読化装置は、
或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すことにして、Zpの元ρα,ραa1,ρv,ρv1,ρv2を選び、
(cα,1',cα,2',cα,3'):=Enc(pke,g-α),
cα:=(cα,1',cα,2',cα,3'・ζρα,gρα,gba1ρα),
(cαa1,1',cαa1,2',cαa1,3'):=Enc(pke,gαa1),
cαa1:=(cαa1,1',cαa1,2',cαa1,3'・ζραa1,gραa1,gbραa1),
(cv,1',cv,2',cv,3'):=Enc(pke,v),
cv:=(cv,1',cv,2',cv,3'・ζρv,gρv,gbρv),
(cv1,1',cv1,2',cv1,3'):=Enc(pke,v1),
cv1:=(cv1,1',cv1,2',cv1,3'・ζρv1,gρv1,gba1ρv1),
(cv2,1',cv2,2',cv2,3'):=Enc(pke,v2)，
cv2:=(cv2,1',cv2,2',cv2,3'・ζρv2,gρv2,gba2ρv2)
を計算し、難読化された暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を出力する暗号化署名鍵生成部を含む
署名鍵難読化システム。
【請求項７】
送信装置と受信装置と署名鍵難読化装置と暗号化署名生成装置を含む暗号化署名システムにおける暗号化署名方法であって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとして、
上記送信装置の鍵生成部が、群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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成ステップと、
上記署名鍵難読化装置の暗号化署名鍵生成部が、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すこととして、
cα:=(cα,1,cα,2,cα,3):=Enc(pke,g-α),
cαa1:=(cαa1,1,cαa1,2,cαa1,3):=Enc(pke,gαa1),
cv:=(cv,1,cv,2,cv,3):=Enc(pke,v),
cv1:=(cv1,1,cv1,2,cv1,3):=Enc(pke,v1), および
cv2:=(cv2,1,cv2,2,cv2,3):=Enc(pke,v2)を計算し、
難読化された暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を生成する暗号化署名鍵生成ステップと、
上記暗号化署名生成装置の暗号化署名生成部が、
(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (ただし、η',ψ'はZpの任意の元)と表すこととして、Zpの元r1, r2, z1, z2, tagkを選び、r:=r1+r2として、
１．(cσ1,1,cσ1,2,cσ1,3):=(cαa1,1・cv,1r,cαa1,2・cv,2r,cαa1,3・cv,3r), Cσ1:=(c1,1',c1,2',c1,3'):=ReRand(pke,(cσ1,1,cσ1,2,cσ1,3))
２．(cσ2,1,cσ2,2,cσ2,3):=(cα,1・cv1,1r,cα,2・cv1,2r, cα,3・cv1,3r・gz1), Cσ2:=(c2,1',c2,2',c2,3'):=ReRand(pke,(cσ2,1,cσ2,2,cσ2,3))
３．σ3:=(gb)-z1, Cσ3:=Enc(pke,σ3)
４．(cσ4,1,cσ4,2,cσ4,3):=(cv2,1r,cv2,2r,cv2,3r・gz2), Cσ4:=(c4,1',c4,2',c4,3'):=ReRand(pke,(cσ4,1,cσ4,2,cσ4,3))
５．σ5:=(gb)-z2, Cσ5:=Enc(pke,σ5)
６．σ6:=(gb)r2, Cσ6:=Enc(pke,σ6)
７．σ7:=gr1, Cσ7:=Enc(pke,σ7)
８．σ8:=(uMwtagkh)r1, Cσ8:=Enc(pke,σ8)
９．Cσ9:=Enc(pke,tagk)
を計算して、暗号化署名ctσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)を出力する暗号化署名生成ステップと、
上記受信装置の復号部が、暗号化署名Cσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)についてCi=(ci,1,ci,2,ci,3) （ただし、i=1，…，9）と分割し、各i（i=1，…，9）について復号鍵dkを用いてσi:=ci,3/(ci,1)(1/xe)(ci,2)(1/ye)を計算し、復号された署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を出力する復号ステップを有する
難読化された署名鍵を用いた暗号化署名方法。
【請求項８】
調停装置と送信装置と受信装置と検証可能暗号化署名鍵難読化装置と暗号化検証可能暗号化署名生成装置を含む暗号化署名システムにおける暗号化署名方法であって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成ステップと、
上記検証可能暗号化署名鍵難読化装置の暗号化署名鍵生成部が、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すことにして、Zpの元ρα,ραa1,ρv,ρv1,ρv2を選び、
(cα,1',cα,2',cα,3'):=Enc(pke,g-α),
cα:=(cα,1',cα,2',cα,3'・ζρα,gρα,gba1ρα),
(cαa1,1',cαa1,2',cαa1,3'):=Enc(pke,gαa1),
cαa1:=(cαa1,1',cαa1,2',cαa1,3'・ζραa1,gραa1,gbραa1),
(cv,1',cv,2',cv,3'):=Enc(pke,v),
cv:=(cv,1',cv,2',cv,3'・ζρv,gρv,gbρv),
(cv1,1',cv1,2',cv1,3'):=Enc(pke,v1),
cv1:=(cv1,1',cv1,2',cv1,3'・ζρv1,gρv1,gba1ρv1),
(cv2,1',cv2,2',cv2,3'):=Enc(pke,v2)，
cv2:=(cv2,1',cv2,2',cv2,3'・ζρv2,gρv2,gba2ρv2)
を計算し、難読化された暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を出力する暗号化署名鍵生成ステップと、
上記暗号化検証可能暗号化署名生成装置の暗号化検証可能暗号化署名生成部が、
(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (ただし、η',ψ'はZpの任意の元)を表すこととして、Zpの元r1, r2, z1, z2, tagkを選び、r:=r1+r2とし、
１．c1,1:=cαa1,1・cv,1r, c1,2:=cαa1,2・cv,2r, K1:=cαa1,3・cv,3r・ζρ1, K1':=cαa1,4・cv,4r・gρ1, K1^:=cαa1,5・cv,5r・(gb)ρ1, C1:=(c1,1',c1,2',c1,3'):=ReRand(pke,(c1,1,c1,2,K1)), C1':=Enc(pke,K1'), C1^:=Enc(pke,K1^).
２．c2,1:=cα,1・cv1,1r, c2,2:=cα,2・cv1,2r, K2:=cα,3・cv1,3r・gz1・ζρ2, K2':=cα,4・cv1,4r・gρ2, K2^:=cα,5・cv1,5r・(gba1)ρ2, C2:=(c2,1',c2,2',c2,3'):=ReRand(pke,(c2,1,c2,2,K2)), C2':=Enc(pke,K2'), C2^:=Enc(pke,K2^).
３．K3:=(gb)-z1・ζρ3,K3':=gρ3,K3^:=(ga1)ρ3, C3:=Enc(pke,σ3), C3':=Enc(pke,K3'), C3^:=Enc(pke,K3')
４．c4,1:=cv2,2r,c4,2:=cv2,3r,K4:=cv2,3r・gz2・ζρ4, K4':=cv2,4r・gρ4, K4^:=cv2,5r・(gba2)ρ4, C4:=(c4,1',c4,2',c4,3'):=ReRand (pke,(c4,1,c4,2,K4)), C4':=Enc(pke,K4'), C4^:=Enc(pke,K4^).
５．K5:=(gb)-z2, C5:=Enc(pke,K5)
６．K6:=(gb)r2, C6:=Enc(pke,K6)
７．K7:=gr1, C7:=Enc(pke,K7)
８．K8:=(uMwtagkh)r1,C8:=Enc(pke,K8)
９．C9:=Enc(pke,tagk)
を計算して、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)を出力する暗号化検証可能暗号化署名生成ステップと、
上記受信装置の復号部が、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)についてCi=(ci,1',ci,2',ci,3') （ただし、i=1，…，9）と分割し、各i（i=1，…，9）について復号鍵dkを用いてKi:=ci,3'/((ci,1')1/xe(ci,2')1/ye)を計算し、Cj',Cj^についてdk:=(xe,ye)を用いて復号し、復号した検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K1',K2',K3',K4',K1^,K2^,K3^,K4^)を出力する復号ステップを有する
難読化された署名鍵を用いた暗号化署名方法。
【請求項９】
送信装置と受信装置と署名鍵難読化装置を含む署名鍵難読化システムにおける署名鍵難読化方法であって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとして、
上記送信装置の鍵生成部が、群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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成ステップと、
上記署名鍵難読化装置の暗号化署名鍵生成部が、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すこととして、
cα:=(cα,1,cα,2,cα,3):=Enc(pke,g-α),
cαa1:=(cαa1,1,cαa1,2,cαa1,3):=Enc(pke,gαa1),
cv:=(cv,1,cv,2,cv,3):=Enc(pke,v),
cv1:=(cv1,1,cv1,2,cv1,3):=Enc(pke,v1), および
cv2:=(cv2,1,cv2,2,cv2,3):=Enc(pke,v2)を計算し、
難読化された暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を生成する暗号化署名鍵生成ステップを有する
署名鍵難読化方法。
【請求項１０】
調停装置と送信装置と受信装置と検証可能暗号化署名鍵難読化装置を含む署名鍵難読化システムにおける署名鍵難読化方法であって、
pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする鍵生成ステップと、
上記検証可能暗号化署名鍵難読化装置の暗号化署名鍵生成部が、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（ただし、η,ψはZpの任意の元）と表すことにして、Zpの元ρα,ραa1,ρv,ρv1,ρv2を選び、
(cα,1',cα,2',cα,3'):=Enc(pke,g-α),
cα:=(cα,1',cα,2',cα,3'・ζρα,gρα,gba1ρα),
(cαa1,1',cαa1,2',cαa1,3'):=Enc(pke,gαa1),
cαa1:=(cαa1,1',cαa1,2',cαa1,3'・ζραa1,gραa1,gbραa1),
(cv,1',cv,2',cv,3'):=Enc(pke,v),
cv:=(cv,1',cv,2',cv,3'・ζρv,gρv,gbρv),
(cv1,1',cv1,2',cv1,3'):=Enc(pke,v1),
cv1:=(cv1,1',cv1,2',cv1,3'・ζρv1,gρv1,gba1ρv1),
(cv2,1',cv2,2',cv2,3'):=Enc(pke,v2)，
cv2:=(cv2,1',cv2,2',cv2,3'・ζρv2,gρv2,gba2ρv2)
を計算し、難読化された暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を出力する暗号化署名鍵生成ステップを有する
署名鍵難読化方法。
【請求項１１】
請求項７または８に記載の暗号化署名方法もしくは請求項９または１０に記載の署名鍵難読化方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名の難読化技術と、難読化された署名鍵を用いた暗号化署名技術に関する。
【背景技術】
【０００２】
暗号化署名の難読化について、Hadaによる方式が存在する（非特許文献１参照）。これは標準モデルにおいて標準的暗号学仮定に基づき安全性が証明できる方式であるが、検証鍵のサイズがセキュリティパラメータに比例して大きくなってしまうという欠点がある。
【０００３】
暗号化検証可能暗号化署名の難読化について、Chengらによる方式が存在する（非特許文献２参照）。これはランダムオラクルモデル(ROM)の下で安全性が証明される非対話ゼロ知識証明を利用しており、モデルが現実的でない。さらに暗号学仮定が非標準的な仮定（exponent 3-weak DH仮定）であり、安全性に信頼がおけない。また検証鍵のサイズもセキュリティパラメータに比例して大きくなるという欠点がある・
【０００４】
なお、安全性が証明可能な難読化技術は非常に困難であり、実現例は数少ない（非特許文献３）。
【０００５】
なお、標準モデルやランダムオラクルモデル、暗号の安全性などについては、例えば非特許文献４が参考になる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】S. Hada. Secure Obfuscation for Encrypted Signatures. In EUROCRYPT, volume 6110 of Lecture Notes in Computer Science, pages 92-112. Springer, 2010.
【非特許文献２】R. Cheng, B. Zhang, and F. Zhang. Secure Obfuscation of Encrypted Verifiable Encrypted Signatures. In ProvSec, volume 6980 of Lecture Notes in Computer Science, pages 188-203. Springer, 2011.
【非特許文献３】B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, and K. Yang. On the (Im)possibility of Obfuscating Programs. In CRYPTO’01, volume 2139 of LNCS, 2001.
【非特許文献４】森山大輔、西巻陵、岡本龍明共著、「公開鍵暗号の数理−シリーズ応用数理第２巻−」、初版、共立出版株式会社、２０１１年３月、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を双線形写像、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとする。送信装置の鍵生成部が、群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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする[鍵生成処理]。そして、署名鍵難読化装置の暗号化署名鍵生成部が、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（η,ψ ←U Zp）と表すこととして、
cα:=(cα,1,cα,2,cα,3) ←R Enc(pke,g-α), 
cαa1:=(cαa1,1,cαa1,2,cαa1,3) ←R Enc(pke,gαa1), 
cv:=(cv,1,cv,2,cv,3) ←R Enc(pke,v), 
cv1:=(cv1,1,cv1,2,cv1,3) ←R Enc(pke,v1), および 
cv2:=(cv2,1,cv2,2,cv2,3) ←R Enc(pke,v2)を計算し、
難読化された暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を生成する[暗号化署名鍵生成処理]。そして、暗号化署名生成装置の暗号化署名生成部が、(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (η',ψ' ←U Zp)と表すこととして、Zpの元r1, r2, z1, z2, tagkを選び、r:=r1+r2として、
１．(cσ1,1,cσ1,2,cσ1,3):=(cαa1,1・cv,1r,cαa1,2・cv,2r,cαa1,3・cv,3r), Cσ1:=(c1,1',c1,2',c1,3') ←R ReRand(pke,(cσ1,1,cσ1,2,cσ1,3))
２．(cσ2,1,cσ2,2,cσ2,3):=(cα,1・cv1,1r,cα,2・cv1,2r, cα,3・cv1,3r・gz1), Cσ2:=(c2,1',c2,2',c2,3') ←R ReRand(pke,(cσ2,1,cσ2,2,cσ2,3))
３．σ3:=(gb)-z1, Cσ3 ←REnc(pke,σ3)
４．(cσ4,1,cσ4,2,cσ4,3):=(cv2,1r,cv2,2r,cv2,3r・gz2), Cσ4:=(c4,1',c4,2',c4,3') ←R ReRand(pke,(cσ4,1,cσ4,2,cσ4,3))
５．σ5:=(gb)-z2, Cσ5 ←R Enc(pke,σ5) 
６．σ6:=(gb)r2, Cσ6 ←R Enc(pke,σ6)
７．σ7:=gr1, Cσ7←R Enc(pke,σ7)
８．σ8:=(uMwtagkh)r1, Cσ8 ←R Enc(pke,σ8) 
９．Cσ9 ←R Enc(pke,tagk)
を計算して、暗号化署名ctσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)を出力する[暗号化署名生成処理]。そして、受信装置の復号部が、暗号化署名Cσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)についてCi=(ci,1,ci,2,ci,3) （ただし、i=1，…，9）と分割し、各i（i=1，…，9）について復号鍵dkを用いてσi:=ci,3/(ci,1)(1/xe)(ci,2)(1/ye)を計算し、復号された署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を出力する[復号処理]。
【００１０】
あるいは、本発明の暗号化署名技術は、次のとおりである。調停装置の調停者鍵生成部が、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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする[鍵生成処理]。そして、検証可能暗号化署名鍵難読化装置の暗号化署名鍵生成部は、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（η,ψ ←U Zp）と表すことにして、Zpの元ρα,ραa1,ρv,ρv1,ρv2を選び、
(cα,1',cα,2',cα,3') ←R Enc(pke,g-α), 
cα:=(cα,1',cα,2',cα,3'・ζρα,gρα,gba1ρα), 
(cαa1,1',cαa1,2',cαa1,3') ←R Enc(pke,gαa1), 
cαa1:=(cαa1,1',cαa1,2',cαa1,3'・ζραa1,gραa1,gbραa1), 
(cv,1',cv,2',cv,3') ←R Enc(pke,v), 
cv:=(cv,1',cv,2',cv,3'・ζρv,gρv,gbρv), 
(cv1,1',cv1,2',cv1,3') ←R Enc(pke,v1), 
cv1:=(cv1,1',cv1,2',cv1,3'・ζρv1,gρv1,gba1ρv1), 
(cv2,1',cv2,2',cv2,3') ←R Enc(pke,v2)，
cv2:=(cv2,1',cv2,2',cv2,3'・ζρv2,gρv2,gba2ρv2)
を計算し、難読化された暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を出力する[暗号化署名鍵生成処理]。そして、暗号化検証可能暗号化署名生成装置の暗号化検証可能暗号化署名生成部が、(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (η',ψ' ←U Zp)を表すこととして、Zpの元r1, r2, z1, z2, tagkを選び、r:=r1+r2とし、
１．c1,1:=cαa1,1・cv,1r, c1,2:=cαa1,2・cv,2r, K1:=cαa1,3・cv,3r・ζρ1, K1':=cαa1,4・cv,4r・gρ1, K1^:=cαa1,5・cv,5r・(gb)ρ1, C1:=(c1,1',c1,2',c1,3') ←R ReRand(pke,(c1,1,c1,2,K1)), C1' ←R Enc(pke,K1'), C1^ ←R Enc(pke,K1^). 
２．c2,1:=cα,1・cv1,1r, c2,2:=cα,2・cv1,2r, K2:=cα,3・cv1,3r・gz1・ζρ2, K2':=cα,4・cv1,4r・gρ2, K2^:=cα,5・cv1,5r・(gba1)ρ2, C2:=(c2,1',c2,2',c2,3') ←R ReRand(pke,(c2,1,c2,2,K2)), C2' ←R Enc(pke,K2'), C2^ ←R Enc(pke,K2^).  
３．K3:=(gb)-z1・ζρ3,K3':=gρ3,K3^:=(ga1)ρ3, C3 ←R Enc(pke,σ3), C3' ←R Enc(pke,K3'), C3^ ←R Enc(pke,K3')
４．c4,1:=cv2,2r,c4,2:=cv2,3r,K4:=cv2,3r・gz2・ζρ4, K4':=cv2,4r・gρ4, K4^:=cv2,5r・(gba2)ρ4, C4:=(c4,1',c4,2',c4,3') ←R ReRand (pke,(c4,1,c4,2,K4)), C4' ←R Enc(pke,K4'), C4^ ←R Enc(pke,K4^). 
５．K5:=(gb)-z2, C5 ←R Enc(pke,K5) 
６．K6:=(gb)r2, C6 ←R Enc(pke,K6)
７．K7:=gr1, C7 ←R Enc(pke,K7)
８．K8:=(uMwtagkh)r1,C8 ←R Enc(pke,K8) 
９．C9 ←R Enc(pke,tagk)
を計算して、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)を出力する[暗号化検証可能暗号化署名生成処理]。そして、受信装置の復号部が、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)についてCi=(ci,1',ci,2',ci,3') （ただし、i=1，…，9）と分割し、各i（i=1，…，9）について復号鍵dkを用いてKi:=ci,3'/((ci,1')1/xe(ci,2')1/ye)を計算し、Cj',Cj^についてdk:=(xe,ye)を用いて復号し、復号した検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K1',K2',K3',K4',K1^,K2^,K3^,K4^)を出力する[復号処理]。
【００１１】
本発明の署名難読化技術は、次のとおりである。pを素数、Zを整数全体を表す集合、Zpをpを法とするZの剰余類環、Zp＊=Zp-{0}、G,GTをそれぞれ素数位数pの巡回乗法群、gを群Gの生成元、eを双線形写像、Γ:=(p,G,GT,e,g)を双線型写像についての標準的な群生成アルゴリズムによって生成された予め定められたシステムパラメータとする。送信装置の鍵生成部が、群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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする[鍵生成処理]。そして、署名鍵難読化装置の暗号化署名鍵生成部が、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（η,ψ ←U Zp）と表すこととして、
cα:=(cα,1,cα,2,cα,3) ←R Enc(pke,g-α), 
cαa1:=(cαa1,1,cαa1,2,cαa1,3) ←R Enc(pke,gαa1), 
cv:=(cv,1,cv,2,cv,3) ←R Enc(pke,v), 
cv1:=(cv1,1,cv1,2,cv1,3) ←R Enc(pke,v1), および 
cv2:=(cv2,1,cv2,2,cv2,3) ←R Enc(pke,v2)を計算し、
難読化された暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を生成する[暗号化署名鍵生成処理]。
【００１２】
あるいは、本発明の署名難読化技術は、次のとおりである。調停装置の調停者鍵生成部が、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の元xe,yeを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする[鍵生成処理]。そして、検証可能暗号化署名鍵難読化装置の暗号化署名鍵生成部が、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（η,ψ ←U Zp）と表すことにして、Zpの元ρα,ραa1,ρv,ρv1,ρv2を選び、
(cα,1',cα,2',cα,3') ←R Enc(pke,g-α), 
cα:=(cα,1',cα,2',cα,3'・ζρα,gρα,gba1ρα), 
(cαa1,1',cαa1,2',cαa1,3') ←R Enc(pke,gαa1), 
cαa1:=(cαa1,1',cαa1,2',cαa1,3'・ζραa1,gραa1,gbραa1), 
(cv,1',cv,2',cv,3') ←R Enc(pke,v), 
cv:=(cv,1',cv,2',cv,3'・ζρv,gρv,gbρv), 
(cv1,1',cv1,2',cv1,3') ←R Enc(pke,v1), 
cv1:=(cv1,1',cv1,2',cv1,3'・ζρv1,gρv1,gba1ρv1), 
(cv2,1',cv2,2',cv2,3') ←R Enc(pke,v2)，
cv2:=(cv2,1',cv2,2',cv2,3'・ζρv2,gρv2,gba2ρv2)
を計算し、難読化された暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を出力する[暗号化署名鍵生成処理]。
【発明の効果】
【００１３】
本発明に拠れば、詳細は後述の実施形態に譲るが、安全性が標準的な暗号学的仮定のみに基づており、検証鍵のサイズがセキュリティパラメータのサイズに依存しない、署名難読化技術と、難読化された署名鍵を用いた暗号化署名技術となっている。
【図面の簡単な説明】
【００１４】
【図１】実施形態１の暗号化署名システムを示す図。
【図２】実施形態１における暗号化署名の処理手順を示す図。
【図３】実施形態１に関わる暗号化署名システムの構成要素であるシステムパラメータ生成装置、送信装置、受信装置、署名鍵難読化装置、暗号化署名生成装置の機能構成を示す図。
【図４】実施形態２の暗号化署名システムを示す図。
【図５】実施形態２における暗号化署名の処理手順を示す図。
【図６】実施形態２に関わる暗号化署名システムの構成要素であるシステムパラメータ生成装置、調停装置、送信装置、受信装置、検証可能暗号化署名鍵難読化装置、暗号化検証可能暗号化署名生成装置の機能構成を示す図。
【発明を実施するための形態】
【００１５】
本発明の実施形態を説明する前に、いくつかの基本的事項について説明する。
まず、記法について説明する。
或る有限集合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(λ)が無視できることをいう。
【００２１】
［Waters05署名］
Waters05署名の概要は下記のとおりである（参考文献２）。
鍵生成：
γ:=(q,G,GT,e,g) ←R BMSetup(1λ)、α ←U Zq、 g1:=gα, g2,u', u1, …, un ←U G, U:={ui}i∈[n], pk:=(g1,g2,u',U), sk:=(g2α,u',U)
署名生成：
m:=(m1,…,mn), x ←U Zq, σ:=(σ1,σ2):=(g2α(u'Πi∈Mu2)x,gx)
ただしMはmi=1を満たすiの集合を表す。
検証：
e(σ1,g)=e(g1,g2)e(σ2,u'Πi∈Mui)
（参考文献２）B. Waters. Efficient Identity-Based Encryption Without Random Oracles. In EUROCRYPT’05, volume 3494 of Lecture Notes in Computer Science, pages 114-127. Springer, 2005.
【００２２】
［線型暗号化］
LGen(1λ):
セキュリティパラメータλを入力として、Γ:=(p,G,GT,e,g) ←R BMSetup(1λ)を生成し、a,b ←UZpを選択し、pk:=(f,h):=(ga,gb), dk:=(a,b)を出力する。
LEnc(pk,m):
平文m∈Gと公開鍵pk:=(f,h)を入力として、r,s ←UZp を選択して、暗号文c:=(c1,c2,c3):=(fr,hs,gr+sm)を出力する。
LDec(sk,c):
暗号文c=(c1,c2,c3)と秘密鍵dkを入力として、平文m:=c3/(c11/ac21/b)を出力する。
【００２３】
次に、本発明が基づくWaters09署名について概説する（参考文献３）。λはセキュリティパラメータを表す。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
【００２７】
本発明は、既存技術と異なりWaters09署名を利用する（既存技術はWaters05署名を利用している）。Waters09署名を利用して暗号化署名および暗号化検証可能暗号化署名を実現できるかは自明ではない。なぜならWaters09署名はWaters05署名と比べ、署名鍵、署名の要素が増加し、署名生成方法が大きく異なり、構造が複雑になっているからである。特に、Waters05署名では署名生成において、署名鍵を利用する部分は他の群要素に署名鍵を乗じるだけという単純な構造であったが、Waters09署名では署名鍵を乱数を用いて冪乗し複数の群要素と乗じる必要がある、という点で大きく異なる。本発明は、暗号化方式の加法準同型性を冪乗演算にも活用することによって複雑な構造についても難読化できるようにしている。さらに検証可能暗号化署名については、検証可能暗号化署名の内部で利用する暗号化方式と検証可能暗号化署名そのものを暗号化するための暗号方式を別の方式にし、且つ組み合わせることができるような方式を利用することに特徴がある。従来技術では同じ暗号方式を利用していたため、検証可能性の実現が困難になっていた。具体的には検証可能暗号化署名の実現に線型暗号方式を利用していたことが問題になっていた。また、既存技術は非対話ゼロ知識証明を導入することでこの問題を解決していたが、本発明では非対話ゼロ知識証明が不要である。
【００２８】
《実施形態１》
［暗号化署名システム］
実施形態の暗号化署名システム１は、図１に示すように、システムパラメータ生成装置５００、送信装置２００、受信装置３００、署名鍵難読化装置６００、暗号化署名生成装置７００を含んで構成される。これらの各装置は、例えばインターネットなどの通信網５を経由して、相互に通信可能とされている。なお、後述のシステムパラメータが予め決まっていれば十分なので、システムパラメータ生成装置５００は暗号化署名システム１の必須の構成要素ではなく、図示しない装置によって生成された当該システムパラメータが暗号化署名システム１に提供されていれば足りる。
【００２９】
本発明の暗号化署名システムは、ユーザなどの数に応じて一つまたは複数の送信装置２００と一つまたは複数の受信装置３００を含みえるが、本発明の理解を容易にするため、後述の実施形態では、暗号化署名システム１は、１個の送信装置２００と１個の受信装置３００と１個の署名鍵難読化装置６００と１個の暗号化署名生成装置７００を含むとする。
【００３０】
暗号化署名システム１における処理を、図２を参照しながら叙述する。各装置の機能構成については、図３を参照されたい。
【００３１】
システムパラメータ生成装置５００のシステムパラメータ生成部５０１は、既述の暗号学的仮定の下、セキュリティパラメータλを入力とし、システム全体に共通なシステムパラメータ、つまり双線形写像のパラメータΓ:=(p,G,GT,e,g) ←R BMsetup(1λ)を出力する（ステップＳ１）。システムパラメータ生成装置５００の送信部５０８は、パラメータΓを各装置２００，３００，６００，７００に送信する。
【００３２】
送信装置２００の受信部２０９は、パラメータΓを受信する。パラメータΓは送信装置２００の図示しない記憶部に記憶される。
【００３３】
送信装置２００の鍵生成部２０１は、システムパラメータ生成装置５００から受信したΓ:=(p,G,GT,e,g)を入力とし、以下のとおりWaters09署名の鍵対を生成する。群の元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)を出力する（ステップＳ２）。検証鍵VKおよび署名鍵SKも送信装置２００の図示しない記憶部に記憶される。
【００３４】
送信装置２００の送信部２０８は、平文Mを暗号化署名生成装置７００に送信し、署名鍵SKを署名鍵難読化装置６００に送信する。
【００３５】
受信装置３００の受信部３０９はシステムパラメータΓを受信し、システムパラメータΓは受信装置３００の図示しない記憶部に記憶される。
【００３６】
受信装置３００の鍵生成部３０１は、システムパラメータΓを入力とし、xe, ye ←UZpを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする（ステップＳ３）。
【００３７】
受信装置３００の送信部３０８は、公開鍵pkeを署名鍵難読化装置６００に送信する。
【００３８】
署名鍵難読化装置６００の受信部６０９は、送信装置２００の署名鍵SK、受信装置３００の公開鍵pke、システムパラメータΓを受信し、これらは署名鍵難読化装置６００の図示しない記憶部に記憶される。
【００３９】
署名鍵難読化装置６００の暗号化署名鍵生成部６０１は、送信装置２００の署名鍵SKと受信装置３００の公開鍵pke、システムパラメータΓを入力とし、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（η,ψ ←U Zp）と表すこととすると、
cα:=(cα,1,cα,2,cα,3) ←R Enc(pke,g-α), 
cαa1:=(cαa1,1,cαa1,2,cαa1,3) ←R Enc(pke,gαa1), 
cv:=(cv,1,cv,2,cv,3) ←R Enc(pke,v), 
cv1:=(cv1,1,cv1,2,cv1,3) ←R Enc(pke,v1), および 
cv2:=(cv2,1,cv2,2,cv2,3) ←R Enc(pke,v2)を計算し、
難読化された暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を生成する（ステップＳ４）。
【００４０】
署名鍵難読化装置６００の送信部６０９は、暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)を暗号化署名生成装置７００に送信する。
【００４１】
暗号化署名生成装置７００の受信部７０９は、平文M、暗号化署名鍵obf(SK,pke):=ctsk:=(cα,cαa1,cv,cv1,cv2)、システムパラメータΓを受信し、これらは暗号化署名生成装置７００の図示しない記憶部に記憶される。
【００４２】
ここで(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (η',ψ' ←U Zp)と表すこととして、暗号化署名生成装置７００の暗号化署名生成部７０１は、平文Mと難読化された暗号化署名鍵ctsk:=(cα,cαa1,cv,cv1,cv2)を入力として、r1, r2, z1, z2, tagk ←U Zpを選び、r:=r1+r2として、
１．(cσ1,1,cσ1,2,cσ1,3):=(cαa1,1・cv,1r,cαa1,2・cv,2r,cαa1,3・cv,3r), Cσ1:=(c1,1',c1,2',c1,3') ←R ReRand(pke,(cσ1,1,cσ1,2,cσ1,3))
２．(cσ2,1,cσ2,2,cσ2,3):=(cα,1・cv1,1r,cα,2・cv1,2r, cα,3・cv1,3r・gz1), Cσ2:=(c2,1',c2,2',c2,3') ←R ReRand(pke,(cσ2,1,cσ2,2,cσ2,3))
３．σ3:=(gb)-z1, Cσ3 ←REnc(pke,σ3)
４．(cσ4,1,cσ4,2,cσ4,3):=(cv2,1r,cv2,2r,cv2,3r・gz2), Cσ4:=(c4,1',c4,2',c4,3') ←R ReRand(pke,(cσ4,1,cσ4,2,cσ4,3))
５．σ5:=(gb)-z2, Cσ5 ←R Enc(pke,σ5) 
６．σ6:=(gb)r2, Cσ6 ←R Enc(pke,σ6)
７．σ7:=gr1, Cσ7←R Enc(pke,σ7)
８．σ8:=(uMwtagkh)r1, Cσ8 ←R Enc(pke,σ8) 
９．Cσ9 ←R Enc(pke,tagk)
を計算して、暗号化署名ctσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)を出力する（ステップＳ５）。
【００４３】
難読化された暗号化署名鍵についてη,ψ ←U Zpを明示的に表すために(feη,heψ,gη+ψm):=Enc(pke,m;η,ψ)と表すことにすると、Enc(pke,・)の加法準同型性により、(cσ1,1,cσ1,2,cσ1,3)=Enc(pke,gαa1・vr;ηαa1+rηv,ψαa1+rψv), (cσ2,1,cσ2,2,cσ2,3)=Enc(pke,g-α・v1r・gz1;ηα+rηv1,ψα+rψv1), (cσ4,1,cσ4,2,cσ4,3)=Enc(pke,v2r・gz2;rηv2,rψv2)と表すことができる。
【００４４】
暗号化署名生成装置７００の送信部７０８は、暗号化署名ctσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)を受信装置３００に送信する。
【００４５】
受信装置３００の受信部３０９は、暗号化署名生成装置７００から暗号化署名ctσを受信する。
【００４６】
受信装置３００の復号部３０２は、暗号化署名Cσ:=(Cσ1,Cσ2,Cσ3,Cσ4,Cσ5,Cσ6,Cσ7,Cσ8,Cσ9)を受信したときCi=(ci,1,ci,2,ci,3)と分割し、各i（i=1，…，9）について復号鍵dkを用いてσi:=ci,3/(ci,1)(1/xe)(ci,2)(1/ye)を計算し、復号された署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を出力する（ステップＳ６）。
【００４７】
なお、ステップＳ７の処理にて復号された署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)は、仮に送信装置２００の署名生成部２０２が生成するとした場合のWaters09署名に一致する。仮に署名生成部２０２が生成するとした場合のWaters09署名は、次のとおりである。署名生成部２０２は、署名鍵SKと平文Mを入力として、r1, r2, z1, z2, tagk ←U Zpを選び（ただし、r1, r2, z1, z2, tagkは暗号化署名生成装置７００の暗号化署名生成部７０１が選択した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を計算して、Waters09署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を出力する。
【００４８】
《実施形態２》
［暗号化署名システム］
実施形態の暗号化署名システム２は、図４に示すように、システムパラメータ生成装置５００、調停装置１００、送信装置２００、受信装置３００、検証可能暗号化署名鍵難読化装置８００、暗号化検証可能暗号化署名生成装置９００を含んで構成される。これらの各装置は、例えばインターネットなどの通信網５を経由して、相互に通信可能とされている。なお、後述のシステムパラメータが予め決まっていれば十分なので、システムパラメータ生成装置５００は暗号化署名システム１の必須の構成要素ではなく、図示しない装置によって生成された当該システムパラメータが暗号化署名システム２に提供されていれば足りる。
【００４９】
本発明の暗号化署名システムは、ユーザなどの数に応じて一つまたは複数の送信装置２００と一つまたは複数の受信装置３００を含みえるが、本発明の理解を容易にするため、後述の実施形態では、暗号化署名システム２は、１個の送信装置２００と１個の受信装置３００と１個の検証可能暗号化署名鍵難読化装置８００と１個の暗号化検証可能暗号化署名生成装置９００を含むとする。
【００５０】
暗号化署名システム２における処理を、図５を参照しながら叙述する。各装置の機能構成については、図６を参照されたい。
【００５１】
システムパラメータ生成装置５００のシステムパラメータ生成部５０１は、既述の暗号学的仮定の下、セキュリティパラメータλを入力とし、システム全体に共通なシステムパラメータ、つまり双線形写像のパラメータΓ:=(p,G,GT,e,g) ←R BMsetup(1λ)を出力する（ステップＳ１０）。
【００５２】
システムパラメータ生成装置５００の送信部５０８は、パラメータΓを各装置１００，２００，３００，８００，９００に送信する。
【００５３】
調停装置１００の受信部１０９は、パラメータΓを受信する。パラメータΓは調停装置１００の図示しない記憶部に記憶される。調停装置１００の調停者鍵生成部１０１は、調停者公開鍵および調停者復号鍵を以下のように生成する。システムパラメータ生成装置５００から受信したΓ:=(p,G,GT,e,g)を入力とし、β ←U Zp＊を選び、調停者公開鍵apk:=ζ:=gβおよび調停者復号鍵ask:=βを出力する（ステップＳ１１）。Zp＊=Zp-{0}である。調停者公開鍵apkおよび調停者復号鍵askも調停装置１００の図示しない記憶部に記憶される。
【００５４】
調停装置１００の送信部１０８は、調停者公開鍵apkを検証可能暗号化署名鍵難読化装置８００と受信装置３００に送信する。
【００５５】
送信装置２００の受信部２０９は、パラメータΓを受信する。パラメータΓは送信装置２００の図示しない記憶部に記憶される。
【００５６】
送信装置２００の鍵生成部２０１は、システムパラメータ生成装置５００から受信したΓ:=(p,G,GT,e,g)を入力とし、以下のとおりWaters09署名の鍵対を生成する。群の元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)を出力する（ステップＳ１２）。検証鍵VKおよび署名鍵SKも送信装置２００の図示しない記憶部に記憶される。
【００５７】
送信装置２００の送信部２０８は、平文Mを受信装置３００と暗号化検証可能暗号化署名生成装置９００に、署名鍵SKを検証可能暗号化署名鍵難読化装置８００に、検証鍵VKを受信装置３００に送信する。なお、必要に応じて、送信装置２００の送信部２０８は、検証鍵VKを調停装置１００にも送信する。
【００５８】
受信装置３００の受信部３０９は平文M、検証鍵VK、調停者公開鍵apk、システムパラメータΓを受信し、これらは受信装置３００の図示しない記憶部に記憶される。
【００５９】
受信装置３００の鍵生成部３０１は、システムパラメータΓを入力とし、xe, ye ←UZpを選び、公開鍵pke:=(fe,he):=(gxe,gye), 復号鍵dk:=(xe,ye)とする（ステップＳ１３）。
【００６０】
受信装置３００の送信部３０８は、公開鍵pkeを検証可能暗号化署名鍵難読化装置８００に送信する。
【００６１】
検証可能暗号化署名鍵難読化装置８００の受信部８０９は、送信装置２００の署名鍵SK、受信装置３００の公開鍵pke、調停装置１００の調停者公開鍵apk、システムパラメータΓを受信し、これらは検証可能暗号化署名鍵難読化装置８００の図示しない記憶部に記憶される。
【００６２】
検証可能暗号化署名鍵難読化装置８００の暗号化署名鍵生成部８０１は、送信装置２００の署名鍵SK:=(VK,gα,gαa1,v,v1,v2)、受信装置３００の公開鍵pke:=(fe,he)および調停装置１００の公開鍵apk:=ζを入力として、或る値mをpkeで暗号化することを(feη,heψ,gη+ψm):=Enc(pke,m)（η,ψ ←U Zp）と表すことにして、ρα,ραa1,ρv,ρv1,ρv2 ←U Zpを選び、
(cα,1',cα,2',cα,3') ←R Enc(pke,g-α), 
cα:=(cα,1',cα,2',cα,3'・ζρα,gρα,gba1ρα), 
(cαa1,1',cαa1,2',cαa1,3') ←R Enc(pke,gαa1), 
cαa1:=(cαa1,1',cαa1,2',cαa1,3'・ζραa1,gραa1,gbραa1), 
(cv,1',cv,2',cv,3') ←R Enc(pke,v), 
cv:=(cv,1',cv,2',cv,3'・ζρv,gρv,gbρv), 
(cv1,1',cv1,2',cv1,3') ←R Enc(pke,v1), 
cv1:=(cv1,1',cv1,2',cv1,3'・ζρv1,gρv1,gba1ρv1), 
(cv2,1',cv2,2',cv2,3') ←R Enc(pke,v2)，
cv2:=(cv2,1',cv2,2',cv2,3'・ζρv2,gρv2,gba2ρv2)
を計算し、難読化された暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を出力する（ステップＳ１４）。
【００６３】
検証可能暗号化署名鍵難読化装置８００の送信部８０９は、暗号化署名鍵obf(SK,pke,apk):=ctsk:=(cα,cαa1,cv,cv1,cv2)を暗号化検証可能暗号化署名生成装置９００に送信する。
【００６４】
暗号化検証可能暗号化署名生成装置９００の受信部９０９は平文Mと暗号化署名鍵ctsk:=(cα,cαa1,cv,cv1,cv2)を受信し、これらは暗号化検証可能暗号化署名生成装置９００の図示しない記憶部に記憶される。
【００６５】
ここで(c1・feη',c2・heψ',c3・gη'+ψ'):=ReRand(pke,c1,c2,c3) (η',ψ' ←U Zp)を表すものとして、暗号化検証可能暗号化署名生成装置９００の暗号化検証可能暗号化署名生成部９０１は、平文Mと暗号化署名鍵ctsk:=(cα,cαa1,cv,cv1,cv2)を入力とし、r1, r2, z1, z2, tagk ←U Zpを選び、r:=r1+r2とし、
１．c1,1:=cαa1,1・cv,1r, c1,2:=cαa1,2・cv,2r, K1:=cαa1,3・cv,3r・ζρ1, K1':=cαa1,4・cv,4r・gρ1, K1^:=cαa1,5・cv,5r・(gb)ρ1, C1:=(c1,1',c1,2',c1,3') ←R ReRand(pke,(c1,1,c1,2,K1)), C1' ←R Enc(pke,K1'), C1^ ←R Enc(pke,K1^). 
２．c2,1:=cα,1・cv1,1r, c2,2:=cα,2・cv1,2r, K2:=cα,3・cv1,3r・gz1・ζρ2, K2':=cα,4・cv1,4r・gρ2, K2^:=cα,5・cv1,5r・(gba1)ρ2, C2:=(c2,1',c2,2',c2,3') ←R ReRand(pke,(c2,1,c2,2,K2)), C2' ←R Enc(pke,K2'), C2^ ←R Enc(pke,K2^).  
３．K3:=(gb)-z1・ζρ3,K3':=gρ3,K3^:=(ga1)ρ3, C3 ←R Enc(pke,σ3), C3' ←R Enc(pke,K3'), C3^ ←R Enc(pke,K3')
４．c4,1:=cv2,2r,c4,2:=cv2,3r,K4:=cv2,3r・gz2・ζρ4, K4':=cv2,4r・gρ4, K4^:=cv2,5r・(gba2)ρ4, C4:=(c4,1',c4,2',c4,3') ←R ReRand (pke,(c4,1,c4,2,K4)), C4' ←R Enc(pke,K4'), C4^ ←R Enc(pke,K4^). 
５．K5:=(gb)-z2, C5 ←R Enc(pke,K5) 
６．K6:=(gb)r2, C6 ←R Enc(pke,K6)
７．K7:=gr1, C7 ←R Enc(pke,K7)
８．K8:=(uMwtagkh)r1,C8 ←R Enc(pke,K8) 
９．C9 ←R Enc(pke,tagk)
を計算して、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)を出力する（ステップＳ１５）。
【００６６】
難読化された署名鍵についてρ1':=ραa1+rρv+ρ1, ρ2':=ρα+rρv1+ρ2, ρ4':=rρv2+ρ4とおくと、(c1,1,c1,2,K1)=Enc(pke,gαa1・vr・ζρ1';ηαa1+rηv,ψαa1+rψv), (K1',K1^)=(gραa1+rρv+ρ1,(gb)ραa1+rρv+ρ1)=(gρ1',(gb)ρ1'), (c2,1,c2,2,K2)=Enc(pke,g-α・v1r・gz1・ζρ2';ηα+rηv1,ψα+rψv1), (K2',K2^)=(gρα+rρv1+ρ2,(gba1)ρα+rρv1+ρ2)=(gρ2',(gba1)ρ2'), 
(c4,1,c4,2,K4)=Enc(pke,v2r・gz2・ζρ4';rηv2,rψv2), (K4',K4^)=(grρv2+ρ4,(gba2)rρv2+ρ4)=(gρ4',(gba2)ρ4')と表すことができる。
【００６７】
暗号化検証可能暗号化署名生成装置９００の送信部９０８は、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)を受信装置３００に送信する。
【００６８】
受信装置３００の受信部３０９は、暗号化検証可能暗号化署名生成装置９００から暗号化署名ctσを受信する。
【００６９】
受信装置３００の復号部３０２は、暗号化検証可能暗号化署名ctσ:=(C1,C2,C3,C4,C5,C6,C7,C8,C9,C1',C2',C3',C4',C1^,C2^,C3^,C4^)を受信したときCi=(ci,1',ci,2',ci,3')と分割し、各i（i=1，…，9）について復号鍵dkを用いてKi:=ci,3'/((ci,1')1/xe(ci,2')1/ye)を計算し、Cj',Cj^についてもdk:=(xe,ye)を用いて復号し、復号した検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K1',K2',K3',K4',K1^,K2^,K3^,K4^)を出力する（ステップＳ１６）。
【００７０】
受信装置３００による検証処理は次のとおりである。受信装置３００の検証部３０３は、検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K1',K2',K3',K4',K1^,K2^,K3^,K4^)、平文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-K9≠0を確認し、θ:=1/(tagc-K9)として、e(K1',gb)=e(g,K1^), e(K2',gba1)=e(g,K2^), e(K3',ga1)=e(g,K3^), e(K4',gba2)=e(g,K4^), および(e(V1,K1)/e(ζs,K1^))・(e(V2,K2)/e(ζs1,K2^))・(e(V3,K3)/e(ζs1,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を出力する。
【００７１】
受信装置３００は、送信装置２００による平文Mに対する署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を必要とする場合、送信部３０８によって、検証可能暗号化署名ωと平文Mを調停装置１００に送信する。
【００７２】
調停装置１００の受信部１０９は、送信装置２００からの検証鍵VKと、受信装置３００からの検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K1',K2',K3',K4',K1^,K2^,K3^,K4^)および平文Mを受信し、これらは調停装置１００の図示しない記憶部に記憶される。
【００７３】
調停装置１００は、さらに、検証可能暗号化署名ωの暗号化を解除して通常の署名を復元する復元部１０２を備えている。復元部１０２が検証可能暗号化署名の暗号化を解除する処理は次のとおりである。復元部１０２は、調停者公開鍵apk、調停者復号鍵ask、検証鍵VK、検証可能暗号化署名ω:=(K1,K2,K3,K4,K5,K6,K7,K8,K9,K1',K2',K3',K4',K1^,K2^,K3^,K4^)、平文Mを入力とし、まず受信装置３００による検証処理と同じ処理を行って検証可能暗号化署名ωが正しい暗号化署名であることを検証し、その検証が正しい場合に、σ1:=K1・(K1')-β, σ2:=K2・(K2')-β, σ3:=K3・(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'，およびtagk:=K9を計算し、σ':=(σ1',σ2',σ3',σ4',σ5',σ6',σ7',σ8',tagk)として、σ'を署名として出力する（ステップＳ１８）。復元部１０２は、検証に失敗した場合はσ'を求めない（なお、調停装置１００が受信装置３００に対して検証に失敗したことを表す情報を送信するようにしてもよい）。送信部１０８は、平文Mと復元された署名σ'を受信装置３００に送信する。
【００７４】
なお、ステップＳ１８の処理にて復元された署名σ':=(σ1',σ2',σ3',σ4',σ5',σ6',σ7',σ8',tagk)は、仮に送信装置２００の署名生成部２０２が生成するとした場合のWaters09署名に一致する。仮に署名生成部２０２が生成するとした場合のWaters09署名は、次のとおりである。署名生成部２０２は、署名鍵SKと平文Mを入力として、r1, r2, z1, z2, tagk ←U Zpを選び（ただし、r1, r2, z1, z2, tagkは暗号化検証可能暗号化署名生成装置９００の暗号化検証可能暗号化署名生成部９０１が選択した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を計算して、Waters09署名σ:=(σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,tagk)を出力する。
【００７５】
表１に比較を示す。なおESはencrypted signature、EVESはencrypted verifiably encrypted signatureの略で、それぞれ暗号化署名、暗号化検証可能暗号化署名のことを指す。
【表１】
0005679344.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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005679344.tif 000003
【図２】
0005679344.tif 000004
【図３】
0005679344.tif 000005
【図４】
0005679344.tif 000006
【図５】
0005679344.tif 000007
【図６】
0005679344.tif 000008