(57)【特許請求の範囲】
【請求項１】
システム全体に共通なシステムパラメータを生成するシステムパラメータ生成装置と、情報mから暗号文を生成する暗号化装置と、暗号文を復号する復号装置と、を含む暗号化システムであって、
qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*を表すものとし、前記システムパラメータ生成装置は、セキュリティパラメータλと3n+2を入力として、paramv:=（q,V,GT,A,e）を生成し、乱数r→0∈Fq(n-2)およびη→0∈Fqnを生成し、次式で表される公開鍵pkとマスター秘密鍵mskとを生成し、
pk:=(paramV,B^,B^*),
msk:=(1,0,0,r→0,0n,η→0,0)B^*
B^:=(B1,B2,…,Bn,B3n+2),B^*:=(B*2,…,B*n+1,B*2n+2,…,B*3n+2),
【数２９】
0006000207.tif 000030
ｉ’を1,2,…,3n+2の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子とし、前記暗号化装置は、公開鍵pkを用いて、次式により情報mを暗号化して暗号文(c0,C)を生成し、
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')
乱数σ、η、ｒ'i∈Fq(i=4,5,…,n+1)、個別秘密鍵を
【数３０】
0006000207.tif 000031
とし、前記復号装置は、個別秘密鍵skID(d)を用いて、次式により、暗号文(c0,C)から復号結果m'を得る、
m':=c0(e(C,skID(d)))-1
暗号化システム。
【請求項２】
請求項１の暗号化システムであって、
乱数ｒ'→0∈Fq(n-2)、η'→0∈Fqnとし、前記システムパラメータ生成装置は、msk'=msk+(0,0,0,ｒ'→0,0n,η'→0,0)B^*を計算し、msk'を新たなマスター秘密鍵として更新する、
暗号化システム。
【請求項３】
IDベース暗号化方式を用いた暗号化システム全体に共通なシステムパラメータを生成するシステムパラメータ生成装置であって、
qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*を表すものとし、セキュリティパラメータλと3n+2を入力として、paramv:=（q,V,GT,A,e）を生成し、乱数r→0∈Fq(n-2)およびη→0∈Fqnを生成し、次式で表される公開鍵pkとマスター秘密鍵mskとを生成する、
pk:=(paramV,B^,B^*),
msk:=(1,0,0,r→0,0n,η→0,0)B^*
B^:=(B1,B2,…,Bn,B3n+2),B^*:=(B*2,…,B*n+1,B*2n+2,…,B*3n+2),
【数３１】
0006000207.tif 000032
システムパラメータ生成装置。
【請求項４】
請求項３のシステムパラメータ生成装置であって、
乱数ｒ'→0∈Fq(n-2)、η'→0∈Fqnとし、msk'=msk+(0,0,0,ｒ'→0,0n,η'→0,0)B^*を計算し、msk'を新たなマスター秘密鍵として更新する、
システムパラメータ生成装置。
【請求項５】
IDベース暗号化方式を用いた暗号化システムにおいて、情報mから暗号文を生成する暗号化装置であって、
qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*、paramv:=（q,V,GT,A,e）、乱数r→0∈Fq(n-2)、η→0∈Fqn、pk:=(paramV,B^,B^*),
B^:=(B1,B2,…,Bn,B3n+2),B^*:=(B*2,…,B*n+1,B*2n+2,…,B*3n+2),
【数３２】
0006000207.tif 000033
ｉ’を1,2,…,3n+2の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子とし、公開鍵pkを用いて、次式により情報mを暗号化して暗号文(c0,C)を生成する、
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')
暗号化装置。
【請求項６】
IDベース暗号化方式を用いた暗号化システムにおいて、暗号文を復号する復号装置であって、
qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*、paramv:=（q,V,GT,A,e）、乱数r→0∈Fq(n-2)、η→0∈Fqn、
pk:=(paramV,B^,B^*),
B^:=(B1,B2,…,Bn,B3n+2),B^*:=(B*2,…,B*n+1,B*2n+2,…,B*3n+2),
【数３３】
0006000207.tif 000034
ｉ’を1,2,…,3n+2の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子、暗号文(c0,C)を
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')
とし、乱数σ、η、ｒ'i∈Fq(i=4,5,…,n+1)、個別秘密鍵を
【数３４】
0006000207.tif 000035
とし、個別秘密鍵skID(d)を用いて、次式により、暗号文(c0,C)から復号結果m'を求め、
m':=c0(e(C,skID(d)))-1
乱数σ'∈Fq、ｒ'→0∈Fq(n-2)、η'→0∈Fqn、下付添え字B^*はB*を表すものとし、sk'ID(d):=skID(d)+σ'・ID(d)・B*1-σ'・B*2+(0,0,0,ｒ'→0,0n,η'→0,0)B^*を計算し、sk'ID(d)を新たな個別秘密鍵として更新する、
復号装置。
【請求項７】
システム全体に共通なシステムパラメータを生成するシステムパラメータ生成装置と、情報mから暗号文を生成する暗号化装置と、暗号文を復号する復号装置と、を用いた暗号
化方法であって、
qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*を表すものとし、前記システムパラメータ生成装置が、セキュリティパラメータλと3n+2を入力として、paramv:=（q,V,GT,A,e）を生成し、乱数r→0∈Fq(n-2)およびη→0∈Fqnを生成し、次式で表される公開鍵pkとマスター秘密鍵mskとを生成するステップと、
pk:=(paramV,B^,B^*),
msk:=(1,0,0,r→0,0n,η→0,0)B^*
B^:=(B1,B2,…,Bn,B3n+2),B^*:=(B*2,…,B*n+1,B*2n+2,…,B*3n+2),
【数３５】
0006000207.tif 000036
ｉ’を1,2,…,3n+2の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子とし、前記暗号化装置が、公開鍵pkを用いて、次式により情報mを暗号化して暗号文(c0,C)を生成するステップと、
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')
乱数σ、η、ｒ'i∈Fq(i=4,5,…,n+1)、個別秘密鍵を
【数３６】
0006000207.tif 000037
とし、前記復号装置が、個別秘密鍵skID(d)を用いて、次式により、暗号文(c0,C)から復
号結果m'を得るステップとを含む、
m':=c0(e(C,skID(d)))-1
暗号化方法。
【請求項８】
請求項３または４のシステムパラメータ生成装置、請求項５の暗号化装置、請求項６の復号装置の何れかとして、コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、IDベース暗号化方式を用いた暗号化システム、システムパラメータ生成装置、暗号化装置、復号装置、及びその方法、プログラムに関する。
【背景技術】
【０００２】
従来の公開鍵の安全性は秘密鍵の情報が部分的に漏洩することを想定しないものであった。しかし、近年サイドチャネル攻撃という攻撃方法の進展により、秘密鍵が漏洩した場合の安全性を考慮する必要があると考えられている(非特許文献１参照)。
【０００３】
秘密鍵が漏洩したとしても安全な（通常の）公開鍵暗号方式として、非特許文献２が知られている。非特許文献２の構成は、秘密鍵が漏洩したとしても、CPA（選択平文）攻撃に対する安全性を達成している。
【０００４】
選択的安全性とは秘密鍵の情報が全く漏洩していないときに安全性が保証されることをいい、完全安全性とは秘密鍵の情報の一部が漏洩したとしても安全性が保証されることをいう。よって、完全安全性のほうが、選択的安全性より高い安全性を保障されている。
【０００５】
秘密鍵漏洩耐性とは、秘密鍵の情報が一部漏洩したとしても安全性が保証されることをいい、マスター秘密鍵漏洩耐性とはマスター秘密鍵の一部が漏洩したとしても安全性（暗号の秘匿性）が保証されることであり、個別秘密鍵漏洩耐性とは個別秘密鍵の一部が漏洩したとしても安全性（その個別秘密鍵を用いた暗号の秘匿性）が保証されることである。マスター秘密鍵から個別秘密鍵を生成することができるため、マスター秘密鍵漏洩耐性のほうが、個別秘密鍵漏洩耐性より高い安全性を保障されている。
【０００６】
非特許文献３は、選択的安全性および個別秘密鍵の漏洩耐性をもつIDベース暗号方式を提案した。
【０００７】
非特許文献４は、選択的安全性と個別秘密鍵の漏洩耐性をもつIDベース暗号方式を提案した。
【０００８】
非特許文献５は、完全安全性とマスター秘密鍵漏洩耐性をもつIDベース暗号方式を提案した。しかし、合成数位数に基づくペアリングを利用した方式であるため非効率的である。なお、非特許文献３及び４では、素数位数に基づくペアリングを利用した方式であるため、非特許文献５の方式に比べ、効率的である。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten, "Lest we remember: cold-boot attacks on encryption keys", Commun. ACM, 2009, vol. 52, no.5, pp. 91-98.
【非特許文献２】A. Akavia, S. Goldwasser, and V. Vaikuntanathan, "Simultaneous Hardcore Bits and Cryptography against Memory Attacks", In TCC, Lecture Notes in Computer Science, Springer, 2009, volume 5444, pages 474-495.
【非特許文献３】S. S. M. Chow, Y. Dodis, Y. Rouselakis, and B. Waters. "Practical leakage-resilient identity-based encryption from simple assumptions", In ACM Conference on Computer and Communications Security, ACM, 2010, pages 152-161.
【非特許文献４】Z. Brakerski, Y. T. Kalai, J. Katz, and V. Vaikuntanathan. "Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage", In FOCS, IEEE Computer Society, 2010, pages501-510.
【非特許文献５】A. B. Lewko, Y. Rouselakis, and B. Waters, "Achieving Leakage Resilience through Dual System Encryption", In TCC, Lecture Notes in Computer Science, Springer, 2011, volume 6597, pages 70-88.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来技術は、秘密鍵漏洩耐性をもつIDベース暗号方式は、効率的であるが選択的安全性のみ達成し、マスター秘密鍵漏洩耐性を持たない方式か、完全安全性を達成し、マスター秘密鍵漏洩耐性を持つが、非効率的な方式のどちらかであった。図１は非特許文献３〜５と第一実施形態のIDベース暗号方式の概要を説明するための図である。
【００１１】
本発明は、完全安全性を達成し、秘密鍵漏洩耐性および効率性を同時に達成する暗号化システム、システムパラメータ生成装置、暗号化装置、復号装置、及びその方法、プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、本発明の第一の態様によれば、暗号化システムは、システム全体に共通なシステムパラメータを生成するシステムパラメータ生成装置と、情報mから暗号文を生成する暗号化装置と、暗号文を復号する復号装置と、を含む。qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*を表すものとし、システムパラメータ生成装置は、セキュリティパラメータλと3n+2を入力として、paramv:=（q,V,GT,A,e）を生成し、乱数r→0∈Fq(n-2)およびη→0∈Fqnを生成し、次式で表される公開鍵pkとマスター秘密鍵mskとを生成する。
pk:=(paramV,B^,B^*),
msk:=(1,0,0,r→0,0n,η→0,0)B^*
B^:=(B0,B1,…,Bn,B3n+1),B^*:=(B*1,…,B*n,B*2n+1,…,B*3n+1),
【００１３】
【数１】
0006000207.tif 000002
【００１４】
ｉ’を0,1,…,3n+1の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子とし、暗号化装置は、公開鍵pkを用いて、次式により情報mを暗号化して暗号文(c0,C)を生成する。
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')
乱数σ、η、ｒ'i∈Fq(i=3,4,…,n)、個別秘密鍵を
【００１５】
【数２】
0006000207.tif 000003
【００１６】
とし、復号装置は、個別秘密鍵skID(d)を用いて、次式により、暗号文(c0,C)から復号結果m'を得る。
m':=c0(e(C,skID(d)))-1。
【００１７】
上記の課題を解決するために、本発明の他の態様によれば、システムパラメータ生成装置は、IDベース暗号化方式を用いた暗号化システム全体に共通なシステムパラメータを生成する。qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*を表すものとし、セキュリティパラメータλと3n+2を入力として、paramv:=（q,V,GT,A,e）を生成し、乱数r→0∈Fq(n-2)およびη→0∈Fqnを生成し、次式で表される公開鍵pkとマスター秘密鍵mskとを生成する。
pk:=(paramV,B^,B^*),
msk:=(1,0,0,r→0,0n,η→0,0)B^*
B^:=(B0,B1,…,Bn,B3n+1),B^*:=(B*1,…,B*n,B*2n+1,…,B*3n+1),
【００１８】
【数３】
0006000207.tif 000004
【００１９】
上記の課題を解決するために、本発明の他の態様によれば、暗号化装置は、IDベース暗号化方式を用いた暗号化システムにおいて、情報mから暗号文を生成する。qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*、paramv:=（q,V,GT,A,e）、乱数r→0∈Fq(n-2)、η→0∈Fqn、
pk:=(paramV,B^,B^*),
B^:=(B0,B1,…,Bn,B3n+1),B^*:=(B*1,…,B*n,B*2n+1,…,B*3n+1),
【００２０】
【数４】
0006000207.tif 000005
【００２１】
ｉ’を0,1,…,3n+1の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子とし、公開鍵pkを用いて、次式により情報mを暗号化して暗号文(c0,C)を生成する。
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')。
【００２２】
上記の課題を解決するために、本発明の他の態様によれば、復号装置は、IDベース暗号化方式を用いた暗号化システムにおいて、暗号文を復号する。qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*、paramv:=（q,V,GT,A,e）、乱数r→0∈Fq(n-2)、η→0∈Fqn、
pk:=(paramV,B^,B^*),
B^:=(B0,B1,…,Bn,B3n+1),B^*:=(B*1,…,B*n,B*2n+1,…,B*3n+1),
【００２３】
【数５】
0006000207.tif 000006
【００２４】
ｉ’を0,1,…,3n+1の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子、暗号文(c0,C)を
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')
とし、乱数σ、η、ｒ'i∈Fq(i=3,4,…,n)、個別秘密鍵を
【００２５】
【数６】
0006000207.tif 000007
【００２６】
とし、個別秘密鍵skID(d)を用いて、次式により、暗号文(c0,C)から復号結果m'を求め、
m':=c0(e(C,skID(d)))-1
乱数σ'∈Fq、ｒ'→0∈Fq(n-2)、η'→0∈Fqn、下付添え字B^*はB*を表すものとし、sk'ID(d):=skID(d)+σ'・ID(d)・B*1-σ'・B*2+(0,0,0,ｒ'→0,0n,η'→0,0)B^*を計算し、sk'ID(d)を新たな個別秘密鍵として更新する。
【００２７】
上記の課題を解決するために、本発明の他の態様によれば、暗号化方法は、システム全体に共通なシステムパラメータを生成するシステムパラメータ生成装置と、情報mから暗号文を生成する暗号化装置と、暗号文を復号する復号装置と、を用いる。qを素数、Fqを位数qの有限体、N'を自然数の集合、n∈N',VをFq上の(3n+2)次元ベクトル空間、GTを位数qの巡回群、AをVの標準基底、eをV×V→GTの非退化双線型ペアリング、GL(3n+2,Fq)をFq上の(3n+2)次元一般線形群、下付添え字B^*はB*を表すものとし、システムパラメータ生成装置が、セキュリティパラメータλと3n+2を入力として、paramv:=（q,V,GT,A,e）を生成し、乱数r→0∈Fq(n-2)およびη→0∈Fqnを生成し、次式で表される公開鍵pkとマスター秘密鍵mskとを生成するステップと、
pk:=(paramV,B^,B^*),
msk:=(1,0,0,r→0,0n,η→0,0)B^*
B^:=(B0,B1,…,Bn,B3n+1),B^*:=(B*1,…,B*n,B*2n+1,…,B*3n+1),
【００２８】
【数７】
0006000207.tif 000008
【００２９】
ｉ’を0,1,…,3n+1の何れかの値、乱数ζ、ω、ψ∈Fq、ID(d)を復号側の識別子とし、暗号化装置が、公開鍵pkを用いて、次式により情報mを暗号化して暗号文(c0,C)を生成するステップと、
C:=(ζ,ω,ω・ID(d),0n-2,0n,0n,ψ)B,
c0:=gTζ・m
gT:=e(Bi',B*i')
乱数σ、η、ｒ'i∈Fq(i=3,4,…,n)、個別秘密鍵を
【００３０】
【数８】
0006000207.tif 000009
【００３１】
とし、復号装置が、個別秘密鍵skID(d)を用いて、次式により、暗号文(c0,C)から復号結果m'を得るステップとを含む。
m':=c0(e(C,skID(d)))-1。
【発明の効果】
【００３２】
本発明によれば、DLIN仮定（参考文献１及び参考文献２参照）が成立するならば、完全安全性を達成し、秘密鍵漏洩耐性および効率性を同時に達成することができる。
[参考文献１]T. Okamoto and K. Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption", In CRYPTO, Springer, 2010, volume 6223 of LNCS, pages 191-208.
[参考文献２]T. Okamoto and K. Takashima, "Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption", In EUROCRYPT, Lecture Notes in Computer Science, Springer, 2012, volume 7237, pages 591-608.
【図面の簡単な説明】
【００３３】
【図１】従来技術と第一実施形態の特徴を説明するための図。
【図２】第一実施形態の暗号化システムの配置図。
【図３】第一実施形態の暗号化システムの処理フローを示す図。
【図４】第一実施形態の暗号化システムのシステムパラメータ生成装置の機能ブロック図。
【図５】第一実施形態の暗号化システムの送信装置の機能ブロック図。
【図６】第一実施形態の暗号化システムの受信装置の機能ブロック図。
【発明を実施するための形態】
【００３４】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。以下の説明において、テキスト中で使用する記号「^」「→」等は、本来直前の文字の真上に記載されるべきものであるが、テキスト記法の制限により、当該文字の直後に記載する。式中においてはこれらの記号は本来の位置に記述している。また、ベクトルや行列の各要素単位で行われる処理は、特に断りが無い限り、そのベクトルやその行列の全ての要素に対して適用されるものとする。
【００３５】
＜第一実施形態の概要＞
以下で本明細書で利用する記法を説明する。
【００３６】
λはセキュリティパラメータを表す。ある有限集合Sについて、
【００３７】
【数９】
0006000207.tif 000010
【００３８】
とかいたとき、集合Sから要素rを一様ランダムに選んだことを表す。ある確率的多項式時間アルゴリズムAについて、
【００３９】
【数１０】
0006000207.tif 000011
【００４０】
とかいたとき、アルゴリズムAはxを入力にとり、乱数を用いて動作し、aを出力したことを表す。入力xに対して乱数rを使用して動作し、aを出力することを明示するときはa:=A(x;r)と書くことにする（記号:=は以下を参照）。ある値a,bについて、a:=bと書いたとき、aにbを代入する、またはaをbで定義することを表す。
【００４１】
位数qの有限体をFqと書き、Fq×は、Fq＼{0}を表す。ベクトル記号は有限体Fq上のベクトル表現である。例えばx→は、(x1,x2,…,xn)∈Fqnを表す。2つのベクトルx→=(x1,x2,…,xn)及びv→=(v1,v2,…,vn)に対し、x→・v→及び<x→,v→>は内積
【００４２】
【数１１】
0006000207.tif 000012
【００４３】
を表す。ZTは行列Zの転置を表す。Iｌはｌ×ｌ(ローマ字のエル)の単位行列を表す。X∈Vとかいたとき、Xはベクトル空間Vの元を表す。Bi∈V(i=1,…,n)のとき、span<B1,…,Bn>⊆V(resp.span<x→1,…,x→n>)はB1,…,Bn(resp.x→1,…,x→n)によって生成される部分空間である。なお、span<>は線型結合を表し、resp.は各々処理を行うことを表す。基底B:=(B1,…,BN)とB*:=(B*1,…,B*N)に対し、
【００４４】
【数１２】
0006000207.tif 000013
【００４５】
とする。ベクトルe→jは標準基底ベクトル
【００４６】
【数１３】
0006000207.tif 000014
【００４７】
である。GL(n,Fq)はFq上のn次元一般線形群である。本実施形態は、参考文献１や参考文献２の双対ペアリングベクトル空間を利用する。双対ペアリングベクトル空間、及びそれに関連した関数暗号方式の詳細は、参考文献１や参考文献２等に記載されているため、ここでは説明を省略する。
【００４８】
対称ペアリング群(q,g,G,GT,e)は、素数q、位数qの巡回加法群G、位数qの巡回乗法群G、巡回乗法群Gの生成元g、多項式時間で計算可能な非退化双線型ペアリングe:=G×G→GT、すなわち、e(sg,tg)=e(g,g)stかつe(g,g)≠1で表される。
【００４９】
対称ペアリング群(q,g,G,GT,e)による双対ペアリングベクトル空間（Dual pairing vector spaces、以下「DPVS」ともいう）(q,V,GT,A,e)とは、素数q、Fq上のN次元ベクトル空間
【００５０】
【数１４】
0006000207.tif 000015
【００５１】
位数qの巡回群GT、Vの標準基底A:=(A1,…,AN)ただし、
【００５２】
【数１５】
0006000207.tif 000016
【００５３】
、およびペアリングe:V×V→GTの組である。ペアリングは、
【００５４】
【数１６】
0006000207.tif 000017
【００５５】
である。ただし、X:=(g1,…,gN)∈VおよびY:=(h1,…,hN)∈Vと定義される。これは非退化双線型である。つまり、e(sX,tY)=e(X,Y)stかつ、もしすべてのY∈Vに対しe(X,Y)=1ならばX=0である。すべてのiおよびjに対しe(Ai,Aj)=e(g,g)δ_i,jである。ただし、上付き添え字δ_i,jはδi,jを表し、i=jならδi,j=1、そうでなければδi,j=0である。またe(g,g)≠1である。
【００５６】
DPVS生成アルゴリズムGdpvsは、入力として1λ(λ∈N'、ただし、N'は自然数の集合を表す)とN∈N'とを取り、params'V:=(q,V,GT,A,e)を得る。ここでNはVの次元である。なお、対称ペアリング群(q,g,G,GT,e)は、BMSetup()を使用して構成できる。
【００５７】
双対ペアリングベクトル空間において、双対基底を構成する方法は以下の通りである。最初に
【００５８】
【数１７】
0006000207.tif 000018
【００５９】
を生成し、双対直交基底
【００６０】
【数１８】
0006000207.tif 000019
【００６１】
を生成する。ただし、
【００６２】
【数１９】
0006000207.tif 000020
【００６３】
である。
【００６４】
DPVSの性質により、以下が成り立つ。
(Pairing operation)
DPVSの要素X,Y∈Vについて、
【００６５】
【数２０】
0006000207.tif 000021
【００６６】
が成立する。ただしX:=(x1g,…,xNg)およびY:=(y1g,…,yNg)である。ここでXおよびYは基底A上の係数ベクトルとして表現可能である。つまり、(x1,…,xN)A=(x→)A:=Xおよび(y1,…,yN)A=(y→)A:=Yである。
(Base change)
標準基底Aは一様ランダムな正則行列
【００６７】
【数２１】
0006000207.tif 000022
【００６８】
を用いてVの基底B:=(B1,…,BN)に変換可能である。ただし、
【００６９】
【数２２】
0006000207.tif 000023
【００７０】
である。AはVの基底B*:=(B*1,…,B*N)へも変換可能である。ただし、(θi,j):=(ZT)-1、
【００７１】
【数２３】
0006000207.tif 000024
【００７２】
である。ここで注目すべきは以下が成立していることである。
e(Bi,B*j)=e(g,g)δ_i,j(δi,j=1 if i=j, and δi,j=0 if i≠j),
つまり、BとB*はVの双対直交基底である。ここでX:=x1B1+…+xNBN∈VおよびY:=y1B*1+…+yNB*N∈Vは基底BおよびB*の係数ベクトルとして表現可能である。つまり、(x1,…,xN)B=(x→)B:=X、(y1,…,yN)B^*=(y→)B^*:=Y（ただし、下付添え字B^*はB*を表す）、
【００７３】
【数２４】
0006000207.tif 000025
【００７４】
である。
【００７５】
＜第一実施形態に係る暗号化システム１＞
図２及び図３を用いて、第一実施形態に係る暗号化システム１を説明する。暗号化システム１は、システムパラメータ生成装置１０、Ｃ個の送信装置２０ｃ及びＤ個の受信装置３０ｄを含む。ただし、Ｃ及びＤは１以上の整数であり、ｃ＝１，２，…，Ｃ、ｄ＝１，２，…，Ｄである。暗号化システム１はIDベース暗号方式を用いる。
【００７６】
＜事前処理＞
システムパラメータ生成装置１０は、パラメータ生成部１１、送信部１２、個別秘密鍵生成部１３、更新部１４及び記憶部１５を含む（図４参照）。
【００７７】
パラメータ生成部１１は、システム全体に共通なシステムパラメータを生成する（ｓ１１）。例えば、パラメータ生成部１１は、セキュリティパラメータλ∈N'を受け取り（入力とし）、対称ペアリング群
【００７８】
【数２５】
0006000207.tif 000026
【００７９】
を生成する。さらに、パラメータ生成部１１は、N=3n+2（ただし、n∈N'）を受け取り（入力とし）、双対直交基底
【００８０】
【数２６】
0006000207.tif 000027
【００８１】
を生成する。ただし、
【００８２】
【数２７】
0006000207.tif 000028
【００８３】
である。gT:=e(Bi',B*i')（ただし、下付添え字ｉ’は0,1,…,3n+1の何れかの値である）、B^:=(B0,B1,…,Bn,B3n+1)、B^*:=(B*1,…,B*n,B*2n+1,…,B*3n+1)とする。乱数r→0∈Fq(n-2)およびη→0∈Fqnを生成し、S1:=(1,0,0,r→0,0n,η→0,0)B^*（ただし、下付添え字B^*はB*を表す）を生成する。ここで、公開鍵pk:=(paramV,B^,B^*)として記憶部１５に利用者がアクセス可能に記憶し、マスター秘密鍵msk:=S1として記憶部１５に秘密に管理する。
【００８４】
送信部１２は、生成したシステムパラメータ（公開鍵pk）を利用者に送信する（ｓ１２）。
【００８５】
次に、個別秘密鍵生成部１３は、各受信装置３０ｄの個別秘密鍵skID(d)を生成する（ｓ１３）。
【００８６】
例えば、個別秘密鍵生成部１３は、記憶部１５からマスター秘密鍵mskを取り出し、受信装置３０ｄから送られてきた識別子ID(d)を受け取り、乱数σ、η、ｒ'i∈Fq(i=3,4,…,n)を用いて、次式により、KID(d)を生成する。
【００８７】
【数２８】
0006000207.tif 000029
【００８８】
なお、識別子ID(d)は、復号側の識別子であればよく、名前やメールアドレスを含む復号する利用者の識別子でもよいし、macアドレスやスマートフォンの電話番号等の復号する受信装置の識別子等でもよい。
【００８９】
送信部１２は、生成した個別秘密鍵skID(d):=KID(d)を受信装置３０ｄに送信する（ｓ１４）。
【００９０】
＜暗号化処理＞
送信装置２０ｃは、乱数生成部２１と暗号化部２２と送信部２３とを含む（図５参照）。送信装置２０ｃは、パラメータ生成装置１０から公開鍵pkを受信し、ある受信装置３０ｄ'の識別子ID(d')と情報mとを入力とし、情報mの暗号文を生成し、出力する。なお、ｄ’は１，２，…，Ｄの何れかであり、送信装置のことを暗号化処理を行うという意味で、暗号化装置ともいう。
【００９１】
乱数生成部２１は、乱数を生成し（ｓ２１）、暗号化部２２に出力する。
【００９２】
暗号化部２２は、生成された乱数を受け取り、暗号文を生成する（ｓ２２）。
【００９３】
例えば、暗号文の生成については、公開鍵pkを用いて、情報mを暗号化するために、乱数ζ、ω、ψ∈Fqを選び、C:=(ζ,ω,ω・ID(d'),0n-2,0n,0n,ψ)Bおよびc0:=gTζ・mを生成し、暗号文を(c0,C)とする。
【００９４】
送信部２３は、生成した暗号文(c0,C)を受信装置３０ｄ’へ送信する（ｓ２３）。
【００９５】
＜復号処理＞
受信装置３０ｄは、記憶部３１と復号部３２と更新部３３とを含む（図６参照）。受信装置３０ｄは、個別秘密鍵skID(d)を用いて、暗号文(c0,C)を復号して、暗号文(c0,C)から復号結果m'を得る。
【００９６】
例えば、受信装置３０ｄは、送信装置２０ｃからの暗号文(c0,C)を受信し、記憶部３１に記憶する（ｓ３１）。
【００９７】
受信装置３０ｄは、利用に先立ちシステムパラメータ生成装置１０から個別秘密鍵skID(d)を受信し、記憶部３１に秘密に記憶しておく。
【００９８】
復号部３２は、暗号文(c0,C)を受信した後に、記憶部３１から個別秘密鍵skID(d)を取り出し、個別秘密鍵skID(d)を用いて暗号文(c0,C)を復号する（ｓ３２）。例えば、復号方法については、復号部３２は、暗号文(c0,C)および個別秘密鍵skID(d)を入力とし、m':=c0(e(C,skID(d)))-1を計算して、平文（復号結果）として出力する。なお、受信装置のことを復号処理を行うという意味で、復号装置ともいう。
【００９９】
＜更新処理＞
システムパラメータ生成装置１０の更新部１４は、マスター秘密鍵mskを更新する。マスター秘密鍵mskに関する情報（マスター秘密鍵mskの一部）が漏洩した際には、更新部１４は、乱数ｒ'→0∈Fq(n-2)、η'→0∈Fqnを生成し、msk'=msk+(0,0,0,ｒ'→0,0n,η'→0,0)B^*を計算し、新たなマスター秘密鍵をmsk'とし、記憶部１５に記憶する。なお、更新部１４は、古いマスター秘密鍵mskを記憶部１５から消去する。
【０１００】
このような構成により、マスター秘密鍵mskを更新し、完全安全性を達成し、マスター秘密鍵漏洩耐性を達成することができる。なお、マスター秘密鍵を更新しても、公開鍵や個別秘密鍵を更新する必要はなく、効率的な運用が可能となる。
【０１０１】
また、受信装置３０ｄの更新部３３は、個別秘密鍵skID(d)を更新する。個別秘密鍵skID(d)に関する情報（個別秘密鍵skID(d)の一部）が漏洩した際には、乱数σ'∈Fq、ｒ'→0∈Fq(n-2)、η'→0∈Fqnを生成し、sk'ID(d):=skID(d)+σ'・ID(d)・B*1-σ'・B*2+(0,0,0,ｒ'→0,0n,η'→0,0)B^*を計算し、新たな個別秘密鍵をsk'ID(d)とする。更新部３３は、古い個別秘密鍵sk'ID(d)は消去する。
【０１０２】
このような構成により、個別秘密鍵sk'ID(d)を更新し、完全安全性を達成し、個別秘密鍵漏洩耐性を達成することができる。なお、個別秘密鍵を更新しても、公開鍵や他の受信装置の個別秘密鍵やマスター秘密鍵を更新する必要はなく、効率的な運用が可能となる。また、受信装置３０ｄ側で、個別秘密鍵を更新できるため、システムパラメータ生成装置１０の処理を軽減することができる。
【０１０３】
＜効果＞
このような構成により、完全安全性を達成し、秘密鍵漏洩耐性と効率性を同時に達成することができる。
【０１０４】
＜変形例＞
送信装置は、暗号化処理機能に加え、復号処理機能を備える構成としてもよい。同様に受信装置は、復号処理機能に加え、暗号化処理機能を備える構成としてもよい。また、システムパラメータ生成装置は、事前処理機能に加え、暗号化処理機能や復号処理機能を備える構成としてもよい。
【０１０５】
個別秘密鍵生成部は、必ずしもシステムパラメータ生成装置内に設ける必要はなく、受信装置内に設けてもよい。その場合、システムパラメータ生成装置は生成した秘密鍵を受信装置に秘密に送信する。
【０１０６】
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【０１０７】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１０８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【０１１０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１１】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0006000207.tif 000038
【図２】
0006000207.tif 000039
【図３】
0006000207.tif 000040
【図４】
0006000207.tif 000041
【図５】
0006000207.tif 000042
【図６】
0006000207.tif 000043