(57)【要約】      （修正有）【課題】効率が良い署名システム、方法、生成、検証装置を提供する。【解決手段】秘密鍵SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)、公開鍵VK=(N,G,g,X=gx,Y=gy,g3,gw1,…,gwn)を生成する鍵生成装置と、乱数r~,z1′,…,zn′∈ZNを生成する第二乱数生成部と、署名対象のメッセージをmとし、σ1=(Kz1)r~(gr~z1′),…,σn=(Kzn)r~(gr~zn′),σn+1=(Kr)r~,σn+2=(Ky)r~,σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)とし、SKを用いてmに対する署名をσ=(σ1,…,σn+3)を生成する署名生成部と、を含む署名生成装置と、m≠0かつ２つの式e(Y,σn+1)=e(g,σn+2),e(X,σn+1)e(X,σn+2)mΠi=1ne(gwi,σi)m=e(g,σn+3)の成立を判定する。【選択図】図１
2014230254.tif 000002
【特許請求の範囲】
【請求項１】
p1,p2,p3を素数とし、位数N=p1p2p3の群をG,GTとし、e:G×G→GTを双線形写像として、乱数g∈Gp1,g2∈Gp2,g3,R31,…,R3n+4∈Gp3と、乱数x,y,xe,ye,r^,r^′,z1,…,zn,w1,…,wn∈ZNとを生成する第一乱数生成部と、Kz1=gz1R31，…，Kzn=gznR3n，Kr=gr^g2r^′R3n+1，Kx=gr^xg2r^′xeR3n+2,Ky=gr^yg2r^′yeR3n+3，Kxy=gr^xyg2r^′xeyeR3n+4Πi=1ng-ziwiとして、秘密鍵SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)を生成する秘密鍵生成部と、公開鍵VK=(N,G,g,X=gx,Y=gy,g3,gw1,…,gwn)を生成する公開鍵生成部と、を含む鍵生成装置と、
乱数r~,z1′,…,zn′∈ZNを生成する第二乱数生成部と、署名の対象となるメッセージをmとし、σ1=(Kz1)r~(gr~z1′),…,σn=(Kzn)r~(gr~zn′),σn+1=(Kr)r~,σn+2=(Ky)r~,σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)として、上記秘密鍵SKを用いてメッセージmに対する署名をσ=(σ1,…,σn+3)を生成する署名生成部と、を含む署名生成装置と、
m≠0かつ２つの式e(Y,σn+1)=e(g,σn+2),e(X,σn+1)e(X,σn+2)mΠi=1ne(gwi,σi)m=e(g,σn+3)が成立するかどうか判定し、m≠0かつ上記２つの式が成立する場合には上記署名σを受理する判定部を含む署名検証装置と、
を含む署名システム。
【請求項２】
鍵生成装置の第一乱数生成部が、p1,p2,p3を素数とし、位数N=p1p2p3の群をG,GTとし、e:G×G→GTを双線形写像として、乱数g∈Gp1,g2∈Gp2,g3,R31,…,R3n+4∈Gp3と、乱数x,y,xe,ye,r^,r^′,z1,…,zn,w1,…,wn∈ZNとを生成する第一乱数生成ステップと、
鍵生成装置の秘密鍵生成部が、Kz1=gz1R31，…，Kzn=gznR3n，Kr=gr^g2r^′R3n+1，Kx=gr^xg2r^′xeR3n+2,Ky=gr^yg2r^′yeR3n+3，Kxy=gr^xyg2r^′xeyeR3n+4Πi=1ng-ziwiとして、秘密鍵SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)を生成する秘密鍵生成ステップと、
鍵生成装置の公開鍵生成部が、公開鍵VK=(N,G,g,X=gx,Y=gy,g3,gw1,…,gwn)を生成する公開鍵生成ステップと、
署名生成装置の第二乱数生成部が、署名生成部が、乱数r~,z1′,…,zn′∈ZNを生成する第二乱数生成ステップと、
署名生成装置の署名生成部が、署名の対象となるメッセージをmとし、σ1=(Kz1)r~(gr~z1′),…,σn=(Kzn)r~(gr~z′n),σn+1=(Kr)r~,σn+2=(Ky)r~,σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)として、上記秘密鍵SKを用いてメッセージmに対する署名をσ=(σ1,…,σn+3)を生成する署名生成ステップと、
署名検証装置の判定部が、m≠0かつ２つの式e(Y,σn+1)=e(g,σn+2),e(X,σn+1)e(X,σn+2)mΠi=1ne(gwi,σi)m=e(g,σn+3)が成立するかどうか判定し、m≠0かつ上記２つの式が成立する場合には上記署名σを受理する判定ステップと、
を含む署名方法。
【請求項３】
p1,p2,p3を素数とし、位数N=p1p2p3の群をG,GTとし、e:G×G→GTを双線形写像とし、g∈Gp1,g2∈Gp2,g3,R31,…,R3n+4∈Gp3と、x,y,xe,ye,r^,r^′,z1,…,zn,w1,…,wn∈ZNとを乱数とし、Kz1=gz1R31，…，Kzn=gznR3n，Kr=gr^g2r^′R3n+1，Kx=gr^xg2r^′xeR3n+2,Ky=gr^yg2r^′yeR3n+3，Kxy=gr^xyg2r^′xeyeR3n+4Πi=1ng-ziwiとし、SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)を秘密鍵とし、VK=(N,G,g,X=gx,Y=gy,g3,gw1,…,gwn)を公開鍵として、
乱数r~,z1′,…,zn′∈ZNを生成する第二乱数生成部と、
署名の対象となるメッセージをmとし、σ1=(Kz1)r~(gr~z1′),…,σn=(Kzn)r~(gr~z′n),σn+1=(Kr)r~,σn+2=(Ky)r~,σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)として、上記秘密鍵SKを用いてメッセージmに対する署名をσ=(σ1,…,σn+3)を生成する署名生成部と、
を含む署名生成装置。
【請求項４】
p1,p2,p3を素数とし、位数N=p1p2p3の群をG,GTとし、e:G×G→GTを双線形写像とし、g∈Gp1,g2∈Gp2,g3,R31,…,R3n+4∈Gp3と、x,y,xe,ye,r^,r^′,z1,…,zn,w1,…,wn∈ZNとを乱数とし、Kz1=gz1R31，…，Kzn=gznR3n，Kr=gr^g2r^′R3n+1，Kx=gr^xg2r^′xeR3n+2,Ky=gr^yg2r^′yeR3n+3，Kxy=gr^xyg2r^′xeyeR3n+4Πi=1ng-ziwiとし、SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)を秘密鍵とし、VK=(N,G,g,X=gx,Y=gy,g3,gw1,…,gwn)を公開鍵とし、r~,z1′,…,zn′∈ZNを乱数とし、署名の対象となるメッセージをmとし、σ1=(Kz1)r~(gr~z1′),…,σn=(Kzn)r~(gr~zn′),σn+1=(Kr)r~,σn+2=(Ky)r~,σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)とし、σ=(σ1,…,σn+3)をメッセージmに対する署名として、
m≠0かつ２つの式e(Y,σn+1)=e(g,σn+2),e(X,σn+1)e(X,σn+2)mΠi=1ne(gwi,σi)m=e(g,σn+3)が成立するかどうか判定し、m≠0かつ上記２つの式が成立する場合には上記署名σを受理する判定部、
を含む署名検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、電子署名技術に特に関する。
【背景技術】
【０００２】
従来の公開鍵の安全性は秘密鍵の情報が部分的に漏洩することを想定しないものであったが、近年サイドチャネル攻撃という攻撃方法の進展により、秘密鍵が漏洩した場合の安全性を考慮する必要があると考えられている（例えば、非特許文献１参照。）。
【０００３】
秘密鍵が漏洩したとしても安全な署名方式はKatz,Vaikuntanathanらによって初めて構成された（例えば、非特許文献２参照。）。
【０００４】
また、Dodis,Haralambiev,L opez-Alt,Wichsらは鍵漏洩耐性をもちかつ秘密鍵を更新可能な方式を提案した（例えば、非特許文献３参照。）。
【０００５】
また、Malkin,Teranishi,Vahlis,Yungらは秘密鍵漏洩耐性に加え署名生成時の乱数が漏洩しても安全な方式を提案した（例えば、非特許文献４参照。）。
【０００６】
また、Boyle,Segev,WichsらはMalkinらと同様、秘密鍵漏洩耐性に加え署名生成時の乱数が漏洩しても安全な方式を提案した（例えば、非特許文献５参照。）。
【０００７】
さらに、Lewko,Rouselakis,Watersらはマスター秘密鍵漏洩耐性をもつID ベース暗号を構成したので、その方式から秘密鍵漏洩耐性をもつ署名を得ることができる（例えば、非特許文献６参照。）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】J.A.Halderman, S.D.Schoen, N.Heninger, W.Clarkson, W.Paul, J.A.Calan-drino, A.J.Feldman, J.Appelbaum, and E.W.Felten. “Lest we remember: cold-boot attacks on encryption keys”, Commun. ACM, 52(5), 2009.
【非特許文献２】J.Katz and V.Vaikuntanathan, “Signature Schemes with Bounded Leakage Resilience”, In ASIACRYPT, volume 5912 of Lecture Notes in Computer Science, pages 703-720. Springer, 2009.
【非特許文献３】Y.Dodis, K.Haralambiev, A.Lopez-Alt, and D.Wichs, “Efficient Public-Key Cryptogra-phy in the Presence of Key Leakage”, In ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 613-631. Springer, 2010.
【非特許文献４】T.Malkin, I.Teranishi, Y.Vahlis, and M.Yung. “Signatures Resilient to Continual Leakage on Memory and Computation”, In TCC, volume 6597 of Lecture Notes in Computer Science, pages 89-106. Springer, 2011.
【非特許文献５】E.Boyle, G.Segev, and D.Wichs, “Fully Leakage-Resilient Signatures”, In EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 89-108, Springer, 2011.
【非特許文献６】A.B.Lewko, Y.Rouselakis, and B.Waters, “Achieving Leakage Resilience through Dual System Encryption”, In TCC, volume 6597 of Lecture Notes in Computer Science, pages 70-88. Springer, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、これまでに提案されてきた秘密鍵漏洩耐性を持つ署名方式は全て、非対話ゼロ知識証明を利用するか、マスター秘密鍵漏洩耐性をもつIDベース暗号を利用して構成されていたため効率が悪かった。
【００１０】
非特許文献２から６のそれぞれに記載された署名方式が、非ゼロ知識証明を利用するかどうか、IDベース暗号を利用しているかどうかを図３に示す。なお、非特許文献２から６のそれぞれに記載された署名方式が、鍵更新を行うか、乱数漏洩耐性を持つかどうかについても図３に示す。
【００１１】
この発明は、従来よりも効率が良い署名システム及び方法、署名生成装置並びに署名検証装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
この発明の一態様による署名システムは、p1,p2,p3を素数とし、位数N=p1p2p3の群をG,GTとし、e:G×G→GTを双線形写像として、乱数g∈Gp1,g2∈Gp2,g3,R31,…,R3n+4∈Gp3と、乱数x,y,xe,ye,r^,r^′,z1,…,zn,w1,…,wn∈ZNとを生成する第一乱数生成部と、Kz1=gz1R31，…，Kzn=gznR3n，Kr=gr^g2r^′R3n+1，Kx=gr^xg2r^′xeR3n+2,Ky=gr^yg2r^′yeR3n+3，Kxy=gr^xyg2r^′xeyeR3n+4Πi=1ng-ziwiとして、秘密鍵SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)を生成する秘密鍵生成部と、公開鍵VK=(N,G,g,X=gx,Y=gy,g3,gw1,…,gwn)を生成する公開鍵生成部と、を含む鍵生成装置と、乱数r~,z1′,…,zn′∈ZNを生成する第二乱数生成部と、署名の対象となるメッセージをmとし、σ1=(Kz1)r~(gr~z1′),…,σn=(Kzn)r~(gr~zn′),σn+1=(Kr)r~,σn+2=(Ky)r~,σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)として、秘密鍵SKを用いてメッセージmに対する署名をσ=(σ1,…,σn+3)を生成する署名生成部と、を含む署名生成装置と、m≠0かつ２つの式e(Y,σn+1)=e(g,σn+2),e(X,σn+1)e(X,σn+2)mΠi=1ne(gwi,σi)m=e(g,σn+3)が成立するかどうか判定し、m≠0かつ２つの式が成立する場合には署名σを受理する判定部を含む署名検証装置と、を含む。
【発明の効果】
【００１３】
秘密鍵漏洩耐性を持つ署名方式を、従来よりも効率良く実現することができる。
【図面の簡単な説明】
【００１４】
【図１】署名システムの例を説明するためのブロック図。
【図２】署名方法の例を説明するためのフローチャート。
【図３】背景技術を説明するための図。
【発明を実施するための形態】
【００１５】
以下、図面を参照して、署名システム及び方法、署名生成装置並びに署名検証装置の実施形態を説明する。
【００１６】
署名システムは、図１に示すように、鍵生成装置１、署名生成装置２及び署名検証装置３を例えば備えている。図１の例では、鍵生成装置１は、署名生成装置２の内に備えられている。
【００１７】
＜ステップＳ１、図２＞
鍵生成装置１の第一乱数生成部１１は、乱数g∈Gp1,g2∈Gp2,g3,R31,…,R3n+4∈Gp3と、乱数x,y,xe,ye,r^,r^′,z1,…,zn,w1,…,wn∈ZNとを生成する（ステップＳ１）。ここで、p1,p2,p3は所定の素数であり、G,GTは位数N=p1p2p3の群であるとする。Gp1,Gp2,Gp3は、それぞれ位数p1,p2,p3の群であるとする。ZNは、Nに関する剰余類群である。
【００１８】
ただし、λ1=logp1,λ2=logp2,λ3=logp3としたとき、logN=λ1+λ2+λ3であるとする。ここで、λ2=λ,λ1=c1λ,λ3=c3λとする。λは、セキュリティパラメータであり、任意の正の自然数である。c1及びc3は定数であり、任意の正の自然数である。言い換えれば、c1及びc3は、正の自然数であれば何でもよい。
【００１９】
よって、セキュリティパラメータλは、群Gp2の位数p2のビット数を表し、他の群の位数p1,p3のビット数に関してはp2のビット数の定数倍ということになる。
【００２０】
＜ステップＳ２＞
鍵生成装置１の秘密鍵生成部１２は、Kz1=gz1R31，…，Kzn=gznR3n，Kr=gr^g2r^′R3n+1，Kx=gr^xg2r^′xeR3n+2,Ky=gr^yg2r^′yeR3n+3，Kxy=gr^xyg2r^′xeyeR3n+4Πi=1ng-ziwiとして、第一乱数生成部１１により生成された乱数を用いて、秘密鍵SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)を生成する（ステップＳ２）。生成された秘密鍵SKは、署名生成装置２の記憶部２３に記憶される。
【００２１】
ここで、Kz1=gz1R31の中のgの上付き添え字の「z1」は、z1を意味する。Kzn=gznR3nの中のgの上付き添え字の「zn」は、znを意味する。Kx=gr^xg2r^′xeの中のg2の上付き添え字の「r^′xe」は、r^′xeを意味する。Ky=gr^yg2r^′yeR3n+3の中のg2の上付き添え字の「r^′ye」は、r^′yeを意味する。Kxy=gr^xyg2r^′xeyeR3n+4Πi=1ng-ziwiの中のg2の上付き添え字の「r^′xeye」はr^′xeyeを意味し、gの上付き添え字の「-ziwi」は-ziwiを意味する。
【００２２】
＜ステップＳ３＞
鍵生成装置１の公開鍵生成部１３は、第一乱数生成部１１により生成された乱数を用いて、公開鍵VK=(N,G,g,X=gx,Y=gy,g3,gw1,…,gwn)を生成する（ステップＳ３）。生成された公開鍵VKは、鍵生成装置１の外部に公開される。この例では、生成された公開鍵VKは、署名生成装置２の記憶部２３に記憶され、また、署名検証装置３に送信され記憶部３２に記憶される。
【００２３】
ここで、gの上付き添え字の「w1」はw1を意味する。gの上付き添え字の「wn」はwnを意味する。
【００２４】
＜ステップＳ４＞
署名生成装置２の第二乱数生成部２１は、乱数r~,z1′,…,zn′∈ZNを生成する（ステップＳ４）。生成された乱数r~,z1′,…,zn′は、署名生成部２２に送信される。
【００２５】
＜ステップＳ５＞
署名生成装置２の署名生成部２２は、署名の対象となるメッセージをmとし、σ1=(Kz1)r~(gr~z1′),…,σn=(Kzn)r~(gr~zn′),σn+1=(Kr)r~,σn+2=(Ky)r~,σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)として、秘密鍵SKを用いてメッセージmに対する署名をσ=(σ1,…,σn+3)を生成する（ステップＳ５）。生成された署名σは、メッセージmと共に、署名検証装置３に送信される。
【００２６】
ここで、σ1=(Kz1)r~(gr~z1′)の中のgの上付き添え字の「r~z1′」は、r~z1′を意味する。σn=(Kzn)r~(gr~zn′)の中のgの上付き添え字の「r~zn′」は、r~zn′を意味する。σn+3=(Kx)r~(Kxy)r~m(Πi=1n(gwi)r~mzi)の中のgの上付き添え字「wi」はgの上付きのwiを意味し、(gwi)の上付き添え字の「r~mzi」はr~mziを意味する。
【００２７】
＜ステップＳ６＞
署名検証装置３の判定部３１は、署名生成装置２から受信した署名σ及びメッセージmと、記憶部３２から読み込んだ公開鍵VKとを用いて、m≠0かつ２つの式e(Y,σn+1)=e(g,σn+2),e(X,σn+1)e(X,σn+2)mΠi=1ne(gwi,σi)m=e(g,σn+3)が成立するかどうか判定し、m≠0かつ上記２つの式が成立する場合には署名σを受理する（ステップＳ６）。２つ目の式の中のgの上付き添え字の「wi」は、wiを意味する。一方、m=0又は上記２つの式の何れかが成立しない場合には、署名σを受理しない。
【００２８】
G,GTを位数N=p1p2p3の群として、e:G×G→GTは双線形写像である。
【００２９】
署名検証装置３は、署名σを受理する場合には、その署名σを受理したことを示す情報、例えば「１」を出力してもよい。また、署名検証装置３は、署名σを受理しない場合には、その署名σを受理しないことを示す情報、例えば「０」を出力してもよい。
【００３０】
以上に説明した署名システム及び方法は、非対話ゼロ知識証明を用いておらず、かつ、IDベース暗号を利用していない。
【００３１】
また、この署名システム及び方法は、いわゆる合成数位数群上の部分群識別仮定が成立するならば、秘密鍵漏洩耐性を持つ安全な署名方式である。この署名システム及び方法では、秘密鍵SK=(Kz1,…,Kzn,Kr,Kx,Ky,Kxy)が多数の数値Kz1,…,Kzn,Kr,Kx,Ky,Kxyにより構成されており、また、これらの数値Kz1,…,Kzn,Kr,Kx,Ky,Kxyは、ZN等の剰余類群ではない群Gp1,Gp2,Gp3の要素とされているためである。この署名システム及び方法が、いわゆる合成数位数群上の部分群識別仮定が成立するならば、秘密鍵漏洩耐性を持つ安全な署名方式であることの証明の詳細については、参考文献１を参照のこと。
〔参考文献１〕小関義博，西巻陵，藤崎英一郎，田中圭介，「秘密鍵の漏洩に対して安全なデュアルフォーム署名」，SCIS2013
【００３２】
［変形例］
図１の例では、鍵生成装置１は、署名生成装置２の内に備えられているが、鍵生成装置１は、署名生成装置２の外に設けられていてもよい。この場合、鍵生成装置１は、上記と同様に秘密鍵SK及び公開鍵VKを生成し、秘密鍵SKを秘密裏に署名生成装置２に送信し、公開鍵VKを署名生成装置２及び署名検証装置３に送信する。
【００３３】
上記装置及び方法において説明した処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００３４】
また、署名システムの各装置における各処理をコンピュータによって実現する場合、その各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００３５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３６】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００３７】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００３８】
１      鍵生成装置
１１    第一乱数生成部
１２    秘密鍵生成部
１３    公開鍵生成部
２      署名生成装置
２１    第二乱数生成部
２２    署名生成部
２３    記憶部
３      署名検証装置
３１    判定部
３２    記憶部
【図１】
2014230254.tif 000003
【図２】
2014230254.tif 000004
【図３】
2014230254.tif 000005