説明

検索システム、判定装置、ベクトル構成装置、その方法及びプログラム

【課題】検索用情報の要素集合が検索対象情報に対応する登録用情報の要素集合内に含まれるか否か判定する。
【解決手段】登録用情報の要素をX,…,Xtr、検索用情報の要素をs,…,str


(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式等、f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式等、Pを1以上の整数、式(A)は


と表現し、X,…,Xtrを用いて、式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成し、s,…,strを用いて、式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明はキーワード検索や文書照合のための技術に関し、特に述語論理をベクトル表現し2つのベクトルの内積が0になるか否かを判定することにより、キーワード検索や文書照合を行う検索システム、判定装置、ベクトル構成装置、その方法及びプログラムに関する。
【背景技術】
【0002】
述語論理を表現し2つのベクトルの内積が0になるか否かを判定することにより、キーワードや文書が一致するか否かを判定する従来技術として、非特許文献1及び2が知られている。これらの技術を用いることで、暗号情報に対して内積述語用いて検索タグと検索問い合わせ文(以下、「検索クエリ」という)を生成し、例えば内積該当暗号情報を復号することなくキーワードや文書を検索することができる。この検索技術を利用したものとして内積述語検索可能暗号がある(非特許文献1〜3参照)。
【先行技術文献】
【非特許文献】
【0003】
【非特許文献1】R. Yoshida, S. Oda, and T. Kobayashi. "Public-key encryption with partial matching keyword search", In Symp. on Cryptography and Information Security, 2010.
【非特許文献2】N. Matsuda, M. Hattori, T. Ito, and T. Yoneda. "Secure datacenter systems with hierarchical predicate encryption", In Symp. on Cryptography and Information Security, 2010.
【非特許文献3】R. Yoshida, A. Nagai, and T. Kobayashi. "Hierarchical predicate encryption with keyword search in multi-user setting", In Computer Security Symposium, 2010.
【発明の概要】
【発明が解決しようとする課題】
【0004】
従来技術では、ある長さnの属性ベクトルから検索タグを作成し、そして同じ長さnの述語ベクトルから検索クエリを生成し、それぞれの属性ベクトルと述語ベクトルの内積が0となるか否かを判定することで、暗号情報に対してキーワード検索や文書照合を行う。従来の属性ベクトル及び述語ベクトルの構成方法では、検索しようとする情報(以下、「検索用情報」という、例えば検索しようとするキーワードや照合しようとする文書等)が複数の要素(例えば文字や単語等)からなる場合、検索対象情報に対応する登録用情報の要素の中に、検索用情報の要素が全て登場するか否かを一回の検証(内積)で判定することが難しい。
【0005】
本発明は、述語多項式を用いて集合部分一致検索を行い、検索用情報の要素の集合が検索対象情報に対応する登録用情報の要素の集合内に含まれるか否かを判定する検索システム、判定装置、ベクトル構成装置、その方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【0006】
上記の課題を解決するために、本発明の第一の態様に係る検索システムは、属性ベクトル生成装置と、述語ベクトル生成装置と、判定装置と、からなる。Fを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとする。添え字trはtを意味する。rd,…,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX,…,Xtrとし、検索用情報の要素をs,…,strとする。
【0007】
【数1】

【0008】
とする。f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式(A)は
【0009】
【数2】

【0010】
と表現されるものとする。属性ベクトル生成装置は検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成する。述語ベクトル生成装置は検索用情報の要素の集合s,…,strを用いて、式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成し、判定装置は属性ベクトルと述語ベクトルとの内積が0のとき、検索対象情報に対応する登録用情報中に検索用情報が含まれると判定する。
【0011】
上記の課題を解決するために、本発明の第二の態様に係るベクトル構成装置によれば、少なくとも属性ベクトルまたは述語ベクトルを生成する。Fを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとする。添え字trはtを意味する。rd,…,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX,…,Xtrとする。検索用情報の要素をs,…,strとする。
【0012】
【数3】

【0013】
とする。f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式(A)は
【0014】
【数4】

【0015】
と表現されるものとする。少なくとも検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成するか、または、述語ベクトル生成装置は検索用情報の要素の集合s,…,strを用いて、式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成する。
【0016】
上記の課題を解決するために、本発明の第三の態様に係る検索方法は、属性ベクトル生成ステップと、述語ベクトル生成ステップと、判定ステップと、からなる。Fを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとする。添え字trはtを意味する。rd,…,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX,…,Xtrとする。検索用情報の要素をs,…,strとする。
【0017】
【数5】

【0018】
とする。f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式(A)は
【0019】
【数6】

【0020】
と表現されるものとする。属性ベクトル生成ステップにおいて、検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成する。述語ベクトル生成ステップにおいて、検索用情報の要素の集合s,…,strを用いて、式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成する。判定ステップにおいて、属性ベクトルと述語ベクトルとの内積が0のとき、検索対象情報に対応する登録用情報中に検索用情報が含まれると判定する。
【0021】
上記の課題を解決するために、本発明の第四の態様に係るベクトル構成方法によれば、少なくとも属性ベクトルまたは述語ベクトルを生成する。Fを位数qの有限体とする。検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとする。添え字trはtを意味し、rd,…,rdtrを乱数とする。検索対象情報に対応する登録用情報の要素をX,…,Xtrとする。検索用情報の要素をs,…,strとする。
【0022】
【数7】

【0023】
とする。f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。Pを1以上の整数とする。式(A)は
【0024】
【数8】

【0025】
と表現されるものとする。少なくとも検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成するか、述語ベクトル生成方法は検索用情報の要素の集合s,…,strを用いて、式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成する。
【発明の効果】
【0026】
本発明は、
【0027】
【数9】

【0028】
を満たす属性ベクトルと述語ベクトルを用いて、登録用情報中に検索用情報が含まれるか否かを判定するため、検索用情報が複数の要素からなる場合であっても1回の検証により判定することができるという効果を奏する。
【図面の簡単な説明】
【0029】
【図1】検索システム1の構成例を示すブロック図。
【図2】検索システム1の処理フローを示す図。
【図3】検索システム1の各装置の機能ブロック図。
【図4】検索システム2の構成例を示すブロック図。
【図5】図5Aは管理装置27−1の機能ブロック図、図5Bは管理装置27−(m’+1)の機能ブロック図。
【図6】属性ベクトル生成装置21−uの機能ブロック図。
【図7】判定装置26の機能ブロック図。
【図8】図8Aは保管装置23の機能ブロック図、図5Bは暗号化データベース233内に記憶されるデータ例を示す図。
【図9】述語ベクトル生成装置25−uの機能ブロック図。
【発明を実施するための形態】
【0030】
以下、本発明の実施形態について、説明する。
【0031】
〔定義〕
まず、各実施形態で使用される用語や記号を定義する。
【0032】
行列:「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
【0033】
(・):(・)は・の転置行列を表す。
(・)−1:(・)−1は・の逆行列を表す。
∧:∧は論理積を表す。
∨:∨は論理和を表す。
Z:Zは整数集合を表す。
sec:secはセキュリティパラメータ(sec∈Z,sec>0)を表す。
【0034】
:Fは位数qの有限体を表す。位数qは1以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fの例は素体やそれを基礎体とした拡大体である。
:0は有限体Fの加法単位元(零元)を表す。一般化した加法単位元を0と表す。
:1は有限体Fの乗法単位元を表す。一般化した乗法単位元を1と表す。
δ(i,j):δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1を満たし、i≠jの場合にδ(i,j)=0を満たす。
E:Eは有限体F上で定義された楕円曲線を表す。
,G,G:G,G,Gは位数qの巡回群を表す。巡回群G,Gの具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G=GであってもよいしG≠Gであってもよい。また、巡回群Gの具体例は、有限体Fを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fの代数閉包における1のp乗根からなる有限集合である。
【0035】
なお、本形態では、巡回群G,G上で定義された演算を加法的に表現し、巡回群G上で定義された演算を乗法的に表現する。すなわち、χ∈F及びΩ∈Gに対するχ・Ω∈Gは、Ω∈Gに対して巡回群Gで定義された演算をχ回施すことを意味し、Ω,Ω∈Gに対するΩ+Ω∈Gは、Ω∈GとΩ∈Gとを被演算子として巡回群Gで定義された演算を行うことを意味する。同様に、χ∈F及びΩ∈Gに対するχ・Ω∈Gは、Ω∈Gに対して巡回群Gで定義された演算をχ回施すことを意味し、Ω,Ω∈Gに対するΩ+Ω∈Gは、Ω∈GとΩ∈Gとを被演算子として巡回群Gで定義された演算を行うことを意味する。一方、χ∈F及びΩ∈Gに対するΩχ∈Gは、Ω∈Gに対して巡回群Gで定義された演算をχ回施すことを意味し、Ω,Ω∈Gに対するΩ・Ω∈Gは、Ω∈GとΩ∈Gとを被演算子として巡回群Gで定義された演算を行うことを意味する。
【0036】
n:nは1以上の整数を表す。
ζ:ζは1以上の整数を表す。ζの一例は2または3である。
n+ζ:Gn+ζはn+ζ個の巡回群Gの直積を表す。
n+ζ:Gn+ζはn+ζ個の巡回群Gの直積を表す。
,g,g:g,g,gは巡回群G,G,G,Gの生成元を表す。
V:Vはn+ζ個の巡回群Gの直積からなるn+ζ次元のベクトル空間を表す。
:Vはn+ζ個の巡回群Gの直積からなるn+ζ次元のベクトル空間を表す。
e:eは直積Gn+ζと直積Gn+ζとの直積Gn+ζ×Gn+ζを巡回群Gに写す非退化な双線形写像(bilinearmap)を表す。双線形写像eは、巡回群Gのn+ζ個の元γβ(β=1,…,n+ζ)と巡回群Gのn+ζ個の元γβ(β=1,…,n+ζ)とを入力とし、巡回群Gの1個の元を出力する。
【0037】
e:G1n+ζ×G2n+ζ→GT (1)
双線形写像eは以下の性質を満たす。
【0038】
[双線形性]全てのΓ∈Gn+ζ,Γ∈Gn+ζ及びν,κ∈Fについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ12)ν・κ (2)
【0039】
[非退化性]全てのΓ∈Gn+ζ,Γ∈Gn+ζを巡回群Gの単位元に写すものではない。
【0040】
[計算可能性]あらゆる
Γ1∈G1n+ζ2∈G2n+ζ (3)
についてe(Γ,Γ)を効率的に計算するアルゴリズムが存在する。
【0041】
本形態では、巡回群Gと巡回群Gとの直積G×Gを巡回群Gに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT (4)
を用いて双線形写像eを構成する。本形態の双線形写像eは、巡回群Gのn+ζ個の元γβ(β=1,…,n+ζ)からなるn+ζ次元ベクトル(γ,…,γn+ζ)と、巡回群Gのn+ζ個の元γβ(β=1,…,n+ζ)からなるn+ζ次元ベクトル(γ,…,γn+ζ)との入力に対し、巡回群Gの1個の元
e=Πβ=1n+ζPair(γββ*) (5)
を出力する。
【0042】
なお、双線形写像Pairは、巡回群Gの1個の元と巡回群Gの1個の元との組を入力とし、巡回群Gの1個の元を出力するものであり、以下の性質を満たす。
【0043】
[双線形性]全てのΩ∈G,Ω∈G及びν,κ∈Fについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω12)ν・κ (6)
【0044】
[非退化性]全ての
Ω1∈G12∈G2 (7)
を巡回群Gの単位元に写すものではない。
【0045】
[計算可能性]あらゆるΩ∈G,Ω∈GについてPair(Ω,Ω)を効率的に計算するアルゴリズムが存在する。
【0046】
なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである(例えば、参考文献1及び2等参照)。
(参考文献1)Alfred. J. Menezes,"ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS",ISBN0-7923-9368-6,pp. 61-81
(参考文献2)"RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems"
(i=1,…,n+ζ):aは巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルaの一例は、κ・g∈Gをi次元目の要素とし、残りのn個の要素を巡回群Gの単位元(加法的に「0」と表現)とするn+ζ次元の基底ベクトルである。この場合、n+ζ次元の基底ベクトルa(i=1,…,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
【0047】
a1=(κ1・g1,0,0,…,0)
a2=(0,κ1・g1,0,…,0) (8)

an+ζ=(0,0,0,…,κ1・g1)
【0048】
ここで、κは加法単位元0以外の有限体Fの元からなる定数であり、κ∈Fの具体例はκ=1である。基底ベクトルaは直交基底であり、巡回群Gのn+ζ個の元を要素とする全てのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルa(i=1,…,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルaはベクトル空間Vを張る。
【0049】
(i=1,…,n+ζ):巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルaの一例は、κ・g∈Gをi次元目の要素とし、残りのn個の要素を巡回群Gの単位元(加法的に「0」と表現)とするn+ζ次元の基底ベクトルである。この場合、基底ベクトルa(i=1,…,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
【0050】
a1*=(κ2・g2,0,0,…,0)
a2*=(0,κ2・g2,0,…,0) (9)

an+ζ*=(0,0,0,…,κ2・g2)
【0051】
ここで、κは加法単位元0以外の有限体Fの元からなる定数であり、κ∈Fの具体例はκ=1である。基底ベクトルaは直交基底であり、巡回群Gのn+ζ個の元を要素とする全てのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルa(i=1,…,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルaはベクトル空間Vを張る。
【0052】
なお、基底ベクトルaと基底ベクトルaとは、0を除く有限体Fの元τ=κ・κについて
e(ai,aj*)=gTτ・δ(i,j) (10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係から、
e(ai,aj*)=Pair(κ1・g12・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(a,a)=Πi=1n+ζPair(a,a)の右辺は、Pair(κ・g,κ・g)を含まず、Pair(κ・g,0)とPair(0,κ・g)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g,0)=Pair(0,g)=Pair(g,gを満たす。そのため、i≠jの場合には、
e(ai,aj*)=e(g1,g2)0=gT0
を満たす。
【0053】
特に、τ=κ・κ=1である場合(例えば、κ=κ=1の場合)、
e(ai,aj*)=gTδ(i,j) (11)
を満たす。ここで、g=1は巡回群Gの単位元であり、g=gは巡回群Gの生成元である。この場合、基底ベクトルaと基底ベクトルaとは双対正規直交基底であり、ベクトル空間Vとベクトル空間Vとは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間(DPVS:Dual Paring Vectorspace)〕である。
【0054】
A:基底ベクトルa(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルa(i=1,…,n+ζ)が式(8)によって表現される場合、行列Aは、
【0055】
【数10】

となる。
【0056】
:基底ベクトルa(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルa(i=1,…,n+ζ)が式(9)によって表現される場合、行列Aは、
【0057】
【数11】

となる。
【0058】
X:有限体Fの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaの座標変換に用いられる。行列Xのi行j列(i=1,…,n+ζ,j=1,…,n+ζ)の要素をχi,j∈Fとすると、行列Xは、
【0059】
【数12】

となる。なお、行列Xの各要素χi,jを変換係数と呼ぶ。
【0060】
:Xは行列Xの逆行列の転置行列X=(X−1を表す。基底ベクトルaの座標変換に用いられる。行列Xのi行j列の要素をχi,j∈Fとすると、行列Xは、
【0061】
【数13】

となる。なお、行列Xの各要素χi,jを変換係数と呼ぶ。
【0062】
この場合、n+ζ行n+ζ列の単位行列をIとするとX・(X=Iを満たす。すなわち、単位行列
【0063】
【数14】

に対し、
【0064】
【数15】

を満たす。ここで、n+ζ次元ベクトル
χi=(χi,1,…,χi,n+ζ) (18)
χj→*=(χj,1*,…,χj,n+ζ*) (19)
を定義する。すると、式(17)の関係から、n+ζ次元ベクトルχとχ→*との内積は、
χi・χj→*=δ(i,j) (20)
となる。
【0065】
:bは巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルa(i=1,…,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbは、
bij=1n+ζχi,j・aj (21)
の演算によって得られる。例えば、基底ベクトルa(j=1,…,n+ζ)が式(8)によって表現される場合、基底ベクトルbの各要素をそれぞれ列挙して表現すると、以下のようになる。
【0066】
bi=(χi,1・κ1・g1i,2・κ1・g1,…,χi,n+ζ・κ1・g1) (22)
巡回群Gのn+ζ個の元を要素とする全てのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルb(i=1,…,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbは前述のベクトル空間Vを張る。
【0067】
:bは巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルa(i=1,…,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbは、
bi*j=1n+ζχi,j*・aj* (23)
の演算によって得られる。例えば、基底ベクトルa(j=1,…,n+ζ)が式(9)によって表現される場合、基底ベクトルbの各要素をそれぞれ列挙して表現すると、以下のようになる。
【0068】
bi*=(χi,1*・κ2・g2i,2*・κ2・g2,…,χi,n+ζ*・κ2・g2) (24)
となる。巡回群Gのn+ζ個の元を要素とする全てのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルb(i=1,…,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbは前述のベクトル空間Vを張る。
【0069】
なお、基底ベクトルbと基底ベクトルbとは、0を除く有限体Fの元τ=κ・κについて
e(bi,bj*)=gTτ・δ(i,j) (25)
を満たす。すなわち、式(5)(20)(22)(24)の関係から、
【0070】
【数16】

【0071】
を満たす。特に、τ=κ・κ=1である場合(例えば、κ=κ=1の場合)、
e(bi,bj*)=gTδ(i,j) (26)
を満たす。この場合、基底ベクトルbと基底ベクトルbとは、双対ペアリングベクトル空間(ベクトル空間Vとベクトル空間V)の双対正規直交基底である。
【0072】
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルa及びaや、式(21)(23)で例示したもの以外の基底ベクトルb及びbを用いてもよい。
【0073】
B:Bは基底ベクトルb(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列。B=X・Aを満たす。例えば、基底ベクトルbが式(22)によって表現される場合、行列Bは、
【0074】
【数17】

となる。
【0075】
:Bは基底ベクトルb(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B=X・Aを満たす。例えば、基底ベクトルb(i=1,…,n+ζ)が式(24)によって表現される場合、行列Bは、
【0076】
【数18】

となる。
【0077】
〔内積述語暗号方式〕
次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。
【0078】
[内積と論理式の真理値との関係]
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
【0079】
まず、「xがηである」という命題1と「xがηである」という命題2との論理和(x=η)∨(x=η)を
(x11)・(x22) (29)
という多項式で表現する。すると、各真理値と式(29)の関数値との関係は以下のようになる。
【0080】
【表1】

【0081】
[表1]から分かるように、論理和(x=η)∨(x=η)が真である場合、式(29)の関数値は0になり、論理和(x=η)∨(x=η)が偽である場合、式(29)の関数値は0以外の値となる。すなわち、論理和(x=η)∨(x=η)が真であることと、式(29)の関数値が0となることとは等価である。よって、論理和は式(29)で表現できる。
【0082】
また、「xがηである」という命題1と「xがηである」という命題2との論理積(x=η)∧(x=η)を
ι1・(x11)+ι2・(x22) (30)
という多項式で表現する。但し、ι及びιは乱数である。すると、真理値と式(30)の関数値とは以下の関係となる。
【0083】
【表2】

【0084】
[表2]から分かるように、論理積(x=η)∧(x=η)が真である場合、式(30)の関数値は0になり、論理積(x=η)∧(x=η)が偽である場合、式(30)の関数値は0以外の値となる。すなわち、論理積(x=η)∧(x=η)が真であることと、式(30)の関数値が0となることとは等価である。よって、論理積は式(30)で表現できる。
【0085】
以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式{(x=η)∨(x=η)}∧(x=η)∧(x=η)は、多項式
ι1・{(x11)・(x22)}+ι2・(x33)+ι3・(x44) (31)
で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。
【0086】
述語多項式は2つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と1とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式(31)の述語多項式は、各項の不定元成分と1を各要素とするベクトル(x・x,x,x,x,x,1)と、各項の係数成分を各要素とするベクトル(ι,−ι・η,−ι・η,ι,−ι・η+ι,ι・η・η−ι・η)との内積に等しい。
【0087】
そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と1とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。
【0088】
内積述語暗号方式では、上述の各項の不定元成分と1を各要素とするベクトル(以下、「属性ベクトル」という)及び各項の係数成分を各要素とするベクトル(以下、「述語ベクトル」という)の何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw=(w1,…,)とし、復号鍵に埋め込まれるベクトルをv=(v1,…,)とする。
【0089】
[内積述語暗号方式の基本構成]
内積述語暗号方式で鍵カプセル化メカニズムKEM(Key Encapsulation Mechanisms)を構成する例を示す。この構成はSetup,GenKey,Enc,Decを含む。
【0090】
《Setup:セットアップ》
−入力:セキュリティパラメータsec
−出力:マスタ鍵情報MSK,公開パラメータPK
Setupの一例では、まず、セキュリティパラメータsecをnとして、n+ζ次元の基底ベクトルa(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列Aと、基底ベクトルa(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列Aと、座標変換のためのn+ζ行n+ζ列の行列X,Xとが選択される。次に、式(21)に従って座標変換されたn+ζ次元の基底ベクトルb(i=1,…,n+ζ)が算出され、式(23)に従って座標変換されたn+ζ次元の基底ベクトルb(i=1,…,n+ζ)が算出される。そして、基底ベクトルb(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列Bがマスタ鍵情報MSKとして出力され、ベクトル空間V,V、基底ベクトルb(i=1,…,n+ζ)を要素とするn+ζ行n+ζ列の行列B、セキュリティパラメータsec、有限体F、楕円曲線E、巡回群G,G,G、生成元g,g,g、双線形写像eなどが公開パラメータPKとして出力される。
【0091】
《GenKey:復号鍵生成》
−入力:マスタ鍵情報MSK,ベクトルv
−出力:ベクトルvに対応する復号鍵D
GenKeyの一例では、まず、有限体Fから元σ,σι−n∈Fが選択される。そして、マスタ鍵情報MSKである行列Bを用い、ベクトルvに対応する復号鍵
D*=σ・(Σμ=1nvμ・bμ*)+Σι=n+1n+ζ’σι-n・bι*∈G2n+ζ’ (32)
が生成され、出力される。但し、σ,σι−nは乱数などの変数や定数などであり、ζ’≦ζである(例えばζ=3,ζ’=2)。またΣι=n+1n+ζ’σι−nはシステムで共有される定数値とされる。以下では
Σι=n+1n+ζ’σι-n=1F (33)
とされた例を説明する。これは本発明を限定しない。
【0092】
《Enc:暗号化》
−入力:公開パラメータPK,ベクトルw,平文mes
−出力:暗号文(C,C
Encの一例では、行列Bなどの公開パラメータPKと、有限体Fの元である乱数υ,υ,…,υζと、ベクトルwとを用い、暗号文
C10・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-n・bμ∈G1n+ζ (34)
が生成される。但し、
υ1=…=υζ’ (35)
を満たす(例えばζ’=2のときにはυ=υ)。また、gτ・υ1を共通鍵Kとし、所定の共通鍵暗号方式(第2暗号方式)に則って平文mesの暗号文Cが生成される。暗号文Cの一例は、
C2=gTτ・υ1・mes(36)
である。添え字のυ1はυを意味する。前述のように定数τの一例はτ=1である。生成された暗号文(C,C)は出力される。
【0093】
《Dec:復号》
−入力:ベクトルvに対応する復号鍵D,暗号文(C,C
−出力:復号値mes’
Decの一例では、まず、暗号文Cと復号鍵Dとが式(1)の双線形写像eに入力され、その演算結果を共通鍵K=e(C,D)とし、以下のように復号値mes’が求められる。
【0094】
mes’=C2/e(C1,D*)∈GT (37)
ここで、式(2)(25)(33)(35)の性質から、
【0095】
【数19】

を満たす。
【0096】
内積w・v=0であれば、式(38)は、
【0097】
【数20】

を満たす。式(36)(37)(39)から、内積w・v=0であればmes’=mesとなり、正しく復号されることが分かる。
【0098】
[階層的内積述語暗号方式の基本構成]
階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。但し、これは本発明を限定するものではない。
【0099】
《前提》
深さdの属性空間の階層フォーマットを以下の式によって定義する。但し、dは1以上n以下の整数である。
【0100】
ξ=(n,d;ξ1,…,ξd)(0=ξ01<…<ξd=n) (40)
有限体Fの元を要素とするξω−ξω−1(ω=1,…,d)次元のベクトル(零ベクトルを除く)を階層ωに対応するベクトル
【0101】
【数21】

【0102】
とし、階層1から階層m(m≦d)までに対応するベクトルを(w,…,w)とする。有限体Fの元を要素とするξω−ξω−1次元(ω=1,…,d)のベクトル(零ベクトルを除く)を階層ωに対応するベクトル
【0103】
【数22】

とし、階層1から階層mまでに対応するベクトルを(v,…,v)とする。
【0104】
《Setup:セットアップ》
−入力:セキュリティパラメータsec
−出力:階層フォーマットξ,マスタ鍵情報MSK,公開パラメータmpk
Setupの一例では、セキュリティパラメータsecの単調増加関数値をnとし、階層フォーマットξ=(n,d;ξ,…,ξ)が定められる。また、この例ではζ=3とし、n+3次元の基底ベクトルa(i=1,…,n+3)を要素とするn+3行n+3列の行列Aと、基底ベクトルa(i=1,…,n+3)を要素とするn+3行n+3列の行列Aと、座標変換のためのn+3行n+3列の行列X,Xとが選択される。次に、式(21)に従って座標変換されたn+3次元の基底ベクトルb(i=1,…,n+3)が算出され、式(23)に従って座標変換されたn+3次元の基底ベクトルb(i=1,…,n+3)が算出される。
【0105】
この例では、基底ベクトル(b,…,b,bn+1,bn+2,bn+3)と行列Xとがマスタ鍵情報MSKとして出力され、基底ベクトル(b,…,b,bn+1+bn+2,bn+3)、ベクトル空間V,V、セキュリティパラメータsec、有限体F、楕円曲線E、巡回群G,G,G、生成元g,g,g、双線形写像eなどが公開パラメータmpkとして出力される。
【0106】
《GenKey:鍵情報生成》
−入力:マスタ鍵情報MSK,公開パラメータmpk,ベクトル(v,…,v
−出力:ベクトル(v,…,v)に対応する鍵情報k
GenKeyの一例では、まず、有限体Fから元σα,ω,Ψ,Φα∈F(α=0,…,m+1,ξ+1,…,n;ω=1,…,m)が任意に選択される。この例では、これらとマスタ鍵情報MSKである基底ベクトル(b,…,b,bn+1,bn+2,bn+3)とベクトル(v,…,v)とを用い、ベクトル(v,…,v)に対応する鍵情報
【0107】
【数23】

が生成されて出力される。但し、
【0108】
【数24】

である。
【0109】
《Delegate(m’):鍵情報生成委譲》
−入力:公開パラメータmpk,鍵情報km’,ベクトルvm’+1
−出力:ベクトル(v,…,vm’+1)に対応する鍵情報km’+1
階層的内積述語暗号方式では、マスタ鍵情報MSKを用いることなく、公開パラメータmpk,鍵情報km’,ベクトルvm’+1からベクトル(v,…,vm’+1)に対応する鍵情報km’+1を生成できる。但し、m’=1,…,d−1である。
【0110】
Delegate(m’)の一例では、有限体Fから元σ’α,ω,Ψ’,Φ’α∈F(α=0,…,m’+2,ξm’+1+1,…,n;ω=1,…,m’+1)が任意に選択される。この例では、これらと鍵情報km’とベクトルvm’+1と用い、ベクトル(v,…,vm’+1)に対応する鍵情報
【0111】
【数25】

が生成されて出力される。但し、
【0112】
【数26】

である。
【0113】
《Enc:暗号化》
−入力:公開パラメータmpk,ベクトル(w,…,w),平文mes
−出力:暗号文(C,C
Encの一例では、まず、有限体Fから任意の元υ,…,υ,υn+3,υが選択される。そして、これらと公開パラメータmpkとベクトル(w,…,w)とを用い、暗号文
【0114】
【数27】

が生成される。また、gτ・υを共通鍵Kとし、所定の共通鍵暗号方式(第2暗号方式)に則って平文mesの暗号文Cが生成される。暗号文Cの一例は、
C2=gTτ・υ・mes(52)
である。なお、前述のように定数τの一例はτ=1である。その後、以上のように生成された暗号文(C,C)が出力される。
【0115】
《Dec:復号》
−入力:公開パラメータmpk,ベクトル(v,…,v)に対応する鍵情報k,暗号文(C,C
−出力:復号値mes’
Decの一例では、
mes’=C2/e(C1,km,0*) (53)
によって復号値mes’を計算する。
【0116】
暗号文Cと鍵情報kのkm,0とが式(1)の双線形写像e(この例ではζ=3)に入力されると、式(2)(25)の性質から、
【0117】
【数28】

【0118】
を満たす。なお、σω及びσは有限体Fの元である。Delegate(m’)がなされることなく鍵情報kが生成された場合にはσω=σ0,ωである。Delegate(m’)が1回以上なされた場合には、GenKeyに使用された有限体Fの元σα,ωやDelegate(m’)時に使用された有限体Fの元σ’α,ωやΦ’αに応じてσωの値が定まる。ここで、全てのω=1,…,mについて内積vω・wω=0であれば、式(54)は、
e(C1,km,0*)=gTτ・υ (55)
と変形できる。式(52)(53)(55)より、全てのω=1,…,mについて内積vω・wω=0である場合にmes’=mesとなり、正しく復号がなされることが分かる。
【0119】
<第一実施形態>
以下に説明する情報処理では、文字列を含む情報が暗号化の対象となるが、暗号処理の実際では、人間が意味内容を認識可能なテキスト情報である文字そのものが暗号化されるのではなく、例えば当該文字に割り当てられている文字コード情報(EUC-JP、Shift_JIS、UTF-8などのバイト表現)が暗号化の対象となる。従って、後述の説明において例えば変数Xに文字wを代入ないし設定する(X=w)とは、テキスト情報としての文字wを変数Xに代入ないし設定することではなく、文字コード情報としての文字wを変数Xに代入ないし設定することと理解するべきである。このことは暗号処理の常套手段であるから、その詳細な説明を省略する。また、この明細書では、ベクトルの表記として慣用的にベクトルであることを示す記号“→”を省略している場合がある。従って、或る記号がベクトルであるか否かは明細書全体の記載から合理的に理解されたい。
【0120】
<ポイント>
式(32)等で用いる述語ベクトルv及び式(34)等で用いる属性ベクトルwの構成方法が従来の方法と異なる。まず、従来技術の述語ベクトル及び属性ベクトルの構成方法について説明する。
【0121】
従来の内積述語検索可能暗号(非特許文献1及び2参照)は、属性ベクトルや述語ベクトルをキーワードに見立てて、属性ベクトルを使って作成された暗号文が述語ベクトルを使って復号できるとき、暗号文中にキーワードが存在すると判定する暗号文検索技術である。この場合、属性ベクトルは最大文字数をrとして、述語論理に最大d−1回の論理和が許される場合に、r個の属性変数X,…,Xからなる次数d以下の単項式を全て辞書式順序で並べた順に各成分とした変数ベクトルXr,dに登録用キーワードに含まれる文字を設定して得られるベクトルである。また、この場合、述語ベクトルは述語論理を属性変数と検索用キーワードに含まれる文字を用いて多項式で表現した述語多項式の係数を、変数ベクトルXr,dの成分に対応する順に並べたものを成分として持つベクトルである。
【0122】
本実施形態では集合部分一致検索が可能になる述語多項式ppm1を与える。集合部分一致検索を行うことで、検索用情報が複数の要素からなる場合であっても1回の検証により判定することができる。さらに変形例1ではその効率的な表現を与える。そのために、まずキーワードの部分一致検索(非特許文献1参照)を表現する多項式とそのベクトル長を説明する。キーワード部分一致検索は検索用キーワードに部分的に一致するもの全てを見つける検索である。集合部分一致検索と異なる点は、キーワード部分一致検索は文字の順序(ABBという文字列の検索は、{A、B、B}={A、B}をA⇒B⇒Bの順に含まなければならない)含めて一致したものを検索するが、集合部分一致検索は{A、B、B}={A、B}を含むものが検索されることである。
【0123】
従来技術で用いる部分一致検索は、検索用キーワードが、登録用キーワードに当てはまりうる全てのパターンを述語で記述することで実現できる。例えば、登録用キーワードの文字数t=6、検索用キーワードが「ABCA」である時、検索用キーワードの文字数t=4であることから、登録用キーワードが検索用キーワードの含むその含み方は全部でt−t+1=3通りである。具体的には、「ABCA**」、「*ABCA*」、「**ABCA」の3通りである。但し、「*」は任意の文字を表す。従って、これらを論理和でつないだ述語論理を考えればよい。このことから、部分一致検索のための述語多項式ppm(X,…,Xtr)は、
【0124】
【数29】

【0125】
と書ける(但し、rdi,jは乱数を表す)。この述語多項式の単項式の数nは
tr−ts+1≦n≦tr−ts+1ts
である。但し、添え字のtr、tsはそれぞれt、tを意味し、tr−ts+1tsはt−t+1個のものから重複してt個のものを選ぶ組み合わせの総数を表す。従来技術の上記式(61)を用いて、集合部分一致検索を実現しようとすると、検索用キーワードを構成する各文字「A」、「B」、「C」をそれぞれ、検索用キーワードとして、部分一致検索を行い、全ての検索においてヒットした登録用キーワードを検索結果とすると考えられる。登録用キーワードの文字の中に、検索用キーワードの文字が全て登場するか否かを一回の検証(内積)で判定することができず、演算時間が長くなる。
【0126】
一方、第一実施形態では、集合部分一致検索が可能になる述語多項式ppm1を与える。Fを位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとし、rd,…,rdtrを乱数とする。
【0127】
【数30】

【0128】
pm1は登録用キーワードと検索用キーワードの格納領域(変数)の長さをどちらもtとしている。登録用キーワード及び検索用キーワードの文字数がtr未満だった場合、記号⊥に対応する文字をそれ以降に格納していくことで対応する。ppmを利用して達成する部分一致検索は、文字列s…stsが文字列X…Xtrのどこかに含まれることを文字の順序を含めてチェックする検索であったが、ppm1を利用して達成する検索は、s…strを文字列としてまとめてとらえるのではなく、文字s、…、stsと一つ一つ個別に、文字列X…Xtrの中に含まれているかどうかをチェックするものである。文字s、…、strが順序に関係なく、文字列X…Xtrの中に全て含まれる場合には、ppm1=0となる。文字列として含まれている場合は、個別の文字として含まれている場合に含まれるので、ppm1による検索結果はppmを含む。ppm1は単純に展開すると、
【0129】
【数31】

【0130】
となる。式(63)は、X,…,Xtrの基本対称式の線形和に出てくる全ての単項式と同様の単項式((2tr−1)個)と、定数項(1個)とを持つ。よって、式(63)は2tr個の単項式を持つ。なお、X,…,Xtrのk次の基本対称式をYとすると、
【0131】
【数32】

【0132】
であり、具体的には、
=−(X+X+…+Xtr
=X+X+…+Xtr+X+…+Xtr−1tr

tr=(−1)tr…Xtr
である。なお、X,…,Xtrの基本対称式の線形和とは、t個のk次の基本対称式Yの線形和である。本実施形態では、各単項式の値または定数1を要素とする属性ベクトルwを構成し、各単項式の係数の値または定数1に対応する値aを要素とする述語ベクトルvを構成する。つまり、
=(1,X,X,…,Xtr,X,…,X…Xtr
=(a,a,…,a(2^tr)−1
である。但し、(C^D)はCのD乗を表す。よって、各ベクトルの次元は2tr次元である。内積述語暗号検索可能暗号の検索時間は
演算時間=各種暗号基本演算(ペアリング演算等)×ベクトルの次元×タグの数(文書数)
である。部分一致検索におけるベクトルの次元数n(但し、2tr−ts+1≦n≦tr−ts+1ts)はtr−ts+1tsに近い値をとることとなり、tの値が大きくなるにつれて、その傾向は顕著になると考えられ、本実施形態の次元数2trよりも大きくなる。そのため、tが大きくなるにつれて、本実施形態の検索システムのほうが、従来技術に比べ、検索時間が短くなる。
【0133】
<検索システム1>
以下、図1を用いて第一実施形態に係る検索システム1を説明する。検索システム1は、上述の述語多項式ppm1を内積述語暗号に適用する(参考文献3及び4参照)。
(参考文献3):T. Okamoto and K. Takashima. "Hierarchical predicate encryption for inner-products", In ASIACRYPT, 2009, pp. 214-231,
(参考文献4):A. B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters. "Fullysecure functional encryption: Attribute-based encryption and (hierarchical)
inner product encryption", In EUROCRYPT, 2010, pp. 62-91
検索システム1は、暗号化されたデータベースの検索が可能な検索可能暗号システムである。この実施形態の検索システム1は、図1に示すように、属性ベクトル生成装置11と、述語ベクトル生成装置15と、判定装置16と、保管装置13とを少なくとも含んで構成される。これらの各装置は、例えばインターネットである通信網12を介して相互に通信可能とされている。
【0134】
検索システム1における検索処理を、図2を参照しながら叙述する。各装置の機能構成については、図3を参照されたい。
【0135】
<事前処理>
前述したSetupが実行され、マスタ鍵情報msk,公開パラメータmpkが定められる。マスタ鍵情報mskは、マスタ鍵格納部153に安全に格納され、属性ベクトル生成装置11、述語ベクトル生成装置15、判定装置16が、公開パラメータmpkを用いた処理が可能なように構成される。
【0136】
<暗号情報及び検索タグの登録処理>
まず、属性ベクトル生成装置11の暗号情報生成部111は、文字列を含む情報(以下「検索対象情報」という)Texttiを暗号化して暗号情報C(Textti)を得る(ステップS2)。この暗号方式(Enc,Dec)に限定はない。この暗号方式として、例えば共通鍵暗号方式や公開鍵暗号方式を利用できる。共通鍵暗号方式の場合、検索対象情報Texttiは、属性ベクトル生成装置11と述語ベクトル生成装置15との間で共有される共通鍵で暗号化される。また、公開鍵暗号方式の場合、検索対象情報Texttiは述語ベクトル生成装置15の公開鍵で暗号化される。つまり、暗号情報C(Textti)を得るための情報処理は、暗号化アルゴリズムEncに従う。
【0137】
生成された暗号情報C(Textti)は、検索対象情報Texttiに対応する登録用キーワードXとともに、登録キーワード格納部114に格納される。登録用キーワードXは、例えば、ユーザによって予め設定される、検索対象となるキーワードであり、検索対象情報Texttiに含まれるキーワードまたはキーワードの集合である。
【0138】
次に、属性ベクトル生成装置11の属性ベクトル生成部113は、登録キーワード格納部114から、検索対象情報Texttiに対応する登録用キーワードXを抽出し、登録用キーワードXを表す属性ベクトルwが以下の関係を満たすように生成する。この属性ベクトルwは、検索において、文書等を検索するためのインデックスとしての役割を持つ。なお、t文字の登録用キーワードXのi番目の文字をX(1≦i≦t)とし、登録用キーワードXの文字列をX,…,X,…,Xtrとする。また、後述するt文字の検索用キーワードsのi番目の文字をs(1≦i≦t)とし、検索用キーワードsの文字列をs,…,s,…,strとする。また、rd,…,rdtrを乱数とし、図示しない乱数生成部により生成される。
【0139】
【数33】

【0140】
但し、述語多項式ppm1は登録用キーワード及び後述する検索用キーワードの格納領域(変数)の長さをtとする。各キーワードの長さがt未満の場合、記号⊥に対応する文字をtに達するまで格納することで対応する。また、登録用キーワードのt番目の格納領域には記号⊥に対応する文字を格納する。つまり、登録用キーワードは実質的には最大(t−1)文字である。登録用キーワードに記号⊥に対応する文字が含まれていない場合、登録用キーワードの文字の中に、t未満の検索用キーワードに含まれる全ての文字が含まれている場合であっても、記号⊥に対応する文字が含まれていないために、検索されないことが生じうるが、このような構成とすることで、漏れを防ぐことができる。
【0141】
式(62)の述語多項式ppm1を単純に展開すると、
【0142】
【数34】

となる。本実施形態では、各単項式の値または定数1を要素とする属性ベクトルwを構成する。つまり、属性ベクトル
=(1,X,X,…,Xtr,X,…,X…Xtr) (64)
を生成する(ステップS3)。つまり、属性ベクトル生成装置11の属性ベクトル生成部113は、各単項式X,X,…,Xtr,X,…,X…Xtrに対し、具体的な登録用キーワードXの文字X,…,Xtrを与え、各単項式の値を計算し、計算結果を求める。この計算結果と定数1を要素とする属性ベクトルを生成する。属性ベクトル生成部113は、生成した属性ベクトルwを検索タグ生成部112へ出力する。
【0143】
検索タグ生成部112は、公開パラメータPKと属性ベクトルwを入力とし、式(34)により、暗号文Cを生成する。
【0144】
C10・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-n・bμ∈G1n+ζ (34)
なお、式(34)において、乱数ν,ν,…,νζは、検索タグ生成部112内部の図示しない乱数生成部により生成する。なお式(34)において、n=2trである。
【0145】
さらに、検索タグ生成部112は、公開パラメータPKと登録用キーワードXを入力とし、式(36)により、暗号文Cを生成する。
【0146】
C2=gTτ・υ1・mes(36)
なお、式(36)において、mes=Xである。
【0147】
検索タグ生成部112は、上述の処理により得られた暗号文C,Cの組合せを検索タグTagti=(C,C)として出力する(ステップS4)。
【0148】
属性ベクトル生成装置11の送信部118は、暗号情報C(Textti)と検索タグTagtiとを一組として保管装置13へ送信する(ステップS5)。保管装置13の受信部139は、暗号情報と検索タグとの組(Textti,Tagti)を受信する(ステップS6)。保管装置13の記憶部131には、通常、属性ベクトル生成装置11から受信した複数の(Textti,Tagti)が記憶されている。さらに言えば、保管装置13の記憶部131には、一般的に、複数の属性ベクトル生成装置から受信した複数の(Textti,Tagti)が記憶されている。各組(Textti,Tagti)には固有のインデックスが割り当てられている。
【0149】
<復号鍵(検索クエリ)生成処理>
述語ベクトル生成装置15は、検索用キーワードsを入力されると、述語ベクトル生成部151において、検索用キーワードsを表す述語ベクトルvを以下の関係を満たすように生成する。なお、この述語ベクトルvは検索において、文書等を検索するためのクエリの役割を持つ。
【0150】
【数35】

pm1を単純に展開すると、
【0151】
【数36】

【0152】
となり、本実施形態では、定数1に対応する値aと各単項式の係数の値を要素とする述語ベクトルvを構成する。つまり、述語ベクトル
【0153】
【数37】

【0154】
を生成する(S7)。式(62)から各単項式の係数は、sの冪乗(つまりs(但し、0≦k≦t))と乱数rdの積の和からなる。つまり、述語ベクトル生成装置15の述語ベクトル生成部151は、定数1に対応する値a、各単項式の係数a,…,a(2^tr)−1に対し、具体的な検索用キーワードsの文字s,…,strを与え、さらに乱数rdを生成し、これらの値を用いて、値a及び各係数を計算し、計算結果を求める。この計算結果を要素とする述語ベクトルを生成する。
【0155】
述語ベクトル生成装置15の鍵生成部152は、マスタ鍵情報MSKと述語ベクトルvを入力とし、式(32)により、述語ベクトルvに対応する復号鍵Dを生成する(ステップS8)。
【0156】
D*=σ・(Σμ=1nvμ・bμ*)+Σι=n+1n+ζ'σι-n・bι*∈G2n+ζ’ (32)
但し、乱数や定数等であるσ、σι-nは鍵生成部152において、生成されるか、または、予め鍵生成部152に記憶されているものとする。
【0157】
述語ベクトル生成装置15の送信部158は、復号鍵Dを判定装置16へ送信する(ステップS9)。
【0158】
<判定処理>
判定装置16の受信部169は、復号鍵Dを受信する(ステップS10)。
【0159】
判定装置16の制御部165は、送信部168を制御して、保管装置13に対して保管装置13の記憶部131に記憶されている全ての検索タグを判定装置16へ送信するように要求し、これを受けて保管装置13の送信部138は記憶部131に記憶されている全ての検索タグをインデックスとともに判定装置16へ送信し、判定装置16の受信部169がこれらを受信する(ステップS11)。
【0160】
判定装置16の復号判定部161は、全ての検索タグを復号判定処理の対象とし、復号鍵Dを用いて検索タグを個別に復号して検索が当たりか否かを判定する(ステップS12)。具体的には、復号判定部161は、全ての検索タグについて、式(38)に従って、e(C,D)を求め、式(36)、(37)、(39)から、mes’=mesの成否を判定する(判定処理)。
【0161】
C2=gTτ・υ1・mes(36)
mes’=C2/e(C1,D*)∈GT (37)
【0162】
【数38】

【0163】
【数39】

【0164】
内積w・v=0であれば、mes’=mesとなり、登録用キーワードXの文字X,X,…,Xtrの中に、検索用キーワードsの文字s,s,…,strが含まれていることが分かる。
【0165】
判定装置16の送信部168は、mes’=mesが成立した検索タグのインデックスを述語ベクトル生成装置15へ送信する(ステップS13)。
【0166】
述語ベクトル生成装置15の受信部159は、mes’=mesが成立した検索タグのインデックスを受信する(ステップS14)。
【0167】
述語ベクトル生成装置15の制御部155は、送信部158を制御して、保管装置13に対して、保管装置13の記憶部131に記憶されている、判定装置16から受信したインデックスに対応する暗号情報を述語ベクトル生成装置15へ送信するように要求し、これを受けて保管装置13の送信部138は当該インデックスに対応する暗号情報を述語ベクトル生成装置15へ送信し、述語ベクトル生成装置15の受信部159がこれらを受信する(ステップS15)。
【0168】
述語ベクトル生成装置15の復号部156は、必要に応じて、保管装置13から受信した暗号情報C(Textti)を復号して検索対象情報Texttiを得る(ステップS16)。検索対象情報Texttiを得るための情報処理は、属性ベクトル生成装置11の暗号情報生成部111が実施した暗号方式(Enc,Dec)に対応する復号アルゴリズムDecに従う。
【0169】
<効果>
このような構成とすることで、複数の文字からなる検索用キーワードが登録用キーワード内に含まれるか否かを1回の検証により判定することができるという効果を奏する。
【0170】
なお、本実施形態において、登録用情報及び検索用情報の単位をキーワードとし、それぞれの要素を文字としているが、登録用情報の単位を文章とし、登録用情報及び検索用情報の要素を単語としてもよい。これは、例えば検索対象情報が英文等である場合、登録用情報を検索対象情報でもある英文自体とし、その英文の単語を要素として、属性ベクトルを構成し、複数の単語を述語ベクトルとして表現し検索することができる。また例えば和文の場合には、形態素解析等を行うことで同様に登録用情報の単位を文章とし、登録用情報及び検索用情報の要素を単語とすることができる。
【0171】
<変形例1>
第一実施形態と異なる部分を主に説明する。
【0172】
属性ベクトル生成装置11の属性ベクトル生成部113と述語ベクトル生成装置15の述語ベクトル生成部151の処理内容が第一実施形態と異なる。他の処理は第一実施形態と同様である。
【0173】
属性ベクトル生成装置11の属性ベクトル生成部113は、登録キーワード格納部114から、検索対象情報Texttiに対応する登録用キーワードXを抽出し、登録用キーワードXを表すベクトルwが以下の関係を満たすように生成する。
【0174】
【数40】

【0175】
式(62)の述語多項式ppm1を変形して、−X,−X,…,−Xtrのk次基本対称式Yを用いて、属性ベクトルw={Y,Y,…,Y,…,Ytr}を生成する。以下、説明する。
【0176】
【数41】

【0177】
但し、X’=−Xであり、Yは−X,−X,…,−Xtrのk次の基本対称式であり(但し、Y=1とする)、
【0178】
【数42】

【0179】
である。具体的には、
=X+X+…+Xtr
=X+X+…+Xtr+X+…+Xtr−1tr

tr=X…Xtr
である。また、
【0180】
【数43】

である。
【0181】
本変形例の属性ベクトル生成部113では、登録用キーワードXを用いて、式(74)の−X,−X,…,−Xtrのk次の基本対称式Y(但し、Y=1とする)から属性ベクトル
【0182】
【数44】

【0183】
を生成する。つまり、本変形例の属性ベクトル生成部113では、各基本対称式Yに対し、具体的な登録用キーワードXの文字X,…,Xtrを与え、各基本対称式Yの値を計算し、計算結果を求める。Y(=1)とこの計算結果を要素とする属性ベクトルを生成する。
【0184】
また、本変形例の述語ベクトル生成部151では、検索用キーワードsと乱数rd,…,rdtrを用いて、述語ベクトル
【0185】
【数45】

【0186】
を生成する。式(74)から各基本対称式Yの係数は、V(sの冪乗と乱数rdの積の和)である。つまり、述語ベクトル生成部151は、各基本対称式Yの係数Vに対し、具体的な検索用キーワードsの文字s,…,strを与え、さらに乱数rdを生成し、これらの値を用いて、値V及びk次の基本対称式Yに対する係数Vを計算し、計算結果を求める。この計算結果を要素とする述語ベクトルを生成する。
【0187】
<効果>
このような構成とすることで、属性ベクトル及び述語ベクトルの次元数をt+1とすることができる。従来技術や第一実施形態に比べ、ベクトルの次元数を小さくすることができる。なお、tが大きくなるに従い、次元数の差は大きくなる。よって、演算時間が短くなるという効果が得られる。
【0188】
<変形例2>
第一実施形態と異なる部分を主に説明する。
【0189】
属性ベクトル生成装置11の属性ベクトル生成部113と述語ベクトル生成装置15の述語ベクトル生成部151の処理内容が第一実施形態及びその変形例1と異なる。他の処理は第一実施形態またはその変形例1と同様である。
【0190】
属性ベクトル生成装置11の属性ベクトル生成部113は、検索対象情報に対応する登録用情報の要素から重複する要素を削除して属性ベクトルを生成する。
【0191】
また、述語ベクトル生成装置15の述語ベクトル生成部151は、検索用情報の要素から重複する要素を削除して述語ベクトルを生成する。
【0192】
つまり、キーワードが「ABCCBA」の場合、A,B,Cがそれぞれ重複するので、それぞれ重複する要素を削除し、キーワードを「ABC」に変換し、変換後のキーワードを用いて属性ベクトル及び述語ベクトルを作成する。なお、削除した格納領域には記号⊥に対応する文字を格納する。
【0193】
<効果>
このような構成とすることで、属性ベクトル及び述語ベクトルの生成や判定処理の計算量を減らすことができる。なお、集合部分一致検索を行うため、このような構成が可能となるのであって、従来の部分一致検索ではこのような構成とすることはできない。
【0194】
<その他の変形例>
集合部分一致検索が可能になる述語多項式ppm1を与える点がポイントである。よって、必ずしも暗号化されたデータベースの検索が可能な検索可能暗号システムに述語多項式ppm1を用いる必要はない。つまり、暗号化されていないデータベースの検索において、述語多項式ppm1を利用してもよい。この場合、属性ベクトル生成装置11には暗号情報生成部111や検索タグ生成部112は不要であり、述語ベクトル生成装置15には鍵生成部152や復号部156やマスタ鍵格納部153は不要である。保管装置13の記憶部131には暗号化されていない検索対象情報と、検索対象情報に対応する登録用キーワードから得られる属性ベクトルが記憶される。判定装置16は述語ベクトル生成装置15から述語ベクトルを受信し、保管装置13から属性ベクトルを受信する。そして、判定装置16の復号判定部161では属性ベクトルと述語ベクトルの内積が0か否かを判定し、内積が0となる属性ベクトルに対応する検索対象情報を検索結果として述語ベクトル構成装置に送信する。
【0195】
また、少なくとも属性ベクトル生成装置または述語ベクトル生成装置の何れか一方の機能を有する装置をベクトル構成装置と呼ぶ。本実施形態では属性ベクトル生成装置11と述語ベクトル生成装置15は別装置として構成しているが、両方の機能を有するベクトル構成装置として構成してもよい。さらに、本実施形態では、ベクトル構成装置と保管装置、判定装置を別装置としているが、同一装置として構成してもよい。同一装置内の検索システムとして利用することができる。
【0196】
また、集合部分一致検索を用いているため、文字列X…Xtrや文字列s…strの順序を入れ替えて、文字の集合X,…,Xtrやs,…,strを用いて属性ベクトル及び述語ベクトルを生成しても第一実施形態と同様の効果を得ることができる。
【0197】
なお、属性ベクトル及び述語ベクトルは式(62)を満たすものであればよい。ここで、式(62)は、
【0198】
【数46】

【0199】
と表現される。但し、f(X,…,Xtr)を、変数s,…,strを含まない登録用情報の要素X,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。なお、「変数s,…,strを含まない」とは、具体的な値sと同様の値をf(X,…,Xtr)中に含む場合はあるが、検索用情報の要素(変数)としてのs,…,strを含まないことを意味する。例えば、f(X,…,Xtr)は、(1)基本対称式の項、(2)基本対称式の項と定数の積、(3)基本対称式の項または基本対称式の項と定数の積の和(4)定数等として表される。また、f(s,…,str)を変数X,…,Xtrを含まない検索用情報の要素s,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とする。なお、「変数X,…,Xtrを含まない」とは、具体的な値Xと同様の値をf(s,…,str)中に含む場合はあるが、登録用情報の要素(変数)としてのX,…,Xtrを含まないことを意味する。例えば、f(s,…,str)は、(1)sの冪乗(つまりs(但し、0≦k≦t))、(2)sの冪乗と定数の積、(3)sの冪乗またはsの冪乗と定数の積の和(4)定数等として表される。Pを1以上の整数とする。式(81)のf(X,…,Xtr)及びf(s,…,str)は式(62)を満たすように適宜設定される。例えば、式(62)において、t=2の場合、式(62)を展開すると、
【0200】
【数47】

【0201】
となる。例えば、第一実施形態の場合は、f(X,…,Xtr)をXの基本対称式の単項式または定数とし、f(s,…,str)を各単項式の係数または定数に対するsの冪乗と定数の積(rd+rd)とするので、P=4であり、例えば、f(X,X)=1、f(X,X)=−X、f(X,X)=−X、f(X,X)=Xであり、f(s,s)=rd+rd、f(s,s)=rd+rd、f(s,s)=rd+rd、f(s,s)=rd+rdである。よって、
w=(1,-X1,-X2,X1X2)
v=(rd1s12+rd2s22,rd1s1+rd2s2,rd1s1+rd2s2,rd1+rd2)
である。また、例えば、変形例1の場合は、式(74)よりf(X,…,Xtr)を−Xのk次の基本対称式または定数とし、f(s,…,str)を各基本対称式の係数または定数に対するsの冪乗と定数の積(rd+rd)とするので、P=3であり、例えば、f(X,X)=1、f(X,X)=X+X、f(X,X)=Xであり、f(s,s)=rd+rd、f(s,s)=−rd−rd、f(s,s)=rd+rdである。よって、
w=(1,X1+X2,X1X2)
v=(rd1s12+rd2s22,-rd1s1-rd2s2,rd1+rd2)
となる。また、例えば、f(s,…,str)をs(但し、0≦k≦t)とし、f(X,…,Xtr)を各sの係数とすると、P=6であり、例えば、f(s,s)=s、f(s,s)=s、f(s,s)=s、f(s,s)=s、f(s,s)=s、f(s,s)=sであり、f(X,X)=rd、f(X,X)=rd、f(X,X)=−rd−rd、f(X,X)=−rd−rd、f(X,X)=−rd、f(X,X)=rdである。よって、
w=(rd1X1X2,rd2X1X2,-rd1X1-rd1X2,-rd2X1-rd2X2,rd1,rd2)
v=(s10, s20,s1,s2,s12,s22)
となる。前述の通り、f(X,…,Xtr)及びf(s,…,str)は式(62)を満たすように適宜設定されるものであり、例えば、rd等はf(X,…,Xtr)またはf(s,…,str)に含まれればよい。
【0202】
よって、前述の属性ベクトル生成装置は、登録用情報の要素X,…,Xtrを用いて、f(X,…,Xtr)の値を要素とするP次元の属性ベクトルを生成する。つまり、属性ベクトル生成装置は、単項式若しくは多項式または定数であるf(X,…,Xtr)に対し、具体的な登録用情報の要素X,…,Xtrを与え、f(X,…,Xtr)を計算し、計算結果を求める。この計算結果を要素とするP次元の属性ベクトルを生成する。
【0203】
前述の述語ベクトル生成装置は、検索用情報の要素s,…,strを用いて、f(s,…,str)の値を要素とするP次元の述語ベクトルを生成する。つまり、述語ベクトル生成装置は、単項式若しくは多項式または定数であるf(s,…,str)に対し、具体的な検索用情報の要素s,…,strを与え、f(s,…,str)を計算し、計算結果を求める。この計算結果を要素とするP次元の述語ベクトルを生成する。
<第二実施形態>
<検索システム2>
以下、図4を用いて第二実施形態に係る検索システム2を説明する。検索システム2は、上述の述語多項式ppm1を階層的内積述語暗号に適用する(参考文献3及び4参照)。検索システム1は、暗号化されたデータベースの検索が可能な検索可能暗号システムである。
【0204】
図4に例示するように、本形態の検索可能暗号システム2は、管理装置27−m(m=1,…,M)と属性ベクトル生成装置21(u=1,…,U)と判定装置26と保管装置23と述語ベクトル生成装置25(u=1,…,U)とを有する。なお、M及びUはそれぞれ1以上の整数である。また、管理装置27−mは、検索可能暗号システム1のm番目の管理者が使用する装置である。本形態では、小さいmに対応する管理者ほど強い管理権限を持つ。すなわち、m=1に対応する管理者が最も強い権限を持つ。また、属性ベクトル生成装置21及び述語ベクトル生成装置25は、検索可能暗号システム1を利用するu番目の登録ユーザが使用する装置である。また、各装置は他の装置へ情報を提供可能なように構成されている。装置間の情報提供は通信網12を通じて行われてもよいし、可搬型記録媒体を介して行われてもよい。
【0205】
[管理装置27]
図5Aは、実施形態の管理装置27−1の機能構成を説明するための図であり、図5Bは、実施形態の管理装置27−(m’+1)(m’=1,…,M−1)の機能構成を説明するための図である。
【0206】
図5Aに例示するように、管理装置27−1は、入力部271−1と出力部272−1とマスタ鍵格納部273−1と制御部275−1とベクトル設定部276a−1と鍵情報生成部276b−1とを有する。図5Bに例示するように、管理装置27−(m’+1)は、入力部271−(m’+1)と出力部272−(m’+1)と制御部275−(m’+1)とベクトル設定部276a−(m’+1)と鍵情報生成部276b−(m’+1)とを有する。管理装置27−mは、例えば、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)などを有する公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、管理装置27−mは、それぞれ、制御部275−mの制御のもと各処理を実行する。また、管理装置27−mでの各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【0207】
[属性ベクトル生成装置21]
図6は、実施形態の属性ベクトル生成装置21−uの機能構成を説明するための図である。
【0208】
図6に例示するように、属性ベクトル生成装置21−uは、入力部211−uと出力部212−uと属性格納部213a−uと登録キーワード格納部213b−uと検索者鍵格納部213c−uと制御部215−uと属性ベクトル生成部216e−uと検索タグ生成部216f−uとを有する。属性ベクトル生成装置21は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、属性ベクトル生成装置21は、それぞれ、制御部215−uの制御のもと各処理を実行する。なお、属性ベクトル生成装置21での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【0209】
[判定装置26]
図7は、実施形態の判定装置26の機能構成を説明するための図である。
【0210】
図7に例示するように、判定装置26は、入力部261と出力部262と制御部265と検証処理部267とを有する。判定装置26は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、判定装置26は、それぞれ、制御部265の制御のもと各処理を実行する。また、判定装置26での各演算結果は、図示していない一時メモリに格納され、必要に応じて読み出されて使用される。
【0211】
[保管装置23]
図8Aは、実施形態の保管装置23の機能構成を説明するための図である。
【0212】
図8Aに例示するように、保管装置23は、入力部231と出力部232と暗号化データベース格納部233と制御部235と読み書き部236とを有する。保管装置23は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、保管装置23は、制御部135の制御のもと各処理を実行する。
【0213】
図8Bは、暗号化データベース格納部233に格納される暗号化データベースのデータ構成を説明するための図である。
【0214】
図8Bに例示するように、暗号化データベース格納部233には、文書などの検索対象情報Texttiの暗号文C(Textti)と検索対象情報Texttiのキーワードに対応する暗号化情報であるタグ情報Tag(ti,u)とが互いに対応付けられて格納されている。暗号文C(Textti)を生成するための検索対象情報Texttiの暗号化方式には限定はなく、任意の既存の暗号化方式(共通鍵暗号方式,公開鍵暗号方式,関数暗号方式など)でよい。タグ情報Tag(ti,u)は暗号文C(Textti)を検索するための情報である。保管装置23は、タグ情報Tag(ti,u)が与えられても、それに対応する検索キーワードを知ることができない。タグ情報Tag(ti,u)の生成方法の詳細は後述する。
【0215】
[述語ベクトル生成装置25]
図9は、実施形態の述語ベクトル生成装置25の機能構成を説明するための図である。
【0216】
図9に例示するように、述語ベクトル生成装置25は、入力部251−uと出力部252−uと鍵情報格納部253−uと検索対象情報復号鍵格納部254−uと制御部255−uと述語ベクトル生成部256−uと検索クエリ生成部257−uと復号部258−uとを有する。述語ベクトル生成装置25は、例えば、公知のコンピュータまたは専用コンピュータに特別なプログラムが読み込まれて構成される特別な装置である。また、述語ベクトル生成装置25は、それぞれ、制御部255−uの制御のもと各処理を実行する。
【0217】
<事前処理>
前述したSetupが実行され、階層フォーマットξ,マスタ鍵情報msk,公開パラメータmpkが定められる。マスタ鍵情報mskは、管理装置27−1(図5A)のマスタ鍵格納部273−1に安全に格納され、管理装置27−m,属性ベクトル生成装置21,述語ベクトル生成装置25及び判定装置26が、公開パラメータmpkを用いた処理が可能なように構成される。また、管理装置27−m及び属性ベクトル生成装置21が階層フォーマットξに従った処理が可能なように構成される。
【0218】
属性ベクトル生成装置21(図6)の登録キーワード格納部213b−uには、登録を行う検索対象情報Texttiの暗号文C(Textti)と検索対象情報Texttiに対応するキーワードXとが格納されている。さらに、属性ベクトル生成装置21の属性格納部213a−uには、属性ベクトル生成装置21を利用するユーザの属性を表す情報(以下、単に「属性」という)が格納されている。ユーザの属性の例は、ユーザが所属するグループを表す情報(会社名、所属部門、課、担当、グループなど)、住所、年齢、職業、趣味などである。
【0219】
述語ベクトル生成装置25(図9)の検索対象情報復号鍵格納部254−uには、属性ベクトル生成装置21(図6)の登録キーワード格納部213b−uに格納された暗号文C(Textti)を復号するための検索対象情報復号鍵Keytiが格納されている。
【0220】
<ユーザ登録>
ユーザ登録では、管理装置27−mが登録ユーザの属性に対して設定されたベクトル(v,…,v)に対応する鍵情報kを生成する。鍵情報kの生成方式は大きく分けて2通り存在する。
【0221】
一つ目の方式は、管理装置27−1が前述のGenKeyのみに従って鍵情報kを生成する方式である(一括方式)。このような方式は小規模グループに適したものであるといえる。二つ目の方式は、管理装置27−1が前述のGenKeyに従い、その他の管理装置27−(m’+1)が前述のDelegate(m’)に従い、鍵情報kを生成する方式である(委託方式)。このような方式は階層化された大規模グループに適したものであるといえる。
【0222】
[一括方式]
図7は、一括方式によって鍵情報kを生成する処理を説明するためのフローチャートである。
【0223】
一括方式では、最も強い権限をもつm=1に対応する管理者の管理装置27−1のみによって鍵情報kを生成する。
【0224】
まず、管理装置27−1(図5A)の入力部271−1に登録ユーザの属性ATTが入力される。属性ATTはM層ATT,…,ATTに階層化されている。各層に対応する属性ATTを部分属性と呼ぶことにし、小さいmに対応する部分属性ATTほど上位の属性を表すものとする。例えば、M=2の場合、属性ATTは2層の部分属性ATT及びATTからなり、この場合の部分属性の例は、
ATT1=(○○株式会社,○○部門) …(81)
ATT2=(○○課,○○担当,○○グループ) …(82)
である。
【0225】
入力された属性ATTはベクトル設定部276a−1に入力される。ベクトル設定部276a−1は、階層フォーマットξ及びシステム内で定められた規則に従って属性ATTに対応するベクトル(v,…,v)を設定する。例えば、ベクトル設定部276a−1は、まず、階層フォーマットξ及びシステム内で定められた規則に従い、属性ATTを表すベクトル(w,…,w)を式(41)に従って設定し、内積wω・vω=0となる式(42)に従ったベクトル(v,…,v)を属性ATTに対応するベクトルとする。式(81)(82)の例を用いて説明すると、例えば、ベクトル設定部276a−1は、部分属性ATTを「○○株式会社」を表すw及び「○○部門」を表すwを要素とする2次元のベクトル
w1=(w1,w2) …(83)
に変換し、部分属性ATTを「○○課」を表すw、「○○担当」を表すw、及び「○○グループ」を表すwを要素とする3次元のベクトル
w2=(w3,w4,w5) …(84)
に変換し、属性ATTを表すベクトル(w,w)=(w,w,w,w,w)を設定し、内積wω・vω=0となるベクトル(v,v)=(v,v,v,v,v)を属性ATTに対応するベクトルとする。なお、システム内で定められた規則に基づいて定められるのであれば、属性ATTを表すベクトル(w,…,w)をどのように定めるかについては特に限定はなく、属性ATTごとにベクトル(w,…,w)が定まるのであればどのような方法でもよい。
【0226】
生成されたベクトル(v,…,v)は鍵情報生成部276b−1に入力される。鍵情報生成部276b−1は、マスタ鍵格納部273−1からマスタ鍵情報mskを読み出し、m=Mとした前述のGenKeyに従い、ベクトル(v,…,v)に対応する鍵情報kを生成する。例えば、鍵情報生成部276b−1は、m=Mとした式(43)−(46)に従って鍵情報kを生成する。生成された鍵情報kは出力部272−1に送られる。
【0227】
出力部272−1は、鍵情報k(M≦d−1)を出力する。鍵情報kは登録ユーザが使用する述語ベクトル生成装置25(図9)の入力部251−uに入力され、鍵情報格納部253−uに格納される。
【0228】
[委託方式]
委託方式では、最も強い権限をもつm=1に対応する管理者の管理装置27−1が前述のGenKeyに従って鍵情報kを生成し、上位階層の鍵情報を受け取った下位階層の管理者の管理装置27−(m’+1)が前述のDelegate(m’)に従って鍵情報を生成していき、最終的に鍵情報kが生成される。
【0229】
まず、管理装置27−1(図5A)の入力部271−1に登録ユーザの部分属性ATTが入力される。
【0230】
入力された部分属性ATTはベクトル設定部276a−1に入力される。ベクトル設定部276a−1は、階層フォーマットξ及びシステム内で定められた規則に従って部分属性ATTに対応するベクトルvを設定する。例えば、ベクトル設定部276a−1は、まず、階層フォーマットξ及びシステム内で定められた規則に従い、部分属性ATTを表すベクトルwを式(41)に従って設定し、内積w・v=0となる式(42)に従ったベクトルvを部分属性ATTに対応するベクトルとする。式(81)(82)の例を用いて説明すると、例えば、ベクトル設定部276a−1は、式(83)によって部分属性ATTを表すベクトルwを設定し、内積w・v=0となる式(84)のベクトルvを、部分属性ATTに対応するベクトルとする。
【0231】
生成されたベクトルvは鍵情報生成部276b−1に入力される。鍵情報生成部276b−1は、マスタ鍵格納部273−1からマスタ鍵情報mskを読み出し、m=1とした前述のGenKeyに従い、ベクトルvに対応する鍵情報kを生成する。例えば、鍵情報生成部276b−1は、m=1とした式(43)−(46)に従って鍵情報kを生成する。生成された鍵情報kは出力部272−1に送られる。
【0232】
鍵情報kは管理装置27−2に入力される。管理装置27−2以降では前述したDelegate(m’)(m’=1,…,M−1)に従って鍵生成が行われる。以下では管理装置27−m’から鍵情報km’を受け取る管理装置27−(m’+1)の処理を一般化して説明する。
【0233】
まず、鍵情報km’が管理装置27−(m’+1)(図5B)の入力部271−(m’+1)に入力され、鍵情報生成部276b−(m’+1)に入力される。また、部分属性ATTm’+1がベクトル設定部276a−(m’+1)に入力される。ベクトル設定部276a−(m’+1)は、階層フォーマットξ及びシステム内で定められた規則に従って部分属性ATTm’+1に対応するベクトルvm’+1を設定する。例えば、ベクトル設定部276a−(m’+1)は、まず、階層フォーマットξ及びシステム内で定められた規則に従い、部分属性ATTm’+1を表すベクトルwm’+1を式(41)に従って設定し、内積wm’+1・vm’+1=0となる式(42)に従ったベクトルvm’+1を部分属性ATTm’+1に対応するベクトルとする。生成されたベクトルvm’+1は鍵情報生成部276b−(m’+1)に入力される。
【0234】
鍵情報km’とベクトルvm’+1とが入力された鍵情報生成部276b−(m’+1)は、前述のDelegate(m’)に従って、ベクトル(v,…,vm’+1)に対応する鍵情報km’+1を生成する。例えば、鍵情報生成部276b−(m’+1)は、式(47)−(50)に従って鍵情報km’+1を生成する。生成された鍵情報km’+1は出力部272−(m’+1)に送られる。出力部272−(m’+1)は鍵情報km’+1を出力する。
【0235】
m’+1<Mの場合、出力された鍵情報km’+1は下位階層の管理装置27−(m’+2)に入力され、m’+1を新たなm’として同様の処理が実行される。一方、m’+1=Mの場合、出力された鍵情報km’+1=kは、登録ユーザが使用する述語ベクトル生成装置25(図9)の入力部251−uに入力され、鍵情報格納部253−uに格納される。
【0236】
<データベース登録>
登録ユーザは属性ベクトル生成装置21を用い、以下のようにデータベース登録を行うことができる。
【0237】
まず、属性ベクトル生成装置11の属性ベクトル生成部113は、登録キーワード格納部114から、検索対象情報Texttiに対応する登録用キーワードXを抽出し、登録用キーワードXを表す属性ベクトルwM+1が以下の関係を満たすように生成する。
【0238】
【数48】

属性ベクトルwM+1の生成方法は第一実施形態及びその変形例と同様である。
【0239】
また、属性ベクトル生成部216e−uが、属性格納部213a−uから登録ユーザの属性ATTを抽出する。この属性ATTは当該登録ユーザのユーザ登録時に用いられたものと同じである。属性ベクトル生成部216e−uは、階層フォーマットξ及びシステム内で定められた規則に従って属性ATTを表すベクトル(w,…,w)を設定する。当該ベクトル(w,…,w)とユーザ登録時のステップS103で設定されたベクトル(v,…,v)とは、ω=1,…,Mについて内積wω・vω=0を満たす。
【0240】
属性ベクトル生成部216e−uは、生成したベクトル(w,…,w)と属性ベクトルwM+1をまとめて検索タグ生成部216f−uに送る。
【0241】
検索タグ生成部216f−uは、w,…,w,wM+1を用い、例えば、d=M+1とした式(51)に従って暗号文Cを生成し、mes=Xとした式(52)に従って暗号文Cを生成する。検索タグ生成部216f−uは、上述の処理により得られた暗号文C,Cの組合せを検索タグTag(ti,u)=(C,C)とする。
【0242】
生成されたタグ情報Tag(ti,u)は出力部212−uに送られる。また、登録キーワード格納部213b−uから読み出された暗号文C(Textti)が出力部212−uに送られる。出力部212−uは、暗号文C(Textti)とタグ情報Tag(ti,u)とを出力する。これらの組は保管装置23(図8A)の入力部231に入力され、書込み部236から暗号化データベース格納部233に格納される(図8B)。
【0243】
<検索>
登録ユーザは述語ベクトル生成装置25(図9)を用い、以下のように検索を行うことができる。
【0244】
まず、検索を行う登録ユーザによって選択された検索用キーワードsが入力部251−uに入力される。検索用キーワードsは述語ベクトル生成部256−uに送られる。
【0245】
述語ベクトル生成部256−uにおいて、検索用キーワードsを表す述語ベクトルvM+1を以下の関係を満たすように生成する。
【0246】
【数49】

【0247】
述語ベクトルvM+1の生成方法は第一実施形態及びその変形例と同様である。生成された述語ベクトルvM+1は、検索クエリ生成部257−uに送られる。検索クエリ生成部257−uは、鍵情報格納部253−uから鍵情報kを抽出する。検索クエリ生成部257−uは、k,vM+1を用い、m’=Mとした前述のDelegate(m’)によって、v,…,v及びvM+1に対応する鍵情報(復号鍵)である検索クエリkM+1を生成する。例えば、検索クエリ生成部257−uは、m’=M(M≦d−1)とした式(47)−(50)に従って検索クエリkM+1を生成する。なお、m=d−1の場合には式(50)のkm’+1,αを含まない。生成された検索クエリkM+1は出力部252−uに送られる。出力部252−uは検索クエリkM+1を出力する。
【0248】
検索クエリkM+1は、判定装置26(図7)の入力部261に入力され、検証処理部267に送られる。判定装置26は保管装置23(図8A)にアクセスし、暗号化データベース格納部233に格納されたタグ情報Tag(ti,u)の取得を要求するための情報を出力部261から出力する。この情報は保管装置23の入力部231に入力されて読み書き部236に送られる。保管装置23の読み書き部236は、暗号化データベース格納部233から何れかのタグ情報Tag(ti,u)を読み出し、出力部232はそれを判定装置26に送る。タグ情報Tag(ti,u)は判定装置26(図7)の入力部261に入力され、検証処理部267に送られる。
【0249】
式(52)(53)(55)より、全てのω=1,…,M,M+1について内積vω・wω=0である場合に、mes’=mesとなる。検証処理部267は、公開パラメータmpkと検索クエリkM+1とタグ情報Tag(ti,u)を入力とし、mes’=mesを満たすか否かを検証する。満たす場合には検証合格となる。
【0250】
ここで、検証合格とならなかった場合、判定装置26は保管装置23に対して未検証のタグ情報Tag(ti,u)が暗号化データベース格納部233内に存在するかを問い合わせるための情報を出力部262から出力する。この情報は保管装置23(図8A)の入力部231に入力され、読み書き部236に送られる。読み書き部236は、暗号化データベース格納部233を検索して未検証のタグ情報Tag(ti,u)が暗号化データベース格納部233内に存在するか否かを判定し、その判定結果が出力部232から出力される。判定結果は、判定装置26(図7)の入力部261に入力され、制御部265に送られる。ここで、未検証のタグ情報Tag(ti,u)が暗号化データベース格納部233内に存在しない旨の応答があった場合、判定装置26の出力部262が「該当なし」を表す⊥を出力して処理を終了する。一方、未検証のタグ情報Tag(ti,u)が暗号化データベース格納部233内に存在する旨の応答があった場合には、未検証のタグ情報に対して検証を行う。
【0251】
一方、ステップS257で検証合格となった場合、判定装置26は保管装置23に対し、検証合格となったタグ情報Tag(ti,u)に対応する検証対象情報の暗号文C(Textti)の出力を要求するための情報を出力部262から出力する。この情報は保管装置23(図8A)の入力部231に入力され読み書き部236に送られる。読み書き部236は、検証合格となったタグ情報Tag(ti,u)に対応する検証対象情報の暗号文C(Textti)を暗号化データベース格納部233から抽出し、出力部232に送る。出力部232は暗号文C(Textti)を出力する。暗号文C(Textti)は、判定装置26(図7)の入力部261に入力され、検証処理部267に送られる。暗号文C(Textti)は、出力部262に送られて出力され、述語ベクトル生成装置(図9)の入力部251−uに入力される。暗号文C(Textti)は、復号部258−uに送られる。復号部258−uは検索対象情報復号鍵格納部254−uから検索対象情報復号鍵Keytiを読み出し、これを用いて暗号文C(Textti)を復号して検索対象情報Texttiを出力する。
【0252】
<効果>
このような構成とすることで、階層的内積述語暗号において部分集合一致検索可能な検索システムを構成することができる。
【0253】
<プログラム及び記録媒体>
上述した属性ベクトル生成装置、述語ベクトル生成装置、ベクトル構成装置及び判定装置は、コンピュータにより機能させることもできる。この場合はコンピュータに、目的とする装置(各種実施例で図に示した機能構成をもつ装置)として機能させるためのプログラム、またはその処理手順(各実施例で示したもの)の各過程をコンピュータに実行させるためのプログラムを、CD−ROM、磁気ディスク、半導体記憶装置などの記録媒体から、あるいは通信回線を介してそのコンピュータ内にダウンロードし、そのプログラムを実行させればよい。
【0254】
<その他の変形例>
属性ベクトル生成装置及び述語ベクトル生成装置を関数暗号方式を用いて暗号化されたデータベースの検索が可能な検索可能暗号システムにおいても用いてもよい(参考文献5参照)。
(参考文献5):Tatsuaki Okamoto, Katsuyuki Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption", Advances in Cryptology - CRYPTO 2010, 2010, p.191-208
【0255】
また、本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【0256】
1,2 検索システム
11、21−u 属性ベクトル生成装置
12 通信網
13、23 保管装置
15、25 述語ベクトル生成装置
16、26 判定装置

【特許請求の範囲】
【請求項1】
属性ベクトル生成装置と、述語ベクトル生成装置と、判定装置と、からなる検索システムであって、
を位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとし、添え字trはtを意味し、rd,…,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX,…,Xtrとし、検索用情報の要素をs,…,strとし、
【数50】

とし、f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式(A)は
【数51】

と表現されるものとし、
前記属性ベクトル生成装置は検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、前記式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成し、
前記述語ベクトル生成装置は検索用情報の要素の集合s,…,strを用いて、前記式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成し、
前記判定装置は前記属性ベクトルと前記述語ベクトルとの内積が0のとき、前記検索対象情報に対応する登録用情報中に前記検索用情報が含まれると判定する、
検索システム。
【請求項2】
請求項1記載の検索システムであって、
=1とし、前記属性ベクトル生成装置は−X,−X,…,−Xtrのk次基本対称式Yを用いて、k次基本対称式Yの値を要素とする属性ベクトルw={Y,Y,…,Y,…,Ytr}を生成し、
前記述語ベクトル生成装置は
【数52】

の値を要素とする述語ベクトルv={V,V,…,V,…,Vtr}を生成する、
検索システム。
【請求項3】
請求項1または2記載の検索システムであって、
前記属性ベクトル生成装置は、検索対象情報に対応する登録用情報の要素の集合から重複する要素を削除して属性ベクトルを生成し、
前記述語ベクトル生成装置は、検索用情報の要素の集合から重複する要素を削除して述語ベクトルを生成する、
検索システム。
【請求項4】
請求項1から3の何れかに記載の検索システムにおいて用いられる判定装置。
【請求項5】
少なくとも属性ベクトルまたは述語ベクトルを生成するベクトル構成装置であって、
を位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとし、添え字trはtを意味し、rd,…,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX,…,Xtrとし、検索用情報の要素をs,…,strとし、
【数53】

とし、f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式(A)は
【数54】

と表現されるものとし、
少なくとも検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、前記式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成するか、
前記述語ベクトル生成装置は検索用情報の要素の集合s,…,strを用いて、前記式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成する、
ベクトル構成装置。
【請求項6】
請求項5記載のベクトル構成装置であって、
=1とし、少なくとも−X,−X,…,−Xtrのk次の基本対称式Yを用いて、k次基本対称式Yの値を要素とする属性ベクトルw={Y,Y,…,Y,…,Ytr}として生成するか、
【数55】

の値を要素とする述語ベクトルv={V,V,…,V,…,Vtr}を生成する、
ベクトル構成装置。
【請求項7】
請求項6または7記載のベクトル構成装置であって、
少なくとも、検索対象情報に対応する登録用情報の要素の集合から重複する要素を削除して属性ベクトルを生成するか、または、検索用情報の要素の集合から重複する要素を削除して述語ベクトルを生成する、
ベクトル構成装置。
【請求項8】
属性ベクトル生成ステップと、述語ベクトル生成ステップと、判定ステップと、からなる検索方法であって、
を位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとし、添え字trはtを意味し、rd,…,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX,…,Xtrとし、検索用情報の要素をs,…,strとし、
【数56】

とし、f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式(A)は
【数57】

と表現されるものとし、
前記属性ベクトル生成ステップにおいて、検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、前記式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成し、
前記述語ベクトル生成ステップにおいて、検索用情報の要素の集合s,…,strを用いて、前記式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成し、
前記判定ステップにおいて、前記属性ベクトルと前記述語ベクトルとの内積が0のとき、前記検索対象情報に対応する登録用情報中に前記検索用情報が含まれると判定する、
検索方法。
【請求項9】
少なくとも属性ベクトルまたは述語ベクトルを生成するベクトル構成方法であって、
を位数qの有限体とし、検索対象情報に対応する登録用情報の要素の個数及び検索用情報の要素の個数を有限体Fの元で表現されるtとし、添え字trはtを意味し、rd,…,rdtrを乱数とし、検索対象情報に対応する登録用情報の要素をX,…,Xtrとし、検索用情報の要素をs,…,strとし、
【数58】

とし、f(X,…,Xtr)を変数s,…,strを含まないX,…,Xtrの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、f(s,…,str)を変数X,…,Xtrを含まないs,…,strの少なくとも1つ以上を含む単項式若しくは多項式または定数とし、Pを1以上の整数とし、前記式(A)は
【数59】

と表現されるものとし、
少なくとも検索対象情報に対応する登録用情報の要素の集合X,…,Xtrを用いて、前記式(B)のf(X,…,Xtr)の値を要素とする属性ベクトルを生成するか、
前記述語ベクトル生成方法は検索用情報の要素の集合s,…,strを用いて、前記式(B)のf(s,…,str)の値を要素とする述語ベクトルを生成する、
ベクトル構成方法。
【請求項10】
請求項4から7の何れかに記載の判定装置またはベクトル構成装置としてコンピュータを機能させるためのプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate