ベクトル構成システム、方法、装置及びプログラム並びに暗号システム
【課題】n個の属性の論理積t個の論理和についての述語論理に関する属性ベクトル及び述語ベクトルのそれぞれの次元数をt+1にする技術を提供する。
【解決手段】ベクトル構成システムは、nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成装置１と、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成装置２と、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成装置３と、を含む。
【解決手段】ベクトル構成システムは、nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成装置１と、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成装置２と、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成装置３と、を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、二者間で同じ情報を共有するための技術に関する。
【背景技術】
【０００２】
非特許文献１で属性秘匿な述語暗号が提案され、内積述語を用いることで様々な論理和を暗号化関数及び鍵生成関数を使って、暗号文や鍵に埋め込むことが可能になった。内積述語では、例えばn個の属性の論理積がt個あるとしてこれらのt個の論理積が論理和で組み合わされた述語論理、すなわちn個の属性の論理積t個の論理和についての述語論理を扱うことができる。n=2,t=2の場合の述語論理の例は、以下のような属性「役職」が部長でありかつ属性「部署」が人事部、または、属性「役職」が課長でありかつ属性「部署」が人事部というものである。
（役職＝部長 かつ 部署＝人事部）
または
（役職＝課長 かつ 部署＝総務部）
【０００３】
一般に、n個の属性の論理積t個の論理和についての述語論理は、n個の属性値xi(i=1,2,…,n)∈Fq、t×n個の述語値vj,i(j=1,2,…,t, i=1,2,…,n)∈Fq、t×n個の乱数rj,i(j=1,2,…,t, i=1,2,…,n)∈Fqを用いて以下のように記述することができる。Fqは、位数ｑの有限体である。ここで、Vj=-Σi=1nrj,ivj,iとする。
【０００４】
[r1,1(x1-v1,1)+r1,2(x2-v1,2)+r1,3(x3-v1,3)+…+r1,n(xn-v1,n)]
×[r2,1(x1-v2,1)+r2,2(x2-v2,2)+r2,3(x3-v2,3)+…+r2,n(xn-v1,n)]
×…
×[rt,1(x1-vt,1)+rt,2(x2-vt,2)+rt,3(x3-vt,3)+…+rt,n(xn-vt,n)]
=Πj=1tΣi=1nrj,i(xi-vj,i)
=Πj=1t(Σi=1nrj,ixi-Σi=1nrj,ivj,i)
=Πj=1t(Σi=1nrj,ixi+Vj)
この式の値が０になれば、この述語論理は所定の条件を満たしたと判断することができる。
【０００５】
Σi=1nrj,ixi+Vjは、xiについての多項式として見るとn+1個の項から構成されている。したがって、上記のΠj=1t(Σi=1nrj,ixi+Vj)は、xiについての多項式として見るとn+1Ht=n+1+t-1Ct=(n+t)!/n!t!個の項から構成されている。このため、上記のΠj=1t(Σi=1nrj,ixi+Vj)は、(n+t)!/n!t!次元の属性ベクトルと(n+t)!/n!t!次元の述語ベクトルとの内積とみなすことができる。属性ベクトルとは、属性値xiから構成されるベクトルであり、述語ベクトルとは、述語値vj,iから構成されるベクトルである。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Jonathan Katz, Amit Sahai, Brent Waters, “Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products”, EUROCRYPTO 2008, LNCS 4965, pp.146-162, 2008
【発明の概要】
【発明が解決しようとする課題】
【０００７】
背景技術に記載した技術では、属性ベクトル及び述語ベクトルのそれぞれは(n+t)!/n!t!次元となる。
【０００８】
この発明の課題は、属性ベクトル及び述語ベクトルのそれぞれの次元数を背景技術に記載した技術の次元数以下にするベクトル構成システム、方法、装置及びプログラム並びに暗号システムを提供することである。
【課題を解決するための手段】
【０００９】
この発明の一態様によるベクトル構成システムは、nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成装置と、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成装置と、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成装置と、を含む。
【発明の効果】
【００１０】
n個の属性の論理積t個の論理和についての述語論理に関する属性ベクトル及び述語ベクトルのそれぞれの次元数をt+1にすることができる。
【図面の簡単な説明】
【００１１】
【図１】実施形態のベクトル構成システムの構成を説明するためのブロック図。
【図２】実施形態のベクトル構成システムの変形例の構成を説明するためのブロック図。
【図３】実施形態のベクトル構成システムの変形例の構成を説明するためのブロック図。
【図４】実施形態のベクトル構成システムの変形例の構成を説明するためのブロック図。
【図５】暗号システムの一例の構成を説明するためのブロック図。
【図６】実施形態のベクトル構成システムを説明するためのフローチャート。
【発明を実施するための形態】
【００１２】
以下、図面を参照してこの発明の一実施形態を説明する。
【００１３】
［技術的背景］
まず、技術的背景について説明する。
【００１４】
背景技術では、n個の属性の論理積がt個あるとしてこれらのt個の論理積が論理和で組み合わされた述語論理、すなわちn個の属性の論理積t個の論理和についての述語論理を、n個の属性値xi(i=1,2,…,n)∈Fq、t×n個の述語値vj,i(j=1,2,…,t, i=1,2,…,n)∈Fq、t×n個の乱数rj,i(j=1,2,…,t, i=1,2,…,n)∈Fqを用いて記述した。n,tのそれぞれは、正の整数であり、Fqは位数qの有限体である。
【００１５】
これに対して、この実施形態では、t×n個の乱数rj,i(j=1,2,…,t, i=1,2,…,n)∈Fqの代わりに、Fqの元又は整数であるn個の共通パラメータri(i=1,2,…,n)を用いて述語論理を記述する。属性値xi(i=1,2,…,n)∈Fq及び述語値vj,i(j=1,2,…,t, i=1,2,…,n)∈Fqは、背景技術と同様である。具体的には、n個の属性の論理積t個の論理和についての述語論理を以下のように表現する。この式の値が０になれば、この述語論理は所定の条件を満たしたと判断することができる。
【００１６】
[r1(x1-v1,1)+r2(x2-v1,2)+r3(x3-v1,3)+…+rn(xn-v1,n)]
×[r1(x1-v2,1)+r2(x2-v2,2)+r3(x3-v2,3)+…+rn(xn-v1,n)]
×…
×[r1(x1-vt,1)+r2(x2-vt,2)+r3(x3-vt,3)+…+rn(xn-vt,n)]
=Πj=1tΣi=1nri(xi-vj,i)
=Πj=1t(Σi=1nrixi-Σi=1nrivj,i)
=Πj=1t(X+Vj)
=Xt+(V1+V2+…+Vt)Xt-1+(V1V2+V1V3…+Vt-1Vt)Xt-2+…+ (V1V2…Vt-1Vt)X0
=Σk=1tskXt-k
=(Xt,Xt-1,Xt-2,…,X,1)(s0,s1,…,st)T
ここで、X=Σi=1nrixi, Vj=-Σi=1nrivj,i, s0=1, skはVjのk次基本対称式、（・）Tは・の転置とする。例えば、１次基本対称式s1=V1+V2+…+Vnであり、２次基本対称式s2=V1V2+V1V3…+Vn-1Vnである。kをt以下の正の整数として、k次基本対称式skは以下のように書くことができる。
【数１】
【００１７】
ここで、Xt,Xt-1,Xt-2,…,X,1を要素とするベクトル、すなわち(Xt,Xt-1,Xt-2,…,X,1)を属性ベクトルとする。また、s0,s1,…,stを要素とするベクトル、すなわち(s0,s1,…,st)Tを述語ベクトルとする。
【００１８】
このように、n個の共通パラメータri(i=1,2,…,n)を用いることにより、属性ベクトル及び述語ベクトルのそれぞれの次元数がt+1となり、背景技術の次元数(n+t)!/n!t!以下となる。これにより、この属性ベクトル及び述語ベクトルを用いた暗号技術の演算量を削減することができる。なお、このように、共通パラメータriを共有化することにより、これらの共通パラメータriの数を少なくしても、安全性には問題がない。
【００１９】
［実施形態］
ベクトル構成システム及び方法の一実施形態を以下に示す。
【００２０】
ベクトル構成システムは、図１に示すように、共通パラメータ生成装置１、属性ベクトル生成装置２、述語ベクトル生成装置３、判定装置４を例えば含む。ベクトル構成システムは、図６に例示されたベクトル構成方法の各ステップの処理を行う。
【００２１】
共通パラメータ生成装置１は、Fqの元又は整数であるn個の共通パラメータri(i=1,2,…,n)を生成する（ステップＳ１）。例えば、riを乱数とする。すなわち、Fqからランダムに選択した元をriとする。生成された共通パラメータriは、属性ベクトル生成装置２及び述語ベクトル生成装置３に送信される。
【００２２】
属性ベクトル生成装置２は、属性値xi及び共通パラメータriを用いて、Xt,Xt-1,…,X1,X0を要素とする属性ベクトル(Xt,Xt-1,Xt-2,…,X,1)を生成する（ステップＳ２）。技術的背景の欄で説明したように、X=Σi=1nrixiである。生成された属性ベクトルは、この例では判定装置４に送信される。
【００２３】
ここで、X=Σi=1nrixiである。Xのベキ乗の計算は、既に計算されたXのベキ乗にXを乗算する操作を繰り返すことにより計算しても良いし、例えば参考文献１に記載されているような効率の良い計算手法を用いてもよい。
【００２４】
〔参考文献１〕WIEB BOSMA, “Signed bits and fast exponentiation”, Journal de Theorie des Nombres de Bordeaux, tome 13, n0 1, pp.27-41, 2001
【００２５】
属性ベクトル生成装置２自身が属性値xiを生成しても良いし、属性ベクトル生成装置２以外の装置、例えば図４のセットアップ装置５が属性値xiを生成してもよい。
【００２６】
述語ベクトル生成装置３は、述語値vj,i及び共通パラメータriを用いて、s0,s1,…,stを要素とする述語ベクトル(s0,s1,…,st)Tを生成する（ステップＳ３）。技術的背景の欄で説明したように、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとして、skはVjのk次基本対称式である。ただし、s0=1である。生成された述語ベクトルは、この例では判定装置４に送信される。
【００２７】
述語ベクトル生成装置３自身が述語値vj,iを生成しても良いし、述語ベクトル生成装置３以外の装置、例えば図４のセットアップ装置５が述語値vj,iを生成してもよい。
【００２８】
判定装置４は、属性ベクトル(Xt,Xt-1,Xt-2,…,X,1)と述語ベクトル(s0,s1,…,st)Tとの内積が０になるか判定する（ステップＳ４）。内積が０になれば所定の条件を満たしたと判断することができ、内積が０でなければその所定の条件は満たしていないと判断することができる。
【００２９】
［暗号システムへの応用例］
ベクトル構成システム及び方法により生成された属性ベクトル及び述語ベクトルは、関数暗号又は内積述語暗号を用いた暗号システムに用いることができる。すなわち、属性ベクトル及び述語ベクトルを用いる関数暗号又は内積述語暗号の暗号システムが、上記のベクトル構成システムを有していても良い。属性ベクトル及び述語ベクトルを用いる内積述語暗号の暗号システムについては、例えば参考文献２から４を参照のこと。また、属性ベクトル及び述語ベクトルを用いる内積述語暗号により、例えば参考文献５のようにファイルサーバの暗号情報の検索を階層的に利用することができる。また、属性ベクトル及び述語ベクトルを用いる関数暗号の暗号システムについては、例えば参考文献６を参照のこと。
【００３０】
〔参考文献２〕A.B.Lewko, T.Okamoto, A.Sahai, K.Takashima, B.Waters, “Fully
secure functional encryption: Attribute-based encryption and (hierarchical)
inner product encryption”, In EUROCRYPT, pp.62-91, 2010
〔参考文献３〕N.Matsuda, M.Hattori, T.Ito, T.Yoneda, “Secure datacenter systems with hierarchical predicate encryption”, In Symp. on Cryptography and Information Security, 2010
〔参考文献４〕T.Okamoto, K.Takashima, “Hierarchical predicate encryption for innerproducts”, In ASIACRYPT, pp.214-231, 2009
〔参考文献５〕R.Yoshida, A.Nagai, T.Kobayashi, “Hierarchical predicate encryption with keyword search in multi-user setting”, In Computer Security Symposium, 2010
〔参考文献６〕T.Okamoto, K.Takashima, “Fully secure functional encryption with general relations from the decisional linear assumption”, In CRYPTO, pp.191-208, 2010.
【００３１】
以下、図５を参照して、上記のベクトル構成システムを含む暗号システムの例を説明する。この例の暗号システムは、共通パラメータ生成装置１、属性ベクトル生成装置２、述語ベクトル生成装置３、暗号化装置６、鍵生成装置７及び復号装置８を含む。この例では、属性ベクトル生成装置２は暗号化装置６に含まれ、述語ベクトル生成装置３は鍵生成装置７に含まれる。
【００３２】
図示していないセットアップ装置により公開パラメータprm及びマスタ秘密鍵mskが生成され、公開パラメータprmは各装置に配布され、マスタ秘密鍵mskは鍵生成装置７に配布される。
【００３３】
共通パラメータ生成装置１、属性ベクトル生成装置２及び述語ベクトル生成装置３の処理は、上記と同様であるため重複説明を省略する。以下、属性ベクトル生成装置２により生成された属性ベクトル(Xt,Xt-1,Xt-2,…,X,1)をx→と表記し、述語ベクトル生成装置３により生成された述語ベクトル(s0,s1,…,st)Tをu→と表記する。
【００３４】
暗号化装置６は、公開パラメータprm及び属性ベクトルx→を用いて、所定の暗号化アルゴリズムEncにより平文mを暗号化して、暗号文cを生成する。暗号文cは、復号装置８に送信される。
c=Enc(prm,x→,m)
【００３５】
鍵生成装置７は、マスタ秘密鍵msk、述語ベクトルu→及び公開パラメータprmを用いて、所定の鍵生成アルゴリズムKeyGenより、鍵kを生成する。鍵kは、復号装置８に送信される。
k=KeyGen(msk,u→,prm)
【００３６】
復号装置８は、鍵kを用いて所定の復号アルゴリズムDecにより暗号文cを復号して、平文mを生成する。
m=Dec(k,c)
【００３７】
［変形例等］
共通パラメータ生成装置１は、図２に示すように、属性ベクトル生成装置２に含まれていても良い。同様に、共通パラメータ生成装置１は、図３に示すように、述語ベクトル生成装置３に含まれていても良い。
【００３８】
また、図４に示すように、共通パラメータ生成装置１は、セットアップ装置５に含まれていても良い。
【００３９】
この場合、セットアップ装置５は、まず属性値xiを生成する。そして、セットアップ装置５は、共通パラメータ生成装置１により生成された共通パラメータriと属性値xiの積である新属性値rixiを計算し、計算された新属性値rixiを属性ベクトル生成装置２に送信する。属性ベクトル生成装置２は、新属性値rixiを用いて属性ベクトルの生成を行う。また、セットアップ装置５は、まず述語値vj,iを生成する。そして、セットアップ装置５は、共通パラメータ生成装置１により生成された共通パラメータriと述語値vj,iの積である新述語値rivj,iを計算し、計算された新述語値rivj,iを述語ベクトル生成装置３に送信する。述語ベクトル生成装置３は、新述語値rivj,iを用いて述語ベクトルの生成を行う。
【００４０】
各装置間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、各装置の内部でのデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００４１】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
【００４３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４４】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００４５】
１ 共通パラメータ生成装置
２ 属性ベクトル生成装置
３ 述語ベクトル生成装置
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関する。特に、二者間で同じ情報を共有するための技術に関する。
【背景技術】
【０００２】
非特許文献１で属性秘匿な述語暗号が提案され、内積述語を用いることで様々な論理和を暗号化関数及び鍵生成関数を使って、暗号文や鍵に埋め込むことが可能になった。内積述語では、例えばn個の属性の論理積がt個あるとしてこれらのt個の論理積が論理和で組み合わされた述語論理、すなわちn個の属性の論理積t個の論理和についての述語論理を扱うことができる。n=2,t=2の場合の述語論理の例は、以下のような属性「役職」が部長でありかつ属性「部署」が人事部、または、属性「役職」が課長でありかつ属性「部署」が人事部というものである。
（役職＝部長 かつ 部署＝人事部）
または
（役職＝課長 かつ 部署＝総務部）
【０００３】
一般に、n個の属性の論理積t個の論理和についての述語論理は、n個の属性値xi(i=1,2,…,n)∈Fq、t×n個の述語値vj,i(j=1,2,…,t, i=1,2,…,n)∈Fq、t×n個の乱数rj,i(j=1,2,…,t, i=1,2,…,n)∈Fqを用いて以下のように記述することができる。Fqは、位数ｑの有限体である。ここで、Vj=-Σi=1nrj,ivj,iとする。
【０００４】
[r1,1(x1-v1,1)+r1,2(x2-v1,2)+r1,3(x3-v1,3)+…+r1,n(xn-v1,n)]
×[r2,1(x1-v2,1)+r2,2(x2-v2,2)+r2,3(x3-v2,3)+…+r2,n(xn-v1,n)]
×…
×[rt,1(x1-vt,1)+rt,2(x2-vt,2)+rt,3(x3-vt,3)+…+rt,n(xn-vt,n)]
=Πj=1tΣi=1nrj,i(xi-vj,i)
=Πj=1t(Σi=1nrj,ixi-Σi=1nrj,ivj,i)
=Πj=1t(Σi=1nrj,ixi+Vj)
この式の値が０になれば、この述語論理は所定の条件を満たしたと判断することができる。
【０００５】
Σi=1nrj,ixi+Vjは、xiについての多項式として見るとn+1個の項から構成されている。したがって、上記のΠj=1t(Σi=1nrj,ixi+Vj)は、xiについての多項式として見るとn+1Ht=n+1+t-1Ct=(n+t)!/n!t!個の項から構成されている。このため、上記のΠj=1t(Σi=1nrj,ixi+Vj)は、(n+t)!/n!t!次元の属性ベクトルと(n+t)!/n!t!次元の述語ベクトルとの内積とみなすことができる。属性ベクトルとは、属性値xiから構成されるベクトルであり、述語ベクトルとは、述語値vj,iから構成されるベクトルである。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Jonathan Katz, Amit Sahai, Brent Waters, “Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products”, EUROCRYPTO 2008, LNCS 4965, pp.146-162, 2008
【発明の概要】
【発明が解決しようとする課題】
【０００７】
背景技術に記載した技術では、属性ベクトル及び述語ベクトルのそれぞれは(n+t)!/n!t!次元となる。
【０００８】
この発明の課題は、属性ベクトル及び述語ベクトルのそれぞれの次元数を背景技術に記載した技術の次元数以下にするベクトル構成システム、方法、装置及びプログラム並びに暗号システムを提供することである。
【課題を解決するための手段】
【０００９】
この発明の一態様によるベクトル構成システムは、nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成装置と、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成装置と、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成装置と、を含む。
【発明の効果】
【００１０】
n個の属性の論理積t個の論理和についての述語論理に関する属性ベクトル及び述語ベクトルのそれぞれの次元数をt+1にすることができる。
【図面の簡単な説明】
【００１１】
【図１】実施形態のベクトル構成システムの構成を説明するためのブロック図。
【図２】実施形態のベクトル構成システムの変形例の構成を説明するためのブロック図。
【図３】実施形態のベクトル構成システムの変形例の構成を説明するためのブロック図。
【図４】実施形態のベクトル構成システムの変形例の構成を説明するためのブロック図。
【図５】暗号システムの一例の構成を説明するためのブロック図。
【図６】実施形態のベクトル構成システムを説明するためのフローチャート。
【発明を実施するための形態】
【００１２】
以下、図面を参照してこの発明の一実施形態を説明する。
【００１３】
［技術的背景］
まず、技術的背景について説明する。
【００１４】
背景技術では、n個の属性の論理積がt個あるとしてこれらのt個の論理積が論理和で組み合わされた述語論理、すなわちn個の属性の論理積t個の論理和についての述語論理を、n個の属性値xi(i=1,2,…,n)∈Fq、t×n個の述語値vj,i(j=1,2,…,t, i=1,2,…,n)∈Fq、t×n個の乱数rj,i(j=1,2,…,t, i=1,2,…,n)∈Fqを用いて記述した。n,tのそれぞれは、正の整数であり、Fqは位数qの有限体である。
【００１５】
これに対して、この実施形態では、t×n個の乱数rj,i(j=1,2,…,t, i=1,2,…,n)∈Fqの代わりに、Fqの元又は整数であるn個の共通パラメータri(i=1,2,…,n)を用いて述語論理を記述する。属性値xi(i=1,2,…,n)∈Fq及び述語値vj,i(j=1,2,…,t, i=1,2,…,n)∈Fqは、背景技術と同様である。具体的には、n個の属性の論理積t個の論理和についての述語論理を以下のように表現する。この式の値が０になれば、この述語論理は所定の条件を満たしたと判断することができる。
【００１６】
[r1(x1-v1,1)+r2(x2-v1,2)+r3(x3-v1,3)+…+rn(xn-v1,n)]
×[r1(x1-v2,1)+r2(x2-v2,2)+r3(x3-v2,3)+…+rn(xn-v1,n)]
×…
×[r1(x1-vt,1)+r2(x2-vt,2)+r3(x3-vt,3)+…+rn(xn-vt,n)]
=Πj=1tΣi=1nri(xi-vj,i)
=Πj=1t(Σi=1nrixi-Σi=1nrivj,i)
=Πj=1t(X+Vj)
=Xt+(V1+V2+…+Vt)Xt-1+(V1V2+V1V3…+Vt-1Vt)Xt-2+…+ (V1V2…Vt-1Vt)X0
=Σk=1tskXt-k
=(Xt,Xt-1,Xt-2,…,X,1)(s0,s1,…,st)T
ここで、X=Σi=1nrixi, Vj=-Σi=1nrivj,i, s0=1, skはVjのk次基本対称式、（・）Tは・の転置とする。例えば、１次基本対称式s1=V1+V2+…+Vnであり、２次基本対称式s2=V1V2+V1V3…+Vn-1Vnである。kをt以下の正の整数として、k次基本対称式skは以下のように書くことができる。
【数１】
【００１７】
ここで、Xt,Xt-1,Xt-2,…,X,1を要素とするベクトル、すなわち(Xt,Xt-1,Xt-2,…,X,1)を属性ベクトルとする。また、s0,s1,…,stを要素とするベクトル、すなわち(s0,s1,…,st)Tを述語ベクトルとする。
【００１８】
このように、n個の共通パラメータri(i=1,2,…,n)を用いることにより、属性ベクトル及び述語ベクトルのそれぞれの次元数がt+1となり、背景技術の次元数(n+t)!/n!t!以下となる。これにより、この属性ベクトル及び述語ベクトルを用いた暗号技術の演算量を削減することができる。なお、このように、共通パラメータriを共有化することにより、これらの共通パラメータriの数を少なくしても、安全性には問題がない。
【００１９】
［実施形態］
ベクトル構成システム及び方法の一実施形態を以下に示す。
【００２０】
ベクトル構成システムは、図１に示すように、共通パラメータ生成装置１、属性ベクトル生成装置２、述語ベクトル生成装置３、判定装置４を例えば含む。ベクトル構成システムは、図６に例示されたベクトル構成方法の各ステップの処理を行う。
【００２１】
共通パラメータ生成装置１は、Fqの元又は整数であるn個の共通パラメータri(i=1,2,…,n)を生成する（ステップＳ１）。例えば、riを乱数とする。すなわち、Fqからランダムに選択した元をriとする。生成された共通パラメータriは、属性ベクトル生成装置２及び述語ベクトル生成装置３に送信される。
【００２２】
属性ベクトル生成装置２は、属性値xi及び共通パラメータriを用いて、Xt,Xt-1,…,X1,X0を要素とする属性ベクトル(Xt,Xt-1,Xt-2,…,X,1)を生成する（ステップＳ２）。技術的背景の欄で説明したように、X=Σi=1nrixiである。生成された属性ベクトルは、この例では判定装置４に送信される。
【００２３】
ここで、X=Σi=1nrixiである。Xのベキ乗の計算は、既に計算されたXのベキ乗にXを乗算する操作を繰り返すことにより計算しても良いし、例えば参考文献１に記載されているような効率の良い計算手法を用いてもよい。
【００２４】
〔参考文献１〕WIEB BOSMA, “Signed bits and fast exponentiation”, Journal de Theorie des Nombres de Bordeaux, tome 13, n0 1, pp.27-41, 2001
【００２５】
属性ベクトル生成装置２自身が属性値xiを生成しても良いし、属性ベクトル生成装置２以外の装置、例えば図４のセットアップ装置５が属性値xiを生成してもよい。
【００２６】
述語ベクトル生成装置３は、述語値vj,i及び共通パラメータriを用いて、s0,s1,…,stを要素とする述語ベクトル(s0,s1,…,st)Tを生成する（ステップＳ３）。技術的背景の欄で説明したように、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとして、skはVjのk次基本対称式である。ただし、s0=1である。生成された述語ベクトルは、この例では判定装置４に送信される。
【００２７】
述語ベクトル生成装置３自身が述語値vj,iを生成しても良いし、述語ベクトル生成装置３以外の装置、例えば図４のセットアップ装置５が述語値vj,iを生成してもよい。
【００２８】
判定装置４は、属性ベクトル(Xt,Xt-1,Xt-2,…,X,1)と述語ベクトル(s0,s1,…,st)Tとの内積が０になるか判定する（ステップＳ４）。内積が０になれば所定の条件を満たしたと判断することができ、内積が０でなければその所定の条件は満たしていないと判断することができる。
【００２９】
［暗号システムへの応用例］
ベクトル構成システム及び方法により生成された属性ベクトル及び述語ベクトルは、関数暗号又は内積述語暗号を用いた暗号システムに用いることができる。すなわち、属性ベクトル及び述語ベクトルを用いる関数暗号又は内積述語暗号の暗号システムが、上記のベクトル構成システムを有していても良い。属性ベクトル及び述語ベクトルを用いる内積述語暗号の暗号システムについては、例えば参考文献２から４を参照のこと。また、属性ベクトル及び述語ベクトルを用いる内積述語暗号により、例えば参考文献５のようにファイルサーバの暗号情報の検索を階層的に利用することができる。また、属性ベクトル及び述語ベクトルを用いる関数暗号の暗号システムについては、例えば参考文献６を参照のこと。
【００３０】
〔参考文献２〕A.B.Lewko, T.Okamoto, A.Sahai, K.Takashima, B.Waters, “Fully
secure functional encryption: Attribute-based encryption and (hierarchical)
inner product encryption”, In EUROCRYPT, pp.62-91, 2010
〔参考文献３〕N.Matsuda, M.Hattori, T.Ito, T.Yoneda, “Secure datacenter systems with hierarchical predicate encryption”, In Symp. on Cryptography and Information Security, 2010
〔参考文献４〕T.Okamoto, K.Takashima, “Hierarchical predicate encryption for innerproducts”, In ASIACRYPT, pp.214-231, 2009
〔参考文献５〕R.Yoshida, A.Nagai, T.Kobayashi, “Hierarchical predicate encryption with keyword search in multi-user setting”, In Computer Security Symposium, 2010
〔参考文献６〕T.Okamoto, K.Takashima, “Fully secure functional encryption with general relations from the decisional linear assumption”, In CRYPTO, pp.191-208, 2010.
【００３１】
以下、図５を参照して、上記のベクトル構成システムを含む暗号システムの例を説明する。この例の暗号システムは、共通パラメータ生成装置１、属性ベクトル生成装置２、述語ベクトル生成装置３、暗号化装置６、鍵生成装置７及び復号装置８を含む。この例では、属性ベクトル生成装置２は暗号化装置６に含まれ、述語ベクトル生成装置３は鍵生成装置７に含まれる。
【００３２】
図示していないセットアップ装置により公開パラメータprm及びマスタ秘密鍵mskが生成され、公開パラメータprmは各装置に配布され、マスタ秘密鍵mskは鍵生成装置７に配布される。
【００３３】
共通パラメータ生成装置１、属性ベクトル生成装置２及び述語ベクトル生成装置３の処理は、上記と同様であるため重複説明を省略する。以下、属性ベクトル生成装置２により生成された属性ベクトル(Xt,Xt-1,Xt-2,…,X,1)をx→と表記し、述語ベクトル生成装置３により生成された述語ベクトル(s0,s1,…,st)Tをu→と表記する。
【００３４】
暗号化装置６は、公開パラメータprm及び属性ベクトルx→を用いて、所定の暗号化アルゴリズムEncにより平文mを暗号化して、暗号文cを生成する。暗号文cは、復号装置８に送信される。
c=Enc(prm,x→,m)
【００３５】
鍵生成装置７は、マスタ秘密鍵msk、述語ベクトルu→及び公開パラメータprmを用いて、所定の鍵生成アルゴリズムKeyGenより、鍵kを生成する。鍵kは、復号装置８に送信される。
k=KeyGen(msk,u→,prm)
【００３６】
復号装置８は、鍵kを用いて所定の復号アルゴリズムDecにより暗号文cを復号して、平文mを生成する。
m=Dec(k,c)
【００３７】
［変形例等］
共通パラメータ生成装置１は、図２に示すように、属性ベクトル生成装置２に含まれていても良い。同様に、共通パラメータ生成装置１は、図３に示すように、述語ベクトル生成装置３に含まれていても良い。
【００３８】
また、図４に示すように、共通パラメータ生成装置１は、セットアップ装置５に含まれていても良い。
【００３９】
この場合、セットアップ装置５は、まず属性値xiを生成する。そして、セットアップ装置５は、共通パラメータ生成装置１により生成された共通パラメータriと属性値xiの積である新属性値rixiを計算し、計算された新属性値rixiを属性ベクトル生成装置２に送信する。属性ベクトル生成装置２は、新属性値rixiを用いて属性ベクトルの生成を行う。また、セットアップ装置５は、まず述語値vj,iを生成する。そして、セットアップ装置５は、共通パラメータ生成装置１により生成された共通パラメータriと述語値vj,iの積である新述語値rivj,iを計算し、計算された新述語値rivj,iを述語ベクトル生成装置３に送信する。述語ベクトル生成装置３は、新述語値rivj,iを用いて述語ベクトルの生成を行う。
【００４０】
各装置間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。同様に、各装置の内部でのデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【００４１】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
【００４３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００４４】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００４５】
１ 共通パラメータ生成装置
２ 属性ベクトル生成装置
３ 述語ベクトル生成装置
【特許請求の範囲】
【請求項１】
nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成装置と、
ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成装置と、
vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s 0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成装置と、
を含むベクトル構成システム。
【請求項２】
請求項１のベクトル構成システムを含む、関数暗号又は内積述語暗号の暗号システム。
【請求項３】
共通パラメータ生成装置が、nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成ステップと、
属性ベクトル生成装置が、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成ステップと、
述語ベクトル生成装置が、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成ステップと、
を含むベクトル構成方法。
【請求項４】
nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnとし、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成するベクトル構成装置。
【請求項５】
nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnとし、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成するベクトル構成装置。
【請求項６】
請求項４又は５のベクトル構成装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１】
nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成装置と、
ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成装置と、
vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s 0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成装置と、
を含むベクトル構成システム。
【請求項２】
請求項１のベクトル構成システムを含む、関数暗号又は内積述語暗号の暗号システム。
【請求項３】
共通パラメータ生成装置が、nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnを生成する共通パラメータ生成ステップと、
属性ベクトル生成装置が、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成する属性ベクトル生成ステップと、
述語ベクトル生成装置が、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成する述語ベクトル生成ステップと、
を含むベクトル構成方法。
【請求項４】
nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnとし、ｔを正の整数とし、x1,x2,…,xn∈Fqとし、X=Σi=1nrixiとして、Xt,Xt-1,…,X1,X0を要素とする属性ベクトルを生成するベクトル構成装置。
【請求項５】
nを正の整数とし、Fqを有限体として、Fqの元又は整数である共通パラメータr1,r2,…rnとし、vj,1,vj,2,…,vj,n∈Fqとし、Vj=-Σi=1nrivj,iとし、s0=1とし、skをVjのk次基本対称式として、s0,s1,…,stを要素とする述語ベクトルを生成するベクトル構成装置。
【請求項６】
請求項４又は５のベクトル構成装置の各部としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−２４９２１５（Ｐ２０１２−２４９２１５Ａ）
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願番号】特願２０１１−１２１３００（Ｐ２０１１−１２１３００）
【出願日】平成２３年５月３１日（２０１１．５．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願日】平成２３年５月３１日（２０１１．５．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]