図面 (/)

技術 検索処理方法、データ生成方法及び情報処理装置

出願人 富士通株式会社
発明者 山岡裕司牛田芽生恵
出願日 2012年11月13日 (8年0ヶ月経過) 出願番号 2012-249499
公開日 2014年5月29日 (6年5ヶ月経過) 公開番号 2014-098989
状態 特許登録済
技術分野 記憶装置の機密保護 計算機におけるファイル管理 検索装置
主要キーワード 孤立ノード 差分集合 二部グラフ 偽データ 処理ルート データブロック群 最小要素 秘匿化処理
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2014年5月29日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

解決手段

本方法は、第1インデックス値と当該第1インデックス値に関連付けられている第2インデックス値と当該第1インデックス値の変換後の複数の第3インデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3インデックス値を取得する処理、データ格納部から、入力されたインデックス値に関連付けられている第2インデックス値を取得する処理、データ格納部から、取得された第2インデックス値に関連付けられている、当該取得された第2インデックス値の変換後の複数の第3インデックス値を取得する処理、入力されたインデックス値の変換後の複数の第3インデックス値及び取得された第2インデックス値の変換後の複数の第3インデックス値から、クエリを生成する処理を含む。

概要

背景

検索のためのインデックス値秘匿化してデータベース登録し、当該データベースに対する検索時にもキーワードを秘匿したまま検索するという要求が存在する。このため、例えば、検索のためのインデックス値を、鍵付ハッシュ関数で暗号化してデータベースに登録して検索に用いる方法がある。

例えば図1のようなデータを考える。一番右の「詳細」の列以外の5列は検索用インデックスだとする。図1のまま登録するとデータベースの管理者からデータを秘匿できないので、暗号化して登録する。

そこで、例えば図2のように暗号化することが考えられる。Hk()は鍵付ハッシュ関数で、例えばHMAC(Keyed-Hashing for Message Authentication code)などである。Ek()は可逆暗号化関数で、たとえばAES(Advanced Encryption Standard)などである。

図2を見ても、鍵Kを知らないデータベースの管理者等からは平文(すなわち元データ)を一般的には知ることはできない。一方、鍵Kを知っている利用者は検索用インデックス値を使って検索をすることができる。例えば、「姓=佐」の行を知りたい場合は、「姓=Hk(佐藤)」を指定した検索クエリーを用いれば、データベースから検索結果(1行目、... など)を得ることができる。

しかしながら、攻撃者(データベースの管理者など)が平文の出現頻度を知っている場合には、攻撃者は検索用インデックス値の平文を推測できてしまうという問題がある。

例えば、「姓」の平文として、「佐藤」が最頻出であることを攻撃者が知っているとする。そこで、図3に模式的に示すように、図2の「姓」列の出現頻度についてヒストグラムを生成すると、「姓」列の値「HK(佐藤)」が最頻出であると分かれば、攻撃者は、その値の平文は「佐藤」であると容易に推測できる。

また、平文をいくつかの別の平文に変換し、秘匿化文(例えばハッシュ値)の頻度を均一にすることで、頻度情報からの平文推測を防ぐ技術がある。例えば、「姓」の頻度情報として、図4左に示すように、「佐藤」は「山田」の2.5倍頻出するものとする。そうすると、図4右に模式的に示すように、例えば「佐藤」を「佐藤1」乃至「佐藤5」の5種類の値のいずれかにランダムに変換し、「山田」を「山田1」と「山田2」の2種類の値のどちらかにランダムに変換する。そうすると、「佐藤」と「山田」についての変換後のインデックス値の出現頻度は均一化される。そして、図5に示すように、変換後のインデックス値の鍵付ハッシュ値の頻度も均一化されるため、データベースの管理者は暗号文の出現頻度から平文を推測することができない。この例では、少なくとも「佐藤」と「山田」のいずれであるかは分からない。

しかし、この従来技術には、検索結果の頻度から平文を推測されることへの対策がない。例えば、上で述べた例において、利用者が「姓=佐藤」の行を抽出する状況を考える。「佐藤」から「佐藤1」乃至「佐藤5」への変換はランダムであるので、それら個々の値を独立に検索する理由はない。すなわち、「姓=佐藤」の行を知りたい場合、「姓=Hk(佐藤1)」乃至「姓=HK(佐藤5)」の5種類の検索クエリーを短時間内に発行することになる。

その検索結果の行数の総和は、元々「姓=佐藤」だった行数に一致する。よって、データベースの管理人等が、図6に模式的に示すように、検索クエリーとその結果を何度も観測していると、「姓」に対する検索クエリーについて、短時間内の検索結果に含まれる行番号のうち他の検索結果でも必ず共起する行番号の集合を抽出し、図7に示すようにヒストグラムを生成してみる。そうすると、含まれる行の数が最も多い集合が、「姓」が平文「佐藤」の行の集合であることが推定できる。また、含まれる行の数が最も多い集合の行数×約0.4が行数となっている集合についても、「姓」が平文「山田」の行の集合であることを推測できる。このような検索結果における共起をも考慮に入れないと、検索用インデックス値を推測されてしまう。

なお、別の従来技術として、検索クエリーに偽データを含めることで検索クエリーの秘匿性を確保する技術がある。しかし、この従来技術は、あくまで検索クエリーの秘匿性を確保するためのものであり、検索結果における頻度から平文を推測されることへの対策にはならない。

たとえば、前述の例で、「姓=佐藤」の行を知りたい場合、この従来技術では「姓=HK(佐藤1)」乃至「姓=HK(佐藤5)」の5種類に加え「姓=ランダム値」の検索クエリーを短時間内に発行し、「姓=HK(佐藤1)」乃至「姓=HK(佐藤5)」の5種類の検索結果の行を抽出する。しかし、ランダム値が鍵付ハッシュ値に一致することはほぼ無いので、やはり、データベースの管理者等が検索結果を観測すれば、上と同じ方法で、「姓」が平文「佐藤」の行の集合を推定することができる。また、たとえランダム値が「HK(山田1)」などに一致することがあっても、別のランダム値を使った検索結果との共通行集合を求めることで、やはりその共通行集合に含まれる行の「姓」が平文「佐藤」であることを推測できる。

例えば、7行のレコードが登録されていて、「佐藤」に相当する行は {1, 3, 4, 6, 7}行目だとする。短時間内のある検索結果は {1, 2, 3, 4, 6, 7} 行目であり、他のある検索結果は {1, 3, 4, 5, 6, 7}行目であるかもしれない。しかし、どの検索結果を見ても、1行目が含まれているときは常に {1, 3, 4, 6, 7} 行目が含まれているため、その集合に含まれる{1, 3, 4, 6, 7} 行は、頻度が最多の「佐藤」であると推測できてしまう。

概要

