(57)【要約】  CCA安全性を向上させるためのみの空間を暗号文空間に設けることなくCCA安全性を向上させる。暗号化処理では、平文Mと共通鍵Kから第１暗号文C1を算出し、共通鍵Kに対応する値と第１暗号文C1に対応する値とを含む値を衝突困難な関数Hに入力して関数Hの関数値を算出し、それに対応するrを用いて第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出する。復号処理では、第２暗号文C2∈G1n+1と鍵情報D1*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出し、関数値S〜に対応する値と第１暗号文C1とを衝突困難な関数Hに入力して関数Hの関数値を算出し、それに対応するr〜に対して、C2=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を満たすか否かを判定する。
2010123112.tif 000002
【特許請求の範囲】
【請求項１】
平文Mと共通鍵Kとを共通鍵暗号関数に入力して暗号文C1を算出し、当該暗号文C1を出力するように構成された共通鍵暗号化部と、
前記共通鍵Kに対応する値と前記暗号文C1に対応する値とを含む値を衝突困難な関数Hに入力して関数Hの関数値を算出するように構成された関数演算部と、
前記関数Hの関数値に対応する値rと、前記共通鍵Kに対応する値ρと、n次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n)(n≧1)と、巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルbi∈G1n+1 (i=1,...,n+1)とを用い、第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出し、当該第２暗号文C2を出力するように構成されたベクトル演算部と、
を有する暗号化装置。
【請求項２】
請求項１の暗号化装置であって、
前記共通鍵Kは、バイナリ系列であり、
前記関数演算部は、前記共通鍵Kと前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r及びρを算出するように構成されており、
当該暗号化装置は、
前記値ρを用い、gTを巡回群GTの生成元とし、τを加法単位元以外の定数とした場合における関数値S=gTτ・ρ∈GTを算出するように構成された群演算部と、
前記関数値Sを単射関数Rに入力して得られるバイナリ系列である関数値R(S)と前記共通鍵Kとの排他的論理和値である第３暗号文C3を算出し、当該第３暗号文C3を出力するように構成された排他的論理和演算部と、をさらに有する、暗号化装置。
【請求項３】
請求項１の暗号化装置であって、
前記値ρを選択するように構成された選択部と、
前記値ρを用い、gTを巡回群GTの生成元とし、τを加法単位元以外の定数とした場合における関数値S=gTτ・ρ∈GTを算出するように構成された群演算部と、
前記関数値Sを単射関数Rに入力して関数値R(S)を算出し、当該関数値R(S)を前記共通鍵Kとするように構成された共通鍵生成部と、をさらに有し、
前記関数演算部は、前記関数値Sと前記暗号文C1とを前記衝突困難な関数Hに入力して前記値rを算出するように構成される、暗号化装置。
【請求項４】
請求項２の暗号化装置であって、
前記単射関数Rは、擬似的なランダム関数である、暗号化装置。
【請求項５】
請求項３の暗号化装置であって、
前記単射関数Rは、擬似的なランダム関数である、暗号化装置。
【請求項６】
請求項１の暗号化装置であって、
前記衝突困難な関数Hは、擬似的なランダム関数である、暗号化装置。
【請求項７】
請求項２の暗号化装置であって、
前記衝突困難な関数Hは、擬似的なランダム関数である、暗号化装置。
【請求項８】
請求項３の暗号化装置であって、
前記衝突困難な関数Hは、擬似的なランダム関数である、暗号化装置。
【請求項９】
請求項２の暗号化装置であって、
前記巡回群G1及び前記巡回群GTは、前記巡回群G1のn+1個の元γL (L=1,...,n+1)と巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対して前記巡回群GTの１個の元を出力する非退化な双線形関数eが存在する集合である、暗号化装置。
【請求項１０】
請求項９の暗号化装置であって、
前記値rと前記値ρと前記定数τとが有限体Fqの元であり、
前記巡回群G1及びG2の位数は、それぞれ、前記有限体Fqの位数q(q≧1)と等しい、暗号化装置。
【請求項１１】
請求項９又は１０の暗号化装置であって、
前記双線形関数eは、前記巡回群G1のn+1個の元γL(L=1,...,n+1)と前記巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対し、前記巡回群GTの元e=Πi=1n+1 Pair(γL, γL*)を出力する関数であり、Pairが前記巡回群G1の１個の元と前記巡回群G2の１個の元との組を前記巡回群GTの１個の元に移す非退化な双線形関数である、暗号化装置。
【請求項１２】
請求項３の暗号化装置であって、
前記巡回群G1及び前記巡回群GTは、前記巡回群G1のn+1個の元γL (L=1,...,n+1)と巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対して前記巡回群GTの１個の元を出力する非退化な双線形関数eが存在する集合である、暗号化装置。
【請求項１３】
請求項１２の暗号化装置であって、
前記値rと前記値ρと前記定数τとが有限体Fqの元であり、
前記巡回群G1及びG2の位数は、それぞれ、前記有限体Fqの位数q(q≧1)と等しい、暗号化装置。
【請求項１４】
請求項１２又は１３の暗号化装置であって、
前記双線形関数eは、前記巡回群G1のn+1個の元γL(L=1,...,n+1)と前記巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対し、前記巡回群GTの元e=Πi=1n+1 Pair(γL, γL*)を出力する関数であり、Pairが前記巡回群G1の１個の元と前記巡回群G2の１個の元との組を前記巡回群GTの１個の元に移す非退化な双線形関数である、暗号化装置。
【請求項１５】
暗号文C1と第２暗号文C2∈G1n+1とを含む値が入力される入力部と、
前記第２暗号文C2∈G1n+1と鍵情報D1*∈G2n+1とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出するように構成された双線形関数演算部と、
前記関数値S〜に対応する値と前記暗号文C1とを衝突困難な関数Hに入力して関数Hの関数値を算出するように構成された関数演算部と、
前記第２暗号文C2と、値ρ〜と、前記関数Hの関数値に対応する値r〜と、n次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n)と、基底ベクトルbi∈G1n+1(i=1,...,n+1)とに対して、C2=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を満たすか否かを判定し、その判定結果を出力するように構成された判定部と、を有し、
前記双線形関数eが巡回群G1のn+1個の元γL(L=1,...,n+1)(n≧1)と巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対して巡回群GTの１個の元を出力する非退化な双線形関数であり、前記基底ベクトルbi∈G1n+1 (i=1,...,n+1)のそれぞれが、前記巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルであり、bi*∈G2n+1(i=1,...,n+1)のそれぞれが、前記巡回群G2のn+1個の元を要素とするn+1次元の基底ベクトルであり、前記基底ベクトルbi∈G1n+1(i=1,...,n+1)の各要素と前記基底ベクトルbj*∈G2n+1(j=1,...,n+1)の各要素とを前記双線形関数eに入力して得られる関数値が、クロネッカーのデルタ関数δ(i,j)を用いてgTτ・δ(i,j)∈GTと表現され、τが加法単位元以外の定数であり、gTが前記巡回群GTの生成元であり、w→=(w1,...,wn)がn次元ベクトルであり、wμ(μ=1,...,n)が前記n次元ベクトルw→=(w1,...,wn)の要素であり、αが選択された値であり、前記鍵情報D1*∈G2n+1がD1*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1である、復号装置。
【請求項１６】
請求項１５の復号装置であって、
前記入力部に入力される前記暗号文C1と前記第２暗号文C2∈G1n+1とを含む値は、バイナリ系列である第３暗号文C3をさらに含み、
当該復号装置は、前記関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と前記第３暗号文C3との排他的論理和値K〜を算出するように構成された排他的論理和演算部をさらに含み、
前記関数演算部は、前記排他的論理和値K〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜及びρ〜を算出するように構成され、
前記判定部は、
前記n次元ベクトルv→の要素vμ(μ=1,...,n)と前記値r〜及びρ〜とを用い、関数値C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を算出するように構成されたベクトル演算部と、
前記関数値C2〜と前記第２暗号文C2とが等しいか否かを判定するように構成された比較部と、を含み、
当該復号装置は、前記比較部での判定結果が、前記演算結果C2〜と前記第２暗号文C2とが等しい旨の判定結果である場合に、前記排他的論理和値K〜を共通鍵とし、当該排他的論理和値K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するように構成された共通鍵復号部をさらに有する、復号装置。
【請求項１７】
請求項１５の復号装置であって、
前記関数演算部は、前記関数値S〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜を算出するように構成され、
前記判定部は、
前記第２暗号文C2と前記値r〜と前記n次元ベクトルv→の要素vμ(μ=1,...,n)とを用い、関数値λ=C2-r〜・Σμ=1nvμ・bμ∈G1n+1を算出するように構成されたベクトル演算部と、
前記関数値λと値βμ(μ=1,...,n)に対する補助鍵情報D2*=Σμ=1nβμ・bμ*とを前記双線形関数eに入力して関数値e(λ,D2*)を算出するように構成された第２双線形関数演算部と、
前記関数値e(λ,D2*)が e(λ,D2*)=1∈GTを満たすか否かを判定するように構成された比較部と、を含み、
当該復号装置は、前記比較部での判定結果が、e(λ,D2*)=1∈GTを満たす旨の判定結果である場合に、前記関数値S〜を単射関数Rに入力して得られる関数値R(S〜)を共通鍵K〜とし、当該共通鍵K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するように構成された共通鍵復号部をさらに有する、復号装置。
【請求項１８】
請求項１６又は１７の復号装置であって、
前記単射関数Rは、擬似的なランダム関数である、復号装置。
【請求項１９】
請求項１５から１７の何れかの復号装置であって、
前記衝突困難な関数Hは、擬似的なランダム関数である、復号装置。
【請求項２０】
請求項１５から１７の何れかの復号装置であって、
前記巡回群G1の生成元をg1とし、κ1を加法単位元以外の定数とした場合における、κ1・g1をi次元目の要素とし、残りのn個の要素を前記巡回群G1の単位元とする、n+1次元の基底ベクトルをそれぞれai∈G1n+1(i=1,...,n+1)とし、n+1行n+1列の行列をＸとし、当該行列Ｘのi行j列の要素をχi,jとした場合に、前記基底ベクトルbiがbi=Σj=1n+1χi,j・ajを満たし、
前記巡回群G2の生成元をg2とし、κ2を加法単位元以外の定数とした場合における、κ2・g2をi次元目の要素とし、残りのn個の要素を前記巡回群G2の単位元とする、n+1次元の基底ベクトルをそれぞれai*∈G2n+1(i=1,...,n+1)とし、n+1行n+1列の行列をＸ*とし、当該行列Ｘ*のi行j列の要素をχi,j*とした場合に、前記基底ベクトルbi*がbi*=Σj=1n+1χi,j*・aj*を満たす、復号装置。
【請求項２１】
請求項１５から１７の何れかの復号装置であって、
前記値r〜と前記値ρ〜と前記定数τと前記値αとが有限体Fqの元であり、
前記巡回群G1及びG2の位数は、それぞれ、前記有限体Fqの位数q(q≧1)と等しい、復号装置。
【請求項２２】
請求項１５から１７の何れかの復号装置であって、
前記双線形関数eは、前記巡回群G1のn+1個の元γL(L=1,...,n+1)と前記巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対し、前記巡回群G1の１個の元と前記巡回群G2の１個の元との組を前記巡回群GTの１個の元に移す非退化な双線形関数をPairとした場合における、前記巡回群GTの元e=ΠL=1n+1 Pair(γL, γL*)を出力する関数である、復号装置。
【請求項２３】
暗号化装置と復号装置とで実行されるセキュリティ方法であって、
(A) 前記暗号化装置において、平文Mと共通鍵Kとを共通鍵暗号関数に入力して暗号文C1を算出し、当該暗号文C1を出力するステップと、
(B) 前記暗号化装置において、前記共通鍵Kに対応する値と前記暗号文C1に対応する値とを含む値を衝突困難な関数Hに入力して関数Hの第１関数値を算出するステップと、
(C) 前記暗号化装置において、前記関数Hの第１関数値に対応する値rと、前記共通鍵Kに対応する値ρと、n次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n、n≧1)と、巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルbi∈G1n+1(i=1,...,n+1)とを用い、第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出し、当該第２暗号文C2を出力するステップと、
(D) 前記復号装置に、前記暗号文C1と前記第２暗号文C2∈G1n+1とを含む値が入力されるステップと、
(E) 前記復号装置において、前記第２暗号文C2∈G1n+1と鍵情報D1*とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出するステップと、
(F) 前記復号装置において、前記関数値S〜に対応する値と前記暗号文C1とを前記衝突困難な関数Hに入力して関数Hの第２関数値を算出するステップと、
(G) 前記復号装置において、前記第２暗号文C2と、前記値ρ〜と、前記関数Hの第２関数値に対応する値r〜と、前記n次元ベクトルv→の要素vμと、基底ベクトルbi∈G1n+1 (i=1,...,n+1)とに対して、C2=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を満たすか否かを判定するステップと、を有し、
前記双線形関数eが巡回群G1のn+1個の元γL(L=1,...,n+1)(n≧1)と巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対して巡回群GTの１個の元を出力する非退化な双線形関数であり、前記基底ベクトルbi∈G1n+1 (i=1,...,n+1)のそれぞれが、前記巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルであり、基底ベクトルbi*∈G2n+1(i=1,...,n+1) のそれぞれが、前記巡回群G2のn+1個の元を要素とするn+1次元の基底ベクトルであり、前記基底ベクトルbi∈G1n+1(i=1,...,n+1)の各要素と前記基底ベクトルbj*∈G2n+1(j=1,...,n+1)の各要素とを前記双線形関数eに入力して得られる関数値がクロネッカーのデルタ関数δ(i,j)を用いてgTτ・δ(i,j)∈GTと表現され、τが加法単位元以外の定数であり、gTが前記巡回群GTの生成元であり、αが選択された値であり、w→=(w1,...,wn)がn次元ベクトルであり、wμ(μ=1,...,n)が前記n次元ベクトルw→=(w1,...,wn)の要素であり、前記鍵情報D1*がD1*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1である、セキュリティ方法。
【請求項２４】
請求項２３のセキュリティ方法であって、
前記ステップ(B)は、前記共通鍵Kと前記暗号文C1とを衝突困難な関数Hに入力して前記値r及びρを算出するステップを含み、
前記ステップ(C)は、
前記復号装置において、前記値ρを用いて関数値S=gTτ・ρ∈GTを算出するステップと、
前記復号装置において、前記関数値Sを単射関数Rに入力して得られるバイナリ系列である関数値R(S)と前記共通鍵Kとの排他的論理和値である第３暗号文C3を算出し、当該第３暗号文C3を出力するステップと、
前記復号装置において、n次元ベクトルv→の各要素vμ(μ=1,...,n)と前記値r及びρとを用い、前記第２暗号文C2を算出し、当該第２暗号文C2を出力するステップと、を含み、
前記ステップ(D)は、
前記復号装置において、前記復号装置に前記暗号文C1と前記第２暗号文C2∈G1n+1と前記第３暗号文C3とを含む値が入力されるステップを含み、
前記ステップ(F)は、
前記復号装置において、前記関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と前記第３暗号文C3との排他的論理和値K〜を算出するステップと、
前記復号装置において、前記排他的論理和値K〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜及びρ〜を算出するステップと、を含み、
前記ステップ(G)は、
前記復号装置において、前記n次元ベクトルv→の要素vμ(μ=1,...,n)と前記値r〜及びρ〜とを用い、関数値C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を算出するステップと、
前記復号装置において、前記関数値C2〜と前記第２暗号文C2とが等しいか否かを判定し、その判定結果が、前記関数値C2〜と前記第２暗号文C2とが等しい旨の判定結果である場合に、前記排他的論理和値K〜を共通鍵とし、当該排他的論理和値K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するステップと、を含む、セキュリティ方法。
【請求項２５】
請求項２３のセキュリティ方法であって、
前記ステップ(A)は、
前記暗号化装置において、前記値ρを選択するステップと、
前記暗号化装置において、前記値ρを用いて関数値S=gTτ・ρ∈GTを算出するステップと、
前記暗号化装置において、前記関数値Sを単射関数Rに入力して得られる関数値R(S)を共通鍵Kとし、当該共通鍵Kと平文Mとを共通鍵暗号関数に入力して暗号文C1を算出し、当該暗号文C1を出力するステップと、を含み、
前記ステップ(B)は、前記暗号化装置において、前記関数値Sと前記暗号文C1とを前記衝突困難な関数Hに入力して前記値rを算出するステップを含み、
前記ステップ(C)は、前記暗号化装置において、n次元ベクトルv→の各要素vμ(μ=1,...,n)と前記値rと前記値ρとを用い、前記第２暗号文を算出し、当該第２暗号文C2を出力するステップを含み、
前記ステップ(F)は、前記復号装置において、前記関数値S〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜を算出するステップを含み、
前記ステップ(G)は、
前記復号装置において、前記第２暗号文C2と前記値r〜と前記n次元ベクトルv→の各要素vμ(μ=1,...,n)とを用い、関数値λ=C2-r〜・(Σμ=1nvμ・bμ)∈G1n+1を算出するステップと、
前記復号装置において、前記関数値λと補助鍵情報D2*とを前記双線形関数eに入力して関数値e(λ,D2*)を算出するステップと、
前記復号装置において、前記関数値e(λ,D2*)が e(λ,D2*)=1∈GTを満たすか否かを判定し、その判定結果が、e(λ,D2*)=1∈GTを満たす旨の判定結果である場合に、前記関数値S〜を単射関数Rに入力して得られる関数値R(S〜)を共通鍵K〜とし、当該共通鍵K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するステップと、を含む、セキュリティ方法。
【請求項２６】
(A) 暗号化装置の第１手段において、平文Mと共通鍵Kとを共通鍵暗号関数に入力して暗号文C1を算出し、当該暗号文C1を出力するステップと、
(B) 前記暗号化装置の第２手段において、前記共通鍵Kに対応する値と前記暗号文C1に対応する値とを含む値を衝突困難な関数Hに入力して関数Hの関数値を算出するステップと、
(C) 前記暗号化装置の第３手段において、前記関数Hの関数値に対応する値rと、前記共通鍵Kに対応する値ρと、n次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n)(n≧1)と、巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルbi∈G1n+1(i=1,...,n+1)とを用い、第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出し、当該第２暗号文C2を出力するステップと、
を有する暗号化方法。
【請求項２７】
請求項２６の暗号化方法であって、
前記共通鍵Kは、バイナリ系列であり、
前記ステップ(B)は、前記暗号化装置の第４手段において、前記共通鍵Kと前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r及びρを算出するステップを含み、
当該暗号化方法は、
前記暗号化装置の第５手段において、前記値ρを用い、gTを巡回群GTの生成元とし、τを加法単位元以外の定数とした場合における関数値S=gTτ・ρ∈GTを算出するステップと、
前記暗号化装置の第６手段において、前記関数値Sを単射関数Rに入力して得られるバイナリ系列である関数値R(S)と前記共通鍵Kとの排他的論理和値である第３暗号文C3を算出し、当該第３暗号文C3を出力するステップと、をさらに有する、暗号化方法。
【請求項２８】
請求項２６の暗号化方法であって、
前記暗号化装置の第７手段において、前記値ρを選択するステップと、
前記暗号化装置の第８手段において、前記値ρを用い、gTを巡回群GTの生成元とし、τを加法単位元以外の定数とした場合における関数値S=gTτ・ρ∈GTを算出するステップと、
前記暗号化装置の第９手段において、前記関数値Sを単射関数Rに入力して関数値R(S)を算出し、当該関数値R(S)を前記共通鍵Kとするステップと、をさらに有し、
前記ステップ(B)は、前記暗号化装置の第１０手段において、前記関数値Sと前記暗号文C1とを前記衝突困難な関数Hに入力して前記値rを算出するステップを含む、暗号化方法。
【請求項２９】
(A) 暗号文C1と第２暗号文C2∈G1n+1とを含む値が復号装置に入力されるステップと、
(B) 前記復号装置の第１手段において、前記第２暗号文C2∈G1n+1と鍵情報D1*∈G2n+1とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出するステップと、
(C) 前記復号装置の第２手段において、前記関数値S〜に対応する値と前記暗号文C1とを衝突困難な関数Hに入力して関数Hの関数値を算出するステップと、
(D) 前記復号装置の第３手段において、前記第２暗号文C2と、前記関数Hの関数値に対応する値r〜と、値ρ〜と、n次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n)と、基底ベクトルbi∈G1n+1(i=1,...,n+1)とに対して、C2=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を満たすか否かを判定し、その判定結果を出力するステップと、を有し、
前記双線形関数eが巡回群G1のn+1個の元γL(L=1,...,n+1)(n≧1)と巡回群G2のn+1個の元γL*(L=1,...,n+1)との入力に対して巡回群GTの１個の元を出力する非退化な双線形関数であり、前記基底ベクトルbi∈G1n+1 (i=1,...,n+1)のそれぞれが、前記巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルであり、bi*∈G2n+1(i=1,...,n+1)のそれぞれが、前記巡回群G2のn+1個の元を要素とするn+1次元の基底ベクトルであり、前記基底ベクトルbi∈G1n+1(i=1,...,n+1)の各要素と前記基底ベクトルbj*∈G2n+1(j=1,...,n+1)の各要素とを前記双線形関数eに入力して得られる関数値が、クロネッカーのデルタ関数δ(i,j)を用いてgTτ・δ(i,j)∈GTと表現され、τが加法単位元以外の定数であり、gTが前記巡回群GTの生成元であり、w→=(w1,...,wn)がn次元ベクトルであり、wμ(μ=1,...,n)が前記n次元ベクトルw→=(w1,...,wn)の要素であり、αが選択された値であり、前記鍵情報D1*∈G2n+1がD1*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1である、復号方法。
【請求項３０】
請求項２９の復号方法であって、
前記ステップ(A)で入力される前記暗号文C1と前記第２暗号文C2∈G1n+1とを含む値は、バイナリ系列である第３暗号文C3をさらに含み、
当該復号方法は、前記復号装置の第４手段において、前記関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と前記第３暗号文C3との排他的論理和値K〜を算出するステップをさらに含み、
前記ステップ(C)は、前記復号装置の第５手段において、前記排他的論理和値K〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜及びρ〜を算出するステップを含み、
前記ステップ(D)は、
(D-1) 前記復号装置の第６手段において、前記n次元ベクトルv→の要素vμ(μ=1,...,n)と前記値r〜及びρ〜とを用い、関数値C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を算出するステップと、
(D-2) 前記復号装置の第７手段において、前記関数値C2〜と前記第２暗号文C2とが等しいか否かを判定するステップと、を含み、
当該復号方法は、前記ステップ(D-2)での判定結果が、前記演算結果C2〜と前記第２暗号文C2とが等しい旨の判定結果である場合に、前記復号装置の第８手段において、前記排他的論理和値K〜を共通鍵とし、当該排他的論理和値K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するステップをさらに有する。
【請求項３１】
請求項２９の復号方法であって、
前記ステップ(C)は、前記復号装置の第９手段において、前記関数値S〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜を算出するステップを含み、
前記ステップ(D)は、
(D-1) 前記復号装置の第１０手段において、前記第２暗号文C2と前記値r〜と前記n次元ベクトルv→の要素vμ(μ=1,...,n)とを用い、関数値λ=C2-r〜・Σμ=1nvμ・bμ∈G1n+1を算出するステップと、
(D-2) 前記復号装置の第１１手段において、前記関数値λと値βμ(μ=1,...,n)に対する補助鍵情報D2*=Σμ=1nβμ・bμ*とを前記双線形関数eに入力して関数値e(λ,D2*)を算出するステップと、
(D-3) 前記復号装置の第１２手段において、前記関数値e(λ,D2*)が e(λ,D2*)=1∈GTを満たすか否かを判定するステップと、を含み、
当該復号方法は、前記ステップ(D-3)での判定結果が、e(λ,D2*)=1∈GTを満たす旨の判定結果である場合に、前記復号装置の第１３手段において、前記関数値S〜を単射関数Rに入力して得られる関数値R(S〜)を共通鍵K〜とし、当該共通鍵K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するステップをさらに有する。
【請求項３２】
請求項１から３の何れかの暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項３３】
請求項１５から１７の何れかの復号装置としてコンピュータを機能させるためのプログラム。
【請求項３４】
請求項１から３の何れかの暗号化装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項３５】
請求項１５から１７の何れかの復号装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に関し、特に暗号技術に関する。
【背景技術】
【０００２】
暗号研究分野の一つに、選択暗号文攻撃(CCA: Chosen ciphertext attack)に対する安全性（CCA安全性）を持つ暗号方式（CCA安全な暗号方式）の構築がある。特に近年、選択平文攻撃(CPA: Chosen Plaintext Attack)に対する安全性しか持たないIDベース暗号(IBE: Identity-based Encryption)（例えば、非特許文献１参照）からCCA安全な暗号方式を構成しようとする研究が盛んに行われている。例えば、非特許文献２では、One-Time 署名を用い、CPA安全な任意のIDベース暗号からCCA安全な暗号方式を構成する方法が提案されている(CHK 変換方式)。また、例えば、非特許文献３では、メッセージ認証子（MAC: Message Authentication Code）とビットコミットメント方式とを用い、CPA安全な任意のIDベース暗号からCCA安全な暗号方式を構成する方法が提案されている(BK 変換方式)。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D.Boneh, M. Franklin, "Identity based encryption from the Weil pairing," Crypto 2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp.213-229, 2001.
【非特許文献２】R. Canetti, S. Halevi, J. Katz, “Chosen-Ciphertext Security from Identity-Based Encryption,” Proc. of EUROCRYPT’04, LNCS 3027, pp. 207-222, 2004.
【非特許文献３】D. Boneh, J. Katz, “Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption,” Proc. of CT-RSA’05, LNCS 3376, pp.87-103, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述したCHK 変換方式によって生成される暗号文は、平文の暗号文と当該平文の暗号文のOne-Time 署名と当該One-Time 署名を検証するための署名鍵とを含む。そのため、このCHK 変換方式の暗号文空間には、平文の暗号文のための空間だけではなく、One-Time 署名や署名鍵のための空間が必要となる。また、上述したBK 変換方式によって生成される暗号文は、平文の暗号文とメッセージ認証子とビットコミットメント列とを含む。そのため、BK 変換方式の暗号文空間には、平文の暗号文だけではなく、メッセージ認証子やビットコミットメント列のための空間が必要となる。すなわち、CHK 変換方式やBK 変換方式の暗号文空間には、CCA安全性を向上させるためのみに用いる2次元の空間が余分に設けられている。しかしながら、暗号文空間のサイズが大きくなるほど演算量やデータ量が増加するため、暗号文空間のサイズはできるだけ小さいほうが望ましい。【０００５】
また、IDベース暗号は、暗号化を行う者が、暗号化を行う前に復号を行う者のIDを取得しておかなければならない。これに対し、暗号化を行う者が復号を行う者を特定することなく暗号文を生成でき、所望の条件に合致した者が当該暗号文を復号できる方式を構成できれば便利である。【０００６】
本発明はこのような点に鑑みてなされたものであり、利便性が高く、CCA安全性を向上させるためのみに用いる空間を暗号文空間に設けることなくCCA安全性を向上できる暗号方式を提供する。
【課題を解決するための手段】
【０００７】
本発明の暗号化処理では、少なくとも、平文Mと共通鍵Kとを共通鍵暗号関数に入力して第１暗号文C1を算出し、共通鍵Kに対応する値と第１暗号文C1に対応する値とを含む値を衝突困難な関数Hに入力して関数Hの関数値を算出し、関数Hの関数値に対応する値rと、共通鍵Kに対応する値ρと、n次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n、n≧1)と、巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルbi∈G1n+1(i=1,...,n+1)とを用い、第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出する。【０００８】
これに対応する復号処理では、少なくとも、第２暗号文C2∈G1n+1と鍵情報D1*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出し、関数値S〜に対応する値と第１暗号文C1とを衝突困難な関数Hに入力して関数Hの関数値を算出する。なお、鍵情報D1*が正しい場合、「関数値S〜に対応する値」は、暗号化処理で衝突困難な関数Hに入力された「共通鍵Kに対応する値」と等しくなる。そして、値ρ〜と、関数Hの関数値に対応する値r〜と、n次元ベクトルv→の要素vμと、基底ベクトルbi∈G1n+1 (i=1,...,n+1)とに対して、C2=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を満たすか否かを判定する。【０００９】
ここで、暗号化処理の処理に用いられる値rは、共通鍵Kに対応する値と第１暗号文C1に対応する値とを含む値とを衝突困難な関数Hに入力して得られる関数値に対応する。そのため、第１暗号文C1や共通鍵Kが異なれば値rも異なる。よって、共通鍵Kを知らない攻撃者は、たとえ、正しく取得した第１暗号文C1’からそれと異なる第１暗号文C1を生成することができたとしても、生成した第１暗号文C1に対応する値rを正しく生成することはできない。よって、復号処理において、関数値S〜に対応する値と第１暗号文C1とを衝突困難な関数Hに入力して値r〜を復元し、C2=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を満たすか否かを判定する構成とすることで、CCA安全性を向上させることができる。なお、「値１に対応する値２」とは、値２が値１である場合、又は、値２が少なくとも値１に依存する値である場合を意味する。【００１０】
また、第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1は、第２暗号文C2の基本構成となるn次元ベクトルv→=(v1,...,vn)のためのn次元空間と、共通鍵Kを含む値に対応する値ρのための１次元空間とのみによって構成される。すなわち、第２暗号文C2は、CCA安全性を向上させるためのみに用いる空間を必要としない。【００１１】
また、本発明の暗号化処理の一例では、平文Mと共通鍵Kとを共通鍵暗号関数に入力して第１暗号文C1を算出し、共通鍵Kと第１暗号文C1とを衝突困難な関数Hに入力して値r及びρを算出し、τを加法単位元以外の定数とした場合における関数値S=gTτ・ρ∈GTを算出し、関数値Sを単射関数Rに入力して得られるバイナリ系列である関数値R(S)と共通鍵Kとの排他的論理和値である第３暗号文C3を算出し、第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出する。【００１２】
これに対応する復号処理では、例えば、第２暗号文C2∈G1n+1と鍵情報D1*とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出し、関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と第３暗号文C3との排他的論理和値K〜を算出し、排他的論理和値K〜と第１暗号文C1とを衝突困難な関数Hに入力して値r〜及びρ〜を算出し、関数値C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を算出し、関数値C2〜と第２暗号文C2とが等しいか否かを判定し、関数値C2〜と第２暗号文C2とが等しい旨の判定結果である場合に、排他的論理和値K〜を共通鍵とし、当該排他的論理和値K〜と第１暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出する。【００１３】
また、暗号化処理の他の例では、値ρを選択し、τを加法単位元以外の定数とした場合における関数値S=gTτ・ρ∈GTを算出し、関数値Sを単射関数Rに入力して得られる関数値R(S)を共通鍵Kとし、当該共通鍵Kと平文Mとを共通鍵暗号関数に入力して第１暗号文C1を算出し、関数値Sと第１暗号文C1とを衝突困難な関数Hに入力して値rを算出し、第２暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出する。【００１４】
これに対応する復号処理では、例えば、第２暗号文C2∈G1n+1と鍵情報D1*とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出し、関数値S〜と第１暗号文C1とを衝突困難な関数Hに入力して値r〜を算出し、第２暗号文C2と値r〜とn次元ベクトルv→の各要素vμ(μ=1,...,n)とを用い、関数値λ=C2-r〜・(Σμ=1nvμ・bμ)∈G1n+1を算出し、関数値λと補助鍵情報D2*=Σμ=1nβμ・bμ*とを双線形関数eに入力して関数値e(λ,D2*)を算出し、関数値e(λ,D2*)が e(λ,D2*)=1∈GTを満たすか否かを判定し、e(λ,D2*)=1∈GTを満たす旨の判定結果である場合に、関数値S〜を単射関数Rに入力して得られる関数値R(S〜)を共通鍵K〜とし、当該共通鍵K〜と第１暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出する。【００１５】
また、好ましい単射関数Rや衝突困難な関数Hの例は、擬似的なランダム関数である。これにより、より安全性が向上する。
【発明の効果】
【００１６】
上述のように、本発明の暗号方式は、利便性が高く、CCA安全性を向上させるためのみに用いる空間を暗号文空間に設けることなくCCA安全性を向上できる。
【図面の簡単な説明】
【００１７】
【図１】図１は、第１実施形態の暗号システムの構成を説明するための図である。
【図２】図２は、図１の暗号化装置の構成を説明するための図である。
【図３】図３は、図１の復号装置の構成を説明するための図である。
【図４】図４は、図１の鍵生成装置の構成を説明するための図である。
【図５】図５は、第１実施形態の暗号化処理を説明するための図である。
【図６】図６は、第１実施形態の鍵情報の生成処理を説明するための図である。
【図７】図７は、第１実施形態の復号処理を説明するための図である。
【図８】図８は、第２実施形態の暗号システムの構成を説明するための図である。
【図９】図９は、図８の暗号化装置の構成を説明するための図である。
【図１０】図１０は、図８の復号装置の構成を説明するための図である。
【図１１】図１１は、図８の鍵生成装置の構成を説明するための図である。
【図１２】図１２は、第２実施形態の暗号化処理を説明するための図である。
【図１３】図１３は、第２実施形態の鍵情報の生成処理を説明するための図である。
【図１４】図１４は、第２実施形態の復号処理を説明するための図である。
【発明を実施するための形態】
【００１８】
本発明を実施するための形態を説明する。
【００１９】
〔定義〕
まず、本形態で使用する用語や記号を定義する。
【００２０】
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
Ｚ：Ｚは整数集合を表す。
ｋ：ｋはセキュリティパラメータ（k∈Z, k>0）を表す。
【００２１】
{0,1}*：{0,1}*は任意ビット長のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。しかし、{0,1}*は整数0及び1からなる系列に限定されない。{0,1}*は位数2の有限体又はその拡大体と同義である。
【００２２】
{0,1}ζ：{0,1}ζはビット長ζ（ζ∈Z, ζ>0）のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。しかし、{0,1}ζは整数0及び1からなる系列に限定されない。{0,1}ζは位数2の有限体（ζ=1の場合）又はそれをζ次拡大した拡大体（ζ>1の場合）と同義である。
【００２３】
(+):(+)はバイナリ系列間の排他的論理和演算子を表す。例えば、10110011(+)11100001=01010010を満たす。
【００２４】
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。なお、有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。また、有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献１「ISO/IEC 18033-2: Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers」に開示されている。
【００２５】
0F：0Fは有限体Fqの加法単位元を表す。
1F：1Fは有限体Fqの乗法単位元を表す。
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0 Fを満たす。
【００２６】
E：Eは有限体Fq上で定義された楕円曲線を表す。Eはアフィン（affine）座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6          …(1)
（ただし、a1,a2,a3,a4,a6∈Fq）を満たすx,y∈Fqからなる点(x,y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。楕円曲線E上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線E上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている（例えば、参考文献１、参考文献２「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」、参考文献３「イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0」等参照）。
【００２７】
また、楕円曲線E上の有理点からなる有限集合は位数p(p≧1)の部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数を＃Eとし、pを＃Eを割り切る大きい素数とした場合、楕円曲線Eのp等分点からなる有限集合E[p]は、楕円曲線E上の有理点からなる有限集合の部分群を構成する。なお、楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値p・Aがp・A＝Ｏを満たす点を意味する。
【００２８】
G1, G2,GT：G1, G2, GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における１のｐ乗根からなる有限集合である。
【００２９】
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈G1に対するχ・Ω∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G1に対するΩ1+Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχ・Ω∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G2に対するΩ1+Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1,Ω2∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
【００３０】
G1n+1：G1n+1はn+1(n≧1)個の巡回群G1の直積を表す。
G2n+1：G2n+1はn+1個の巡回群G2の直積を表す。
g1, g2,gT：g1, g2, gTは巡回群G1, G2,GTの生成元を表す。
V：Vはn+1個の巡回群G1の直積からなるn+1次元のベクトル空間を表す。
V*：V*はn+1個の巡回群G2の直積からなるn+1次元のベクトル空間を表す。
【００３１】
e：eは直積G1n+1と直積G2n+1との直積G1n+1×G2n+1を巡回群GTに写す非退化な双線形写像（bilinear map）を計算するための関数（「双線形関数」と呼ぶ）を表す。双線形関数eは、巡回群G1のn+1個の元γL(L=1,...,n+1)(n≧1)と巡回群G2のn+1個の元γL*(L=1,...,n+1)とを入力とし、巡回群GTの１個の元を出力する。
e：G1n+1×G2n+1→GT            …(2)
【００３２】
双線形関数eは以下の性質を満たす。
［双線形性］すべてのΓ1∈G1n+1，Γ2∈G2n+1及びν，κ∈Fqについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ          …(3)
［非退化性］すべての
Γ1∈G1n+1，Γ2∈G2n+1          …(4)
を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΓ1∈G1n+1，Γ2∈G2n+1についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００３３】
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT            …(5)
を用いて双線形関数eを構成する。本形態の双線形関数eは、巡回群G1のn+1個の元γL(L=1,...,n+1)からなるn+1次元ベクトル(γ1,...,γn+1)と、巡回群G2のn+1個の元γL*(i=1,...,n+1)からなるn+1次元ベクトル(γ1*,...,γn+1*)との入力に対し、巡回群GTの１個の元
e=ΠL=1n+1 Pair(γL, γL*)          …(6)
を出力する関数である。
【００３４】
なお、双線形関数Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する関数であり、以下の性質を満たす。
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(7)
［非退化性］すべての
Ω1∈G1，Ω2∈G2          …(8)
を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてPair(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
【００３５】
なお、双線形関数Pairの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、参考文献４「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。また、楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(Ω1,phi(Ω2))（Ω1∈G1，Ω2∈G2）を双線形関数Pairとして用いてもよい（例えば、参考文献２等参照）。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズム（参考文献５「V. S. Miller, “Short Programs for functions on Curves,”1986，インターネット＜http://crypto.stanford.edu/miller/miller.pdf＞」などが存在する。また、ペアリング演算を効率的に行うための楕円曲線や巡回群の構成方法はよく知られている（例えば、参考文献２、参考文献６「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献７「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献８「R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/」等参照）。
【００３６】
ai(i=1,...,n+1)：巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1・g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元（加法的に「0」と表現）とするn+1次元の基底ベクトルである。この場合、n+1次元の基底ベクトルai(i=1,...,n+1)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1=(κ1・g1,0,0,...,0)
a2=(0,κ1・g1,0,...,0)           …(9)
...
an+1=(0,0,0,...,κ1・g1)
【００３７】
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルaiは直交基底であり、巡回群G1のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルai(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルaiは前述のベクトル空間Vを張る。
【００３８】
ai*(i=1,...,n+1)：ai*は巡回群G2のn+1個の元を要素とするn+1次元の基底ベクトルを表す。基底ベクトルai*の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元（加法的に「0」と表現）とするn+1次元の基底ベクトルである。この場合、基底ベクトルai*(i=1,...,n+1)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*=(κ2・g2,0,0,...,0)
a2*=(0,κ2・g2,0,...,0)            …(10)
...
an+1*=(0,0,0,...,κ2・g2)
【００３９】
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*は直交基底であり、巡回群G2のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルai*(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルai*は前述のベクトル空間V*を張る。
【００４０】
なお、基底ベクトルaiと基底ベクトルai*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(ai, aj*)=gTτ・δ(i,j)           …(11)
を満たす。すなわち、i=jの場合には、式(6)(7)の関係から、
e(ai, aj*)= Pair(κ1・g1,κ2・g2)・Pair(0, 0)・...・Pair(0, 0)
= Pair(g1, g2)κ1・κ2・Pair(g1, g2)0・0・...・Pair(g1, g2)0・0
= Pair(g1, g2)κ1・κ2=gTτ
を満たす。一方、i≠jの場合には、e(ai, aj*)は、Pair(κ1・g1,κ2・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(7)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、
e(ai, aj*)=e(g1, g2)0=gT0
を満たす。
【００４１】
特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(ai, aj*)=gTδ(i,j)           …(12)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルai*とは双対正規直交基底であり、ベクトル空間Vとベクトル空間V*とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間（DPVS:Dual Paring Vector space)〕である。
【００４２】
A：Aは基底ベクトルai(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。例えば、基底ベクトルai(i=1,...,n+1)が式(9)によって表現される場合、行列Aは、
【００４３】
【数１】
2010123112.tif 000003
【００４４】
となる。
【００４５】
A*：A*は基底ベクトルai*(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+1)が式(10)によって表現される場合、行列A*は、
【００４６】
【数２】
2010123112.tif 000004
【００４７】
となる。
【００４８】
X：Xは有限体Fqの元を要素とするn+1行n+1列の行列を表す。行列Xは基底ベクトルaiの座標変換に用いられる。行列Xのi行j列(i=1,...,n+1,j=1,...,n+1)の要素をχi,j∈Fqとすると、行列Xは、
【００４９】
【数３】
2010123112.tif 000005
【００５０】
となる。なお、行列Xの各要素χi,jを変換係数と呼ぶ。
【００５１】
X *：X *は行列Xの逆行列の転置行列X*=( X-1)Tを表す。行列X *は基底ベクトルai*の座標変換に用いられる。行列X *のi行j列の要素をχi,j*∈Fqとすると、行列X*は、
【００５２】
【数４】
2010123112.tif 000006
【００５３】
となる。なお、行列X*の各要素χi,j*を変換係数と呼ぶ。
【００５４】
この場合、n+1行n+1列の単位行列をIとするとX・(X*)T=Ｉを満たす。すなわち、単位行列
【００５５】
【数５】
2010123112.tif 000007
【００５６】
に対し、
【００５７】
【数６】
2010123112.tif 000008
【００５８】
を満たす。ここで、n+1次元ベクトル
χi→=(χi,1,...,χi,n+1)            …(19)
χj→*=(χj,1*,...,χj,n+1*)           …(20)
を定義する。すると、式(18)の関係から、n+1次元ベクトルχi→とχj→*との内積は、
χi→・χj→*=δ(i,j)          …(21)
となる。
【００５９】
bi：biは巡回群G1のn+1個の元を要素とするn+1次元の基底ベクトルを表す。基底ベクトルbiは行列Xを用いて基底ベクトルai(i=1,...,n+1)を座標変換することで得られる。具体的には、基底ベクトルbiは、
bi=Σj=1n+1χi,j・aj          …(22)
の演算によって得られる。例えば、基底ベクトルaj(j=1,...,n+1)が式(9)によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。
【００６０】
bi=(χi,1・κ1・g1 ,χi,2・κ1・g1 ,...,χi,n+1・κ1・g1)     …(23)
巡回群G1のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルbi(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルbiは前述のベクトル空間Vを張る。
【００６１】
bi*：bi*は巡回群G2のn+1個の元を要素とするn+1次元の基底ベクトルを表す。行列X*を用いて基底ベクトルai*(i=1,...,n+1)を座標変換することで得られる。具体的には、基底ベクトルbi*は、
bi*=Σj=1n+1χi,j*・aj*          …(24)
の演算によって得られる。例えば、基底ベクトルaj*(j=1,...,n+1)が式(10)によって表現される場合、基底ベクトルbi*の各要素をそれぞれ列挙して表現すると、以下のようになる。
【００６２】
bi*=(χi,1*・κ2・g2 ,χi,2*・κ2・g2 ,...,χi,n+1*・κ2・g2)   …(25)
となる。巡回群G2のn+1個の元を要素とするすべてのn+1次元ベクトルは、n+1次元の基底ベクトルbi*(i=1,...,n+1)の線形和によって表される。すなわち、n+1次元の基底ベクトルbi*は前述のベクトル空間V*を張る。
【００６３】
なお、基底ベクトルbiと基底ベクトルbi*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(bi, bj*)=gTτ・δ(i,j)           …(26)
を満たす。すなわち、式(6)(21)(23)(25)の関係から、
【００６４】
【数７】
2010123112.tif 000009
【００６５】
を満たす。特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(bi, bj*)=gTδ(i,j)           …(27)
を満たす。この場合、基底ベクトルbiと基底ベクトルbi*とは、双対ペアリングベクトル空間（ベクトル空間Vとベクトル空間V*）の双対正規直交基底である。
【００６６】
なお、式(26)の関係を満たすのであれば、式(9)(10)で例示したもの以外の基底ベクトルai及びai*や、式(22)(24)で例示したもの以外の基底ベクトルbi及びbi*を用いてもよい。
【００６７】
B：Bは基底ベクトルbi(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。B=X・Aを満たす。例えば、基底ベクトルbiが式(23)によって表現される場合、行列Bは、
【００６８】
【数８】
2010123112.tif 000010
【００６９】
となる。
【００７０】
B*：B*は基底ベクトルbi*(i=1,...,n+1)を要素とするn+1行n+1列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+1)が式(25)によって表現される場合、行列B*は、
【００７１】
【数９】
2010123112.tif 000011
【００７２】
となる。
【００７３】
w→：w→は有限体Fqの元を要素とするn次元ベクトルを表す。
w→=(w1,...,wn)∈Fqn           …(30)
wμ：wμはn次元ベクトルのμ(μ=1,...,n)番目の要素を表す。
v→：v→は有限体Fqの元を要素とするn次元ベクトルを表す。
v→=(v1,...,vn)∈Fqn           …(31)
vμ：vμはn次元ベクトルのμ(μ=1,...,n)番目の要素を表す。
【００７４】
衝突困難な関数：「衝突困難な関数」とは、十分大きなセキュリティパラメータkに対して以下の条件を満たす関数h、又は、それとみなせる関数を表す。
【００７５】
Pr[A(h)=(x,y)|h(x)=h(y)∧x≠y]<ε(k)           …(32)
ただし、Pr[・]は事象[・]の確率であり、A(h)は関数hに対してh(x)=h(y)を満たす値x,y（x≠y）を算出する確率的多項式時間アルゴリズムであり、ε(k)はセキュリティパラメータkについての多項式である。衝突困難な関数の例は、参考文献１に開示された「cryptographic hash function」などのハッシュ関数である。
【００７６】
単射関数：「単射関数」とは、値域に属する元が何れもその定義域のただ一つの元の像として表される関数、又は、それとみなせる関数を表す。単射関数の例は、参考文献１に開示された「KDF(Key Derivation Function)」などのハッシュ関数である。
【００７７】
擬似的なランダム関数：「擬似的なランダム関数」とは、任意の確率的多項式時間アルゴリズムが集合Φζとその部分集合φζとを区別できない場合における、当該部分集合φζに属する関数、又は、それとみなせる関数を表す。ただし、集合Φζは集合{0,1}ζの元を集合{0,1}ζの元へ写すすべての関数の集合である。擬似的なランダム関数の例は、上述のようなハッシュ関数である。
【００７８】
H1：H1は２つのバイナリ系列（ω1,ω2）∈{0,1}k×{0,1}*を入力とし、有限体Fqの２つの元（ψ1,ψ2）∈Fq×Fqを出力する衝突困難な関数を表す。
H1：{0,1}k×{0,1}*→Fq×Fq           …(33)
【００７９】
このような関数H1の例は、ω1とω2とのビット連結値ω1||ω2を入力とし、参考文献１に開示された「cryptographic hash function」などのハッシュ関数と、「バイナリ系列から整数への変換関数（Octet string/integer conversion）」と、「バイナリ系列から有限体の元への変換関数（Octet string and integer/finite field conversion）」との演算を行い、有限体Fqの２つの元（ψ1,ψ2）∈Fq×Fqを出力する関数である。なお、関数H1は、擬似的なランダム関数であることが望ましい。
【００８０】
H2：H2は巡回群GTの元とバイナリ系列（ξ,ω2）∈GT ×{0,1}*を入力とし、有限体Fqの１つの元ψ∈Fqを出力する衝突困難な関数を表す。
H2：GT×{0,1}*→Fq          …(34)
【００８１】
このような関数H2の例は、巡回群GTの元ξ∈GTとバイナリ系列ω2∈{0,1}*とを入力とし、巡回群GTの元ξ∈GTを参考文献１に開示された「有限体の元からバイナリ系列への変換関数（Octet string and integer/finite field conversion）」に入力してバイナリ系列を求め、そのバイナリ系列とバイナリ系列ω2∈{0,1}*とのビット連結値に対して参考文献１に開示された「cryptographic hash function」などのハッシュ関数演算を行い、さらに「バイナリ系列から有限体の元への変換関数（Octet string and integer/finite field conversion）」の演算を行い、有限体Fqの１つの元ψ∈Fqを出力する関数である。なお、安全性の観点から、関数H2は擬似的なランダム関数であることがより望ましい。
【００８２】
R:Rは１つの巡回群GTの元ξ∈GTを入力とし、１つのバイナリ系列ω∈{0,1}kを出力する単射関数を表す。
R：GT→{0,1}k          …(35)
【００８３】
このような単射関数Rの例は、巡回群GTの元ξ∈GTを入力とし、参考文献１に開示された「有限体の元からバイナリ系列への変換関数（Octet string and integer/finite field conversion）」と、参考文献１に開示された「KDF(Key Derivation Function)」などのハッシュ関数との演算を行い、１つのバイナリ系列ω∈{0,1}kを出力する関数である。なお、安全性の観点から、関数Rは衝突困難な関数であることが望ましく、擬似的なランダム関数であることがより望ましい。
【００８４】
Enc：Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。共通鍵暗号方式の具体例は、カメリア（Camellia）やAESなどである。
Enck(M)：Enck(M)は、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。
Dec：Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。
Deck(C)：Deck(C)は、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。
【００８５】
〔内積述語暗号〕
次に、内積述語暗号の基本的な構成について説明する。
【００８６】
＜述語暗号＞
述語暗号（「関数暗号」と呼ぶ場合もある）とは、「属性情報」と呼ばれる情報と「述語情報」と呼ばれる情報との組み合わせが所定の論理式を「真」にする場合に暗号文が復号できる方式である。「属性情報」と「述語情報」の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。従来の述語暗号の構成は、例えば、参考文献９「"Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products," with Amit Sahai and Brent Waters One of 4 papers from Eurocrypt 2008 invited to the Journal of Cryptology」等に開示されている。
【００８７】
＜内積述語暗号＞
内積述語暗号は、属性情報や述語情報としてベクトルを用い、それらの内積が０となる場合に暗号文が復号される述語暗号である。内積述語暗号では、内積が０となることと論理式が「真」となることとが等価である。
【００８８】
［論理式と多項式との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
【００８９】
まず、「xがη1である」という命題１と「xがη2である」という命題２との論理和 (x=η1)∨(x=η2)を
(x-η1)・(x-η2)          …(36)
という多項式で表現する。すると、各真理値と式(36)の関数値との関係は以下のようになる。
【００９０】
【表１】
2010123112.tif 000012
[表1]から分かるように、論理和(x=η1)∨(x=η2)が真である場合、式(36)の関数値は0になり、論理和(x=η1)∨(x=η2)が偽である場合、式(36)の関数値は0以外の値となる。すなわち、論理和(x=η1)∨(x=η2)が真であることと、式(36)の関数値が0となることとは等価である。よって、論理和は式(36)で表現できる。
【００９１】
また、「xがη1である」という命題１と「xがη2である」という命題２との論理積 (x=η1)∧(x=η2)を
ι1・(x-η1)+ι2・(x-η2)          …(37)
という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式(37)の関数値とは以下の関係となる。
【００９２】
【表２】
2010123112.tif 000013
[表２]から分かるように、論理積 (x=η1)∧(x=η2)が真である場合、式(37)の関数値は0になり、論理積 (x=η1)∧(x=η2)が偽である場合、式(37)の関数値は0以外の値となる。すなわち、論理積 (x=η1)∧(x=η2)が真であることと、式(37)の関数値が0となることとは等価である。よって、論理積は式(37)で表現できる。
【００９３】
以上のように、式(36)と式(37)とを用いることで論理和や論理積からなる論理式を多項式f(x)で表現できる。例えば、論理式{(x=η1)∨(x=η2)∨(x=η3)}∧(x=η4)∧(x=η5)は、多項式
f(x)=ι1・{(x-η1)・(x-η2)・(x-η3)}+ι2・(x=η4)+ι3・(x=η5)  …(38)
で表現できる。
【００９４】
なお、式(36）では、１つの不定元xを用いて論理和を表現したが、複数の不定元を用いて論理和を表現することも可能である。例えば、２つの不定元x0及びx1を用い、「x0がη0である」という命題１と「x1がη1である」という命題２との論理和 (x0=η0)∨(x1=η1)を
(x0-η0)・(x1-η1)
という多項式で表現することも可能であり、３つ以上の不定元を用い、論理和を多項式で表現することも可能である。
【００９５】
また、式(37）では、１つの不定元xを用いて論理積を表現したが、複数の不定元を用いて論理積を表現することも可能である。例えば、また、「x0がη0である」という命題１と「x1がη1である」という命題２との論理積 (x0=η0)∧(x1=η1)を
ι0・(x0-η0)+ι1・(x1-η1)
という多項式で表現することも可能であり、３つ以上の不定元を用い、論理積を多項式で表現することも可能である。
【００９６】
論理和及び／又は論理積を含む論理式をH(H≧1)種類の不定元x0,...,xH-1を用いて表現した多項式をf(x0,...,xH-1)と表現する。また、各不定元x0,...,xH-1に対応する命題を「xhがηhである」とする。ただし、ηh（h=0,...H-1）は命題ごとに定まる定数である。この場合、当該論理式を示す多項式f(x0,...,xH-1)は、不定元xhと定数ηhとの差をとる多項式によって当該不定元xhが当該定数ηhであるという命題を表現し、命題をそれぞれ表現する多項式の積によって当該命題の論理和を表現し、命題又は命題の論理和をそれぞれ表現する多項式の線形和によって当該命題又は命題の論理和の論理積を表現し、それによって論理式を表現した多項式となる。例えば、５つの不定元x0,...,x4を用い、論理式{(x0=η0)∨(x1=η1)∨(x2=η2)}∧(x3=η3)∧(x4=η4)を多項式で表現すると、
f(x0,...,x4)=ι0・{(x0-η0)・(x1-η1)・(x2-η2)}+ι1・(x3=η3)+ι2・(x4=η4)
となる。
【００９７】
［多項式と内積の関係］
論理式を示す多項式f(x0,...,xH-1)は、２つのn次元ベクトルの内積で表現できる。すなわち、多項式f(x0,...,xH-1)は、当該多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトル
v→=(v1,...,vn)
と、当該多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトル
w→=(w1,...,wn)
との内積
f(x0,...,xH-1)=w→・v→
に等しい。すなわち、論理式を示す多項式f(x0,...,xH-1)が0であるか否かと、多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトルv→と、多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトルw→との内積が0であるか否かとは等価である。
【００９８】
f(x0,...,xH-1)=0  ←→  w→・v→=0
例えば、１つの不定元xで表現された多項式f(x)=θ0・x0+θ1・x+...+θn-1・xn-1は、２つのn次元ベクトル
w→=(w1,...,wn)=(θ0,...,θn-1)          …(39)
v→=(v1,...,vn)=(x0,...,xn-1)          …(40)
の内積
f(x)= w→・v→          …(41)
で表現できる。すなわち、論理式を示す多項式f(x)が0であるか否かと、式(41)の内積が0であるか否かとは等価である。
f(x)=0  ←→  w→・v→=0          …(42)
【００９９】
また、多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトルを
w→=(w1,...,wn)
とし、多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトル
v→=(v1,...,vn)
としても、論理式を示す多項式f(x0,...,xH-1)が0であるか否かと、ベクトルw→とベクトルv→との内積が0であるか否かとは等価である。
【０１００】
例えば、式(39)(40)の代わりに
w→=(w1,...,wn)=(x0,...,xn)        …(43)
v→=(v1,...,vn)=(θ1,...,θn-1)          …(44)
としても、論理式を示す多項式f(x)が0であるか否かと、式(41)の内積が0であるか否かとは等価である。
【０１０１】
内積述語暗号では、ベクトルv→=(v0,...,vn-1)及びw→=(w0,...,wn-1)の何れか一方を属性情報とし、他方を述語情報とし、属性情報と述語情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、n次元ベクトル(θ0,...,θn-1)が述語情報とされ、n次元ベクトル(x0,...,xn-1)が属性情報とされ、属性情報と述語情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。なお、以下では、鍵情報に埋め込まれるn次元ベクトルをw→=(w1,...,wn)とし、暗号文に埋め込まれるn次元ベクトルをv→=(v1,...,vn)とする。例えば、
述語情報：w→=(w1,...,wn)=(θ0,...,θn-1)
属性情報：v→=(v1,...,vn)=(x0,...,xn-1)
であるか、
述語情報：v→=(v1,...,vn)=(θ0,...,θn-1)
属性情報：w→=(w1,...,wn)=(x0,...,xn-1)
である。
【０１０２】
［内積述語暗号の基本構成］
以下では、内積述語暗号を用いて鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本構成を例示する。この構成はSetup(1k)，GenKey(MSK,w→)，Enc(PA,v→)，Dec(SKw,C2)を含む。
【０１０３】
《Setup(1k)：セットアップ》
−入力：セキュリティパラメータk
−出力：マスター鍵情報MSK，公開パラメータPK
Setup(1k)の一例では、まず、セキュリティパラメータkをnとして、n+1次元の基底ベクトルai(i=1,...,n+1)を要素とするn+1行n+1列の行列Aと、基底ベクトルai*(i=1,...,n+1)を要素とするn+1行n+1列の行列A*と、座標変換のためのn+1行n+1列の行列X，X*とが選択される。次に、式(22)に従って座標変換されたn+1次元の基底ベクトルbi(i=1,...,n+1)が算出され、式(24)に従って座標変換されたn+1次元の基底ベクトルbi*(i=1,...,n+1)が算出される。そして、基底ベクトルbi*(i=1,...,n+1)を要素とするn+1行n+1列の行列B*がマスター鍵情報MSKとして出力され、ベクトル空間V, V*、基底ベクトルbi(i=1,...,n+1)を要素とするn+1行n+1列の行列B、セキュリティパラメータk、有限体Fq、楕円曲線E、巡回群G1, G2,GT、生成元g1, g2, gT、双線形関数eなどが公開パラメータPKとして出力される。
【０１０４】
《GenKey(MSK,w→)：鍵情報生成》
−入力：マスター鍵情報MSK，ベクトルw→
−出力：ベクトルw→に対応する鍵情報D*
GenKey(MSK,w→)の一例では、まず、有限体Fqから元α∈Fqが選択される。そして、マスター鍵情報MSKである行列B*を用い、ベクトルw→に対応する鍵情報
D*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1        …(45)
が生成され、出力される。なお、巡回群G2上での離散対数問題の求解が困難である場合、鍵情報D*からwμ・bμ*やbn+1*の成分を分離抽出することは困難である。
【０１０５】
《Enc(PA,v→)：暗号化》
−入力：公開パラメータPK，ベクトルv→
−出力：暗号文C2，共通鍵K
Enc(PA,v→)の一例では、まず、共通鍵Kと有限体Fqの元である乱数υ1とが生成される。そして、行列Bなどの公開パラメータPKと、共通鍵Kを含む値に対応する有限体Fqの元υ2と、ベクトルv→と、乱数υ1とを用い、暗号文
C2=υ1・(Σμ=1nvμ・bμ)+υ2・bn+1∈G1n+1        …(46)
が生成される。そして、暗号文C2と共通鍵Kとが出力される。共通鍵Kの一例はK=gTτ・υ2∈GTである。ここで、添え字のυ2はυ2を意味する。また、前述のようにτの一例はτ=1Fである。なお、巡回群G1上での離散対数問題の求解が困難である場合、暗号文C2からvμ・bμやυ2・bn+1の成分を分離抽出することは困難である。
【０１０６】
《Dec(SKw,C2)：復号・鍵共有》
−入力：ベクトルw→に対応する鍵情報D1*，暗号文C2
−出力：共通鍵K
Dec(SKw,C2)の一例では、まず、暗号文C2と鍵情報D1*とが式(2)の双線形関数eに入力される。すると、式(3)(26)の性質から、
【０１０７】
【数１０】
2010123112.tif 000014
【０１０８】
を満たす。
【０１０９】
ここで、内積w→・v→=0であれば、式(47)は、
【０１１０】
【数１１】
2010123112.tif 000015
【０１１１】
と変形できる。この結果から共通鍵Kが生成され出力される。共通鍵Kの一例はK=gTτ・υ2∈GTである。
【０１１２】
〔CCA安全性〕
以下の仮定において
Pr[bit=bit']<(1/2)-FNK(k)          …(49)
である（ただしFNK(k)はkの関数）ことを「CCA安全である」という。この場合、[2]の後に[3]が行われるのであれば「CCA2に対して安全である」といい、[3]の後に[2]が行われるのであれば「CCA1に対して安全である」という。「CCA2」は「CCA1」よりも強力な攻撃法である。
【０１１３】
[1]攻撃者に公開パラメータPKが与えられる。
【０１１４】
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルに2つのビット列である平文M0,M1を渡し、暗号オラクルは、ランダムにbit∈{0,1}を選択し、一方の平文Mbitを暗号化し、その暗号文Cを攻撃者に渡す。
【０１１５】
[3]攻撃者は、鍵情報D*を持つ復号オラクルに暗号文C(σ)（C(σ)≠C）を渡し、復号オラクルから暗号文C(σ)の復号結果を受け取ることができる。
【０１１６】
[4]攻撃者は、bit'∈{0,1}を出力する。
【０１１７】
〔内積述語暗号の基本構成のCCA安全性〕
上述した内積述語暗号の基本構成はCCA安全性を持たない。このことを簡単な例を示して説明する。この簡単な例では、τ=1Fであり、共通鍵KがK=MAP(gTυ2)であり、平文Mに対する共通鍵Kを用いた共通鍵暗号方式の暗号文がC1=K(+)Mであるものとする。なお、MAP(gTυ2)はgTυ2∈GTのビット列への写像を表す。この場合、攻撃者は以下のような戦略（以下「想定戦略」と呼ぶ）をとることができる。
【０１１８】
[1]攻撃者に公開パラメータPKが与えられる。
【０１１９】
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルにベクトルv→と2つの平文M0, M1と渡し、暗号オラクルは、ランダムにbit∈{0,1}を選択し、一方の平文Mbitを共通鍵K=gTυ2で暗号化した暗号文
C1=K(+)Mbit        …(50)
と、共通鍵K=gTυ2の暗号文
C2=υ1・(Σμ=1nvμ・bμ)+υ2・bn+1∈G1n+1        …(51)
とを生成し、暗号文(C1, C2)を攻撃者に渡す。
【０１２０】
[3]攻撃者は、鍵情報D*を持つ復号オラクルに暗号文
(C1(+)ΔM, C2)         …(52)
を渡し、復号オラクルから暗号文C1(1)及びC1(2)の復号結果を受け取る。
ここで、bit=0だったのであれば、C1=K(+)M0であり、C1(+)ΔMの復号結果はM0(+)ΔMとなる。一方、bit=1だったのであれば、C1=K(+)M1であり、C1(+)ΔMの復号結果はM1(+)ΔMとなる。
【０１２１】
[4]攻撃者は、C1(+)ΔMの復号結果がM0(+)ΔMのときにbit'=0を出力し、M1(+)ΔMのときにbit'=1を出力する。
この場合Pr[bit=bit']=1となり、式(49)を満たさない。
【０１２２】
〔本形態の内積述語暗号〕
上述のように、内積述語暗号の基本構成はCCA安全性を持たない。一方、内積述語暗号の基本構成にCCA安全性を持たせるためにCHK 変換方式やBK 変換方式を用いるのでは、CCA安全性を向上させるためのみに用いる2次元の空間が暗号文空間に必要となり、ベクトル空間V,V*の次元数をn+3にしなければならない。本形態では、CCA安全性を向上させるためのみに用いる空間を設けることなくCCA安全性を向上させる。
【０１２３】
＜内積述語暗号の改良方式＞
以下に、本形態の内積述語暗号の改良方式の概要を示す。
【０１２４】
[暗号化処理]
暗号化処理を行う暗号化装置において以下の処理を実行する。
【０１２５】
(ENC-1)共通鍵暗号化部において、記憶部から読み出した平文Mと共通鍵Kとを共通鍵暗号関数に入力して暗号文C1を算出し、当該暗号文C1を出力する。
【０１２６】
(ENC-2)関数演算部において、共通鍵Kに対応する値と暗号文C1に対応する値とを含む値を衝突困難な関数Hに入力して関数Hの関数値を算出し、当該関数Hの関数値を出力する。
【０１２７】
(ENC-3)ベクトル演算部において、関数Hの関数値に対応する有限体Fqの元rと、共通鍵Kに対応する有限体Fqの元ρと、有限体Fqの元を要素とするn次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n、n≧1)と、n+1次元の基底ベクトルbi∈G1n+1とを用い、暗号文
C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1         …(53)
を算出し、当該暗号文C2を出力する。
【０１２８】
[復号処理]
復号処理を行う復号装置において以下の処理を実行する。
【０１２９】
(DEC-1)暗号文C1と暗号文C2∈G1n+1とを含む値が入力部に入力される。
(DEC-2)双線形関数演算部において、暗号文C2∈G1n+1と鍵情報
D1*=α・(Σμ=1nwμ・bμ*)+bn+1*         …(54)
とを双線形関数eに入力して関数値
S〜=e(C2, D1*)∈GT         …(55)
を算出し、当該関数値S〜を出力する。
【０１３０】
(DEC-3)関数演算部において、関数値S〜に対応する値と暗号文C1とを衝突困難な関数Hに入力して関数Hの関数値を算出し、当該関数Hの関数値を出力する。なお、鍵情報D1*が正しい場合、「関数値S〜に対応する値」は、暗号化処理の(ENC-2)で衝突困難な関数Hに入力された「共通鍵Kに対応する値」と等しくなる。
【０１３１】
(DEC-4)判定部において、第２暗号文C2と、関数Hの関数値に対応する有限体Fqの元r〜と、前記有限体Fqの元ρ〜と、n次元ベクトルv→の要素vμと、基底ベクトルbi∈G1n+1 (i=1,...,n+1)とに対して、
C2=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1         …(56)
を満たすか否かを判定し、その判定結果を出力する。
【０１３２】
(DEC-5)式(55)を満たすのであれば暗号文C1の復号結果を出力し、式(56)を満たさないのであれば⊥（エラー）を出力する。
【０１３３】
＜内積述語暗号の改良方式のCCA安全性＞
この改良方式に対し、上述の想定戦略が適用される場合を想定する。
【０１３４】
[1]攻撃者に公開パラメータPKが与えられる。
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルにベクトルv→と2つの平文M0, M1と渡す。暗号オラクルは、ランダムにbit∈{0,1}を選択し、一方の平文Mbitを共通鍵K=gTυ2で暗号化した暗号文
C1=K(+)Mbit        …(57)
を生成する(ENC-1)。さらに、暗号オラクルは、共通鍵Kに対応する値と暗号文C1に対応する値とを含む値を衝突困難な関数Hに入力して関数Hの関数値を算出する(ENC-2)。そして、暗号オラクルは、関数Hの関数値に対応する有限体Fqの元rと、共通鍵Kに対応する有限体Fqの元ρと、有限体Fqの元を要素とするn次元ベクトルv→=(v1,...,vn)の要素vμ(μ=1,...,n、n≧1)と、n+1次元の基底ベクトルbi∈G1n+1とを用い、共通鍵K=gTυ2の暗号文
C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1        …(58)
を生成し(ENC-3)、暗号文(C1, C2)を攻撃者に渡す。
【０１３５】
[3]攻撃者は秘密鍵Kを知らないため、共通鍵Kに対応する値と暗号文C1(+)ΔMとを含む値を衝突困難な関数Hに入力して得られる関数値に対応する有限体Fqの元r’に対応するC2’=r’・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を生成できない。そのため、攻撃者は、C1(+)ΔMと暗号文C1に対応する暗号文C2との組
(C1(+)ΔM, C2)         …(59)
を復号オラクルに渡す。
【０１３６】
式(59)の暗号文が入力された(DEC-1)復号オラクルは、式(55)の関数値S〜を生成し(DEC-2)、関数値S〜に対応する値と暗号文C1(+)ΔMとを衝突困難な関数Hに入力して関数Hの関数値を算出し、当該関数Hの関数値を出力する(DEC-3)。そして、復号オラクルは、第２暗号文C2と、関数Hの関数値に対応する有限体Fqの元r〜ΔMと、前記有限体Fqの元ρ〜と、n次元ベクトルv→の要素vμと、基底ベクトルbi∈G1n+1(i=1,...,n+1)とに対して、
C2=r〜ΔM・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1         …(60)
を満たすか否かを判定する(DEC-4)。ここでr〜ΔM≠r〜であるため、式(60)を満たさず、復号オラクルは⊥（エラー）を出力する。
【０１３７】
[4]攻撃者は、C1(+)ΔMの復号結果を取得できないため、「復号結果がM0(+)ΔMのときにbit'=0を出力し、M1(+)ΔMのときにbit'=1を出力する」ことができない。よって、この攻撃者の戦略は成功しない。
【０１３８】
〔第１実施形態〕
次に、上記改良方式の第１実施形態を説明する。
【０１３９】
＜概要＞
まず、第１実施形態の概要を示す。
【０１４０】
[暗号化処理]
暗号化処理を行う暗号化装置において以下の処理を実行する。
【０１４１】
(ENC-11)共通鍵暗号化部において、記憶部から読み出した平文Mと共通鍵Kとを共通鍵暗号関数に入力して暗号文C1を算出し、当該暗号文C1を出力する。
【０１４２】
(ENC-21)関数演算部において、共通鍵Kと暗号文C1とを衝突困難な関数Hに入力して有限体Fqの元r及びρを算出し、当該元r及びρを出力する。なお、(ENC-21)では「共通鍵K」が前述した(ENC-2)の「共通鍵Kに対応する値」に相当する。
【０１４３】
(ENC-31)群演算部において、元ρを用いて関数値S=gTτ・ρ∈GTを算出し、当該関数値Sを出力する。
【０１４４】
(ENC-32)排他的論理和演算部において、関数値Sを単射関数Rに入力して得られるバイナリ系列である関数値R(S)と共通鍵Kとの排他的論理和値である暗号文C3を算出し、当該暗号文C3を出力する。
【０１４５】
(ENC-33)ベクトル演算部において、有限体Fqの元を要素とするn次元ベクトルv→の各要素vμ(μ=1,...,n)と元r及びρとを用い、C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出し、当該暗号文C2を出力する。
【０１４６】
[復号処理]
復号処理を行う復号装置において以下の処理を実行する。
【０１４７】
(DEC-11)暗号文C1と暗号文C2と暗号文C3とを含む値が入力部に入力される。
【０１４８】
(DEC-21)双線形関数演算部において、暗号文C2∈G1n+1と鍵情報D1*=α・(Σμ=1nwμ・bμ*)+bn+1*とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出し、当該関数値S〜を出力する。なお、内積w→・v→=0である場合、式(3)(26)の性質から、
【０１４９】
【数１２】
2010123112.tif 000016
【０１５０】
を満たす。
【０１５１】
(DEC-31)排他的論理和演算部において、関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と暗号文C3との排他的論理和値K〜を算出し、当該排他的論理和値K〜を出力する。なお、式(61)を満たす場合、
K〜=R(S〜)(+)C3
=R(S)(+)C3 
=R(S)(+)R(S)(+)K 
=K                                    …(62)
を満たす。
【０１５２】
(DEC-32)関数演算部において、排他的論理和値K〜と暗号文C1とを衝突困難な関数Hに入力して有限体Fqの元r〜及びρ〜を算出し、当該元r〜及びρ〜を出力する。なお、(DEC-31)の「元r〜及びρ〜」が前述の(DEC-3)の「元r〜を含む値」に相当する。
【０１５３】
(DEC-41)ベクトル演算部において、n次元ベクトルv→の要素vμ(μ=1,...,n)と元r〜及びρ〜とを用い、関数値C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を算出し、当該関数値C2〜を出力する。
【０１５４】
(DEC-42)比較部において、関数値C2〜と暗号文C2とが等しいか否かを判定し、その判定結果を出力する。この判定は、(DEC-4)の判定に相当する。
【０１５５】
(DEC-51)比較部から出力された判定結果が、関数値C2〜と暗号文C2とが等しい旨の判定結果である場合に、共通鍵復号部において、排他的論理和値K〜を共通鍵とし、当該排他的論理和値K〜と暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力する。一方、比較部から出力された判定結果が、関数値C2〜と暗号文C2とが等しくない旨の判定結果である場合には、⊥（エラー）が出力される。
【０１５６】
＜第１実施形態のCCA安全性＞
第１実施形態の方式に対し、前述の想定戦略が適用される場合を想定する。なお、この例では、τ=1Fであり、平文Mに対する共通鍵Kを用いた共通鍵暗号方式の暗号文がC1=K(+)Mであるものとする。
【０１５７】
[1]攻撃者に公開パラメータPKが与えられる。
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルにベクトルv→と2つの平文M0, M1と渡す。暗号オラクルは、ランダムにbit∈{0,1}を選択し、一方の平文Mbitを共通鍵K=gTυ2で暗号化した暗号文
C1=K(+)Mbit        …(63)
を生成する(ENC-11)。さらに、暗号オラクルは、共通鍵Kと暗号文C1とを衝突困難な関数Hに入力して有限体Fqの元r及びρを算出し(ENC-21)、関数値S=gTτ・ρ∈GTを算出し(ENC-31)、関数値R(S)と共通鍵Kとの排他的論理和値である暗号文C3を算出し(ENC-32)、C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出し(ENC-33)、暗号文(C1, C2, C3)を攻撃者に渡す。
【０１５８】
[3]攻撃者は秘密鍵Kを知らないため、共通鍵Kと暗号文C1(+)ΔMとを衝突困難な関数Hに入力して得られる有限体Fqの元r'及びρ'に対応するC2’=r'・(Σμ=1nvμ・bμ)+ρ'・bn+1∈G1n+1を生成できない。そのため、攻撃者は、C1(+)ΔMと暗号文C1に対応する暗号文C2と暗号文C3との組
(C1(+)ΔM, C2, C3)         …(64)
を復号オラクルに渡す。
【０１５９】
式(64)の暗号文が入力され(DEC-11)た復号オラクルは、関数値S〜=e(C2, D1*)∈GTを生成し(DEC-21)、関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と暗号文C3との排他的論理和値K〜を算出し、排他的論理和値K〜と暗号文C1(+)ΔMとを衝突困難な関数Hに入力して有限体Fqの元r〜ΔM及びρ〜ΔMを算出する(DEC-32)。そして、復号オラクルは、v→の要素vμと、元r〜ΔMと、基底ベクトルbi∈G1n+1(i=1,...,n+1)と、元ρ〜ΔMとに対して、
C2〜=r〜ΔM・(Σμ=1nvμ・bμ)+ρ〜ΔM・bn+1∈G1n+1         …(65)
を算出し(DEC-41)、関数値C2〜と暗号文C2とが等しいか否かを判定する。ここでr〜ΔM≠r〜であり、ρ〜ΔM≠ρ〜であるため、式(65)を満たさず、復号オラクルは⊥（エラー）を出力する。
【０１６０】
[4]攻撃者は、C1(+)ΔMの復号結果を取得できないため、「復号結果がM0(+)ΔMのときにbit'=0を出力し、M1(+)ΔMのときにbit'=1を出力する」ことができない。よって、この攻撃者の戦略は成功しない。
【０１６１】
＜詳細＞
次に、第１実施形態の詳細を説明する。なお、以下ではτ=1Fの場合を例にとって説明する。しかし、これは本発明を限定するものではなく、0F及び1F以外の有限体Fqの元をτとしてもよい。
【０１６２】
[全体構成]
図１は、第１実施形態の暗号システム１の構成を説明するための図である。
図１に例示するように、本形態の暗号システム１は、ネットワーク１４０を通じて通信可能に接続された暗号化装置１１０と復号装置１２０と鍵生成装置１３０とを有する。
【０１６３】
[暗号化装置]
図２は、図１の暗号化装置１１０の構成を説明するための図である。なお、図２における矢印はデータの流れを示すが、制御部１１１や一時記憶部１１３ｂに入出力されるデータの記述は省略してある。
図２に例示するように、本形態の暗号化装置１１０は、制御部１１１と、乱数生成部１１２ａと、共通鍵暗号化部１１２ｂと、関数演算部１１２ｃと、群演算部１１２ｄと、排他的論理和演算部１１２ｅと、ベクトル演算部１１２ｆと、記憶部１１３ａと、一時記憶部１１３ｂと、送信部１１４とを有する。
【０１６４】
暗号化装置１１０は、例えば、CPU（Central Processing Unit）、RAM（Random Access Memory）、ROM（Read-Only Memory）等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。すなわち、制御部１１１、乱数生成部１１２ａ、共通鍵暗号化部１１２ｂ、関数演算部１１２ｃ、群演算部１１２ｄ、排他的論理和演算部１１２ｅ及びベクトル演算部１１２ｆは、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、乱数生成部１１２ａを公知の乱数生成用IC(integrated Circuit)で構成するなど、処理部の少なくとも一部を特別な集積回路で構成してもよい。また、記憶部１１３ａ及び一時記憶部１１３ｂは、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。また、送信部１１４は、例えば、モデム、LAN（Local Area Network）カード等の通信装置である。
【０１６５】
また、暗号化装置１１０は、制御部１１１の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１１３ｂ又は記憶部１１３ａに格納される。一時記憶部１１３ｂ又は記憶部１１３ａに格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【０１６６】
[復号装置]
図３は、図１の復号装置１２０の構成を説明するための図である。なお、図３における矢印はデータの流れを示すが、制御部１２１や一時記憶部１２３ｂに入出力されるデータの記述は省略してある。
【０１６７】
図３に例示するように、本形態の復号装置１２０は、制御部１２１と、双線形関数演算部１２２ａと、排他的論理和演算部１２２ｂと、関数演算部１２２ｃと、判定部１２２ｄと、共通鍵復号部１２２ｅと、記憶部１２３ａと、一時記憶部１２３ｂと、送信部１２４と、受信部１２５（「入力部」に相当）とを有する。また、判定部１２２ｄは、ベクトル演算部１２２ｄａと比較部１２２ｄｂとを有する。
【０１６８】
復号装置１２０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。すなわち、制御部１２１、双線形関数演算部１２２ａ、排他的論理和演算部１２２ｂ、関数演算部１２２ｃ、判定部１２２ｄ及び共通鍵復号部１２２ｅは、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、双線形関数演算部１２２ａを公知のペアリング演算用ICで構成するなど、処理部の少なくとも一部を特別な集積回路で構成してもよい。また、記憶部１２３ａ及び一時記憶部１２３ｂは、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。また、送信部１２４及び受信部１２５は、例えば、モデム、LANカード等の通信装置である。
【０１６９】
また、復号装置１２０は、制御部１２１の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１２３ｂ又は記憶部１２３ａに格納される。一時記憶部１２３ｂ又は記憶部１２３ａに格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【０１７０】
[鍵生成装置]
図４は、図１の鍵生成装置１３０の構成を説明するための図である。なお、図４における矢印はデータの流れを示すが、制御部１３１や一時記憶部１３３ｂに入出力されるデータの記述は省略してある。
図４に例示するように、本形態の鍵生成装置１３０は、制御部１３１と、乱数生成部１３２ａと、ベクトル演算部１３２ｂと、記憶部１３３ａと、一時記憶部１３３ｂと、受信部１３４と、送信部１３５とを有する。
【０１７１】
鍵生成装置１３０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。すなわち、制御部１３１、乱数生成部１３２ａ及びベクトル演算部１３２ｂは、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、処理部の少なくとも一部を特別な集積回路で構成してもよい。また、記憶部１３３ａ及び一時記憶部１３３ｂは、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。また、送信部１３４及び受信部１３５は、例えば、モデム、LANカード等の通信装置である。
【０１７２】
また、鍵生成装置１３０は、制御部１３１の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１３３ｂ又は記憶部１３３ａに格納される。一時記憶部１３３ｂ又は記憶部１３３ａに格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【０１７３】
[事前設定]
次に、本形態の各処理を実行するための事前設定を説明する。
【０１７４】
ベクトル空間V, V*、基底ベクトルbi(i=1,...,n+1)を要素とするn+1行n+1列の行列B、セキュリティパラメータk、有限体Fq、楕円曲線E、巡回群G1, G2, GT、生成元g1, g2, gT、双線形関数e、１以上の整数nなどからなる公開パラメータPKが、暗号化装置１１０、復号装置１２０及び鍵生成装置１３０に設定される。また、式(33)に示した衝突困難な関数H1及び式(35)に示した単射関数Rが、暗号化装置１１０及び復号装置１２０に設定される。
【０１７５】
また、マスター鍵情報MSKであるn+1行n+1列の行列B*が鍵生成装置１３０の記憶部１３３ａに安全に格納される。行列B*は秘密情報であり、公開されない。
【０１７６】
また、式(31)に示した有限体Fqの元を要素とするn次元ベクトルv→=(v1,...,vn)が暗号化装置１１０の記憶部１１３ａに格納され、n次元ベクトルv→=(v1,...,vn)及び式(30)に示した有限体Fqの元を要素とするn次元ベクトルw→=(w1,...,wn)が、復号装置１２０の記憶部１２３ａに格納される。なお、これらのベクトルは
w→・v→=0         …(66)
を満たすものとする。なお、述語情報：w→=(w1,...,wn)かつ属性情報：v→=(v1,...,vn)であってもよいし、述語情報：v→=(v1,...,vn)かつ属性情報：w→=(w1,...,wn)であってもよい。
また、暗号化装置１１０の記憶部１１３ａには、暗号化を行う平文M∈{0,1}*が格納される。
【０１７７】
[暗号化処理]
図５は、第１実施形態の暗号化処理を説明するための図である。以下、本形態の暗号化処理を説明する。
【０１７８】
まず、暗号化装置１１０（図２）の乱数生成部１１２ａが、kビットのバイナリ系列の乱数を生成し、それを共通鍵
K∈{0,1}k         …(67)
として記憶部１１３ａに格納する（ステップＳ１０１）。
【０１７９】
次に、記憶部から読み出された平文Mと共通鍵Kとが共通鍵暗号化部１１２ｂに入力される。共通鍵暗号化部１１２ｂは、これらを共通鍵暗号関数Encに入力して暗号文
C1=Enck(M)∈{0,1}k         …(68)
を算出し、当該暗号文C1を出力する（ステップＳ１０２）。
【０１８０】
次に、関数演算部１１２ｃに暗号文C1と共通鍵Kとが入力される。数演算部１１２ｃは、共通鍵Kと暗号文C1とを衝突困難な関数H1に入力して
(r, ρ)=H1(K, C1)∈Fq×Fq         …(69)
を算出し、有限体Fqの元r及びρを出力する（ステップＳ１０３）。
【０１８１】
次に、群演算部１１２ｄに有限体Fqの元ρが入力される。群演算部１１２ｄは、この元ρを用いて関数値
S=gTρ∈GT         …(70)
を算出し、当該関数値Sを出力する（ステップＳ１０４）。
【０１８２】
次に、排他的論理和演算部１１２ｅに関数値Sと共通鍵Kとが入力される。排他的論理和演算部１１２ｅは、関数値Sを単射関数Rに入力して得られるkビットのバイナリ系列である関数値
R(S)∈{0,1}k         …(71)
と共通鍵Kとの排他的論理和値である暗号文
C3=R(S)(+)K∈{0,1}k         …(72)
を算出し、当該暗号文C3を出力する（ステップＳ１０５）。
【０１８３】
また、ベクトル演算部１１２ｆに有限体Fqの元r及びρとn次元ベクトルv→=(v1,...,vn)とが入力される。ベクトル演算部１１２ｆは、n次元ベクトルv→の各要素vμ(μ=1,...,n)と元r及びρとを用い、暗号文
C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1         …(73)
を算出し、当該暗号文C2を出力する（ステップＳ１０６）。
【０１８４】
その後、送信部１１４に暗号文C1と暗号文C2と暗号文C3とが入力される。送信部１１４は、これらを含む値をネットワーク１４０経由で復号装置１２０に送信する（ステップＳ１０７）。
【０１８５】
[鍵情報の生成処理]
鍵情報の生成処理は、特に、復号装置１２０の記憶部１２３ａに鍵情報D1*が格納されていない場合に実行される。復号装置１２０の記憶部１２３ａに鍵情報D1*が格納されているときには、この処理を省略してもよい。
【０１８６】
図６は、第１実施形態の鍵情報の生成処理を説明するための図である。以下、本形態の鍵情報の生成処理を説明する。
【０１８７】
まず、復号装置１２０（図３）に格納されたn次元ベクトルw→=(w1,...,wn)が読み出され、送信部１２４に入力される。送信部１２４は、n次元ベクトルw→=(w1,...,wn)をネットワーク１４０経由で鍵生成装置１３０に送信する（ステップＳ１１１）。
【０１８８】
送信されたn次元ベクトルw→=(w1,...,wn)は、鍵生成装置１３０（図４）の受信部１３４で受信される（ステップＳ１１２）。これを契機に、鍵生成装置１３０の乱数生成部１３２ａは、有限体Fqの元の乱数
α∈Fq         …(74)
を生成し、当該乱数αを出力する（ステップＳ１１３）。
【０１８９】
次に、ベクトル演算部１３２ｂにn次元ベクトルw→=(w1,...,wn)と乱数αと行列B*とが入力される。ベクトル演算部１３２ｂは、これらを用いて鍵情報
D1*=α・(Σμ=1nwμ・bμ*)+bn+1*∈G1n+1         …(75)
を生成し、当該鍵情報D1*を出力する（ステップＳ１１４）。
【０１９０】
次に、鍵情報D1*が送信部１３５に入力される。送信部１３５は、ネットワーク１４０経由で鍵情報D1*を復号装置１２０に送信する（ステップＳ１１５）。
送信された鍵情報D1*は、復号装置１２０（図３）の受信部１２５で受信され、記憶部１２３ａに格納される（ステップＳ１１６）。
【０１９１】
[復号処理]
図７は、第１実施形態の復号処理を説明するための図である。以下、本形態の復号処理を説明する。
【０１９２】
まず、復号装置１２０（図３）の受信部１２５が、暗号文C1と暗号文C2∈G1n+1と暗号文C3とを含む値を受信する（ステップＳ１２１）。
【０１９３】
次に、双線形関数演算部１２２ａに暗号文C2∈G1n+1と鍵情報D1*とが入力される。双線形関数演算部１２２ａは、暗号文C2∈G1n+1と鍵情報D1*とを双線形関数eに入力して関数値
S〜=e(C2, D1*)∈GT         …(76)
を算出し、当該関数値S〜を出力する（ステップＳ１２２）。
【０１９４】
次に、排他的論理和演算部１２２ｂに関数値S〜と暗号文C3とが入力される。排他的論理和演算部１２２ｂは、関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と暗号文C3との排他的論理和値
K〜=R(S〜)(+)C3        …(77)
を算出し、当該排他的論理和値K〜を出力する（ステップＳ１２３）。
【０１９５】
次に、関数演算部１２２ｃに排他的論理和値K〜と暗号文C1とが入力される。関数演算部１２２ｃは、排他的論理和値K〜と暗号文C1とを衝突困難な関数H1に入力して
(r〜, ρ〜)=H1(K〜, C1)∈Fq×Fq         …(78)
を算出し、当該元r〜及びρ〜を出力する（ステップＳ１２４）。
【０１９６】
次に、判定部１２２ｄのベクトル演算部１２２ｄａにn次元ベクトルv→の要素vμ(μ=1,...,n)と元r〜及びρ〜とが入力される。ベクトル演算部１２２ｄａは、これらを用いて関数値
C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1         …(79)
を算出し、当該関数値C2〜を出力する（ステップＳ１２５）。
【０１９７】
次に、関数値C2〜と暗号文C2とが判定部１２２ｄの比較部１２２ｄｂに入力される。比較部１２２ｄｂは、関数値C2〜と暗号文C2とが等しいか否かを判定し、その判定結果を出力する（ステップＳ１２６）。
【０１９８】
ここで、比較部１２２ｄｂから出力された判定結果が、関数値C2〜と暗号文C2とが等しい旨の判定結果である場合、共通鍵復号部１２２ｅに排他的論理和値K〜と暗号文C1とが入力され、共通鍵復号部１２２ｅは、当該排他的論理和値K〜と暗号文C1とを共通鍵復号関数に入力して復号値
M〜=DecK〜(C1)         …(80)
を算出し、当該復号値M〜を出力する（ステップＳ１２７）。一方、比較部１２２ｄｂから出力された判定結果が、関数値C2〜と暗号文C2とが異なる旨の判定結果である場合、共通鍵復号部１２２ｅは、エラー出力（⊥）を行う（ステップＳ１２８）。
【０１９９】
〔第２実施形態〕
次に、上記改良方式の第２実施形態を説明する。
＜概要＞
まず、第２実施形態の概要を示す。
【０２００】
[暗号化処理]
暗号化処理を行う暗号化装置において以下の処理を実行する。
【０２０１】
(ENC-111)選択部において、有限体Fqの元ρを選択し、当該元ρを出力する。
【０２０２】
(ENC-112)群演算部において、元ρを用いて関数値S=gTτ・ρ∈GTを算出し、当該関数値Sを出力する。
【０２０３】
(ENC-113)共通鍵暗号化部において、関数値Sを単射関数Rに入力して得られる関数値R(S)を共通鍵Kとし、当該共通鍵Kと平文Mとを共通鍵暗号関数に入力して暗号文C1を算出し、当該暗号文C1を出力する。
【０２０４】
(ENC-211)関数演算部において、関数値Sと暗号文C1とを衝突困難な関数Hに入力して有限体Fqの元rを算出し、当該元rを出力する。
【０２０５】
(ENC-311)ベクトル演算部において、有限体Fqの元を要素とするn次元ベクトルv→の各要素vμ(μ=1,...,n)と元rと元ρとを用い、暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を算出し、当該暗号文C2を出力する。
【０２０６】
[復号処理]
復号処理を行う復号装置において以下の処理を実行する。
【０２０７】
(DEC-101)暗号文C1と暗号文C2∈G1n+1とを含む値が入力部に入力される。
【０２０８】
(DEC-201)双線形関数演算部において、暗号文C2∈G1n+1と鍵情報D1*=α・(Σμ=1nwμ・bμ*)+bn+1*とを双線形関数eに入力して関数値S〜=e(C2, D1*)∈GTを算出し、当該関数値S〜を出力する。なお、内積w→・v→=0である場合、式(3)(26)の性質から、S〜=Sを満たす。
【０２０９】
(DEC-301)関数演算部において、関数値S〜と暗号文C1とを衝突困難な関数Hに入力して有限体Fqの元r〜を算出し、当該元r〜を出力する。なお、S〜=Sを満たし、なおかつ、暗号文C1が正当に生成されたものである場合、r〜=rを満たす。
【０２１０】
(DEC-401)ベクトル演算部において、暗号文C2と元r〜とn次元ベクトルv→の各要素vμ(μ=1,...,n)とを用い、関数値λ=C2-r〜・(Σμ=1nvμ・bμ)∈G1n+1を算出し、当該関数値λを出力する。なお、r〜=rを満たす場合、λ=ρ・bn+1∈G1n+1を満たす。
【０２１１】
(DEC-402)双線形関数演算部において、関数値λと補助鍵情報D2*=Σμ=1nβμ・bμ*とを双線形関数eに入力して関数値e(λ,D2*)を算出し、当該関数値e(λ,D2*)を出力する。λ=ρ・bn+1∈G1n+1を満たす場合、式(3)の性質からe(λ,D2*)=1∈GTを満たす。
【０２１２】
(DEC-403)比較部において、関数値e(λ,D2*)が e(λ,D2*)=1∈GTを満たすか否かを判定し、その判定結果を出力する。なお、本形態では、関数値e(λ,D2*)が e(λ,D2*)=1∈GTを満たすか否かによって、式(56)を満たすか否かを判定している。すなわち、この判定は、(DEC-4)の判定に相当する。
【０２１３】
(DEC-501)比較部から出力された判定結果が、e(λ,D2*)=1∈GTを満たす旨の判定結果である場合に、共通鍵復号部において、関数値S〜を単射関数Rに入力して得られる関数値R(S〜)を共通鍵K〜とし、当該共通鍵K〜と第１暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力する。一方、比較部から出力された判定結果が、e(λ,D2*)=1∈GTを満たさない旨の判定結果である場合には、⊥（エラー）が出力される。
【０２１４】
＜第２実施形態のCCA安全性＞
第２実施形態の方式に対し、前述の想定戦略が適用される場合を想定する。なお、この例では、τ=1Fであり、平文Mに対する共通鍵Kを用いた共通鍵暗号方式の暗号文がC1=K(+)Mであるものとする。
【０２１５】
[1]攻撃者に公開パラメータPKが与えられる。
【０２１６】
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルにベクトルv→と2つの平文M0, M1と渡す。暗号オラクルは、有限体Fqの元ρを選択し(ENC-111)、関数値S=gTτ・ρ∈GTを算出し(ENC-112)、関数値R(S)を共通鍵Kとし(ENC-113)、暗号文
C1=K(+)Mbit         …(81)
を生成する(ENC-113)。さらに、暗号オラクルは、関数値Sと暗号文C1とを衝突困難な関数Hに入力して有限体Fqの元rを算出する(ENC-211)。そして、暗号オラクルは、有限体Fqの元を要素とするn次元ベクトルv→の各要素vμ(μ=1,...,n)と元rと元ρとを用い、暗号文C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を生成し(ENC-311)、暗号文(C1, C2)を攻撃者に渡す。
【０２１７】
[3]攻撃者は秘密鍵K=R(S)や関数値S（「共通鍵Kに対応する値」）を知らないため、関数値Sと暗号文C1(+)ΔMとを衝突困難な関数Hに入力して得られる有限体Fqの元r’に対応するC2’=r’・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1を生成できない。そのため、攻撃者は、C1(+)ΔMと暗号文C1に対応する暗号文C2との組
(C1(+)ΔM, C2)         …(82)
を復号オラクルに渡す。
【０２１８】
式(82)の暗号文が入力され(DEC-101)た復号オラクルは、関数値S〜=e(C2, D1*)∈GTを算出し(DEC-201)、関数値S〜と暗号文C1(+)ΔMとを衝突困難な関数Hに入力して有限体Fqの元r〜ΔMを算出し(DEC-301)、関数値λΔM=C2-r〜ΔM・(Σμ=1nvμ・bμ)∈G1n+1を算出する(DEC-401)。なお、r〜ΔM ≠rであるため、λΔM=(r-r〜ΔM)・(Σμ=1nvμ・bμ)+ρ・bn+1≠ρ・bn+1となる。復号オラクルは、関数値e(λΔM,D2*)を算出し(DEC-402)、関数値e(λ,D2*)が e(λ,D2*)=1∈GTを満たすか否かを判定する(DEC-403)。ここで、λΔM≠ρ・bn+1であるため、e(λ,D2*)=1∈GTを満たさない(DEC-403)。よって復号オラクルは、⊥（エラー）を出力する。
【０２１９】
[4]攻撃者は、C1(+)ΔMの復号結果を取得できないため、「復号結果がM0(+)ΔMのときにbit'=0を出力し、M1(+)ΔMのときにbit'=1を出力する」ことができない。よって、この攻撃者の戦略は成功しない。
【０２２０】
＜詳細＞
次に、第２実施形態の詳細を説明する。なお、以下ではτ=1Fの場合を例にとって説明する。しかし、これは本発明を限定するものではなく、0F及び1F以外の有限体Fqの元をτとしてもよい。また、第２実施形態において、第１実施形態と同じ構成部分については第１実施形態と同じ符号を用いて説明を行う。
【０２２１】
[全体構成]
図８は、第２実施形態の暗号システムの構成を説明するための図である。
図８に例示するように、本形態の暗号システム２は、ネットワーク１４０を通じて通信可能に接続された暗号化装置２１０と復号装置２２０と鍵生成装置２３０とを有する。
【０２２２】
[暗号化装置]
図９は、図８の暗号化装置２１０の構成を説明するための図である。なお、図９における矢印はデータの流れを示すが、制御部１１１や一時記憶部１１３ｂに入出力されるデータの記述は省略してある。
【０２２３】
図９に例示するように、本形態の暗号化装置２１０は、制御部１１１と、選択部２１２ａと、群演算部１１２ｄと、関数演算部２１２ｃと、共通鍵生成部２１２ｅと、共通鍵暗号化部１１２ｂと、ベクトル演算部１１２ｆと、記憶部１１３ａと、一時記憶部１１３ｂと、送信部１１４とを有する。
【０２２４】
暗号化装置２１０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。すなわち、制御部１１１、乱数生成部２１２ａ（「選択部」に相当）、群演算部１１２ｄ、関数演算部２１２ｃ、共通鍵生成部２１２ｅ、共通鍵暗号化部１１２ｂ及びベクトル演算部１１２ｆは、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、乱数生成部２１２ａを公知の乱数生成用ICで構成するなど、処理部の少なくとも一部を特別な集積回路で構成してもよい。
【０２２５】
また、暗号化装置２１０は、制御部１１１の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１１３ｂ又は記憶部１１３ａに格納される。一時記憶部１１３ｂ又は記憶部１１３ａに格納されたデータは、必要に応じて各処理部に入力されてその処理に利用される。
【０２２６】
[復号装置]
図１０は、図８の復号装置２２０の構成を説明するための図である。なお、図１０における矢印はデータの流れを示すが、制御部１２１や一時記憶部１２３ｂに入出力されるデータの記述は省略してある。
【０２２７】
図１０に例示するように、本形態の復号装置２２０は、制御部１２１と、双線形関数演算部１２２ａと、関数演算部２２２ｂ，２２２ｃと、判定部２２２ｄと、共通鍵復号部１２２ｅと、記憶部１２３ａと、一時記憶部１２３ｂと、送信部１２４と、受信部１２５（「入力部」に相当）とを有する。また、判定部２２２ｄは、ベクトル演算部２２２ｄａと、双線形関数演算部２２２ｄｂと、比較部２２２ｄｃとを有する。
【０２２８】
復号装置２２０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。すなわち、制御部１２１、双線形関数演算部１２２ａ、関数演算部２２２ｂ，２２２ｃ、判定部２２２ｄ及び共通鍵復号部１２２ｅは、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、処理部の少なくとも一部を特別な集積回路で構成してもよい。
【０２２９】
また、復号装置２２０は、制御部１２１の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１２３ｂ又は記憶部１２３ａに格納される。一時記憶部１２３ｂ又は記憶部１２３ａに格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【０２３０】
[鍵生成装置]
図１１は、図８の鍵生成装置２３０の構成を説明するための図である。なお、図１１における矢印はデータの流れを示すが、制御部１３１や一時記憶部１３３ｂに入出力されるデータの記述は省略してある。
【０２３１】
図１１に例示するように、本形態の鍵生成装置２３０は、制御部１３１と、乱数生成部２３２ａと、ベクトル演算部１３２ｂ，２３２ｃと、記憶部１３３ａと、一時記憶部１３３ｂと、受信部１３４と、送信部１３５とを有する。
【０２３２】
鍵生成装置２３０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。すなわち、制御部１３１、乱数生成部２３２ａ及びベクトル演算部１３２ｂ，２３２ｃは、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、処理部の少なくとも一部を特別な集積回路で構成してもよい。
【０２３３】
また、鍵生成装置２３０は、制御部１３１の制御のもと各処理を実行する。また、以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１３３ｂ又は記憶部１３３ａに格納される。一時記憶部１３３ｂ又は記憶部１３３ａに格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【０２３４】
[事前設定]
第２実施形態の事前設定では、第１実施形態と同様な公開パラメータPKが、暗号化装置２１０、復号装置２２０及び鍵生成装置２３０に設定される。また、式(34)に示した衝突困難な関数H2が暗号化装置２１０及び復号装置２２０に設定される。
また、マスター鍵情報MSKであるn+1行n+1列の行列B*が鍵生成装置２３０の記憶部１３３ａに安全に格納される。行列B*は秘密情報であり、公開されない。
【０２３５】
また、式(31)に示した有限体Fqの元を要素とするn次元ベクトルv→=(v1,...,vn)が暗号化装置１１０の記憶部１１３ａに格納され、n次元ベクトルv→=(v1,...,vn)及び式(30)に示した有限体Fqの元を要素とするn次元ベクトルw→=(w1,...,wn)が、復号装置１２０の記憶部１２３ａに格納される。なお、これらのベクトルは式(66)を満たすものとする。なお、述語情報：w→=(w1,...,wn)かつ属性情報：v→=(v1,...,vn)であってもよいし、述語情報：v→=(v1,...,vn)かつ属性情報：w→=(w1,...,wn)であってもよい。
また、暗号化装置２１０の記憶部１１３ａには、暗号化を行う平文M∈{0,1}*が格納される。
【０２３６】
[暗号化処理]
図１２は、第２実施形態の暗号化処理を説明するための図である。以下、本形態の暗号化処理を説明する。
【０２３７】
まず、暗号化装置２１０（図９）の乱数生成部２１２ａが、有限体Fqの元
ρ∈Fq         …(83)
をランダムに選択し、当該元ρを出力する（ステップＳ２０１）。
【０２３８】
次に、群演算部１１２ｄに元ρが入力される。群演算部１１２ｄは、元ρを用いて関数値
S=gTρ∈GT        …(84)
を算出し、当該関数値Sを出力する（ステップＳ２０２）。
【０２３９】
次に、共通鍵生成部２１２ｅに関数値Sが入力される。共通鍵生成部２１２ｅは、関数値Sを単射関数Rに入力して共通鍵
K=R(S)∈{0,1}k        …(85)
を算出し、当該共通鍵Kを記憶部１１３ａに格納する（ステップＳ２０３）。
【０２４０】
次に、共通鍵暗号化部１１２ｂに共通鍵Kと平文Mとが入力される。共通鍵暗号化部１１２ｂは、共通鍵Kと平文Mとを共通鍵暗号関数Encに入力して暗号文
C1=Enck(M)∈{0,1}k         …(86)
を算出し、当該暗号文C1を出力する（ステップＳ２０４）。
【０２４１】
次に、関数演算部２１２ｃに暗号文C1と関数値Sとが入力される。関数演算部２１２ｃは、関数値Sと第１暗号文C1とを衝突困難な関数H2に入力して有限体Fqの元
r=H2(S,C1)∈Fq         …(87)
を算出し、当該元rを出力する（ステップＳ２０５）。
【０２４２】
次に、ベクトル演算部１１２ｆにn次元ベクトルv→の各要素vμ(μ=1,...,n)と元rと元ρとが入力される。ベクトル演算部１１２ｆは、n次元ベクトルv→の各要素vμ(μ=1,...,n)と元rと元ρとを用い、暗号文
C2=r・(Σμ=1nvμ・bμ)+ρ・bn+1∈G1n+1        …(88)
を算出し、当該暗号文C2を出力する（ステップＳ２０６）。
【０２４３】
次に、暗号文C1と暗号文C2とが送信部１１４に入力される。送信部１１４は、これらを含む値をネットワーク１４０経由で復号装置１２０に送信する（ステップＳ２０７）。
【０２４４】
[鍵情報の生成処理]
鍵情報の生成処理は、特に、復号装置２２０の記憶部１２３ａに鍵情報D1*及び補助鍵情報D2*が格納されていない場合に実行される。復号装置２２０の記憶部１２３ａに鍵情報D1*及び補助鍵情報D2*が格納されているときには、この処理を省略してもよい。
図１３は、第２実施形態の鍵情報の生成処理を説明するための図である。以下、本形態の鍵情報の生成処理を説明する。
【０２４５】
まず、復号装置２２０（図１０）に格納されたn次元ベクトルw→=(w1,...,wn)が読み出され、送信部１２４に入力される。送信部１２４は、n次元ベクトルw→=(w1,...,wn)をネットワーク１４０経由で鍵生成装置２３０に送信する（ステップＳ１１１）。
【０２４６】
送信されたn次元ベクトルw→=(w1,...,wn)は、鍵生成装置２３０（図１１）の受信部１３４で受信される（ステップＳ１１２）。これを契機に、鍵生成装置２３０の乱数生成部２３２ａとベクトル演算部１３２ｂとが、第１実施形態のステップＳ１１３及びＳ１１４の処理を行って式(75)に示す鍵情報D1*を生成し、当該鍵情報D1*を出力する。
【０２４７】
また、乱数生成部２３２ａが、有限体Fqの元の乱数
βμ(μ=1,...,n)∈Fq        …(89)
を生成し、当該乱数βμを出力する（ステップＳ２１５）。
【０２４８】
次に、ベクトル演算部２３２ｃに乱数βμと行列B*とが入力される。ベクトル演算部２３２ｂは、これらを用いて補助鍵情報
D2*=Σμ=1nβμ・bμ*∈G2n        …(90)
を生成し、当該補助鍵情報D2*を出力する（ステップＳ２１６）。
【０２４９】
次に、鍵情報D1*と補助鍵情報D2*とが送信部１３５に入力される。送信部１３５は、ネットワーク１４０経由で鍵情報D1*と補助鍵情報D2*を復号装置２２０に送信する（ステップＳ２１７）。
送信された鍵情報D1*と補助鍵情報D2*は、復号装置２２０（図１０）の受信部１２５で受信され、記憶部１２３ａに格納される（ステップＳ２１８）。
【０２５０】
[復号処理]
図１４は、第２実施形態の復号処理を説明するための図である。以下、本形態の復号処理を説明する。
まず、復号装置２２０（図１０）の受信部１２５が、暗号文C1と暗号文C2∈G1n+1とを含む値を受信する（ステップＳ２２１）。
【０２５１】
次に、双線形関数演算部１２２ａに暗号文C2∈G1n+1と鍵情報D1*とが入力される。双線形関数演算部１２２ａは、暗号文C2∈G1n+1と鍵情報D1*とを双線形関数eに入力して関数値
S〜=e(C2, D1*)∈GT         …(91)
を算出し、当該関数値S〜を出力する（ステップＳ２２２）。
【０２５２】
次に、関数演算部２２２ｃに関数値S〜と暗号文C1とが入力される。関数演算部２２２ｃは、関数値S〜と第１暗号文C1とを衝突困難な関数H2に入力して有限体Fqの元
r〜=H2(S〜,C1)∈Fq         …(92)
を算出し、当該元r〜を出力する（ステップＳ２２３）。
【０２５３】
次に、判定部２２２ｄのベクトル演算部２２２ｄａに暗号文C2と元r〜とn次元ベクトルv→の各要素vμ(μ=1,...,n)とが入力される。ベクトル演算部２２２ｄａは、暗号文C2と元r〜とn次元ベクトルv→の各要素vμ(μ=1,...,n)とを用い、関数値
λ=C2-r〜・(Σμ=1nvμ・bμ)∈G1n+1         …(93)
を算出し、当該関数値λを出力する（ステップＳ２２４）。
【０２５４】
次に、判定部２２２ｄの双線形関数演算部２２２ｄｂに関数値λと補助鍵情報D2*とが入力される。双線形関数演算部２２２ｄｂは、関数値λと補助鍵情報D2*とを双線形関数eに入力して関数値
e(λ,D2*)∈GT        …(94)
を算出し、当該関数値e(λ,D2*)を出力する（ステップＳ２２５）。
【０２５５】
次に、判定部２２２ｄの比較部２２２ｄｃに関数値e(λ,D2*)が入力される。比較部２２２ｄｃは、関数値e(λ,D2*)が 
e(λ,D2*)=1∈GT         …(95)
を満たすか否かを判定し、その判定結果を出力する（ステップＳ２２６）。
【０２５６】
ここで、２２２ｄｃから出力された判定結果が、e(λ,D2*)=1∈GTを満たす旨の判定結果である場合、関数演算部２２２ｂに関数値S〜が入力される。関数演算部２２２ｂは、関数値S〜を単射関数Rに入力して共通鍵
K〜=R(S〜)         …(96)
を算出し、当該共通鍵K〜を出力する（ステップＳ２２７）。そして、共通鍵復号部２２２ｂに共通鍵K〜と暗号文C1とが入力され、共通鍵復号部２２２ｂは、当該共通鍵K〜と暗号文C1とを共通鍵復号関数Decに入力して復号値
M〜=DecK〜(C1)         …(97)
を算出し、当該復号値M〜を出力する（ステップＳ２２８）。
【０２５７】
一方、比較部２２２ｄｃから出力された判定結果が、e(λ,D2*)=1∈GTを満たさない旨の判定結果である場合、共通鍵復号部１２２ｅは、エラー出力（⊥）を行う（ステップＳ２２９）。
【０２５８】
〔変形例等〕
なお、本発明は上述の各実施の形態に限定されるものではない。例えば、第１実施形態のステップＳ１０１では、バイナリ系列の乱数を共通鍵Kとしたが、予め設定された複数のバイナリ系列から定められた規則にしたがって選択された値を共通鍵Kとしてもよい。同様に、第１実施形態のステップＳＳ１１３では、有限体Fqの元の乱数をαとしたが、有限体Fqの元から定められた規則にしたがってαを選択してもよい。その他の乱数によって生成される値についても同様な変形が可能である。
【０２５９】
また、第１実施形態では、式(69)で得られる関数値をそのままr及びρとして用いた。しかし、式(69)で得られる関数値をさらに或る付加関数に入力して得られる関数値をrやρとしてもよい。この場合には、式(78)で得られる関数値をさらに当該付加関数に入力して得られる関数値をr〜やρ〜とする。同様に、第２実施形態では、式(87)で得られる関数値をそのままrとして用いたが、式(87)で得られる関数値をさらに或る付加関数に入力して得られる関数値をrとしてもよい。この場合には、式(92)で得られる関数値をさらに当該付加関数に入力して得られる関数値をr〜とする。
【０２６０】
また、第１，２実施形態の復号処理では、ステップＳ１２６やＳ２２６の判定要件を満たさない場合にエラー出力がなされる例を示した。しかし、判定要件を満たさない場合に、復号装置が復号結果と無関係な乱数を出力したり、何も出力しなかったりする構成であってもよい。
【０２６１】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。例えば、第１実施形態のステップＳ１０５とステップＳ１０６との処理は並列に実行されてもよいし、ステップＳ１０６の処理の後にステップＳ１０５の処理が実行されてもよい。
【０２６２】
また、上述の有限体Fq上で定義された各演算を位数qの有限環Zq上で定義された演算に置き換えてもよい。有限体Fq上で定義された各演算を有限環Zq上で定義された演算に置き換える方法の一例は、素数やそのべき乗値以外のqを許容する方法である。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０２６３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０２６４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０２６５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２６６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【符号の説明】
【０２６７】
１，２  暗号システム
１１０，２１０  暗号化装置
１２０，２２０  復号装置
【図１】
2010123112.tif 000017
【図２】
2010123112.tif 000018
【図３】
2010123112.tif 000019
【図４】
2010123112.tif 000020
【図５】
2010123112.tif 000021
【図６】
2010123112.tif 000022
【図７】
2010123112.tif 000023
【図８】
2010123112.tif 000024
【図９】
2010123112.tif 000025
【図１０】
2010123112.tif 000026
【図１１】
2010123112.tif 000027
【図１２】
2010123112.tif 000028
【図１３】
2010123112.tif 000029
【図１４】
2010123112.tif 000030
【手続補正書】
【提出日】平成23年10月6日(2011.10.6)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】変更
【補正の内容】
【００３３】
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT            …(5)
を用いて双線形関数eを構成する。本形態の双線形関数eは、巡回群G1のn+1個の元γL(L=1,...,n+1)からなるn+1次元ベクトル(γ1,...,γn+1)と、巡回群G2のn+1個の元γL*(L=1,...,n+1)からなるn+1次元ベクトル(γ1*,...,γn+1*)との入力に対し、巡回群GTの１個の元
e=ΠL=1n+1 Pair(γL, γL*)          …(6)
を出力する関数である。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７６
【補正方法】変更
【補正の内容】
【００７６】
単射関数：「単射関数」とは、値域に属するそれぞれの元がその定義域に属するそれぞれ一つの元のみの像である関数、又は、それとみなせる関数を表す。単射関数の例は、参考文献１に開示された「KDF(Key Derivation Function)」などのハッシュ関数である。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００７７
【補正方法】変更
【補正の内容】
【００７７】
擬似的なランダム関数：「擬似的なランダム関数」とは、任意の確率的多項式時間アルゴリズムが集合Φζとその部分集合φζとを区別できない場合における、当該部分集合φζに属する関数、又は、それとみなせる関数を表す。ただし、集合Φζは集合{0,1}*の元を集合{0,1}ζの元へ写すすべての関数の集合である。擬似的なランダム関数の例は、上述のようなハッシュ関数である。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００９３
【補正方法】変更
【補正の内容】
【００９３】
以上のように、式(36)と式(37)とを用いることで論理和や論理積からなる論理式を多項式f(x)で表現できる。例えば、論理式{(x=η1)∨(x=η2)∨(x=η3)}∧(x=η4)∧(x=η5)は、多項式
f(x)=ι1・{(x-η1)・(x-η2)・(x-η3)}+ι2・(x-η4)+ι3・(x-η5)  …(38)
で表現できる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００９６
【補正方法】変更
【補正の内容】
【００９６】
論理和及び／又は論理積を含む論理式をH(H≧1)種類の不定元x0,...,xH-1を用いて表現した多項式をf(x0,...,xH-1)と表現する。また、各不定元x0,...,xH-1に対応する命題を「xhがηhである」とする。ただし、ηh（h=0,...H-1）は命題ごとに定まる定数である。この場合、当該論理式を示す多項式f(x0,...,xH-1)は、不定元xhと定数ηhとの差をとる多項式によって当該不定元xhが当該定数ηhであるという命題を表現し、命題をそれぞれ表現する多項式の積によって当該命題の論理和を表現し、命題又は命題の論理和をそれぞれ表現する多項式の線形和によって当該命題又は命題の論理和の論理積を表現し、それによって論理式を表現した多項式となる。例えば、５つの不定元x0,...,x4を用い、論理式{(x0=η0)∨(x1=η1)∨(x2=η2)}∧(x3=η3)∧(x4=η4)を多項式で表現すると、
f(x0,...,x4)=ι0・{(x0-η0)・(x1-η1)・(x2-η2)}+ι1・(x3-η3)+ι2・(x4-η4)
となる。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１００
【補正方法】変更
【補正の内容】
【０１００】
例えば、式(39)(40)の代わりに
w→=(w1,...,wn)=(x0,...,xn-1)        …(43)
v→=(v1,...,vn)=(θ0,...,θn-1)          …(44)
としても、論理式を示す多項式f(x)が0であるか否かと、式(41)の内積が0であるか否かとは等価である。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１３２
【補正方法】変更
【補正の内容】
【０１３２】
(DEC-5)式(56)を満たすのであれば暗号文C1の復号結果を出力し、式(56)を満たさないのであれば⊥（エラー）を出力する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１５９
【補正方法】変更
【補正の内容】
【０１５９】
式(64)の暗号文が入力され(DEC-11)た復号オラクルは、関数値S〜=e(C2, D1*)∈GTを生成し(DEC-21)、関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と暗号文C3との排他的論理和値K〜を算出し、排他的論理和値K〜と暗号文C1(+)ΔMとを衝突困難な関数Hに入力して有限体Fqの元r〜ΔM及びρ〜ΔMを算出する(DEC-32)。そして、復号オラクルは、v→の要素vμと、元r〜ΔMと、基底ベクトルbi∈G1n+1(i=1,...,n+1)と、元ρ〜ΔMとに対して、
C2〜=r〜ΔM・(Σμ=1nvμ・bμ)+ρ〜ΔM・bn+1∈G1n+1         …(65)
を算出し(DEC-41)、関数値C2〜と暗号文C2とが等しいか否かを判定する。ここでr〜ΔM≠r〜であり、ρ〜ΔM≠ρ〜であるため、式(65)はこの関係を満たさず、復号オラクルは⊥（エラー）を出力する。
【手続補正９】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１６
【補正方法】変更
【補正の内容】
【請求項１６】
請求項１５の復号装置であって、
前記入力部に入力される前記暗号文C1と前記第２暗号文C2∈G1n+1とを含む値は、バイナリ系列である第３暗号文C3をさらに含み、
当該復号装置は、前記関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と前記第３暗号文C3との排他的論理和値K〜を算出するように構成された排他的論理和演算部をさらに含み、
前記関数演算部は、前記排他的論理和値K〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜及びρ〜を算出するように構成され、
前記判定部は、
前記n次元ベクトルv→の要素vμ(μ=1,...,n)と前記値r〜及びρ〜とを用い、関数値C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を算出するように構成されたベクトル演算部と、
前記関数値C2〜と前記第２暗号文C2とが等しいか否かを判定するように構成された比較部と、を含み、
当該復号装置は、前記比較部での判定結果が、前記関数値C2〜と前記第２暗号文C2とが等しい旨の判定結果である場合に、前記排他的論理和値K〜を共通鍵とし、当該排他的論理和値K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するように構成された共通鍵復号部をさらに有する、復号装置。
【手続補正１０】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項３０
【補正方法】変更
【補正の内容】
【請求項３０】
請求項２９の復号方法であって、
前記ステップ(A)で入力される前記暗号文C1と前記第２暗号文C2∈G1n+1とを含む値は、バイナリ系列である第３暗号文C3をさらに含み、
当該復号方法は、前記復号装置の第４手段において、前記関数値S〜を単射関数Rに入力して得られるバイナリ系列である関数値R(S〜)と前記第３暗号文C3との排他的論理和値K〜を算出するステップをさらに含み、
前記ステップ(C)は、前記復号装置の第５手段において、前記排他的論理和値K〜と前記暗号文C1とを前記衝突困難な関数Hに入力して前記値r〜及びρ〜を算出するステップを含み、
前記ステップ(D)は、
(D-1) 前記復号装置の第６手段において、前記n次元ベクトルv→の要素vμ(μ=1,...,n)と前記値r〜及びρ〜とを用い、関数値C2〜=r〜・(Σμ=1nvμ・bμ)+ρ〜・bn+1∈G1n+1を算出するステップと、
(D-2) 前記復号装置の第７手段において、前記関数値C2〜と前記第２暗号文C2とが等しいか否かを判定するステップと、を含み、
当該復号方法は、前記ステップ(D-2)での判定結果が、前記関数値C2〜と前記第２暗号文C2とが等しい旨の判定結果である場合に、前記復号装置の第８手段において、前記排他的論理和値K〜を共通鍵とし、当該排他的論理和値K〜と前記暗号文C1とを共通鍵復号関数に入力して復号値M〜を算出し、当該復号値M〜を出力するステップをさらに有する。
【国際調査報告】
2010123112.tif 000031
2010123112.tif 000032