(57)【特許請求の範囲】
【請求項１】
検索文字列の各文字が位置を指定され、属性値ｖｔが設定された検索鍵ＴＤｖを生成する検索鍵生成部と、
被検索文字列の各文字が位置を指定され、属性値ｘｔが設定された暗号化タグＥＴｘを生成する暗号化タグ生成部と、
前記暗号化タグＥＴｘの中から、前記検索鍵ＴＤｖに対応する暗号化タグＥＴｘを検索する検索部と
を備え、
前記検索鍵ＴＤｖに含まれる要素および前記暗号化タグＥＴｘに含まれる要素の一方に、前記各文字の位置を示すインデックスｔが設定され、他方に、前記インデックスｔの符号を反転したインデックス−ｔが設定され、
検索時に、前記検索鍵ＴＤｖと前記暗号化タグＥＴｘとに設定された前記インデックスｔと前記インデックス−ｔとを加算することで、前記インデックスｔと前記インデックス−ｔとを打消して、前記検索鍵ＴＤｖに対応する前記暗号化タグＥＴｘを検索し、
前記検索部は、秘密値ｓ０と、ｔ∈Ｉｖの各前記インデックスｔについての第１の分散値ｓｔと、ｔ∈Ｉｖの各インデックスｔについての第２の分散値τｔとを用いて検索を行い、
前記秘密値ｓ０と前記第１の分散値ｓｔとは、ｓ０＝Σｔ∈Ｉｖｓｔの関係を満たし、
前記第２の分散値τｔは、０＝Σｔ∈Ｉｖτｔの関係を満たし、
ここで、前記Ｉｖは、前記インデックスｔの集合であり、
前記検索鍵ＴＤｖは、
前記秘密値ｓ０が設定された基底Ｂ＊０上のベクトルである要素ｋ＊０と、
ｔ∈Ｉｖの各前記インデックスｔについて、前記第１の分散値ｓｔと前記第２の分散値τｔと前記属性値ｖｔと前記インデックスｔとが設定された基底Ｂ＊上のベクトルである要素ｋ＊ｔと
を含み、
前記検索文字列の各文字を前記属性値ｖｔとして、前記検索鍵ＴＤｖが生成され、
前記暗号化タグＥＴｘは、
前記基底Ｂ＊０に対応する基底Ｂ０上のベクトルである要素ｃ０と、
ｔ∈Ｉｘの各インデックスｔについて、前記属性値ｘｔと前記インデックス−ｔとが設定された、前記基底Ｂ＊に対応する基底Ｂ上のベクトルである要素ｃｔと
を含み、
前記被検索文字列の各文字を前記属性値ｘｔとして、前記暗号文タグＥＴｘが生成され、
ここで、前記Ｉｘは、前記インデックスｔの集合である、
秘匿検索システム。
【請求項２】
前記検索部は、前記検索鍵ＴＤｖに含まれる要素と前記暗号化タグＥＴｘに含まれる要素との内積を演算する内積述語暗号方式を用いて、前記検索鍵ＴＤｖに対応する前記暗号化タグを検索する、
請求項１に記載の秘匿検索システム。
【請求項３】
コンピュータを用いて、複数の被検索文字列の中から検索文字列を含む被検索文字列を検索する秘匿検索方法であって、
前記コンピュータにおいて実行するステップとして、
前記検索文字列の各文字が位置を指定され、属性値ｖｔが設定された検索鍵ＴＤｖを生成する検索鍵生成ステップと、
前記被検索文字列の各文字が位置を指定され、属性値ｘｔが設定された複数の暗号化タグＥＴｘを生成する暗号化タグ生成ステップと、
複数の前記暗号化タグＥＴｘから、前記検索鍵ＴＤｖに対応する暗号化タグＥＴｘを検索する検索ステップと
を備え、
前記検索鍵ＴＤｖに含まれる要素および前記暗号化タグＥＴｘに含まれる要素の一方に、前記各文字の位置を示すインデックスｔが設定され、他方に、前記インデックスｔの符号を反転したインデックス−ｔが設定され、
前記コンピュータが、検索時に、前記検索鍵ＴＤｖと前記暗号化タグＥＴｘとに設定された前記インデックスｔと前記インデックス−ｔとを加算することで、前記インデックスｔと前記インデックス−ｔとを打消して、前記検索鍵ＴＤｖに対応する前記暗号化タグＥＴｘを検索し、
前記検索ステップは、秘密値ｓ０と、ｔ∈Ｉｖの各前記インデックスｔについての第１の分散値ｓｔと、ｔ∈Ｉｖの各インデックスｔについての第２の分散値τｔとを用いて検索を行い、
前記秘密値ｓ０と前記第１の分散値ｓｔとは、ｓ０＝Σｔ∈Ｉｖｓｔの関係を満たし、
前記第２の分散値τｔは、０＝Σｔ∈Ｉｖτｔの関係を満たし、
ここで、前記Ｉｖは、前記インデックスｔの集合であり、
前記検索鍵ＴＤｖは、
前記秘密値ｓ０が設定された基底Ｂ＊０上のベクトルである要素ｋ＊０と、
ｔ∈Ｉｖの各前記インデックスｔについて、前記第１の分散値ｓｔと前記第２の分散値τｔと前記属性値ｖｔと前記インデックスｔとが設定された基底Ｂ＊上のベクトルである要素ｋ＊ｔと
を含み、
前記検索文字列の各文字を前記属性値ｖｔとして、前記検索鍵ＴＤｖが生成され、
前記暗号化タグＥＴｘは、
前記基底Ｂ＊０に対応する基底Ｂ０上のベクトルである要素ｃ０と、
ｔ∈Ｉｘの各インデックスｔについて、前記属性値ｘｔと前記インデックス−ｔとが設定された、前記基底Ｂ＊に対応する基底Ｂ上のベクトルである要素ｃｔと
を含み、
前記被検索文字列の各文字を前記属性値ｘｔとして、前記暗号文タグＥＴｘが生成され、
ここで、前記Ｉｘは、前記インデックスｔの集合である、
秘匿検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の被検索文字列の中から検索文字列を含む被検索文字列を検索する秘匿検索システムおよび秘匿検索方法に関する。
【背景技術】
【０００２】
秘匿検索とは、暗号化したままデータを検索することが可能な技術である。クラウドサービスの広がりを見せる現代において、安価かつ手間なく利用可能なクラウドストレージが、一般的に用いられるようになりつつある。一方で、極めて慎重に取り扱うべきセンシティブな情報である機微な情報を含むデータをクラウドで管理するような場合は、情報漏洩のリスクがある。そのため、データを暗号化して保管する必要がある。秘匿検索は、暗号化されているデータであっても、当該データを復号することなく検索が行えるため、安全性と利便性を両立することが可能である。【０００３】
秘匿検索では、２つの暗号化されたキーワードを用いることで検索を実現する。１つ目は、データに関連付けるキーワード（以下、被検索文字列とする）の暗号文で、暗号化タグという。２つ目は、検索するキーワード（以下、検索文字列とする）の暗号文で、検索鍵という。データを登録するときは、暗号化したデータと暗号化タグとをストレージサーバに登録する。このとき、暗号化タグは関連付けられているデータまたはデータの識別子と紐づけられて、暗号化索引として保管される。秘匿検索は、検索者が送信する検索鍵と一致する暗号化タグを、暗号化索引内から復号することなく特定することで、データおよびキーワードの情報を露出することなく実現される。【０００４】
秘匿検索では、被検索文字列と検索文字列とが等しい場合に一致と判定する方式（以下、完全一致秘匿検索とする）と、被検索文字列に検索文字列が含まれる場合に一致と判定する方式（以下、部分一致秘匿検索という）とが知られている。部分一致秘匿検索は、暗号化タグの部分文字列と一致判定が可能なため、完全一致秘匿検索よりもあいまいな検索を実現でき、利便性が高い。部分一致秘匿検索の実現方法の一つに、文字または単語など部分文字列毎に暗号文を生成する方式がある。暗号化タグまたは検索鍵の部分文字列を入れ替えたり切り離したりしてさらに検索が可能な場合、頻度分析等の攻撃手法により、部分文字列情報が漏洩する可能性がある。そのため、登録者または検索者が意図しない検索を悪意のある第三者に実行させない仕組みが必要である。【０００５】
特許文献１および特許文献２は、部分一致秘匿検索を実現することが可能な手法をそれぞれ示している。ただし、特許文献１の手法は、暗号化タグの生成と検索鍵の生成とにおいて、同じ鍵を使用するため、権限が分離できない。特許文献２の手法は、暗号化タグの生成と検索鍵の生成とで異なる鍵を使用でき、さらに検索者毎に異なる権限を持つ鍵を生成可能なため、安全性が特許文献１より高い。また、特許文献２の手法は、暗号文への分散値の埋め込み、および、部分一致検索時に必要な秘密鍵（以下、シフト用秘密鍵）を導入することで、悪意のある第三者による意図しない検索を防止している。【０００６】
また、非特許文献１は、安全性が高く、部分一致秘匿検索に利用可能な暗号方式を示している。しかしながら、非特許文献１には、特許文献２のような検索鍵変換による検索者端末から検索装置へ送信される検索情報量の削減を行うための手法については記載されていない。以下、特許文献２の検索鍵変換について説明する。【０００７】
上述したように、特許文献２は、権限を分離することで、安全性が高く柔軟性のある部分一致秘匿検索を実現している。しかしながら、特許文献２では、暗号化タグの部分文字列と検索鍵とが一致するか否かの判定を行うために、暗号化タグの部分文字列の先頭文字位置と検索鍵の先頭文字位置とを合わせる処理を行う必要がある。当該処理を「検索鍵変換」という。このように、特許文献２では、検索鍵変換を行う必要があり、暗号化タグまたは検索鍵の文字数によっては、検索時間の大幅な増加を招く可能性がある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】国際公開第２０１７／１２２３５２号
【特許文献２】国際公開第２０１６／１１３８７８号
【非特許文献】
【０００９】
【非特許文献１】Ｔａｔｓｕａｋｉ  Ｏｋａｍｏｔｏ  ａｎｄ  Ｋａｔｓｕｙｕｋｉ  Ｔａｋａｓｈｉｍａ，"Ｆｕｌｌｙ  Ｓｅｃｕｒｅ  Ｕｎｂｏｕｎｄｅｄ  Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔ  ａｎｄ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ"，Ａｓｉａｃｒｙｐｔ  ２０１２，ＬＮＣＳ  ７６５８，２０１２年，ｐ．３４９−３６６
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述したように、特許文献２における検索処理は、検索鍵変換処理の計算量が大きいため、暗号化タグの部分文字列と検索鍵とが一致するか否かの判定を多用する場合には、検索時間が長くなるという課題があった。【００１１】
この発明は、かかる課題を解決するためになされたものであり、悪意のある第三者による意図しない検索を防止しつつ、検索時間の短縮化を図ることが可能な秘匿検索システムおよび秘匿検索方法を得ることを目的とする。
【課題を解決するための手段】
【００１２】
この発明に係る秘匿検索システムは、検索文字列の各文字が位置を指定され、属性値ｖｔが設定された検索鍵ＴＤｖを生成する検索鍵生成部と、被検索文字列の各文字が位置を指定され、属性値ｘｔが設定された暗号化タグＥＴｘを生成する暗号化タグ生成部と、前記暗号化タグＥＴｘの中から、前記検索鍵ＴＤｖに対応する暗号化タグＥＴｘを検索する検索部とを備え、前記検索鍵ＴＤｖに含まれる要素および前記暗号化タグＥＴｘに含まれる要素の一方に、前記各文字の位置を示すインデックスｔが設定され、他方に、前記インデックスｔの符号を反転したインデックス−ｔが設定され、検索時に、前記検索鍵ＴＤｖと前記暗号化タグＥＴｘとに設定された前記インデックスｔと前記インデックス−ｔとを加算することで、前記インデックスｔと前記インデックス−ｔとを打消して、前記検索鍵ＴＤｖに対応する前記暗号化タグＥＴｘを検索し、前記検索部は、秘密値ｓ０と、ｔ∈Ｉｖの各前記インデックスｔについての第１の分散値ｓｔと、ｔ∈Ｉｖの各インデックスｔについての第２の分散値τｔとを用いて検索を行い、前記秘密値ｓ０と前記第１の分散値ｓｔとは、ｓ０＝Σｔ∈Ｉｖｓｔの関係を満たし、前記第２の分散値τｔは、０＝Σｔ∈Ｉｖτｔの関係を満たし、ここで、前記Ｉｖは、前記インデックスｔの集合であり、前記検索鍵ＴＤｖは、前記秘密値ｓ０が設定された基底Ｂ＊０上のベクトルである要素ｋ＊０と、ｔ∈Ｉｖの各前記インデックスｔについて、前記第１の分散値ｓｔと前記第２の分散値τｔと前記属性値ｖｔと前記インデックスｔとが設定された基底Ｂ＊上のベクトルである要素ｋ＊ｔとを含み、前記検索文字列の各文字を前記属性値ｖｔとして、前記検索鍵ＴＤｖが生成され、前記暗号化タグＥＴｘは、前記基底Ｂ＊０に対応する基底Ｂ０上のベクトルである要素ｃ０と、ｔ∈Ｉｘの各インデックスｔについて、前記属性値ｘｔと前記インデックス−ｔとが設定された、前記基底Ｂ＊に対応する基底Ｂ上のベクトルである要素ｃｔとを含み、前記被検索文字列の各文字を前記属性値ｘｔとして、前記暗号文タグＥＴｘが生成され、ここで、前記Ｉｘは、前記インデックスｔの集合である。
【００１３】
この発明に係る秘匿検索方法は、コンピュータを用いて、複数の被検索文字列の中から検索文字列を含む被検索文字列を検索する秘匿検索方法であって、前記コンピュータにおいて実行するステップとして、前記検索文字列の各文字が位置を指定され、前記属性値ｖｔが設定された検索鍵ＴＤｖを生成する検索鍵生成ステップと、前記被検索文字列の各文字が位置を指定され、前記属性値ｘｔが設定された複数の暗号化タグＥＴｘを生成する暗号化タグ生成ステップと、複数の前記暗号化タグＥＴｘから、前記検索鍵ＴＤｖに対応する暗号化タグＥＴｘを検索する検索ステップとを備え、前記検索鍵ＴＤｖに含まれる要素および前記暗号化タグＥＴｘに含まれる要素の一方に、前記各文字の位置を示すインデックスｔが設定され、他方に、前記インデックスｔの符号を反転したインデックス−ｔが設定され、前記コンピュータが、検索時に、前記検索鍵ＴＤｖと前記暗号化タグＥＴｘとに設定された前記インデックスｔと前記インデックス−ｔとを加算することで、前記インデックスｔと前記インデックス−ｔとを打消して、前記検索鍵ＴＤｖに対応する前記暗号化タグＥＴｘを検索し、前記検索ステップは、秘密値ｓ０と、ｔ∈Ｉｖの各前記インデックスｔについての第１の分散値ｓｔと、ｔ∈Ｉｖの各インデックスｔについての第２の分散値τｔとを用いて検索を行い、前記秘密値ｓ０と前記第１の分散値ｓｔとは、ｓ０＝Σｔ∈Ｉｖｓｔの関係を満たし、前記第２の分散値τｔは、０＝Σｔ∈Ｉｖτｔの関係を満たし、ここで、前記Ｉｖは、前記インデックスｔの集合であり、前記検索鍵ＴＤｖは、前記秘密値ｓ０が設定された基底Ｂ＊０上のベクトルである要素ｋ＊０と、ｔ∈Ｉｖの各前記インデックスｔについて、前記第１の分散値ｓｔと前記第２の分散値τｔと前記属性値ｖｔと前記インデックスｔとが設定された基底Ｂ＊上のベクトルである要素ｋ＊ｔとを含み、前記検索文字列の各文字を前記属性値ｖｔとして、前記検索鍵ＴＤｖが生成され、前記暗号化タグＥＴｘは、前記基底Ｂ＊０に対応する基底Ｂ０上のベクトルである要素ｃ０と、ｔ∈Ｉｘの各インデックスｔについて、前記属性値ｘｔと前記インデックス−ｔとが設定された、前記基底Ｂ＊に対応する基底Ｂ上のベクトルである要素ｃｔとを含み、前記被検索文字列の各文字を前記属性値ｘｔとして、前記暗号文タグＥＴｘが生成され、ここで、前記Ｉｘは、前記インデックスｔの集合である。
【発明の効果】
【００１４】
この発明に係る秘匿検索システムおよび秘匿検索方法によると、悪意のある第三者による意図しない検索を防止しつつ、検索時間の短縮化を図ることができる。
【図面の簡単な説明】
【００１５】
【図１】内積述語暗号における内積の取り方の説明図である。
【図２】内積述語暗号における内積の取り方の説明図である。
【図３】内積述語暗号の基本構成の説明図である。
【図４】この発明の実施の形態１に係る部分一致秘匿検索方式のキーテクニックの説明図である。
【図５】この発明の実施の形態１に係る部分一致秘匿検索方式の実現例の説明図である。
【図６】この発明の実施の形態１に係る部分一致秘匿検索方式の実現例の説明図である。
【図７】この発明の実施の形態１に係る部分一致秘匿検索方式の実現例の説明図である。
【図８】この発明の実施の形態１に係る秘匿検索システムの構成図である。
【図９】この発明の実施の形態１に係る鍵生成装置の構成図である。
【図１０】この発明の実施の形態１に係る暗号化タグ生成装置の構成図である。
【図１１】この発明の実施の形態１に係る検索鍵生成装置の構成図である。
【図１２】この発明の実施の形態１に係る検索装置の構成図である。
【図１３】この発明の実施の形態１に係るＫＧアルゴリズムの処理のフローチャートである。
【図１４】この発明の実施の形態１に係るＴａｇＧｅｎアルゴリズムの処理のフローチャートである。
【図１５】この発明の実施の形態１に係るＴｒａｐＧｅｎアルゴリズムの処理のフローチャートである。
【図１６】この発明の実施の形態１に係るＳｅａｒｃｈアルゴリズムの処理のフローチャートである。
【図１７】この発明の実施の形態１に係る鍵生成装置と、暗号化タグ生成装置と、検索鍵生成装置と、変換後検索鍵生成装置と、検索装置とのハードウェア構成例を示す図である。
【発明を実施するための形態】
【００１６】
実施の形態１．
以下、この発明の実施の形態１に係る秘匿検索システムについて、図面を用いて説明する。
【００１７】
＜記法の説明＞
はじめに、以下の説明における記法について説明する。
【００１８】
Ａがランダムな値または分布であるとき、下式（１）は、Ａの分布に従い、Ａからｙをランダムに選択することを表す。つまり、下式（１）において、ｙは乱数である。
【００１９】
【数１】
0006918253.tif 000002
【００２０】
Ａが集合であるとき、下式（２）は、Ａからｙを一様に選択することを表す。つまり、下式（２）において、ｙは一様乱数である。
【００２１】
【数２】
0006918253.tif 000003
【００２２】
下式（３）は、ｙにｚが設定されたこと、ｙがｚにより定義されたこと、または、ｙがｚを代入されたことを表す。
【００２３】
【数３】
0006918253.tif 000004
【００２４】
ａが定数であるとき、下式（４）は、機械ＡまたはアルゴリズムＡが、入力ｘに対して、ａを出力することを表し、下式（５）は、ａ＝１の場合を例示した式である。
【００２５】
【数４】
0006918253.tif 000005
【００２６】
下式（６）は、位数ｑの体を表す。
【００２７】
【数５】
0006918253.tif 000006
【００２８】
ベクトルｘ→は、有限体Ｆqにおける下式（７）のようなベクトル表現を表す。なお、表記「→」は、その前に記載された記号の上部に→が付されることを意味しており、ベクトルを表している。
【００２９】
【数６】
0006918253.tif 000007
【００３０】
下式（８）は、下式（９）に示す２つのベクトルｘ→およびｖ→の下式（１０）に示す内積を表す。
【００３１】
【数７】
0006918253.tif 000008
【００３２】
ＸTは、行列Ｘの転置行列を表す。
【００３３】
また、下式（１１）に示す基底Ｂと基底Ｂ*とは、下式（１２）の関係を満たす。
【００３４】
【数８】
0006918253.tif 000009
【００３５】
＜実施の形態１の概要の説明＞
本実施の形態１では、内積述語暗号を応用して、部分一致秘匿検索方式を実現する。
【００３６】
図１および図２に基づき、内積述語暗号における内積の取り方について説明する。
【００３７】
図１に示すように、暗号文がベクトルｘ→＝（ｘ1，ｘ2，．．．，ｘn）であり、鍵がベクトルｖ→＝（ｖ1，ｖ2，．．．，ｖn）であるとする。暗号文のベクトルｘ→と鍵のベクトルｖ→との要素数は同じである。この場合、内積述語暗号では、ベクトルｘ→とベクトルｖ→との内積Σi=1n（ｘi・ｖi）が計算され、暗号文が鍵により復号される。つまり、暗号文のベクトルｘ→と鍵のベクトルｖ→との対応する要素毎の内積の和が計算され、暗号文が鍵により復号される。
【００３８】
また、図２に示すように、暗号文がベクトルｘ→＝（ｘ1，ｘ2）であり、鍵がベクトルｖ→＝（ｖ1，ｖ2，．．．，ｖn）であるように、暗号文のベクトルｘ→と鍵のベクトルｖ→との要素数が異なる場合もある。この場合にも、暗号文のベクトルｘ→と鍵のベクトルｖ→との対応する要素毎の内積の和が計算され、暗号文が鍵により復号される。図２の場合、ベクトルｘ→の要素ｘ1，ｘ2が、ベクトルｖ→の要素ｖ1，ｖ2にそれぞれ対応しているので、これらの要素毎の内積の和が計算される。一方、ベクトルｖ→の要素ｖ3，．．．，ｖnについては、対応するベクトルｘ→の要素がないため、内積は計算されない。
【００３９】
次に、図３に基づき、内積述語暗号の基本構成について説明する。
【００４０】
一般に、内積述語暗号では、秘密値ｓ0と、ｔ∈Ｉｖの各整数ｔについての分散値ｓtとが用いられる。秘密値ｓ0と分散値ｓtとには、ｓ0＝Σt∈Ivｓtという関係がある。ここで、ｔはインデックスであり、Ｉｖは、インデックスｔの集合である。
【００４１】
鍵は、秘密値ｓ0が設定された基底Ｂ*0上のベクトルである要素ｋ*0と、ｔ∈Ｉｖの各整数ｔについて、分散値ｓtと属性値ｖtとインデックスｔとが設定された基底Ｂ*上のベクトルである要素ｋ*tとを含む。一方、暗号文は、基底Ｂ*0に対応する基底Ｂ0上のベクトルである要素ｃ0と、ｔ∈Ｉｘの各整数ｔについて、属性値ｘtとインデックスｔとが設定された、基底Ｂ*に対応する基底Ｂ上のベクトルである要素ｃtとを含む。ここで、Ｉｘは、インデックスｔの集合である。
【００４２】
そして、要素ｋ*0と要素ｃ0との内積が計算されるとともに、ｔ∈Ｉｖとの各整数ｔについて、鍵に含まれる要素ｋ*tと、暗号文に含まれる要素ｃtとの内積が計算される。ｔ∈Ｉｖの各整数ｔについては、要素ｋ*tに設定された属性値ｖtと、要素ｃtに設定された属性値ｘtとが対応している場合に、分散値ｓtが得られる。ｓ0＝Σt∈Ivｓtであるため、ｔ∈Ｉｖの全ての要素ｋ*tに設定された分散値ｓtが得られると、要素ｋ*0に設定された秘密値ｓ0が得られる。そして、この場合に、暗号文が鍵により復号できる。
【００４３】
なお、上述したように、要素ｋ*tと要素ｃtとには、インデックスｔが設定されている。そのため、ｉ≠ｊの整数ｉ，ｊについて、属性値ｖiと属性値ｘjとが対応していたとしても、要素ｋ*iと要素ｃjとの内積を計算しても分散値ｓiが得られることはない。ここで、インデックスｔは、被検索文字列および検索文字列における各文字の位置を示す。
【００４４】
次に、図４に基づき、実施の形態１に係る部分一致秘匿検索方式のキーテクニックを説明する。
【００４５】
上述した内積述語暗号の基本構成では、暗号文の要素ｃtと鍵の要素ｋ*tのインデックスｔに関連する各要素μ（ｔ，−１）およびσ（１，ｔ）によって、悪意のある第三者による意図しない検索を防止している。一方で、同じインデックスｔを共有する要素同士でなければ分散値ｓiを計算できないため、追加の仕組みおよび追加の計算なしに部分一致秘匿検索は実現が困難である。
【００４６】
そこで、本実施の形態１では、インデックスｔの設定方法を変更する。図４に示すように、まず、新たに、分散値τtを使用する。すなわち、本実施の形態１においては、内積述語暗号において、秘密値ｓ0と、ｔ∈Ｉｖの各整数ｔについての第１の分散値ｓtと、ｔ∈Ｉｖの各整数ｔについての第２の分散値τtとが用いられる。秘密値ｓ0と分散値ｓtとには、ｓ0＝Σt∈Ivｓtという関係がある。また、各整数ｔについての分散値τtは、０＝Σt∈Ivτtの関係を満たす。
【００４７】
次に、本実施の形態１においては、暗号文の要素ｃtには、σ（１，ｔ）に代えて、γβ-tを設定する。また、鍵の要素ｋ*tには、μ（ｔ，−１）に代えて、γ’βtτtを設定する。すなわち、本実施の形態１においては、鍵は、要素ｋ*0と要素ｋ*tとを含む。要素ｋ*0は、秘密値ｓ0が設定された基底Ｂ*0上のベクトルである。要素ｋ*tは、ｔ∈Ｉｖの各整数ｔについて、第１の分散値ｓtと第２の分散値τtと属性値ｖtとインデックスｔとが設定された基底Ｂ*上のベクトルである。一方、暗号文は、要素ｃ0と要素ｃtとを含む。要素ｃ0は、基底Ｂ*0に対応する基底Ｂ0上のベクトルである。要素ｃtは、ｔ∈Ｉｘの各整数ｔについて、属性値ｘtとインデックス−ｔとが設定された、基底Ｂ*に対応する基底Ｂ上のベクトルである。
【００４８】
ここで、βは、位数が十分大きいＦqの固定された元とし、γおよびγ’は乱数とする。ただし、βの冪の符号は暗号文と鍵とで入れ替えても構わない。すなわち、上記の説明においては、検索文字列である鍵にインデックスｔを設定し、被検索文字列である暗号文にインデックス−ｔを設定すると説明した。しかしながら、その場合に限らず、検索文字列である鍵にインデックス−ｔを設定し、被検索文字列である暗号文にインデックスｔを設定するようにしてもよい。また、γおよびγ’は省略しても構わない。また、βは公開しても構わないが、秘密情報として登録者と検索者との間で安全な通信路を用いて事前に共有しても構わない。
【００４９】
このことにより、例えば同じインデックスｔを共有する暗号文と鍵とで部分一致秘匿検索を行う場合、各インデックスｔにおける各暗号文の要素ｃtと各鍵の要素ｋ*tとで内積を計算する。その結果、各インデックスｔにおいてβの冪要素が打ち消しあい、γγ’τtを取り出すことができる。このとき、０＝γγ’Σt∈Ivτtであることから、τtの項は打ち消しあって、残った分散値ｓiを得ることができる。
【００５０】
次に、鍵の要素のインデックスｔに対して暗号文の要素のインデックスをαだけずらして部分一致秘匿検索を行う場合について説明する。即ち、この場合は、暗号文の要素ｃt+αに対して鍵の要素ｋ*tとの内積を計算することになり、各インデックスｔにおいてγγ’β-ατtを取り出すことができる。この結果、０＝γγ’β-αΣt∈Ivτtであることから、この場合も、τtの項は打ち消しあって、残った分散値ｓiを得ることができる。
【００５１】
言い換えると、一定の幅αだけ、鍵の全要素をずらす場合のみ一致判定が可能となる。これは、即ち、検索鍵変換処理を行わずに部分一致秘匿検索を実現し、一方で、文字の入れ替えまたは切り離しによる意図しない検索を防止することができることを意味する。
【００５２】
このように、本実施の形態１においては、内積述語暗号において、第１の分散値ｓtと第２の分散値τtとを用いる。また、検索文字列である鍵と被検索文字列である暗号文において、一方にインデックスｔを設定し、他方に符号を反転させたインデックス−ｔを設定する。これにより、内積を計算する際に、インデックスｔを打ち消すことができる。その結果、特許文献２で必要であった検索鍵変換処理が不要となり、検索時間の短縮を図ることができる。また、悪意のある第三者による意図しない検索を防止することができる。
【００５３】
図５に基づき、本実施の形態１に係る部分一致秘匿検索方式の実現例を説明する。
【００５４】
図５に示すように、データベースに、ＡＢＣＤＥという検索タグとなる被検索文字列が暗号化されて生成された暗号化タグＥＴxが記憶されている。このとき、検索文字列として、ＣＤという文字列が与えられたとする。
【００５５】
この場合、ＡＢＣＤＥという被検索文字列の各文字を属性値ｘtとして、暗号文の要素ｃtが生成される。つまり、要素ｃ1には属性値Ａが設定され、要素ｃ2には属性値Ｂが設定され、要素ｃ3には属性値Ｃが設定され、要素ｃ4には属性値Ｄが設定され、要素ｃ5には属性値Ｅが設定される。このように、暗号化タグＥＴxは、被検索文字列の各文字が位置を指定されて設定されている。
【００５６】
一方、ＣＤという文字列の各文字を属性値ｖtとして、検索鍵ＴＤvが生成される。つまり、要素ｋ*1には属性値Ｃが設定され、要素ｋ*2には属性値Ｄが設定される。このように、検索鍵ＴＤvは、検索文字列の各文字が位置を指定されて設定されている。
【００５７】
検索処理では、図５に示すように、検索鍵ＴＤvの要素ｋ*tを１つずつ順にずらして暗号化タグＥＴxを順に復号して、一致判定を行う。この実現例では、要素ｃ3，ｃ4を要素ｋ*1，ｋ*2で復号したときに一致となる。
【００５８】
次に、図６に基づき、本実施の形態１に係る部分一致秘匿検索方式の他の実現例を説明する。
【００５９】
データベースに、ＡＢＣＤＥという検索タグとなる被検索文字列が暗号化された暗号化タグＥＴxが記憶されており、検索文字列として、ＢＤという文字列が与えられたとする。
【００６０】
この場合、ＡＢＣＤＥという被検索文字列の各文字を属性値ｘtとして、暗号文の要素ｃtが生成される。つまり、要素ｃ1には属性値Ａが設定され、要素ｃ2には属性値Ｂが設定され、要素ｃ3には属性値Ｃが設定され、要素ｃ4には属性値Ｄが設定され、要素ｃ5には属性値Ｅが設定される。
【００６１】
一方、ＢＤという検索文字列の各文字を属性値ｖtとして、検索鍵ＴＤvが生成される。つまり、要素ｋ*1には属性値Ｂが設定され、要素ｋ*2には属性値Ｄが設定される。
【００６２】
この実現例では、例えば、意図しない検索として、要素ｋ*1，ｋ*2を不正に分離して要素ｃ2，ｃ4を復号した場合を考える。このとき、各要素の属性値が一致しているため、内積の結果としてｖtおよびｘt成分は打ち消されて０となる。一方で、内積の結果として取り出されるτtの項は、γγ’（β-1τ1＋β-2τ2）≠０となり、打ち消されないため、部分一致秘匿検索の結果は不一致となる。
【００６３】
次に、図７に基づき、実施の形態１に係る部分一致秘匿検索方式のさらなる他の実現例を説明する。
【００６４】
データベースに、ＡＢＣＤＥという検索タグとなる被検索文字列が暗号化された暗号化タグが記憶されており、検索文字列として、ＢＡという文字列が与えられたとする。
【００６５】
この場合、ＡＢＣＤＥという被検索文字列の各文字を属性値ｘtとして、暗号文の要素ｃtが生成される。つまり、要素ｃ1には属性値Ａが設定され、要素ｃ2には属性値Ｂが設定され、要素ｃ3には属性値Ｃが設定され、要素ｃ4には属性値Ｄが設定され、要素ｃ5には属性値Ｅが設定される。
【００６６】
一方、ＢＡという文字列の各文字を属性値ｖtとして、検索鍵が生成される。つまり、要素ｋ*1には属性値Ｂが設定され、要素ｋ*2には属性値Ａが設定される。
【００６７】
この実現例では、例えば、意図しない検索として、要素ｋ*1，ｋ*2を不正に置換して要素ｃ1，ｃ2を復号した場合を考える。このとき、各要素の属性値が一致しているため、内積の結果としてｖtおよびｘt成分は打ち消されて０となる。一方で、内積の結果として取り出されるτtの項は、γγ’（β-1τ1＋β1τ2）≠０となり、打ち消されないため、部分一致秘匿検索の結果は不一致となる。
【００６８】
このように、本実施の形態１においては、図５に示すように、一定の幅αだけ、鍵の全要素をずらす場合のみ一致判定が可能となる。一方、図６に示すような文字の切り離し、および、図７に示すような文字の入れ替えなどの、意図しない検索の場合には、一致判定が不可能になる。これにより、悪意のある第三者による意図しない検索を防止することができる。
【００６９】
＜実施の形態１に係る秘匿検索システムの構成の説明＞
本実施の形態１に係る秘匿検索システム１０の構成を説明する前に、本実施の形態１における部分一致秘匿検索方式の基本構成について説明する。
【００７０】
本実施の形態１に係る秘匿検索システム１０で用いられる部分一致秘匿検索方式は、ＫＧアルゴリズムと、ＴａｇＧｅｎアルゴリズムと、ＴｒａｐＧｅｎアルゴリズムと、Ｓｅａｒｃｈアルゴリズムとを備える。
【００７１】
ＫＧアルゴリズムは、セキュリティパラメータλを入力として、公開鍵ｐｋと、秘密鍵ｓｋとを出力するアルゴリズムである。
【００７２】
ＴａｇＧｅｎアルゴリズムは、公開鍵ｐｋと、属性ベクトルｘ→とを入力として、暗号化タグＥＴxを出力する確率的アルゴリズムである。
【００７３】
ＴｒａｐＧｅｎアルゴリズムは、公開鍵ｐｋと、秘密鍵ｓｋと、述語ベクトルｖ→とを入力として、検索鍵ＴＤvを出力する確率的アルゴリズムである。
【００７４】
Ｓｅａｒｃｈアルゴリズムは、公開鍵ｐｋと、暗号化タグＥＴxと、検索鍵ＴＤvとを入力として、検索にヒットしたことを示す０、または、検索にヒットしなかったことを示す１を出力する確定的アルゴリズムである。
【００７５】
図８に基づき、本実施の形態１に係る秘匿検索システム１０について説明する。
【００７６】
図８に示す秘匿検索システム１０は、検索文字列の各文字が位置を指定されて設定された検索鍵ＴＤvを生成する。また、秘匿検索システム１０は、被検索文字列の各文字が位置を指定されて設定された複数の暗号化タグＥＴxを生成する。そして、秘匿検索システム１０は、生成した検索鍵ＴＤvに対応する暗号化タグＥＴxを検索する。このとき、秘匿検索システム１０は、上述したように、検索鍵ＴＤvに各文字の位置を示すインデックスｔを設定し、暗号化タグＥＴxに、インデックスｔの符号を反転したインデックス−ｔを設定している。そのため、検索時に、検索鍵ＴＤvと暗号化タグＥＴxとに設定されたインデックスｔとインデックス−ｔとを加算することで、双方に設定された位置を打消して、検索鍵ＴＤvを部分文字列として含む暗号化タグＥＴxを検索する。
【００７７】
図８に示すように、秘匿検索システム１０は、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、検索装置５００とを備える。
【００７８】
なお、ここでは、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、検索装置５００とをそれぞれ別の装置としているが、これらの装置のうち２つ以上の装置が１つの装置として構成されていてもよい。したがって、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、検索装置５００とを、それぞれ、鍵生成部と、暗号化タグ生成部と、検索鍵生成部と、検索部と読み替え、或る１つ以上の装置の各構成要素としてもよい。
【００７９】
鍵生成装置１００は、セキュリティパラメータλを入力として、ＫＧアルゴリズムを実行して、公開鍵ｐｋと、秘密鍵ｓｋと、固定値βとを出力する。セキュリティパラメータλは、秘匿検索システム１０の管理者等によって、秘匿検索システム１０の入力インタフェースに接続された入力装置により入力される。
【００８０】
暗号化タグ生成装置２００は、公開鍵ｐｋと、属性ベクトルｘ→と、固定値βとを入力として、ＴａｇＧｅｎアルゴリズムを実行して、暗号化タグＥＴxを生成する。属性ベクトルｘ→は、秘匿検索システム１０の管理者または暗号化タグ生成装置２００の使用者等によって、秘匿検索システム１０の入力インタフェースに接続された入力装置により入力される。
【００８１】
検索鍵生成装置３００は、公開鍵ｐｋと、秘密鍵ｓｋと、述語ベクトルｖ→と、固定値βとを入力として、ＴｒａｐＧｅｎアルゴリズムを実行して、検索鍵ＴＤvを生成する。述語ベクトルｖ→は、秘匿検索システム１０の管理者または検索鍵生成装置３００の使用者等によって、秘匿検索システム１０の入力インタフェースに接続された入力装置により入力される。
【００８２】
検索装置５００は、公開鍵ｐｋと、暗号化タグＥＴxと、検索鍵ＴＤvとを入力として、Ｓｅａｒｃｈアルゴリズムを実行して、検索鍵ＴＤvを部分文字列として含む暗号化タグＥＴxを検索する。検索装置５００は、検索においてヒットしたことを示す０、または、検索においてヒットしなかったことを示す１を出力する。
【００８３】
次に、図９に基づき、本実施の形態１に係る鍵生成装置１００の構成について説明する。
【００８４】
図９に示すように、鍵生成装置１００は、情報取得部１１０と、基底生成部１２０と、鍵生成部１４０と、鍵出力部１５０とを備える。
【００８５】
情報取得部１１０は、秘匿検索システム１０に接続された入力装置から入力されたセキュリティパラメータλを取得する。
【００８６】
基底生成部１２０は、セキュリティパラメータλに基づき、部分一致秘匿検索方式を実現するための基礎となる基底Ｂ0と基底Ｂ*0と基底Ｂと基底Ｂ*とを生成する。また、基底生成部１２０は、パラメータｐａｒａｍを生成する。これらの基底およびパラメータの生成方法については後述する。
【００８７】
鍵生成部１４０は、基底Ｂ0および基底Ｂと、パラメータｐａｒａｍとを用いて、公開鍵ｐｋを生成する。また、鍵生成部１４０は、基底Ｂ*0および基底Ｂ*を用いて、秘密鍵ｓｋを生成する。さらに、鍵生成部１４０は、固定値βを生成する。公開鍵ｐｋ、秘密鍵ｓｋおよび固定値βの生成方法については後述する。
【００８８】
鍵出力部１５０は、鍵生成部１４０が生成した公開鍵ｐｋを公開する。また、鍵出力部１５０は、鍵生成部１４０が生成した秘密鍵ｓｋを、検索鍵生成装置３００へ出力する。さらに、鍵出力部１５０は、鍵生成部１４０が生成した固定値βを、暗号化タグ生成装置２００と検索鍵生成装置３００へ出力する。このとき、固定値βは公開しても構わないし、秘密情報として暗号化タグ生成装置２００と検索鍵生成装置３００へ安全な通信路を用いて出力しても構わない。
【００８９】
次に、図１０に基づき、本実施の形態１に係る暗号化タグ生成装置２００の構成を説明する。
【００９０】
図１０に示すように、暗号化タグ生成装置２００は、情報取得部２１０と、タグ生成部２２０と、暗号化タグ出力部２３０とを備える。
【００９１】
情報取得部２１０は、鍵生成装置１００から公開鍵ｐｋと固定値βとを取得するとともに、秘匿検索システム１０に接続された入力装置から入力された属性ベクトルｘ→を取得する。
【００９２】
タグ生成部２２０は、公開鍵ｐｋと、固定値βと、属性ベクトルｘ→とを用いて、１つ以上の基底Ｂ上のタグベクトルｃtを含む暗号化タグＥＴxを生成する。タグ生成部２２０は、乱数生成部２２１と、要素生成部２２２とを備える。乱数生成部２２１および要素生成部２２２の動作については後述する。
【００９３】
暗号化タグ出力部２３０は、暗号化タグＥＴxを検索装置５００に出力する。
【００９４】
次に、図１１に基づき、本実施の形態１に係る検索鍵生成装置３００の構成を説明する。
【００９５】
図１１に示すように、検索鍵生成装置３００は、情報取得部３１０と、鍵生成部３２０と、鍵出力部３３０とを備える。
【００９６】
情報取得部３１０は、鍵生成装置１００から公開鍵ｐｋと、秘密鍵ｓｋと、固定値βとを取得するとともに、秘匿検索システム１０に接続された入力装置から述語ベクトルｖ→を取得する。
【００９７】
鍵生成部３２０は、公開鍵ｐｋと、秘密鍵ｓｋと、固定値βと、述語ベクトルｖ→とを用いて、文字列の各文字が位置を指定されて設定された検索鍵ＴＤvを生成する。ここでは、鍵生成部３２０は、１つ以上の基底Ｂ*上の検索ベクトルｋ*tを含む検索鍵ＴＤvを生成する。鍵生成部３２０は、乱数生成部３２１と、秘密値生成部３２２と、要素生成部３２３とを備える。乱数生成部３２１、秘密値生成部３２２、および、要素生成部３２３の動作については、後述する。
【００９８】
鍵出力部３３０は、鍵生成部３２０が生成した検索鍵ＴＤvを検索装置５００に出力する。
【００９９】
次に、図１２に基づき、本実施の形態１に係る検索装置５００の構成を説明する。
【０１００】
図１２に示すように、検索装置５００は、情報取得部５１０と、検索判定部５２０と、結果出力部５３０とを備える。
【０１０１】
情報取得部５１０は、鍵生成装置１００から公開鍵ｐｋを取得する。また、情報取得部５１０は、暗号化タグ生成装置２００から、暗号化タグＥＴxを取得する。さらに、情報取得部５１０は、検索鍵生成装置３００から、検索鍵ＴＤvを取得する。
【０１０２】
検索判定部５２０は、暗号化タグ生成装置２００が生成した複数の暗号化タグＥＴxであって、文字列の各文字が位置を指定されて設定された複数の暗号化タグＥＴxから、検索鍵生成装置３００が生成した検索鍵ＴＤvに設定された各文字について、その文字と、その文字に対して指定された位置に設定された文字とが一致する暗号化タグＥＴxを検索する。ここでは、検索判定部５２０は、公開鍵ｐｋと検索鍵ＴＤvとを用いて、暗号化タグＥＴxを復号することにより、検索にヒットしたか否かを判定する。つまり、検索判定部５２０は、暗号化タグ生成装置２００が生成した複数の暗号化タグＥＴxから、検索鍵生成装置３００が生成した検索鍵ＴＤvに対応する暗号化タグＥＴxを検索する。
【０１０３】
結果出力部５３０は、検索にヒットしたことを示す０、または、検索にヒットしなかったことを示す１を出力する。
【０１０４】
＜実施の形態１に係る秘匿検索システムの動作の説明＞
以下、図１３〜図１６に基づいて、本実施の形態１に係る秘匿検索システム１０の動作について説明する。
【０１０５】
［ＫＧアルゴリズムの処理の説明］
はじめに、図１３に基づいて、ＫＧアルゴリズムの処理について説明する。上述した通り、ＫＧアルゴリズムは、鍵生成装置１００によって実行される。ＫＧアルゴリズムは、本実施の形態１に係る秘匿検索方法における鍵生成ステップに相当する。また、ＫＧアルゴリズムは、本実施の形態１に係る秘匿検索プログラムにおける鍵生成処理に相当する。
【０１０６】
［ステップＳ１０１：情報取得処理］
ステップＳ１０１では、情報取得部１１０が、セキュリティパラメータλを取得する。セキュリティパラメータλは、秘匿検索システム１０の管理者等によって入力装置により入力される。
【０１０７】
［ステップＳ１０２：基底生成処理］
ステップＳ１０２では、基底生成部１２０が、セキュリティパラメータλを入力として、下式（１３）を計算して、基底Ｂ0と基底Ｂ*0と基底Ｂ1と基底Ｂ*1と、双対ペアリングベクトル空間のパラメータｐａｒａｍとを生成する。ただし、以降では基底Ｂ1と基底Ｂ*1とを、各々、基底Ｂと基底Ｂ*とも書く。さらに、固定値βを位数が十分大きいＦqの元として生成する。
【０１０８】
【数９】
0006918253.tif 000010
【０１０９】
なお、上式（１３）において、Ｇbpgは、双線形ペアリング群を生成する関数であり、Ｇdpvsは、双対ペアリングベクトル空間を生成する関数である。
【０１１０】
［ステップＳ１０４：公開鍵生成処理］
ステップＳ１０４では、鍵生成部１４０が、ステップＳ１０２で生成された基底Ｂ0の部分基底Ｂ＾0と、基底Ｂの部分基底Ｂ＾とを下式（１４）に示すように生成する。
【０１１１】
【数１０】
0006918253.tif 000011
【０１１２】
鍵生成部１４０は、部分基底Ｂ＾0およびＢ＾と、ステップＳ１０２で生成されたパラメータｐａｒａｍとを、公開鍵ｐｋとする。
【０１１３】
［Ｓ１０５：秘密鍵生成処理］
ステップＳ１０５では、鍵生成部１４０は、ステップＳ１０２で生成された基底Ｂ*0の部分基底Ｂ＾*0と、基底Ｂ*の部分基底Ｂ＾*とを、下式（１５）に示すように生成する。なお、表記「＾」は、その前に記載された記号の上部に＾が付されることを意味している。
【０１１４】
【数１１】
0006918253.tif 000012
【０１１５】
鍵生成部１４０は、部分基底Ｂ＾*0および部分基底Ｂ＾*を、秘密鍵ｓｋとする。
【０１１６】
［ステップＳ１０７：鍵出力処理］
ステップＳ１０７では、鍵出力部１５０が、ステップＳ１０４で生成された公開鍵ｐｋを公開用のサーバ等へ出力して、公開鍵ｐｋを公開する。また、鍵出力部１５０は、ステップＳ１０５で生成された秘密鍵ｓｋを秘密裡に検索鍵生成装置３００へ出力する。さらに、鍵出力部１５０は、ステップＳ１０２で生成された固定値βを暗号化タグ生成装置２００と検索鍵生成装置３００とへ出力する。このとき、固定値βを公開することで、暗号化タグ生成装置２００と検索鍵生成装置３００へ出力しても構わないし、秘密情報として暗号化タグ生成装置２００と検索鍵生成装置３００へ安全な通信路を用いて出力しても構わない。
【０１１７】
［ＴａｇＧｅｎアルゴリズムの処理の説明］
次に、図１４に基づき、本実施の形態１に係るＴａｇＧｅｎアルゴリズムの処理を説明する。上述した通り、ＴａｇＧｅｎアルゴリズムは、暗号化タグ生成装置２００によって実行される。ＴａｇＧｅｎアルゴリズムは、本実施の形態１に係る秘匿検索方法における暗号化タグ生成ステップに相当する。また、ＴａｇＧｅｎアルゴリズムは、本実施の形態１に係る秘匿検索プログラムにおける暗号化タグ生成処理に相当する。
【０１１８】
［ステップＳ２０１：情報取得処理］
ステップＳ２０１では、情報取得部２１０が、鍵生成装置１００によって公開された公開鍵ｐｋを取得する。また、情報取得部２１０は、鍵生成装置１００によって出力された固定値βを取得する。
【０１１９】
さらに、情報取得部２１０は、暗号化タグ生成装置２００の使用者等によって入力装置により入力された、属性ベクトルｘ→を取得する。属性ベクトルｘ→は、次式で示される。
【０１２０】
属性ベクトルｘ→：＝｛（ｔ，ｘt）｜ｔ∈Ｉｘ⊆｛１，．．．｝｝
【０１２１】
ここで、Ｉｘは、インデックスの集合である。例えば、属性ベクトルｘ→の各要素ｘtには、図５〜図７で説明したように、検索タグとなる文字列の各文字が設定される。
【０１２２】
［ステップＳ２０２：乱数生成処理］
ステップＳ２０２では、乱数生成部２２１が、下式（１６）に示すように、乱数を生成する。
【０１２３】
【数１２】
0006918253.tif 000013
【０１２４】
［ステップＳ２０３：タグ要素生成処理］
ステップＳ２０３では、要素生成部２２２が、ステップＳ２０１で取得された公開鍵ｐｋおよび属性ベクトルｘ→と、ステップＳ２０２で生成された乱数とを入力として、下式（１７）に示すように、タグベクトルｃ0と、ｔ∈Ｉｘの各整数ｔについてのタグベクトルｃtと、タグベクトルｃTとを生成する。ただし、βは位数が十分大きいＦqの固定された元とする。
【０１２５】
【数１３】
0006918253.tif 000014
【０１２６】
［ステップＳ２０４：タグ出力処理］
ステップＳ２０４では、暗号化タグ出力部２３０が、暗号化タグＥＴxを、検索装置５００に出力する。暗号化タグＥＴxは、ステップＳ２０１で取得されたインデックスの集合Ｉｘと、ステップＳ２０３で生成されたタグベクトルｃ0およびｔ∈Ｉｘの各整数ｔについてのタグベクトルｃtおよびタグベクトルｃTとを要素として含む。
【０１２７】
［ＴｒａｐＧｅｎアルゴリズムの処理の説明］
次に、図１５に基づき、本実施の形態１に係るＴｒａｐＧｅｎアルゴリズムの処理を説明する。上述した通り、ＴｒａｐＧｅｎアルゴリズムは、検索鍵生成装置３００によって実行される。ＴｒａｐＧｅｎアルゴリズムは、本実施の形態１に係る秘匿検索方法における検索鍵生成ステップに相当する。また、ＴｒａｐＧｅｎアルゴリズムは、本実施の形態１に係る秘匿検索プログラムにおける検索鍵生成処理に相当する。
【０１２８】
［ステップＳ３０１：情報取得処理］
ステップＳ３０１では、情報取得部３１０が、鍵生成装置１００によって公開された公開鍵ｐｋと、鍵生成装置１００によって出力された秘密鍵ｓｋとを取得する。また、情報取得部３１０は、鍵生成装置１００によって出力された固定値βを取得する。
【０１２９】
さらに、情報取得部３１０は、検索鍵生成装置３００の使用者等によって入力装置により入力された、述語ベクトルｖ→を取得する。述語ベクトルｖ→は、下式で表わされる。
【０１３０】
述語ベクトルｖ→：＝｛（ｔ，ｖt）｜ｔ∈Ｉｖ⊆｛１，．．．｝｝
【０１３１】
ここで、Ｉｖは、インデックスの集合である。例えば、述語ベクトルｖ→の各要素ｖtには、図５から図７で説明したように、検索文字列となる文字列の各文字が設定される。
【０１３２】
［ステップＳ３０２：乱数生成処理］
ステップＳ３０２では、乱数生成部３２１が、下式（１８）に示すように、乱数を生成する。ただし、τtはｓtとは異なり、０＝Σt∈Ivτtを満たすように生成する。
【０１３３】
【数１４】
0006918253.tif 000015
【０１３４】
［ステップＳ３０３：秘密値生成処理］
ステップＳ３０３では、秘密値生成部３２２が、ステップＳ２０２で生成されたｔ∈Ｉｖの各整数ｔについての乱数ｓtを入力として、秘密値ｓ0＝Σt∈Ivｓtを生成する。
【０１３５】
［ステップＳ３０４：鍵要素生成処理］
ステップＳ３０４では、要素生成部３２３が、ステップＳ３０１で取得された公開鍵ｐｋ、秘密鍵ｓｋおよび述語ベクトルｖ→と、ステップＳ３０２で生成された乱数と、ステップＳ３０３で生成された秘密値ｓ0とを入力として、下式（１９）に示すように、検索ベクトルｋ*0と、ｔ∈Ｉｖの各整数ｔについての検索ベクトルｋ*tとを生成する。ただし、βは位数が十分大きいＦqの固定された元とする。
【０１３６】
【数１５】
0006918253.tif 000016
【０１３７】
［ステップＳ３０５：鍵出力処理］
ステップＳ３０５では、鍵出力部３３０が、検索鍵ＴＤvを、検索装置５００に出力する。検索鍵ＴＤvは、ステップＳ３０１で取得されたインデックスの集合Ｉｖと、ステップＳ３０４で生成された検索ベクトルｋ*0およびｔ∈Ｉｖの各整数ｔについての検索ベクトルｋ*tとを要素として含む。
【０１３８】
［Ｓｅａｒｃｈアルゴリズムの処理の説明］
次に、図１６に基づき、本実施の形態１に係るＳｅａｒｃｈアルゴリズムの処理を説明する。上述した通り、Ｓｅａｒｃｈアルゴリズムは、検索装置５００によって実行される。Ｓｅａｒｃｈアルゴリズムは、本実施の形態１に係る秘匿検索方法における検索ステップに相当する。また、Ｓｅａｒｃｈアルゴリズムは、本実施の形態１に係る秘匿検索プログラムにおける検索処理に相当する。
【０１３９】
［ステップＳ５０１：情報取得処理］
ステップＳ５０１では、情報取得部５１０が、鍵生成装置１００によって公開された公開鍵ｐｋを取得する。また、情報取得部５１０は、暗号化タグ生成装置２００によって出力された暗号化タグＥＴxを取得する。さらに、情報取得部５１０は、検索鍵生成装置３００によって出力された検索鍵ＴＤvを取得する。
【０１４０】
［ステップＳ５０２：検索可能判定処理］
ステップＳ５０２では、検索判定部５２０が、ステップＳ５０１で取得された検索鍵ＴＤvに含まれるインデックスの集合Ｉｖが、ステップＳ５０１で取得された暗号化タグＥＴxに含まれるインデックスの集合Ｉｘの部分集合であるか否かを判定する。
【０１４１】
検索判定部５２０は、インデックスの集合Ｉｖが、インデックスの集合Ｉｘの部分集合である場合には検索可能であるとして、処理をステップＳ５０３に進める。一方、インデックスの集合Ｉｖが、インデックスの集合Ｉｘの部分集合でない場合には検索不可能であるとして、処理をステップＳ５０７へ進める。
【０１４２】
［ステップＳ５０３：復号処理］
ステップＳ５０３では、検索判定部５２０が、下式（２０）に示すように、暗号化タグＥＴxに含まれるタグと、検索鍵ＴＤvに含まれる検索ベクトルとについて、ペアリング演算して、セッション鍵Ｋを計算する。
【０１４３】
【数１６】
0006918253.tif 000017
【０１４４】
つまり、検索判定部５２０は、内積述語暗号方式で言うところの、公開鍵ｐｋと検索鍵ＴＤvとを用いて、暗号化タグＥＴxを復号する処理を行う。
【０１４５】
［ステップＳ５０４：検索判定処理］
ステップＳ５０４では、検索判定部５２０が、ステップＳ５０３で計算されたセッション鍵Ｋが、暗号化タグＥＴxに含まれるタグベクトルｃTと等しいか否かを判定する。
【０１４６】
検索判定部５２０は、セッション鍵ＫがタグベクトルｃTと等しい場合、処理をステップＳ５０５へ進める。一方、セッション鍵ＫがタグベクトルｃTと等しくない場合、処理をステップＳ５０７へ進める。
【０１４７】
［ステップＳ５０５：結果Ａ出力処理］
ステップＳ５０５では、結果出力部５３０が、検索にヒットしたことを示す０を出力する。
【０１４８】
［ステップＳ５０７：検索鍵インデックス更新処理］
ステップＳ５０７では、検索判定部５２０が、ステップＳ５０１で取得された検索鍵ＴＤvに含まれるインデックスの集合Ｉｖの各要素に対して１を加算する。また、検索判定部５２０が、検索鍵ＴＤvに含まれる各検索ベクトルｋ*tのインデックスｔに対して１を加算する。
【０１４９】
［ステップＳ５０８：検索終了判定処理］
ステップＳ５０８では、検索判定部５２０が、ステップＳ５０７で更新された検索鍵ＴＤvに含まれるインデックスの集合Ｉｖに含まれる最大のインデックスが、ステップＳ５０１で取得された暗号化タグＥＴxに含まれるインデックスの集合Ｉｘに含まれる最大のインデックス以下であるとき、処理をステップＳ５０２へ進め、さもなければ処理Ｓ５０６へ進む。
［ステップＳ５０６：結果Ｂ出力処理］
ステップＳ５０６では、結果出力部５３０が、検索にヒットしなかったことを示す１を出力する。
【０１５０】
つまり、検索装置５００は、検索鍵ＴＤvに含まれる検索ベクトルｋ*tと、各暗号化タグＥＴxに含まれるタグベクトルｃtとを用いた計算をすることにより、検索鍵ＴＤvに対応する暗号化タグＥＴxを検索する。
【０１５１】
より具体的には、検索装置５００は、検索鍵ＴＤvに含まれる検索ベクトルｋ*tと、各暗号化タグＥＴxに含まれるタグベクトルｃtであって、その検索ベクトルｋ*tに対応するタグベクトルｃtとの内積の計算をすることにより、検索鍵ＴＤvに対応する暗号化タグＥＴxを検索する。
【０１５２】
図５を用いて説明したように、検索鍵ＴＤvに含まれる検索ベクトルｋ*tのインデックスｔを１つずつ順にずらして内積を計算することにより、部分一致秘匿検索を実現できる。このインデックスｔの更新は、単純なインデックスの張替えであるため、特別な検索鍵変換処理を必要とせず、高速である。一方で、図６または図７に基づいて説明したように、検索文字列の分離あるいは置換したうえで検索することはできず、悪意のある第三者による意図しない検索を防止できる。
【０１５３】
なお、上記説明では、検索可能な利用者を限定せず、全ての利用者が全ての暗号化タグＥＴxを検索可能であった。しかし、特許文献２と同様に、上述した部分一致秘匿検索方式を、内積述語暗号方式と組み合わせることにより、暗号化タグＥＴx毎に、検索可能な利用者を限定することも可能である。
【０１５４】
＜実施の形態１に係る秘匿検索システムのハードウェア構成＞
次に、図１７に基づき、本実施の形態１に係る秘匿検索システム１０のハードウェア構成例について説明する。本実施の形態１に係る秘匿検出システムは、上述したように、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、検索装置５００とから構成されている。
【０１５５】
鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、検索装置５００とは、例えばコンピュータから構成される。
【０１５６】
鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、検索装置５００とは、プロセッサ９０１、補助記憶装置９０２、メモリ９０３、通信装置９０４、入力インタフェース９０５、ディスプレイインタフェース９０６などのハードウェアを備える。
【０１５７】
プロセッサ９０１は、信号線９１０を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【０１５８】
入力インタフェース９０５は、ケーブル９１１により入力装置９０７に接続されている。
【０１５９】
ディスプレイインタフェース９０６は、ケーブル９１２によりディスプレイ９０８に接続されている。
【０１６０】
プロセッサ９０１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ９０１は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
【０１６１】
補助記憶装置９０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。
【０１６２】
メモリ９０３は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【０１６３】
通信装置９０４は、データを受信するレシーバー９０４１およびデータを送信するトランスミッター９０４２を含む。通信装置９０４は、例えば、通信チップまたはＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
【０１６４】
入力インタフェース９０５は、入力装置９０７のケーブル９１１が接続されるポートである。入力インタフェース９０５は、例えば、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）端子である。
【０１６５】
ディスプレイインタフェース９０６は、ディスプレイ９０８のケーブル９１２が接続されるポートである。ディスプレイインタフェース９０６は、例えば、ＵＳＢ端子またはＨＤＭＩ（登録商標）（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）端子である。
【０１６６】
入力装置９０７は、例えば、マウス、キーボードまたはタッチパネルである。
【０１６７】
ディスプレイ９０８は、例えば、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）である。
【０１６８】
補助記憶装置９０２には、上述した情報取得部１１０、基底生成部１２０、鍵生成部１４０、鍵出力部１５０、情報取得部２１０、タグ生成部２２０、乱数生成部２２１、要素生成部２２２、暗号化タグ出力部２３０、情報取得部３１０、鍵生成部３２０、乱数生成部３２１、秘密値生成部３２２、要素生成部３２３、鍵出力部３３０、情報取得部５１０、検索判定部５２０、結果出力部５３０の機能を実現するプログラムが記憶されている。以下では、情報取得部１１０、基底生成部１２０、鍵生成部１４０、鍵出力部１５０、情報取得部２１０、タグ生成部２２０、乱数生成部２２１、要素生成部２２２、暗号化タグ出力部２３０、情報取得部３１０、鍵生成部３２０、乱数生成部３２１、秘密値生成部３２２、要素生成部３２３、鍵出力部３３０、情報取得部５１０、検索判定部５２０、および、結果出力部５３０をまとめて、「各部」と表記する。
【０１６９】
このプログラムは、メモリ９０３にロードされ、プロセッサ９０１に読み込まれ、プロセッサ９０１によって実行される。
【０１７０】
更に、補助記憶装置９０２には、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）も記憶されている。
【０１７１】
そして、ＯＳの少なくとも一部がメモリ９０３にロードされ、プロセッサ９０１はＯＳを実行しながら、「各部」の機能を実現するプログラムを実行する。
【０１７２】
なお、図１７では、１つのプロセッサ９０１が図示されているが、鍵生成装置１００と、暗号化タグ生成装置２００と、検索鍵生成装置３００と、変換後検索鍵生成装置４００と、検索装置５００とが、複数のプロセッサ９０１から構成されていてもよい。そして、複数のプロセッサ９０１が「各部」の機能を実現するプログラムを連携して実行してもよい。
【０１７３】
また、「各部」の処理の結果を示す情報、データ、信号値、および、変数値が、メモリ９０３、補助記憶装置９０２、または、プロセッサ９０１内のレジスタまたはキャッシュメモリにファイルとして記憶される。
【０１７４】
さらに、「各部」を「サーキットリー」で提供してもよい。また、「各部」のそれぞれを「回路」または「ステップ」または「手順」または「処理」に読み替えてもよい。「回路」および「サーキットリー」は、プロセッサ９０１だけでなく、ロジックＩＣまたはＧＡ（Ｇａｔｅ  Ａｒｒａｙ）またはＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）またはＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）といった他の種類の処理回路をも包含する概念である。
【符号の説明】
【０１７５】
１０  秘匿検索システム、１００  鍵生成装置、１１０  情報取得部、１２０  基底生成部、１４０  鍵生成部、１５０  鍵出力部、２００  暗号化タグ生成装置、２１０  情報取得部、２２０  タグ生成部、２２１  乱数生成部、２２２  要素生成部、２３０  暗号化タグ出力部、３００  検索鍵生成装置、３１０  情報取得部、３２０  鍵生成部、３２１  乱数生成部、３２２  秘密値生成部、３２３  要素生成部、３３０  鍵出力部、５００  検索装置、５１０  情報取得部、５２０  検索判定部、５３０  結果出力部、ｐｋ  公開鍵、ｓｋ  秘密鍵、Ｂ，Ｂ*  基底、Ｂ＾，Ｂ＾*  部分基底、ｐａｒａｍ  パラメータ、Ｉｘ，Ｉｖ  インデックスの集合、ｘ→  属性ベクトル、ｖ→  述語ベクトル、ｋ*  検索ベクトル、ＥＴx  暗号化タグ、ＴＤv  検索鍵。
【図１】
0006918253.tif 000018
【図２】
0006918253.tif 000019
【図３】
0006918253.tif 000020
【図４】
0006918253.tif 000021
【図５】
0006918253.tif 000022
【図６】
0006918253.tif 000023
【図７】
0006918253.tif 000024
【図８】
0006918253.tif 000025
【図９】
0006918253.tif 000026
【図１０】
0006918253.tif 000027
【図１１】
0006918253.tif 000028
【図１２】
0006918253.tif 000029
【図１３】
0006918253.tif 000030
【図１４】
0006918253.tif 000031
【図１５】
0006918253.tif 000032
【図１６】
0006918253.tif 000033
【図１７】
0006918253.tif 000034