データベースのインデックス値を秘匿する。本方法は、第1インデックス値と当該第1インデックス値に関連付けられている第2インデックス値と当該第1インデックス値の変換後の複数の第3インデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3インデックス値を取得する処理、データ格納部から、入力されたインデックス値に関連付けられている第2インデックス値を取得する処理、データ格納部から、取得された第2インデックス値に関連付けられている、当該取得された第2インデックス値の変換後の複数の第3インデックス値を取得する処理、入力されたインデックス値の変換後の複数の第3インデックス値及び取得された第2インデックス値の変換後の複数の第3インデックス値から、クエリを生成する処理を含む。

目的

特開2010−267227号公報




伊藤隆, 服部 充洋,田 規,井 祐介, 太田 和夫,頻度分析耐性を持つ高速秘匿検索方式, "電子情報通信学会技術研究報告. ISEC,情報セキュリティ", Vol. 110, Num. 443, pp. 1-6, 2011.






従って、本技術の目的は、一側面によれば、データベースのインデックス値を秘匿するための技術を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する処理を、コンピュータに実行させるためプログラム

請求項2

前記クエリの検索結果に含まれるデータのうち、前記入力されたインデックス値の変換後の複数の第3のインデックス値についてのデータを抽出する処理をさらに前記コンピュータに実行させるための請求項1記載のプログラム。

請求項3

前記クエリの検索結果において、前記入力されたインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記入力されたインデックス値に関連付けられている第2のインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、前記頻度が一致する前記第3のインデックス値の種類数が予め定められた数以上となっている請求項2記載のプログラム。

請求項4

第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックに含まれる出現確率に従って、前記検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定し、特定された前記第3のインデックス値又は当該特定された前記第3のインデックス値の秘匿化値で、前記検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する処理をコンピュータに実行させ、前記第1のインデックス値の変換後の複数の第3のインデックス値及び前記第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、前記第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ前記頻度が一致する前記第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、前記出現確率が設定されているプログラム。

請求項5

前記第1のインデックス値を当該第1のインデックス値の相対頻度降順ソートし、前記相対頻度が大きい順に、前記第1のインデックス値を、予め定められた数以上の第1のインデックス値が含まれるようにグループ化し、各グループにおいて、当該グループに含まれる第1のインデックス値についての変換後の第3のインデックス値の種類数を最小化し、且つ前記条件を満たすように、当該グループに含まれる第1のインデックス値の各々について、前記第3のインデックス値の種類数及び当該第3のインデックス値の各々についての出現確率を決定する処理をさらに含む請求項4記載のプログラム。

請求項6

第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する処理を、コンピュータが実行する検索処理方法

請求項7

第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックに含まれる出現確率に従って、前記検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定し、特定された前記第3のインデックス値又は当該特定された前記第3のインデックス値の秘匿化値で、前記検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する処理を、コンピュータが実行し、前記第1のインデックス値の変換後の複数の第3のインデックス値及び前記第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、前記第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ前記頻度が一致する前記第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、前記出現確率が設定されているデータ生成方法

請求項8

第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部と、前記データ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する生成部と、を有する情報処理装置

請求項9

第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部と、前記データ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックを特定し、特定された前記データブロックに含まれる出現確率に従って、前記検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定し、特定された前記第3のインデックス値又は当該特定された前記第3のインデックス値の秘匿化値で、前記検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する生成部と、を有し、前記第1のインデックス値の変換後の複数の第3のインデックス値及び前記第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、前記第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ前記頻度が一致する前記第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、前記出現確率が設定されている情報処理装置。

請求項10

情報処理装置と、検索処理装置と、を有し、前記情報処理装置は、第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部と、前記データ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する生成部と、前記クエリを前記検索処理装置に送信する送信部と、前記検索処理装置から、前記クエリの検索結果を受信する受信部と、前記クエリの検索結果に含まれるデータのうち、前記入力されたインデックス値の変換後の複数の第3のインデックス値についてのデータを抽出する抽出部と、を有し、前記検索処理装置は、前記クエリを前記情報処理装置から受信すると、前記クエリに従ってデータベースに対して検索処理を実行して、前記クエリの検索結果を前記情報処理装置に送信し、前記第1のインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ前記頻度が一致する前記第3のインデックス値の種類数が予め定められた数以上となるように、前記第3のインデックス値についてのデータが前記データベースに格納されているシステム

技術分野

0001

本技術は、情報の秘匿検索技術に関する。

背景技術

0002

検索のためのインデックス値秘匿化してデータベース登録し、当該データベースに対する検索時にもキーワードを秘匿したまま検索するという要求が存在する。このため、例えば、検索のためのインデックス値を、鍵付ハッシュ関数で暗号化してデータベースに登録して検索に用いる方法がある。

0003

例えば図1のようなデータを考える。一番右の「詳細」の列以外の5列は検索用インデックスだとする。図1のまま登録するとデータベースの管理者からデータを秘匿できないので、暗号化して登録する。

0004

そこで、例えば図2のように暗号化することが考えられる。Hk()は鍵付ハッシュ関数で、例えばHMAC(Keyed-Hashing for Message Authentication code)などである。Ek()は可逆暗号化関数で、たとえばAES(Advanced Encryption Standard)などである。

0005

図2を見ても、鍵Kを知らないデータベースの管理者等からは平文(すなわち元データ)を一般的には知ることはできない。一方、鍵Kを知っている利用者は検索用インデックス値を使って検索をすることができる。例えば、「姓=佐」の行を知りたい場合は、「姓=Hk(佐藤)」を指定した検索クエリーを用いれば、データベースから検索結果(1行目、... など)を得ることができる。

0006

しかしながら、攻撃者(データベースの管理者など)が平文の出現頻度を知っている場合には、攻撃者は検索用インデックス値の平文を推測できてしまうという問題がある。

0007

例えば、「姓」の平文として、「佐藤」が最頻出であることを攻撃者が知っているとする。そこで、図3に模式的に示すように、図2の「姓」列の出現頻度についてヒストグラムを生成すると、「姓」列の値「HK(佐藤)」が最頻出であると分かれば、攻撃者は、その値の平文は「佐藤」であると容易に推測できる。

0008

また、平文をいくつかの別の平文に変換し、秘匿化文(例えばハッシュ値)の頻度を均一にすることで、頻度情報からの平文推測を防ぐ技術がある。例えば、「姓」の頻度情報として、図4左に示すように、「佐藤」は「山田」の2.5倍頻出するものとする。そうすると、図4右に模式的に示すように、例えば「佐藤」を「佐藤1」乃至「佐藤5」の5種類の値のいずれかにランダムに変換し、「山田」を「山田1」と「山田2」の2種類の値のどちらかにランダムに変換する。そうすると、「佐藤」と「山田」についての変換後のインデックス値の出現頻度は均一化される。そして、図5に示すように、変換後のインデックス値の鍵付ハッシュ値の頻度も均一化されるため、データベースの管理者は暗号文の出現頻度から平文を推測することができない。この例では、少なくとも「佐藤」と「山田」のいずれであるかは分からない。

0009

