【課題】内積述語暗号の機能を有する再暗号化方式を提供する。
【解決手段】W(0,1)=(h(1)^a(1))^r,Θ(0,1)=(h(1)^b(1))^s,Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1),Λ(0,1)=h(1)^ζを含む暗号文ct(0,1)から、W’=W(0,1)・(h(1)^a(1))^r’,Θ’=Θ(0,1)・(h(1)^b(1))^s’,Y’=Y(0,1)・h(1)^r’+s’,U’=U(0,1)+(REV^→)_B(1),Λ’=Λ(0,1)・h(1)^ζ’,Ψ₁=e₁(W’,Z₁),Ψ₂=e₁(Θ’,Z₂),Ψ₃=e₁(Y’,Z₃),Ω₁=e_n+μ(U’,k^*),Ω₂=e₁(Λ’,k₀)を生成し、E(1,2)=Ψ₁^y,F(1,2)=Ψ₂^y,G(1,2)=Ψ₃^y・Ω₁^y’,Z(1,2)=Z₃^y,H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)を生成する。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化技術に関し、特に再暗号化可能な暗号化技術に関する。
【背景技術】
【０００２】
従来の再暗号化方式では、プロキシ装置が持っている再暗号化鍵を利用すれば、プロキシ装置は、無条件で、第１復号装置で復号可能な暗号文を第２復号装置で復号可能な暗号文に変換できる（例えば、非特許文献１，２参照）。
【０００３】
プロキシ再暗号化機能を有さない（内積）述語暗号や関数暗号として、非特許文献３，４に記載された内積述語暗号や、非特許文献５に記載された関数暗号などがある。
【先行技術文献】
【特許文献】
【０００４】
【非特許文献１】S. Hohenberger, G. N. Rothblum, A. Shelat, and V. Vaikuntanathan, “Securely Obfuscating Re-encryption,” In TCC, volume 4392 of Lecture Notes in Computer Science, pages 233-252, Springer, 2007.
【非特許文献２】N. Chandran, M. Chase, and V. Vaikuntanathan, “Collusion Resistant Obfuscation and Functional Re-encryption,” [online], 22 Jun 2011, [平成２３年１０月２７日検索]、インターネット＜http://eprint.iacr.org/2011/337.＞
【非特許文献３】J. Katz, A. Sahai, and B. Waters, “Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products,” In EUROCRYPT, volume 4965 of Lecture Notes in Computer Science, pages 146-162, Springer, 2008.
【非特許文献４】A. B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters, “Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption,” In EUROCRYPT, volume 6110 of Lecture Notes in Computer Science, pages 62-91, Springer, 2010.
【非特許文献５】T. Okamoto and K. Takashima, “Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption,” In CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 191-208, Springer, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、内積述語暗号の機能を有する再暗号化方式は存在しない。本発明はこのような点に鑑みてなされたものであり、内積述語暗号の機能を有する再暗号化方式を提供する。
【課題を解決するための手段】
【０００６】
本発明では、G, G_Tが巡回群であり、gが巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、基底Bと基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、第２復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、第２復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して巡回群G_Tの元を得る双線形写像である。
【０００７】
暗号化装置は、r, s, ζ, ω∈F_qを選択し、第１復号装置の公開鍵(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))とn次元ベクトルx^→=(x_ι(1),...,x_ι(n))∈F_qⁿとを用い、メッセージm∈Gの第１暗号文ct(0,1)を生成する。ただし、第１暗号文ct(0,1)がW(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含み、CV^→がn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}がζであり、CV_ι(n+1),...,CV_ι(Γ)からCV_κを除いた要素からなるベクトルとRV_ι(n+1),...,RV_ι(Γ)からRV_κを除いた要素からなるベクトルとの内積が0である。
【０００８】
再暗号化装置は、r’, s’, ζ’∈F_qを選択し、W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’を得、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)を得、y, y’∈F_q^×に対するE(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)を生成する。REV^→はn+μ次元ベクトルREV^→=(REV_ι(1),...,REV_ι(n+μ))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(n+μ)}がζ’であり、REV_κを除くREV_ι(1),...,REV_ι(n+μ)が0∈F_qである。
【０００９】
第２復号装置は、e₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2) ^1/b(2)}を満たすm’∈Gを復号値として得る。
【発明の効果】
【００１０】
本発明では、内積述語暗号の機能を有する再暗号化方式を実現できる。
【図面の簡単な説明】
【００１１】
【図１】図１は実施形態のセキュリティシステムの全体構成を説明するための図である。
【図２】図２は実施形態の暗号化装置の構成を説明するための図である。
【図３】図３は実施形態の復号装置の構成を説明するための図である。
【図４】図４は実施形態の復号装置の構成を説明するための図である。
【図５】図５は実施形態の難読化装置の構成を説明するための図である。
【図６】図６は実施形態の再暗号化装置の構成を説明するための図である。
【図７】図７Ａ及び７Ｂは復号装置の秘密鍵及び公開鍵の生成方法を説明するためのフローチャートであり、図７Ｃは再暗号化鍵の生成方法を説明するためのフローチャートである。
【図８】図８は実施形態の暗号化方法を説明するためのフローチャートである。
【図９】図９は実施形態の再暗号化方法を説明するためのフローチャートである。
【図１０】図１０Ａ及び１０Ｂは実施形態の復号方法を説明するためのフローチャートである。
【発明を実施するための形態】
【００１２】
実施形態を説明する。
〔定義〕
基本的な用語・表記を定義する。
secはセキュリティパラメータを表す１以上の整数である。qはsecビットの素数であり、G, G_Tは位数qの巡回群（巡回乗法群）であり、g∈Gは巡回群Gの生成元であり、g_T∈G_Tは巡回群G_Tの生成元である。F_qは位数qの有限体であり、F_q^×=F_q＼{0}は有限体F_qから零元（加法単位元）0を除いた集合である。
【００１３】
実施形態では、原則、巡回群G, G_Tでの演算が乗法群として乗法的に表記される。ただし、記法の便宜上の例外として、巡回群Gの元を要素とするベクトル単位の演算（結果）、及び、巡回群Gの元を要素とする行列単位の演算（結果）のみが加法的に表現（以下「便宜的加法表現」）される。加法的に表現されたとしても、このようなベクトルや行列の各要素が巡回群Gの元（巡回乗法群の元）であることに注意されたい。
【００１４】
nが１以上の整数であり、x^→=(x₁,...,x_n)∈F_qⁿがn個の有限体F_qの元x_i∈F_qを要素とするn次元ベクトル（例えば属性ベクトル）であり、v^→=(v₁,...,v_n)∈F_qⁿがn個の有限体F_qの元v_i∈F_qを要素とするn次元ベクトル（例えば述語ベクトル）である。２つのベクトルx^→，v^→に対するx^→・v^→は、内積x^→・v^→=Σ_i=1ⁿx_i・v_i∈F_qを表す。1^→は単位ベクトル1^→=(1,...,1)を表す。I_Nは有限体F_qの元を要素に持つN行N列の単位行列を表す。
【００１５】
e_ξ（ξは１以上の整数）は、任意の直積群G^ξ×G^ξの元に対して巡回群G_Tの元を得る双線形写像（bilinear map）である。
e_ξ：G^ξ×G^ξ→G_T …(1)
双線形写像e_ξは以下の性質を満たす。
［双線形性］双線形写像e_ξは、任意のλ₁，λ₂∈G^ξ及びν1，ν2∈F_qについて以下の関係を満たす。
e(λ₁^ν1, λ₂^ν2)=e(λ₁, λ₂)^ν1・ν2 …(2)
［非退化］e_ξ(λ₁, λ₂)≠1∈G_Tを満たすλ₁，λ₂∈G^ξが存在する。すべてのλ₁∈G^ξに対してe_ξ(λ₁, λ₂)=1∈G_Tであるならλ₂=0^ξ∈G^ξである。e_ξ(g, g)=g_T∈G_Tを満たす。
［計算可能性］任意のλ₁，λ₂∈G^ξに対してe(λ₁, λ₂)の効率的な（つまり多項式時間での）計算が可能である。
【００１６】
本形態の双線形写像e_ξは、任意のξ，γ=(γ₁,...,γ_ξ)∈G^ξ，γ^*=(γ₁^*,...,γ_ξ^*)∈G^ξ，γ_ι∈G及びγ_ι^*∈G（ι=1,...,ξ）について、以下のように構成される。
e_ξ(γ, γ^*)=Π_ι=1^ξe₁(γ_ι, γ_ι^*) …(3)
双線形写像e₁の具体例は、有限体F_q上で定義された楕円曲線上の２点に対して定義されるWeilペアリングやTateペアリングなどのペアリングである。したがって、例えば公知のペアリングを用いることで任意のξに対する双線形写像e_ξを定義できる。ペアリングなどの双線形写像についての詳細は、例えば、参考文献１「D. Boneh and M. K. Franklin, “Identity-Based Encryption from the Weil Pairing,” In CRYPTO’01, volume 2139 of Lecture Notes in Computer Science, pages 213-229, Springer, 2001.」や、参考文献２「黒澤馨著，“現代暗号への招待”，サイエンス社，2010年9月10日，ISBN 978-4-7819-1262-2，第１３章」などを参照されたい。
【００１７】
a_i∈G^N (i=1,...,N)は、巡回群GのN個の元を要素とするN次元の基底ベクトルを表す。ただし、μが２以上の整数であり、N=n+μである。基底ベクトルa_iの一例はg∈Gをi次元目の要素とし、残りのN-1個の要素を巡回群Gの単位元（乗法的に「1」と表現）とするN-1次元の基底ベクトルである。N次元の基底ベクトルa_i(i=1,...,N)の各要素をそれぞれ列挙して表記すると、以下のようになる。
a₁=(g,1,1,...,1)
a₂=(1,g,1,...,1) …(4)
...
a_N=(1,1,1,...,g)
【００１８】
a_i^*∈G^N (i=1,...,N)は、巡回群GのN個の元を要素とするN次元の基底ベクトルを表す。基底ベクトルa_i^*の一例はg∈Gをi次元目の要素とし、残りのN-1個の要素を巡回群Gの単位元（乗法的に「1」と表現）とするN-1次元の基底ベクトルである。N次元の基底ベクトルa_i^*(i=1,...,N)の各要素をそれぞれ列挙して表記すると、以下のようになる。
a₁^*=(g,1,1,...,1)
a₂^*=(1,g,1,...,1) …(5)
...
a_N^*=(1,1,1,...,g)
【００１９】
N個の基底ベクトルa_i(i=1,...,N)からなる基底Aは直交基底であり、巡回群G上のN次元ベクトル空間V=G×...×Gを張る（V=span<a₁,...,a_N>）。N次元ベクトル空間V上の任意の元γ=(γ₁,...,γ_N)∈Vは、基底ベクトルa_i(i=1,...,N)とd_i∈F_q(i=1,...,N)とを用い、便宜上、以下のように加法的に表記できる（便宜的加法表現）。
γ=Σ_i=1^N d_i・a_i …(6)
式(6)を乗法的に表記すると以下のようになる。
γ=(g^d1,...,g^dN) …(7)
ただし、上付き添え字の「d1」,...,「dN」は「d₁」,...,「d_N」を表す。
N個の基底ベクトルa_i(i=1,...,N)からなる基底AとN個のd_i∈F_q(i=1,...,N)からベクトルd^→=(d₁,...,d_N)とを用い、N次元ベクトル空間V上の任意の元γを以下のように表記する。
γ=(d^→)_A=(d₁,...,d_N)_A …(8)
【００２０】
N個の基底ベクトルa_i^*(i=1,...,N)からなる基底A^*は直交基底であり、巡回群G上のN次元ベクトル空間V^*=G×...×Gを張る（V^*=span<a₁^*,...,a_N^*>）。N次元ベクトル空間V^*上の任意の元γ^*=(γ₁^*,...,γ_N^*)∈V^*は、基底ベクトルa_i^* (i=1,...,N)とf_i∈F_q(i=1,...,N)とを用い、便宜上、以下のように加法的に表記できる（便宜的加法表現）。
γ^*=Σ_i=1^N f_i・a_i^* …(9)
式(9)を乗法的に表記すると以下のようになる。
γ^*=(g^f1,...,g^fN) …(10)
ただし、上付き添え字の「f1」,...,「fN」は「f₁」,...,「f_N」を表す。
N個の基底ベクトルa_i^*(i=1,...,N)からなる基底A^*とN個のf_i∈F_q(i=1,...,N)からベクトルf^→=(f₁,...,f_N)とを用い、N次元ベクトル空間V^*上の任意の元γ^*を以下のように表記する。
γ^*=(f^→)_A*=(f₁,...,f_N)_A* …(11)
ただし、下付き添え字の「A*」はA^*を表す。
【００２１】
式(2)(3)(7)(10)より、γ=(d^→)_A=(d₁,...,d_N)_A∈V，γ^*=(f^→)_A*=(f₁,...,f_N)_A*∈V^*について、以下の関係が成り立つ。
e_N(γ, γ^*)=Π_i=1^N e₁(γ_i, γ_i^*)
=Π_i=1^N e₁(g^di, g^fi)
=e₁(g, g)^{d1・f1+...+dN・fN}
=e₁(g, g)^d→・f→
=g_T^d→・f→ …(12)
ただし、上付き添え字の「d→」「f→」は、それぞれ「d^→」「f^→」を表す。
【００２２】
また式(2)(3)より、基底ベクトルa_i(i=1,...,N)と基底ベクトルa_j^*(j=1,...,N)は以下の関係を満たす。すなわち、基底Aと基底A^*とは互いに双対な直交基底（双対直交基底）である。
e_N(a_i, a_j^*)=g_T^δ(i,j) …(13)
ただし、δ(i,j)はクロネッカーのデルタ関数を表す。すなわち、i=jの場合にδ(i,j)=1∈F_qを満たし、i≠jの場合にδ(i,j)=0∈F_qを満たす。
【００２３】
双線形写像e_Nがペアリングによって構成される場合、上述のような位数q，N次元ベクトル空間V，V^*，巡回群G, G_T，生成元g，双線形写像e_Nの組を「対称ペアリング群による双対ペアリングベクトル空間（DPVS:Dual Paring Vector space)）と呼ぶ。
【００２４】
N個の基底ベクトルa_i(i=1,...,N)からなる基底Aは、一様ランダムなN行N列の正則行列X=(χ_i,j) ←^U GL(N, F_q)を用い、N次元ベクトル空間Vの基底B=(b₁,...,b_N)に変換可能である。GL(N, F_q)は有限体F_q上のN次元一般線形群を表し、(χ_i,j)は、χ_i,jをi行j列の要素とする行列を表す。「MENBER ←^USET」は集合「SET」の要素「MENBER」を一様ランダムに選択することを意味する。基底Bの要素b_i∈G^N (i=1,...,N)のそれぞれは、巡回群GのN個の元を要素とするN次元の基底ベクトルであり、便宜上、以下のように加法的に表記できる（便宜的加法表現）。
b_i=Σ_j=1^N χ_i,j・a_j (i=1,...,N) …(14)
式(14)を乗法的に表記すると以下のようになる。
b_i=(g^χi,1,...,g^χi,N) (i=1,...,N) …(15)
ただし、上付き添え字の「χi,j」は「χ_i,j」を表す。
すなわち、基底B=(b₁,...,b_N)は巡回群Gの元を要素とするN×Nの行列とみることができ、乗法的に以下のように表記することができる。
B=((g^χi,j)_i,j) …(16)
【００２５】
N個の基底ベクトルa_i^*(i=1,...,N)からなる基底A^*は、正則行列(θ_i,j)=(X^T)^-1を用い、N次元ベクトル空間V^*の直交基底B^*=(b₁^*,...,b_N^*)に変換可能である。ただし、Ξ^TはΞの転置を表し、Ξ^-1はΞの逆行列を表し、(θ_i,j)はθ_i,j (i=1,...,N, j=1,...,N)をi行j列の要素とする行列を表す。直交基底B^*の要素b_i^*∈G^N (i=1,...,N)のそれぞれは、巡回群GのN個の元を要素とするN次元の基底ベクトルであり、便宜上、以下のように加法的に表記できる（便宜的加法表現）。
b_i^*=Σ_j=1^N θ_i,j・a_j^* (i=1,...,N) …(17)
式(17)を乗法的に表記すると以下のようになる。
b_i^*=(g^θi,1,...,g^θi,N) (i=1,...,N) …(18)
ただし、上付き添え字の「θi,j」は「θ_i,j」を表す。
すなわち、基底B^*=(b₁,...,b_N)は巡回群Gの元を要素とするN×Nの行列とみることができ、乗法的に以下のように表記することができる。
B^*=((g^θi,j)_i,j) …(19)
【００２６】
(θ_i,j)=(X^T)^-1から(θ_i,j)・(X_i,j)^T=I_Nが成り立つことから、χ_i^→=(χ_i,1,...,χ_i,N)，θ_j^→=(θ_j,1,...,θ_j,N)とおくと以下が成り立つ。
χ_i^→・θ_j^→=(χ_i,1,...,χ_i,N)・(θ_j,1,...,θ_j,N)
=δ(i,j)∈F_q^× …(20)
【００２７】
式(3)(15)(18)(20)から以下が成り立つ。
e_N(b_i, b_j^*)=Π_ι=1^Ne₁(g^χi,ι, g^θj,ι)
=e₁(g, g)^{χi→・θj→}
=e₁(g, g)^δ(i,j)
=g_T^δ(i,j) …(21)
すなわち、基底Bと基底B^*とは互いに双対な直交基底（双対直交基底）である。基底Bは巡回群G上のN次元ベクトル空間V=G×...×Gを張り（V=span<b₁,...,b_N>）、基底B^*は巡回群G上のN次元ベクトル空間V^*=G×...×Gを張る（V^*=span<b₁^*,...,b_N^*>）。
【００２８】
N次元ベクトル空間V上の任意の元γ=(γ₁,...,γ_N)∈Vは、基底ベクトルb_i(i=1,...,N)とd_i∈F_q(i=1,...,N)とを用い、便宜上、以下のように加法的に表記できる（便宜的加法表現）。
γ=Σ_i=1^N d_i・b_i …(22)
式(16)より、式(22)を乗法的に表記すると以下のようになる。
【数１】

