(57)【要約】  秘匿検索システム（１０）は、文字列の各文字が位置を指定されて設定されたオリジナル検索鍵を変換して変換後検索鍵を生成し、複数の暗号化タグＥＴｘから、生成した変換後検索鍵ＴＤｖ’に対応する暗号化タグを検索する。特に、秘匿検索システム（１０）は、オリジナル検索鍵ＴＤｖに設定された文字のうち少なくとも一部の文字に対して指定された位置を他の位置に変換することにより、変換後検索鍵ＴＤｖ’を生成し、文字列の各文字が位置を指定されて設定された複数の暗号化タグから、変換後検索鍵ＴＤｖ’に設定された各文字について、その文字と、その文字に対して指定された位置に設定された文字とが一致する暗号化タグを検索する。
2016113878.tif 000002
【特許請求の範囲】
【請求項１】
文字列の各文字が位置を指定されて設定されたオリジナル検索鍵を変換して変換後検索鍵を生成する変換後検索鍵生成部であって、前記オリジナル検索鍵に設定された文字のうち少なくとも一部の文字に対して指定された位置を他の位置に変換することにより、前記変換後検索鍵を生成する変換後検索鍵生成部と、
文字列の各文字が位置を指定されて設定された複数の暗号化タグから、前記変換後検索鍵生成部が生成した前記変換後検索鍵に設定された各文字について、その文字と、その文字に対して指定された位置に設定された文字とが一致する暗号化タグを検索する検索部と
を備える秘匿検索システム。
【請求項２】
前記オリジナル検索鍵は、前記各文字が設定された検索ベクトルであって、位置を指定する複数の基底のうちのいずれかの基底上のベクトルである検索ベクトルを含み、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる少なくとも一部の検索ベクトルを前記複数の基底のうちの他の基底上の検索ベクトルに変換することにより、前記変換後検索鍵を生成する
請求項１に記載の秘匿検索システム。
【請求項３】
前記複数の基底は、ｔ＝１，．．．，ｄ−１の各整数ｔについて、基底Ｂ＊ｔ＋１が基底Ｂ＊ｔを変換行列Ｗ＊ｔによって変換されて得られる、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる少なくとも一部の検索ベクトルを、前記変換行列Ｗ＊ｔにより前記他の基底上の検索ベクトルに変換する
請求項２に記載の秘匿検索システム。
【請求項４】
前記複数の基底は、ｔ＝１，．．．，ｄ−１の各整数ｔについて、基底Ｂ＊ｔ＋１が前記基底Ｂ＊ｔに変換行列Ｗ＊ｔを乗じて得られ、
前記変換後検索鍵生成部は、１以上ｄ以下の整数ｔ，ｔ’について、ｔ＜ｔ’のときには、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔにｊ＝ｔ，．．．，ｔ’−１の各整数ｊについての変換行列Ｗ＊ｊを乗じて、前記検索ベクトルｋ＊ｔを基底Ｂ＊ｔ’上の検索ベクトルｋ＊ｔ’に変換し、ｔ＞ｔ’の場合のときには、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔにｊ＝ｔ−１，．．．，ｔ’の各整数ｊについての変換行列Ｗ＊ｊの逆行列（Ｗ＊ｊ）−１を乗じて、前記検索ベクトルｋ＊ｔを基底Ｂ＊ｔ’上の検索ベクトルｋ＊ｔ’に変換する
請求項３に記載の秘匿検索システム。
【請求項５】
前記複数の基底は、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
各暗号化タグは、ｔ＝１，．．．，ｄのうちの少なくとも一部の整数ｔについて、前記基底Ｂ＊ｔに対応する基底Ｂｔ上のタグベクトルを含み、
前記検索部は、前記変換後検索鍵に含まれる検索ベクトルと、前記各暗号化タグに含まれるタグベクトルとを用いた計算をすることにより、前記変換後検索鍵に対応する暗号化タグを検索する
請求項２に記載の秘匿検索システム。
【請求項６】
前記検索部は、前記変換後検索鍵に含まれる検索ベクトルと、前記各暗号化タグに含まれるタグベクトルであって、その検索ベクトルの基底Ｂ＊ｔに対応する基底Ｂｔ上のタグベクトルとの内積の計算をすることにより、前記変換後検索鍵に対応する暗号化タグを検索する
請求項５に記載の秘匿検索システム。
【請求項７】
前記複数の基底は、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる全ての検索ベクトルを、検索ベクトルの基底Ｂ＊ｔの添え字ｔが同じ値だけずれるように変換することにより、前記変換後検索鍵を生成する
請求項２に記載の秘匿検索システム。
【請求項８】
前記複数の基底は、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる検索ベクトルのうち、検索ベクトルの基底Ｂ＊ｔの添え字ｔが基準値未満の検索ベクトルと、基準値以上の検索ベクトルとの間で、前記添え字ｔの値の差が大きくなるように、前記オリジナル検索鍵に含まれる検索ベクトルを変換することにより、前記変換後検索鍵を生成する
請求項２に記載の秘匿検索システム。
【請求項９】
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる第１検索ベクトルと第２検索ベクトルとを、第１検索ベクトルの基底と第２検索ベクトルの基底とが入れ替わるように変換することにより、前記変換後検索鍵を生成する
請求項２に記載の秘匿検索システム。
【請求項１０】
文字列の各文字が位置を指定されて設定されたオリジナル検索鍵を変換して変換後検索鍵を生成する変換後検索鍵生成処理であって、前記オリジナル検索鍵に設定された文字のうち少なくとも一部の文字に対して指定された位置を他の位置に変換することにより、前記変換後検索鍵を生成する変換後検索鍵生成処理と、
文字列の各文字が位置を指定されて設定された複数の暗号化タグから、前記変換後検索鍵生成処理で生成した前記変換後検索鍵に設定された各文字について、その文字と、その文字に対して指定された位置に設定された文字とが一致する暗号化タグを検索する検索処理と
をコンピュータに実行させる秘匿検索プログラム。
【請求項１１】
文字列の各文字が位置を指定されて設定されたオリジナル検索鍵を取得する情報取得部と、
前記情報取得部が取得したオリジナル検索鍵に設定された文字のうち少なくとも一部の文字に対して指定された位置を他の位置に変換することにより、変換後検索鍵を生成する鍵変換部と
を備える変換後検索鍵生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データを暗号化した状態で検索を行う秘匿検索技術に関する。
【背景技術】
【０００２】
ネットワーク、特にインターネットにおける演算資源を用いて、様々なサービスを提供するクラウドコンピューティングが存在する。例えば、ネットワーク上にデータを保管しておき、許可された利用者がデータを端末にダウンロードし利用するといったサービスが提供されている。
ネットワーク上に保管するデータの中には、利用者の個人情報等の第三者に漏えいしない様に秘匿する必要があるデータが存在する。このようなデータは、秘密鍵暗号や公開鍵暗号といった暗号で暗号化することにより秘匿することが可能である。【０００３】
暗号化したデータをネットワーク上に保管することで、データの秘匿化とクラウドコンピューティングの活用とを両立させることができる。
しかし、データを暗号化してしまうとデータを検索できなくなってしまうという課題がある。この課題を解決する技術として秘匿検索技術が提案されている。秘匿検索技術では、特別な暗号化方法によりデータを暗号化することによって、暗号化されたデータであっても検索が可能となる。【０００４】
様々な秘匿検索が提案されているが、検索対象データと、検索キーワードとが全く同じ場合にのみ検索される完全一致秘匿検索方式が多く提案されている。これに対して、検索キーワードが検索対象データ中の一部に含まれている場合に検索される方式を部分一致秘匿検索方式という。【０００５】
非特許文献１には、部分一致秘匿検索方式について記載されている。非特許文献１に記載された方式では、部分一致する可能性のある全てのパターンについての検索情報を検索者端末から検索装置へ送信することにより、部分一致秘匿検索を実現している。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】“部分一致検索可能暗号”  吉田  麗生、小田  哲、小林  鉄太郎  ＳＣＩＳ  ２０１０
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１の方式では、検索者端末が、全てのパターンについての検索情報を作成し、検索装置に送信する。そのため、検索者端末から検索装置へ送信される検索情報量が多くなる。
この発明は、検索者端末が送信する検索情報量を減らすことを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る秘匿検索システムは、
文字列の各文字が位置を指定されて設定されたオリジナル検索鍵を変換して変換後検索鍵を生成する変換後検索鍵生成部であって、前記オリジナル検索鍵に設定された文字のうち少なくとも一部の文字に対して指定された位置を他の位置に変換することにより、前記変換後検索鍵を生成する変換後検索鍵生成部と、
文字列の各文字が位置を指定されて設定された複数の暗号化タグから、前記変換後検索鍵生成部が生成した前記変換後検索鍵に設定された各文字について、その文字と、その文字に対して指定された位置に設定された文字とが一致する暗号化タグを検索する検索部とを備える。
【発明の効果】
【０００９】
この発明に係る秘匿検索システムでは、オリジナル検索鍵を変換後検索鍵に変換して暗号化タグを検索する。そのため、検索者端末からオリジナル検索鍵が送信されれば、検索を実行することが可能である。したがって、検索者端末が送信する検索情報量を減らすことが可能である。
【図面の簡単な説明】
【００１０】
【図１】内積述語暗号における内積の取り方の説明図。
【図２】内積述語暗号における内積の取り方の説明図。
【図３】内積述語暗号の基本構成の説明図。
【図４】実施の形態１に係る部分一致秘匿検索方式のキーテクニックの説明図。
【図５】実施の形態１に係る部分一致秘匿検索方式の実現例の説明図。
【図６】実施の形態１に係る部分一致秘匿検索方式の実現例の説明図。
【図７】実施の形態１に係る部分一致秘匿検索方式の実現例の説明図。
【図８】実施の形態１に係る秘匿検索システム１０の構成図。
【図９】実施の形態１に係る鍵生成装置１００の構成図。
【図１０】実施の形態１に係る暗号化タグ生成装置２００の構成図。
【図１１】実施の形態１に係る検索鍵生成装置３００の構成図。
【図１２】実施の形態１に係る変換後検索鍵生成装置４００の構成図。
【図１３】実施の形態１に係る検索装置５００の構成図。
【図１４】実施の形態１に係るＫＧアルゴリズムの処理のフローチャート。
【図１５】実施の形態１に係るＴａｇＧｅｎアルゴリズムの処理のフローチャート。
【図１６】実施の形態１に係るＴｒａｐＧｅｎアルゴリズムの処理のフローチャート。
【図１７】実施の形態１に係るＴｒａｐＳｈｉｆｔアルゴリズムの処理のフローチャート。
【図１８】実施の形態１に係るＳｅａｒｃｈアルゴリズムの処理のフローチャート。
【図１９】実施の形態１に係る鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とのハードウェア構成例を示す図。
【発明を実施するための形態】
【００１１】
実施の形態１．
＊＊＊記法の説明＊＊＊
以下の説明における記法について説明する。
Ａがランダムな値または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
2016113878.tif 000003
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
2016113878.tif 000004
数１０３は、ｙにｚが設定されたこと、ｙがｚにより定義されたこと、又はｙがｚを代入されたことを表す。
【数１０３】
2016113878.tif 000005
ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数１０４】
2016113878.tif 000006
数１０５は、位数ｑの体を表す。
【数１０５】
2016113878.tif 000007
数１０６は、有限体Ｆｑにおけるベクトル表現を表す。
【数１０６】
2016113878.tif 000008
数１０７は、数１０８に示す２つのベクトルｘ→とｖ→との数１０９に示す内積を表す。
【数１０７】
2016113878.tif 000009
【数１０８】
2016113878.tif 000010
【数１０９】
2016113878.tif 000011
ＸＴは、行列Ｘの転置行列を表す。
数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１である。
【数１１０】
2016113878.tif 000012
【数１１１】
2016113878.tif 000013
【００１２】
＊＊＊概要の説明＊＊＊
実施の形態１では、内積述語暗号を応用して、部分一致秘匿検索方式を実現する。
【００１３】
図１及び図２に基づき、内積述語暗号における内積の取り方について説明する。
図１に示すように、暗号文がベクトルｘ→＝（ｘ１，ｘ２，．．．，ｘｎ）であり、鍵がベクトルｖ→＝（ｖ１，ｖ２，．．．，ｖｎ）であるとする。この場合、内積述語暗号では、ベクトルｘ→とベクトルｖ→との内積Σｉ＝１ｎ（ｘｉ・ｖｉ）が計算され、暗号文が鍵により復号される。つまり、暗号文のベクトルｘ→と鍵のベクトルｖ→との対応する要素毎の内積の和が計算され、暗号文が鍵により復号される。
【００１４】
図２に示すように、暗号文がベクトルｘ→＝（ｘ１，ｘ２）であり、鍵がベクトルｖ→＝（ｖ１，ｖ２，．．．，ｖｎ）であるように、暗号文のベクトルｘ→と鍵のベクトルｖ→との要素数が異なる場合もある。この場合にも、暗号文のベクトルｘ→と鍵のベクトルｖ→との対応する要素毎の内積の和が計算され、暗号文が鍵により復号される。
【００１５】
図３に基づき、内積述語暗号の基本構成について説明する。
秘密値ｓ０と、ｔ∈Ｉｖの各整数ｔについての分散値ｓｔとが用いられる。秘密値ｓ０と分散値ｓｔとには、ｓ０＝Σｔ∈Ｉｖｓｔという関係がある。
鍵は、秘密値ｓ０が設定された基底Ｂ＊０上のベクトルである要素ｋ＊０と、ｔ∈Ｉｖの各整数ｔについて、分散値ｓｔと属性値ｖｔとインデックスｔとが設定された基底Ｂ＊上のベクトルである要素ｋ＊ｔとを含む。一方、暗号文は、基底Ｂ＊０に対応する基底Ｂ０上のベクトルである要素ｃ０と、ｔ∈Ｉｘの各整数ｔについて、属性値ｘｔとインデックスｔとが設定された、基底Ｂ＊に対応する基底Ｂ上のベクトルである要素ｃｔとを含む。
そして、要素ｋ＊０と要素ｃ０との内積が計算されるとともに、ｔ∈Ｉｖとの各整数ｔについて、鍵に含まれる要素ｋ＊ｔと、暗号文に含まれる要素ｃｔとの内積が計算される。ｔ∈Ｉｖの各整数ｔについては、要素ｋ＊ｔに設定された属性値ｖｔと要素ｃｔに設定された属性値ｘｔとが対応している場合に、分散値ｓｔが得られる。ｓ０＝Σｔ∈Ｉｖｓｔであるため、ｔ∈Ｉｖの全ての要素ｋ＊ｔに設定された分散値ｓｔが得られると、要素ｋ＊０に設定された秘密値ｓ０が得られる。そして、この場合に、暗号文が鍵により復号できる。
なお、要素ｋ＊ｔと要素ｃｔとにインデックスｔが設定されている。そのため、ｉ≠ｊの整数ｉ，ｊについて、属性値ｖｉと属性値ｘｊとが対応していたとしても、要素ｋ＊ｉと要素ｃｊとの内積を計算しても分散値ｓｉが得られることはない。
【００１６】
図４に基づき、実施の形態１に係る部分一致秘匿検索方式のキーテクニックを説明する。
内積述語暗号の基本構成で説明したように、鍵の要素ｋ＊ｔは、分散値ｓｔと属性値ｖｔとインデックスｔとが設定された基底Ｂ＊上のベクトルであった。この要素ｋ＊ｔを、分散値ｓｔと属性値ｖｔとが設定された基底Ｂ＊ｔ上のベクトルとする。つまり、要素ｋ＊ｔにインデックスｔを設定せず、インデックスｔ毎に割り当てられた基底Ｂ＊ｔ上のベクトルにする。
同様に、暗号文の要素ｃｔは、属性値ｘｔとインデックスｔとが設定された基底Ｂ上のベクトルであった。この要素ｃｔを、属性値ｘｔが設定された、基底Ｂ＊ｔに対応する基底Ｂｔ上のベクトルにする。つまり、要素ｃｔにインデックスｔを設定せず、インデックスｔ毎に割り当てられた基底Ｂｔ上のベクトルにする。
【００１７】
ここで、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔは、ｔ＝１，．．．，ｄ−１の各整数ｔについて、基底Ｂ＊ｔ＋１が基底Ｂ＊ｔを変換行列Ｗ＊ｔによって変換されて得られたものる。
つまり、変換行列Ｗ＊ｔを用いれば、基底Ｂ＊ｔを基底Ｂ＊ｔ＋１に変換できるし、逆に基底Ｂ＊ｔ＋１を基底Ｂ＊ｔに変換できる。したがって、ｔ＝１，．．．，ｄ−１の各整数ｔについての変換行列Ｗ＊ｔを用いれば、ある基底Ｂ＊ｔをｔ＝１，．．．，ｄのどの整数ｔについての基底Ｂ＊ｔにも変換することができる。
これにより、ある基底Ｂ＊ｔ上のベクトルを、ｔ＝１，．．．，ｄのどの整数ｔについての基底Ｂ＊ｔ上のベクトルにも変換することができる。
【００１８】
ｉ≠ｊの整数ｉ，ｊについて、基底Ｂ＊ｉと基底Ｂｊとが対応していない。そのため、属性値ｖｉと属性値ｘｊとが対応していたとしても、要素ｋ＊ｉと要素ｃｊとの内積を計算しても分散値ｓｉが得られることはない。
しかし、要素ｋ＊ｔと要素ｃｔとにはインデックスｔが設定されていない。そのため、要素ｋ＊ｉを、基底Ｂ＊ｉ上のベクトルから基底Ｂ＊ｊ上のベクトルに変換すれば、要素ｋ＊ｉと要素ｃｊとの内積を計算して分散値ｓｉを得ることができる。
つまり、鍵の要素ｋ＊ｔの基底Ｂ＊ｔを変換して、要素ｋ＊ｔと内積を取る相手となる暗号文の要素ｃｔを変更できる。そのため、検索者から与えられたオリジナル検索鍵における各要素ｋ＊ｔの基底Ｂ＊ｔを変換して、要素ｋ＊ｔと内積を取る相手となる暗号文の要素ｃｔを別の要素ｃｔ’に変更した複数の変換後検索鍵を生成することができる。これを利用すれば、部分一致秘匿検索方式を実現することができる。
【００１９】
図５に基づき、実施の形態１に係る部分一致秘匿検索方式の実現例を説明する。
データベースに、ＡＢＣＤＥという検索タグとなる文字列が暗号化された暗号化タグが記憶されており、検索キーワードとして、ＣＤという文字列が与えられたとする。
この場合、ＡＢＣＤＥという文字列の各文字を属性値ｘｔとして、暗号文の要素ｃｔが生成される。つまり、要素ｃ１には属性値Ａが設定され、要素ｃ２には属性値Ｂが設定され、要素ｃ３には属性値Ｃが設定され、要素ｃ４には属性値Ｄが設定され、要素ｃ５には属性値Ｅが設定される。
一方、ＣＤという文字列の各文字を属性値ｖｔとして、オリジナル検索鍵が生成される。つまり、要素ｋ＊１には属性値Ｃが設定され、要素ｋ＊２には属性値Ｄが設定される。
【００２０】
検索処理では、オリジナル検索鍵の要素ｋ＊ｔの基底Ｂ＊ｔの添え字ｔを１つづつ順にずらして変換後検索鍵を生成し、変換後検索鍵で暗号化タグを復号する。復号されれば、変換後検索鍵で暗号化タグが検索されたことになる。
【００２１】
つまり、初めに、オリジナル検索鍵の要素ｋ＊ｔの基底Ｂ＊ｔの添え字ｔを０ずらして変換後検索鍵を生成し、変換後検索鍵で暗号化タグを復号する。すなわち、オリジナル検索鍵をそのまま変換後検索鍵として、変換後検索鍵で暗号化タグを復号する。
この場合、属性値Ａが設定された要素ｃ１と属性値Ｃが設定された要素ｋ＊１との内積が取られ、属性値Ｂが設定された要素ｃ２と属性値Ｄが設定された要素ｋ＊２との内積が取られる。要素ｃ１と要素ｋ＊１とでは属性値が対応しておらず、要素ｃ２と要素ｋ＊２とでは属性値が対応していないため、変換後検索鍵で暗号化タグを復号できない。
【００２２】
次に、オリジナル検索鍵の要素ｋ＊ｔの基底Ｂ＊ｔの添え字ｔを１ずらして変換後検索鍵を生成し、変換後検索鍵で暗号化タグを復号する。すなわち、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１を基底Ｂ＊２に変換し、要素ｋ＊２の基底Ｂ＊２を基底Ｂ＊３に変換して変換後検索鍵として、変換後検索鍵で暗号化タグを復号する。
この場合、属性値Ｂが設定された要素ｃ２と属性値Ｃが設定された要素ｋ＊１との内積が取られ、属性値Ｃが設定された要素ｃ３と属性値Ｄが設定された要素ｋ＊２との内積が取られる。要素ｃ２と要素ｋ＊１とでは属性値が対応しておらず、要素ｃ３と要素ｋ＊２とでは属性値が対応していないため、変換後検索鍵で暗号化タグを復号できない。
【００２３】
次に、オリジナル検索鍵の要素ｋ＊ｔの基底Ｂ＊ｔの添え字ｔを２ずらして変換後検索鍵を生成し、変換後検索鍵で暗号化タグを復号する。すなわち、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１を基底Ｂ＊３に変換し、要素ｋ＊２の基底Ｂ＊２を基底Ｂ＊４に変換して変換後検索鍵として、変換後検索鍵で暗号化タグを復号する。
この場合、属性値Ｃが設定された要素ｃ３と属性値Ｃが設定された要素ｋ＊１との内積が取られ、属性値Ｄが設定された要素ｃ４と属性値Ｄが設定された要素ｋ＊２との内積が取られる。要素ｃ３と要素ｋ＊１とでは属性値が対応しており、要素ｃ４と要素ｋ＊２とでは属性値が対応しているため、変換後検索鍵で暗号化タグを復号できる。したがって、変換後検索鍵で暗号化タグが検索される。
【００２４】
このように、オリジナル検索鍵の要素ｋ＊ｔの基底Ｂ＊ｔの添え字ｔを１つづつ順にずらして変換後検索鍵を生成することにより、部分一致秘匿検索方式を実現できる。
【００２５】
図６に基づき、実施の形態１に係る部分一致秘匿検索方式の実現例を説明する。
データベースに、ＡＢＣＤＥという検索タグとなる文字列が暗号化された暗号化タグが記憶されており、検索キーワードとして、ＢＤという文字列が与えられたとする。
この場合、ＡＢＣＤＥという文字列の各文字を属性値ｘｔとして、暗号文の要素ｃｔが生成される。つまり、要素ｃ１には属性値Ａが設定され、要素ｃ２には属性値Ｂが設定され、要素ｃ３には属性値Ｃが設定され、要素ｃ４には属性値Ｄが設定され、要素ｃ５には属性値Ｅが設定される。
一方、ＢＤという文字列の各文字を属性値ｖｔとして、オリジナル検索鍵が生成される。つまり、要素ｋ＊１には属性値Ｂが設定され、要素ｋ＊２には属性値Ｄが設定される。
【００２６】
検索処理では、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１の添え字と、要素ｋ＊２の基底Ｂ＊２の添え字との差が大きくなるように変換して変換後検索鍵を生成し、変換後検索鍵で暗号化タグを復号する。
【００２７】
例えば、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１を基底Ｂ＊２に変換し、要素ｋ＊２の基底Ｂ＊２を基底Ｂ＊４に変換して、変換後検索鍵が生成される。
この場合、属性値Ｂが設定された要素ｃ２と属性値Ｂが設定された要素ｋ＊１との内積が取られ、属性値Ｄが設定された要素ｃ４と属性値Ｄが設定された要素ｋ＊２との内積が取られる。要素ｃ２と要素ｋ＊１とでは属性値が対応しており、要素ｃ４と要素ｋ＊２とでは属性値が対応しているため、変換後検索鍵で暗号化タグを復号できる。したがって、変換後検索鍵で暗号化タグが検索される。
【００２８】
このように、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１の添え字と、要素ｋ＊２の基底Ｂ＊２の添え字との差が大きくなるように変換して変換後検索鍵を生成することにより、検索キーワードの文字列に間を空けた部分一致秘匿検索方式を実現できる。
【００２９】
図７に基づき、実施の形態１に係る部分一致秘匿検索方式の実現例を説明する。
データベースに、ＡＢＣＤＥという検索タグとなる文字列が暗号化された暗号化タグが記憶されており、検索キーワードとして、ＢＡという文字列が与えられたとする。
この場合、ＡＢＣＤＥという文字列の各文字を属性値ｘｔとして、暗号文の要素ｃｔが生成される。つまり、要素ｃ１には属性値Ａが設定され、要素ｃ２には属性値Ｂが設定され、要素ｃ３には属性値Ｃが設定され、要素ｃ４には属性値Ｄが設定され、要素ｃ５には属性値Ｅが設定される。
一方、ＢＡという文字列の各文字を属性値ｖｔとして、オリジナル検索鍵が生成される。つまり、要素ｋ＊１には属性値Ｂが設定され、要素ｋ＊２には属性値Ａが設定される。
【００３０】
検索処理では、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１と、要素ｋ＊２の基底Ｂ＊２とが入れ替わるように変換して変換後検索鍵を生成し、変換後検索鍵で暗号化タグを復号する。
【００３１】
例えば、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１を基底Ｂ＊２に変換し、要素ｋ＊２の基底Ｂ＊２を基底Ｂ＊１に変換して、変換後検索鍵が生成される。
この場合、属性値Ｂが設定された要素ｃ２と属性値Ｂが設定された要素ｋ＊１との内積が取られ、属性値Ａが設定された要素ｃ１と属性値Ａが設定された要素ｋ＊２との内積が取られる。要素ｃ２と要素ｋ＊１とでは属性値が対応しており、要素ｃ１と要素ｋ＊２とでは属性値が対応しているため、変換後検索鍵で暗号化タグを復号できる。したがって、変換後検索鍵で暗号化タグが検索される。
【００３２】
このように、オリジナル検索鍵の要素ｋ＊１の基底Ｂ＊１と、要素ｋ＊２の基底Ｂ＊２とが入れ替わるように変換して変換後検索鍵を生成することにより、検索キーワードの文字列の順序を入れ替えた部分一致秘匿検索方式を実現できる。
【００３３】
＊＊＊構成の説明＊＊＊
実施の形態１に係る部分一致秘匿検索方式の構成について説明する。
部分一致秘匿検索方式は、ＫＧアルゴリズムと、ＴａｇＧｅｎアルゴリズムと、ＴｒａｐＧｅｎアルゴリズムと、ＴｒａｐＳｈｉｆｔアルゴリズムと、Ｓｅａｒｃｈアルゴリズムとを備える。
【００３４】
ＫＧアルゴリズムは、セキュリティパラメータλとベクトル長ｄとを入力として、公開鍵ｐｋと、秘密鍵ｓｋと、シフト用秘密鍵ｓｓｋとを出力するアルゴリズムである。
【００３５】
ＴａｇＧｅｎアルゴリズムは、公開鍵ｐｋと、属性ベクトルｘ→とを入力として、暗号化タグＥＴｘを出力する確率的アルゴリズムである。
【００３６】
ＴｒａｐＧｅｎアルゴリズムは、公開鍵ｐｋと、秘密鍵ｓｋと、述語ベクトルｖ→とを入力として、オリジナル検索鍵ＴＤｖを出力する確率的アルゴリズムである。
【００３７】
ＴｒａｐＳｈｉｆｔアルゴリズムは、オリジナル検索鍵ＴＤｖと、シフト情報ＳＩと、シフト用秘密鍵ｓｓｋとを入力として、変換後検索鍵ＴＤｖ’を出力するアルゴリズムである。
【００３８】
Ｓｅａｒｃｈアルゴリズムは、公開鍵ｐｋと、暗号化タグＥＴｘと、変換後検索鍵ＴＤｖ’とを入力として、検索にヒットしたことを示す０、又は、検索にヒットしなかったことを示す１を出力する確定的アルゴリズムである。
【００３９】
図８に基づき、実施の形態１に係る秘匿検索システム１０の構成について説明する。
秘匿検索システム１０は、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とを備える。
なお、ここでは、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とをそれぞれ別の装置としているが、これらの装置のうち２つ以上の装置が１つの装置で構成されていてもよい。例えば、変換後検索鍵生成装置４００と検索装置５００とは１つの装置で構成されていてもよい。したがって、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とを、それぞれ鍵生成部と、暗号化タグ生成部と、検索鍵生成部と、変換後検索鍵生成部と、検索部と読み替え、ある装置の要素としてもよい。
【００４０】
鍵生成装置１００は、セキュリティパラメータλと、ベクトル長ｄを入力として、ＫＧアルゴリズムを実行して、公開鍵ｐｋと、秘密鍵ｓｋと、シフト用秘密鍵ｓｓｋとを出力する。
【００４１】
暗号化タグ生成装置２００は、公開鍵ｐｋと、属性ベクトルｘ→とを入力として、ＴａｇＧｅｎアルゴリズムを実行して、暗号化タグＥＴｘを出力する。
【００４２】
検索鍵生成装置３００は、公開鍵ｐｋと、秘密鍵ｓｋと、述語ベクトルｖ→とを入力として、ＴｒａｐＧｅｎアルゴリズムを実行して、オリジナル検索鍵ＴＤｖを出力する。
【００４３】
変換後検索鍵生成装置４００は、オリジナル検索鍵ＴＤｖと、シフト情報ＳＩと、シフト用秘密鍵ｓｓｋとを入力として、ＴｒａｐＳｈｉｆｔアルゴリズムを実行して、変換後検索鍵ＴＤｖ’を出力する。
【００４４】
検索装置５００は、公開鍵ｐｋと、暗号化タグＥＴｘと、変換後検索鍵ＴＤｖ’とを入力として、Ｓｅａｒｃｈアルゴリズムを実行して、検索にヒットしたことを示す０、又は、検索にヒットしなかったことを示す１を出力する。
【００４５】
図９に基づき、実施の形態１に係る鍵生成装置１００の構成について説明する。
鍵生成装置１００は、情報取得部１１０と、基底生成部１２０と、変換行列生成部１３０と、鍵生成部１４０と、鍵出力部１５０とを備える。
【００４６】
情報取得部１１０は、セキュリティパラメータλと、ベクトル長ｄとを取得する。
【００４７】
基底生成部１２０は、セキュリティパラメータλに基づき、部分一致秘匿検索方式を実現するための基礎となる基底Ｂ０と基底Ｂ＊０と基底Ｂ１と基底Ｂ＊１とを生成する。また、基底生成部１２０は、パラメータｐａｒａｍを生成する。
【００４８】
変換行列生成部１３０は、ベクトル長ｄを用いて、ｉ＝１，．．．，ｄ−１の各整数ｉについて、変換行列Ｗｉと変換行列Ｗ＊ｉとを生成する。
【００４９】
鍵生成部１４０は、基底Ｂ０及び基底Ｂ１と、パラメータｐａｒａｍと、変換行列Ｗｉとを用いて、公開鍵ｐｋを生成する。また、鍵生成部１４０は、基底Ｂ＊０及び基底Ｂ＊０と、変換行列Ｗ＊ｉとを用いて、秘密鍵ｓｋを生成する。また、鍵生成部１４０は、変換行列Ｗ＊ｉを用いて、シフト用秘密鍵ｓｓｋを生成する。
【００５０】
鍵出力部１５０は、公開鍵ｐｋを公開する。また、鍵出力部１５０は、秘密鍵ｓｋを検索鍵生成装置３００へ出力する。また、鍵出力部１５０は、シフト用秘密鍵ｓｓｋを変換後検索鍵生成装置４００に出力する。
【００５１】
図１０に基づき、実施の形態１に係る暗号化タグ生成装置２００の構成を説明する。
暗号化タグ生成装置２００は、情報取得部２１０と、タグ生成部２２０と、暗号化タグ出力部２３０とを備える。
【００５２】
情報取得部２１０は、公開鍵ｐｋと、属性ベクトルｘ→とを取得する。
【００５３】
タグ生成部２２０は、公開鍵ｐｋと、属性ベクトルｘ→とを用いて、複数の基底Ｂｔのうちの少なくとも一部の基底Ｂｔ上のタグベクトルｃｔを含む暗号化タグＥＴｘを生成する。タグ生成部２２０は、乱数生成部２２１と、要素生成部２２２とを備える。
【００５４】
暗号化タグ出力部２３０は、暗号化タグＥＴｘを検索装置５００に出力する。
【００５５】
図１１に基づき、実施の形態１に係る検索鍵生成装置３００の構成を説明する。
検索鍵生成装置３００は、情報取得部３１０と、鍵生成部３２０と、鍵出力部３３０とを備える。
【００５６】
情報取得部３１０は、公開鍵ｐｋと、秘密鍵ｓｋと、述語ベクトルｖ→とを取得する。
【００５７】
鍵生成部３２０は、公開鍵ｐｋと、秘密鍵ｓｋと、述語ベクトルｖ→とを用いて、文字列の各文字が位置を指定されて設定されたオリジナル検索鍵ＴＤｖを生成する。ここでは、鍵生成部３２０は、複数の基底Ｂ＊ｔのうちの少なくとも一部の基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔを含むオリジナル検索鍵ＴＤｖを生成する。鍵生成部３２０は、乱数生成部３２１と、秘密値生成部３２２と、要素生成部３２３とを備える。
【００５８】
鍵出力部３３０は、オリジナル検索鍵ＴＤｖを変換後検索鍵生成装置４００に出力する。
【００５９】
図１２に基づき、実施の形態１に係る変換後検索鍵生成装置４００の構成を説明する。
変換後検索鍵生成装置４００は、情報取得部４１０と、判定部４２０と、鍵変換部４３０と、鍵出力部４４０とを備える。
【００６０】
情報取得部４１０は、オリジナル検索鍵ＴＤｖと、シフト情報ＳＩと、シフト用秘密鍵ｓｓｋとを取得する。
【００６１】
判定部４２０は、シフト情報ＳＩに基づきオリジナル検索鍵ＴＤｖを変換可能か否かを判定する。
【００６２】
鍵変換部４３０は、変換可能である場合に、シフト用秘密鍵ｓｓｋを用いて、シフト情報ＳＩに基づきオリジナル検索鍵ＴＤｖを変換して、変換後検索鍵ＴＤｖ’を生成する。特に、鍵変換部４３０は、オリジナル検索鍵ＴＤｖに設定された文字のうち少なくとも一部の文字に対して指定された位置を他の位置に変換することにより、変換後検索鍵ＴＤｖ’を生成する。ここでは、鍵変換部４３０は、は、オリジナル検索鍵ＴＤｖに含まれる少なくとも一部の検索ベクトルｋ＊ｔを複数の基底Ｂ＊ｔのうちの他の基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔに変換することにより、変換後検索鍵ＴＤｖ’を生成する。
【００６３】
鍵出力部４４０は、変換後検索鍵ＴＤｖ’を検索装置５００に出力する。
【００６４】
図１３に基づき、実施の形態１に係る検索装置５００の構成を説明する。
検索装置５００は、情報取得部５１０と、検索判定部５２０と、結果出力部５３０とを備える。
【００６５】
情報取得部５１０は、公開鍵ｐｋと、暗号化タグＥＴｘと、変換後検索鍵ＴＤｖ’とを取得する。
【００６６】
検索判定部５２０は、暗号化タグ生成装置２００が生成した複数の暗号化タグＥＴｘであって、文字列の各文字が位置を指定されて設定された複数の暗号化タグＥＴｘから、変換後検索鍵生成装置４００が生成した変換後検索鍵ＴＤｖ’に設定された各文字について、その文字と、その文字に対して指定された位置に設定された文字とが一致する暗号化タグＥＴｘを検索する。ここでは、検索判定部５２０は、公開鍵ｐｋと変換後検索鍵ＴＤｖ’とを用いて、暗号化タグＥＴｘを復号することにより、検索にヒットしたか否かを判定する。つまり、検索判定部５２０は、暗号化タグ生成装置２００が生成した複数の暗号化タグＥＴｘから、変換後検索鍵生成装置４００が生成した変換後検索鍵ＴＤｖ’に対応する暗号化タグＥＴｘを検索する。
【００６７】
結果出力部５３０は、検索にヒットしたことを示す０、又は、検索にヒットしなかったことを示す１を出力する。
【００６８】
＊＊＊動作の説明＊＊＊
図１４に基づき、実施の形態１に係るＫＧアルゴリズムの処理を説明する。
上述した通り、ＫＧアルゴリズムは、鍵生成装置１００によって実行される。ＫＧアルゴリズムは、実施の形態１に係る秘匿検索方法における鍵生成工程に相当する。また、ＫＧアルゴリズムは、実施の形態１に係る秘匿検索プログラムにおける鍵生成処理に相当する。
【００６９】
（Ｓ１０１：情報取得処理）
情報取得部１１０は、秘匿検索システム１０の管理者等によって入力装置により入力された、セキュリティパラメータλと、ベクトル長ｄとを取得する。ベクトル長ｄは、２以上の整数である。
【００７０】
（Ｓ１０２：基底生成処理）
基底生成部１２０は、セキュリティパラメータλを入力として、数１１２を計算して、基底Ｂ０と基底Ｂ＊０と基底Ｂ１と基底Ｂ＊１と、双対ペアリングベクトル空間のパラメータｐａｒａｍとを生成する。
【数１１２】
2016113878.tif 000014
なお、数１１２において、Ｇｂｐｇは、双線形ペアリング群を生成する関数であり、Ｇｄｐｖｓは、双対ペアリングベクトル空間を生成する関数である。
【００７１】
（Ｓ１０３：変換行列生成処理）
変換行列生成部１３０は、ｉ＝１，．．．，ｄ−１の各整数ｉについて、数１１３を計算して、変換行列Ｗｉと変換行列Ｗ＊ｉとを生成する。
【数１１３】
2016113878.tif 000015
【００７２】
（Ｓ１０４：公開鍵生成処理）
鍵生成部１４０は、ｉ＝１，．．．，ｄ−１の各整数ｉについて、Ｓ１０２で生成された基底Ｂ１と、Ｓ１０３で生成された変換行列Ｗｉとを入力として、数１１４を計算して、ｉ＝２，．．．，ｄの各整数ｉについての基底Ｂｉを生成する。
【数１１４】
2016113878.tif 000016
鍵生成部１４０は、Ｓ１０２で生成された基底Ｂ０の部分基底Ｂ＾０と、ｉ＝１，．．．，ｄの各整数ｉについて、部分基底Ｂ＾ｉとを数１１５に示すように生成する。
【数１１５】
2016113878.tif 000017
鍵生成部１４０は、ｉ＝０，．．．，ｄの各整数ｉについての部分基底Ｂ＾ｉと、Ｓ１０２で生成されたパラメータｐａｒａｍとを公開鍵ｐｋとする。
【００７３】
（Ｓ１０５：秘密鍵生成処理）
鍵生成部１４０は、ｉ＝１，．．．，ｄ−１の各整数ｉについて、Ｓ１０２で生成された基底Ｂ＊１と、Ｓ１０３で生成された変換行列Ｗ＊ｉとを入力として、数１１６を計算して、ｉ＝２，．．．，ｄの各整数ｉについての基底Ｂ＊ｉを生成する。
【数１１６】
2016113878.tif 000018
鍵生成部１４０は、Ｓ１０２で生成された基底Ｂ＊０の部分基底Ｂ＾＊０と、ｉ＝１，．．．，ｄの各整数ｉについて、部分基底Ｂ＾＊ｉとを数１１７に示すように生成する。
【数１１７】
2016113878.tif 000019
鍵生成部１４０は、ｉ＝０，．．．，ｄの各整数ｉについての部分基底Ｂ＾＊ｉを秘密鍵ｓｋとする。
【００７４】
（Ｓ１０６：シフト用秘密鍵生成処理）
鍵生成部１４０は、Ｓ１０３で生成された、ｉ＝１，．．．，ｄ−１の各整数ｉについての変換行列Ｗ＊ｉをシフト用秘密鍵ｓｓｋとする。
【００７５】
（Ｓ１０７：鍵出力処理）
鍵出力部１５０は、Ｓ１０４で生成された公開鍵ｐｋを公開用のサーバ等へ出力して、公開鍵ｐｋを公開する。鍵出力部１５０は、Ｓ１０５で生成された秘密鍵ｓｋを秘密裡に検索鍵生成装置３００へ出力する。鍵出力部１５０は、Ｓ１０６で生成されたシフト用秘密鍵ｓｓｋを秘密裡に変換後検索鍵生成装置４００に出力する。
【００７６】
図１５に基づき、実施の形態１に係るＴａｇＧｅｎアルゴリズムの処理を説明する。
上述した通り、ＴａｇＧｅｎアルゴリズムは、暗号化タグ生成装置２００によって実行される。ＴａｇＧｅｎアルゴリズムは、実施の形態１に係る秘匿検索方法における暗号化タグ生成工程に相当する。また、ＴａｇＧｅｎアルゴリズムは、実施の形態１に係る秘匿検索プログラムにおける暗号化タグ生成処理に相当する。
【００７７】
（Ｓ２０１：情報取得処理）
情報取得部２１０は、鍵生成装置１００によって公開された公開鍵ｐｋを取得する。
情報取得部２１０は、暗号化タグ生成装置２００の使用者等によって入力装置により入力された、属性ベクトルｘ→を取得する。属性ベクトルｘ→：＝｛（ｔ，ｘｔ）｜ｔ∈Ｉｘ⊆｛１，．．．，ｄ｝｝である。Ｉｘは、インデックスの集合である。例えば、属性ベクトルｘ→の各要素ｘｔには、図５から図７で説明したように、検索タグとなる文字列の各文字が設定される。
【００７８】
（Ｓ２０２：乱数生成処理）
乱数生成部２２１は、数１１８に示すように、乱数を生成する。
【数１１８】
2016113878.tif 000020
【００７９】
（Ｓ２０３：タグ要素生成処理）
要素生成部２２２は、Ｓ２０１で取得された公開鍵ｐｋ及び属性ベクトルｘ→と、Ｓ２０２で生成された乱数とを入力として、数１１９に示すように、タグベクトルｃ０と、ｔ∈Ｉｘの各整数ｔについてのタグベクトルｃｔと、タグベクトルｃＴとを生成する。
【数１１９】
2016113878.tif 000021
【００８０】
（Ｓ２０４：タグ出力処理）
暗号化タグ出力部２３０は、Ｓ２０１で取得されたインデックスの集合Ｉｘと、Ｓ２０３で生成されたタグベクトルｃ０及びｔ∈Ｉｘの各整数ｔについてのタグベクトルｃｔ及びタグベクトルｃＴとを要素として含む暗号化タグＥＴｘを検索装置５００に出力する。
【００８１】
図１６に基づき、実施の形態１に係るＴｒａｐＧｅｎアルゴリズムの処理を説明する。
上述した通り、ＴｒａｐＧｅｎアルゴリズムは、検索鍵生成装置３００によって実行される。ＴｒａｐＧｅｎアルゴリズムは、実施の形態１に係る秘匿検索方法における検索鍵生成工程に相当する。また、ＴｒａｐＧｅｎアルゴリズムは、実施の形態１に係る秘匿検索プログラムにおける検索鍵生成処理に相当する。
【００８２】
（Ｓ３０１：情報取得処理）
情報取得部３１０は、鍵生成装置１００によって公開された公開鍵ｐｋと、鍵生成装置１００によって出力された秘密鍵ｓｋとを取得する。
情報取得部３１０は、検索鍵生成装置３００の使用者等によって入力装置により入力された、述語ベクトルｖ→を取得する。述語ベクトルｖ→：＝｛（ｔ，ｖｔ）｜ｔ∈Ｉｖ⊆｛１，．．．，ｄ｝｝である。Ｉｖは、インデックスの集合である。例えば、述語ベクトルｖ→の各要素ｖｔには、図５から図７で説明したように、検索キーワードとなる文字列の各文字が設定される。
【００８３】
（Ｓ３０２：乱数生成処理）
乱数生成部３２１は、数１２０に示すように、乱数を生成する。
【数１２０】
2016113878.tif 000022
【００８４】
（Ｓ３０３：秘密値生成処理）
秘密値生成部３２２は、Ｓ２０２で生成されたｔ∈Ｉｖの各整数ｔについての乱数ｓｔを入力として、秘密値ｓ０＝Σｔ∈Ｉｖｓｔを生成する。
【００８５】
（Ｓ３０４：鍵要素生成処理）
要素生成部３２３は、Ｓ３０１で取得された公開鍵ｐｋ及び秘密鍵ｓｋ及び述語ベクトルｖ→と、Ｓ３０２で生成された乱数と、Ｓ３０３で生成された秘密値ｓ０とを入力として、数１２１に示すように、検索ベクトルｋ＊０と、ｔ∈Ｉｖの各整数ｔについての検索ベクトルｋ＊ｔとを生成する。
【数１２１】
2016113878.tif 000023
【００８６】
（Ｓ３０５：鍵出力処理）
鍵出力部３３０は、Ｓ３０１で取得されたインデックスの集合Ｉｖと、Ｓ３０４で生成された検索ベクトルｋ＊０及びｔ∈Ｉｖの各整数ｔについての検索ベクトルｋ＊ｔとを要素として含むオリジナル検索鍵ＴＤｖを変換後検索鍵生成装置４００に出力する。
【００８７】
図１７に基づき、実施の形態１に係るＴｒａｐＳｈｉｆｔアルゴリズムの処理を説明する。
上述した通り、ＴｒａｐＳｈｉｆｔアルゴリズムは、変換後検索鍵生成装置４００によって実行される。ＴｒａｐＳｈｉｆｔアルゴリズムは、実施の形態１に係る秘匿検索方法における変換後検索鍵生成工程に相当する。また、ＴｒａｐＳｈｉｆｔアルゴリズムは、実施の形態１に係る秘匿検索プログラムにおける変換後検索鍵生成処理に相当する。
【００８８】
（Ｓ４０１：情報取得処理）
情報取得部４１０は、検索鍵生成装置３００によって出力されたオリジナル検索鍵ＴＤｖを取得する。
情報取得部４１０は、シフト情報ＳＩを取得する。シフト情報ＳＩ：＝（Ｉｖ’⊆｛１，．．．，ｄ｝，ρ）である。つまり、シフト情報ＳＩは、インデックスの集合Ｉｖ’と、遷移情報ρとを含む。遷移情報ρは、インデックスの集合Ｉｖに含まれるインデックスｔiをインデックスの集合Ｉｖ’に含まれるインデックスｔ’iに移すことを表現した情報である。ここでｉ＝１，．．．，ｄである。
情報取得部４１０は、鍵生成装置１００によって出力されたシフト用秘密鍵ｓｓｋを取得する。
【００８９】
（Ｓ４０２：サイズ判定処理）
判定部４２０は、インデックスの集合Ｉｖのサイズ｜Ｉｖ｜＝Ｕと、インデックスの集合Ｉｖ’のサイズ｜Ｉｖ’｜＝Ｕ’とが等しいか否かを判定する。これにより、判定部４２０は、シフト情報ＳＩに基づきオリジナル検索鍵ＴＤｖを変換可能か否かを判定する。
判定部４２０は、Ｕ＝Ｕ’であれば変換可能であるため、処理をＳ３０３へ進め、Ｕ≠Ｕ’であれば変換不可能であるため、処理を終了する。
【００９０】
（Ｓ４０３：インデックス初期化処理）
鍵変換部４３０は、インデックスの集合Ｉｖのうち、最も小さい値のインデックスｔをインデックスｔｉとして選択する。
【００９１】
（Ｓ４０４：シフト判定処理）
鍵変換部４３０は、遷移情報ρがｔｉ＝ｔ’ｉを示すか、又は、ｔｉ＜ｔ’ｉを示すか、又は、ｔｉ＞ｔ’ｉを示すかを判定する。
鍵変換部４３０は、ｔｉ＝ｔ’ｉを示す場合には、処理をＳ４０５へ進め、ｔｉ＜ｔ’ｉを示す場合には、処理をＳ４０６へ進め、ｔｉ＞ｔ’ｉを示す場合には、処理をＳ４０７へ進める。
【００９２】
（Ｓ４０５：シフトＡ処理）
鍵変換部４３０は、数１２２に示すように、検索ベクトルｋ＊ｔ’ｉを生成する。
【数１２２】
2016113878.tif 000024
つまり、鍵変換部４３０は、検索ベクトルｋ＊ｔｉをそのまま検索ベクトルｋ＊ｔ’ｉとする。
【００９３】
（Ｓ４０６：シフトＢ処理）
鍵変換部４３０は、数１２３に示すように、検索ベクトルｋ＊ｔ’ｉを生成する。
【数１２３】
2016113878.tif 000025
つまり、鍵変換部４３０は、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔｉに、ｊ＝ｔｉ，．．．，ｔ’ｉ−１の各整数ｊについての変換行列Ｗ＊ｊを順に乗じて、基底Ｂ＊ｔ’ｉ上の検索ベクトルｋ＊ｔ’ｉに変換する。
【００９４】
（Ｓ４０７：シフトＣ処理）
鍵変換部４３０は、数１２４に示すように、検索ベクトルｋ＊ｔ’ｉを生成する。
【数１２４】
2016113878.tif 000026
つまり、鍵変換部４３０は、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔに、ｊ＝ｔｉ−１，．．．，ｔ’ｉの各整数ｊについての変換行列Ｗ＊ｊの逆行列（Ｗ＊ｊ）−１を順に乗じて、基底Ｂ＊ｔ’ｉ上の検索ベクトルｋ＊ｔ’ｉに変換する。
【００９５】
（Ｓ４０８：終了判定処理）
鍵変換部４３０は、インデックスの集合Ｉｖの全てのインデックスｔについての処理が終了したか否かを判定する。
鍵変換部４３０は、終了していない場合、インデックスの集合Ｉｖに含まれるインデックスｔのうち、現在選択されているインデックスｔの次に大きい値のインデックスｔをインデックスｔｉとして選択して、処理をＳ４０４に戻す。一方、鍵変換部４３０は、終了している場合、処理をＳ４０９に進める。
【００９６】
（Ｓ４０９：鍵出力処理）
鍵出力部４４０は、Ｓ４０１で取得されたインデックスの集合Ｉｖ’及び検索ベクトルｋ＊０と、Ｓ４０５からＳ４０７で生成されたｔ’∈Ｉｖ’の各整数ｔ’についての検索ベクトルｋ＊ｔ’とを要素として含む変換後検索鍵ＴＤｖ’を検索装置５００に出力する。
【００９７】
つまり、複数の基底Ｂ＊ｔは、ｔ＝１，．．．，ｄ−１の各整数ｔについて、基底Ｂ＊ｔ＋１が基底Ｂ＊ｔを変換行列Ｗ＊ｔによって変換されて得られる、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔである。そして、変換後検索鍵生成装置４００は、オリジナル検索鍵ＴＤｖに含まれる少なくとも一部の検索ベクトルｋ＊ｔを、変換行列Ｗ＊ｔにより他の基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔに変換する。
より具体的には、複数の基底Ｂ＊ｔは、ｔ＝１，．．．，ｄ−１の各整数ｔについて、基底Ｂ＊ｔ＋１が基底Ｂ＊ｔに変換行列Ｗ＊ｔを乗じて得られたものである。そして、変換後検索鍵生成装置４００は、１以上ｄ以下の整数ｔ，ｔ’について、ｔ＜ｔ’のときには、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔにｊ＝ｔ，．．．，ｔ’−１の各整数ｊについての変換行列Ｗ＊ｊを乗じて、検索ベクトルｋ＊ｔを基底Ｂ＊ｔ’上の検索ベクトルｋ＊ｔ’に変換する。変換後検索鍵生成装置４００は、ｔ＞ｔ’の場合のときには、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔにｊ＝ｔ−１，．．．，ｔ’の各整数ｊについての変換行列Ｗ＊ｊの逆行列（Ｗ＊ｊ）−１を乗じて、検索ベクトルｋ＊ｔを基底Ｂ＊ｔ’上の検索ベクトルｋ＊ｔ’に変換する。
これにより、変換後検索鍵生成装置４００は、変換後検索鍵ＴＤｖ’を生成する。
【００９８】
図１８に基づき、実施の形態１に係るＳｅａｒｃｈアルゴリズムの処理を説明する。
上述した通り、Ｓｅａｒｃｈアルゴリズムは、検索装置５００によって実行される。Ｓｅａｒｃｈアルゴリズムは、実施の形態１に係る秘匿検索方法における検索工程に相当する。また、Ｓｅａｒｃｈアルゴリズムは、実施の形態１に係る秘匿検索プログラムにおける検索処理に相当する。
【００９９】
（Ｓ５０１：情報取得処理）
情報取得部５１０は、鍵生成装置１００によって公開された公開鍵ｐｋを取得する。
情報取得部５１０は、暗号化タグ生成装置２００によって出力された暗号化タグＥＴｘを取得する。
情報取得部５１０は、変換後検索鍵生成装置４００によって出力された変換後検索鍵ＴＤｖ’を取得する。
【０１００】
（Ｓ５０２：検索可能判定処理）
検索判定部５２０は、Ｓ５０１で取得された変換後検索鍵ＴＤｖ’に含まれるインデックスの集合Ｉｖ’が、Ｓ５０１で取得された暗号化タグＥＴｘに含まれるインデックスの集合Ｉｘの部分集合であるか否かを判定する。
検索判定部５２０は、部分集合である場合には検索可能であるとして、処理をＳ５０３に進め、部分集合でない場合には検索不可能であるとして、処理を終了する。
【０１０１】
（Ｓ５０３：復号処理）
検索判定部５２０は、数１２５に示すように、暗号化タグＥＴｘに含まれるタグと、変換後検索鍵ＴＤｖ’に含まれる検索ベクトルとについて、ペアリング演算して、セッション鍵Ｋを計算する。
【数１２５】
2016113878.tif 000027
つまり、検索判定部５２０は、内積述語暗号方式で言うところの、公開鍵ｐｋと変換後検索鍵ＴＤｖ’とを用いて、暗号化タグＥＴｘを復号する処理を行う。
【０１０２】
（Ｓ５０４：検索判定処理）
検索判定部５２０は、Ｓ５０３で計算されたセッション鍵Ｋが、暗号化タグＥＴｘに含まれるタグベクトルｃＴと等しいか否かを判定する。
検索判定部５２０は、等しい場合、処理をＳ５０５へ進め、等しくない場合、処理をＳ５０６へ進める。
【０１０３】
（Ｓ５０５：結果Ａ出力処理）
結果出力部５３０は、検索にヒットしたことを示す０を出力する。
【０１０４】
（Ｓ５０６：結果Ｂ出力処理）
結果出力部５３０は、検索にヒットしなかったことを示す１を出力する。
【０１０５】
つまり、検索装置５００は、変換後検索鍵ＴＤｖ’に含まれる検索ベクトルｋ＊ｔと、各暗号化タグＥＴｘに含まれるタグベクトルｃｔとを用いた計算をすることにより、変換後検索鍵ＴＤｖ’に対応する暗号化タグＥＴｘを検索する。
より具体的には、検索装置５００は、変換後検索鍵ＴＤｖ’に含まれる検索ベクトルｋ＊ｔと、各暗号化タグＥＴｘに含まれるタグベクトルｃｔであって、その検索ベクトルｋ＊ｔの基底Ｂ＊ｔに対応する基底Ｂｔ上のタグベクトルｃｔとの内積の計算をすることにより、変換後検索鍵ＴＤｖ’に対応する暗号化タグＥＴｘを検索する。
【０１０６】
以上のように、実施の形態１に係る秘匿検索システム１０は、変換後検索鍵生成装置４００がオリジナル検索鍵ＴＤｖに含まれる少なくとも一部の検索ベクトルｋ＊ｔを複数の基底Ｂ＊ｔのうちの他の基底Ｂ＊ｔ’上の検索ベクトルｋ＊ｔ’に変換することにより、変換後検索鍵ＴＤｖ’を生成することができる。
そのため、図５に基づき説明したように、オリジナル検索鍵ＴＤｖに含まれる検索ベクトルｋ＊ｔの基底Ｂ＊ｔの添え字ｔを１つづつ順にずらして変換後検索鍵ＴＤｖ’を生成することにより、部分一致秘匿検索方式を実現できる。
【０１０７】
なお、基底Ｂ＊ｔの添え字ｔを１つづつ順にずらして変換後検索鍵ＴＤｖ’を生成することに限らず、オリジナル検索鍵ＴＤｖに含まれる全ての検索ベクトルｋ＊ｔを、検索ベクトルｋ＊ｔの基底Ｂ＊ｔの添え字ｔが同じ値だけずれるように変換することにより、変換後検索鍵を生成してもよい。
【０１０８】
実施の形態１に係る秘匿検索システム１０では、検索鍵生成装置３００は、１つのオリジナル検索鍵ＴＤｖを生成して変換後検索鍵生成装置４００へ送信すれば、部分一致秘匿検索を行うことができる。そのため、検索者端末である検索鍵生成装置３００が送信する検索情報量を減らすことが可能である。
また、実施の形態１に係る秘匿検索システム１０は、オリジナル検索鍵ＴＤｖの情報が検索装置５００に漏洩することもない。
【０１０９】
また、図６に基づき説明したように、オリジナル検索鍵ＴＤｖに含まれる検索ベクトルｋ＊１の基底Ｂ＊１の添え字と、検索ベクトルｋ２の基底Ｂ＊２の添え字との差が大きくなるように変換して変換後検索鍵ＴＤｖ’を生成することもできる。
より一般的には、オリジナル検索鍵ＴＤｖに含まれる検索ベクトルｋ＊ｔのうち、検索ベクトルｋ＊ｔの基底Ｂ＊ｔの添え字ｔが基準値未満の検索ベクトルと、基準値以上の検索ベクトルｋ＊ｔとの間で、添え字ｔの値の差が大きくなるように、オリジナル検索鍵ＴＤｖに含まれる検索ベクトルｋ＊ｔを変換することにより、変換後検索鍵ＴＤｖ’を生成することもできる。
これにより、検索キーワードの文字列の途中に間を空けた部分一致秘匿検索方式を実現できる。
【０１１０】
また、図７に基づき説明したように、オリジナル検索鍵ＴＤｖの要素ｋ＊１の基底Ｂ＊１と、要素ｋ＊２の基底Ｂ＊２とが入れ替わるように変換して変換後検索鍵ＴＤｖ’を生成することもできる。
より一般的には、オリジナル検索鍵ＴＤｖに含まれる第１検索ベクトルと第２検索ベクトルとを、第１検索ベクトルの基底Ｂ＊ｔ１と第２検索ベクトルの基底Ｂ＊ｔ２とが入れ替わるように変換することにより、変換後検索鍵ＴＤｖ’を生成することもできる。
これにより、検索キーワードの文字列の順序を入れ替えた部分一致秘匿検索方式を実現できる。
【０１１１】
なお、上記説明では、検索可能な利用者を限定せず、全ての利用者が全ての暗号化タグＥＴｘを検索可能であった。しかし、上述した部分一致秘匿検索方式を、内積述語暗号方式と組み合わせることにより、暗号化タグＥＴｘ毎に、検索可能な利用者を限定することも可能である。
この場合、ＫＧアルゴリズムにおいて、ｉ＝１，．．．，ｄの各整数ｉについての基底Ｂｉ及び基底Ｂ＊ｉに加えて、ｉ＝ｄ＋１，．．．，ｄ＋ｎの各整数ｉについての基底Ｂｉ及び基底Ｂ＊ｉを検索可能な利用者を限定するために生成する。そして、ＴａｇＧｅｎアルゴリズムにおいて、ｔ＝ｄ＋１，．．．，ｄ＋ｎの少なくとも一部の整数ｔについてのタグベクトルｃｔに関しては検索可能な利用者の属性を示す要素ｘｔを設定し、ＴｒａｐＧｅｎアルゴリズムにおいて、ｔ＝ｄ＋１，．．．，ｄ＋ｎの少なくとも一部の整数ｔについての検索ベクトルｋ＊ｔに関しては検索者の属性を示す要素ｖｔを設定する。
これにより、検索可能な利用者の属性を示す要素ｘｔと、検索者の属性を示す要素ｖｔとが対応している場合に限り検索可能となる。
【０１１２】
図１９に基づき、実施の形態１に係る鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とのハードウェア構成例を説明する。
鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とはコンピュータである。
鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とは、プロセッサ９０１、補助記憶装置９０２、メモリ９０３、通信装置９０４、入力インタフェース９０５、ディスプレイインタフェース９０６といったハードウェアを備える。
プロセッサ９０１は、信号線９１０を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
入力インタフェース９０５は、ケーブル９１１により入力装置９０７に接続されている。
ディスプレイインタフェース９０６は、ケーブル９１２によりディスプレイ９０８に接続されている。
【０１１３】
プロセッサ９０１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ９０１は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
補助記憶装置９０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。
メモリ９０３は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
通信装置９０４は、データを受信するレシーバー９０４１及びデータを送信するトランスミッター９０４２を含む。通信装置９０４は、例えば、通信チップ又はＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
入力インタフェース９０５は、入力装置９０７のケーブル９１１が接続されるポートである。入力インタフェース９０５は、例えば、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）端子である。
ディスプレイインタフェース９０６は、ディスプレイ９０８のケーブル９１２が接続されるポートである。ディスプレイインタフェース９０６は、例えば、ＵＳＢ端子又はＨＤＭＩ（登録商標）（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）端子である。
入力装置９０７は、例えば、マウス、キーボード又はタッチパネルである。
ディスプレイ９０８は、例えば、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）である。
【０１１４】
補助記憶装置９０２には、上述した情報取得部１１０、基底生成部１２０、変換行列生成部１３０、鍵生成部１４０、鍵出力部１５０、情報取得部２１０、タグ生成部２２０、乱数生成部２２１、要素生成部２２２、暗号化タグ出力部２３０、情報取得部３１０、鍵生成部３２０、乱数生成部３２１、秘密値生成部３２２、要素生成部３２３、鍵出力部３３０、情報取得部４１０、判定部４２０、鍵変換部４３０、鍵出力部４４０、情報取得部５１０、検索判定部５２０、結果出力部５３０（以下、情報取得部１１０、基底生成部１２０、変換行列生成部１３０、鍵生成部１４０、鍵出力部１５０、情報取得部２１０、タグ生成部２２０、乱数生成部２２１、要素生成部２２２、暗号化タグ出力部２３０、情報取得部３１０、鍵生成部３２０、乱数生成部３２１、秘密値生成部３２２、要素生成部３２３、鍵出力部３３０、情報取得部４１０、判定部４２０、鍵変換部４３０、鍵出力部４４０、情報取得部５１０、検索判定部５２０、結果出力部５３０をまとめて「部」と表記する）の機能を実現するプログラムが記憶されている。
このプログラムは、メモリ９０３にロードされ、プロセッサ９０１に読み込まれ、プロセッサ９０１によって実行される。
更に、補助記憶装置９０２には、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）も記憶されている。
そして、ＯＳの少なくとも一部がメモリ９０３にロードされ、プロセッサ９０１はＯＳを実行しながら、「部」の機能を実現するプログラムを実行する。
図１９では、１つのプロセッサ９０１が図示されているが、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とが複数のプロセッサ９０１を備えていてもよい。そして、複数のプロセッサ９０１が「部」の機能を実現するプログラムを連携して実行してもよい。
また、「部」の処理の結果を示す情報やデータや信号値や変数値が、メモリ９０３、補助記憶装置９０２、又は、プロセッサ９０１内のレジスタ又はキャッシュメモリにファイルとして記憶される。
【０１１５】
「部」を「サーキットリー」で提供してもよい。また、「部」を「回路」又は「工程」又は「手順」又は「処理」に読み替えてもよい。「回路」及び「サーキットリー」は、プロセッサ９０１だけでなく、ロジックＩＣ又はＧＡ（Ｇａｔｅ  Ａｒｒａｙ）又はＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）又はＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）といった他の種類の処理回路をも包含する概念である。
【符号の説明】
【０１１６】
１０  秘匿検索システム、１００  鍵生成装置、１１０  情報取得部、１２０  基底生成部、１３０  変換行列生成部、１４０  鍵生成部、１５０  鍵出力部、２００  暗号化タグ生成装置、２１０  情報取得部、２２０  タグ生成部、２２１  乱数生成部、２２２  要素生成部、２３０  暗号化タグ出力部、３００  検索鍵生成装置、３１０  情報取得部、３２０  鍵生成部、３２１  乱数生成部、３２２  秘密値生成部、３２３  要素生成部、３３０  鍵出力部、４００  変換後検索鍵生成装置、４１０  情報取得部、４２０  判定部、４３０  鍵変換部、４４０  鍵出力部、５００  検索装置、５１０  情報取得部、５２０  検索判定部、５３０  結果出力部、ｐｋ  公開鍵、ｓｋ  秘密鍵、ｓｓｋ  シフト用秘密鍵、Ｂ，Ｂ＊  基底、Ｂ＾，Ｂ＾＊  部分基底、ｐａｒａｍ  パラメータ、Ｗ，Ｗ＊  変換行列、Ｉｘ，Ｉｖ  インデックスの集合、ｘ→  属性ベクトル、ｖ→  述語ベクトル、ｃ  タグ、ｋ＊  検索ベクトル、ＳＩ  シフト情報、ＥＴｘ  暗号化タグ、ＴＤｖ  オリジナル検索鍵、ＴＤｖ’  変換後検索鍵。
【図１】
2016113878.tif 000028
【図２】
2016113878.tif 000029
【図３】
2016113878.tif 000030
【図４】
2016113878.tif 000031
【図５】
2016113878.tif 000032
【図６】
2016113878.tif 000033
【図７】
2016113878.tif 000034
【図８】
2016113878.tif 000035
【図９】
2016113878.tif 000036
【図１０】
2016113878.tif 000037
【図１１】
2016113878.tif 000038
【図１２】
2016113878.tif 000039
【図１３】
2016113878.tif 000040
【図１４】
2016113878.tif 000041
【図１５】
2016113878.tif 000042
【図１６】
2016113878.tif 000043
【図１７】
2016113878.tif 000044
【図１８】
2016113878.tif 000045
【図１９】
2016113878.tif 000046
【手続補正書】
【提出日】平成28年11月21日(2016.11.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
文字列の各文字が位置を指定されて設定されたオリジナル検索鍵を変換して変換後検索鍵を生成する変換後検索鍵生成部であって、前記オリジナル検索鍵に設定された文字のうち少なくとも一部の文字に対して指定された位置を他の位置に変換することにより、前記変換後検索鍵を生成する変換後検索鍵生成部と、
文字列の各文字が位置を指定されて設定された複数の暗号化タグから、前記変換後検索鍵生成部が生成した前記変換後検索鍵に設定された各文字について、その文字と、その文字に対して指定された位置に設定された文字とが一致する暗号化タグを検索する検索部と
を備える秘匿検索システム。
【請求項２】
前記オリジナル検索鍵は、前記各文字が設定された検索ベクトルであって、位置を指定する複数の基底のうちのいずれかの基底上のベクトルである検索ベクトルを含み、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる少なくとも一部の検索ベクトルを前記複数の基底のうちの他の基底上の検索ベクトルに変換することにより、前記変換後検索鍵を生成する
請求項１に記載の秘匿検索システム。
【請求項３】
前記複数の基底は、ｔ＝１，．．．，ｄ−１の各整数ｔについて、基底Ｂ＊ｔ＋１が基底Ｂ＊ｔを変換行列Ｗ＊ｔによって変換されて得られる、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる少なくとも一部の検索ベクトルを、前記変換行列Ｗ＊ｔにより前記他の基底上の検索ベクトルに変換する
請求項２に記載の秘匿検索システム。
【請求項４】
前記複数の基底は、ｔ＝１，．．．，ｄ−１の各整数ｔについて、基底Ｂ＊ｔ＋１が前記基底Ｂ＊ｔに変換行列Ｗ＊ｔを乗じて得られ、
前記変換後検索鍵生成部は、１以上ｄ以下の整数ｔ，ｔ’について、ｔ＜ｔ’のときには、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔにｊ＝ｔ，．．．，ｔ’−１の各整数ｊについての変換行列Ｗ＊ｊを乗じて、前記検索ベクトルｋ＊ｔを基底Ｂ＊ｔ’上の検索ベクトルｋ＊ｔ’に変換し、ｔ＞ｔ’の場合のときには、基底Ｂ＊ｔ上の検索ベクトルｋ＊ｔにｊ＝ｔ−１，．．．，ｔ’の各整数ｊについての変換行列Ｗ＊ｊの逆行列（Ｗ＊ｊ）−１を乗じて、前記検索ベクトルｋ＊ｔを基底Ｂ＊ｔ’上の検索ベクトルｋ＊ｔ’に変換する
請求項３に記載の秘匿検索システム。
【請求項５】
前記複数の基底は、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
各暗号化タグは、ｔ＝１，．．．，ｄのうちの少なくとも一部の整数ｔについて、前記基底Ｂ＊ｔに対応する基底Ｂｔ上のタグベクトルを含み、
前記検索部は、前記変換後検索鍵に含まれる検索ベクトルと、前記各暗号化タグに含まれるタグベクトルとを用いた計算をすることにより、前記変換後検索鍵に対応する暗号化タグを検索する
請求項２に記載の秘匿検索システム。
【請求項６】
前記検索部は、前記変換後検索鍵に含まれる検索ベクトルと、前記各暗号化タグに含まれるタグベクトルであって、その検索ベクトルの基底Ｂ＊ｔに対応する基底Ｂｔ上のタグベクトルとの内積の計算をすることにより、前記変換後検索鍵に対応する暗号化タグを検索する
請求項５に記載の秘匿検索システム。
【請求項７】
前記複数の基底は、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる全ての検索ベクトルを、検索ベクトルの基底Ｂ＊ｔの添え字ｔが同じ値だけずれるように変換することにより、前記変換後検索鍵を生成する
請求項２に記載の秘匿検索システム。
【請求項８】
前記複数の基底は、ｔ＝１，．．．，ｄの各整数ｔについての基底Ｂ＊ｔであり、
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる検索ベクトルのうち、検索ベクトルの基底Ｂ＊ｔの添え字ｔが基準値未満の検索ベクトルと、基準値以上の検索ベクトルとの間で、前記添え字ｔの値の差が大きくなるように、前記オリジナル検索鍵に含まれる検索ベクトルを変換することにより、前記変換後検索鍵を生成する
請求項２に記載の秘匿検索システム。
【請求項９】
前記変換後検索鍵生成部は、前記オリジナル検索鍵に含まれる第１検索ベクトルと第２検索ベクトルとを、第１検索ベクトルの基底と第２検索ベクトルの基底とが入れ替わるように変換することにより、前記変換後検索鍵を生成する
請求項２に記載の秘匿検索システム。
【請求項１０】
各文字が設定された検索ベクトルであって、位置を指定する複数の基底のうちのいずれかの基底上のベクトルである検索ベクトルを含むオリジナル検索鍵を取得する情報取得部と、
前記情報取得部が取得したオリジナル検索鍵に含まれる少なくとも一部の検索ベクトルを前記複数の基底のうちの他の基底上の検索ベクトルに変換することにより、変換後検索鍵を生成する鍵変換部と
を備える変換後検索鍵生成装置。
【国際調査報告】
2016113878.tif 000047
2016113878.tif 000048