(57)【要約】【課題】関数秘匿性を持つ複数入力内積関数型暗号技術を提供する。【解決手段】マスター秘密鍵mskを用いて、m次元ベクトル{xι}ι∈[n]から所定の式により2m+2k+1次元ベクトル{cι}ι∈[n]を計算するベクトル計算部と、秘密鍵Kを用いて、2m+2k+1次元ベクトル{cι}ι∈[n]から、Cι=SKE.Enc(K, cι) (ι∈[n])を計算し、マスター秘密鍵mskを用いて、暗号文{ctι}ι∈[n]（ただし、ctι=(κι, Cι, ι)）を生成する暗号文生成部とを含む。【選択図】図４
2019117232.tif 000002
【特許請求の範囲】
【請求項１】
Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、
前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、
kを1以上の整数、f(x1, …, xn)=Σι∈[n]xι・yιを内積関数（ただし、nは1以上の整数、y1, …, ynは内積関数の定義に用いるm次元ベクトル）、νをe(G1, G2)ν=gTを満たすZpの要素、ppをアリティn、ベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータ、msk=(B1, …, Bn, B1*, …, Bn*, κ1, …, κn)をマスター秘密鍵（ただし、B1, …, BnはZp上の2m+2k+1次元正則行列、Bι*=ν(Bι-1)T (ι∈[n])、KはSKE.Genにより生成した共通鍵暗号の秘密鍵、κ1, …, κnは次式を満たす秘密鍵Kと同じビット長のビット列）とし、
【数１７】
2019117232.tif 000019
m次元ベクトル{xι}ι∈[n]から暗号文{ctι}ι∈[n]を生成する暗号化装置であって、
マスター秘密鍵mskを用いて、前記ベクトル{xι}ι∈[n]から次式により2m+2k+1次元ベクトル{cι}ι∈[n]を計算するベクトル計算部と、
【数１８】
2019117232.tif 000020
秘密鍵Kを用いて、前記ベクトル{cι}ι∈[n]から、Cι=SKE.Enc(K, cι) (ι∈[n])を計算し、マスター秘密鍵mskを用いて、前記暗号文{ctι}ι∈[n]（ただし、ctι=(κι, Cι, ι)）を生成する暗号文生成部と
を含む暗号化装置。
【請求項２】
Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、
前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、
kを1以上の整数、f(x1, …, xn)=Σι∈[n]xι・yιを内積関数（ただし、nは1以上の整数、y1, …, ynは内積関数の定義に用いるm次元ベクトル）、νをe(G1, G2)ν=gTを満たすZpの要素、ppをアリティn、ベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータ、sk=SKE.Enc(K, {kι}ι∈[n])を復号鍵（ただし、{rι}ι∈[n]はΣι∈[n]rι=0を満たすZpの要素、B1, …, BnはZp上の2m+2k+1次元正則行列、Bι*=ν(Bι-1)T (ι∈[n])、{kι}ι∈[n]は次式で計算される2m+2k+1次元ベクトル）とし、
【数１９】
2019117232.tif 000021
前記復号鍵skを用いて、請求項１に記載の暗号化装置がm次元ベクトル{xι}ι∈[n]から生成した暗号文{ctι}ι∈[n]（ただし、ctι=(κι, Cι, ι)）から関数値f(x1, …, xn)を生成する復号装置であって、
前記暗号文{ctι}ι∈[n]から、次式により秘密鍵K'を計算する秘密鍵計算部と、
【数２０】
2019117232.tif 000022
前記秘密鍵K'を用いて、前記復号鍵skと前記暗号文{ctι}ι∈[n]から{k'ι}ι∈[n]=SKE.Dec(K', sk)と{c'ι}ι∈[n]（ただし、c'ι=SKE.Dec(K', Cι)）を計算するベクトル復号部と、
前記{k'ι}ι∈[n]と前記{c'ι}ι∈[n]から、次式により双線型写像値hTを計算する双線型写像計算部と、
【数２１】
2019117232.tif 000023
前記双線型写像値hTに対してgTz=hTを満たすZpの要素zを前記関数値f(x1, …, xn)として生成する関数値生成部と
を含む復号装置。
【請求項３】
Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、
前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、
k、λを1以上の整数、νをe(G1, G2)ν=gTを満たすZpの要素、ppをベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータ、msk=(D, D*, K1, K2)をマスター秘密鍵（ただし、DはZp上の2m+2k+1次元正則行列、D*=ν(D-1)T、K1, K2はλビットのビット列）とし、
F1:{0, 1}λ×{0, 1}λ→Zp(2m+2k+1)×(2m+2k+1), F2: {0, 1}λ×{0, 1}λ→{0, 1}λを擬似ランダム関数、S={s1, …, s|S|}を引数のインデックス集合（ただし、siはインデックス集合Sの要素を昇順に並べたときのi番目の要素）、f({xι}ι∈S)=Σι∈Sxι・yιを内積関数（ただし、yι (ι∈S)は内積関数の定義に用いるm次元ベクトル）とし、
m次元ベクトル{xι}ι∈Sから暗号文{ctι}ι∈Sを生成する暗号化装置であって、
マスター秘密鍵mskを用いて、擬似ランダム関数値{Wι}ι∈S（ただし、Wι=F1(K1, ι)）, {κι}ι∈S（ただし、κι=F2(K2, ι)）を計算する擬似ランダム関数値計算部と、
マスター秘密鍵mskを用いて、前記擬似ランダム関数値{Wι}ι∈Sから行列積{Bι}ι∈S（ただし、Bι=DWι）を計算する行列積計算部と、
前記行列積{Bι}ι∈Sと前記ベクトル{xι}ι∈Sから次式により2m+2k+1次元ベクトル{cι}ι∈Sを計算するベクトル計算部と、
【数２２】
2019117232.tif 000024
前記擬似ランダム関数値{κι}ι∈Sと前記ベクトル{cι}ι∈Sから前記暗号文{ctι}ι∈S（ただし、ctι=(κι, cι, ι)）を生成する暗号文生成部と
を含む暗号化装置。
【請求項４】
Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、
前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、
k、λを1以上の整数、νをe(G1, G2)ν=gTを満たすZpの要素、ppをベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータとし、
F1:{0, 1}λ×{0, 1}λ→Zp(2m+2k+1)×(2m+2k+1), F2: {0, 1}λ×{0, 1}λ→{0, 1}λを擬似ランダム関数、S={s1, …, s|S|}を引数のインデックス集合（ただし、siはインデックス集合Sの要素を昇順に並べたときのi番目の要素）、f({xι}ι∈S)=Σι∈Sxι・yιを内積関数（ただし、yι (ι∈S)は内積関数の定義に用いるm次元ベクトル）、skS=(C|S|, S)を復号鍵（ただし、K1, K2はλビットのビット列、Wι=F1(K1, ι) (ι∈S), κι=F2(K2, ι) (ι∈S)、DはZp上の2m+2k+1次元正則行列、D*=ν(D-1)T、Bι*=D*(Wι-1)T (ι∈S)、{rι}ι∈SはΣι∈Srι=0を満たすZpの要素、{kι}ι∈Sは次式で計算される2m+2k+1次元ベクトル）とし、
【数２３】
2019117232.tif 000025
前記復号鍵skSを用いて、請求項３に記載の暗号化装置がm次元ベクトル{xι}ι∈Sから生成した暗号文{ctι}ι∈S（ただし、ctι=(κι, cι, ι)）から関数値f({xι}ι∈S)を生成する復号装置であって、
前記暗号文{ctι}ι∈S を用いて、前記復号鍵sksから次式により{k'ι}ι∈Sを計算するベクトル復号部と、
【数２４】
2019117232.tif 000026
前記{k'ι}ι∈S と前記暗号文{ctι}ι∈S から、次式により双線型写像値hTを計算する双線型写像計算部と、
【数２５】
2019117232.tif 000027
前記双線型写像値hTに対してgTz=hTを満たすZpの要素zを前記関数値f({xι}ι∈S)として生成する関数値生成部と
を含む復号装置。
【請求項５】
Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、
前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、
kを1以上の整数、f(x1, …, xn)=Σι∈[n]xι・yιを内積関数（ただし、nは1以上の整数、y1, …, ynは内積関数の定義に用いるm次元ベクトル）、νをe(G1, G2)ν=gTを満たすZpの要素、ppをアリティn、ベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータ、msk=(B1, …, Bn, B1*, …, Bn*, κ1, …, κn)をマスター秘密鍵（ただし、B1, …, BnはZp上の2m+2k+1次元正則行列、Bι*=ν(Bι-1)T (ι∈[n])、KはSKE.Genにより生成した共通鍵暗号の秘密鍵、κ1, …, κnは次式を満たす秘密鍵Kと同じビット長のビット列）とし、
【数２６】
2019117232.tif 000028
暗号化装置が、m次元ベクトル{xι}ι∈[n]から暗号文{ctι}ι∈[n]を生成する暗号化方法であって、
マスター秘密鍵mskを用いて、前記ベクトル{xι}ι∈[n]から次式により2m+2k+1次元ベクトル{cι}ι∈[n]を計算するベクトル計算ステップと、
【数２７】
2019117232.tif 000029
秘密鍵Kを用いて、前記ベクトル{cι}ι∈[n]から、Cι=SKE.Enc(K, cι) (ι∈[n])を計算し、マスター秘密鍵mskを用いて、前記暗号文{ctι}ι∈[n]（ただし、ctι=(κι, Cι, ι)）を生成する暗号文生成ステップと
を含む暗号化方法。
【請求項６】
Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、
前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、
kを1以上の整数、f(x1, …, xn)=Σι∈[n]xι・yιを内積関数（ただし、nは1以上の整数、y1, …, ynは内積関数の定義に用いるm次元ベクトル）、νをe(G1, G2)ν=gTを満たすZpの要素、ppをアリティn、ベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータ、sk=SKE.Enc(K, {kι}ι∈[n])を復号鍵（ただし、{rι}ι∈[n]はΣι∈[n]rι=0を満たすZpの要素、B1, …, BnはZp上の2m+2k+1次元正則行列、Bι*=ν(Bι-1)T (ι∈[n])、{kι}ι∈[n]は次式で計算される2m+2k+1次元ベクトル）とし、
【数２８】
2019117232.tif 000030
復号装置が、前記復号鍵skを用いて、請求項５に記載の暗号化方法がm次元ベクトル{xι}ι∈[n]から生成した暗号文{ctι}ι∈[n]（ただし、ctι=(κι, Cι, ι)）から関数値f(x1, …, xn)を生成する復号方法であって、
前記暗号文{ctι}ι∈[n]から、次式により秘密鍵K'を計算する秘密鍵計算ステップと、
【数２９】
2019117232.tif 000031
前記秘密鍵K'を用いて、前記復号鍵skと前記暗号文{ctι}ι∈[n]から{k'ι}ι∈[n]=SKE.Dec(K', sk)と{c'ι}ι∈[n]（ただし、c'ι=SKE.Dec(K', Cι)）を計算するベクトル復号ステップと、
前記{k'ι}ι∈[n]と前記{c'ι}ι∈[n]から、次式により双線型写像値hTを計算する双線型写像計算ステップと、
【数３０】
2019117232.tif 000032
前記双線型写像値hTに対してgTz=hTを満たすZpの要素zを前記関数値f(x1, …, xn)として生成する関数値生成ステップと
を含む復号方法。
【請求項７】
請求項１または３に記載の暗号化装置、請求項２または４に記載の復号装置のいずれかの装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号方式の構成に関し、特に暗号文から平文の関数値を復号する関数型暗号に関する。
【背景技術】
【０００２】
単一入力関数型暗号では、暗号文を復号するための鍵（復号鍵）に関数fを埋め込むことができる。関数fを埋め込んだ復号鍵を用いて入力xの暗号文を復号すると、関数値f(x)が復号される。
【０００３】
複数入力関数型暗号は、単一入力関数型暗号を拡張したものであり、１つの引数をもつ関数だけでなく、２以上の引数をもつ関数をも復号鍵に埋め込むことができる方式である。つまり、引数1, …, nに対応する値x1, …, xnの暗号文ct1, …, ctnがあるとき、引数1, …, nをとる関数fを埋め込んだ復号鍵skfを用いて暗号文ct1, …, ctnを復号すると、関数値f(x1, …, xn)が復号される。ただし、関数fがとる引数のうち、どれか１つでもその引数に対応する暗号文が存在しない場合は復号することができない。
【０００４】
内積関数型暗号は、扱う関数fを内積に限定した関数型暗号であり、複数入力内積関数型暗号では、復号鍵にn個のベクトルy1, …, ynが埋め込まれていて、n個のベクトルx1, …, xnをそれぞれ暗号化したn個の暗号文ct1, …, ctnを復号鍵で復号すると、関数値
【０００５】
【数１】
2019117232.tif 000003
【０００６】
が復号されるというものである。
【０００７】
関数型暗号に対して関数秘匿性という性質がある。この関数秘匿性とは、関数を埋め込んだ復号鍵が、その関数を秘匿しているという性質である（内積関数型暗号の場合はベクトルが関数に対応する）。すなわち、ある関数を埋め込んだ復号鍵の所持者であっても、その埋め込まれた関数がどのような関数であるかを知ることができないという性質である。
【０００８】
従来、関数秘匿性を持つ単一入力内積関数型暗号（非特許文献１）や複数入力内積関数型暗号（非特許文献２）は構成されている。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】A. Bishop, A. Jain, and L. Kowalczyk, “Function-hiding inner product encryption”, In T. Iwata and J. H. Cheon, editors, ASIACRYPT 2015, Part I, vol. 9452 of LNCS, pp. 470-491, Springer, Heidelberg, Nov./Dec. 2015.
【非特許文献２】M. Abdalla, R. Gay, M. Raykova, and H. Wee, “Multi-input inner-product functional encryption from pairings”, In J. Coron and J. B. Nielsen, editors, EUROCRYPT 2017, Part I, vol. 10210 of LNCS, pp. 601-626, Springer, Heidelberg, May 2017.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、関数秘匿性を持つ複数入力内積関数型暗号の構成方法は知られていない。内積関数型暗号は、クラウドサーバ上のデータベースに対する統計計算などへの応用が考えられる。例えば、当該データベースが個人情報のような機微な情報を含んでいる場合、どのような計算を行っているのかをサーバから秘匿する必要があることもある。そのような場合、関数秘匿性を持つ内積関数型暗号でなければ、サーバに対して復号鍵から計算内容が漏洩する可能性がある。
【００１１】
そこで本発明では、関数秘匿性を持つ複数入力内積関数型暗号技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の一態様は、Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、kを1以上の整数、f(x1, …, xn)=Σι∈[n]xι・yιを内積関数（ただし、nは1以上の整数、y1, …, ynは内積関数の定義に用いるm次元ベクトル）、νをe(G1, G2)ν=gTを満たすZpの要素、ppをアリティn、ベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータ、msk=(B1, …, Bn, B1*, …, Bn*, κ1, …, κn)をマスター秘密鍵（ただし、B1, …, BnはZp上の2m+2k+1次元正則行列、Bι*=ν(Bι-1)T (ι∈[n])、KはSKE.Genにより生成した共通鍵暗号の秘密鍵、κ1, …, κnは次式を満たす秘密鍵Kと同じビット長のビット列）とし、
【００１３】
【数２】
2019117232.tif 000004
【００１４】
m次元ベクトル{xι}ι∈[n]から暗号文{ctι}ι∈[n]を生成する暗号化装置であって、マスター秘密鍵mskを用いて、前記ベクトル{xι}ι∈[n]から次式により2m+2k+1次元ベクトル{cι}ι∈[n]を計算するベクトル計算部と、
【００１５】
【数３】
2019117232.tif 000005
【００１６】
秘密鍵Kを用いて、前記ベクトル{cι}ι∈[n]から、Cι=SKE.Enc(K, cι) (ι∈[n])を計算し、マスター秘密鍵mskを用いて、前記暗号文{ctι}ι∈[n]（ただし、ctι=(κι, Cι, ι)）を生成する暗号文生成部とを含む。
【００１７】
本発明の一態様は、Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とし、前記巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であり、k、λを1以上の整数、νをe(G1, G2)ν=gTを満たすZpの要素、ppをベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTからなる公開パラメータ、msk=(D, D*, K1, K2)をマスター秘密鍵（ただし、DはZp上の2m+2k+1次元正則行列、D*=ν(D-1)T、K1, K2はλビットのビット列）とし、F1:{0, 1}λ×{0, 1}λ→Zp(2m+2k+1)×(2m+2k+1), F2: {0, 1}λ×{0, 1}λ→{0, 1}λを擬似ランダム関数、S={s1, …, s|S|}を引数のインデックス集合（ただし、siはインデックス集合Sの要素を昇順に並べたときのi番目の要素）、f({xι}ι∈S)=Σι∈Sxι・yιを内積関数（ただし、yι (ι∈S)は内積関数の定義に用いるm次元ベクトル）とし、m次元ベクトル{xι}ι∈Sから暗号文{ctι}ι∈Sを生成する暗号化装置であって、マスター秘密鍵mskを用いて、擬似ランダム関数値{Wι}ι∈S（ただし、Wι=F1(K1, ι)）, {κι}ι∈S（ただし、κι=F2(K2, ι)）を計算する擬似ランダム関数値計算部と、マスター秘密鍵mskを用いて、前記擬似ランダム関数値{Wι}ι∈Sから行列積{Bι}ι∈S（ただし、Bι=DWι）を計算する行列積計算部と、前記行列積{Bι}ι∈Sと前記ベクトル{xι}ι∈Sから次式により2m+2k+1次元ベクトル{cι}ι∈Sを計算するベクトル計算部と、
【００１８】
【数４】
2019117232.tif 000006
【００１９】
前記擬似ランダム関数値{κι}ι∈Sと前記ベクトル{cι}ι∈Sから前記暗号文{ctι}ι∈S（ただし、ctι=(κι, cι, ι)）を生成する暗号文生成部とを含む。
【発明の効果】
【００２０】
本発明によれば、関数秘匿性を持つ複数入力内積関数型暗号技術を構成することができる。
【図面の簡単な説明】
【００２１】
【図１】内積関数型暗号システム１０の構成の一例を示すブロック図。
【図２】システムパラメータ生成装置１００の構成の一例を示すブロック図。
【図３】鍵生成装置２００の構成の一例を示すブロック図。
【図４】暗号化装置３００の構成の一例を示すブロック図。
【図５】復号装置４００の構成の一例を示すブロック図。
【図６】システムパラメータ生成装置１００の動作の一例を示すフローチャート。
【図７】マスター秘密鍵生成部１２０の動作の一例を示すフローチャート。
【図８】鍵生成装置２００の動作の一例を示すフローチャート。
【図９】暗号化装置３００の動作の一例を示すフローチャート。
【図１０】復号装置４００の動作の一例を示すフローチャート。
【図１１】内積関数型暗号システム５０の構成の一例を示すブロック図。
【図１２】システムパラメータ生成装置５００の構成の一例を示すブロック図。
【図１３】鍵生成装置６００の構成の一例を示すブロック図。
【図１４】暗号化装置７００の構成の一例を示すブロック図。
【図１５】復号装置８００の構成の一例を示すブロック図。
【図１６】システムパラメータ生成装置５００の動作の一例を示すフローチャート。
【図１７】マスター秘密鍵生成部５２０の動作の一例を示すフローチャート。
【図１８】鍵生成装置６００の動作の一例を示すフローチャート。
【図１９】暗号化装置７００の動作の一例を示すフローチャート。
【図２０】復号装置８００の動作の一例を示すフローチャート。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００２３】
＜記法・用語＞
まず、記法や基礎的概念に関する用語について説明する。
【００２４】
ベクトルは行ベクトルとして扱う。
【００２５】
集合Sからその要素sをランダムに選ぶことをs←USと表記する。
【００２６】
集合Sに対し、|S|を集合Sの要素数とする。
【００２７】
Zを整数の集合、pを素数とし、Zp=Z/pZとする。
【００２８】
自然数nに対してn以下の自然数の集合を[n]と表記する。
【００２９】
m次元ベクトル空間において、ある基底Bの一次結合でベクトルvを表すとき、それぞれの係数がa1, …, amであるとする。このとき、v=(a1, …, am)Bと表記する。
【００３０】
次に、本発明の実施形態で用いる要素技術について説明する。
【００３１】
［共通鍵暗号］
共通鍵暗号SKEは鍵生成アルゴリズムSKE.Gen、暗号化アルゴリズムSKE.Enc、復号アルゴリズムSKE.Decの３つのアルゴリズムにより構成される。つまり、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)である。鍵生成アルゴリズムSKE.Genは秘密鍵Kを出力する。暗号化アルゴリズムSKE.Encは、秘密鍵Kとメッセージmを入力とし、暗号文cを出力する。つまり、c=SKE.Enc(K, m)となる。復号アルゴリズムSKE.Decは、秘密鍵Kと暗号文cを入力とし、メッセージm（またはエラー⊥）を出力する。つまり、m=SKE.Dec(K, c)となる。
【００３２】
なお、本発明の実施形態で説明する内積関数型暗号技術が安全であるためには、ある種の識別不可能性（具体的には、Indistinguishability under Chosen-Plaintext Attack（選択的平文攻撃のもとでの識別不可能性））を満たす共通鍵暗号を用いる必要がある。共通鍵暗号及び上記識別不可能性については、例えば、参考非特許文献１に記載されている。
（参考非特許文献１：COSC 530: Lecture Notes on Symmetric-Key Encryption, [online], ［平成29年12月4日検索］、インターネット<URL: http://people.cs.georgetown.edu/~adam/fa15530/cs530-lec4.pdf>）
【００３３】
［擬似ランダム関数］
PRF={Fк: FSк×Domк→Rngк}кを鍵空間{FSк}к、定義域{Domк}к、値域{Rngк}кを持つ関数族とする。このとき、もし任意の多項式時間の識別者Dに対して、関数Fкと真正ランダム関数RFк: Domк→Rngкが見分けられなければ、PRF={Fк}кを擬似ランダム関数族と呼ぶ。擬似ランダム関数の具体例は、例えば、参考非特許文献２に記載されている。
（参考非特許文献２：O.ゴールドライヒ，“現代暗号・確率的証明・擬似乱数”，シュプリンガー・フェアラーク東京，2001年）
なお、共通鍵暗号及び擬似ランダム関数は任意の一方向性関数から構成できることが広く知られている。また、実用上、共通鍵暗号を実現したものとしてAES(Advanced Encryption Standard)を用いることが多い。
【００３４】
［双対ペアリングベクトル空間(DPVS: Dual Pairing Vector Space)］
位数が素数pの巡回群~G1, ~G2, ~GTを考える。また、巡回群~G1, ~G2, ~GTの生成元をそれぞれG1, G2, gTとする。これらの巡回群の間には非退化双線型写像e: ~G1×~G2→~GTがあるものとする。このとき、~V=~G1m, ~V*=~G2mはそれぞれZp上のm次元ベクトル空間となり、これらを合わせて双対ペアリングベクトル空間DPVS=(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)と呼ぶ。詳しくは、例えば、参考非特許文献３に記載されている。
（参考非特許文献３：T. Okamoto and K. Takashima, “Fully secure functional encryption with general relations from the decisional linear assumption”, In T. Rabin, editor, CRYPTO 2010, vol. 6223 of LNCS, pp. 191-208, Springer, Heidelberg, Aug. 2010.）
【００３５】
また、Zp上のm次正方行列Bをランダムに選び、その双対行列B*をB*=ν(B-1)T（νはZpのランダムな値）と定義する。そして、双対ペアリングベクトル空間DPVS上の行列~B、~B*を、それぞれ行列BをG1の係数に持つ行列、行列B*をG2の係数に持つ行列と定義する。すなわち、B=(bi,j) (1≦i, j≦n), B*=(b*i,j) (1≦i, j≦n)とすると、~B=(bi,jG1) (1≦i, j≦n), ~B*=(b*i,jG2) (1≦i, j≦n)である。このとき、~B, ~B*の各行はそれぞれ~V, ~V*の基底となる。
【００３６】
さらに、双対ペアリングベクトル空間DPVSのベクトル(x)~B, (y)~B*に対して、e((x)~B, (y)~B*)を各要素のペアリングの積によりe(G1, G2)νx.yを求める関数とする。(x)~B, (y)~B*はそれぞれ~Bの各行を基底ベクトルとする一次結合として表されるベクトル、~B*の各行を基底ベクトルとする一次結合として表されるベクトルであり、x・yは内積を表す。
【００３７】
なお、以下では、巡回群~G1, ~G2, ~GTはk-線形仮定と呼ばれる性質が成り立つ双線型群であるとする。双線型群の具体例は、例えば、参考非特許文献４に記載されている。また、k-線形仮定の定義については、例えば、参考非特許文献５に記載されている。k-線形仮定が成り立つ双線型群を楕円曲線から構成する一例が参考非特許文献５に、上記楕円曲線のより一般的な構成方法が参考非特許文献６に記載されている。
（参考非特許文献４：D. Boneh and M. K. Franklin, “Identity-based encryption from the Weil pairing”, In J. Kilian, editor, CRYPTO 2001, vol. 2139 of LNCS, pp. 213-229, Springer, Heidelberg, Aug. 2001.）
（参考非特許文献５：Allison B. Lewko and Brent Waters, “Efficient pseudorandom functions from the decisional linear assumption and weaker variants”, Proceedings of the 2009 ACM Conference on Computer and Communications Security, CCS 2009, Chicago, Illinois, USA, pp. 112-120, Nov. 2009.）
（参考非特許文献６：David Freeman, Michael Scott and Edlyn Teske, “A taxonomy of pairing-friendly elliptic curves, IACR Cryptology ePrint Archive, vol. 2006, pp. 372, http://eprint.iacr.org/2006/372, 2006.）
【００３８】
＜技術的背景＞
以下、２つの関数秘匿性を持つ複数入力内積関数型暗号について説明する。１つ目が引数に制限がある複数入力内積関数型暗号であり、２つ目が引数に制限がない複数入力内積関数型暗号である。ここで、引数に制限がないとは、当該暗号の利用開始時に引数の集合を決定する必要がなく、暗号化や復号鍵生成時に任意の引数を指定できることをいう。
【００３９】
引数に制限がある複数入力内積関数型暗号では、暗号の利用開始時に扱う引数の集合をあらかじめ決定する必要があり、それ以降変更することができない。そして、復号鍵はその決定された引数の集合に対するものしか作ることができない。しかし、暗号化したいデータは、随時増えていくことが通常であり、利用開始時に扱う引数を固定することは非常に不都合である。このような場合に、引数に制限がない複数入力内積関数型暗号は有効である。
【００４０】
以下、まず、引数に制限がある複数入力内積関数型暗号について説明する。その後、引数に制限がない複数入力内積関数型暗号について説明する。
［引数に制限がある複数入力内積関数型暗号］
引数に制限がある複数入力内積関数型暗号は、Setup, KeyGen, Enc, Decの４つのアルゴリズムから構成される。
【００４１】
（セットアップアルゴリズムSetup(k, n, m, 1λ)）
kを任意の自然数とする。ただし、kの値が大きいほど安全性は高くなる。
【００４２】
セットアップアルゴリズムSetupは、公開パラメータppとマスター秘密鍵mskを生成、出力する。公開パラメータppを、内積関数の引数の数であるアリティn(nは1以上の整数)、内積関数の定義に用いるベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTとする。このとき、e(G1, G2)ν=gT(νはZpの要素)となるようにする。また、マスター秘密鍵mskを以下のように生成する。
(1) Zp上の2m+2k+1次元正則行列B1, …, Bnをランダムに選ぶ。
(2) すべてのι∈[n]に対して、Bι*=ν(Bι-1)Tとする。
(3) SKE.Genにより生成した共通鍵暗号の秘密鍵Kとする。
(4) 秘密鍵Kと同じビット長λのビット列κ1, …, κnを以下の式を満たすようにランダムに選ぶ。
【００４３】
【数５】
2019117232.tif 000007
【００４４】
(5) msk=(B1, …, Bn, B1*, …, Bn*, κ1, …, κn)とする。
【００４５】
（鍵生成アルゴリズムKeyGen(pp, msk, {yι}ι∈[n])）
鍵生成アルゴリズムKeyGenは、引数のインデックス1, …, nに対応するm次元ベクトルy1, …, ynを埋め込んだ復号鍵skを生成、出力する。具体的には、復号鍵skを以下のように生成する。なお、m次元ベクトルy1, …, ynが内積関数の定義に用いるベクトルである。
(1) {rι}ι∈[n]をZpから以下の式を満たすようにランダムに選ぶ。
【００４６】
【数６】
2019117232.tif 000008
【００４７】
(2) すべてのι∈[n]に対して、2m+2k+1次元ベクトルkιを以下のように計算する。なお、0iは0のi個の列を表す。
【００４８】
【数７】
2019117232.tif 000009
【００４９】
つまり、ベクトルkιは行列~Bι*の各行を基底ベクトルとする一次結合として計算される。
(3) sk=SKE.Enc(K, {kι}ι∈[n])とする。
【００５０】
（暗号化アルゴリズムEnc(pp, msk, ι, xι)）
暗号化アルゴリズムEncは、入力されたm次元ベクトルxιを引数のインデックスιに対応させて暗号化し、暗号文ctιを生成、出力する。具体的には、暗号文ctιを以下のように生成する。
(1) 2m+2k+1次元ベクトルcιを以下のように計算する。
【００５１】
【数８】
2019117232.tif 000010
【００５２】
つまり、ベクトルcιは行列~Bιの各行を基底ベクトルとする一次結合として計算される。
(2) Cι=SKE.Enc(K, cι)とし、ctι=(κι, Cι, ι)とする。
【００５３】
（復号アルゴリズムDec(pp, sk, {ctι}ι∈[n])）
復号アルゴリズムDecは、引数1, …, nに対応する暗号文ct1, …, ctnを一つずつとり、復号鍵skを用いてそれらを復号、関数値Σxι・yιを生成、出力する。具体的には、関数値Σxι・yιを以下のように生成する。
(1) 共通鍵暗号の秘密鍵K'を以下の式で計算する。
【００５４】
【数９】
2019117232.tif 000011
【００５５】
(2) {k'ι}ι∈[n]=SKE.Dec(K', sk)、c'ι=SKE.Dec(K', Cι) (ι∈[n])と計算する。
(3) hTを以下の式で計算する。
【００５６】
【数１０】
2019117232.tif 000012
【００５７】
なお、式(6)の右辺のeは、＜記法・用語＞で説明したように、非退化双線型写像eを用いて定義される双対ペアリングベクトル空間DPVS上の関数である。
(4) gTz=hTを満たすz（zはZpの要素）を探索し、見つかったらそれを関数値Σxι・yιとして出力する。
【００５８】
［引数に制限がない複数入力内積関数型暗号］
ここでは、共通鍵暗号の鍵生成アルゴリズムSKE.Genが出力する秘密鍵はλビットのビット列集合からランダムに選んだビット列であるものとする。また、kを任意の自然数として、F1, F2をF1:{0, 1}λ×{0, 1}λ→Zp(2m+2k+1)×(2m+2k+1), F2: {0, 1}λ×{0, 1}λ→{0, 1}λであるような鍵空間、定義域、値域を持つ擬似ランダム関数とする。さらに、引数のインデックス集合をSとし、集合Sの要素を昇順に並べたときのi番目の要素をsiと表記する。
【００５９】
引数に制限がない複数入力内積関数型暗号は、Setup, KeyGen, Enc, Decの４つのアルゴリズムから構成される。
【００６０】
（セットアップアルゴリズムSetup(k, m, 1λ)）
kは任意の自然数とする。ただし、kの値が大きいほど安全性は高くなる。
【００６１】
セットアップアルゴリズムSetupは、公開パラメータppとマスター秘密鍵mskを生成、出力する。公開パラメータppを、内積関数の定義に用いるベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTとする。このとき、e(G1, G2)ν=gT(νはZpの要素)となるようにする。また、マスター秘密鍵mskを以下のように生成する。
(1) 2m+2k+1次元正則行列Dをランダムに選ぶ。
(2) D*=ν(D-1)Tとする。
(3) 擬似ランダム関数の鍵K1, K2をλビットのビット列としてランダムに選ぶ。
(4) msk=(D, D*, K1, K2)とする。
【００６２】
（鍵生成アルゴリズムKeyGen(pp, msk, S, {yι}ι∈S)）
鍵生成アルゴリズムKeyGenは、引数のインデックス集合Sと集合Sに対応するm次元ベクトル{yι}ι∈Sを入力とし、ベクトル{yι}ι∈Sを埋め込んだ復号鍵skSを生成、出力する。具体的には、復号鍵skSを以下のように生成する。なお、m次元ベクトル{yι}ι∈Sが内積関数の定義に用いるベクトルである。
(1) すべてのι∈Sに対して、擬似ランダム関数値Wι=F1(K1, ι), κι=F2(K2, ι)を計算する。ここで、Wιは、Zp上の2m+2k+1次元行列、κιは、λビットのビット列である。
(2) すべてのι∈Sに対して、Bι*=D*(Wι-1)Tとする。Wιが一つでも逆行列を持たなかった場合は処理を終了する。
(3) {rι}ι∈SをZpから以下の式を満たすようにランダムに選ぶ。
【００６３】
【数１１】
2019117232.tif 000013
【００６４】
(4) すべてのι∈Sに対して、2m+2k+1次元ベクトルkιを以下のように計算する。
【００６５】
【数１２】
2019117232.tif 000014
【００６６】
つまり、ベクトルkιは行列~Bι*の各行を基底ベクトルとする一次結合として計算される。
(5) {kι}ι∈Sを以下のように繰り返し暗号化する。
【００６７】
【数１３】
2019117232.tif 000015
【００６８】
(6) skS=(C|S|, S)とする。
【００６９】
（暗号化アルゴリズムEnc(pp, msk, ι, xι)）
暗号化アルゴリズムEncは、入力されたベクトルxιを引数のインデックスιに対応させて暗号化し、暗号文ctιを生成、出力する。具体的には、暗号文ctιを以下のように生成する。
(1) 擬似ランダム関数値Wι=F1(K1, ι), κι=F2(K2, ι)を計算する。
(2) Bι=DWιとする。
(3) 2m+2k+1次元ベクトルcιを以下のように計算する。
【００７０】
【数１４】
2019117232.tif 000016
【００７１】
つまり、ベクトルcιは行列~Bιの各行を基底ベクトルとする一次結合として計算される。
(4) ctι=(κι, cι, ι)とする。
【００７２】
（復号アルゴリズムDec(pp, skS, {ctι}ι∈S)）
復号アルゴリズムDecは、引数のインデックス集合Sの要素に対応する暗号文{ctι}ι∈Sを一つずつとり、集合Sに対応する復号鍵skSを用いてそれらを復号、関数値Σxι・yιを生成、出力する。具体的には、関数値Σxι・yιを以下のように生成する。
(1) 共通鍵暗号で暗号化されている復号鍵skSを、暗号文に添付されている秘密鍵{κι}ι∈Sで繰り返し復号する。
【００７３】
【数１５】
2019117232.tif 000017
【００７４】
(2) hTを以下の式で計算する。
【００７５】
【数１６】
2019117232.tif 000018
【００７６】
なお、式(12)の右辺のeは、＜記法・用語＞で説明したように、非退化双線型写像eを用いて定義される双対ペアリングベクトル空間DPVS上の関数である。
(3) gTz=hTを満たすz（zはZpの要素）を探索し、見つかったらそれを関数値Σxι・yιとして出力する。
【００７７】
＜第一実施形態＞
ここでは、＜技術的背景＞の［引数に制限がある複数入力内積関数型暗号］で説明した内積関数型暗号を実行するシステムである内積関数型暗号システム１０について説明する。
【００７８】
以下、＜記法・用語＞で説明したように、Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とする。なお、巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であるとする。
【００７９】
［システム構成］
図１を参照して、内積関数型暗号システム１０について説明する。図１は、内積関数型暗号システム１０の構成の一例を示すブロック図である。内積関数型暗号システム１０は、システムパラメータ生成装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００を含む。システムパラメータ生成装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００は、インターネットなどのネットワーク９００に接続し、相互に通信可能である。
【００８０】
次に、図２〜図５を参照して、システムパラメータ生成装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００の各装置について説明する。図２は、システムパラメータ生成装置１００の構成の一例を示すブロック図である。システムパラメータ生成装置１００は、公開パラメータ生成部１１０、マスター秘密鍵生成部１２０、送受信部１８０、記録部１９０を含む。更に、マスター秘密鍵生成部１２０は、正則行列生成部１２１、双対行列計算部１２２、ビット列生成部１２３、マスター秘密鍵出力部１２４を含む。送受信部１８０は、システムパラメータ生成装置１００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部１９０は、システムパラメータ生成装置１００の処理に必要な情報を適宜記録する構成部である。例えば、生成した公開パラメータppやマスター秘密鍵mskを記録する。また、共通鍵暗号の秘密鍵Kを記録しておく。
【００８１】
図３は、鍵生成装置２００の構成の一例を示すブロック図である。鍵生成装置２００は、Zp要素生成部２１０、ベクトル計算部２２０、復号鍵生成部２３０、送受信部２８０、記録部２９０を含む。送受信部２８０は、鍵生成装置２００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部２９０は、鍵生成装置２００の処理に必要な情報を適宜記録する構成部である。例えば、システムパラメータ生成装置１００から取得した公開パラメータppやマスター秘密鍵mskを記録する。また、生成した復号鍵skを記録する。さらに、共通鍵暗号の秘密鍵Kを記録しておく。
【００８２】
図４は、暗号化装置３００の構成の一例を示すブロック図である。暗号化装置３００は、ベクトル計算部３１０、暗号文生成部３２０、送受信部３８０、記録部３９０を含む。送受信部３８０は、暗号化装置３００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部３９０は、暗号化装置３００の処理に必要な情報を適宜記録する構成部である。例えば、システムパラメータ生成装置１００から取得した公開パラメータppやマスター秘密鍵mskを記録する。また、共通鍵暗号の秘密鍵Kを記録しておく。
【００８３】
図５は、復号装置４００の構成の一例を示すブロック図である。復号装置４００は、秘密鍵計算部４１０、ベクトル復号部４２０、双線型写像計算部４３０、関数値生成部４４０、送受信部４８０、記録部４９０を含む。送受信部４８０は、復号装置４００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部４９０は、復号装置４００の処理に必要な情報を適宜記録する構成部である。例えば、システムパラメータ生成装置１００から取得した公開パラメータppを記録する。また、鍵生成装置２００から取得した復号鍵skを記録する。
【００８４】
［各装置における処理］
以下、図６〜図１０を参照して、システムパラメータ生成装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００の各装置における処理について説明する。
【００８５】
ここで、kを1以上の整数、f(x1, …, xn)=Σι∈[n]xι・yιを内積関数（ただし、nは1以上の整数、y1, …, ynは内積関数の定義に用いるm次元ベクトル）とする。
【００８６】
（システムパラメータ生成装置１００における処理）
システムパラメータ生成装置１００は、セットアップアルゴリズムSetupに対応する処理を実行する装置である。システムパラメータ生成装置１００は、公開パラメータppとマスター秘密鍵mskを生成する。以下、生成手順について説明する（図６参照）。
【００８７】
公開パラメータ生成部１１０は、公開パラメータppを生成する（Ｓ１１０）。公開パラメータppは、内積関数の引数の数であるアリティn、内積関数の定義に用いるベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTである。このとき、e(G1, G2)ν=gT(νはZpの要素)となるようにする。
【００８８】
マスター秘密鍵生成部１２０は、マスター秘密鍵mskを生成する（Ｓ１２０）。以下、図７を参照して、具体的に説明する。正則行列生成部１２１は、Zp上の2m+2k+1次元正則行列B1, …, Bnをランダムに生成する（Ｓ１２１）。
【００８９】
双対行列計算部１２２は、Ｓ１２１で生成した正則行列B1, …, BnからZp上の2m+2k+1次元行列である双対行列B1*, …, Bn*を計算する（Ｓ１２２）。具体的には、Bι*=ν(Bι-1)T (ι∈[n])とする。
【００９０】
ビット列生成部１２３は、共通鍵暗号の秘密鍵Kと同じビット長のビット列κ1, …, κnを所定の式を満たすようにランダムに生成する（Ｓ１２３）。ここで、所定の式とは式(1)のことである。また、秘密鍵Kは、共通鍵暗号の鍵生成アルゴリズムSKE.Genを用いて生成された秘密鍵である。
【００９１】
マスター秘密鍵出力部１２４は、Ｓ１２１で生成した正則行列B1, …, Bn、Ｓ１２２で計算した双対行列B1*, …, Bn*、Ｓ１２３で生成したビット列κ1, …, κnからマスター秘密鍵mskをmsk=(B1, …, Bn, B1*, …, Bn*, κ1, …, κn)として生成、出力する。（Ｓ１２４）。
【００９２】
鍵生成装置２００、暗号化装置３００は、公開パラメータppとマスター秘密鍵mskを、復号装置４００は公開パラメータppを取得し、それぞれ記録部に記録する。取得方法はどのようなものでもよく、例えば、システムセットアップ装置１００が各装置に送信するようにするとよい。
【００９３】
（鍵生成装置２００における処理）
鍵生成装置２００は、鍵生成アルゴリズムKeyGenに対応する処理を実行する装置である。鍵生成装置２００は、内積関数の定義に用いるm次元ベクトル{yι}ι∈[n]から復号鍵skを生成する。以下、生成手順について説明する（図８参照）。
【００９４】
Zp要素生成部２１０は、{rι}ι∈[n]をZpから所定の式を満たすようにランダムに生成する（Ｓ２１０）。ここで、所定の式とは式(2)のことである。
【００９５】
ベクトル計算部２２０は、マスター秘密鍵mskとm次元ベクトル{yι}ι∈[n]を用いて、Ｓ２１０で生成した{rι}ι∈[n]から、所定の式により2m+2k+1次元ベクトル{kι}ι∈[n]を計算する（Ｓ２２０）。ここで、所定の式とは式(3)のことである。
【００９６】
復号鍵生成部２３０は、共通鍵暗号の秘密鍵Kを用いて、Ｓ２２０で計算したベクトル{kι}ι∈[n]から、復号鍵skをsk=SKE.Enc(K, {kι}ι∈[n])として生成する（Ｓ２３０）。
【００９７】
復号装置４００は復号鍵skを取得し、記録部４９０に記録する。取得方法はどのようなものでもよく、例えば、鍵生成装置２００が復号装置４００に送信するようにするとよい。
【００９８】
（暗号化装置３００における処理）
暗号化装置３００は、暗号化アルゴリズムEncに対応する処理を実行する装置である。暗号化装置３００は、暗号化対象であるm次元ベクトル{xι}ι∈[n]から暗号文{ctι}ι∈[n]を生成する。以下、生成手順について説明する（図９参照）。
【００９９】
ベクトル計算部３１０は、マスター秘密鍵mskを用いて、m次元ベクトル{xι}ι∈[n]から所定の式により2m+2k+1次元ベクトル{cι}ι∈[n]を計算する（Ｓ３１０）。ここで、所定の式とは式(4)のことである。
【０１００】
暗号文生成部３２０は、共通鍵暗号の秘密鍵Kを用いて、Ｓ３１０で計算したベクトル{cι}ι∈[n]から、Cι=SKE.Enc(K, cι) (ι∈[n])を計算し、マスター秘密鍵mskを用いて、暗号文{ctι}ι∈[n]（ただし、ctι=(κι, Cι, ι)）を生成する（Ｓ３２０）。
【０１０１】
復号装置４００は暗号文{ctι}ι∈[n]を取得し、記録部４９０に記録する。取得方法はどのようなものでもよく、例えば、暗号化装置３００が復号装置４００に送信するようにするとよい。
【０１０２】
（復号装置４００における処理）
復号装置４００は、復号アルゴリズムDecに対応する処理を実行する装置である。復号装置４００は、暗号文{ctι}ι∈[n]から関数値f(x1, …, xn)=Σι∈[n]xι・yιを生成する。以下、生成手順について説明する（図１０参照）。
【０１０３】
秘密鍵計算部４１０は、暗号文{ctι}ι∈[n]から、所定の式により共通鍵暗号の秘密鍵K'を計算する（Ｓ４１０）。ここで、所定の式とは式(5)のことである。
【０１０４】
ベクトル復号部４２０は、Ｓ４１０で計算した秘密鍵K'を用いて、復号鍵skと暗号文{ctι}ι∈[n]から、{k'ι}ι∈[n]=SKE.Dec(K', sk)と{c'ι}ι∈[n]（ただし、c'ι=SKE.Dec(K', Cι)）を計算する（Ｓ４２０）。
【０１０５】
双線型写像計算部４３０は、Ｓ４２０で計算した{k'ι}ι∈[n]と{c'ι}ι∈[n]から、所定の式により双線型写像値hTを計算する（Ｓ４３０）。ここで、所定の式とは式(6)のことである。
【０１０６】
関数値生成部４４０は、Ｓ４３０で計算した双線型写像値hTに対してgTz=hTを満たすZpの要素zを関数値f(x1, …, xn)として生成する（Ｓ４４０）。
【０１０７】
本実施形態の発明によれば、関数秘匿性を持つ複数入力内積関数型暗号技術を構成することができる。これにより、クラウドサーバ上での計算を、複数入力内積関数型暗号を用いて実行する際に、どのような計算を行っているのかをサーバから秘匿したまま計算結果を得ることが可能になる。
【０１０８】
＜第二実施形態＞
ここでは、＜技術的背景＞の［引数に制限がない複数入力内積関数型暗号］で説明した内積関数型暗号を実行するシステムである内積関数型暗号システム５０について説明する。
【０１０９】
以下、＜記法・用語＞で説明したように、Zを整数の集合、pを素数、Zp=Z/pZ、SKE=(SKE.Gen, SKE.Enc, SKE.Dec)を共通鍵暗号、~G1, ~G2, ~GTをそれぞれ位数が素数pの巡回群、G1, G2, gTをそれぞれ巡回群~G1, ~G2, ~GTの生成元、e: ~G1×~G2→~GTを非退化双線型写像、~V=~G1m, ~V*=~G2mをそれぞれZp上のm次元ベクトル空間（ただし、mは1以上の整数）、(p, ~G1, ~G2, ~GT, G1, G2, gT, e, ~V, ~V*)を双対ペアリングベクトル空間とする。なお、巡回群~G1, ~G2, ~GTはk-線形仮定を満たす双線型群であるとする。
【０１１０】
［システム構成］
図１１を参照して、内積関数型暗号システム５０について説明する。図１１は、内積関数型暗号システム５０の構成の一例を示すブロック図である。内積関数型暗号システム５０は、システムパラメータ生成装置５００、鍵生成装置６００、暗号化装置７００、復号装置８００を含む。システムパラメータ生成装置５００、鍵生成装置６００、暗号化装置７００、復号装置８００は、インターネットなどのネットワーク９００に接続し、相互に通信可能である。
【０１１１】
次に、図１２〜図１５を参照して、システムパラメータ生成装置５００、鍵生成装置６００、暗号化装置７００、復号装置８００の各装置について説明する。図１２は、システムパラメータ生成装置５００の構成の一例を示すブロック図である。システムパラメータ生成装置５００は、公開パラメータ生成部５１０、マスター秘密鍵生成部５２０、送受信部５８０、記録部５９０を含む。更に、マスター秘密鍵生成部５２０は、正則行列生成部５２１、双対行列計算部５２２、鍵生成部５２３、マスター秘密鍵出力部５２４を含む。送受信部５８０は、システムパラメータ生成装置５００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部５９０は、システムパラメータ生成装置５００の処理に必要な情報を適宜記録する構成部である。例えば、生成した公開パラメータppやマスター秘密鍵mskを記録する。
【０１１２】
図１３は、鍵生成装置６００の構成の一例を示すブロック図である。鍵生成装置６００は、擬似ランダム関数値計算部６１０、行列積計算部６２０、Zp要素生成部６３０、ベクトル計算部６４０、ベクトル暗号化部６５０、復号鍵生成部６６０、送受信部６８０、記録部６９０を含む。送受信部６８０は、鍵生成装置６００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部６９０は、鍵生成装置６００の処理に必要な情報を適宜記録する構成部である。例えば、システムパラメータ生成装置５００から取得した公開パラメータppやマスター秘密鍵mskを記録する。また、生成した復号鍵sksを記録する。
【０１１３】
図１４は、暗号化装置７００の構成の一例を示すブロック図である。暗号化装置７００は、擬似ランダム関数値計算部７１０、行列積計算部７２０、ベクトル計算部７３０、暗号文生成部７４０、送受信部７８０、記録部７９０を含む。送受信部７８０は、暗号化装置７００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部７９０は、暗号化装置７００の処理に必要な情報を適宜記録する構成部である。例えば、システムパラメータ生成装置５００から取得した公開パラメータppやマスター秘密鍵mskを記録する。
【０１１４】
図１５は、復号装置８００の構成の一例を示すブロック図である。復号装置８００は、ベクトル復号部８１０、双線型写像計算部８２０、関数値生成部８３０、送受信部８８０、記録部８９０を含む。送受信部８８０は、復号装置８００がその他の装置と交換する必要がある情報を適宜送受信するための構成部である。記録部８９０は、復号装置８００の処理に必要な情報を適宜記録する構成部である。例えば、システムパラメータ生成装置５００から取得した公開パラメータppを記録する。また、鍵生成装置６００から取得した復号鍵sksを記録する。
【０１１５】
［各装置における処理］
以下、図１６〜図２０を参照して、システムパラメータ生成装置５００、鍵生成装置６００、暗号化装置７００、復号装置８００の各装置における処理について説明する。
【０１１６】
ここで、k、λを1以上の整数とする。また、F1:{0, 1}λ×{0, 1}λ→Zp(2m+2k+1)×(2m+2k+1), F2: {0, 1}λ×{0, 1}λ→{0, 1}λを擬似ランダム関数とする。さらに、S={s1, …, s|S|}を引数のインデックス集合（ただし、siはインデックス集合Sの要素を昇順に並べたときのi番目の要素）、f({xι}ι∈S)=Σι∈Sxι・yιを内積関数（ただし、yι (ι∈S)は内積関数の定義に用いるm次元ベクトル）とする。ただし、インデックス集合Sと内積関数f({xι}ι∈S)については、鍵生成装置６００または暗号化装置７００のいずれかによる処理開始前までに指定するようにすればよい。
【０１１７】
（システムパラメータ生成装置５００における処理）
システムパラメータ生成装置５００は、セットアップアルゴリズムSetupに対応する処理を実行する装置である。システムパラメータ生成装置５００は、公開パラメータppとマスター秘密鍵mskを生成する。以下、生成手順について説明する（図１６参照）。
【０１１８】
公開パラメータ生成部５１０は、公開パラメータppを生成する（Ｓ５１０）。公開パラメータppは、内積関数の定義に用いるベクトルの次元m、巡回群~G1, ~G2, ~GTの記述、巡回群の位数p、非退化双線型写像eの記述、巡回群~G1, ~G2, ~GTの生成元G1, G2, gTである。このとき、e(G1, G2)ν=gT(νはZpの要素)となるようにする。
【０１１９】
マスター秘密鍵生成部５２０は、マスター秘密鍵mskを生成する（Ｓ５２０）。以下、図１７を参照して、具体的に説明する。正則行列生成部５２１は、Zp上の2m+2k+1次元正則行列Dをランダムに生成する（Ｓ５２１）。
【０１２０】
双対行列計算部５２２は、Ｓ５２１で生成した正則行列DからZp上の2m+2k+1次元行列である双対行列D*を計算する（Ｓ５２２）。具体的には、D*=ν(D-1)Tとする。
【０１２１】
鍵生成部５２３は、擬似ランダム関数の鍵K1, K2をλビットのビット列としてランダムに生成する（Ｓ５２３）。
【０１２２】
マスター秘密鍵出力部５２４は、Ｓ５２１で生成した正則行列D、Ｓ５２２で計算した双対行列D*、Ｓ５２３で生成した鍵K1, K2からマスター秘密鍵mskをmsk=(D, D*, K1, K2)として生成、出力する。（Ｓ５２４）。
【０１２３】
鍵生成装置６００、暗号化装置７００は、公開パラメータppとマスター秘密鍵mskを、復号装置８００は公開パラメータppを取得し、それぞれ記録部に記録する。取得方法はどのようなものでもよく、例えば、システムセットアップ装置５００が各装置に送信するようにするとよい。
【０１２４】
（鍵生成装置６００における処理）
鍵生成装置６００は、鍵生成アルゴリズムKeyGenに対応する処理を実行する装置である。鍵生成装置６００は、インデックス集合Sと内積関数の定義に用いるm次元ベクトル{yι}ι∈Sから復号鍵sksを生成する。以下、生成手順について説明する（図１８参照）。
【０１２５】
擬似ランダム関数値計算部６１０は、マスター秘密鍵mskを用いて、擬似ランダム関数値{Wι}ι∈S（ただし、Wι=F1(K1, ι)）, {κι}ι∈S（ただし、κι=F2(K2, ι)）を計算する（Ｓ６１０）。
【０１２６】
行列積計算部６２０は、マスター秘密鍵mskを用いて、Ｓ６１０で計算した擬似ランダム関数値{Wι}ι∈Sから行列積{Bι*}ι∈S（ただし、Bι*=D*(Wι-1)T）を計算する（Ｓ６２０）。
【０１２７】
Zp要素生成部６３０は、{rι}ι∈SをZpから所定の式を満たすようにランダムに生成する（Ｓ６３０）。ここで、所定の式とは式(7)のことである。
【０１２８】
ベクトル計算部６４０は、m次元ベクトル{yι}ι∈Sを用いて、Ｓ６２０で計算した行列積{Bι*}ι∈SとＳ６３０で生成した{rι}ι∈Sから、所定の式により2m+2k+1次元ベクトル{kι}ι∈Sを計算する（Ｓ６４０）。ここで、所定の式とは式(8)のことである。
【０１２９】
ベクトル暗号化部６５０は、Ｓ６１０で計算した擬似ランダム関数値{κι}ι∈SとＳ６４０で計算したベクトル{kι}ι∈Sから所定の式によりC|S|を計算する（Ｓ６５０）。ここで、所定の式とは式(9)のことである。
【０１３０】
復号鍵生成部６６０は、インデックス集合Sを用いて、Ｓ６５０で計算したC|S|から復号鍵sksをskS=(C|S|, S)として生成する（Ｓ６６０）。
【０１３１】
復号装置８００は復号鍵sksを取得し、記録部８９０に記録する。取得方法はどのようなものでもよく、例えば、鍵生成装置６００が復号装置８００に送信するようにするとよい。
【０１３２】
（暗号化装置７００における処理）
暗号化装置７００は、暗号化アルゴリズムEncに対応する処理を実行する装置である。暗号化装置７００は、インデックス集合Sと暗号化対象であるm次元ベクトル{xι}ι∈Sから暗号文{ctι}ι∈Sを生成する。以下、生成手順について説明する（図１９参照）。
【０１３３】
擬似ランダム関数値計算部７１０は、マスター秘密鍵mskを用いて、擬似ランダム関数値{Wι}ι∈S（ただし、Wι=F1(K1, ι)）, {κι}ι∈S（ただし、κι=F2(K2, ι)）を計算する（Ｓ７１０）。
【０１３４】
行列積計算部７２０は、マスター秘密鍵mskを用いて、Ｓ７１０で計算した擬似ランダム関数値{Wι}ι∈Sから行列積{Bι}ι∈S（ただし、Bι=DWι）を計算する（Ｓ７２０）。
【０１３５】
ベクトル計算部７３０は、Ｓ７２０で計算した行列積{Bι}ι∈Sとm次元ベクトル{xι}ι∈Sから所定の式により2m+2k+1次元ベクトル{cι}ι∈Sを計算する（Ｓ７３０）。ここで、所定の式とは式(10)のことである。
【０１３６】
暗号文生成部７４０は、Ｓ７１０で計算した擬似ランダム関数値{κι}ι∈SとＳ７３０で計算したベクトル{cι}ι∈Sから暗号文{ctι}ι∈S（ただし、ctι=(κι, cι, ι)）を生成する（Ｓ７４０）。
【０１３７】
復号装置８００は暗号文{ctι}ι∈Sを取得し、記録部８９０に記録する。取得方法はどのようなものでもよく、例えば、暗号化装置７００が復号装置８００に送信するようにするとよい。
【０１３８】
（復号装置８００における処理）
復号装置８００は、復号アルゴリズムDecに対応する処理を実行する装置である。復号装置８００は、暗号文{ctι}ι∈Sから関数値f({xι}ι∈S)=Σι∈Sxι・yιを生成する。以下、生成手順について説明する（図２０参照）。
【０１３９】
ベクトル復号部８１０は、暗号文{ctι}ι∈Sを用いて、復号鍵sksから所定の式により{k'ι}ι∈Sを計算する（Ｓ８１０）。ここで、所定の式とは式(11)のことである。
【０１４０】
双線型写像計算部８２０は、Ｓ８１０で計算した{k'ι}ι∈S と暗号文{ctι}ι∈Sから、所定の式により双線型写像値hTを計算する（Ｓ８２０）。ここで、所定の式とは式(12)のことである。
【０１４１】
関数値生成部８３０は、Ｓ８２０で計算した双線型写像値hTに対してgTz=hTを満たすZpの要素zを関数値f({xι}ι∈S)として生成する（Ｓ８３０）。
【０１４２】
本実施形態の発明によれば、関数秘匿性を持つ複数入力内積関数型暗号技術を構成することができる。これにより、クラウドサーバ上での計算を、複数入力内積関数型暗号を用いて実行する際に、どのような計算を行っているのかをサーバから秘匿したまま計算結果を得ることが可能になる。また、暗号利用開始時に引数の集合を決める必要がなくなり、暗号化、鍵生成を行う際に引数を自由に設定できるようになるため実用上非常に便利になる。
【０１４３】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１４４】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【０１４５】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【０１４６】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１４７】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０１４８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１４９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１５０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１５１】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2019117232.tif 000033
【図２】
2019117232.tif 000034
【図３】
2019117232.tif 000035
【図４】
2019117232.tif 000036
【図５】
2019117232.tif 000037
【図６】
2019117232.tif 000038
【図７】
2019117232.tif 000039
【図８】
2019117232.tif 000040
【図９】
2019117232.tif 000041
【図１０】
2019117232.tif 000042
【図１１】
2019117232.tif 000043
【図１２】
2019117232.tif 000044
【図１３】
2019117232.tif 000045
【図１４】
2019117232.tif 000046
【図１５】
2019117232.tif 000047
【図１６】
2019117232.tif 000048
【図１７】
2019117232.tif 000049
【図１８】
2019117232.tif 000050
【図１９】
2019117232.tif 000051
【図２０】
2019117232.tif 000052