しかし、この従来技術には、検索結果の頻度から平文を推測されることへの対策がない。例えば、上で述べた例において、利用者が「姓=佐藤」の行を抽出する状況を考える。「佐藤」から「佐藤1」乃至「佐藤5」への変換はランダムであるので、それら個々の値を独立に検索する理由はない。すなわち、「姓=佐藤」の行を知りたい場合、「姓=Hk(佐藤1)」乃至「姓=HK(佐藤5)」の5種類の検索クエリーを短時間内に発行することになる。

0010

その検索結果の行数の総和は、元々「姓=佐藤」だった行数に一致する。よって、データベースの管理人等が、図6に模式的に示すように、検索クエリーとその結果を何度も観測していると、「姓」に対する検索クエリーについて、短時間内の検索結果に含まれる行番号のうち他の検索結果でも必ず共起する行番号の集合を抽出し、図7に示すようにヒストグラムを生成してみる。そうすると、含まれる行の数が最も多い集合が、「姓」が平文「佐藤」の行の集合であることが推定できる。また、含まれる行の数が最も多い集合の行数×約0.4が行数となっている集合についても、「姓」が平文「山田」の行の集合であることを推測できる。このような検索結果における共起をも考慮に入れないと、検索用インデックス値を推測されてしまう。

0011

なお、別の従来技術として、検索クエリーに偽データを含めることで検索クエリーの秘匿性を確保する技術がある。しかし、この従来技術は、あくまで検索クエリーの秘匿性を確保するためのものであり、検索結果における頻度から平文を推測されることへの対策にはならない。

0012

たとえば、前述の例で、「姓=佐藤」の行を知りたい場合、この従来技術では「姓=HK(佐藤1)」乃至「姓=HK(佐藤5)」の5種類に加え「姓=ランダム値」の検索クエリーを短時間内に発行し、「姓=HK(佐藤1)」乃至「姓=HK(佐藤5)」の5種類の検索結果の行を抽出する。しかし、ランダム値が鍵付ハッシュ値に一致することはほぼ無いので、やはり、データベースの管理者等が検索結果を観測すれば、上と同じ方法で、「姓」が平文「佐藤」の行の集合を推定することができる。また、たとえランダム値が「HK(山田1)」などに一致することがあっても、別のランダム値を使った検索結果との共通行集合を求めることで、やはりその共通行集合に含まれる行の「姓」が平文「佐藤」であることを推測できる。

0013

例えば、7行のレコードが登録されていて、「佐藤」に相当する行は {1, 3, 4, 6, 7}行目だとする。短時間内のある検索結果は {1, 2, 3, 4, 6, 7} 行目であり、他のある検索結果は {1, 3, 4, 5, 6, 7}行目であるかもしれない。しかし、どの検索結果を見ても、1行目が含まれているときは常に {1, 3, 4, 6, 7} 行目が含まれているため、その集合に含まれる{1, 3, 4, 6, 7} 行は、頻度が最多の「佐藤」であると推測できてしまう。

0014

特開2010−267227号公報

先行技術

0015

伊藤隆, 服部 充洋,田 規,井 祐介, 太田 和夫,頻度分析耐性を持つ高速秘匿検索方式, "電子情報通信学会技術研究報告. ISEC,情報セキュリティ", Vol. 110, Num. 443, pp. 1-6, 2011.

発明が解決しようとする課題

0016

従って、本技術の目的は、一側面によれば、データベースのインデックス値を秘匿するための技術を提供することである。

課題を解決するための手段

0017

第1の態様に係るクエリ生成方法は、(a)第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得する処理、(b)データ格納部から、入力されたインデックス値に関連付けられている第2のインデックス値を取得する処理、(c)データ格納部から、取得された第2のインデックス値に関連付けられている、当該取得された第2のインデックス値の変換後の複数の第3のインデックス値を取得する処理、(d)入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する処理を含む。

0018

第2の態様に係るデータ生成方法は、(e)第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックに含まれる出現確率に従って、検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定する処理、(f)特定された第3のインデックス値又は当該特定された第3のインデックス値の秘匿化値で、検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する処理とを含む。そして、第1のインデックス値の変換後の複数の第3のインデックス値及び第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、(g)第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ(h)頻度が一致する第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、出現確率が設定されている。

発明の効果

0019

一側面によれば、データベースのインデックス値を秘匿できるようになる。

図面の簡単な説明

0020

図1は、検索対象データの一例を示す図である。
図2は、暗号化された検索対象データの一例を示す図である。
図3は、攻撃者による攻撃を説明するための図である。
図4は、従来技術を説明するための図である。
図5は、従来技術を説明するための図である。
図6は、従来技術の問題点を説明するための図である。
図7は、従来技術の問題点を説明するための図である。
図8は、本技術の実施の形態におけるシステム概要図である。
図9は、データ登録装置機能ブロック図である。
図10は、頻度データの一例を示す図である。
図11は、データ検索装置の機能ブロック図である。
図12は、データ登録装置の処理フローを示す図である。
図13は、グループ情報の一例を示す図である。
図14は、グループ情報を用いてインデックス値を置換した場合における検索データに対する検索結果における頻度を模式的に示す図である。
図15Aは、グループ情報を説明するための図である。
図15Bは、グループ情報を説明するための図である。
図15Cは、グループ情報を説明するための図である。
図16は、グループ情報生成処理の処理フローを示す図である。
図17は、因子群生成処理の処理フローを示す図である。
図18は、二部グラフの一例を示す図である。
図19は、変更後の二部グラフの一例を示す図である。
図20は、二部グラフの他の例を示す図である。
図21は、変更後の二部グラフの他の例を示す図である。
図22は、変換及び秘匿化処理の処理フローを示す図である。
図23は、検索用データに含まれるインデックス値の一例を示す図である。
図24は、変換後値のハッシュ値の一例を示す図である。
図25は、データベースに登録される検索用データの一例を示す図である。
図26は、データ検索装置に関連する処理を説明するための処理フローを示す図である。
図27は、クエリ生成処理の処理フローを示す図である。
図28は、データ検索装置の第3データ格納部に格納されるデータの一例を示す図である。
図29は、コンピュータの機能ブロック図である。

実施例

0021

本技術の実施の形態に係るシステムの概要を図8に示す。例えばインターネットなどのネットワーク1には、クラウドなどに含まれる検索サーバ7と、1又は複数のデータ検索装置5と、データ登録装置3とが接続されている。検索サーバ7は、秘匿化されたデータを蓄積しているデータベース(DB)71を管理し、データ検索装置5からの検索要求(すなわちクエリ)に応じて検索を行って、検索結果を返信する。検索サーバ7自体の処理は従前と同様であるからこれ以上説明しない。データ検索装置5は、以下で述べるように秘匿化されたインデックス値を含むクエリを検索サーバ7に送信し、検索サーバ7から検索結果を受信する。データ登録装置3は、以下で述べるように処理したデータを、検索サーバ7のデータベース71に登録する処理を実行する。

0022

図9に、データ登録装置3の機能ブロック図を示す。データ登録装置3は、第1データ格納部31と、第2データ格納部32と、生成部33と、第3データ格納部34と、秘匿化処理部35と、第4データ格納部36と、登録処理部37とを有する。

0023