基底Bとベクトルd^→=(d₁,...,d_N)とを用い、N次元ベクトル空間V^*上の任意の元γを以下のように表記する。
γ=(d^→)_B=(d₁,...,d_N)_B …(24)
【００２９】
N次元ベクトル空間V^*上の任意の元γ^*=(γ₁^*,...,γ_N^*)∈V^*は、基底ベクトルb_i^* (i=1,...,N)とf_i∈F_q(i=1,...,N)とを用い、便宜上、以下のように加法的に表記できる（便宜的加法表現）。
γ^*=Σ_i=1^N f_i・b_i^* …(25)
式(19)より、式(25)を乗法的に表記すると以下のようになる。
【数２】

基底B^*とベクトルf^→=(f₁,...,f_N)とを用い、N次元ベクトル空間V^*上の任意の元γ^*を以下のように表記する。
γ^*=(f^→)_B*=(f₁,...,f_N)_B* …(27)
【００３０】
式(2)(3)(20)より、γ=(d^→)_B=(γ₁,...,γ_N)=(d₁,...,d_N)_B∈V，γ^*=(f^→)_B*=(γ₁^*,...,γ_N^*)= (f₁,...,f_N)_B*∈V^*について、以下の関係が成り立つ。
e_N(γ, γ^*)=e_N(b₁, b₁^*)^d1・f1・...・e_N(b_N, b_N^*)^dN・fN
=g_T^{(d1・f1+...+dN・fN)}
=g_T^d→・f→ …(28)
【００３１】
〔概要〕
次に、実施形態の概要を説明する。
実施形態のセキュリティシステムは、パラメータ生成装置、第１復号装置、第２復号装置、難読化装置、暗号化装置及び再暗号化装置を有する。
【００３２】
パラメータ生成装置は、セキュリティシステム全体に共通なシステムパラメータを生成する機能、及び、生成したシステムパラメータを出力する機能を有する。
パラメータ生成装置は、1^sec（sec個の1）を入力として、セキュリティパラメータsecに対応する双線型写像パラメータparam_V=(q, g, G, G_T, e_N)，正則行列X=(χ_i,j)，基底B=(b₁,...,b_N)，B^*=(b₁^*,...,b_N^*)（N=n+μ）を生成する。パラメータ生成装置は、双線型写像パラメータparam_Vを記憶部に記憶する。
パラメータ生成装置は、n+μ個の基底ベクトルb_i∈G^n+μ(i=1,...,n+μ)の一部であるΓ個の基底ベクトルb_ι(1),...,b_ι(Γ)からなるB^=(b_ι(1),...,b_ι(Γ))を生成する。ただし、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}、n+1≦Γ＜n+μである。例えば、μ=2・n+2であり、Γ=n+2であり、{ι(n+3),...,ι(3・n+2)}⊂{1,...,3・n+2}であり、B^=(b_ι(1),...,b_ι(n+2))である。より具体的な例を挙げると、B^=(b₁,...,b_n,b_2・n+1,b_3・n+2)である。
パラメータ生成装置は、以下のシステムパラメータcrsを公開パラメータとして出力する。
crs=(param_V, B^) …(29)
【００３３】
第１復号装置は、公開鍵と秘密鍵を生成する機能、公開鍵と秘密鍵を記憶部に記憶する機能、及び、公開鍵を出力する機能を有する。第１復号装置は、システムパラメータcrsを入力とし、a(1), b(1), c(1), τ(1)∈F_q^×を選択して秘密鍵sk(1)=(a(1), b(1), c(1), τ(1))及び公開鍵pk(1)=(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)を生成する。秘密鍵sk(1)及び公開鍵pk(1)は第１復号装置の記憶部に記憶され、公開鍵pk(1)は任意の装置に送信可能とされる。
B(1)=c(1)・τ(1)・B^は、巡回群Gの元を要素とするベクトル単位の演算結果を表し、便宜上、加法的に表現されている（便宜的加法表現）。
式(16)より、B(1)=c(1)・τ(1)・B^を乗法的に表記すると以下のようになる。これはB^とc(1)，τ(1)とから計算可能である。
B(1)=((g^{c(1)・τ(1)・χi,j})_i,j) …(30)
ただし、i∈{ι(1),...,ι(Γ)}⊂{1,...,n+μ}，j∈{1,...,n+μ}である。
【００３４】
第２復号装置は、公開鍵と秘密鍵を生成する機能、公開鍵と秘密鍵を記憶部に記憶する機能、及び、公開鍵を出力する機能を有する。第２復号装置は、システムパラメータcrsを入力とし、a(2), b(2), c(2), τ(2)∈F_q^×を選択して秘密鍵sk(2)=(a(2), b(2), c(2), τ(2))及び公開鍵pk(2)=(h(2)=g^τ(2), h(2)^a(2), h(2)^b(1), h(2)^c(1), B(2)=c(2)・τ(2)・B^)を生成する。秘密鍵sk(2)及び公開鍵pk(2)は第２復号装置の記憶部に記憶され、公開鍵pk(2)は任意の装置に送信可能とされる。
B(2)=c(2)・τ(2)・B^は、巡回群Gの元を要素とするベクトル単位の演算結果を表し、便宜上、加法的に表現されている（便宜的加法表現）。
式(16)より、B(2)=c(2)・τ(2)・B^を乗法的に表記すると以下のようになる。これはB^とc(2)，τ(2)とから計算可能である。
B(2)=((g^{c(2)・τ(2)・χi,j})_i,j) …(31)
ただし、i∈{ι(1),...,ι(Γ)}⊂{1,...,n+μ}，j∈{1,...,n+μ}である。
【００３５】
難読化装置は、第１復号装置の秘密鍵sk(1)、第２復号装置の公開鍵pk(2)、n次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿ、及びシステムパラメータ生成時に生成された正則行列Xを入力とし、再暗号化鍵Obf(rk_1→2)を生成する機能を有する。なお、正則行列Xは秘密情報であるため、パラメータ生成装置と難読化装置が同一であるか、難読化装置が何らかの安全な手段（専用回線や記録媒体を介した情報伝達等）を用いてパラメータ生成装置から正則行列Xを取得する必要がある。同様に秘密鍵sk(1)は秘密情報であるため、難読化装置が何らかの安全な手段を用いて第１復号装置から秘密鍵sk(1)を取得する必要がある。
【００３６】
難読化装置は、sk(1)=(a(1), b(1), c(1), τ(1))、pk(2)=(h(2)=g^τ(2), h(2)^a(2), h(2)^b(1), h(2)^c(1), B(2)=c(2)・τ(2)・B^)、v^→=(v_ι(1),...,v_ι(n))∈F_qⁿ、及び正則行列Xを入力として、Z₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含む再暗号化鍵Obf(rk_1→2)を生成する。
RV^→はn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、z, ρ, σ∈F_q^×は乱数であり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))はn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1∈F_qである。例えば、RV^→が3・n+2次元ベクトルRV^→=(RV_ι(1),...,RV_ι(3・n+2))であり、１個のRV_κ∈{RV_ι(n+1), RV_ι(n+2)}が1∈F_qであり、RV_κ以外の１個のRV_φ∈{RV_ι(n+1), RV_ι(n+2)}が0∈F_qであり、n個のRV_ε(1),...,RV_ε(n)∈{RV_ι(n+3),...,RV_ι(3・n+2)}が乱数η_ε(1),...,η_ε(n)∈F_qであり、RV_ε(1),...,RV_ε(n)以外のn個のRV_υ(1),...,RV_υ(n)∈{RV_ι(n+3),...,RV_ι(3・n+2)}のそれぞれが0∈F_qである。これによりより高い安全性を確保できる。より具体的な例を挙げると、v^→=(v₁,...,v_n)，(RV₁,..., RV_n)=(σ・v₁,...,σ・v_n)=σ・v^→，(RV_n+1,...,RV_2・n)=(0,...,0)=0ⁿ，RV_2・n+1=1，(RV_2・n+2,...,RV_3・n+1)=(η_2・n+2,...,η_3・n+1)=η^→∈F_qⁿ，RV_3・n+2=0であり、RV^→の例は以下である。
RV^→=(σ・v^→，0ⁿ，1,η^→，0)∈F_q^3・n+2 …(32)
【００３７】
B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*は、巡回群Gの元を要素とするベクトル単位の演算結果を表し、便宜上、加法的に表現されている（便宜的加法表現）。式(19)より、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*を乗法的に表記し、変形すると以下のようになる。
B(1,2)^*=((g^{θi,j・(ρ/c(1))・c(2)・τ(2)})_i,j)
=((g^{χi,j・c(2)・τ(2)・(ρ・θi,j /c(1)・χi,j)})_i,j) …(33)
【００３８】
難読化装置は、B(2)=((g^{c(2)・τ(2)・χi,j})_i,j)(i∈{ι(1),...,ι(Γ)}，j∈{1,...,n+μ})と正則行列Xを用いることで、g^{c(2)・τ(2)・χi’,j’}=(g^{c(2)・τ(2)・χi,j})^{χi’,j’/χi,j}(i≠i’,j≠j’)を計算でき、以下のB(2)’を生成できる。
B(2)’=((g^{χi,j・c(2)・τ(2)})_i,j) (i,j∈{1,...,n+μ}) …(34)
式(33)(34)より、難読化装置はB(2)’を用いてB(1,2)^*を計算することができることが分かる。
【００３９】
暗号化装置は、システムパラメータcrs、第１復号装置の公開鍵(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))又は第２復号装置の公開鍵(h(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2))、モード選択パラメータβ、n次元ベクトルx^→=(x_ι(1),...,x_ι(n))∈F_qⁿ、及びメッセージm∈Gを入力とし、メッセージm∈Gの暗号文を生成する機能、及び、暗号文を出力する機能を有する。
【００４０】
暗号化装置が第１復号装置で復号可能な暗号文を生成する場合、暗号化装置は、暗号文ct(0,1)（第１暗号文）及び暗号文ct(1,1)（第２暗号文）の何れかを生成する。暗号文ct(0,1)は再暗号化可能なモード（以下「第１モード」という）の暗号文であり、暗号文ct(1,1)は再暗号化不可能なモード（以下「第２モード」という）の暗号文である。本形態の再暗号化方式は「単方向単一ホップ型」であり、第１モードの暗号文が再暗号化されると第２モードの暗号文となる。モード選択パラメータβは、第１モードであるか第２モードであるかを表す。第１モードの場合、モード選択パラメータβが第１値とされ、第２モードの場合、モード選択パラメータβが第２値（≠第１値）とされる。本形態の例では、第１値を「0」とし、第２値を「1」とする（β∈{0,1}）。
【００４１】
暗号文ct(0,1)は、W(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含む。本形態では暗号文ct(0,1)がさらに第１値のモード選択パラメータβ=0を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ct(0,1)がモード選択パラメータを含まなくてもよい。
CV^→はn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))はn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、r, s, ω∈F_qは乱数であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}が乱数ζ∈F_qである。CV_ι(n+1),...,CV_ι(Γ)からCV_κを除いた要素からなるベクトルと上述のRV_ι(n+1),...,RV_ι(Γ)からRV_κを除いた要素からなるベクトルとの内積が0となる。例えば、CV^→が3・n+2次元ベクトルCV^→=(CV_ι(1),...,CV_ι(3・n+2))であり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、１個のCV_κ∈{CV_ι(n+1), CV_ι(n+2)}が乱数ζであり、CV_κ以外の１個のCV_φ∈{CV_ι(n+1), CV_ι(n+2)}が暗号化装置によって選択された乱数ψ∈F_qであり、2・n個のCV_ι(n+3),...,CV_ι(3・n+2)のそれぞれが0である。これによりより高い安全性を確保できる。より具体的な例を挙げると、x^→=(x ₁,...,x _n)，(CV₁,...,CV_n)=(ω・x₁,...,ω・x_n)=ω・x^→，(CV_n+1,...,CV_2・n)=(0,...,0)=0ⁿ，CV_2・n+1=ζ，(CV_2・n+2,...,CV_3・n+1)=(0,...,0)=0ⁿ，CV_3・n+2=ψであり、CV^→の例は例えば以下である。
CV^→=(ω・x^→，0ⁿ，ζ，0ⁿ，ψ)∈F_q^3・n+2 …(35)
【００４２】
暗号文ct(1,1)は、E(1,1)=e₁((h(1)^a(1))^r, t),F(1,1)=e₁((h(1)^b(1))^s, t),G(1,1)=e₁((h(1)^r+s・m, t))・e₁(t^~, (h(1)^c(1))^ζ), Z(1,1)=t, H(1,1)=e₁(t^~, h(1)^ζ)を含む。t, t^~∈Gは乱数である。本形態では暗号文ct(1,1)がさらに第２値のモード選択パラメータβ=1を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ct(1,1)がモード選択パラメータを含まなくてもよい。
【００４３】
暗号化装置が第２復号装置で復号可能な暗号文を生成する場合、暗号化装置は、第１モードの暗号文ct(0,2)及び第２モードの暗号文ct(1,2)’の何れかを生成する。
暗号文ct(0,2)は、W(0,2)=(h(2)^a(2))^r, Θ(0,2)=(h(2)^b(2))^s, Y(0,2)=h(2)^r+s・m,U(0,2)=(CV^→)_B(1), Λ(0,2)=h(2)^ζを含む。本形態では暗号文ct(0,2)がさらに第１値のモード選択パラメータβ=0を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ct(0,2)がモード選択パラメータを含まなくてもよい。
暗号文ct(1,2)’は、E(1,2)’=e₁((h(2)^a(2))^r, t),F(1,2)’=e₁((h(2)^b(2))^s, t),G(1,2)’=e₁((h(2)^r+s・m, t))・e₁(t^~, (h(2)^c(2))^ζ), Z(1,2)’=t, H(1,2)’=e₁(t^~, h(2)^ζ)を含む。本形態では暗号文ct(1,2)’がさらに第２値のモード選択パラメータβ=1を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ct(1,2)’がモード選択パラメータを含まなくてもよい。
【００４４】
再暗号化装置は、第１復号装置の公開鍵pk(1)=(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))、暗号文ct(0,1)、及び再暗号化鍵Obf(rk_1→2)を入力とし、第２復号装置が復号可能な暗号文ct(1,2)（再暗号文）を生成する機能、及び、暗号文ct(1,2)を出力する機能を有する。
再暗号化装置は、乱数r’, s’, ζ’∈F_qを用い、W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’を得、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)を得、乱数y, y’∈F_q^×に対するE(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む暗号文ct(1,2)を生成する。REV^→はn+μ次元ベクトルREV^→=(REV_ι(1),...,REV_ι(n+μ))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(n+μ)}が乱数ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(n+μ)が0∈F_qである。例えば、REV^→は3・n+2次元ベクトルREV^→=(REV_ι(1),...,REV_ι(3・n+2))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(3・n+2)}が乱数ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(3・n+2)が0∈F_qである。より具体的な例を挙げると、(REV₁,...,REV_2・n)=(0,...,0)=0^2・n，REV_2・n+1=ζ’ ，(REV_2・n+2,...,REV_3・n+2)=(0,...,0)=0ⁿ⁺¹であり、REV^→の例は以下である。
REV^→=(0ⁿ，0ⁿ，ζ’,0ⁿ，0)∈F_q^3・n+2 …(36)
前述のように、暗号文ct(1,2)は第２モードの暗号文となる。本形態では暗号文ct(1,2)がさらに第２値のモード選択パラメータβ=1を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ct(1,2)がモード選択パラメータを含まなくてもよい。
【００４５】
第１復号装置は、さらに、入力暗号文を復号して復号値m’を得る機能、及び、復号値m’を出力する機能を有する。第１復号装置は、入力暗号文として暗号文ct(0,1)（第１値を表すモード選択パラメータβ=0を含む入力暗号文）が得られた場合にm’=Y(0,1)/(W(0,1)^1/a(1)・Θ(0,1)^1/b(1))を復号値として得る。第１復号装置は、入力暗号文として暗号文ct(1,1)（第２値を表すモード選択パラメータβ=1を含む入力暗号文）が得られた場合にe₁(m’, Z(1,1))=G(1,1)/{H(1,1)^c(1)・E(1,1)^1/a(1)・F(1,1)^1/b(1)}を満たすm’∈Gを復号値として得る。e₁(m’, Z(1,1))=G(1,1)/{H(1,1)^c(1)・E(1,1)^1/a(1)・F(1,1)^1/b(1)}を満たすm’∈Gの探索は、例えば、有限体Gの元を全数探索することによって行われる。
【００４６】
第２復号装置も、さらに、入力暗号文を復号して復号値m’を得る機能、及び、復号値m’を出力する機能を有する。第２復号装置は、入力暗号文として暗号文ct(0,2)（第１値を表すモード選択パラメータβ=0を含む入力暗号文）が得られた場合にm’=Y(0,2)/(W(0,2)^1/a(2)・Θ(0,2)^1/b(2))を復号値として得る。第２復号装置は、入力暗号文として暗号文ct(1,2)（第２値を表すモード選択パラメータβ=1を含む入力暗号文）が得られた場合にe₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2) ^1/b(2)}を満たすm’∈Gを復号値として得る。e₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2) ^1/b(2)}を満たすm’∈Gの探索は、例えば、有限体Gの元を全数探索することによって行われる。暗号文ct(1,2)’が得られた場合も同様に、第２復号装置は、e₁(m’, Z(1,2)’)=G(1,2)’/{H(1,2)’^c(2)・E(1,2)’^1/a(2)・F(1,2)’^1/b(2)}を満たすm’∈Gを復号値として得る。
【００４７】
＜復号結果の導出＞
以下に復号結果の導出を行う。
［再暗号化前の暗号文ct(0,1)の場合］
以下より正しい復号値が得られることが分かる。
m’=Y(0,1)/(W(0,1)^1/a(1)・Θ(0,1)^1/b(1))
=h(1)^r+s・m/h(1)^(r+s)
=m
［再暗号化前の暗号文ct(1,1)の場合］
式(3)より、復号時の探索用の式には以下の関係が成り立つ。
e₁(m’, Z(1,1))=e₁(m’, t)
G(1,1)/{H(1,1)^c(1)・E(1,1)^1/a(1)・F(1,1)^1/b(1)}
=e₁((h(1)^r+s・m, t))・e₁(t^~, (h(1)^c(1))^ζ)/{e₁(t^~, h(1)^ζ)^c(1)・e₁((h(1)^a(1))^r, t)^1/a(1)・e₁((h(1)^b(1))^s, t)^1/b(1)}
=e₁((m, t))・e₁(h(1), t)^(r+s)・e₁(t^~, h(1))^c(1)・ζ/{e₁(t^~, h(1))^c(1)・ζ・e₁(h(1), t)^(r+s)}
=e₁((m, t))
したがって、正しい復号値が得られることが分かる。
同様に、再暗号化前の暗号文ct(0,2), ct(1,2)’についても正しく復号値が得られることが分かる。
【００４８】
[再暗号化によって得られた暗号文ct(1,2)の場合]
式(2)より、暗号文ct(1,2)が含むE(1,2)は以下のように変形できる。
E(1,2)=e₁((g^τ(1)・a(1))^r・(g^τ(1)・a(1))^r’,(g^τ(2)・a(2))^z/a(1))^y
=e₁(g^{τ(1)・(r+r’)},g^{τ(2)・a(2)・z})^y
=e₁(g^{(τ(1)/τ(2))・τ(2)・a(2)・(r+r’)},g^{τ(2)・y・z})
=e₁(h(2)^{(τ(1)/τ(2))・a(2)・(r+r’)}, h(2)^y・z) …(37)
L=τ(2)/τ(1)，r^-=(r+r’)/L及びt^-=h(2)^y・zとおくと、式(37)は以下のように表記できる。
E(1,2)=e₁(h(2)^a(2)・r-, t^-) …(38)
ただし、上付き添え字の「r-」は「r^-」を表す。
【００４９】
式(2)より、暗号文ct(1,2)が含むF(1,2)は以下のように変形できる。
F(1,2)=e₁((g^τ(1)・b(1))^s・(g^τ(1)・b(1))^s’,(g^τ(2)・b(2))^z/b(1))^y
=e₁(g^{τ(1)・(s+s’)},g^{τ(2)・b(2)・z})^y
=e₁(g^{τ(1)・b(2)・(s+s’)},g^{τ(2)・y・z})
=e₁(g^{(τ(1)/τ(2))・τ(2)・b(2)・(s+s’)},g^{τ(2)・y・z})
=e₁(h(2)^{b(2)・(τ(1)/τ(2))・(s+s’)}, h(2)^y・z) …(39)
L=τ(2)/τ(1)，s^-=(s+s’)/L及びt^-=h(2)^y・zとおくと、式(39)は以下のように表記できる。
F(1,2)=e₁(h(2)^b(2)・s-, t^-) …(40)
ただし、上付き添え字の「s-」は「s^-」を表す。
【００５０】
式(2)(21)(28)(30)(33)より、暗号文ct(1,2)が含むG(1,2)は以下のように変形できる。
G(1,2)
=e₁(g^{τ(1)・(r+s)}・m・g^{τ(1)・(r’+s’)}, g^τ(2)・z)^y・e_n+μ((CV^→+REV^→)_B(1), (RV^→)_B(1,2)*)^y’
=e₁(g^{τ(1)・(r+s+r’+s’)}・m,g^τ(2)・z)^y・e_n+μ((c(1)・τ(1)・CV’^→)_B, ((ρ/c(1))・c(2)・τ(2)・RV^→)_B*)^y’
=e₁(h(2)^{(τ(1)/τ(2))・(r+s+r’+s’)}・m,h(2)^y・z)・e₁(g,g)^{c(2)・τ(1)・τ(2)・ρ・y’・(CV’→・RV→)}…(41)
ただし、上付き添え字の「CV’→」は「CV’^→」を表し、「RV→」は「RV^→」を表す。CV’^→はCV’^→=CV^→+REV^→を満たすn+μ次元ベクトルである。n+μ次元ベクトルCV^→が含む１個の要素CV_κ=ζをζ＋ζ’に置換したものがCV’^→となる。
ここで、RV^→=(RV_ι(1),...,RV_ι(n+μ))を構成する(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、１個のRV_κが1である。CV^→=(CV_ι(1),...,CV_ι(n+μ))を構成する(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、１個のCV_κがζである。(CV_ι(n+1),...,CV_ι(Γ))からCV_κを除いた要素からなるベクトルとRV^→=(RV_ι(n+1),...,RV_ι(Γ))からRV_κを除いた要素からなるベクトルとの内積が0となる。そのため、CV’^→・RV^→=ζ+ζ’+ω・σ・x^→・v^→となる。式(32)(35)(36)の具体例を用いて導出すると以下のようになる。
CV’^→=(ω・x^→，0ⁿ，ζ+ζ’，0ⁿ，ψ)
CV’^→・RV^→=(ω・x^→，0ⁿ，ζ+ζ’，0ⁿ，ψ)・(σ・v^→，0ⁿ，1,η^→，0)
=ζ+ζ’+ω・σ・x^→・v^→
したがって式(41)は以下のように変形できる。
G(1,2)
=e₁(h(2)^{(τ(1)/τ(2))・(r+s+r’+s’)}・m,h(2)^y・z)・e₁(g,g)^{c(2)・τ(1)・τ(2)・ρ・y’・(ζ+ζ’+ω・σ・x→・v→)}
=e₁(h(2)^{(τ(1)/τ(2))・(r+s+r’+s’)}・m,h(2)^y・z)・e₁(h(1)^{L・ρ・y’}, h(2)^{c(2)・(ζ+ζ’+ω・σ・x→・v→)/L}) …(42)
ここで、L=τ(2)/τ(1)，ζ^-=(ζ+ζ’)/L，ν=(ω・σ・x^→・v^→)/L，r^-=(r+r’)/L，s^-=(s+s’)/L，t^-=h(2)^y・z及びt^-’=h(1)^{L・ρ・y’}とおくと、式(42)は以下のように表記できる。
G(1,2)=e₁(h(2)^((r-)+(s-))・m,t^-)・e₁(t^-’, h(2)^{c(2)・((ζ-)+ν)}) …(43)
ただし、上付き添え字の「r-」は「r^-」を表し、「s-」は「s^-」を表し、「ζ-」は「ζ^-」を表す。
【００５１】
t^-=h(2)^y・zとおくと、暗号文ct(1,2)が含むZ(1,2)は以下のように表記できる。
Z(1,2)=Z₃^y=h(2)^y・z=t^- …(44)
式(2)より、暗号文ct(1,2)が含むH(1,2)は以下のように変形できる。
H(1,2)=e₁(h(1)^(ζ+ζ’), h(2)^ρ)^y’
=e₁(h(1)^ρ・y’, h(2)^{L・(ζ+ζ’)/L}) …(45)
ここでζ^-=(ζ+ζ’)/L及びt^-’=h(1)^{L・ρ・y’}とおくと、式(45)は以下のように表記できる。
H(1,2)=e₁(t^-’, h(2)^ζ-) …(46)
【００５２】
式(38)(40)(43)(44)(46)より、復号時の探索用の式には以下の関係がなりたつ。
e₁(m’, Z(1,2))=e₁(m’, t^-)
G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2)^1/b(2)}
=e₁(h(2)^((r-)+(s-))・m,t^-)・e₁(t^-’, h(2)^{c(2)・((ζ-)+ν)})/{e₁(t^-’, h(2)^ζ-)^c(2)・e₁(h(2)^a(2)・r-, t^-)^1/a(2)・e₁(h(2)^b(2)・s-, t^-)^1/b(2)}
=e₁(m, t^-)・e₁(h(2), t^-)^((r-)+(s-))・e₁(t^-’, h(2))^{c(2)・((ζ-)+ν)}/{e₁(t^-’, h(2))^c(2)・ζ-・e₁(h(2), t^-)^((r-)+(s-))}
=e₁(m, t^-)・e₁(t^-’, h(2))^{c(2)・((ζ-)+ν)}/e₁(t^-’, h(2))^c(2)・ζ- …(47)
式(47)はν=0すなわち、内積x^→・v^→=0の場合にはe₁(m, t^-)となり、m’=mとなり正しく復号がなされる。一方、内積x^→・v^→≠0の場合には式(47)はe₁(m, t^-)とならず、正しく復号できない。以上より、n次元ベクトルx^→とn次元ベクトルv^→との内積が０のときに復号が可能となる内積述語暗号において、再暗号化方式が実現されたことが分かる。このように本実施形態では、暗号文にn次元ベクトルx^→を、再暗号化鍵にn次元ベクトルv^→をそれぞれ埋め込み、x^→・v^→=0が成立するか否かによって正しく再暗号化が行われるかを制御することができる。
【００５３】
＜述語秘匿性＞
実施形態のセキュリティシステムは述語秘匿性を有する。述語秘匿性とは、述語暗号方式における鍵に対応するn次元ベクトルv^→の秘匿性を意味する。「述語秘匿性」という呼び名は、鍵に述語ベクトルが対応し、暗号文に属性ベクトルが対応することを前提としたものである。しかしながら、鍵に属性ベクトルが対応し、暗号文に述語ベクトルが対応してもよい。鍵に対応するn次元ベクトルv^→が属性ベクトルである場合には「述語秘匿性」とは属性の秘匿性を意味する。これまでの述語暗号方式に述語秘匿性を持つものは存在しない。これは従来の述語暗号方式では、攻撃者が任意のn次元ベクトルv’^→を用いて鍵を生成し、その鍵で暗号文を復号して正しいメッセージが得られるか否かを探索することで、n次元ベクトルv^→に関する情報を得ることができるからである。これに対し、本実施形態では、暗号文にn次元ベクトルx^→を埋め込み、再暗号化鍵にn次元ベクトルv^→を埋め込む。そのため、攻撃者が任意のn次元ベクトルv’^→を用いて再暗号化鍵を生成し、その再暗号化鍵で暗号文を再暗号化しても、それによって得られるのは暗号文であり、当該攻撃者はその暗号文が正しく再暗号化されたかを判断することができない。よって、本実施形態では述語秘匿性を実現できる。
【００５４】
＜再暗号化鍵の難読化＞
再暗号化鍵Obf(rk_1→2)を含む再暗号化コードが難読化された情報となることを説明する。
［難読化の定義］
入力値INに対してOUT=CODE(IN)を出力するコードCODE、コードCODEに対応する情報Obf(CODE)、任意の入力値INに対して出力値OUT=CODE(IN)を出力するオラクル、仮想的な攻撃者ADV、シミュレータSIM、及び識別器DISを仮定する。攻撃者ADVには情報Obf(CODE)が与えられるが、シミュレータSIMには情報Obf(CODE)が与えられない。攻撃者ADV、シミュレータSIM及び識別器DISは、オラクルORAからコードCODEを与えられないが、オラクルORAに任意の入力値INを与えてそれに対する出力値OUT=CODE(IN)を得ることができる。攻撃者ADVは、情報Obf(CODE)とオラクルORAを用いて得られた情報を識別器DISに与える。シミュレータSIMは、オラクルORAを用いて得られた情報を識別器DISに与える。識別器DISは、オラクルORA及び与えられた情報を用いて当該情報を与えたものが攻撃者ADVであるかシミュレータSIMであるかを識別する。識別器DISは、情報を与えたものが攻撃者ADVであると識別した場合に１を出力し、シミュレータSIMであると識別した場合に0を出力する。以下の条件(I)〜(III)が成り立つ場合、Obf(CODE)はCODEが難読化された情報である。
(I) 任意の入力値^∀INについて、CODE(IN)=Obf(CODE(IN))を満たす。
(II) Obf(CODE(IN))が任意の入力値^∀INのサイズに対する多項式時間で計算可能である。
(III) 任意の攻撃者^∀ADV及び識別器^∀DISに対して以下を満たすシミュレータ^∃SIMが存在する。
Pr[DIS^ORA(ADV^ORA(Obf(CODE)))→1]-Pr[DIS^ORA(SIM^ORA)→1]<NEGL(sec) …(48)
ただし、Pr[DIS^ORA(ADV^ORA(Obf(CODE)))→1]は、攻撃者ADVから情報が与えられた識別器DISが当該情報を与えたものが攻撃者ADVであると識別して1を出力する確率を表す。Pr[DIS^ORA(SIM^ORA)→1]は、シミュレータSIMから情報が与えられた識別器DISが当該情報を与えたものが攻撃者ADVであると識別して1を出力する確率を表す。NEGL(sec)は、無視することができる値を出力する関数である。NEGL(sec)の出力値はセキュリティパラメータsecが大きいほど小さい。
【００５５】
［再暗号化鍵Obf(rk_1→2)を含む再暗号化コードの難読化］
再暗号化鍵Obf(rk_1→2)は、Z₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含む。式(38)(40)(43)(44)(46)より、たとえzやρが定数（例えばz=1、ρ＝１）であったとしても再暗号化された暗号文ct(1,2)を生成することはできる。しかし、z及びρを乱数とすることで再暗号化鍵Obf(rk_1→2)を含む再暗号化コードが難読化される。比較のため、まずz=1の場合を想定する。
z=1の場合、再暗号化鍵Obf(rk_1→2)はZ₁=h(2)^a(2)/a(1)， Z₂=h(2)^b(2)/b(1)， Z₃=h(2)， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含む。攻撃者ADVは、再暗号化鍵Obf(rk_1→2)及び第１復号装置の公開鍵を用い、以下を計算することができる。
e₁(h(2)^a(2)/a(1)，h(1)^a(1))=e₁(h(2)^a(2)，h(1))=Υ …(49)
そのため攻撃者ADVは、Υ=e₁(h(2)^KEY，h(1))を満たすKEYを探索して秘密鍵a(2)に関する情報を得ることができる。一方、再暗号化鍵Obf(rk_1→2)を持たないシミュレータSIMは式(49)の計算によってΥを求めることができず、KEYを探索して秘密鍵a(2)に関する情報を得ることができない。従って式(48)が満たされず、再暗号化鍵Obf(rk_1→2)を含む再暗号化コードは難読化されたといえない。
【００５６】
次に、zが乱数であると仮定する。乱数zに対するZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含む再暗号化鍵Obf(rk_1→2)の場合、攻撃者ADVは、再暗号化鍵Obf(rk_1→2)及び第１復号装置の公開鍵を用い、以下を計算することができる。
e₁(h(2)^{a(2)・z/a(1)}，h(1)^a(1))=e₁(h(2)^a(2)・z，h(1))=Υ’ …(50)
攻撃者ADVは、Υ’=e₁(h(2)^KEY・z，h(1))を満たすKEY・zを探索することはできるが、zが乱数であるため、Computational Diffie-Hellman仮定が真なのであれば、秘密鍵a(2)に関する情報を得ることができない。同様に攻撃者ADVは、z及びρが乱数で或る場合には、再暗号化鍵Obf(rk_1→2)のその他の要素について秘密鍵b(2)やn次元ベクトルv^→などの秘密情報を得ることができない。従ってz及びρが乱数である場合には式(48)が満たされ、条件(III)が満たされる。再暗号化鍵Obf(rk_1→2)を含む再暗号化コードは、その他の条件(I)(II)も満たすため、難読化されたといえる。
【００５７】
＜安全性＞
本実施形態では高い安全性を有する再暗号化方式を実現できる。特に、RV^→=(RV_ι(1),...,RV_ι(3・n+2))であり、１個のRV_κ∈{RV_ι(n+1), RV_ι(n+2)}が1∈F_qであり、RV_κ以外の１個のRV_φ∈{RV_ι(n+1), RV_ι(n+2)}が0∈F_qであり、RV_ε(1),...,RV_ε(n)∈{RV_ι(n+3),...,RV_ι(3・n+2)}が乱数η_ε(1),...,η_ε(n)∈F_qであり、RV_ε(1),...,RV_ε(n)以外のn個のRV_υ(1),...,RV_υ(n)∈{RV_ι(n+3),...,RV_ι(3・n+2)}のそれぞれが0∈F_qであり、CV^→=(CV_ι(1),...,CV_ι(3・n+2))であり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、１個のCV_κ∈{CV_ι(n+1), CV_ι(n+2)}が乱数ζであり、CV_κ以外の１個のCV_φ∈{CV_ι(n+1), CV_ι(n+2)}が暗号化装置によって選択された乱数ψ∈F_qであり、2・n個のCV_ι(n+3),...,CV_ι(3・n+2)のそれぞれが0であり、REV^→=(REV_ι(1),...,REV_ι(3・n+2))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(3・n+2)}が乱数ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(3・n+2)が0∈F_qである場合（例えば式(32)(35)(36)を満たす場合）、判定線形仮定(DLIN仮定)及び強Diffe-Hellman識別仮定(SDHI仮定)が真であれば、IND-CPA安全であるといえる。
【００５８】
〔実施形態〕
次に、図面を参照して実施形態を説明する。
＜構成＞
図１に例示するように、本形態のセキュリティシステム１は、例えば、パラメータ生成装置１１、暗号化装置１２、復号装置１３,１４（第１，２復号装置）、難読化装置１５及び再暗号化装置１６を有し、これらはネットワークを通じて通信可能に構成されている。本形態では、説明の便宜上、１個のパラメータ生成装置、暗号化装置、難読化装置及び再暗号化装置並びに２個の復号装置を有するセキュリティシステムを例示するが、セキュリティシステムが、より多くのパラメータ生成装置、暗号化装置、難読化装置、再暗号化装置及び復号装置を有していてもよい。或いは、パラメータ生成装置と難読化装置が同一の装置であってもよいし、難読化装置と何れかの復号装置とが同一の装置であってもよい。パラメータ生成装置１１、暗号化装置１２、復号装置１３,１４（第１，２復号装置）、難読化装置１５及び再暗号化装置１６のそれぞれは、例えば、CPU(central processing unit), RAM(random-access memory), ROM(read-only memory)等から構成される公知又は専用のコンピュータに特別なプログラムが読み込まれることで構成される特別な装置である。
【００５９】
［暗号化装置１２］
図２に例示するように、本形態の暗号化装置１２は、入力部１２ａ、インタフェース部１２ｂ、一時メモリ１２ｃ、記憶部１２ｄ、制御部１２ｅ、モード切り替え部２１ｆ、選択部１２ｇ，１２ｈ、及び、暗号化部１２ｉ，１２ｊを有する。暗号化装置１２は制御部１２ｅの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ１２ｃに格納され、一時メモリ１２ｃに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。
【００６０】
［復号装置１３］
図３に例示するように、本形態の復号装置１３は、出力部１３ａ、インタフェース部１３ｂ、一時メモリ１３ｃ、記憶部１３ｄ、制御部１３ｅ、選択部１３ｆ、公開鍵生成部１３ｇ〜１３ｋ、モード切り替え部１３ｍ、及び、復号部１３ｎ，１３ｐを有する。復号装置１３は制御部１３ｅの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ１３ｃに格納され、一時メモリ１３ｃに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。
【００６１】
［復号装置１４］
図４に例示するように、本形態の復号装置１４は、出力部１４ａ、インタフェース部１４ｂ、一時メモリ１４ｃ、記憶部１４ｄ、制御部１４ｅ、選択部１４ｆ、公開鍵生成部１４ｇ〜１４ｋ、モード切り替え部１４ｍ、及び、復号部１４ｎ，１４ｐを有する。復号装置１４は制御部１４ｅの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ１４ｃに格納され、一時メモリ１４ｃに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。
【００６２】
［難読化装置１５］
図５に例示するように、本形態の難読化装置１５は、入力部１５ａ、インタフェース部１５ｂ、一時メモリ１５ｃ、記憶部１５ｄ、制御部１５ｅ、選択部１５ｆ，１５ｇ、及び、再暗号化鍵生成部１５ｈ，１５ｉ，１５ｊを有する。難読化装置１５は制御部１５ｅの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ１５ｃに格納され、一時メモリ１５ｃに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。
【００６３】
［再暗号化装置１６］
図６に例示するように、本形態の再暗号化装置１６は、インタフェース部１６ａ，１６ｂ、一時メモリ１６ｃ、記憶部１６ｄ、制御部１６ｅ、選択部１６ｆ，１６ｉ、群演算部１６ｇａ〜１６ｇｅ、双線形写像演算部１６ｈａ〜１６ｈｅ、及び、再暗号化部１６ｊａ〜１６ｊｅを有する。再暗号化装置１６は制御部１６ｅの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ１６ｃに格納され、一時メモリ１６ｃに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。
【００６４】
＜処理＞
本形態の処理を説明する。本形態では、暗号化装置１２が復号装置１３で復号可能な暗号文が作成される例を説明する。暗号化装置１２で作成された暗号文は、そのまま復号装置１３で復号されるか、再暗号化装置１６で復号装置１４が復号可能な暗号文に再暗号化された後、復号装置１４で復号される。
［パラメータ生成］
本形態のパラメータ生成装置１１は、前述のようにシステムパラメータcrsを生成し、ネットワークを通じて送信する。システムパラメータcrsは、暗号化装置１２、復号装置１３,１４、難読化装置１５及び再暗号化装置１６それぞれのインタフェース部１２ｂ，１３ｂ，１４ｂ，１５ｂ，１６ｂで受信され、それぞれの記憶部１２ｄ，１３ｄ，１４ｄ，１５ｄ，１６ｄに格納される。暗号化装置１２、復号装置１３,１４、難読化装置１５及び再暗号化装置１６のそれぞれは、必要に応じて記憶部１２ｄ，１３ｄ，１４ｄ，１５ｄ，１６ｄに格納されたシステムパラメータcrsを読み出して利用する。難読化装置１５の記憶部１５ｄには、さらにシステムパラメータ生成時に生成された正則行列Xが格納される。
【００６５】
［秘密鍵及び公開鍵の生成］
図７Ａに例示するように、復号装置１３（図３）の選択部１３ｆが、乱数a(1), b(1), c(1), τ(1)←^U F_q^×を一様ランダムに選択し、これらを復号装置１３の秘密鍵sk(1)=(a(1), b(1), c(1), τ(1))として記憶部１３ｄに格納する（ステップＳ１０１）。
公開鍵生成部１３ｇ〜１３ｋは、記憶部１３ｄに格納された秘密鍵sk(1)及びシステムパラメータcrsを用い、それぞれh(1)=g^τ(1)∈G, h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^を計算し、それらを復号装置１３の公開鍵pk(1)=(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))として記憶部１３ｄに格納する（ステップＳ１０２〜Ｓ１０６）。公開鍵pk(1)は、必要に応じてインタフェース部１３ｂから他の装置に対して送信される。秘密鍵sk(1)は一般に公開されないが、難読化装置１５のみに対して秘密鍵sk(1)が与えられ、秘密鍵sk(1)が難読化装置１５の記憶部１５ｄに格納される。
【００６６】
図７Ｂに例示するように、復号装置１４（図４）の選択部１４ｆが、乱数a(2), b(2), c(2), τ(2)←^U F_q^×を一様ランダムに選択し、これらを復号装置１４の秘密鍵sk(2)=(a(2), b(2), c(2), τ(2))として記憶部１４ｄに格納する（ステップＳ１１１）。
公開鍵生成部１４ｇ〜１４ｋは、記憶部１４ｄに格納された秘密鍵sk(2)及びシステムパラメータcrsを用い、それぞれh(2)=g^τ(2)∈G, h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^を計算し、それらを復号装置１４の公開鍵pk(2)=(h(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2))として記憶部１４ｄに格納する（ステップＳ１１２〜Ｓ１１６）。公開鍵pk(2)は、必要に応じてインタフェース部１４ｂから他の装置に対して送信される。
【００６７】
［再暗号化鍵の生成］
難読化装置１５（図５）は、ネットワーク及びインタフェース部１３ｂを介して公開鍵pk(2)を取得し、それを記憶部１５ｄに格納する。さらにn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿが入力部１５ａに入力される。図７Ｃに例示するように、難読化装置１５の選択部１５ｆが、乱数z, ρ, σ←^U F_q^×を一様ランダムに選択し（ステップＳ１２１）、選択部１５ｇが、乱数η_ε(1),...,η_ε(n)∈←^U F_qを一様ランダムに選択する。前述のように、乱数η^→=(η_ε(1),...,η_ε(n)）の一例はη^→=(η_2・n+2,...,η_3・n+1）である（ステップＳ１２２）。再暗号化鍵生成部１５ｈは、記憶部１５ｄに格納されたシステムパラメータcrsと正則行列Xと公開鍵pk(2)とを用い、前述のB(2)’=c(2)・τ(2)・B（前述の式(34)では乗法的に表記）を生成する（ステップＳ１２３）。B(2)’は再暗号化鍵生成部１５ｉに入力される。再暗号化鍵生成部１５ｉは、B(2)’と記憶部１５ｄに格納されたシステムパラメータcrsと正則行列Xと秘密鍵sk(1)とを用い、前述のように（式(33)(34)参照）B(1,2)^*=(ρ/c(1))・c(2)・τ(2)B^*を計算する（ステップＳ１２４）。再暗号化鍵生成部１５ｊは、入力されたn次元ベクトルv^→と乱数z, ρ, σと乱数η^→と、記憶部１５ｄに格納されたシステムパラメータcrsと公開鍵pk(2)とを用い、前述のように、Z₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*からなる再暗号化鍵Obf(rk_1→2)を生成する。前述のように、RV^→の一例はRV^→=(σ・v^→，0ⁿ，1,η^→，0)である（ステップＳ１２５）。
生成された再暗号化鍵Obf(rk_1→2)は、インタフェース部１５ｂに送られ、ネットワークを介して再暗号化装置１６に送られる。再暗号化鍵Obf(rk_1→2)は、再暗号化装置１６（図６）のインタフェース部１６ｂで受信され、記憶部１６ｄに格納される。
【００６８】
［暗号化処理］
暗号化装置１２（図２）は、ネットワーク及びインタフェース部１２ｂを介して公開鍵pk(1)を取得し、それを記憶部１２ｄに格納する。図８に例示するように、暗号化装置１２の入力部１２ａに、モード選択パラメータβ∈{0,1}、n次元ベクトルx^→=(x_ι(1),...,x_ι(n))∈F_qⁿ、及びメッセージm∈Gが入力される（ステップＳ１３１）。選択部１２ｇは、乱数r,s,ζ,ω,ψ←^U F_qを一様ランダムに選択する（ステップＳ１３２）。モード切り替え部１２ｆは、入力されたモード選択パラメータβに応じて暗号化方法を選択する（ステップＳ１３３）。β=0であった場合、モード切り替え部１２ｆは第１モードの暗号化方法を選択する。この場合、暗号化部１２ｉが、記憶部１２ｄに格納されたシステムパラメータcrsと公開鍵pk(1)と、入力されたn次元ベクトルx^→=(x_ι(1),...,x_ι(n))とメッセージmと乱数r,s,ζ,ω,ψとを用い、暗号文ct(0,1)=[0, W(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζ]を生成する。前述のようにCV^→の一例は、CV^→=(ω・x^→，0ⁿ，ζ，0ⁿ，ψ)である（ステップＳ１３４）。β=1であった場合、モード切り替え部１２ｆは第２モードの暗号化方法を選択する。この場合、まず、選択部１２ｈが乱数t, t^~←^U Gを一様ランダムに選択する（ステップＳ１３５）。次に、暗号化部１２ｊが、記憶部１２ｄに格納されたシステムパラメータcrsと公開鍵pk(1)と、入力されたn次元ベクトルx^→=(x_ι(1),...,x_ι(n))とメッセージmと乱数r,s,ζ,t, t^~とを用い、暗号文ct(1,1)=[1, E(1,1)=e₁((h(1)^a(1))^r, t),F(1,1)=e₁((h(1)^b(1))^s, t),G(1,1)=e₁((h(1)^r+s・m, t))・e₁(t^~, (h(1)^c(1))^ζ), Z(1,1)=t, H(1,1)=e₁(t^~, h(1)^ζ)] を生成する（ステップＳ１３６）。生成された暗号文ct(β,1)(β∈{0,1})はインタフェース部１３に送られ、そこから送信（出力）される。β=0の場合に生成された暗号文ct(0,1)は、ネットワークを介して復号装置１３又は再暗号化装置１６に送信され、若しくは、復号装置１３に送信された後に再暗号化装置１６に転送される。β=1の場合に生成された暗号文ct(1,1)は、ネットワークを介して復号装置１３に送信される（ステップＳ１３７）。
【００６９】
［再暗号化処理］
暗号文ct(0,1)が再暗号化装置１６（図６）に送信又は転送された場合、図９に示すように、インタフェース部１２ｂで暗号文ct(0,1)が受信され（暗号文ct(0,1)の入力を受け付け）、暗号文ct(0,1)が記憶部１６ｄに格納される。さらに再暗号化装置１６は、ネットワーク及びインタフェース部１２ｂを介して公開鍵pk(1)を取得し、それを記憶部１６ｄに格納する（ステップＳ１４１）。選択部１６ｆが、乱数r’, s’, ζ’←^U F_qを一様ランダムに選択する（ステップＳ１４２）。群演算部１６ｇａ〜１６ｇｅは、入力された乱数r’, s’, ζ’と、記憶部１６に格納されたシステムパラメータcrsと暗号文ct(0,1)と公開鍵pk(1)とを用い、W’=W(0,1)・(h(1)^a(1))^r’,Θ’=Θ(0,1)・(h(1)^b(1))^s’,Y’=Y(0,1)・h(1)^r’+s’,U’=U(0,1)+(REV^→)_B(1),Λ’=Λ(0,1)・h(1)^ζ’をそれぞれ計算する（ステップＳ１４３〜１４７）。双線形写像演算部１６ｈａ〜１６ｈｅが、入力されたW’,Θ’,Y’,U’,Λ’と、記憶部１６ｄに格納されたシステムパラメータcrsと再暗号化鍵Obf(rk_1→2)とを用い、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)をそれぞれ計算する（ステップＳ１４８〜Ｓ１５２）。選択部１６ｉは、乱数y, y’←^U F_q^×を一様ランダムに選択する（ステップＳ１５３）。再暗号化部１６ｊａ〜１６ｊｅは、入力されたΨ₁=, Ψ₂, Ψ₃, Ω₁, Ω₂と乱数y, y’とを用い、E(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’をそれぞれ計算する（ステップＳ１５３〜Ｓ１５９）。インタフェース部１６ａは、暗号文ct(1,2)=[1, E(1,2), F(1,2), G(1,2), Z(1,2), H(1,2)]を送信（出力）する。暗号文ct(1,2)はネットワークを介して復号装置１４に送信される（ステップＳ１６０）。
【００７０】
［復号処理］
暗号文ct(β,1)(β∈{0,1})が復号装置１３（図３）に送信されると、図１０Ａに例示するように、暗号文ct(β,1)が復号装置１３のインタフェース部１３ｂに受信（入力）される（ステップＳ１６１）。モード切り替え部１３ｍは、暗号文ct(β,1)=[β,....]の先頭に位置する「β」が0であるかを判定する（ステップＳ１６２）。β=0であれば、復号部１３ｎは、入力された暗号文ct(0,1)と記憶部１３ｄに格納された秘密鍵sk(1)とを用い、m’=Y(0,1)/(W(0,1)^1/a(1)・Θ(0,1)^1/b(1))を復号値として計算し（ステップＳ１６３）、出力部１３ａが復号値m’を出力する（ステップＳ１６５）。β=1であれば、復号部１３ｐは、入力された暗号文ct(1,1)と記憶部１３ｄに格納された秘密鍵sk(1)とを用い、e₁(m’, Z(1,1))=G(1,1)/{H(1,1)^c(1)・E(1,1)^1/a(1)・F(1,1)^1/b(1)}を満たすm’∈Gを復号値として計算し（ステップＳ１６４）、出力部１３ａが復号値m’を出力する（ステップＳ１６５）。
【００７１】
［復号処理］
暗号文ct(β,2)(β∈{0,1})が復号装置１４（図４）に送信されると、図１０Ｂに例示するように、暗号文ct(β,2)が復号装置１４のインタフェース部１４ｂに受信（入力）される（ステップＳ１７１）。モード切り替え部１４ｍは、暗号文ct(β,2)=[β,....]の先頭に位置する「β」が0であるかを判定する（ステップＳ１７２）。β=0であれば、復号部１４ｎは、入力された暗号文ct(0,2)=[0, W(0,2)=(h(2)^a(2))^r, Θ(0,2)=(h(2)^b(2))^s, Y(0,2)=h(2)^r+s・m,U(0,2)=(CV^→)_B(1), Λ(0,2)=h(2)^ζ]と、記憶部１４ｄに格納された秘密鍵sk(2)とを用い、m’=Y(0,2)/(W(0,2)^1/a(2)・Θ(0,2)^1/b(2))を復号値として計算し（ステップＳ１７３）、出力部１４ａが復号値m’を出力する（ステップＳ１７５）。β=1であれば、復号部１４ｐは、入力された暗号文ct(1,2)と記憶部１４ｄに格納された秘密鍵sk(2)とを用い、e₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2)^1/b(2)}を満たすm’∈Gを復号値として計算し（ステップＳ１７４）、出力部１４ａが復号値m’を出力する（ステップＳ１７５）。
【００７２】
〔変形例等〕
本発明は上述の実施形態に限定されるものではない。例えば、上述の実施形態では、安全性の観点から乱数として一様ランダムな値が用いられたが、用途や利用環境によっては一様ランダムではない乱数が用いられてもよい。また、乱数とは真性乱数及び擬似乱数の両方を含む概念であり、乱数として真性乱数が用いられてもよいし、擬似乱数が用いられてもよい。さらに上述の実施形態で扱った乱数（例えば、t, t^~,ρ, σ, r, s, ζ, ω, r’, s’, ζ’, y, y’, z, η_ε(1),...,η_ε(n)）の少なくとも一部が、予め定められた候補の中から選択された値であったり、定数であったりしてもよい。上述のように巡回群G, G_Tの位数が有限体F_qの位数qと同一である場合に高い安全性を確保できるが、用途によっては巡回群G, G_Tの位数が有限体F_qの位数と異なっていてもよい。上述の実施形態では、qが素数であって有限体F_qが素体である例を示したが、有限体F_qが拡大体であってもよい。上記の実施形態では、各装置がネットワークを経由して情報を通信する例を示したが、装置間の情報通信の少なくとも一部が、可搬型記録媒体を介した情報のやり取りに置換されてもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７３】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００７４】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７６】
この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７７】
１ セキュリティシステム
１１ パラメータ生成装置
１２ 暗号化装置
１３，１４ 復号装置
１５ 難読化装置
１６ 再暗号化装置

【特許請求の範囲】
【請求項１】
暗号化装置と第１復号装置と第２復号装置と再暗号化装置とを有するセキュリティシステムであって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、前記第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、前記第２復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記第２復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、
前記暗号化装置は、
r, s, ζ, ω∈F_qを選択する第１選択部と、
前記第１復号装置の公開鍵(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))とn次元ベクトルx^→=(x_ι(1),...,x_ι(n))∈F_qⁿとを用い、メッセージm∈Gの第１暗号文ct(0,1)を生成する第１暗号化部と、を含み、
前記第１暗号文ct(0,1)がW(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含み、CV^→がn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}が前記ζであり、CV_ι(n+1),...,CV_ι(Γ)からCV_κを除いた要素からなるベクトルとRV_ι(n+1),...,RV_ι(Γ)からRV_κを除いた要素からなるベクトルとの内積が0であり、
前記再暗号化装置は、
r’, s’, ζ’∈F_qを選択する第２選択部と、
W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’を得る群演算部と、
Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)を得る双線形写像演算部と、
y, y’∈F_q^×に対するE(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)を生成する再暗号化部と、を含み、
REV^→がn+μ次元ベクトルREV^→=(REV_ι(1),...,REV_ι(n+μ))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(n+μ)}が前記ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(n+μ)が0∈F_qであり、
前記第２復号装置は、
e₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2) ^1/b(2)}
を満たすm’∈Gを復号値として得る第２復号部を含む、セキュリティシステム。
【請求項２】
請求項１のセキュリティシステムであって、
前記ｚ及びρが乱数である、セキュリティシステム。
【請求項３】
請求項１又は２のセキュリティシステムであって、
前記暗号化装置は、さらに、
t, t^~∈Gを選択する第３選択部と、
E(1,1)=e₁((h(1)^a(1))^r, t), F(1,1)=e₁((h(1)^b(1))^s, t), G(1,1)=e₁((h(1)^r+s・m, t))・e₁(t^~, (h(1)^c(1))^ζ), Z(1,1)=t, H(1,1)=e₁(t^~, h(1)^ζ)を含む第２暗号文ct(1,1)を生成する第２暗号化部と、を含む、セキュリティシステム。
【請求項４】
請求項３のセキュリティシステムであって、
前記第１復号装置は、入力暗号文として前記第１暗号文ct(0,1)が得られた場合にm’=Y(0,1)/(W(0,1)^1/a(1)・Θ(0,1)^1/b(1))を復号値として得、入力暗号文として前記第２暗号文ct(1,1)が得られた場合にe₁(m’, Z(1,1))=G(1,1)/{H(1,1)^c(1)・E(1,1)^1/a(1)・F(1,1)^1/b(1)}を満たすm’∈Gを復号値として得る第１復号部を含む、セキュリティシステム。
【請求項５】
請求項３又は４のセキュリティシステムであって、
t, t^~∈Gが乱数である、セキュリティシステム。
【請求項６】
請求項１から５の何れかのセキュリティシステムであって、
前記ρ, σ, r, s, ζ, ω, r’, s’, ζ’, y, y’が乱数である、セキュリティシステム。
【請求項７】
請求項１から６の何れかのセキュリティシステムであって、
前記巡回群G, G_Tの位数がqである、セキュリティシステム。
【請求項８】
請求項１から７の何れかのセキュリティシステムであって、
μ=2・n+2であり、Γ=n+2であり、B^=(b_ι(1),...,b_ι(n+2))であり、{ι(n+3),...,ι(3・n+2)}⊂{1,...,3・n+2}であり、RV^→が3・n+2次元ベクトルRV^→=(RV_ι(1),...,RV_ι(3・n+2))であり、１個のRV_κ∈{RV_ι(n+1), RV_ι(n+2)}が1であり、RV_κ以外の１個のRV_φ∈{RV_ι(n+1), RV_ι(n+2)}が0であり、n個のRV_ε(1),...,RV_ε(n)∈{RV_ι(n+3),...,RV_ι(3・n+2)}が乱数η_ε(1),...,η_ε(n)∈F_qであり、RV_ε(1),...,RV_ε(n)以外のn個のRV_υ(1),...,RV_υ(n)∈{RV_ι(n+3),...,RV_ι(3・n+2)}のそれぞれが0であり、CV^→が3・n+2次元ベクトルCV^→=(CV_ι(1),...,CV_ι(3・n+2))であり、１個のCV_κ∈{CV_ι(n+1), CV_ι(n+2)}が前記ζであり、CV_κ以外の１個のCV_φ∈{CV_ι(n+1), CV_ι(n+2)}が乱数ψ∈F_qであり、2・n個のCV_ι(n+3),...,CV_ι(3・n+2)のそれぞれが0である、セキュリティシステム。
【請求項９】
選択部と暗号化部とを有する暗号化装置であって、
Gが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_qⁿに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、
前記選択部が、r, s, ζ, ω∈F_qを選択し、
前記暗号化部が、前記第１復号装置の公開鍵(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))とn次元ベクトルx^→=(x_ι(1),...,x_ι(n))∈F_qⁿとを用い、メッセージm∈Gの第１暗号文ct(0,1)を生成し、前記第１暗号文ct(0,1)がW(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含み、CV^→がn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}が前記ζである、暗号化装置。
【請求項１０】
インタフェース部と復号部とを有する復号装置であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=( b_ι(1),...,b_ι(Γ))であり、当該復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、当該復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、他の復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記他の復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、
前記インタフェース部が、W(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含む第１暗号文ct(0,1)、又は、E(1,1)=e₁((h(1)^a(1))^r, t), F(1,1)=e₁((h(1)^b(1))^s, t), G(1,1)=e₁((h(1)^r+s・m, t))・e₁(t^~, (h(1)^c(1))^ζ), Z(1,1)=t, H(1,1)=e₁(t^~, h(1)^ζ)を含む第２暗号文ct(1,1)である入力暗号文の入力を受け付け、CV^→がn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}が前記ζであり、CV_ι(n+1),...,CV_ι(Γ)からCV_κを除いた要素からなるベクトルとRV_ι(n+1),...,RV_ι(Γ)からRV_κを除いた要素からなるベクトルとの内積が0であり、
前記復号部が、入力暗号文として前記第１暗号文ct(0,1)が前記インタフェース部に入力された場合にm’=Y(0,1)/(W(0,1)^1/a(1)・Θ(0,1)^1/b(1))を復号値として得、入力暗号文として前記第２暗号文ct(1,1)が前記インタフェース部に入力された場合にe₁(m’, Z(1,1))=G(1,1)/{H(1,1)^c(1)・E(1,1)^1/a(1)・F(1,1)^1/b(1)}を満たすm’∈Gを復号値として得る、復号装置。
【請求項１１】
インタフェース部と復号部とを有する復号装置であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、当該復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、当該復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、他の復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記他の復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’であり、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)であり、REV^→がn+μ次元ベクトルREV^→=(REV_ι(1),...,REV_ι(n+μ))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(n+μ)}が前記ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(n+μ)が0∈F_qであり、
前記インタフェース部が、E(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)の入力を受け付け、
前記復号部が、e₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2) ^1/b(2)}
を満たすm’∈Gを復号値として得る、復号装置。
【請求項１２】
選択部と群演算部と双線形写像演算部と再暗号化部とを有する再暗号化装置であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、第２復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記第２復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、
前記選択部が、r’, s’, ζ’∈F_qを選択し、
前記群演算部が、W(0,1), Θ(0,1), Y(0,1), U(0,1), Λ(0,1)を含む第１暗号文ct(0,1)に対して、W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’を得、REV^→がn+μ次元ベクトルREV^→=(REV_ι(1),...,REV_ι(n+μ))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(n+μ)}が前記ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(n+μ)が0∈F_qであり、
前記双線形写像演算部が、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)を得、
前記再暗号化部が、y, y’∈F_q^×に対するE(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)を生成する、再暗号化装置。
【請求項１３】
選択部と再暗号化鍵生成部とを有する難読化装置であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、第２復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記第２復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、
前記選択部が、z, ρ, σ∈F_q^×を生成し、
前記再暗号化鍵生成部が、n次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿに対して、Z₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含む再暗号化鍵を生成し、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1である、難読化装置。
【請求項１４】
請求項１３の難読化装置であって、
前記z及びρが乱数である、難読化装置。
【請求項１５】
暗号化装置で、r, s, ζ, ω∈F_qを選択するステップと、
前記暗号化装置で、第１復号装置の公開鍵(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))とn次元ベクトルx^→=(x_ι(1),...,x_ι(n))∈F_qⁿとを用い、メッセージm∈Gの第１暗号文ct(0,1)を生成するステップと、
再暗号化装置で、r’, s’, ζ’∈F_qを選択するステップと、
前記再暗号化装置で、W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’を得るステップと、
前記再暗号化装置で、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)を得るステップと、
前記再暗号化装置で、y, y’∈F_q^×に対するE(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)を生成するステップと、
第２復号装置で、e₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2) ^1/b(2)}を満たすm’∈Gを復号値として得るステップと、を有し、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、前記第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、前記第２復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記第２復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、前記第１暗号文ct(0,1)がW(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含み、CV^→がn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}が前記ζであり、CV_ι(n+1),...,CV_ι(Γ)からCV_κを除いた要素からなるベクトルとRV_ι(n+1),...,RV_ι(Γ)からRV_κを除いた要素からなるベクトルとの内積が0であり、REV^→がn+μ次元ベクトルREV^→=(REV_ι(1),...,REV_ι(n+μ))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(n+μ)}が前記ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(n+μ)が0∈F_qである、セキュリティ方法。
【請求項１６】
選択部と暗号化部とを有する暗号化装置が実行する暗号化方法であって、
Gが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、
前記選択部で、r, s, ζ, ω∈F_qを選択するステップと、
前記暗号化部で、前記第１復号装置の公開鍵(h(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1))とn次元ベクトルx^→=(x_ι(1),...,x_ι(n))∈F_qⁿとを用い、メッセージm∈Gの第１暗号文ct(0,1)を生成するステップと、を有し、
前記第１暗号文ct(0,1)がW(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含み、CV^→がn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}が前記ζである暗号化方法。
【請求項１７】
インタフェース部と復号部とを有する復号装置が実行する復号方法であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、当該復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、当該復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、他の復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記他の復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、
前記インタフェース部で、W(0,1)=(h(1)^a(1))^r, Θ(0,1)=(h(1)^b(1))^s, Y(0,1)=h(1)^r+s・m,U(0,1)=(CV^→)_B(1), Λ(0,1)=h(1)^ζを含む第１暗号文ct(0,1)、又は、E(1,1)=e₁((h(1)^a(1))^r, t), F(1,1)=e₁((h(1)^b(1))^s, t), G(1,1)=e₁((h(1)^r+s・m, t))・e₁(t^~, (h(1)^c(1))^ζ), Z(1,1)=t, H(1,1)=e₁(t^~, h(1)^ζ)を含む第２暗号文ct(1,1)である入力暗号文の入力を受け付けるステップと、
入力暗号文として前記第１暗号文ct(0,1)が前記インタフェース部に入力された場合に、前記復号部で、m’=Y(0,1)/(W(0,1)^1/a(1)・Θ(0,1)^1/b(1))を復号値として得、入力暗号文として前記第２暗号文ct(1,1)が前記インタフェース部に入力された場合に、前記復号部で、e₁(m’, Z(1,1))=G(1,1)/{H(1,1)^c(1)・E(1,1)^1/a(1)・F(1,1)^1/b(1)}を満たすm’∈Gを復号値として得るステップと、を有し、
CV^→がn+μ次元ベクトルCV^→=(CV_ι(1),...,CV_ι(n+μ))∈F_q^n+μであり、(CV_ι(1),...,CV_ι(n))がn次元ベクトルω・x^→=(ω・x_ι(1),...,ω・x_ι(n))であり、何れか１個のCV_κ∈{CV_ι(n+1),...,CV_ι(Γ)}が前記ζであり、CV_ι(n+1),...,CV_ι(Γ)からCV_κを除いた要素からなるベクトルとRV_ι(n+1),...,RV_ι(Γ)からRV_κを除いた要素からなるベクトルとの内積が0である、復号方法。
【請求項１８】
インタフェース部と復号部とを有する復号装置が実行する復号方法であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、当該復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、当該復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、他の復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記他の復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’であり、REV^→がn+μ次元ベクトルREV^→=(REV_ι(1),...,REV_ι(n+μ))∈F_q^n+μであり、何れか１個のREV_κ∈{REV_ι(1),...,REV_ι(n+μ)}が前記ζ’であり、REV_κを除くREV_ι(1),...,REV_ι(n+μ)が0∈F_qであり、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)であり、
前記インタフェース部で、E(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)の入力を受け付けるステップと、
前記復号部で、e₁(m’, Z(1,2))=G(1,2)/{H(1,2)^c(2)・E(1,2)^1/a(2)・F(1,2) ^1/b(2)}
を満たすm’∈Gを復号値として得るステップと、を有する復号方法。
【請求項１９】
選択部と群演算部と双線形写像演算部と再暗号化部とを有する再暗号化装置が実行する再暗号化方法であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、第２復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記第２復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、z, ρ, σ∈F_q^×であり、v^→がn次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿであり、B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、再暗号化鍵がZ₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含み、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1であり、ξが１以上の整数であり、e_ξが直積群G^ξ×G^ξの元に対して前記巡回群G_Tの元を得る双線形写像であり、
前記選択部で、r’, s’, ζ’∈F_qを選択するステップと、
前記群演算部で、W(0,1), Θ(0,1), Y(0,1), U(0,1), Λ(0,1)を含む第１暗号文ct(0,1)に対して、W’=W(0,1)・(h(1)^a(1))^r’, Θ’=Θ(0,1)・(h(1)^b(1))^s’, Y’=Y(0,1)・h(1)^r’+s’, U’=U(0,1)+(REV^→)_B(1), Λ’=Λ(0,1)・h(1)^ζ’を得るステップと、
前記双線形写像演算部で、Ψ₁=e₁(W’,Z₁), Ψ₂=e₁(Θ’,Z₂), Ψ₃=e₁(Y’,Z₃), Ω₁=e_n+μ(U’,k^*), Ω₂=e₁(Λ’,k₀)を得るステップと、
前記再暗号化部で、y, y’∈F_q^×に対するE(1,2)=Ψ₁^y, F(1,2)=Ψ₂^y, G(1,2)=Ψ₃^y・Ω₁^y’, Z(1,2)=Z₃^y, H(1,2)=Ω₂^y’を含む再暗号文ct(1,2)を生成するステップと、
を有する再暗号化方法。
【請求項２０】
選択部と再暗号化鍵生成部とを有する難読化装置が実行する鍵難読化方法であって、
G, G_Tが巡回群であり、gが前記巡回群Gの生成元であり、F_qが位数qの有限体であり、F_q^×=F_q＼{0}であり、nが１以上の整数であり、μが２以上の整数であり、b_i∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B=(b₁,...,b_n+μ)がn+μ個の前記基底ベクトルb_i(i=1,...,n+μ)からなる基底であり、b_i^*∈G^n+μ(i=1,...,n+μ)のそれぞれが前記巡回群Gのn+μ個の元を要素とするn+μ次元の基底ベクトルであり、B^*=(b₁^*,...,b_n+μ^*)がn+μ個の前記基底ベクトルb_i^*(i=1,...,n+μ)からなる基底であり、前記基底Bと前記基底B^*とは双対直交基底であり、n+μ次元ベクトルd^→=(d₁,...,d_n+μ)∈F_q^n+μに対する(d^→)_BがΣ_i=1^n+μd_i・b_iであり、n+μ次元ベクトルf^→=(f₁,...,f_n+μ)∈F_q^n+μに対する(f^→)_B*がΣ_i=1^n+μf_i・b_i^*であり、Γがn+1≦Γ＜n+μの整数であり、{ι(1),...,ι(Γ)}⊂{1,...,n+μ}であり、B^=(b_ι(1),...,b_ι(Γ))であり、第１復号装置の秘密鍵がa(1), b(1), c(1), τ(1)∈F_q^×であり、前記第１復号装置の公開鍵が(h(1)=g^τ(1), h(1)^a(1), h(1)^b(1), h(1)^c(1), B(1)=c(1)・τ(1)・B^)であり、第２復号装置の秘密鍵がa(2), b(2), c(2), τ(2)∈F_q^×であり、前記第２復号装置の公開鍵が(h(2)=g^τ(2), h(2)^a(2), h(2)^b(2), h(2)^c(2), B(2)=c(2)・τ(2)・B^)であり、
前記選択部で、z, ρ, σ∈F_q^×を生成するステップと、
前記再暗号化鍵生成部で、n次元ベクトルv^→=(v_ι(1),...,v_ι(n))∈F_qⁿに対して、Z₁=(h(2)^a(2))^z/a(1)， Z₂=(h(2)^b(2))^z/b(1)， Z₃=h(2)^z， k₀=h(2)^ρ， k^*=(RV^→)_B(1,2)*を含む再暗号化鍵を生成するステップと、を有し、
B(1,2)^*=(ρ/c(1))・c(2)・τ(2)・B^*であり、RV^→がn+μ次元ベクトルRV^→=(RV_ι(1),...,RV_ι(n+μ))∈F_q^n+μであり、ι(i)∈{1,...,n+μ}(i=1,...,n+μ)であり、{ι(1),...,ι(n)}⊂{1,...,n+μ}であり、(RV_ι(1),..., RV_ι(n))がn次元ベクトルσ・v^→=(σ・v_ι(1),...,σ・v_ι(n))であり、何れか１個のRV_κ∈{RV_ι(n+1),...,RV_ι(Γ)}が1である、難読化方法。
【請求項２１】
請求項２０の難読化方法であって、
前記z及びρが乱数である、難読化方法。
【請求項２２】
請求項９の暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項２３】
請求項１０又は１１の復号装置としてコンピュータを機能させるためのプログラム。
【請求項２４】
請求項１２の再暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項２５】
請求項１３又は１４の難読化装置としてコンピュータを機能させるためのプログラム。

【図１】

【図２】

【図３】

【図４】

【図５】

【図６】

【図７】

【図８】

【図９】

【図１０】

【公開番号】特開２０１３−１０５０６５（Ｐ２０１３−１０５０６５Ａ）
【公開日】平成２５年５月３０日（２０１３．５．３０）
【国際特許分類】
【出願番号】特願２０１１−２４９４４１（Ｐ２０１１−２４９４４１）
【出願日】平成２３年１１月１５日（２０１１．１１．１５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】