(57)【要約】【課題】否定表現を含む広い言語表現を扱いつつ、復号時の処理速度を向上する。【解決手段】n→をd次元の属性フォーマットとし、x→,v→をnt次元の属性ベクトルとし、Γを{(t,v→t)}(t=1,…,d)である属性集合とし、ρ(・)を・に対して肯定形の組(t,x→・)もしくは否定形の組¬(t,x→・)であるラベルとし、Sを行列Mとラベルρからなるアクセスストラクチャとする。鍵生成装置１は、属性フォーマットn→を入力とし、公開鍵pkとマスタ秘密鍵skを生成する。鍵生成装置１は、公開鍵pkとマスタ秘密鍵skと属性集合Γを入力とし、秘密鍵skΓを生成する。暗号化装置２は、公開鍵pkと平文mとアクセスストラクチャSを入力とし、暗号文ctを生成する。復号装置３は、公開鍵pkと秘密鍵skΓと暗号文ctを入力とし、平文mを生成する。【選択図】図１
2014095847.tif 000002
【特許請求の範囲】
【請求項１】
鍵生成装置と暗号化装置と復号装置とを含む関数型暗号システムであって、
G,GTを素数位数qの巡回乗法群とし、gを群Gの生成元とし、Fqを位数qの有限体とし、dを正の整数とし、n→:=(n1,…,nd)をd次元の属性フォーマットとし、Vt(t=0,…,d)を有限体Fq上の4nt次元ベクトル空間とし、At(t=0,…,d)を空間Vtの標準基底とし、eをVt×Vt→GTの双線形写像とし、GL(N,Fq)を有限体Fq上のN次元一般線形群とし、x→t,v→t(t=1,…,d)をnt次元の属性ベクトルとし、Γを{(t,v→t)}(t=1,…,d)である属性集合とし、MをL行r列の行列とし、ρ(・)を・に対して肯定形の組(t,x→・)もしくは否定形の組¬(t,x→・)であるラベルとし、Sを行列Mとラベルρからなるアクセスストラクチャとし、X0を一般線形群GL(N,Fq)からランダムに生成した行列とし、Xt(t=1,…,d)を乱数μ*t,i,j,μ’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,nt)を要素に持つ行列とし、1→をすべての要素の値が1であるベクトルとし、e→t,jをj番目の要素が1でその他の要素が0であるnt次元の標準基底ベクトルであるとし、
前記鍵生成装置は、
前記属性フォーマットn→を入力とし、d組の双対ペアリングベクトル空間paramVt:=(q,Vt,GT,At,e)(t=1,…,d)と、乱数Ψと前記生成元gを用いて前記線形写像eにより算出した値gTとから、パラメータparam:=({paramVt},gT)を生成し、t=0,…,dについて、前記行列Xtと前記標準基底Atを用いて基底Btを生成し、前記行列X0と前記標準基底A0を用いて基底B*0を生成し、前記基底Btを用いて基底B^tを生成し、前記基底B*0を用いて基底B^*0を生成し、前記乱数μ*t,i,jと前記生成元gの積である値B*t,i,jを求め、前記乱数μ’*t,i,j,Lと前記生成元gの積である値B’*t,i,j,Lを求め、前記パラメータparamと前記基底B^tを含む公開鍵pkと、前記基底B^*0と前記値B*t,i,jと前記値B’*t,i,j,Lを含むマスタ秘密鍵skとを生成する初期化部と、
前記公開鍵pkと前記マスタ秘密鍵skと前記属性集合Γを入力として、前記基底B0を用いて鍵要素k*0を求め、t=1,…,dについて、前記値B*t,1,jと前記値B*t,3,jとを用いて鍵要素K*t,1,jを求め、前記値B’*t,1,j,Lと前記値B’*t,3,j,Lと前記属性ベクトルv→tとを用いて鍵要素K*t,2,jを求め、前記属性集合Γと前記鍵要素k*0,K*t,1,j,K*k,2,jを含む秘密鍵skΓを生成する鍵生成部と、
を含み、
前記暗号化装置は、
前記公開鍵pkと平文mと前記アクセスストラクチャSを入力とし、r次元の乱数ベクトルf→に基づいて生成された秘密s0と前記基底B0を用いて暗号文要素c0を求め、i=1,…,Lについて、前記ラベルρ(i)が肯定形の組(t,x→i)であれば、前記行列Mと前記乱数ベクトルf→に基づいて生成された分散値siと前記基底Btを用いて暗号文要素ciを求め、前記ラベルρ(i)が否定形の組¬(t,x→i)であれば、前記標準基底ベクトルe→t,1と前記分散値siと前記基底Btを用いて前記暗号文要素ciを求め、前記平文mと前記値gTと乱数ζとを用いて暗号文要素cd+1:=gTζ*mを計算し、前記アクセスストラクチャSと前記暗号文要素c0,…,cL,cd+1を含む暗号文ctを生成する暗号化部
を含み、
前記復号装置は、
前記公開鍵pkと前記秘密鍵skΓと前記暗号文ctを入力とし、前記属性集合Γと前記ラベルρ(i)とに基づいて、i=1,…,Lのうち、前記ラベルρ(i)が肯定形の組(t,x→i)でありx→iとv→tの内積が0であるiと、前記ラベルρ(i)が否定形の組¬(t,x→i)でありx→iとv→tの内積が0でないiとを含む集合Iを求め、i∈Iについて、前記行列Mのi行目と掛け合わせた総和が1→となる係数αiを求め、前記暗号文要素ciを値Ci,1,…,Ci,4niに分解した上で、次の式を計算して値Fを求め、
【数５４】
2014095847.tif 000056
前記暗号文要素cd+1と前記値Fとを用いて前記平文m:=cd+1/Fを計算する復号部
を含む
ことを特徴とする関数型暗号システム。
【請求項２】
請求項１に記載の関数型暗号システムであって、
前記鍵生成部は、乱数δ,ψ0と前記基底B0とを用いて、以下の式に従って前記鍵要素k*0を求め、
【数５５】
2014095847.tif 000057
乱数δ,ψtと前記値B*t,i,jとを用いて、以下の式に従って前記鍵要素K*t,1,jを求め、
【数５６】
2014095847.tif 000058
前記属性ベクトルv→tと前記値B’*t,i,j,Lとを用いて、以下の式に従って前記鍵要素K*t,2,jを求め、
【数５７】
2014095847.tif 000059
前記暗号化部は、前記秘密s0と乱数ζ,η0と前記基底B0とを用いて、以下の式に従って前記暗号文要素c0を求め、
【数５８】
2014095847.tif 000060
i=1,…,Lについて、前記ラベルρ(i)が肯定形の組(t,x→i)であれば、前記標準基底ベクトルe→t,1と前記分散値siと乱数τiとnt次元の乱数ベクトルη→iと前記基底Btとを用いて、以下の式に従って前記暗号文要素ci求め、
【数５９】
2014095847.tif 000061
前記ラベルρ(i)が否定形の組¬(t,x→i)であれば、前記属性ベクトルx→iと前記分散値siと前記乱数ベクトルη→iと前記基底Btとを用いて、以下の式に従って前記暗号文要素ci求める
【数６０】
2014095847.tif 000062
ことを特徴とする関数型暗号システム。
【請求項３】
G,GTを素数位数qの巡回乗法群とし、gを群Gの生成元とし、Fqを位数qの有限体とし、dを正の整数とし、n→:=(n1,…,nd)をd次元の属性フォーマットとし、Vt(t=0,…,d)を有限体Fq上の4nt次元ベクトル空間とし、At(t=0,…,d)を空間Vtの標準基底とし、eをVt×Vt→GTの双線形写像とし、GL(N,Fq)を有限体Fq上のN次元一般線形群とし、x→t,v→t(t=1,…,d)をnt次元の属性ベクトルとし、Γを{(t,v→t)}(t=1,…,d)である属性集合とし、X0を一般線形群GL(N,Fq)からランダムに生成した行列とし、Xt(t=1,…,d)を乱数μ*t,i,j,μ’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,nt)を要素に持つ行列とし、
前記属性フォーマットn→を入力とし、d組の双対ペアリングベクトル空間paramVt:=(q,Vt,GT,At,e)(t=1,…,d)と、乱数Ψと前記生成元gを用いて前記線形写像eにより算出した値gTとから、パラメータparam:=({paramVt},gT)を生成し、t=0,…,dについて、前記行列Xtと前記標準基底Atを用いて基底Btを生成し、前記行列X0と前記標準基底A0を用いて基底B*0を生成し、前記基底Btを用いて基底B^tを生成し、前記基底B*0を用いて基底B^*0を生成し、前記乱数μ*t,i,jと前記生成元gの積である値B*t,i,jを求め、前記乱数μ’*t,i,j,Lと前記生成元gの積である値B’*t,i,j,Lを求め、前記パラメータparamと前記基底B^tを含む公開鍵pkと、前記基底B^*0と前記値B*t,i,jと前記値B’*t,i,j,Lを含むマスタ秘密鍵skとを生成する初期化部と、
前記公開鍵pkと前記マスタ秘密鍵skと前記属性集合Γを入力として、前記基底B0を用いて鍵要素k*0を求め、t=1,…,dについて、前記値B*t,1,jと前記値B*t,3,jとを用いて鍵要素K*t,1,jを求め、前記値B’*t,1,j,Lと前記値B’*t,3,j,Lと前記属性ベクトルv→tとを用いて鍵要素K*t,2,jを求め、前記属性集合Γと前記鍵要素k*0,K*t,1,j,K*k,2,jを含む秘密鍵skΓを生成する鍵生成部と、
を含む鍵生成装置。
【請求項４】
G,GTを素数位数qの巡回乗法群とし、gを群Gの生成元とし、Fqを位数qの有限体とし、dを正の整数とし、n→:=(n1,…,nd)をd次元の属性フォーマットとし、Vt(t=0,…,d)を有限体Fq上の4nt次元ベクトル空間とし、At(t=0,…,d)を空間Vtの標準基底とし、eをVt×Vt→GTの双線形写像とし、GL(N,Fq)を有限体Fq上のN次元一般線形群とし、x→t,v→t(t=1,…,d)をnt次元の属性ベクトルとし、MをL行r列の行列とし、ρ(・)を・に対して肯定形の組(t,x→・)もしくは否定形の組¬(t,x→・)であるラベルとし、Sを行列Mとラベルρからなるアクセスストラクチャとし、X0を一般線形群GL(N,Fq)からランダムに生成した行列とし、Xt(t=1,…,d)を乱数μ*t,i,j,μ’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,nt)を要素に持つ行列とし、e→t,jをj番目の要素が1でその他の要素が0であるnt次元の標準基底ベクトルであるとし、
公開鍵pkは、d組の双対ペアリングベクトル空間paramVt:=(q,Vt,GT,At,e)(t=1,…,d)と、乱数Ψと前記生成元gを用いて前記線形写像eにより算出した値gTとから生成したパラメータparam:=({paramVt},gT)と、t=0,…,dについて、前記行列Xtと前記標準基底Atを用いて生成した基底Btを用いて生成した基底B^tを含むとし、
前記公開鍵pkと平文mと前記アクセスストラクチャSを入力とし、r次元の乱数ベクトルf→に基づいて生成された秘密s0と前記基底B0を用いて暗号文要素c0を求め、i=1,…,Lについて、前記ラベルρ(i)が肯定形の組(t,x→i)であれば、前記行列Mと前記乱数ベクトルf→に基づいて生成された分散値siと前記基底Btを用いて暗号文要素ciを求め、前記ラベルρ(i)が否定形の組¬(t,x→i)であれば、前記標準基底ベクトルe→t,1と前記分散値siと前記基底Btを用いて前記暗号文要素ciを求め、前記平文mと前記値gTと乱数ζとを用いて暗号文要素cd+1:=gTζ*mを計算し、前記アクセスストラクチャSと前記暗号文要素c0,…,cL,cd+1を含む暗号文ctを生成する暗号化部
を含む暗号化装置。
【請求項５】
G,GTを素数位数qの巡回乗法群とし、gを群Gの生成元とし、Fqを位数qの有限体とし、dを正の整数とし、n→:=(n1,…,nd)をd次元の属性フォーマットとし、Vt(t=0,…,d)を有限体Fq上の4nt次元ベクトル空間とし、At(t=0,…,d)を空間Vtの標準基底とし、eをVt×Vt→GTの双線形写像とし、GL(N,Fq)を有限体Fq上のN次元一般線形群とし、x→t,v→t(t=1,…,d)をnt次元の属性ベクトルとし、Γを{(t,v→t)}(t=1,…,d)である属性集合とし、MをL行r列の行列とし、ρ(・)を・に対して肯定形の組(t,x→・)もしくは否定形の組¬(t,x→・)であるラベルとし、Sを行列Mとラベルρからなるアクセスストラクチャとし、X0を一般線形群GL(N,Fq)からランダムに生成した行列とし、Xt(t=1,…,d)を乱数μ*t,i,j,μ’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,nt)を要素に持つ行列とし、1→をすべての要素の値が1であるベクトルとし、e→t,jをj番目の要素が1でその他の要素が0であるnt次元の標準基底ベクトルであるとし、
公開鍵pkは、d組の双対ペアリングベクトル空間paramVt:=(q,Vt,GT,At,e)(t=1,…,d)と、乱数Ψと前記生成元gを用いて前記線形写像eにより算出した値gTとから生成したパラメータparam:=({paramVt},gT)と、t=0,…,dについて、前記行列Xtと前記標準基底Atを用いて生成した基底Btを用いて生成した基底B^tを含み、
秘密鍵skΓは、前記属性集合Γと、基底B0を用いて求めた鍵要素k*0と、値B*t,1,jと値B*t,3,jとを用いて求めた鍵要素K*t,1,jと、値B’*t,1,j,Lと値B’*t,3,j,Lと前記属性ベクトルv→tとを用いて求めた鍵要素K*k,2,jとを含み、
前記基底B0は、前記行列X0と前記標準基底A0を用いて生成し、
前記値B*t,1,j,B*t,3,jは、前記乱数μ*t,1,jと前記生成元gの積であり、
前記値B’*t,1,j,L,B’*t,3,j,Lは、前記乱数μ*t,1,jと前記生成元gの積であり、
暗号文ctは、前記アクセスストラクチャSと、r次元の乱数ベクトルf→に基づいて生成された秘密s0と前記基底B0を用いて求めた暗号文要素c0と、暗号文要素c1,…,cLと、前記平文mと前記値gTと乱数ζとを用いて計算した暗号文要素cd+1:=gTζ*mとを含み、
前記暗号文要素c1,…,cLは、i=1,…,Lについて、前記ラベルρ(i)が肯定形の組(t,x→i)であれば、前記行列Mと前記乱数ベクトルf→に基づいて生成された分散値siと前記基底Btを用いて求められ、前記ラベルρ(i)が否定形の組¬(t,x→i)であれば、前記標準基底ベクトルe→t,1と前記分散値siと前記基底Btを用いて求められるとし、
前記公開鍵pkと前記秘密鍵skΓと前記暗号文ctを入力とし、前記属性集合Γと前記ラベルρ(i)とに基づいて、i=1,…,Lのうち、前記ラベルρ(i)が肯定形の組(t,x→i)でありx→iとv→tの内積が0であるiと、前記ラベルρ(i)が否定形の組¬(t,x→i)でありx→iとv→tの内積が0でないiとを含む集合Iを求め、i∈Iについて、前記行列Mのi行目と掛け合わせた総和が1→となる係数αiを求め、前記暗号文ctに含まれる暗号文要素ciを値Ci,1,…,Ci,4niに分解した上で、次の式を計算して値Fを求め、
【数６１】
2014095847.tif 000063
前記暗号文ctに含まれる暗号文要素cd+1と前記値Fとを用いて平文m:=cd+1/Fを計算する復号部
を含む復号装置。
【請求項６】
G,GTを素数位数qの巡回乗法群とし、gを群Gの生成元とし、Fqを位数qの有限体とし、dを正の整数とし、n→:=(n1,…,nd)をd次元の属性フォーマットとし、Vt(t=0,…,d)を有限体Fq上の4nt次元ベクトル空間とし、At(t=0,…,d)を空間Vtの標準基底とし、eをVt×Vt→GTの双線形写像とし、GL(N,Fq)を有限体Fq上のN次元一般線形群とし、x→t,v→t(t=1,…,d)をnt次元の属性ベクトルとし、Γを{(t,v→t)}(t=1,…,d)である属性集合とし、MをL行r列の行列とし、ρ(・)を・に対して肯定形の組(t,x→・)もしくは否定形の組¬(t,x→・)であるラベルとし、Sを行列Mとラベルρからなるアクセスストラクチャとし、X0を一般線形群GL(N,Fq)からランダムに生成した行列とし、Xt(t=1,…,d)を乱数μ*t,i,j,μ’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,nt)を要素に持つ行列とし、1→をすべての要素の値が1であるベクトルとし、e→t,jをj番目の要素が1でその他の要素が0であるnt次元の標準基底ベクトルであるとし、
鍵生成装置が、前記属性フォーマットn→を入力とし、d組の双対ペアリングベクトル空間paramVt:=(q,Vt,GT,At,e)(t=1,…,d)と、乱数Ψと前記生成元gを用いて前記線形写像eにより算出した値gTとから、パラメータparam:=({paramVt},gT)を生成し、t=0,…,dについて、前記行列Xtと前記標準基底Atを用いて基底Btを生成し、前記行列X0と前記標準基底A0を用いて基底B*0を生成し、前記基底Btを用いて基底B^tを生成し、前記基底B*0を用いて基底B^*0を生成し、前記乱数μ*t,i,jと前記生成元gの積である値B*t,i,jを求め、前記乱数μ’*t,i,j,Lと前記生成元gの積である値B’*t,i,j,Lを求め、前記パラメータparamと前記基底B^tを含む公開鍵pkと、前記基底B^*0と前記値B*t,i,jと前記値B’*t,i,j,Lを含むマスタ秘密鍵skとを生成する初期化ステップと、
前記鍵生成装置が、前記公開鍵pkと前記マスタ秘密鍵skと前記属性集合Γを入力として、前記基底B0を用いて鍵要素k*0を求め、t=1,…,dについて、前記値B*t,1,jと前記値B*t,3,jとを用いて鍵要素K*t,1,jを求め、前記値B’*t,1,j,Lと前記値B’*t,3,j,Lと前記属性ベクトルv→tとを用いて鍵要素K*t,2,jを求め、前記属性集合Γと前記鍵要素k*0,K*t,1,j,K*k,2,jを含む秘密鍵skΓを生成する鍵生成ステップと、
暗号化装置が、前記公開鍵pkと平文mと前記アクセスストラクチャSを入力とし、r次元の乱数ベクトルf→に基づいて生成された秘密s0と前記基底B0を用いて暗号文要素c0を求め、i=1,…,Lについて、前記ラベルρ(i)が肯定形の組(t,x→i)であれば、前記行列Mと前記乱数ベクトルf→に基づいて生成された分散値siと前記基底Btを用いて暗号文要素ciを求め、前記ラベルρ(i)が否定形の組¬(t,x→i)であれば、前記標準基底ベクトルe→t,1と前記分散値siと前記基底Btを用いて前記暗号文要素ciを求め、前記平文mと前記値gTと乱数ζとを用いて暗号文要素cd+1:=gTζ*mを計算し、前記アクセスストラクチャSと前記暗号文要素c0,…,cL,cd+1を含む暗号文ctを生成する暗号化ステップと、
復号装置が、前記公開鍵pkと前記秘密鍵skΓと前記暗号文ctを入力とし、前記属性集合Γと前記ラベルρ(i)とに基づいて、i=1,…,Lのうち、前記ラベルρ(i)が肯定形の組(t,x→i)でありx→iとv→tの内積が0であるiと、前記ラベルρ(i)が否定形の組¬(t,x→i)でありx→iとv→tの内積が0でないiとを含む集合Iを求め、i∈Iについて、前記行列Mのi行目と掛け合わせた総和が1→となる係数αiを求め、前記暗号文要素ciを値Ci,1,…,Ci,4niに分解した上で、次の式を計算して値Fを求め、
【数６２】
2014095847.tif 000064
前記暗号文要素cd+1と前記値Fとを用いて前記平文m:=cd+1/Fを計算する復号ステップと、
を含む関数型暗号方法。
【請求項７】
請求項３に記載の鍵生成装置、請求項４に記載の暗号化装置、請求項５に記載の復号装置のいずれかとしてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報通信分野における暗号技術に関し、特に関数型暗号技術に関する。
【背景技術】
【０００２】
現在最も広い言語表現を扱うことのできる関数型暗号方式が非特許文献１に記載されている。また、暗号文長や秘密鍵長の短い内積暗号方式が非特許文献２に記載されている。
【０００３】
非特許文献２に記載された内積暗号方式では、従来の内積暗号方式と比較して、暗号化処理や鍵生成処理の演算量が増加するが、復号時のペアリング演算を楕円曲線上のスカラ倍算で置き換えており復号処理の高速化が図られている。ペアリング演算の処理速度はパラメータの定義により変動し、必ずしもペアリング演算よりもスカラ倍算の方が高速であるわけではないが、暗号分野で利用する場合にはペアリング演算よりもスカラ倍算の方が早いケースが多いためである。暗号方式の実装によっては、復号処理のみを行い暗号化処理や鍵生成処理を行わない計算機が存在し得るため、暗号方式全体として高速化していなくとも、復号処理のみを高速化するメリットがある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Tatsuaki Okamoto and Katsuyuki Takashima, “Fully secure functional encryption with general relations from the decisional linear assumption”, CRYPTO 2010, pp. 191-208.
【非特許文献２】Tatsuaki Okamoto and Katsuyuki Takashima, “Achieving short ciphertexts or short secret-keys for adaptively secure general inner-product encryption”, CANS 2011, pp.138-159.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載された関数型暗号方式では、復号時のペアリング演算の回数が多く、特に携帯電話等の計算リソースの少ない計算機では、実用的な時間で復号できないという問題がある。
【０００６】
非特許文献２に記載された内積暗号方式では、非特許文献１に記載された関数型暗号方式よりも復号時のペアリング演算の回数が少ないが、扱うことのできる言語表現が狭く、特に否定表現を実用的な時間で扱うことが難しいという問題がある。
【０００７】
この発明の目的は、否定表現を含む広い言語表現を扱うことができ、復号時の処理速度が向上した関数型暗号技術を提供することである。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、この発明の関数型暗号システムは、鍵生成装置と暗号化装置と復号装置とを含む。この発明では、G,GTを素数位数qの巡回乗法群とし、gを群Gの生成元とし、Fqを位数qの有限体とし、dを正の整数とし、n→:=(n1,…,nd)をd次元の属性フォーマットとし、Vt(t=0,…,d)を有限体Fq上の4nt次元ベクトル空間とし、At(t=0,…,d)を空間Vtの標準基底とし、eをVt×Vt→GTの双線形写像とし、GL(N,Fq)を有限体Fq上のN次元一般線形群とし、x→t,v→t(t=1,…,d)をnt次元の属性ベクトルとし、Γを{(t,v→t)}(t=1,…,d)である属性集合とし、MをL行r列の行列とし、ρ(・)を・に対して肯定形の組(t,x→・)もしくは否定形の組¬(t,x→・)であるラベルとし、Sを行列Mとラベルρからなるアクセスストラクチャとし、X0を一般線形群GL(N,Fq)からランダムに生成した行列とし、Xt(t=1,…,d)を乱数μ*t,i,j,μ’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,nt)を要素に持つ行列とし、1→をすべての要素の値が1であるベクトルとし、e→t,jをj番目の要素が1でその他の要素が0であるnt次元の標準基底ベクトルであるとする。
【０００９】
鍵生成装置は、属性フォーマットn→を入力とし、d組の双対ペアリングベクトル空間paramVt:=(q,Vt,GT,At,e)(t=1,…,d)と、乱数Ψと生成元gを用いて線形写像eにより算出した値gTとから、パラメータparam:=({paramVt},gT)を生成し、t=0,…,dについて、行列Xtと標準基底Atを用いて基底Btを生成し、行列X0と標準基底A0を用いて基底B*0を生成し、基底Btを用いて基底B^tを生成し、基底B*0を用いて基底B^*0を生成し、乱数μ*t,i,jと生成元gの積である値B*t,i,jを求め、乱数μ’*t,i,j,Lと生成元gの積である値B’*t,i,j,Lを求め、パラメータparamと基底B^tを含む公開鍵pkと、基底B^*0と値B*t,i,jと値B’*t,i,j,Lを含むマスタ秘密鍵skとを生成する初期化部と、公開鍵pkとマスタ秘密鍵skと属性集合Γを入力として、基底B0を用いて鍵要素k*0を求め、t=1,…,dについて、値B*t,1,jと値B*t,3,jとを用いて鍵要素K*t,1,jを求め、値B’*t,1,j,Lと値B’*t,3,j,Lと属性ベクトルv→tとを用いて鍵要素K*t,2,jを求め、属性集合Γと鍵要素k*0,K*t,1,j,K*k,2,jを含む秘密鍵skΓを生成する鍵生成部と、を含む。
【００１０】
暗号化装置は、公開鍵pkと平文mとアクセスストラクチャSを入力とし、r次元の乱数ベクトルf→に基づいて生成された秘密s0と基底B0を用いて暗号文要素c0を求め、i=1,…,Lについて、ラベルρ(i)が肯定形の組(t,x→i)であれば、行列Mと乱数ベクトルf→に基づいて生成された分散値siと基底Btを用いて暗号文要素ciを求め、ラベルρ(i)が否定形の組¬(t,x→i)であれば、標準基底ベクトルe→t,1と分散値siと基底Btを用いて暗号文要素ciを求め、平文mと値gTと乱数ζとを用いて暗号文要素cd+1:=gTζ*mを計算し、アクセスストラクチャSと暗号文要素c0,…,cL,cd+1を含む暗号文ctを生成する暗号化部を含む。
【００１１】
復号装置は、公開鍵pkと秘密鍵skΓと暗号文ctを入力とし、属性集合Γとラベルρ(i)とに基づいて、i=1,…,Lのうち、ラベルρ(i)が肯定形の組(t,x→i)でありx→iとv→tの内積が0であるiと、ラベルρ(i)が否定形の組¬(t,x→i)でありx→iとv→tの内積が0でないiとを含む集合Iを求め、i∈Iについて、行列Mのi行目と掛け合わせた総和が1→となる係数αiを求め、暗号文要素ciを値Ci,1,…,Ci,4niに分解した上で、次の式を計算して値Fを求め、
【００１２】
【数１】
2014095847.tif 000003
【００１３】
暗号文要素cd+1と値Fとを用いて平文m:=cd+1/Fを計算する復号部を含む。
【発明の効果】
【００１４】
この発明の関数型暗号技術によれば、否定表現を含む広い言語表現を扱うことができる。また、従来よりも復号時に実行するペアリング演算の回数が減少しているため、復号の処理速度が向上する。
【図面の簡単な説明】
【００１５】
【図１】関数型暗号システムの機能構成を例示する図。
【図２】鍵生成装置の機能構成を例示する図。
【図３】暗号化装置の機能構成を例示する図。
【図４】復号装置の機能構成を例示する図。
【図５】鍵生成処理の処理フローを例示する図。
【図６】暗号化処理の処理フローを例示する図。
【図７】復号処理の処理フローを例示する図。
【発明を実施するための形態】
【００１６】
実施形態の説明に先立ち、この明細書で用いる表記方法および用語を定義し、従来技術の概要およびこの発明の概要を説明する。
［表記方法］
【００１７】
【数２】
2014095847.tif 000004
【００１８】
は、ある値a,bについて、aにbを代入する、またはaをbで定義することを表す。
【００１９】
【数３】
2014095847.tif 000005
【００２０】
は、ある有限集合Sについて、集合Sから要素rを一様ランダムに選ぶことを表す。
【００２１】
【数４】
2014095847.tif 000006
【００２２】
は、ある確率的多項式時間アルゴリズムAについて、アルゴリズムAがxを入力にとり、乱数を生成して動作し、aを出力することを表す。
【００２３】
(・)Tは、・の転置行列を表す。(・)-1は、・の逆行列を表す。
【００２４】
∧は論理積（ＡＮＤ）を表す論理記号である。∨は論理和（ＯＲ）を表す論理記号である。¬は否定（ＮＯＴ）を表す論理記号である。
【００２５】
Fqは素数qを位数とする有限体である。Fq×は有限体Fqの乗法群である。
【００２６】
Zは整数集合を表す。λはセキュリティパラメータであり、λ∈Zかつλ>0である。
【００２７】
【数５】
2014095847.tif 000007
【００２８】
は、有限体Fq上のベクトル表現を表す。x→（上付き文字の→）も同様である。つまり、x→は(x1,…,xn)∈Fqを表す。
【００２９】
【数６】
2014095847.tif 000008
【００３０】
は、x→とv→の内積を表す。すなわち、x→:=(x1,…,xn)、v→:=(v1,…,vn)であるとして、
【００３１】
【数７】
2014095847.tif 000009
【００３２】
である。
bi(i=1,…,n)が空間Vのベクトルの要素であるとき、すなわちbi∈V(i=1,…,n)のとき、span<b1,…,bn>⊆Vは、b1,…,bnによって生成される部分空間である。
【００３３】
基底B:=(b1,…,bN)と基底B*:=(b*1,…,b*N)に対し、
【００３４】
【数８】
2014095847.tif 000010
【００３５】
である。
標準基底ベクトルe→j(j=1,…,n)は
【００３６】
【数９】
2014095847.tif 000011
【００３７】
である。
［双線形写像］
双線形写像とは、楕円曲線上の二点に定義されるペアリング演算を行うための関数である。G×G→GTの双線形写像eは以下の性質を満たす。
＜双線型性＞任意のg,h∈Gおよび任意のa,b∈Fqに対して、e(ag,bh)=e(g,h)abが成立する。
＜非退化性＞e(g,g)≠1を満たすgが存在する。つまり、もしgがGの生成元ならe(g,g)はGTの生成元である。
＜計算可能性＞任意のg,h∈Gに対して、e(g,h)を多項式時間で計算可能である。
【００３８】
双線形写像の具体例としては、例えば、WeilペアリングやTateペアリングなどが考えられる。ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMillerのアルゴリズムなどが存在する。詳しくは「D. Boneh and M. K. Franklin. “Identity-Based Encryption from the Weil Pairing.”, In CRYPTO’01,volume 2139 of Lecture Notes in Computer Science, pages 213-229. Springer, 2001.」や「D. Moriyama, R. Nishimaki, and T. Okamoto. “公開鍵暗号の数理” 共立出版, 2011.」および「黒澤馨, “現代暗号への招待”, サイエンス社」を参照されたい。
【００３９】
［対称ペアリング群(Symmetric bilinear pairing groups)］
対称ペアリング群(q,g,G,GT,e)は、素数q、位数qの巡回加法群G、位数qの巡回乗法群GT、群Gの生成元g、およびV×V→GTである双線形写像eの組である。双線形写像eは、e(sg,tg)=e(g,g)st、かつe(g,g)≠1である。対称ペアリング群生成アルゴリズムGbpgは1λを入力として、対称ペアリング群(q,g,G,GT,e)を出力する。
【００４０】
［双対ペアリングベクトル空間(Dual Pairing Vector Space, DPVS)］
対称ペアリング群(q,g,G,GT,e)による双対ペアリングベクトル空間(q,V,GT,A,e)とは、素数q、有限体Fq上のN次元ベクトル空間V、位数qの巡回群GT、N次元ベクトル空間Vの標準基底A、およびV×V→GTである双線形写像eの組である。
【００４１】
N次元ベクトル空間Vは以下の式で定義される。
【００４２】
【数１０】
2014095847.tif 000012
【００４３】
N次元ベクトル空間Vの標準基底Aは以下の式で定義される。
【００４４】
【数１１】
2014095847.tif 000013
【００４５】
双線形写像eは以下の式で定義される。
【００４６】
【数１２】
2014095847.tif 000014
【００４７】
これは非退化双線形である。つまり、e(sx,ty)=e(x,y)st、かつ、もしすべてのy∈Vに対しe(x,y)=1ならばx=0である。すべてのiおよびjに対しe(ai,aj)=e(G,G)δi,jである。ただし、i=jならδi,j=1、そうでなければδi,j=0である。またe(G,G)≠1∈GTである。
【００４８】
双対ペアリングベクトル空間は、空間V上の線形変換φi,jを持つ。φi,j(aj)=aiかつφi,j(ak)(k≠j)である線形変換φi,jは以下の式により容易に実現できる。以下、線形変換φi,jをディストーション写像と呼ぶ。
【００４９】
【数１３】
2014095847.tif 000015
【００５０】
双対ペアリングベクトル空間生成アルゴリズムGdpvsは、1λと空間Vの次元数である自然数Nを入力として、ベクトル空間パラメータparamV:=(q,V,GT,A,e)を得る。双対ペアリングベクトル空間生成アルゴリズムGdpvsは対称ペアリング群生成アルゴリズムGbpgを使用して構成することができる。
【００５１】
非対称双対ペアリングベクトル空間(q,V,V*,GT,A,A*,e)については、非特許文献１を参照されたい。対称双対ペアリングベクトル空間(q,V,GT,A,e)は、非対称双対ペアリングベクトル空間(q,V,V*,GT,A,A*,e)において、V=V*としA=A*とすれば構成できる。
【００５２】
［関数型暗号方式］
関数型暗号方式は、暗号化鍵と復号鍵との間の関係をより高度化し、より柔軟にした暗号方式である。
【００５３】
関数型暗号方式において、暗号化鍵ekと復号鍵dkとは、それぞれ属性xと属性vとが設定されている。そして、関係Rに対してR(x,v)が成立する場合に限り、復号鍵dkは暗号化鍵ekで暗号化された暗号文ctを復号することができる。
【００５４】
Rが等号関係である場合、つまりx=vである場合に限りR(x,v)が成立する場合、関数型暗号方式はIDベース暗号方式(Identity Based Encryption, IBE)である。
【００５５】
IDベース暗号方式よりも一般化された関数型暗号方式として、属性ベース暗号方式(Attribute Based Encryption, ABE)がある。属性ベース暗号方式では、暗号化鍵ekと復号鍵dkとに設定される属性x,vが属性の組である。例えば、暗号化鍵ekと復号鍵dkとに設定される属性が、それぞれx:=(x1,…,xd)とv:=(v1,…,vd)とである。そして、属性のコンポーネントについて、コンポーネント毎の等号関係（例えば、{xt=vt}t∈{1,…,d}）がアクセスストラクチャSに入力される。そして、アクセスストラクチャSが入力を受理した場合にのみ、R(x,v)が成立する。つまり、暗号化鍵ekで暗号化された暗号文ctを復号鍵dkで復号することができる。
【００５６】
アクセスストラクチャSが復号鍵dkに埋め込まれている場合、属性ベース暗号方式は、Key-Policy ABE(KP-ABE)と呼ばれる。一方、アクセスストラクチャSが暗号文ctに埋め込まれている場合、属性ベース暗号方式は、Ciphertext-Policy ABE(CP-ABE)と呼ばれる。
【００５７】
内積述語暗号(Inner-Product Encryption, IPE)も関数型暗号の１つのクラスである。ここでは、暗号化鍵ekと復号鍵dkとに設定される属性がそれぞれ体又は環上のベクトルである。例えば、x→:=(x1,…,xn)∈Fqnとv→:=(v1,…,vn)∈Fqnとがそれぞれ暗号化鍵ekと復号鍵dkとに設定される。そして、x→・v→=0である場合に限り、R(x→,v→)が成立する。
【００５８】
［スパンプログラム］
{p1,…,pn}を変数の集合とする。有限体Fq上のスパンプログラムは、ラベル付けされた行列M^:=(M,ρ)である。Mは有限体Fq上のL行r列の行列であり、ρは行列Mの各行をリテラル{p1,…,pn,¬p1,…,¬pn}によりラベル付けする。なお、行列Mのすべての行はいずれかのリテラルでラベル付けされる。すなわち、ρ:{1,…,L}→{p1,…,pn,¬p1,…,¬pn}である。
【００５９】
すべての入力列δ∈{0,1}nについて、行列Mの部分行列Mδが定義される。部分行列Mδは入力列δに対応してラベルに“1”が設定された行列Mの行から構成される。すなわち、部分行列Mδはδi=1であるような変数piでラベル付けされた行、もしくはδi=0であるような変数¬piでラベル付けされた行のいずれかから構成される。すなわち、γ:{1,…,L}→{0,1}は、[p(j)=pi]∧[δi=1]∨[p(j)=¬pi]∧[δi=0]の場合、γ(j)=1であり、その他の場合、γ(j)=0である。Mjを行列Mのj番目の行として、Mδ:=(Mj)γ(j)=1である。
【００６０】
スパンプログラムM^は1→∈span<Mδ>である場合のみ、入力列δを受理する。すなわち、部分行列Mδの行の線形結合が1→である場合のみ、入力列δを受理する。ただし、1→は、各要素の値が“1”である行ベクトルである。スパンプログラムはブール関数fを実行し、f(δ)=1のときに入力列δを受理する。
【００６１】
スパンプログラムは、行ラベルが肯定的なリテラル{p1,…,pn}のみである場合、モノトーンと呼ばれる。モノトーンスパンプログラムは、モノトーン関数を計算する。行ラベルがすべてのリテラル{p1,…,pn,¬p1,…,¬pn}を含む一般的なスパンプログラムは、非モノトーンと呼ばれる。
【００６２】
この発明では、行列Mは、i=1,…,Lについて、Mi≠0→であることを前提とする。この発明の関数型暗号方式では、属性ベクトルの内積を用いて写像γを評価する非モノトーンアクセスストラクチャを用いる。
【００６３】
［属性ベクトルの内積とアクセスストラクチャ］
非特許文献１によれば、Ut(t=1,…,d;Ut⊂{0,1}*)は、部分全集合であり、属性の集合である。各Utは、部分全集合の識別情報tと、nt次元ベクトルv→とを含む。すなわち、Ut:=(t,v→)である。ここで、t∈{1,…,d}であり、v→∈Fqntである。
【００６４】
部分全集合Ut:=(t,v→)をスパンプログラムM^:=(M,ρ)における変数pとする。つまり、p:=(t,v→)である。アクセスストラクチャSを、変数p:=(t,v→),p’:=(t’,v’→),…としたスパンプログラムM^:=(M,ρ)とする。すなわち、アクセスストラクチャS:=(M,ρ)であり、ρ:{1,…,L}→{(t,v→),(t’,v’→),…,¬(t,v→),¬(t’,v’→),…}である。
【００６５】
Γは属性集合である。すなわち、Γ:={(t,x→t)|x→t∈Fqnt,1≦t≦d}である。ここで、1≦t≦dは、tが{1,…,d}の一部であることを意味している。
【００６６】
属性集合ΓがアクセスストラクチャSに与えられる場合、スパンプログラムM^:=(M,ρ)に対する写像γ:{1,…,L}→{0,1}は以下のように定義される。i=1,…,Lについて、[ρ(i)=(t,v→i)]∧[(t,x→t)∈Γ]∧[v→i・x→t=0]であるとき、もしくは[ρ(i)=¬(t,v→i)]∧[(t,x→t)∈Γ]∧[v→i・x→t≠0]であるとき、γ(i)=1を設定する。その他の場合には、γ(i)=0を設定する。アクセスストラクチャS:=(M,ρ)は、1→∈span<(Mi)γ(i)=1>であれば、Γを受理する。
【００６７】
［秘密分散方式］
スパンプログラムM^:=(M,ρ)の秘密分散方式は以下の通りである。
【００６８】
MをL行r列の行列とする。f→Tを以下の式で定義される列ベクトルとする。
【００６９】
【数１４】
2014095847.tif 000016
【００７０】
s0は共有すべき秘密であり、以下の式で定義される。
【００７１】
【数１５】
2014095847.tif 000017
【００７２】
s→Tは秘密s0のL個の分散値からなるベクトルであり、以下の式で定義される。なお、分散値siはρ(i)に属する。
【００７３】
【数１６】
2014095847.tif 000018
【００７４】
スパンプログラムM^:=(M,ρ)がδを受理する場合、もしくはアクセスストラクチャS:=(M,ρ)がΓを受理する場合、すなわち、γ:{1,…,L}→{0,1}として1→∈span<(Mi)γ(i)=1>である場合、以下の式で定義される定数{αi∈Fq|i∈I}が存在する。ただし、I⊆{i∈{1,…,L}|γ(i)=1}である。
【００７５】
【数１７】
2014095847.tif 000019
【００７６】
なお、定数{αi}は行列Mの大きさの多項式時間で計算可能である。
【００７７】
［Ciphertext-Policy関数型暗号方式(CP-FE)］
Ciphertext-Policy関数型暗号方式は、4つのアルゴリズム(Setup,KeyGen,Enc,Dec)から構成される。
＜Setupアルゴリズム＞セキュリティパラメータと属性フォーマットn→:=(d,n1,…,nd)とを入力とし、公開鍵pkとマスタ秘密鍵skを出力する。
＜KeyGenアルゴリズム＞属性集合Γ:={(t,v→t)|v→t∈Fqnt,1≦t≦d}と公開鍵pkとマスタ秘密鍵skとを入力とし、暗号化鍵を出力する。
＜Encアルゴリズム＞平文mとアクセスストラクチャS:=(M,ρ)と公開鍵pkとを入力とし、暗号文を出力する。
＜Decアルゴリズム＞アクセスストラクチャSの下で暗号化された暗号文と属性集合Γのための暗号化鍵と公開鍵pkとを入力とし、平文mもしくは識別情報⊥を出力する。
【００７８】
［実施形態］
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００７９】
＜構成＞
図１を参照して、この実施形態の関数型暗号システム１０の構成例を説明する。関数型暗号システム１０は、鍵生成装置１と暗号化装置２と復号装置３とを含む。鍵生成装置１と暗号化装置２と復号装置３はネットワーク４に接続される。ネットワーク４は、接続される各装置が相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）などで構成することができる。なお、各装置は必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、鍵生成装置１の出力する情報を磁気テープやＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで暗号化装置２もしくは復号装置３へ入力するように構成してもよい。他の装置間における情報伝播に関しても同様であるので詳細な説明は省略する。
【００８０】
図２を参照して、この実施形態の関数型暗号システム１０に含まれる鍵生成装置１の構成例を説明する。鍵生成装置１は、制御部１０１、メモリ１０２、入力部１１、初期化部１２、鍵生成部１３、出力部１４を備える。鍵生成装置１は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。鍵生成装置１は制御部１０１の制御のもとで各処理を実行する。鍵生成装置１に入力されたデータや各処理で得られたデータはメモリ１０２に格納され、メモリ１０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００８１】
図３を参照して、この実施形態の関数型暗号システム１０に含まれる暗号化装置２の構成例を説明する。暗号化装置２は、制御部２０１、メモリ２０２、入力部２１、暗号化部２２、出力部２３を備える。暗号化装置２は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。暗号化装置２は制御部２０１の制御のもとで各処理を実行する。暗号化装置２に入力されたデータや各処理で得られたデータはメモリ２０２に格納され、メモリ２０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００８２】
図４を参照して、この実施形態の関数型暗号システム１０に含まれる復号装置３の構成例を説明する。復号装置３は、制御部３０１、メモリ３０２、入力部３１、復号部３２、出力部３３を備える。復号装置３は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。復号装置３は制御部３０１の制御のもとで各処理を実行する。復号装置３に入力されたデータや各処理で得られたデータはメモリ３０２に格納され、メモリ３０２に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００８３】
＜鍵生成処理＞
図５を参照して、関数型暗号システム１０の実行する鍵生成処理の動作例について手続きの順に従って詳細に説明する。
【００８４】
鍵生成装置１の備える入力部１１へセキュリティパラメータλと属性フォーマットn→が入力される（ステップＳ１１）。セキュリティパラメータλと属性フォーマットn→は、初期化部１２へ入力される。初期化部１２は、この発明の関数型暗号方式のSetupアルゴリズムを実行する。属性フォーマットn→は、n→:=(d;n1,…,nt)で表現されるd次元ベクトルである。Setupアルゴリズムは、セキュリティパラメータλと属性フォーマットn→を入力として、公開鍵pkとマスタ秘密鍵skを出力する。
【００８５】
Setupアルゴリズムは、まず、正規直交基底生成アルゴリズムgobを実行する。正規直交基底生成アルゴリズムgobは、1λを入力として、パラメータparamと基底B0,B*0と値B*t,i,j,B’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,Nt)を出力する。
【００８６】
以下に、正規直交基底生成アルゴリズムgobの一例を示す。正規直交基底生成アルゴリズムgobは、1λを入力として対称ペアリング群生成アルゴリズムGbpgを実行し、素数qと位数qの巡回乗法群G,GTと群Gの生成元gと線型写像eからなる対称ペアリング群paramG:=(q,G,GT,g,e)を生成する。
【００８７】
【数１８】
2014095847.tif 000020
【００８８】
次に、値N0に5を設定する。また、t=0,…,dについて、値Ntに4ntを設定する。さらに、乗法群Fq×から乱数Ψを選択し、値gT:=e(g,g)Ψを計算する。
【００８９】
【数１９】
2014095847.tif 000021
【００９０】
次に、t=0,…,dについて、1λと値Ntと対称ペアリング群paramGを入力として、双対ペアリングベクトル空間生成アルゴリズムGdpvsを実行することで、それぞれが素数qと空間Vtと位数qの巡回乗法群GTと標準基底Atと線型写像eからなるparamV0,…,paramVdを生成する。
【００９１】
【数２０】
2014095847.tif 000022
【００９２】
そして、paramV0,…,paramVdとgTからなるパラメータparamを生成する。
【００９３】
【数２１】
2014095847.tif 000023
【００９４】
次に、一般線形群GL(N0,Fq)からランダムに値χ0,i,j(i,j=1,…,4)を選択して、行列X0を生成する。
【００９５】
【数２２】
2014095847.tif 000024
【００９６】
また、有限体Fqからランダムに値μ*t,i,jおよび値μ’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,nt)を選択し、行列Xtを生成する。
【００９７】
【数２３】
2014095847.tif 000025
【００９８】
次に、t=0,…,dについて、乱数Ψと行列Xtを用いて値θt,i,j(i,j=1,…,Nt)を生成する。
【００９９】
【数２４】
2014095847.tif 000026
【０１００】
次に、t=0,…,d;i=1,…,Ntについて、値θt,i,jと標準基底Atを用いて、基底ベクトルbt,iを生成し、基底Btを生成する。
【０１０１】
【数２５】
2014095847.tif 000027
【０１０２】
また、i=1,…,5について、値χ0,i,1,…,χ0,i,5と標準基底A0を用いて、基底ベクトルb*0,iを生成し、基底B*0を生成する。
【０１０３】
【数２６】
2014095847.tif 000028
【０１０４】
次に、t=1,…,d;i,j=1,…,4について、値μ*t,i,jと生成元gを用いて、値B*t,i,jを求める。
【０１０５】
【数２７】
2014095847.tif 000029
【０１０６】
また、t=1,…,d;i,j=1,…,4;L=1,…,Ntについて、値μ’*t,i,j,Lと生成元gを用いて、値B’*t,i,j,Lを求める。
【０１０７】
【数２８】
2014095847.tif 000030
【０１０８】
そして、正規直交基底生成アルゴリズムgobは、パラメータparamと基底B0,B*0と値B*t,i,j,B’*t,i,j,L(t=1,…,d;i,j=1,…,4;L=1,…,Nt)を出力する。
【０１０９】
【数２９】
2014095847.tif 000031
【０１１０】
Setupアルゴリズムは、基底B0の基底ベクトルb0,1,b0,3,b0,5を用いて、基底B^0を生成する。また、基底B*0の基底ベクトルb*0,1,b*0,3,b*0,4を用いて、基底B^*0を生成する。
【０１１１】
【数３０】
2014095847.tif 000032
【０１１２】
次に、t=1,…,dについて、基底Btの基底ベクトルbt,1,…,bt,nt,bt,3nt+1,…,bt,4ntを用いて、基底B^tを生成する。
【０１１３】
【数３１】
2014095847.tif 000033
【０１１４】
そして、Setupアルゴリズムは、公開鍵pk:=(1λ,param,{B^t})とマスタ秘密鍵sk:=(B^*0,{B*t,i,j,B’*t,i,j,L})を出力する。
【０１１５】
【数３２】
2014095847.tif 000034
【０１１６】
公開鍵pkは公開される。公開の方法は限定されない。鍵生成装置１から暗号化装置２および復号装置３へ直接配布されてもよいし、ＰＫＩ（Public Key Infrastracture、公開鍵基盤）などを通じて暗号化装置２および復号装置３が取得可能としてもよい。マスタ秘密鍵skは鍵生成装置１が秘密に保持する。
【０１１７】
鍵生成装置１の備える鍵生成部１３は、この発明の関数型暗号方式のKeyGenアルゴリズムを実行する（ステップＳ１３）。KeyGenアルゴリズムは、公開鍵pkとマスタ秘密鍵skと属性集合Γを入力として、秘密鍵skΓを出力する。属性集合Γは値tと属性ベクトルv→tの組からなる。属性ベクトルv→tは、有限体Fq上のnt次元ベクトルであり、vt,1=1である。
【０１１８】
【数３３】
2014095847.tif 000035
【０１１９】
KeyGenアルゴリズムは、まず、t=1,…,dについて、有限体Fqから乱数δ,ψ0,ψtを選択する。
【０１２０】
【数３４】
2014095847.tif 000036
【０１２１】
次に、乱数δ,ψ0と基底B0を用いて、鍵要素k*0を生成する。
【０１２２】
【数３５】
2014095847.tif 000037
【０１２３】
また、t=1,…,d;i=1,3について、乱数δ,ψtと値B*t,i,jを用いて、鍵要素K*t,1,jを求める。
【０１２４】
【数３６】
2014095847.tif 000038
【０１２５】
また、t=1,…,dについて、ベクトルv→tと値B’*t,i,j,Lを用いて、鍵要素K*t,2,jを求める。
【０１２６】
【数３７】
2014095847.tif 000039
【０１２７】
そして、KeyGenアルゴリズムは、属性要素Γと鍵要素k*0,K*t,1,j,K*t,2,jを用いて秘密鍵skΓを生成し出力する。
【０１２８】
【数３８】
2014095847.tif 000040
【０１２９】
秘密鍵skΓは出力部１３を介して出力される（ステップＳ１３）。秘密鍵skΓは復号装置３へ送信される。秘密鍵skΓの送受信は安全な通信路を経由して送受信されなければならない。例えば、周知の暗号化技術により安全性が確保された情報伝達手段を用いてもよい。また、磁気テープやＵＳＢメモリなどの可搬型記録媒体を経由して、鍵生成装置１から復号装置３へ搬送されてもよい。
【０１３０】
＜暗号化処理＞
図６を参照して、関数型暗号システム１０の実行する暗号化処理の動作例について手続きの順に従って詳細に説明する。
【０１３１】
公開鍵pkと平文mとアクセスストラクチャSが入力部２１を介して暗号化装置２へ入力される（ステップＳ２１）。これらはすべて同時に入力されなくてもよく、例えば、公開鍵pkはあらかじめ入力されており、平文mとアクセスストラクチャSが入力されるまでメモリ２０２等に記憶しておいてもよい。また、公開鍵pkと平文mとアクセスストラクチャSが入力された後、即時に以降の処理を実行しなくてもよい。例えば、利用者の操作やスケジュールによる自動実行など、処理開始の契機は限定されない。
【０１３２】
公開鍵pkと平文mとアクセスストラクチャSは暗号化部２２へ入力される。暗号化装置２の備える暗号化部２２は、この発明の関数型暗号方式のEncアルゴリズムを実行する（ステップＳ２２）。Encアルゴリズムは、公開鍵pkと平文mとアクセスストラクチャSを入力として、暗号文ctを出力する。アクセスストラクチャSはL行r列の行列Mとラベルρからなる。ラベルρ(i)は、iに対して肯定形の組(t,x→i)もしくは否定形の組¬(t,x→i)であるラベルである。属性ベクトルx→iは、有限体Fq上のnt次元ベクトルであり、xi,nt≠0である。
【０１３３】
【数３９】
2014095847.tif 000041
【０１３４】
Encアルゴリズムは、まず、有限体Fq上のr次元ベクトルf→をランダムに生成する。
【０１３５】
【数４０】
2014095847.tif 000042
【０１３６】
次に、乱数ベクトルf→と行列Mを用いて、秘密s0の分散値であるL次元ベクトルs→を生成する。また、乱数ベクトルf→を用いて、秘密s0を求める。
【０１３７】
【数４１】
2014095847.tif 000043
【０１３８】
次に、i=1,…,Lについて、有限体Fqからnt次元の乱数ベクトルη→iを生成し、乱数η0,τi,ζを選択する。
【０１３９】
【数４２】
2014095847.tif 000044
【０１４０】
次に、秘密s0と乱数ζ,η0と基底B0を用いて、暗号文要素c0を生成する。
【０１４１】
【数４３】
2014095847.tif 000045
【０１４２】
また、i=1,…,Lについて、ラベルρ(i)が肯定形の組(t,x→i)であれば、標準基底ベクトルe→t,1と分散値siと乱数τiと乱数ベクトルη→iと基底Btを用いて、暗号文要素ciを生成する。ラベルρ(i)が否定形の組¬(t,x→i)であれば、属性ベクトルx→iと分散値siと乱数ベクトルη→iと基底Btを用いて、暗号文要素ciを生成する。
【０１４３】
【数４４】
2014095847.tif 000046
【０１４４】
次に、値gTと乱数ζと平文mを用いて、暗号文要素cd+1を計算する。
【０１４５】
【数４５】
2014095847.tif 000047
【０１４６】
そして、Encアルゴリズムは、アクセスストラクチャSと暗号文要素c0,c1,…,cL,cd+1を用いて暗号文ctを生成し出力する。
【０１４７】
【数４６】
2014095847.tif 000048
【０１４８】
暗号文ctは出力部２３を介して出力される（ステップＳ２３）。暗号文ctは復号装置３へ送信される。暗号文ctの送受信はどのような方法を用いてもよい。
【０１４９】
＜復号処理＞
図７を参照して、関数型暗号システム１０の実行する復号処理の動作例について手続きの順に従って詳細に説明する。
【０１５０】
公開鍵pkと秘密鍵skΓと暗号文ctが入力部３１を介して復号装置３へ入力される（ステップＳ３１）。これらはすべて同時に入力されなくてもよく、例えば、公開鍵pkと秘密鍵skΓはあらかじめ入力されており、暗号文ctが入力されるまでメモリ３０２等へ記憶しておいてもよい。また、公開鍵pkと秘密鍵skΓと暗号文ctが入力された後、即時に以降の処理を実行しなくてもよい。例えば、利用者の操作やスケジュールによる自動実行など、処理開始の契機は限定されない。
【０１５１】
公開鍵pkと秘密鍵skΓと暗号文ctは復号部３２へ入力される。復号装置３の備える復号部３２は、この発明の関数型暗号方式のDecアルゴリズムを実行する（ステップＳ３２）。Decアルゴリズムは、公開鍵pkと秘密鍵skΓと暗号文ctを入力とし、平文mを出力する。
【０１５２】
Decアルゴリズムは、まず、入力されたアクセスストラクチャSが行列Mとラベルρの組であることを確認する。確認ができたら秘密鍵skΓに含まれる属性集合Γを受理する。i=1,…,Lについて、ラベルρ(i)が肯定形の組(t,x→i)であり、肯定形の組(t,x→i)が属性集合Γに含まれており、x→iとv→tの内積が0であるiと、ラベルρ(i)が否定形の組¬(t,x→i)であり、否定形の組¬(t,x→i)が属性集合Γに含まれており、x→iとv→tの内積が0でないiとを抽出して集合Iを求める。
【０１５３】
【数４７】
2014095847.tif 000049
【０１５４】
次に、i∈Iについて、行列Mのi行目と掛け合わせた総和が1→となる係数αiを求める。
【０１５５】
【数４８】
2014095847.tif 000050
【０１５６】
次に、i=1,…,Lについて、暗号文要素ciをそれぞれ4ni個に分割し、値Ci,1,…,Ci,4niを生成する。また、属性ベクトルv→tと値Ci,1,…,Ci,4niを用いて、値Di,jを求める。
【０１５７】
【数４９】
2014095847.tif 000051
【０１５８】
次に、暗号文要素c0と鍵要素k*0と値Di,jと値K*t,1,j,K*t,2,jと係数αiと属性ベクトルx→i,v→tを用いて、値Fを計算する。
【０１５９】
【数５０】
2014095847.tif 000052
【０１６０】
そして、Decアルゴリズムは、暗号文要素cd+1と値Fを用いて平文mを計算し出力する。
【０１６１】
【数５１】
2014095847.tif 000053
【０１６２】
平文mは出力部３３を介して出力される（ステップＳ３３）。
【０１６３】
＜効果＞
この発明の関数型暗号技術による復号の処理速度と、従来の関数型暗号方式の復号の処理速度を比較する。以下では、Aを楕円加算1回の演算時間とし、Sを楕円スカラ倍算の演算時間とし、Pをペアリングの演算時間とする。なお、有限体上の演算は無視できるほど小さいとして考える。
【０１６４】
非特許文献１に記載された従来の関数型暗号方式では、復号の演算時間は下記の式で表すことができる。
【０１６５】
【数５２】
2014095847.tif 000054
【０１６６】
この発明の関数型暗号技術では、復号の演算時間は下記の式で表すことができる。
【０１６７】
【数５３】
2014095847.tif 000055
【０１６８】
この発明の関数型暗号技術は非特許文献１に記載された関数型暗号技術と比較して、ペアリングの演算時間が(Σdt=13nt+2)Pから9Pへ減少している。一方で、楕円加算の演算時間がΣdt=14(nt-2)A、楕円スカラ倍算の演算時間がΣdt=14(nt-1)S、と増加している。
【０１６９】
様々なハードウェアを用いた各演算の処理時間が、例えば「Jean-Luc Beuchat, Jorge Enrique Gonzalez-Diaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodriguez-Henriquez, and Tadanori Teruya, “High-speed software imple-mentation of the optimal ate pairing over barreto-naehrig curves”,Pairing 2010, pp. 21-39.（参考文献１）」などに開示されている。参考文献１に依れば、各演算の演算時間は、素体上の楕円加算が0.005034ミリ秒、スカラ倍算が0.262895ミリ秒、ペアリングが0.861208ミリ秒である。例えば、d=10とし、すべてのtについてnt=10とすると、非特許文献１に記載された関数型暗号技術では、復号時の演算時間が275.58656ミリ秒となる。この発明の関数型暗号技術では、復号時の演算時間が102.55416ミリ秒となる。両者を比較すると、この発明の関数型暗号技術の復号処理の方が約63%高速化することがわかる。
【０１７０】
このように、この発明の関数型暗号技術は、従来の関数型暗号方式と同様に、否定表現を含む広い言語表現を実現しつつ、復号時の処理におけるペアリング演算を楕円加算とスカラ倍算に置き換えることで、復号処理を高速化することができる。
【０１７１】
［安全性］
この発明の実行する関数型暗号方式は、安全性向上のために周知の変換手法を適用することができる。例えば「Dan Boneh, Jonathan Katz, “Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption”, RSA-CT '05, LNCS 3376, pp. 87-103, 2005.（参考文献２）」に記載されている、いわゆるBoneh-Katz変換を適用することにより、選択暗号文攻撃(Chosen Ciphertext Attack, CCA)に対して安全な暗号方式に変換することが可能である。Boneh-Katz変換の詳細な構成方法については、参考文献２を参照されたい。
【０１７２】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１７３】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１７４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１７５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１７６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１７７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１７８】
１０  関数型暗号システム
１  鍵生成装置
２  暗号化装置
３  復号装置
４  ネットワーク
１１  入力部
１２  初期化部
１３  鍵生成部
１４  出力部
２１  入力部
２２  暗号化部
２３  出力部
３１  入力部
３２  復号部
３３  出力部
１０１，２０１，３０１  制御部
１０２，２０２，３０２  メモリ
【図１】
2014095847.tif 000065
【図２】
2014095847.tif 000066
【図３】
2014095847.tif 000067
【図４】
2014095847.tif 000068
【図５】
2014095847.tif 000069
【図６】
2014095847.tif 000070
【図７】
2014095847.tif 000071