第1データ格納部31には、例えば図1に示すような秘匿化されていない検索用データが格納されている。但し、説明を簡単化するために、姓以外の検索インデックスは存在しないものとする。

0024

また、第2データ格納部32には、例えば図10に示すような頻度データを格納している。図10は、例えば図1のようなデータにおいて、「姓」という検索インデックスに含まれる各インデックス値の頻度データが登録されるようになっている。このようなデータについては、予め第1データ格納部31に格納されている検索用データを処理して用意しておくものとする。また、暗号鍵Kについても第2データ格納部32に格納されているものとする。なお、頻度の値は、相対頻度が計算できるような値であれば、どのようなものであっても良い。

0025

生成部33は、第2データ格納部32に格納されている頻度データを用いて、グループ情報を生成し、第3データ格納部34に格納する。秘匿化処理部35は、第1データ格納部31に格納されている検索用データに対して、第3データ格納部34に格納されているグループ情報を用いて変換処理を実行すると共に、第2データ格納部32に格納されている暗号鍵を用いて暗号化処理等を実行し、処理結果を第4データ格納部36に格納する。登録処理部37は、第4データ格納部36に格納されている秘匿化検索用データを、検索サーバ7に送信して、データベース71に登録させる。

0026

また、図11に、データ検索装置5の機能ブロック図を示す。データ検索装置5は、入力部51と、第1データ格納部52と、第2データ格納部53と、クエリ生成部54と、第3データ格納部55と、送信部56と、受信部57と、第4データ格納部58と、抽出部59と、第5データ格納部60と、出力部61とを有する。

0027

入力部51は、ユーザからクエリに係るキーワード(インデックス値)の入力を受け付け、第1データ格納部52に格納する。クエリ生成部54は、第2データ格納部53に格納されているグループ情報等を用いて、第1データ格納部52に格納されているキーワードからクエリのデータを生成し、第3データ格納部55に格納する。送信部56は、生成されたクエリを、検索サーバ7に送信する。

0028

受信部57は、クエリに対する検索結果を受信し、第4データ格納部58に格納する。抽出部59は、第4データ格納部58に格納されている検索結果からを該当するデータを抽出し、さらに暗号鍵Kを用いて復号して、処理結果を第5データ格納部60に格納する。出力部61は、第5データ格納部60に格納されている処理結果をユーザに対して出力する。

0029

次に、図12乃至図28を用いて、図8に示されているシステムの処理内容について説明する。

0030

まず、データ登録装置3の処理内容について図12乃至図25を用いて説明する。

0031

最初に、生成部33は、第2データ格納部32に格納されている頻度データに対してグループ情報生成処理を実行し、処理結果を第3データ格納部34に格納する(図12:ステップS1)。このグループ情報生成処理については、図13乃至図21を用いて説明する。

0032

グループ情報とは、例えば図13に示すようなデータである。図13の例では、各姓(すなわちインデックス値)について、同時にクエリに含めるべきインデックス値と、変換の確率と変換後のインデックス値(すなわち変換後値)との複数の組み合わせとが登録されるようになっている。例えば、「佐藤」についてクエリを生成する場合には、変換後値「佐藤1」乃至「佐藤5」に加えて、「鈴木」及び「高橋」についての変換後値をもクエリに含めることになる。ここでは、このように少なくとも3つの姓(すなわちインデックス値)についての変換後値をクエリに含めることになる。他の姓についても同様である。

0033

さらに、検索用データに含まれる「佐藤」というインデックス値を秘匿化する場合には、確率「90/192」で変換後値「佐藤1」を用い、確率「29/192」で変換後値「佐藤2」を用い、確率「29/192」で変換後値「佐藤3」を用い、確率「22/192」で変換後値「佐藤4」を用い、確率「22/192」で変換後値「佐藤5」を用いる。他の姓についても同様である。

0034

このような変換が検索用データに対して行われて「佐藤」「鈴木」「高橋」のいずれかについて検索を行うと、図14に示すように、「佐藤1」、「鈴木1」及び「高橋1」というインデックス値を含むレコードの頻度が一致するようになり、共起を考慮した場合であっても区別できなくなる。同様に、「佐藤2」「佐藤3」「鈴木2」「鈴木3」及び「高橋2」というインデックス値を含むレコードの頻度が、「佐藤1」「鈴木1」及び「高橋1」よりも低いが一致するようになり、共起を考慮した場合にも区別できなくなる。さらに、「佐藤4」「佐藤5」「鈴木4」及び「高橋3」というインデックス値を含むレコードの頻度が、「佐藤2」「佐藤3」「鈴木2」「鈴木3」及び「高橋2」よりも低いが一致するようになり、共起を考慮した場合にも区別できなくなる。従って、全体として検索の秘匿化が図られる。

0035

本実施の形態では、少なくとも所定数(ここでは「3」)の変換後値の頻度が検索時に同一になるように、且つ頻度が同一なる変換後値の変換前のインデックス値はグループ化された全インデックス値を含むように(すなわち、佐藤、鈴木、高橋のそれぞれ少なくとも1つの変換後値がグループとなって当該グループでは頻度が同じ)、変換後値の数及び確率が決定されるようになっている。さらに、本実施の形態では、変換後値の種類数が最少になるように、変換後値の数及び確率が決定されるようになっている。

0036

但し、変換後値の種類数が最少という要件は、クエリに含まれる変換後値の数を少なくするための条件である。例えば、図15Aに示すようなインデックス値と相対頻度の組み合わせが得られた場合、本実施の形態では以下で述べる処理を実施すれば図15Bに示すようなグループ情報(簡易版)が得られる。但し、AとBとCとが、同時にクエリに含めるべきインデックス値であり、所定値が「3」であるものとする。変換後値「A1」「A2」「B1」「B2」「C1」については検索時の頻度が同一であり、変換後値「A3」「A4」「A5」「B3」「C2」についても検索時の頻度が同一である。よって、上で述べた2つの条件を満たしている。

0037

ここでは、インデックス値「A」で検索を行う場合には、インデックス値「A」の変換後値とインデックス値「B」の変換後値とインデックス値「C」の変換後値の合計10個の変換後値を含むクエリで検索を行うことになる。

0038

一方、図15Cに示すようなグループ情報(簡易版)でも、最初の条件については満たされている。すなわち、変換後値「A1」「A2」「A3」「B1」「B2」「C1」の検索時の頻度は同じであり、変換後値「A4」「B3」「C2」の検索時の頻度は同じであり、変換後値「A5」「B4」「B5」「B6」「C3」の検索時の頻度は同じである。しかしながら、このようなグループ情報を用いると、インデックス値「A」で検索を行う場合には、インデックス値「A」の変換後値とインデックス値「B」の変換後値とインデックス値「C」の変換後値の合計14個の変換後値を含むクエリで検索を行うことになる。すなわち、データ量が増えてしまうので、第2の条件を満たしているわけではない。第2の条件は必須ではないが、第1の条件と第2の条件とを満たしていることが好ましい。

0039

