"暗号化装置と第1復号装置と第2復号装置と再暗号化装置とを有するセキュリティシステムであって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、前記第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、前記第2復号装置の秘密鍵がabcτ∈Fq×であり、前記第2復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、前記暗号化装置は、rsζω∈Fqを選択する第1選択部と、前記第1復号装置の公開鍵hahbhcBとn次元ベクトルx→xι∈Fqnとを用い、メッセージm∈Gの第1暗号文ctを生成する第1暗号化部と、を含み、前記第1暗号文ctがWarΘbsYhrsmUBΛhζを含み、CV→がnμ次元ベクトルCV→CVι∈Fqnμであり、CVιがn次元ベクトルωx→ωxιであり、何れか1個のCVκ∈CVιCVιが前記ζであり、CVιCVιからCVκを除いた要素からなるベクトルとRVιRVιからRVκを除いた要素からなるベクトルとの内積が0であり、前記再暗号化装置は、r’s’ζ’∈Fqを選択する第2選択部と、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’を得る群演算部と、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1を得る双線形写像演算部と、yy’∈Fq×に対するEΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む再暗号文ctを生成する再暗号化部と、を含み、REV→がnμ次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが前記ζ’であり、REVκを除くREVιREVιが0∈Fqであり、前記第2復号装置は、e1GHcE1aF1bを満たすm’∈Gを復号値として得る第2復号部を含む、セキュリティシステム。請求項1のセキュリティシステムであって、前記z及びρが乱数である、セキュリティシステム。請求項1又は2のセキュリティシステムであって、前記暗号化装置は、さらに、tt∈Gを選択する第3選択部と、Ee1artFe1bstGe1rsmte1cζZtHe1ζを含む第2暗号文ctを生成する第2暗号化部と、を含む、セキュリティシステム。請求項3のセキュリティシステムであって、前記第1復号装置は、入力暗号文として前記第1暗号文ctが得られた場合にm’Y1aΘ1bを復号値として得、入力暗号文として前記第2暗号文ctが得られた場合にe1GHcE1aF1bを満たすm’∈Gを復号値として得る第1復号部を含む、セキュリティシステム。請求項3又は4のセキュリティシステムであって、tt∈Gが乱数である、セキュリティシステム。請求項1から5の何れかのセキュリティシステムであって、前記ρσrsζωr’s’ζ’yy’が乱数である、セキュリティシステム。請求項1から6の何れかのセキュリティシステムであって、前記巡回群GGTの位数がqである、セキュリティシステム。請求項1から7の何れかのセキュリティシステムであって、μ2n2であり、Γn2であり、Bbιであり、ιι⊂13n2であり、RV→が3n2次元ベクトルRV→RVιであり、1個のRVκ∈RVιRVιが1であり、RVκ以外の1個のRVφ∈RVιRVιが0であり、n個のRVεRVε∈RVιRVιが乱数ηεηε∈Fqであり、RVεRVε以外のn個のRVυRVυ∈RVιRVιのそれぞれが0であり、CV→が3n2次元ベクトルCV→CVιであり、1個のCVκ∈CVιCVιが前記ζであり、CVκ以外の1個のCVφ∈CVιCVιが乱数ψ∈Fqであり、2n個のCVιCVιのそれぞれが0である、セキュリティシステム。選択部と暗号化部とを有する暗号化装置であって、Gが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、nμ次元ベクトルd→∈Fqnに対するBがΣi1nμdibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、前記選択部が、rsζω∈Fqを選択し、前記暗号化部が、前記第1復号装置の公開鍵hahbhcBとn次元ベクトルx→xι∈Fqnとを用い、メッセージm∈Gの第1暗号文ctを生成し、前記第1暗号文ctがWarΘbsYhrsmUBΛhζを含み、CV→がnμ次元ベクトルCV→CVι∈Fqnμであり、CVιがn次元ベクトルωx→ωxιであり、何れか1個のCVκ∈CVιCVιが前記ζである、暗号化装置。インタフェース部と復号部とを有する復号装置であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、当該復号装置の秘密鍵がabcτ∈Fq×であり、当該復号装置の公開鍵がgτhahbhcBcτBであり、他の復号装置の秘密鍵がabcτ∈Fq×であり、前記他の復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、前記インタフェース部が、WarΘbsYhrsmUBΛhζを含む第1暗号文ct、又は、Ee1artFe1bstGe1rsmte1cζZtHe1ζを含む第2暗号文ctである入力暗号文の入力を受け付け、CV→がnμ次元ベクトルCV→CVι∈Fqnμであり、CVιがn次元ベクトルωx→ωxιであり、何れか1個のCVκ∈CVιCVιが前記ζであり、CVιCVιからCVκを除いた要素からなるベクトルとRVιRVιからRVκを除いた要素からなるベクトルとの内積が0であり、前記復号部が、入力暗号文として前記第1暗号文ctが前記インタフェース部に入力された場合にm’Y1aΘ1bを復号値として得、入力暗号文として前記第2暗号文ctが前記インタフェース部に入力された場合にe1GHcE1aF1bを満たすm’∈Gを復号値として得る、復号装置。インタフェース部と復号部とを有する復号装置であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、当該復号装置の秘密鍵がabcτ∈Fq×であり、当該復号装置の公開鍵がgτhahbhcBcτBであり、他の復号装置の秘密鍵がabcτ∈Fq×であり、前記他の復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’であり、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1であり、REV→がnμ次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが前記ζ’であり、REVκを除くREVιREVιが0∈Fqであり、前記インタフェース部が、EΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む再暗号文ctの入力を受け付け、前記復号部が、e1GHcE1aF1bを満たすm’∈Gを復号値として得る、復号装置。選択部と群演算部と双線形写像演算部と再暗号化部とを有する再暗号化装置であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、第2復号装置の秘密鍵がabcτ∈Fq×であり、前記第2復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、前記選択部が、r’s’ζ’∈Fqを選択し、前記群演算部が、WΘYUΛを含む第1暗号文ctに対して、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’を得、REV→がnμ次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが前記ζ’であり、REVκを除くREVιREVιが0∈Fqであり、前記双線形写像演算部が、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1を得、前記再暗号化部が、yy’∈Fq×に対するEΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む再暗号文ctを生成する、再暗号化装置。選択部と再暗号化鍵生成部とを有する難読化装置であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、第2復号装置の秘密鍵がabcτ∈Fq×であり、前記第2復号装置の公開鍵がgτhahbhcBcτBであり、前記選択部が、zρσ∈Fq×を生成し、前記再暗号化鍵生成部が、n次元ベクトルv→vι∈Fqnに対して、Z1aza,Z2bzb,Z3hz,k0hρ,kBを含む再暗号化鍵を生成し、BcτBであり、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1である、難読化装置。請求項13の難読化装置であって、前記z及びρが乱数である、難読化装置。暗号化装置で、rsζω∈Fqを選択するステップと、前記暗号化装置で、第1復号装置の公開鍵hahbhcBとn次元ベクトルx→xι∈Fqnとを用い、メッセージm∈Gの第1暗号文ctを生成するステップと、再暗号化装置で、r’s’ζ’∈Fqを選択するステップと、前記再暗号化装置で、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’を得るステップと、前記再暗号化装置で、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1を得るステップと、前記再暗号化装置で、yy’∈Fq×に対するEΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む再暗号文ctを生成するステップと、第2復号装置で、e1GHcE1aF1bを満たすm’∈Gを復号値として得るステップと、を有し、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、前記第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、前記第2復号装置の秘密鍵がabcτ∈Fq×であり、前記第2復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、前記第1暗号文ctがWarΘbsYhrsmUBΛhζを含み、CV→がnμ次元ベクトルCV→CVι∈Fqnμであり、CVιがn次元ベクトルωx→ωxιであり、何れか1個のCVκ∈CVιCVιが前記ζであり、CVιCVιからCVκを除いた要素からなるベクトルとRVιRVιからRVκを除いた要素からなるベクトルとの内積が0であり、REV→がnμ次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが前記ζ’であり、REVκを除くREVιREVιが0∈Fqである、セキュリティ方法。選択部と暗号化部とを有する暗号化装置が実行する暗号化方法であって、Gが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、前記選択部で、rsζω∈Fqを選択するステップと、前記暗号化部で、前記第1復号装置の公開鍵hahbhcBとn次元ベクトルx→xι∈Fqnとを用い、メッセージm∈Gの第1暗号文ctを生成するステップと、を有し、前記第1暗号文ctがWarΘbsYhrsmUBΛhζを含み、CV→がnμ次元ベクトルCV→CVι∈Fqnμであり、CVιがn次元ベクトルωx→ωxιであり、何れか1個のCVκ∈CVιCVιが前記ζである暗号化方法。インタフェース部と復号部とを有する復号装置が実行する復号方法であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、当該復号装置の秘密鍵がabcτ∈Fq×であり、当該復号装置の公開鍵がgτhahbhcBcτBであり、他の復号装置の秘密鍵がabcτ∈Fq×であり、前記他の復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、前記インタフェース部で、WarΘbsYhrsmUBΛhζを含む第1暗号文ct、又は、Ee1artFe1bstGe1rsmte1cζZtHe1ζを含む第2暗号文ctである入力暗号文の入力を受け付けるステップと、入力暗号文として前記第1暗号文ctが前記インタフェース部に入力された場合に、前記復号部で、m’Y1aΘ1bを復号値として得、入力暗号文として前記第2暗号文ctが前記インタフェース部に入力された場合に、前記復号部で、e1GHcE1aF1bを満たすm’∈Gを復号値として得るステップと、を有し、CV→がnμ次元ベクトルCV→CVι∈Fqnμであり、CVιがn次元ベクトルωx→ωxιであり、何れか1個のCVκ∈CVιCVιが前記ζであり、CVιCVιからCVκを除いた要素からなるベクトルとRVιRVιからRVκを除いた要素からなるベクトルとの内積が0である、復号方法。インタフェース部と復号部とを有する復号装置が実行する復号方法であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、当該復号装置の秘密鍵がabcτ∈Fq×であり、当該復号装置の公開鍵がgτhahbhcBcτBであり、他の復号装置の秘密鍵がabcτ∈Fq×であり、前記他の復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’であり、REV→がnμ次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが前記ζ’であり、REVκを除くREVιREVιが0∈Fqであり、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1であり、前記インタフェース部で、EΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む再暗号文ctの入力を受け付けるステップと、前記復号部で、e1GHcE1aF1bを満たすm’∈Gを復号値として得るステップと、を有する復号方法。選択部と群演算部と双線形写像演算部と再暗号化部とを有する再暗号化装置が実行する再暗号化方法であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、第2復号装置の秘密鍵がabcτ∈Fq×であり、前記第2復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して前記巡回群GTの元を得る双線形写像であり、前記選択部で、r’s’ζ’∈Fqを選択するステップと、前記群演算部で、WΘYUΛを含む第1暗号文ctに対して、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’を得るステップと、前記双線形写像演算部で、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1を得るステップと、前記再暗号化部で、yy’∈Fq×に対するEΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む再暗号文ctを生成するステップと、を有する再暗号化方法。選択部と再暗号化鍵生成部とを有する難読化装置が実行する鍵難読化方法であって、GGTが巡回群であり、gが前記巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが前記巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の前記基底ベクトルbiからなる基底であり、前記基底Bと前記基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、第1復号装置の秘密鍵がabcτ∈Fq×であり、前記第1復号装置の公開鍵がgτhahbhcBcτBであり、第2復号装置の秘密鍵がabcτ∈Fq×であり、前記第2復号装置の公開鍵がgτhahbhcBcτBであり、前記選択部で、zρσ∈Fq×を生成するステップと、前記再暗号化鍵生成部で、n次元ベクトルv→vι∈Fqnに対して、Z1aza,Z2bzb,Z3hz,k0hρ,kBを含む再暗号化鍵を生成するステップと、を有し、BcτBであり、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、しかしながら、内積述語暗号の機能を有する再暗号化方式は存在しない。本発明はこのような点に鑑みてなされたものであり、内積述語暗号の機能を有する再暗号化方式を提供する。本発明では、GGTが巡回群であり、gが巡回群Gの生成元であり、Fqが位数qの有限体であり、Fq×Fq\0であり、nが1以上の整数であり、μが2以上の整数であり、bi∈Gnμのそれぞれが巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の基底ベクトルbiからなる基底であり、bi∈Gnμのそれぞれが巡回群Gのnμ個の元を要素とするnμ次元の基底ベクトルであり、Bがnμ個の基底ベクトルbiからなる基底であり、基底Bと基底Bとは双対直交基底であり、nμ次元ベクトルd→∈Fqnμに対するBがΣi1nμdibiであり、nμ次元ベクトルf→∈Fqnμに対するBがΣi1nμfibiであり、Γがn1≦Γ<nμの整数であり、ιι⊂1nμであり、Bbιであり、第1復号装置の秘密鍵がabcτ∈Fq×であり、第1復号装置の公開鍵がgτhahbhcBcτBであり、第2復号装置の秘密鍵がabcτ∈Fq×であり、第2復号装置の公開鍵がgτhahbhcBcτBであり、zρσ∈Fq×であり、v→がn次元ベクトルv→vι∈Fqnであり、BcτBであり、再暗号化鍵がZ1aza,Z2bzb,Z3hz,k0hρ,kBを含み、RV→がnμ次元ベクトルRV→RVι∈Fqnμであり、ι∈1nμであり、ιι⊂1nμであり、RVιがn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1であり、ξが1以上の整数であり、eξが直積群Gξ×Gξの元に対して巡回群GTの元を得る双線形写像である。暗号化装置は、rsζω∈Fqを選択し、第1復号装置の公開鍵hahbhcBとn次元ベクトルx→xι∈Fqnとを用い、メッセージm∈Gの第1暗号文ctを生成する。ただし、第1暗号文ctがWarΘbsYhrsmUBΛhζを含み、CV→がnμ次元ベクトルCV→CVι∈Fqnμであり、CVιがn次元ベクトルωx→ωxιであり、何れか1個のCVκ∈CVιCVιがζであり、CVιCVιからCVκを除いた要素からなるベクトルとRVιRVιからRVκを除いた要素からなるベクトルとの内積が0である。再暗号化装置は、r’s’ζ’∈Fqを選択し、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’を得、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1を得、yy’∈Fq×に対するEΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む再暗号文ctを生成する。REV→はnμ次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιがζ’であり、REVκを除くREVιREVιが0∈Fqである。第2復号装置は、e1GHcE1aF1bを満たすm’∈Gを復号値として得る。本発明では、内積述語暗号の機能を有する再暗号化方式を実現できる。実施形態を説明する。定義基本的な用語表記を定義する。secはセキュリティパラメータを表す1以上の整数である。qはsecビットの素数であり、GGTは位数qの巡回群巡回乗法群であり、g∈Gは巡回群Gの生成元であり、gT∈GTは巡回群GTの生成元である。Fqは位数qの有限体であり、Fq×Fq\0は有限体Fqから零元加法単位元0を除いた集合である。実施形態では、原則、巡回群GGTでの演算が乗法群として乗法的に表記される。ただし、記法の便宜上の例外として、巡回群Gの元を要素とするベクトル単位の演算結果、及び、巡回群Gの元を要素とする行列単位の演算結果のみが加法的に表現以下便宜的加法表現される。加法的に表現されたとしても、このようなベクトルや行列の各要素が巡回群Gの元巡回乗法群の元であることに注意されたい。nが1以上の整数であり、x→∈Fqnがn個の有限体Fqの元xi∈Fqを要素とするn次元ベクトル例えば属性ベクトルであり、v→∈Fqnがn個の有限体Fqの元vi∈Fqを要素とするn次元ベクトル例えば述語ベクトルである。2つのベクトルx→,v→に対するx→v→は、内積x→v→Σi1nxivi∈Fqを表す。1→は単位ベクトル1→を表す。INは有限体Fqの元を要素に持つN行N列の単位行列を表す。eξξは1以上の整数は、任意の直積群Gξ×Gξの元に対して巡回群GTの元を得る双線形写像bilinearmapである。eξ:Gξ×Gξ→GT...双線形写像eξは以下の性質を満たす。[双線形性]双線形写像eξは、任意のλ1,λ2∈Gξ及びν1,ν2∈Fqについて以下の関係を満たす。eeν1ν2...[非退化]eξ≠1∈GTを満たすλ1,λ2∈Gξが存在する。すべてのλ1∈Gξに対してeξ1∈GTであるならλ20ξ∈Gξである。eξgT∈GTを満たす。[計算可能性]任意のλ1,λ2∈Gξに対してeの効率的なつまり多項式時間での計算が可能である。本形態の双線形写像eξは、任意のξ,γ∈Gξ,γ∈Gξ,γι∈G及びγι∈Gι1ξについて、以下のように構成される。eξΠι1ξe1...双線形写像e1の具体例は、有限体Fq上で定義された楕円曲線上の2点に対して定義されるWeilペアリングやTateペアリングなどのペアリングである。したがって、例えば公知のペアリングを用いることで任意のξに対する双線形写像eξを定義できる。ペアリングなどの双線形写像についての詳細は、例えば、参考文献1DBonehandMKFranklinIdentityBasedEncryptionfromtheWeilPairingInCRYPTO’01volume2139ofLectureNotesinComputerSciencepages213229Springer2001や、参考文献2黒澤馨著,現代暗号への招待,サイエンス社,2010年9月10日,ISBN9784781912622,第13章などを参照されたい。ai∈GNは、巡回群GのN個の元を要素とするN次元の基底ベクトルを表す。ただし、μが2以上の整数であり、Nnμである。基底ベクトルaiの一例はg∈Gをi次元目の要素とし、残りのN1個の要素を巡回群Gの単位元乗法的に1と表現とするN1次元の基底ベクトルである。N次元の基底ベクトルaiの各要素をそれぞれ列挙して表記すると、以下のようになる。a1a2...aNai∈GNは、巡回群GのN個の元を要素とするN次元の基底ベクトルを表す。基底ベクトルaiの一例はg∈Gをi次元目の要素とし、残りのN1個の要素を巡回群Gの単位元乗法的に1と表現とするN1次元の基底ベクトルである。N次元の基底ベクトルaiの各要素をそれぞれ列挙して表記すると、以下のようになる。a1a2...aNN個の基底ベクトルaiからなる基底Aは直交基底であり、巡回群G上のN次元ベクトル空間VG××Gを張るVspan。N次元ベクトル空間V上の任意の元γ∈Vは、基底ベクトルaiとdi∈Fqとを用い、便宜上、以下のように加法的に表記できる便宜的加法表現。γΣi1Ndiai...式を乗法的に表記すると以下のようになる。γ...ただし、上付き添え字のd1dNはd1dNを表す。N個の基底ベクトルaiからなる基底AとN個のdi∈Fqからベクトルd→とを用い、N次元ベクトル空間V上の任意の元γを以下のように表記する。γAA...N個の基底ベクトルaiからなる基底Aは直交基底であり、巡回群G上のN次元ベクトル空間VG××Gを張るVspan。N次元ベクトル空間V上の任意の元γ∈Vは、基底ベクトルaiとfi∈Fqとを用い、便宜上、以下のように加法的に表記できる便宜的加法表現。γΣi1Nfiai...式を乗法的に表記すると以下のようになる。γ...ただし、上付き添え字のf1fNはf1fNを表す。N個の基底ベクトルaiからなる基底AとN個のfi∈Fqからベクトルf→とを用い、N次元ベクトル空間V上の任意の元γを以下のように表記する。γAA...ただし、下付き添え字のAはAを表す。式より、γAA∈V,γAA∈Vについて、以下の関係が成り立つ。eNΠi1Ne1Πi1Ne1e1d1f1dNfNe1d→f→gTd→f→...ただし、上付き添え字のd→f→は、それぞれd→f→を表す。また式より、基底ベクトルaiと基底ベクトルajは以下の関係を満たす。すなわち、基底Aと基底Aとは互いに双対な直交基底双対直交基底である。eNgTδ...ただし、δはクロネッカーのデルタ関数を表す。すなわち、ijの場合にδ1∈Fqを満たし、i≠jの場合にδ0∈Fqを満たす。双線形写像eNがペアリングによって構成される場合、上述のような位数q,N次元ベクトル空間V,V,巡回群GGT,生成元g,双線形写像eNの組を対称ペアリング群による双対ペアリングベクトル空間DPVSDualParingVectorspaceと呼ぶ。N個の基底ベクトルaiからなる基底Aは、一様ランダムなN行N列の正則行列X←UGLを用い、N次元ベクトル空間Vの基底Bに変換可能である。GLは有限体Fq上のN次元一般線形群を表し、は、χijをi行j列の要素とする行列を表す。MENBER←USETは集合SETの要素MENBERを一様ランダムに選択することを意味する。基底Bの要素bi∈GNのそれぞれは、巡回群GのN個の元を要素とするN次元の基底ベクトルであり、便宜上、以下のように加法的に表記できる便宜的加法表現。biΣj1Nχijaj...式を乗法的に表記すると以下のようになる。bi...ただし、上付き添え字のχijはχijを表す。すなわち、基底Bは巡回群Gの元を要素とするN×Nの行列とみることができ、乗法的に以下のように表記することができる。Bij...N個の基底ベクトルaiからなる基底Aは、正則行列1を用い、N次元ベクトル空間Vの直交基底Bに変換可能である。ただし、ΞTはΞの転置を表し、Ξ1はΞの逆行列を表し、はθijをi行j列の要素とする行列を表す。直交基底Bの要素bi∈GNのそれぞれは、巡回群GのN個の元を要素とするN次元の基底ベクトルであり、便宜上、以下のように加法的に表記できる便宜的加法表現。biΣj1Nθijaj...式を乗法的に表記すると以下のようになる。bi...ただし、上付き添え字のθijはθijを表す。すなわち、基底Bは巡回群Gの元を要素とするN×Nの行列とみることができ、乗法的に以下のように表記することができる。Bij...1からTINが成り立つことから、χi→,θj→とおくと以下が成り立つ。χi→θj→δ∈Fq×...式から以下が成り立つ。eNΠι1Ne1e1χi→θj→e1δgTδ...すなわち、基底Bと基底Bとは互いに双対な直交基底双対直交基底である。基底Bは巡回群G上のN次元ベクトル空間VG××Gを張りVspan、基底Bは巡回群G上のN次元ベクトル空間VG××Gを張るVspan。N次元ベクトル空間V上の任意の元γ∈Vは、基底ベクトルbiとdi∈Fqとを用い、便宜上、以下のように加法的に表記できる便宜的加法表現。γΣi1Ndibi...式より、式を乗法的に表記すると以下のようになる。基底Bとベクトルd→とを用い、N次元ベクトル空間V上の任意の元γを以下のように表記する。γBB...N次元ベクトル空間V上の任意の元γ∈Vは、基底ベクトルbiとfi∈Fqとを用い、便宜上、以下のように加法的に表記できる便宜的加法表現。γΣi1Nfibi...式より、式を乗法的に表記すると以下のようになる。基底Bとベクトルf→とを用い、N次元ベクトル空間V上の任意の元γを以下のように表記する。γBB...式より、γBB∈V,γBB∈Vについて、以下の関係が成り立つ。eNeNd1f1eNdNfNgTgTd→f→...概要次に、実施形態の概要を説明する。実施形態のセキュリティシステムは、パラメータ生成装置、第1復号装置、第2復号装置、難読化装置、暗号化装置及び再暗号化装置を有する。パラメータ生成装置は、セキュリティシステム全体に共通なシステムパラメータを生成する機能、及び、生成したシステムパラメータを出力する機能を有する。パラメータ生成装置は、1secsec個の1を入力として、セキュリティパラメータsecに対応する双線型写像パラメータparamV,正則行列X,基底B,BNnμを生成する。パラメータ生成装置は、双線型写像パラメータparamVを記憶部に記憶する。パラメータ生成装置は、nμ個の基底ベクトルbi∈Gnμの一部であるΓ個の基底ベクトルbιbιからなるBbιを生成する。ただし、ιι⊂1nμ、n1≦Γ<nμである。例えば、μ2n2であり、Γn2であり、ιι⊂13n2であり、Bbιである。より具体的な例を挙げると、Bである。パラメータ生成装置は、以下のシステムパラメータcrsを公開パラメータとして出力する。crs...第1復号装置は、公開鍵と秘密鍵を生成する機能、公開鍵と秘密鍵を記憶部に記憶する機能、及び、公開鍵を出力する機能を有する。第1復号装置は、システムパラメータcrsを入力とし、abcτ∈Fq×を選択して秘密鍵skbcτ及び公開鍵pkgτhahbhcBcτBを生成する。秘密鍵sk及び公開鍵pkは第1復号装置の記憶部に記憶され、公開鍵pkは任意の装置に送信可能とされる。BcτBは、巡回群Gの元を要素とするベクトル単位の演算結果を表し、便宜上、加法的に表現されている便宜的加法表現。式より、BcτBを乗法的に表記すると以下のようになる。これはBとc,τとから計算可能である。Bτχijij...ただし、i∈ιι⊂1nμ,j∈1nμである。第2復号装置は、公開鍵と秘密鍵を生成する機能、公開鍵と秘密鍵を記憶部に記憶する機能、及び、公開鍵を出力する機能を有する。第2復号装置は、システムパラメータcrsを入力とし、abcτ∈Fq×を選択して秘密鍵skbcτ及び公開鍵pkgτhahbhcBcτBを生成する。秘密鍵sk及び公開鍵pkは第2復号装置の記憶部に記憶され、公開鍵pkは任意の装置に送信可能とされる。BcτBは、巡回群Gの元を要素とするベクトル単位の演算結果を表し、便宜上、加法的に表現されている便宜的加法表現。式より、BcτBを乗法的に表記すると以下のようになる。これはBとc,τとから計算可能である。Bτχijij...ただし、i∈ιι⊂1nμ,j∈1nμである。難読化装置は、第1復号装置の秘密鍵sk、第2復号装置の公開鍵pk、n次元ベクトルv→vι∈Fqn、及びシステムパラメータ生成時に生成された正則行列Xを入力とし、再暗号化鍵Obfを生成する機能を有する。なお、正則行列Xは秘密情報であるため、パラメータ生成装置と難読化装置が同一であるか、難読化装置が何らかの安全な手段専用回線や記録媒体を介した情報伝達等を用いてパラメータ生成装置から正則行列Xを取得する必要がある。同様に秘密鍵skは秘密情報であるため、難読化装置が何らかの安全な手段を用いて第1復号装置から秘密鍵skを取得する必要がある。難読化装置は、skbcτ、pkgτhahbhcBcτB、v→vι∈Fqn、及び正則行列Xを入力として、Z1aza,Z2bzb,Z3hz,k0hρ,kBを含む再暗号化鍵Obfを生成する。RV→はnμ次元ベクトルRV→RVι∈Fqnμであり、zρσ∈Fq×は乱数であり、BcτBであり、ι∈1nμであり、ιι⊂1nμであり、RVιはn次元ベクトルσv→σvιであり、何れか1個のRVκ∈RVιRVιが1∈Fqである。例えば、RV→が3n2次元ベクトルRV→RVιであり、1個のRVκ∈RVιRVιが1∈Fqであり、RVκ以外の1個のRVφ∈RVιRVιが0∈Fqであり、n個のRVεRVε∈RVιRVιが乱数ηεηε∈Fqであり、RVεRVε以外のn個のRVυRVυ∈RVιRVιのそれぞれが0∈Fqである。これによりより高い安全性を確保できる。より具体的な例を挙げると、v→,σv→,0n,RV2n11,η→∈Fqn,RV3n20であり、RV→の例は以下である。RV→∈Fq3n2...BcτBは、巡回群Gの元を要素とするベクトル単位の演算結果を表し、便宜上、加法的に表現されている便宜的加法表現。式より、BcτBを乗法的に表記し、変形すると以下のようになる。Bcτijτχijij...難読化装置は、Bτχijijι,j∈1nμと正則行列Xを用いることで、gcτχi’j’τχijχi’j’χijを計算でき、以下のB’を生成できる。B’τij...式より、難読化装置はB’を用いてBを計算することができることが分かる。暗号化装置は、システムパラメータcrs、第1復号装置の公開鍵hahbhcB又は第2復号装置の公開鍵hahbhcB、モード選択パラメータβ、n次元ベクトルx→xι∈Fqn、及びメッセージm∈Gを入力とし、メッセージm∈Gの暗号文を生成する機能、及び、暗号文を出力する機能を有する。暗号化装置が第1復号装置で復号可能な暗号文を生成する場合、暗号化装置は、暗号文ct第1暗号文及び暗号文ct第2暗号文の何れかを生成する。暗号文ctは再暗号化可能なモード以下第1モードというの暗号文であり、暗号文ctは再暗号化不可能なモード以下第2モードというの暗号文である。本形態の再暗号化方式は単方向単一ホップ型であり、第1モードの暗号文が再暗号化されると第2モードの暗号文となる。モード選択パラメータβは、第1モードであるか第2モードであるかを表す。第1モードの場合、モード選択パラメータβが第1値とされ、第2モードの場合、モード選択パラメータβが第2値≠第1値とされる。本形態の例では、第1値を0とし、第2値を1とするβ∈01。暗号文ctは、WarΘbsYhrsmUBΛhζを含む。本形態では暗号文ctがさらに第1値のモード選択パラメータβ0を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ctがモード選択パラメータを含まなくてもよい。CV→はnμ次元ベクトルCV→CVι∈Fqnμであり、CVιはn次元ベクトルωx→ωxιであり、rsω∈Fqは乱数であり、何れか1個のCVκ∈CVιCVιが乱数ζ∈Fqである。CVιCVιからCVκを除いた要素からなるベクトルと上述のRVιRVιからRVκを除いた要素からなるベクトルとの内積が0となる。例えば、CV→が3n2次元ベクトルCV→CVιであり、CVιがn次元ベクトルωx→ωxιであり、1個のCVκ∈CVιCVιが乱数ζであり、CVκ以外の1個のCVφ∈CVιCVιが暗号化装置によって選択された乱数ψ∈Fqであり、2n個のCVιCVιのそれぞれが0である。これによりより高い安全性を確保できる。より具体的な例を挙げると、x→,ωx→,0n,CV2n1ζ,0n,CV3n2ψであり、CV→の例は例えば以下である。CV→∈Fq3n2...暗号文ctは、Ee1artFe1bstGe1rsmte1cζZtHe1ζを含む。tt∈Gは乱数である。本形態では暗号文ctがさらに第2値のモード選択パラメータβ1を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ctがモード選択パラメータを含まなくてもよい。暗号化装置が第2復号装置で復号可能な暗号文を生成する場合、暗号化装置は、第1モードの暗号文ct及び第2モードの暗号文ct’の何れかを生成する。暗号文ctは、WarΘbsYhrsmUBΛhζを含む。本形態では暗号文ctがさらに第1値のモード選択パラメータβ0を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ctがモード選択パラメータを含まなくてもよい。暗号文ct’は、E’e1artF’e1bstG’e1rsmte1cζZ’tH’e1ζを含む。本形態では暗号文ct’がさらに第2値のモード選択パラメータβ1を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ct’がモード選択パラメータを含まなくてもよい。再暗号化装置は、第1復号装置の公開鍵pkhahbhcB、暗号文ct、及び再暗号化鍵Obfを入力とし、第2復号装置が復号可能な暗号文ct再暗号文を生成する機能、及び、暗号文ctを出力する機能を有する。再暗号化装置は、乱数r’s’ζ’∈Fqを用い、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’を得、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1を得、乱数yy’∈Fq×に対するEΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’を含む暗号文ctを生成する。REV→はnμ次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが乱数ζ’であり、REVκを除くREVιREVιが0∈Fqである。例えば、REV→は3n2次元ベクトルREV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが乱数ζ’であり、REVκを除くREVιREVιが0∈Fqである。より具体的な例を挙げると、02n,REV2n1ζ’,0n1であり、REV→の例は以下である。REV→∈Fq3n2...前述のように、暗号文ctは第2モードの暗号文となる。本形態では暗号文ctがさらに第2値のモード選択パラメータβ1を含む例を示す。しかしながら、モード選択パラメータを用いることなく、何れのモードが用いられたかが他の装置で特定可能なのであれば、暗号文ctがモード選択パラメータを含まなくてもよい。第1復号装置は、さらに、入力暗号文を復号して復号値m’を得る機能、及び、復号値m’を出力する機能を有する。第1復号装置は、入力暗号文として暗号文ct第1値を表すモード選択パラメータβ0を含む入力暗号文が得られた場合にm’Y1aΘ1bを復号値として得る。第1復号装置は、入力暗号文として暗号文ct第2値を表すモード選択パラメータβ1を含む入力暗号文が得られた場合にe1GHcE1aF1bを満たすm’∈Gを復号値として得る。e1GHcE1aF1bを満たすm’∈Gの探索は、例えば、有限体Gの元を全数探索することによって行われる。第2復号装置も、さらに、入力暗号文を復号して復号値m’を得る機能、及び、復号値m’を出力する機能を有する。第2復号装置は、入力暗号文として暗号文ct第1値を表すモード選択パラメータβ0を含む入力暗号文が得られた場合にm’Y1aΘ1bを復号値として得る。第2復号装置は、入力暗号文として暗号文ct第2値を表すモード選択パラメータβ1を含む入力暗号文が得られた場合にe1GHcE1aF1bを満たすm’∈Gを復号値として得る。e1GHcE1aF1bを満たすm’∈Gの探索は、例えば、有限体Gの元を全数探索することによって行われる。暗号文ct’が得られた場合も同様に、第2復号装置は、e1’G’H’cE’1aF’1bを満たすm’∈Gを復号値として得る。<復号結果の導出>以下に復号結果の導出を行う。[再暗号化前の暗号文ctの場合]以下より正しい復号値が得られることが分かる。m’Y1aΘ1bhrsmhm[再暗号化前の暗号文ctの場合]式より、復号時の探索用の式には以下の関係が成り立つ。e1e1GHcE1aF1be1rsmte1cζe1ζce1art1ae1bst1be1e1te1cζe1cζe1te1したがって、正しい復号値が得られることが分かる。同様に、再暗号化前の暗号文ctct’についても正しく復号値が得られることが分かる。再暗号化によって得られた暗号文ctの場合式より、暗号文ctが含むEは以下のように変形できる。Ee1arar’azaye1gτazye1ττagτyze1τahyz...Lττ,rL及びthyzとおくと、式は以下のように表記できる。Ee1art...ただし、上付き添え字のrはrを表す。式より、暗号文ctが含むFは以下のように変形できる。Fe1bsbs’bzbye1gτbzye1bgτyze1ττbgτyze1bτhyz...Lττ,sL及びthyzとおくと、式は以下のように表記できる。Fe1bst...ただし、上付き添え字のsはsを表す。式より、暗号文ctが含むGは以下のように変形できる。Ge1mgτgτzyenμBBy’e1mgτzyenμτCV’→BcτRV→By’e1τmhyze1cττρy’...ただし、上付き添え字のCV’→はCV’→を表し、RV→はRV→を表す。CV’→はCV’→CV→REV→を満たすnμ次元ベクトルである。nμ次元ベクトルCV→が含む1個の要素CVκζをζζ’に置換したものがCV’→となる。ここで、RV→RVιを構成するRVιがn次元ベクトルσv→σvιであり、1個のRVκが1である。CV→CVιを構成するCVιがn次元ベクトルωx→ωxιであり、1個のCVκがζである。CVιからCVκを除いた要素からなるベクトルとRV→RVιからRVκを除いた要素からなるベクトルとの内積が0となる。そのため、CV’→RV→ζζ’ωσx→v→となる。式の具体例を用いて導出すると以下のようになる。CV’→CV’→RV→ζζ’ωσx→v→したがって式は以下のように変形できる。Ge1τmhyze1cττρy’e1τmhyze1Lρy’hcL...ここで、Lττ,ζL,νL,rL,sL,thyz及びt’hLρy’とおくと、式は以下のように表記できる。Ge1mte1cν...ただし、上付き添え字のrはrを表し、sはsを表し、ζはζを表す。thyzとおくと、暗号文ctが含むZは以下のように表記できる。ZZ3yhyzt...式より、暗号文ctが含むHは以下のように変形できる。He1hρy’e1ρy’hLL...ここでζL及びt’hLρy’とおくと、式は以下のように表記できる。He1ζ...式より、復号時の探索用の式には以下の関係がなりたつ。e1e1GHcE1aF1be1mte1cνe1ζce1art1ae1bst1be1e1te1cνe1cζe1te1e1cνe1cζ...式はν0すなわち、内積x→v→0の場合にはe1となり、m’mとなり正しく復号がなされる。一方、内積x→v→≠0の場合には式はe1とならず、正しく復号できない。以上より、n次元ベクトルx→とn次元ベクトルv→との内積が0のときに復号が可能となる内積述語暗号において、再暗号化方式が実現されたことが分かる。このように本実施形態では、暗号文にn次元ベクトルx→を、再暗号化鍵にn次元ベクトルv→をそれぞれ埋め込み、x→v→0が成立するか否かによって正しく再暗号化が行われるかを制御することができる。<述語秘匿性>実施形態のセキュリティシステムは述語秘匿性を有する。述語秘匿性とは、述語暗号方式における鍵に対応するn次元ベクトルv→の秘匿性を意味する。述語秘匿性という呼び名は、鍵に述語ベクトルが対応し、暗号文に属性ベクトルが対応することを前提としたものである。しかしながら、鍵に属性ベクトルが対応し、暗号文に述語ベクトルが対応してもよい。鍵に対応するn次元ベクトルv→が属性ベクトルである場合には述語秘匿性とは属性の秘匿性を意味する。これまでの述語暗号方式に述語秘匿性を持つものは存在しない。これは従来の述語暗号方式では、攻撃者が任意のn次元ベクトルv’→を用いて鍵を生成し、その鍵で暗号文を復号して正しいメッセージが得られるか否かを探索することで、n次元ベクトルv→に関する情報を得ることができるからである。これに対し、本実施形態では、暗号文にn次元ベクトルx→を埋め込み、再暗号化鍵にn次元ベクトルv→を埋め込む。そのため、攻撃者が任意のn次元ベクトルv’→を用いて再暗号化鍵を生成し、その再暗号化鍵で暗号文を再暗号化しても、それによって得られるのは暗号文であり、当該攻撃者はその暗号文が正しく再暗号化されたかを判断することができない。よって、本実施形態では述語秘匿性を実現できる。<再暗号化鍵の難読化>再暗号化鍵Obfを含む再暗号化コードが難読化された情報となることを説明する。[難読化の定義]入力値INに対してOUTCODEを出力するコードCODE、コードCODEに対応する情報Obf、任意の入力値INに対して出力値OUTCODEを出力するオラクル、仮想的な攻撃者ADV、シミュレータSIM、及び識別器DISを仮定する。攻撃者ADVには情報Obfが与えられるが、シミュレータSIMには情報Obfが与えられない。攻撃者ADV、シミュレータSIM及び識別器DISは、オラクルORAからコードCODEを与えられないが、オラクルORAに任意の入力値INを与えてそれに対する出力値OUTCODEを得ることができる。攻撃者ADVは、情報ObfとオラクルORAを用いて得られた情報を識別器DISに与える。シミュレータSIMは、オラクルORAを用いて得られた情報を識別器DISに与える。識別器DISは、オラクルORA及び与えられた情報を用いて当該情報を与えたものが攻撃者ADVであるかシミュレータSIMであるかを識別する。識別器DISは、情報を与えたものが攻撃者ADVであると識別した場合に1を出力し、シミュレータSIMであると識別した場合に0を出力する。以下の条件~が成り立つ場合、ObfはCODEが難読化された情報である。任意の入力値∀INについて、CODEObfを満たす。Obfが任意の入力値∀INのサイズに対する多項式時間で計算可能である。任意の攻撃者∀ADV及び識別器∀DISに対して以下を満たすシミュレータ∃SIMが存在する。PrDISORA→1PrDISORA→1NEGL...ただし、PrDISORA→1は、攻撃者ADVから情報が与えられた識別器DISが当該情報を与えたものが攻撃者ADVであると識別して1を出力する確率を表す。PrDISORA→1は、シミュレータSIMから情報が与えられた識別器DISが当該情報を与えたものが攻撃者ADVであると識別して1を出力する確率を表す。NEGLは、無視することができる値を出力する関数である。NEGLの出力値はセキュリティパラメータsecが大きいほど小さい。[再暗号化鍵Obfを含む再暗号化コードの難読化]再暗号化鍵Obfは、Z1aza,Z2bzb,Z3hz,k0hρ,kBを含む。式より、たとえzやρが定数例えばz1、ρ=1であったとしても再暗号化された暗号文ctを生成することはできる。しかし、z及びρを乱数とすることで再暗号化鍵Obfを含む再暗号化コードが難読化される。比較のため、まずz1の場合を想定する。z1の場合、再暗号化鍵ObfはZ1haa,Z2hbb,Z3h,k0hρ,kBを含む。攻撃者ADVは、再暗号化鍵Obf及び第1復号装置の公開鍵を用い、以下を計算することができる。e1aa,hae1a,hΥ...そのため攻撃者ADVは、Υe1KEY,hを満たすKEYを探索して秘密鍵aに関する情報を得ることができる。一方、再暗号化鍵Obfを持たないシミュレータSIMは式の計算によってΥを求めることができず、KEYを探索して秘密鍵aに関する情報を得ることができない。従って式が満たされず、再暗号化鍵Obfを含む再暗号化コードは難読化されたといえない。次に、zが乱数であると仮定する。乱数zに対するZ1aza,Z2bzb,Z3hz,k0hρ,kBを含む再暗号化鍵Obfの場合、攻撃者ADVは、再暗号化鍵Obf及び第1復号装置の公開鍵を用い、以下を計算することができる。e1aza,hae1az,hΥ’...攻撃者ADVは、Υ’e1KEYz,hを満たすKEYzを探索することはできるが、zが乱数であるため、ComputationalDiffieHellman仮定が真なのであれば、秘密鍵aに関する情報を得ることができない。同様に攻撃者ADVは、z及びρが乱数で或る場合には、再暗号化鍵Obfのその他の要素について秘密鍵bやn次元ベクトルv→などの秘密情報を得ることができない。従ってz及びρが乱数である場合には式が満たされ、条件が満たされる。再暗号化鍵Obfを含む再暗号化コードは、その他の条件も満たすため、難読化されたといえる。<安全性>本実施形態では高い安全性を有する再暗号化方式を実現できる。特に、RV→RVιであり、1個のRVκ∈RVιRVιが1∈Fqであり、RVκ以外の1個のRVφ∈RVιRVιが0∈Fqであり、RVεRVε∈RVιRVιが乱数ηεηε∈Fqであり、RVεRVε以外のn個のRVυRVυ∈RVιRVιのそれぞれが0∈Fqであり、CV→CVιであり、CVιがn次元ベクトルωx→ωxιであり、1個のCVκ∈CVιCVιが乱数ζであり、CVκ以外の1個のCVφ∈CVιCVιが暗号化装置によって選択された乱数ψ∈Fqであり、2n個のCVιCVιのそれぞれが0であり、REV→REVι∈Fqnμであり、何れか1個のREVκ∈REVιREVιが乱数ζ’であり、REVκを除くREVιREVιが0∈Fqである場合例えば式を満たす場合、判定線形仮定及び強DiffeHellman識別仮定が真であれば、INDCPA安全であるといえる。実施形態次に、図面を参照して実施形態を説明する。<構成>図1に例示するように、本形態のセキュリティシステム1は、例えば、パラメータ生成装置11、暗号化装置12、復号装置1314第1,2復号装置、難読化装置15及び再暗号化装置16を有し、これらはネットワークを通じて通信可能に構成されている。本形態では、説明の便宜上、1個のパラメータ生成装置、暗号化装置、難読化装置及び再暗号化装置並びに2個の復号装置を有するセキュリティシステムを例示するが、セキュリティシステムが、より多くのパラメータ生成装置、暗号化装置、難読化装置、再暗号化装置及び復号装置を有していてもよい。或いは、パラメータ生成装置と難読化装置が同一の装置であってもよいし、難読化装置と何れかの復号装置とが同一の装置であってもよい。パラメータ生成装置11、暗号化装置12、復号装置1314第1,2復号装置、難読化装置15及び再暗号化装置16のそれぞれは、例えば、CPURAMROM等から構成される公知又は専用のコンピュータに特別なプログラムが読み込まれることで構成される特別な装置である。[暗号化装置12]図2に例示するように、本形態の暗号化装置12は、入力部12a、インタフェース部12b、一時メモリ12c、記憶部12d、制御部12e、モード切り替え部21f、選択部12g,12h、及び、暗号化部12i,12jを有する。暗号化装置12は制御部12eの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ12cに格納され、一時メモリ12cに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。[復号装置13]図3に例示するように、本形態の復号装置13は、出力部13a、インタフェース部13b、一時メモリ13c、記憶部13d、制御部13e、選択部13f、公開鍵生成部13g~13k、モード切り替え部13m、及び、復号部13n,13pを有する。復号装置13は制御部13eの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ13cに格納され、一時メモリ13cに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。[復号装置14]図4に例示するように、本形態の復号装置14は、出力部14a、インタフェース部14b、一時メモリ14c、記憶部14d、制御部14e、選択部14f、公開鍵生成部14g~14k、モード切り替え部14m、及び、復号部14n,14pを有する。復号装置14は制御部14eの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ14cに格納され、一時メモリ14cに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。[難読化装置15]図5に例示するように、本形態の難読化装置15は、入力部15a、インタフェース部15b、一時メモリ15c、記憶部15d、制御部15e、選択部15f,15g、及び、再暗号化鍵生成部15h,15i,15jを有する。難読化装置15は制御部15eの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ15cに格納され、一時メモリ15cに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。[再暗号化装置16]図6に例示するように、本形態の再暗号化装置16は、インタフェース部16a,16b、一時メモリ16c、記憶部16d、制御部16e、選択部16f,16i、群演算部16ga~16ge、双線形写像演算部16ha~16he、及び、再暗号化部16ja~16jeを有する。再暗号化装置16は制御部16eの制御のもとで各処理を実行する。各処理過程で得られたデータは一時メモリ16cに格納され、一時メモリ16cに格納されたデータは必要に応じて読み出されて他の処理過程で使用される。<処理>本形態の処理を説明する。本形態では、暗号化装置12が復号装置13で復号可能な暗号文が作成される例を説明する。暗号化装置12で作成された暗号文は、そのまま復号装置13で復号されるか、再暗号化装置16で復号装置14が復号可能な暗号文に再暗号化された後、復号装置14で復号される。[パラメータ生成]本形態のパラメータ生成装置11は、前述のようにシステムパラメータcrsを生成し、ネットワークを通じて送信する。システムパラメータcrsは、暗号化装置12、復号装置1314、難読化装置15及び再暗号化装置16それぞれのインタフェース部12b,13b,14b,15b,16bで受信され、それぞれの記憶部12d,13d,14d,15d,16dに格納される。暗号化装置12、復号装置1314、難読化装置15及び再暗号化装置16のそれぞれは、必要に応じて記憶部12d,13d,14d,15d,16dに格納されたシステムパラメータcrsを読み出して利用する。難読化装置15の記憶部15dには、さらにシステムパラメータ生成時に生成された正則行列Xが格納される。[秘密鍵及び公開鍵の生成]図7Aに例示するように、復号装置13図3の選択部13fが、乱数abcτ←UFq×を一様ランダムに選択し、これらを復号装置13の秘密鍵skbcτとして記憶部13dに格納するステップS101。公開鍵生成部13g~13kは、記憶部13dに格納された秘密鍵sk及びシステムパラメータcrsを用い、それぞれhgτ∈GhahbhcBcτBを計算し、それらを復号装置13の公開鍵pkhahbhcBとして記憶部13dに格納するステップS102~S106。公開鍵pkは、必要に応じてインタフェース部13bから他の装置に対して送信される。秘密鍵skは一般に公開されないが、難読化装置15のみに対して秘密鍵skが与えられ、秘密鍵skが難読化装置15の記憶部15dに格納される。図7Bに例示するように、復号装置14図4の選択部14fが、乱数abcτ←UFq×を一様ランダムに選択し、これらを復号装置14の秘密鍵skbcτとして記憶部14dに格納するステップS111。公開鍵生成部14g~14kは、記憶部14dに格納された秘密鍵sk及びシステムパラメータcrsを用い、それぞれhgτ∈GhahbhcBcτBを計算し、それらを復号装置14の公開鍵pkhahbhcBとして記憶部14dに格納するステップS112~S116。公開鍵pkは、必要に応じてインタフェース部14bから他の装置に対して送信される。[再暗号化鍵の生成]難読化装置15図5は、ネットワーク及びインタフェース部13bを介して公開鍵pkを取得し、それを記憶部15dに格納する。さらにn次元ベクトルv→vι∈Fqnが入力部15aに入力される。図7Cに例示するように、難読化装置15の選択部15fが、乱数zρσ←UFq×を一様ランダムに選択しステップS121、選択部15gが、乱数ηεηε∈←UFqを一様ランダムに選択する。前述のように、乱数η→ηεの一例はη→とを用い、前述のB’cτB前述の式では乗法的に表記を生成するステップS123。B’は再暗号化鍵生成部15iに入力される。再暗号化鍵生成部15iは、B’と記憶部15dに格納されたシステムパラメータcrsと正則行列Xと秘密鍵skとを用い、前述のように式参照BcτBを計算するステップS124。再暗号化鍵生成部15jは、入力されたn次元ベクトルv→と乱数zρσと乱数η→と、記憶部15dに格納されたシステムパラメータcrsと公開鍵pkとを用い、前述のように、Z1aza,Z2bzb,Z3hz,k0hρ,kBからなる再暗号化鍵Obfを生成する。前述のように、RV→の一例はRV→であるステップS125。生成された再暗号化鍵Obfは、インタフェース部15bに送られ、ネットワークを介して再暗号化装置16に送られる。再暗号化鍵Obfは、再暗号化装置16図6のインタフェース部16bで受信され、記憶部16dに格納される。[暗号化処理]暗号化装置12図2は、ネットワーク及びインタフェース部12bを介して公開鍵pkを取得し、それを記憶部12dに格納する。図8に例示するように、暗号化装置12の入力部12aに、モード選択パラメータβ∈01、n次元ベクトルx→xι∈Fqn、及びメッセージm∈Gが入力されるステップS131。選択部12gは、乱数rsζωψ←UFqを一様ランダムに選択するステップS132。モード切り替え部12fは、入力されたモード選択パラメータβに応じて暗号化方法を選択するステップS133。β0であった場合、モード切り替え部12fは第1モードの暗号化方法を選択する。この場合、暗号化部12iが、記憶部12dに格納されたシステムパラメータcrsと公開鍵pkと、入力されたn次元ベクトルx→xιとメッセージmと乱数rsζωψとを用い、暗号文ct0WarΘbsYhrsmUBΛhζを生成する。前述のようにCV→の一例は、CV→であるステップS134。β1であった場合、モード切り替え部12fは第2モードの暗号化方法を選択する。この場合、まず、選択部12hが乱数tt←UGを一様ランダムに選択するステップS135。次に、暗号化部12jが、記憶部12dに格納されたシステムパラメータcrsと公開鍵pkと、入力されたn次元ベクトルx→xιとメッセージmと乱数rsζttとを用い、暗号文ct1Ee1artFe1bstGe1rsmte1cζZtHe1ζを生成するステップS136。生成された暗号文ctはインタフェース部13に送られ、そこから送信出力される。β0の場合に生成された暗号文ctは、ネットワークを介して復号装置13又は再暗号化装置16に送信され、若しくは、復号装置13に送信された後に再暗号化装置16に転送される。β1の場合に生成された暗号文ctは、ネットワークを介して復号装置13に送信されるステップS137。[再暗号化処理]暗号文ctが再暗号化装置16図6に送信又は転送された場合、図9に示すように、インタフェース部12bで暗号文ctが受信され暗号文ctの入力を受け付け、暗号文ctが記憶部16dに格納される。さらに再暗号化装置16は、ネットワーク及びインタフェース部12bを介して公開鍵pkを取得し、それを記憶部16dに格納するステップS141。選択部16fが、乱数r’s’ζ’←UFqを一様ランダムに選択するステップS142。群演算部16ga~16geは、入力された乱数r’s’ζ’と、記憶部16に格納されたシステムパラメータcrsと暗号文ctと公開鍵pkとを用い、W’War’Θ’Θbs’Y’Yhr’s’U’UBΛ’Λhζ’をそれぞれ計算するステップS143~147。双線形写像演算部16ha~16heが、入力されたW’Θ’Y’U’Λ’と、記憶部16dに格納されたシステムパラメータcrsと再暗号化鍵Obfとを用い、Ψ1e1Ψ2e1Ψ3e1Ω1enμΩ2e1をそれぞれ計算するステップS148~S152。選択部16iは、乱数yy’←UFq×を一様ランダムに選択するステップS153。再暗号化部16ja~16jeは、入力されたΨ1Ψ2Ψ3Ω1Ω2と乱数yy’とを用い、EΨ1yFΨ2yGΨ3yΩ1y’ZZ3yHΩ2y’をそれぞれ計算するステップS153~S159。インタフェース部16aは、暗号文ct1EFGZHを送信出力する。暗号文ctはネットワークを介して復号装置14に送信されるステップS160。[復号処理]暗号文ctが復号装置13図3に送信されると、図10Aに例示するように、暗号文ctが復号装置13のインタフェース部13bに受信入力されるステップS161。モード切り替え部13mは、暗号文ctβの先頭に位置するβが0であるかを判定するステップS162。β0であれば、復号部13nは、入力された暗号文ctと記憶部13dに格納された秘密鍵skとを用い、m’Y1aΘ1bを復号値として計算しステップS163、出力部13aが復号値m’を出力するステップS165。β1であれば、復号部13pは、入力された暗号文ctと記憶部13dに格納された秘密鍵skとを用い、e1GHcE1aF1bを満たすm’∈Gを復号値として計算しステップS164、出力部13aが復号値m’を出力するステップS165。[復号処理]暗号文ctが復号装置14図4に送信されると、図10Bに例示するように、暗号文ctが復号装置14のインタフェース部14bに受信入力されるステップS171。モード切り替え部14mは、暗号文ctβの先頭に位置するβが0であるかを判定するステップS172。β0であれば、復号部14nは、入力された暗号文ct0WarΘbsYhrsmUBΛhζと、記憶部14dに格納された秘密鍵skとを用い、m’Y1aΘ1bを復号値として計算しステップS173、出力部14aが復号値m’を出力するステップS175。β1であれば、復号部14pは、入力された暗号文ctと記憶部14dに格納された秘密鍵skとを用い、e1GHcE1aF1bを満たすm’∈Gを復号値として計算しステップS174、出力部14aが復号値m’を出力するステップS175。変形例等本発明は上述の実施形態に限定されるものではない。例えば、上述の実施形態では、安全性の観点から乱数として一様ランダムな値が用いられたが、用途や利用環境によっては一様ランダムではない乱数が用いられてもよい。また、乱数とは真性乱数及び擬似乱数の両方を含む概念であり、乱数として真性乱数が用いられてもよいし、擬似乱数が用いられてもよい。さらに上述の実施形態で扱った乱数例えば、ttρσrsζωr’s’ζ’yy’zηεηεの少なくとも一部が、予め定められた候補の中から選択された値であったり、定数であったりしてもよい。上述のように巡回群GGTの位数が有限体Fqの位数qと同一である場合に高い安全性を確保できるが、用途によっては巡回群GGTの位数が有限体Fqの位数と異なっていてもよい。上述の実施形態では、qが素数であって有限体Fqが素体である例を示したが、有限体Fqが拡大体であってもよい。上記の実施形態では、各装置がネットワークを経由して情報を通信する例を示したが、装置間の情報通信の少なくとも一部が、可搬型記録媒体を介した情報のやり取りに置換されてもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的なnontransitory記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASPApplicationServiceProvider型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるものコンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等を含むものとする。この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。"