次に、図16乃至図21を用いて具体的に図13に示すようなグループ情報を生成する処理について説明する。

0040

生成部33は、第2データ格納部32に格納されている頻度データに含まれる要素を頻度の降順ソートする(図16:ステップS11)。図10は既にソートされた状態を示している。

0041

次に、生成部33は、頻度の降順に、順次最小要素数p個ずつでグループを生成する(ステップS13)。図10の例であれば、「佐藤」「鈴木」「高橋」で1グループ、「田中」「渡辺」「伊藤」「山本」で1グループとなる。このように最後のグループについては、最大2p−1個のインデックス値でグループ化される。

0042

その後、生成部33は、未処理のグループを1つ選択する(ステップS15)。また、生成部33は、選択されたグループ内の要素の頻度を相対頻度(自然数)に変換する(ステップS17)。予め設定された精度を維持するように自然数の相対頻度を算出する。例えば、「佐藤」「鈴木」「高橋」については「192」「170」「141」が得られたものとする。

0043

そうすると、生成部33は、相対頻度について、差分集合ds及び最小値mを算出する(ステップS19)。ds={192−170,170−141}={22,29}となる。また、m=141となる。

0044

そして、生成部33は、因子群生成処理を実行する(ステップS21)。この因子群生成処理については、後に図17乃至図21を用いて説明する。例えば、上で述べた例では、因子群は{90,29,22}となる。

0045

そして、生成部33は、因子群から変換データを生成する(ステップS23)。変換データについては、各因子が1回以上出現し、因子の和が相対頻度と等しくなり、且つ因子数が最小となるように、しらみつぶしに探索する。上で述べた例では、「佐藤」であれば、{90,29,29,22,22}という変換データが生成され、因子数は5となる。この変換データに含まれる値を全て加算すれば相対頻度「192」となる。「鈴木」であれば、{90,29,29,22}という変換データが生成され、因子数は4となる。この変換データに含まれる値を全て加算すれば相対頻度「170」となる。同様に、「高橋」であれば、{90,29,22}という変換データが生成され、因子数は3となる。この変換データに含まれる値を全て加算すれば相対頻度「141」となる。

0046

そして、生成部33は、未処理のグループが存在するか判断する(ステップS25)。未処理のグループが存在する場合にはステップS15に戻る。一方、未処理のグループが存在しない場合には、生成部33は、変換データからグループ情報を生成し、第3データ格納部34に格納する(ステップS27)。そして処理は呼び出し元の処理に戻る。

0047

変換データに含まれる因子の数分だけ変換後値を所定のルールで生成する。図13の例では、「佐藤」についての因子数は「5」であるから、「佐藤1」乃至「佐藤5」という変換後値を生成する。「鈴木」及び「高橋」などについても同様である。さらに、因子の値から確率を算出する。「佐藤」の場合には、90/192、29/192、29/192、22/192、22/192というように、「佐藤1」乃至「佐藤5」の各々について、因子の値/相対頻度にて確率を設定する。「鈴木」及び「高橋」についても同様の処理を実行する。

0048

このような処理を実行することで、上で述べたような性質を有するグループ情報が得られるようになる。

0049

次に、因子群生成処理について、詳しく説明する。

0050

各グループの因子群は、上でも述べたように当該因子群に含まれる各因子を1回以上加算することで、グループ内における対応する変換後値の各相対頻度と等しくなるような自然数を含む自然数群である。例えば、あるグループ内における相対頻度が4と7の場合、因子群は{1,3}である。なぜなら、4=1+3,7=1+3+3と表せられるからである。一方、{2,3}は因子群ではない。なぜなら、7は7=2+3+3と各因子の1回以上の加算で表せられるが、4は表せられない。すなわち、4=2+2では因子「3」が使われていない。

0051

一方、全ての自然数は「1」を1回以上加算することで表せられるので、{1}は常に因子群となる。

0052

平文を推測されないようにするという目的だけなら、因子群は任意のもので良く、{1}でも良い。しかし、上でも述べたようにグループ情報における変換後値の数が少ない方が「グループ情報」のデータ量を少なくでき、その結果クエリのデータ量も少なくできるので望ましい。

0053

そのためには、各因子の値が大きい因子群を使うことが望ましい。各因子の値が大きいと、加算回数が少なくなり、変換後値が少なくなるためである。

0054

以下で述べる因子群生成処理では、次の考え方により各因子の値が大きい因子群を算出する。まず、処理に係るグループについての相対頻度の最小値mは、各因子の1回以上の加算で構成されることになる。そして、mが構成できる場合、差分集合dsの各要素が各因子の0回以上の加算で構成できれば、mより大きい各相対頻度も構成できる。また、dsの各要素について、要素の約数のいずれかが因子ならその0回以上の加算で要素を構成できる。

0055

すなわち、dsの全要素のうちその約数がまだ因子群になっていないものについては、各因子の和がm未満となる限り最大の約数を順次因子として良い(第1の処理ルート)。但し、dsの全要素についてその約数のいずれかが因子ならば、各因子の和がちょうどmになっていても良い(第2の処理ルート)。dsの全要素についてその約数のいずれかが因子となった状態で、それらの因子の和がm未満なら、その不足分を因子として良い(第3の処理ルート)。

0056

このような処理内容を図17乃至図21を用いて説明する。まず、生成部33は、dsとdsの各要素の約数との関係を、2部グラフを生成する(図17:ステップS31)。例えば、図18のような2部グラフが生成される。dsの要素「29」については約数「1」「29」であり、dsノード「29」と約数ノード「1」「29」が繋がれる。また、dsの要素「22」については約数ノード「22」「11」「2」「1」が繋がれる。

0057

そして、生成部33は、約数ノードにmがあり且つそのノードが残り全てのdsノードに直接繋がっているか判断する(ステップS33)。この条件を満たさない場合には、生成部33は、約数ノードのうち、m未満の最大の約数を因子に設定する(ステップS37)。そして処理はステップS39に移行する。

0058

一方、この条件を満たす場合には、生成部33は、mを因子に設定する(ステップS35)。その後、生成部33は、mから因子に設定された値を差し引き、新たなmに設定する(ステップS39)。さらに、生成部33は、因子とした約数ノードとそれに直接繋がっているdsノードとを全て削除し、さらに孤立した約数ノードをも削除する(ステップS41)。そして、生成部33は、dsノードが残っているか判断する(ステップS43)。dsノードが残っている場合には、処理はステップS33に戻る。

0059

一方、dsノードが残っていない場合には、生成部33は、m=0であるか判断する(ステップS45)。m=0であれば処理はステップS49に移行する。一方、m=0でなければ、生成部33は、mを因子に設定する(ステップS47)。そして、生成部33は、全因子を因子群に設定する(ステップS49)。その後処理は呼び出し元の処理に戻る。

0060

図18のような二部グラフが生成された状態において、m=141なので、「141」という約数ノードはないので、処理はステップS33からステップS37へ移行して、141未満の最大の約数「29」を因子として設定する。そして、ステップS39で、141−29=112をmに設定する。そして、ステップS41で約数ノード「29」に繋がっているdsノード「29」を削除する。但し、dsノード「29」に繋がっている「1」は他のdsノードにも繋がっているので、約数ノード「1」は残る。そうすると、図19に示すような状態となる。

0061

さらに、m=112であるから、「112」という約数ノードはないので、処理はステップS33からステップS37へ移行して、112未満の最大の約数「22」を因子として設定する。そして、ステップS39で、112−22=90をmに設定する。そして、ステップS41で約数ノード「22」に繋がっているdsノード「22」を削除する。そうすると、約数ノード「11」「2」「1」は孤立しているので、これらも削除される。そうすると、二部グラフにノードは残っていないので、ステップS45でm=0であるか判断されるが、m=90であるから、ステップS47で「90」が因子に設定される。

0062

このように結果として因子群には{90,29,22}が入ることになる。

0063

図18及び図19で説明した処理ルートは、第1の処理ルート及び第3の処理ルートである。

0064

また、他の例として、相対頻度が{9,15,24,39}で、ds={6,9,15}でm=9である場合を説明する。このような場合には、ds「15」の約数は「15」「5」「3」「1」であり、ds「9」の約数は「9」「3」「1」であり、ds「6」の約数は「6」「3」「2」「1」である。従って、図20に示すような二部グラフが得られる。そして、m=9の約数ノードが存在しているが、この約数ノードはdsノード「6」「15」には直接繋がっていないので、ステップS33からステップS37に処理は移行して、9未満の最大の約数「6」を因子に設定する。そして、ステップS39でm=9−6=3が設定される。さらに、ステップS41では、約数ノード「6」と、それに繋がっているdsノード「6」を削除し、これにより孤立する約数ノード「2」をも削除する。そうすると、二部グラフは図21に示すような状態になる。

0065

さらに、m=3であるから、ステップS33において、約数ノード「3」が残り全てのdsノードに接続されているか確認するが、ここではdsノード「15」及び「9」に接続されている。そうすると、ステップS33の条件を満たしているので、ステップS35でm=3を因子に設定する。そうすると、ステップS39においてm=0となる。さらに、ステップS41で、約数ノード「3」と、dsノード「9」及び「15」を削除すると、残った約数ノードは孤立ノードとなるので、残りを削除することになる。そうすると、m=0であるから、ステップS45でYesルートを経由して処理が完了することになる。このように、上で述べた第2の処理ルートを経由して処理される。

0066

以上のような処理を実行することで、適切な因子群を得ることができ、最適なグループ情報を生成できるようになる。

0067

図12の処理フローの説明に戻って、秘匿化処理部35は、第1データ格納部31に格納されている検索用データに対して、第2データ格納部32及び第3データ格納部34に格納されているデータを用いて、変換及び秘匿化処理を実行し、処理結果を第4データ格納部36に格納する(ステップS3)。変換及び秘匿化処理については、図22乃至図24を用いて説明する。

0068

秘匿化処理部35は、第1データ格納部31に格納されている検索用データにおけるインデックス値のうち、未処理のインデックス値を選択する(図22:ステップS61)。例えば、図23に示すようなインデックス値が検索用データに含まれているとすると、上から順番に処理することになる。

0069

そして、秘匿化処理部35は、第3データ格納部34に格納されているグループ情報(図13)に従って、インデックス値を変換後値に変換する(ステップS63)。「鈴木」を処理する場合には、90/170の確率で「鈴木1」、29/170の確率で「鈴木2」、29/170の確率で「鈴木3」、22/170の確率で「鈴木4」に変換する。

0070

その後、秘匿化処理部35は、変換後値を、暗号鍵Kとハッシュ関数によりハッシュ値に変換する(ステップS65)。すなわち、Hk(変換後値)を算出する。

0071

そして、秘匿化処理部35は、未処理のインデックス値が存在するか判断し(ステップS67)、未処理のインデックス値が存在する場合には処理はステップS61に戻る。一方、未処理のインデックス値が存在しない場合には、処理は呼び出し元の処理に戻る。

0072

例えば図23のようなインデックス値を処理すれば、図24に示すような変換後値のハッシュ値が得られるようになる。このように、元のインデックス値は、変換後値のハッシュ値により置換されることになる。

0073

図12の処理フローの説明に戻って、秘匿化処理部35は、検索用データに含まれる各レコードのデータ部分を、暗号鍵Kで暗号化し、第4データ格納部36に格納する(ステップS5)。秘匿化処理部35は、第4データ格納部36に格納されており、且つ変換及び秘匿化されたインデックス値及び暗号化データを含むレコード群を、秘匿化検索用データを、検索サーバ7に送信して、データベース71に登録させる(ステップS7)。

0074

このような処理を実施すれば、例えば図25に示すようなデータが、データベース71に登録されるようになる。

0075

なお、上で述べた例では、1つの種類のインデックスについての処理なので、複数種類のインデックスが存在する場合には、各インデックスについて上で述べた処理を行うことになる。

0076

次に、図26乃至図28を用いて、データ検索装置5に関連する処理を説明する。ユーザは、平文検索キーWを含む検索指示を入力部51に対して入力する。そうすると、入力部51は、平文検索キーWを含む検索指示を受け付け、第1データ格納部52に格納する(図26:ステップS101)。

0077

そうすると、クエリ生成部54は、第1データ格納部52に格納されている平文検索キーWについて、第2データ格納部53に格納されているデータを用いてクエリ生成処理を実行し、第3データ格納部55に格納する(ステップS103)。クエリ生成処理については、図27及び図28を用いて説明する。

0078

クエリ生成部54は、平文検索キーWの全ての変換後値を、第2データ格納部53に格納されているグループ情報から読み出す(図27:ステップS121)。図13の例で、「佐藤」が平文検索キーWであれば、「佐藤1」乃至「佐藤5」が読み出される。

0079

また、クエリ生成部54は、読み出された変換後値を、例えば第2データ格納部53に格納されている暗号鍵Kでハッシュ化し、第3データ格納部55に格納し、さらに集合Sに設定する(ステップS123)。集合Sは、後に検索結果から抽出すべきデータを特定するために用いられる。

0080

さらに、クエリ生成部54は、グループ情報から、平文検索キーのインデックス値と同時にクエリに含めるべきインデックス値を抽出する(ステップS125)。図13の例では、「佐藤」に対して「鈴木」「高橋」が抽出される。

0081

その後、クエリ生成部54は、抽出されたインデックス値のうち未処理のインデックス値を1つ選択する(ステップS127)。そして、クエリ生成部54は、選択されたインデックス値に対応する全ての変換後値を、グループ情報から読み出す(ステップS129)。「鈴木」が選択された場合には、「鈴木1」乃至「鈴木4」が読み出される。

0082

また、クエリ生成部54は、読み出された変換後値を暗号鍵Kでハッシュ化し、第3データ格納部55に格納する(ステップS131)。そして、クエリ生成部54は、抽出されたインデックス値のうち未処理のインデックス値が存在しているか判断する(ステップS133)。未処理のインデックス値が存在する場合には、処理はステップS127に戻る。一方、未処理のインデックス値が存在しない場合には、クエリ生成部54は、1又は複数のハッシュ化された変換後値を含むクエリを生成し、第3データ格納部55に格納する(ステップS135)。クエリは1つだけではなく、複数のクエリが生成されるようにしてもよい。そして、処理は呼び出し元の処理に戻る。

0083

なお、以下の処理を実行するため、例えば図28に示すようなデータを、第3データ格納部55に格納しておく。図28の例では、ハッシュ化された変換後値と、集合Sに含まれるか否かを表すフラグとが格納されるようになっている。上でも述べたように、「佐藤1」乃至「佐藤5」については、元々の平文検索キーに対応するインデックス値の変換後値である。

0084

図26の処理の説明に戻って、送信部56は、第3データ格納部55に格納されているクエリを検索サーバ7に送信する(ステップS105)。上でも述べたようにクエリは複数の場合もある。

0085

検索サーバ7は、データ検索装置5からクエリを受信し(ステップS107)、データベース71に対してクエリによる検索を実行する(ステップS109)、そして、検索サーバ7は、検索結果を、クエリの送信元のデータ検索装置5へ送信する(ステップS111)。

0086

これに対して、データ検索装置5の受信部57は、検索サーバ7から検索結果を受信し、検索結果を第4データ格納部58に格納する(ステップS113)。

0087

そして、抽出部59は、第3データ格納部55に格納されているデータを用いて、第4データ格納部58に格納されている検索結果から平文検索キーWに対応する検索結果を抽出する(ステップS115)。図28の例では、集合Sに含まれていることを表すフラグがON(すなわち「Y」)になっており且つハッシュ化された変換後値に対応する検索結果を抽出する。

0088

そして、抽出部59は、抽出された検索結果に含まれる暗号化データを、第2データ格納部53に格納されている暗号鍵Kを用いて復号し、第5データ格納部60に格納し、出力部61は、第5データ格納部60に格納されているデータを、出力装置印刷装置表示装置など)に出力する(ステップS117)。

0089

上でも述べたように、「佐藤」を検索する場合においても、「佐藤1」乃至「佐藤5」、「鈴木1」乃至「鈴木4」及び「高橋1」乃至「高橋3」についてのレコードが検索結果として抽出される。これらのレコードは、常に同時に共起するレコードであり、図14で模式的に示したように、同一値を含むレコードの頻度は均一ではなくても少なくとも3つについては同一となるので、いずれが「佐藤」についてのレコードであるかは、弁別できない。従ってデータ検索の秘匿性が担保されている。

0090

以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。上で示したデータ検索装置5及びデータ登録装置3の機能ブロック図は一例であって、プログラムモジュール構成とは一致しない場合もある。

0091

また、処理フローについても、処理結果が変わらない限りにおいて、処理ステップの順番を入れ替えたり、複数の処理ステップの実行順番を入れ替えたりすることも可能である。

0092

なお、グループ情報については、データ検索時には、確率のデータは用いられないので、検索時のグループ情報は、データ登録時のグループ情報の一部としてもよい。

0093

さらに、グループ情報には、変換後値を登録するのではなく、ハッシュ化された変換後値を登録しておいても良い。

0094

また、グループ情報を自動的に生成する例を示したが、知見のあるユーザが別途用意するようにしても良い。

0095

なお、上で述べた検索サーバ7、データ登録装置3及びデータ検索装置5は、コンピュータ装置であって、図29に示すように、メモリ2501とCPU(Central Processing Unit)2503とハードディスクドライブ(HDD:Hard Disk Drive)2505と表示装置2509に接続される表示制御部2507とリムーバブルディスク2511用のドライブ装置2513と入力装置2515とネットワークに接続するための通信制御部2517とがバス2519で接続されている。オペレーティング・システム(OS:Operating System)及び本実施例における処理を実施するためのアプリケーションプログラムは、HDD2505に格納されており、CPU2503により実行される際にはHDD2505からメモリ2501に読み出される。CPU2503は、アプリケーション・プログラムの処理内容に応じて表示制御部2507、通信制御部2517、ドライブ装置2513を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ2501に格納されるが、HDD2505に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク2511に格納されて頒布され、ドライブ装置2513からHDD2505にインストールされる。インターネットなどのネットワーク及び通信制御部2517を経由して、HDD2505にインストールされる場合もある。このようなコンピュータ装置は、上で述べたCPU2503、メモリ2501などのハードウエアとOS及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。

0096

以上述べた本実施の形態をまとめると、以下のようになる。

0097

本実施の形態の第1の態様に係る検索処理方法は、(A)第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得する処理と、(B)データ格納部から、入力されたインデックス値に関連付けられている第2のインデックス値を取得する処理と、(C)データ格納部から、取得された第2のインデックス値に関連付けられている、当該取得された第2のインデックス値の変換後の複数の第3のインデックス値を取得する処理と、(D)入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する処理とを含む。

0098

このようにすればクエリの内容が秘匿化される。さらに、常に同じ変換後の第3のインデックス値についてのクエリが付加されるので、入力されたインデックス値が同じであれば常に同じ検索結果が得られる。すなわち、検索結果の共起を観察しても、インデックス値が推測しにくくなっている。

0099

また、上記検索方法は、(E)クエリの検索結果に含まれるデータのうち、入力されたインデックス値の変換後の複数の第3のインデックス値についてのデータを抽出する処理をさらに含むようにしても良い。これによって、要求された検索結果のみを抽出できる。

0100

さらに、上記クエリの検索結果において、(F)入力されたインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、入力されたインデックス値に関連付けられている第2のインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、(G)上記頻度が一致する第3のインデックス値の種類数が予め定められた数以上となっていることが好ましい。このような検索結果が得られるデータベースがあれば、元々のインデックス値の出現頻度の偏りから、インデックス値を推定することが困難になる。

0101

本実施の形態の第2の態様に係るデータ生成方法は、(A)第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックを特定する処理と、(B)特定されたデータブロックに含まれる出現確率に従って、検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定する処理と、(C)特定された第3のインデックス値又は当該特定された第3のインデックス値の秘匿化値で、検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する処理とを含む。そして、第1のインデックス値の変換後の複数の第3のインデックス値及び第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、(D)第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうち第一群の第3のインデックス値についての検索結果の頻度とが一致し、且つ(E)頻度が一致する第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、出現確率が設定されている。

0102

このような出現確率が設定されていれば、検索結果と、元々のインデックス値の出現頻度の偏りから、インデックス値を推定しにくくなる。なお、第3のインデックス値の数は少ない方が好ましい。

0103

上で述べたデータ登録方法は、第1のインデックス値を当該第1のインデックス値の相対頻度を降順にソートする処理と、相対頻度が大きい順に、第1のインデックス値を、予め定められた数以上の第1のインデックス値が含まれるようにグループ化する処理と、各グループにおいて、当該グループに含まれる第1のインデックス値についての変換後の第3のインデックス値の種類数を最小化し、且つ条件を満たすように、当該グループに含まれる第1のインデックス値の各々について、第3のインデックス値の種類数及び当該第3のインデックス値の各々についての出現確率を決定する処理をさらに含むようにしても良い。

0104

このようにすれば、クエリのデータ量を抑えつつ秘匿性が十分なデータブロック群を生成できるようになる。

0105

なお、上で述べたような処理をコンピュータに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、CD−ROMなどの光ディスク光磁気ディスク半導体メモリ(例えばROM)、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。

0106

以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。

0107

(付記1)
第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、
前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、
前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、
前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する
処理を、コンピュータに実行させるためプログラム。

0108

(付記2)
前記クエリの検索結果に含まれるデータのうち、前記入力されたインデックス値の変換後の複数の第3のインデックス値についてのデータを抽出する処理
をさらに前記コンピュータに実行させるための付記1記載のプログラム。

0109

(付記3)
前記クエリの検索結果において、
前記入力されたインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記入力されたインデックス値に関連付けられている第2のインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、
前記頻度が一致する前記第3のインデックス値の種類数が予め定められた数以上となっている
付記2記載のプログラム。

0110

(付記4)
第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックに含まれる出現確率に従って、前記検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定し、
特定された前記第3のインデックス値又は当該特定された前記第3のインデックス値の秘匿化値で、前記検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する
処理をコンピュータに実行させ、
前記第1のインデックス値の変換後の複数の第3のインデックス値及び前記第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、
前記第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ
前記頻度が一致する前記第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、前記出現確率が設定されている
プログラム。

0111

(付記5)
前記第1のインデックス値を当該第1のインデックス値の相対頻度を降順にソートし、
記相対頻度が大きい順に、前記第1のインデックス値を、予め定められた数以上の第1のインデックス値が含まれるようにグループ化し、
各グループにおいて、当該グループに含まれる第1のインデックス値についての変換後の第3のインデックス値の種類数を最小化し、且つ前記条件を満たすように、当該グループに含まれる第1のインデックス値の各々について、前記第3のインデックス値の種類数及び当該第3のインデックス値の各々についての出現確率を決定する
処理をさらに含む付記4記載のプログラム。

0112

(付記6)
第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、
前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、
前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、
前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する
処理を、コンピュータが実行する検索処理方法。

0113

(付記7)
第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックに含まれる出現確率に従って、前記検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定し、
特定された前記第3のインデックス値又は当該特定された前記第3のインデックス値の秘匿化値で、前記検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する
処理を、コンピュータが実行し、
前記第1のインデックス値の変換後の複数の第3のインデックス値及び前記第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、
前記第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ
前記頻度が一致する前記第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、前記出現確率が設定されている
データ生成方法。

0114

(付記8)
第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部と、
前記データ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する生成部と、
を有する情報処理装置

0115

(付記9)
第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値と当該複数の第3のインデックス値の各々についての出現確率とを関連付けるデータブロックを複数格納するデータ格納部と、
前記データ格納部から、検索対象データに含まれるインデックス値に関連するデータブロックを特定し、特定された前記データブロックに含まれる出現確率に従って、前記検索対象データに含まれるインデックス値に対応する第3のインデックス値を特定し、特定された前記第3のインデックス値又は当該特定された前記第3のインデックス値の秘匿化値で、前記検索対象データに含まれるインデックス値を置換することで、秘匿化された検索対象データを生成する生成部と、
を有し、
前記第1のインデックス値の変換後の複数の第3のインデックス値及び前記第2のインデックス値の変換後の複数の第3のインデックス値から生成されるクエリにより検索が行われた場合に、
前記第1のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値に関連付けられている複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ
前記頻度が一致する前記第3のインデックス値の数が予め定められた数以上となるという条件を満たすように、前記出現確率が設定されている
情報処理装置。

0116

(付記10)
情報処理装置と、
検索処理装置と、
を有し、
前記情報処理装置は、
第1のインデックス値と当該第1のインデックス値に関連付けられている第2のインデックス値と当該第1のインデックス値の変換後の複数の第3のインデックス値とを関連付けるデータブロックを複数格納するデータ格納部と、
前記データ格納部から、入力されたインデックス値に関連付けられている、当該入力されたインデックス値の変換後の複数の第3のインデックス値を取得し、前記データ格納部から、前記入力されたインデックス値に関連付けられている第2のインデックス値を取得し、前記データ格納部から、取得された前記第2のインデックス値に関連付けられている、当該取得された前記第2のインデックス値の変換後の複数の第3のインデックス値を取得し、前記入力されたインデックス値の変換後の複数の第3のインデックス値及び取得された前記第2のインデックス値の変換後の複数の第3のインデックス値から、クエリを生成する生成部と、
前記クエリを前記検索処理装置に送信する送信部と、
前記検索処理装置から、前記クエリの検索結果を受信する受信部と、
前記クエリの検索結果に含まれるデータのうち、前記入力されたインデックス値の変換後の複数の第3のインデックス値についてのデータを抽出する抽出部と、
を有し、
前記検索処理装置は、
前記クエリを前記情報処理装置から受信すると、前記クエリに従ってデータベースに対して検索処理を実行して、前記クエリの検索結果を前記情報処理装置に送信し、
前記第1のインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度と、前記第1のインデックス値に関連付けられている第2のインデックス値の変換後の複数の第3のインデックス値のうちいずれかのグループに属する第3のインデックス値についての検索結果の頻度とが一致し、且つ
前記頻度が一致する前記第3のインデックス値の種類数が予め定められた数以上となるように、
前記第3のインデックス値についてのデータが前記データベースに格納されている
システム。

0117

31 第1データ格納部
32 第2データ格納部
33 生成部
34 第3データ格納部
35秘匿化処理部
36 第4データ格納部
37登録処理部
51 入力部
52 第1データ格納部
53 第2データ格納部
54クエリ生成部
55 第3データ格納部
56 送信部
57 受信部
58 第4データ格納部
59 抽出部
60 第5データ格納部
61 出力部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 富士ゼロックス株式会社の「 データ管理システム」が 公開されました。( 2020/09/24)

    【課題】階層構造になっている管理システムにおいて、管理対象データの実体を最上位の装置が全て管理する場合と比較して、管理対象データがユーザの意図しない装置に提供されないシステムを提供する。【解決手段】管... 詳細

  • ソニー株式会社の「 情報処理装置、情報処理方法、およびプログラム」が 公開されました。( 2020/09/24)

    【課題・解決手段】本技術は、複数人のユーザが皆満足できる空間を提供することができるようにする情報処理装置、情報処理方法、およびプログラムに関する。分析部は、複数人のユーザが存在する環境におけるセンシン... 詳細

  • アルテリックス インコーポレイテッドの「 並列処理を使用したハッシュ結合の実行」が 公開されました。( 2020/09/24)

    【課題・解決手段】データレコードは、コンピュータを使用して結合される。第1の複数のデータレコードおよび第2の複数のデータレコード内のデータレコードがハッシュされる。第1の複数のデータレコードおよび第2... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