説明

データ処理装置及びデータ保管装置及びデータ処理方法及びデータ保管方法及びプログラム

【課題】確率的暗号を利用した秘匿検索を安全に高速化する。
【解決手段】利用者端末装置201は、保管対象の文書情報に対して指定された保管キーワードから一意に得られる乱数値をエントロピー符号化して、保管対象の文書情報に対応付けられるタグがデータセンター装置301で保管される際にタグに付される保管索引値を生成し、保管対象の文書情報とタグと保管索引値をデータセンター装置301に送信する。データセンター装置301では、保管索引値を用いてタグを分類、索引化することができ、確率的暗号を利用した秘匿検索を安全に高速化することができる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、秘匿検索技術に関する。
【背景技術】
【0002】
秘匿検索とは、暗号化データを暗号化したまま検索する技術である。
近年は、クラウドサービスなどのインターネット上でデータを管理する際に、盗聴などの脅威から守るためのセキュリティ技術として注目されている。
【0003】
暗号化したデータを検索する手法は、確定的暗号を利用する方法と、確率的暗号を利用する方法の2種類がある。
確定的暗号を利用する方法は、同一のキーワードを暗号化した際に、同一の暗号文が得られるため、暗号化しないデータベース検索システムと同様の高速化手法を利用することができる(例えば、同一キーワードのタグのグルーピング)。
一方、確率的暗号を利用した方式は、同一のキーワードを暗号化する場合でも、異なる暗号文となる。
したがって、単純に(バイナリデータとして)同一の暗号文をグルーピングする方法などを利用することはできない。
特に、確率的暗号を利用した方法では、安全性証明が付加される場合が多く、暗号文から一切の情報を得られないことが、数学的に証明されている。
そのため、キーワードの(部分)情報を利用する索引化は困難である。
【0004】
次に、確率的暗号を利用したキーワード検索システムを説明する。
【0005】
確率的暗号を利用した秘匿検索は、ユーザ(検索者、登録者)とデータセンター(データ管理者)の間で、以下のようにしてデータ検索を行うことが一般的である。
データ登録者は、文書情報と、それを検索するためのキーワードを鍵として無意味な平文を暗号化したタグデータ(以下、タグという)を登録する。
データセンターは、タグと文書情報を組にして保存する。
検索時には、検索者は検索したいキーワードで作成した検索クエリをデータセンターに送信する。
データセンターは、検索クエリを用いて、保存しているタグとの一致検査を行う。
一致すれば、組で保存されている文書情報を検索者に返却する。
なお、上記において、文書情報とは、検索システムとは別の暗号で暗号化された文書そのものや、文書名、文書を保管しているデータベースの位置情報などである。
また、上記において、検索クエリとは、検索語に対応するキーワードで暗号化されたタグを復号するための復号鍵である。また、検索クエリから検索キーワードを読み取ることはできない。
【0006】
なお、単純な秘匿検索方式としては、例えば非特許文献1に記載されている方式がある。
これは、単一のキーワードにおける秘匿検索を実現したものである。
【0007】
秘匿検索において、データセンターはタグ、検索クエリ、一致検査のいずれにおいても一切の情報も得ることができないため、高いセキュリティが提供される。
しかし、データセンターで行われる一致検査時に、保存されたすべてのタグを検査しなければないため、検索速度が低速であるという課題がある。
この解決法として、特許文献1では、検索履歴を利用して高速化する手法を提案している。また、特許文献2では、ブルームフィルタによって索引木を構成する方法を提案している。
なお、ブルームフィルタとは、フィルタに登録された集合に対して、ある要素が集合に含まれているかを判定するためのフィルタである。
【先行技術文献】
【特許文献】
【0008】
【特許文献1】特開2005−134990号公報
【特許文献2】特開2007−52698号公報
【非特許文献】
【0009】
【非特許文献1】D Boneh、 G.D.Crescenzo、 R.Ostrovsky、Persiano G、 “Public Key Encryption with Keyword Search”、Proceedings of EUROCRYPT ’04、 vol.3027 LNCS、 pp.506−522 (2004)
【発明の概要】
【発明が解決しようとする課題】
【0010】
秘匿検索の最も基本的な方式は非特許文献1である。
この方式はIDベース暗号(以下、IBE:Identity−Based Encryption)を用いた秘匿検索方式である。
IBEは、IDを鍵としてデータの暗号化を行う。
IDはEメールアドレスや住所、名前など、ユーザを一意に識別できるものある。
IDを鍵とするため、誰でもデータの暗号化を行うことができる。
暗号化データは、IDに対応する復号鍵を持つ者(一般的には暗号化に使用したIDの所有者)だけが復号できる。
データ登録者はまず、文書情報に設定するキーワードを、IBEの暗号化機能を利用して、キーワードを鍵(ID)として無意味な平文を暗号化し、文書情報のタグとして文書情報と共にデータセンターに保存する。
タグは暗号化されているため、キーワードに関する情報は漏洩しない。
次に、検索者は検索したいキーワードと、自身の秘密鍵(ユーザ鍵)から検索クエリを生成し、データセンターに送信する。
第三者は検索クエリからも、キーワード情報を知ることはできない。
検索クエリを受信したデータセンターは、保存されているタグに対し、検索クエリを用いてIBEの復号処理を実行する。
無意味な平文が正しく復号できた場合、暗号化に用いたキーワード(文書情報に設定したキーワード)と検索クエリを生成する際に用いたID(検索キーワード)が対応していることを意味するため、「一致」という検索結果のみをデータセンターは知ることができる。
【0011】
特許文献1は、ある検索キーワードで検索した結果をインデックスに保存し、次回以降に同一のキーワードが検索された場合に、高速に検索結果を応答する仕組みである。
特許文献1の方法は、一度検索したキーワードに対しては高速に検索結果を検索者に返却することが可能であるが、一度も検索したことのないキーワードに対しては、データセンターに保存された全てのタグを検索する必要がある。
そのため、膨大なタグを保存するデータベースで、初めて検索されるキーワードに対する検索結果を得るのに、多大な時間を要するという課題がある。
【0012】
特許文献2の方法は、確定的暗号で暗号化したキーワードからブルームフィルタを作成し、索引木を構築する方法である。
この方法は、データセンターに保存されたブルームフィルタ同士のハミング距離を計算する必要があるため、保存されたブルームフィルタ数が増加すると、索引木生成のための計算量が急激に増加するという課題がある。
また、ブルームフィルタの大きさにより、ブルームフィルタに含まれるキーワードの識別には限度がある。
特に偽陽性の問題から、ブルームフィルタに登録される可能性のあるキーワード種類数を考慮して、十分に大きなフィルタを用意する必要がある。
また、ブルームフィルタ1つに対して1つのキーワードが対応している場合(ブルームフィルタに単一のキーワードしか入力しなかった場合)、ブルームフィルタに対応するデータ数を分析することにより、データセンターにキーワード分布に関する情報が漏洩するという課題がある。
【0013】
また、他の類似する索引方式でも、単一のキーワードに対して対応するデータ群を管理するものがほとんどである。
そのため、データセンターはキーワード分布を知ることができ、経験上知られている分布と照合することで、キーワードを推測する「頻度解析」が実施できるという課題がある。
【0014】
本発明では、上記のような課題を解決することを主な目的としており、確率的暗号を利用した秘匿検索を安全に高速化することを目的とする。
【課題を解決するための手段】
【0015】
本発明に係るデータ処理装置は、
複数の暗号化データと、各暗号化データに対応付けられている、暗号化データの検索の際に照合されるタグデータとを保管するデータ保管装置に接続され、
前記データ保管装置での保管の対象となる保管対象データのキーワードを保管キーワードとして指定するキーワード指定部と、
前記保管キーワードから一意に得られる乱数値をエントロピー符号化して、前記保管対象データの暗号化データに対応付けられるタグデータが前記データ保管装置で保管される際に前記タグデータに付される索引値を生成する索引生成部と、
前記保管対象データの暗号化データと前記タグデータと前記索引値とが含まれる保管要求を、前記データ保管装置に対して送信する通信部とを有することを特徴とする。
【発明の効果】
【0016】
本発明によれば、データ処理装置において、保管キーワードから一意に得られる乱数値をエントロピー符号化して、保管対象データの暗号化データに対応付けられるタグデータがデータ保管装置で保管される際にタグデータに付与される索引値を生成するため、データ保管装置において、索引値を用いてタグデータを分類、索引化することができ、確率的暗号を利用した秘匿検索を安全に高速化することができる。
【図面の簡単な説明】
【0017】
【図1】実施の形態1に係る秘匿検索システムの構成例を示す図。
【図2】実施の形態1に係る利用者端末装置の構成例を示す図。
【図3】実施の形態1に係るデータセンター装置の構成例を示す図。
【図4】実施の形態1に係る検索要求のデータ構成例を示す図。
【図5】実施の形態1に係る登録データのデータ構成例を示す図。
【図6】実施の形態1に係るインデックス情報のデータ構成例を示す図。
【図7】実施の形態1に係るデータ保管部のデータ保管の例を示す図。
【図8】実施の形態1に係る利用者端末装置における索引値生成処理を示すフローチャート図。
【図9】実施の形態1に係るデータセンター装置におけるデータ登録処理を示すフローチャート図。
【図10】実施の形態1に係るデータセンター装置における検索処理を示すフローチャート図。
【図11】実施の形態1に係るハッシュ計算の例とハフマン符号化の例を示す図。
【図12】実施の形態1に係る利用者端末装置及びデータセンター装置のハードウェア構成例を示す図。
【発明を実施するための形態】
【0018】
実施の形態1.
本実施の形態では、エントロピー符号を用いてキーワードタグを分類、索引化することで、確率的暗号を利用した秘匿検索を安全に高速化する構成を説明する。
なお、本実施の形態では、エントロピー符号の例として、ハフマン符号を用いて説明を行う。
また、本実施の形態では、ユーザ(検索者、登録者)とデータセンター(データ管理者)の間で、キーワードの鍵付ハッシュ値をハフマン符号化した符号値を索引値とする例を説明する。
【0019】
本実施の形態における大まかな流れは、次の通りである。
まず、データ登録者は、保存したい文書に関する「文書情報」と文書に関連するキーワードから生成した「タグデータ(以下、タグと表記する)」およびキーワードの鍵付ハッシュ値をハフマン符号で符号化した値(索引値)をデータセンターに保存する。
ここで、文書情報とは、検索システムとは別の暗号で暗号化された文書そのものや、文書名、文書を保管しているデータベースの位置情報などである。
文書情報から文書そのものを閲覧することはできない。
タグは文書情報を検索する際に用いる、キーワードを暗号鍵にして無意味な平文(乱数)を暗号化した値である。
データセンターは、タグと文書情報を組にして保存し、索引値を利用してインデックスを構築する。
検索時には、検索者は検索したいキーワードで作成した検索クエリと、登録時と同様の手順で検索キーワードから生成した索引値をデータセンターに送信する。
データセンターは、受信した索引値から検索対象のタグを限定し、検索クエリを用いて、それらのタグと一致検査を行う。
一致すれば、組で保存されている文書情報を検索者に返却する。
なお、以下では、文書情報をデータセンターに保管する際に、保管対象の文書情報に対して指定するキーワードを保管キーワードとも表記し、検索時に指定するキーワードを検索キーワードとも表記する。
また、文書情報及びタグとともにデータセンターで保管される索引値を保管索引値とも表記し、検索時に検索クエリとともにデータセンターに送信する索引値を検索索引値とも表記する。
【0020】
次に、本実施の形態に係る秘匿検索システムの構成を説明する。
図1は、本実施の形態に係る秘匿検索システムの構成例を示す図である。
【0021】
図1において、秘匿検索システム100は、利用者端末装置201、データセンター装置301を備える。
利用者端末装置201は社内LAN(Local Area Network)102に接続されている。
社内LAN102はネットワーク101を介してデータセンター装置301と接続されている。
【0022】
利用者端末装置201は、企業のユーザが利用するPC(Personal Computer)である。
利用者端末装置201は、文書情報とそれを検索するためのタグをデータセンター装置301に保管するとともに、データセンター装置301に蓄積したタグを検索し、データセンター装置301から文書情報を取り出す。
なお、利用者端末装置201は、データ処理装置の例である。
【0023】
データセンター装置301は、企業内で作成された文書情報およびタグを保管する大容量の記憶装置を持つサーバ装置である。
また、利用者端末装置201から送信されるキーワードの暗号文(またはハッシュ値)をエントロピー符号化した値を利用した索引値を持ち、保存されたタグを効率的に検索する機能を備える。
タグは暗号化された状態で保存されるため、データセンター装置301はタグからキーワードを知ることはできない。
なお、データセンター装置301は、データ保管装置の例である。
【0024】
ネットワーク101は、社内LAN102とデータセンター装置301を接続する通信路である。
代表的なネットワーク101の例はインターネットがある。
【0025】
社内LAN102は、企業内に施設された通信路であり、企業内で利用される様々なサーバ装置やPCが接続される。
なお、通信路は専用線や無線、ルータなどで構成される複雑な通信路となる。
【0026】
図2は、利用者端末装置201の構成例を示すブロック図である。
利用者端末装置201は、文書・鍵格納領域202、文書情報管理部203、利用者I/F(Interface)部204、検索クエリ生成部205、タグ生成部206、通信部207、索引生成部208を備える。
【0027】
文書・鍵格納領域202は、データセンター装置301に保存する文書情報を生成するためのオリジナルの文書と、検索クエリの生成のためのユーザ秘密鍵、およびタグ生成のための公開鍵を保存する。
文書情報として、文書を暗号化したデータを利用する場合、文書情報を暗号化するための鍵も保存する。
また、索引生成部208において、利用者I/F204から得られたキーワードを暗号化(またはハッシュ化)するための鍵を保存する。
【0028】
文書情報管理部203は、文書・鍵格納領域202に保存されている文書をもとに、文書情報を生成する。
文書情報からは、文書を閲覧することはできない。
文書情報の例としては、検索システムとは別の暗号で暗号化された文書そのものや、文書名、文書を保管しているデータベースの位置情報などがある。
つまり、文書情報管理部203は、データセンター装置301での保管の対象となる文書(保管対象データ)の暗号化を行って文書情報(保管対象データの暗号化データ)を生成する。
【0029】
利用者I/F部204は、秘匿検索システム100を操作するためのインタフェースである。
検索クエリ生成部205や、タグ生成部206のためのキーワードをユーザから入力する機能を備える。
つまり、利用者I/F部204は、ユーザからの指示に従って、保管キーワードや検索キーワードを指定する。
利用者I/F部204は、キーワード指定部の例である。
【0030】
検索クエリ生成部205は、ユーザが利用者I/F部204を介して入力した検索したいキーワードと、文書・鍵格納領域202に保存されたユーザ鍵から検索クエリを生成する。
つまり、検索クエリ生成部205は、検索クエリとして検索キーワードに対応するタグを復号するための復号鍵を生成する。
検索クエリ生成部205は、検索キーワード秘匿化部の例である。
【0031】
タグ生成部206は、ユーザが利用者I/F部204を介して入力した文書に設定したいキーワードと、文書・鍵格納領域202に保存された公開鍵からタグデータを生成する。
【0032】
通信部207は、データセンター装置301に対して検索を実行するための検索要求(検索クエリと検索索引値)や、データセンター装置301に対して新規に文書情報とタグを保存するための登録データ(文書情報、タグ、保管索引値)を、データセンター装置301に送信するために、社内LAN102に接続するものである。
なお、登録データは、保管要求ともいう。
【0033】
索引生成部208は、利用者I/F部204から受信したキーワードを、文書・鍵格納領域202に保存してある共通鍵(データ登録者と検索者との間の共通鍵)を用いてハッシュ値を計算する(以下、鍵付ハッシュ値という)。
さらに鍵付ハッシュ値に対して、ハフマン符号化を実施して得られた値を索引値として出力する。
つまり、索引生成部208は、保管キーワードから一意に得られる乱数値をハフマン符号化して、タグがデータセンター装置301で保管される際にタグに付される索引値(保管索引値)を生成する。
また、索引生成部208は、検索キーワードから一意に得られる乱数値をハフマン符号化して、データセンター装置301において、検索クエリ(秘匿化された検索キーワード)との照合の対象となるタグを選出するために、データセンター装置301に保管されている保管索引値と比較される索引値(検索索引値)を生成する。
【0034】
図3は、データセンター装置301の構成例を示すブロック図である。
データセンター装置301は、検索要求受信部302、検索処理部303、インデックス記憶部304、データ保管部305、索引分類部306、検索要求回答部307、登録データ受信部308を備える。
【0035】
登録データ受信部308は、利用者端末装置201から登録データ(保管要求)を受信すると、受信した登録データに含まれるタグにタグID(Identification)を付与し、索引分類部306に保管索引値とタグIDを、データ保管部305にタグと文書情報をそれぞれ転送する。
タグIDは、タグを一意に特定することができる識別子である。
なお、登録データ受信部308は、保管要求受信部の例である。
【0036】
索引分類部306は、登録データ受信部308から登録データとして保管索引値とタグIDを受信し、インデックス記憶部304にインデックス情報を追加する機能を持つ。
つまり、索引分類部306は、タグIDと保管索引値とを対応付けるインデックス情報を生成する。
索引分類部306は、インデックス情報生成部の例である。
また、索引分類部306は、後述する検索処理部303から受信した検索索引値から、対応するタグID群をインデックス記憶部304から取り出す機能を持つ。
【0037】
インデックス記憶部304は、保管索引値とタグIDとの対応付けが示されるインデックス情報を保存する機能を持つ。
なお、インデックス記憶部304に保存するインデックス情報では、一つの保管索引値に1つ又は複数のタグIDが対応する。
【0038】
データ保管部305は、登録データ受信部308から受信した文書情報とタグとを対応付けて保存する。
【0039】
検索要求受信部302は、利用者端末装置201から送信された検索要求を受信し、検索処理部303へ転送する。
【0040】
検索処理部303は、検索要求受信部302から検索要求を受信し、検索要求に含まれる検索索引値を索引分類部306に送信し、検索索引値と一致する保管索引値がインデックス記憶部304に存在する場合は、保管索引値から得られた検索対象タグをデータ保管部305から取り出し、検索クエリとの一致検査を行う。
そして、検索処理部303は、一致検査の結果より得られた文書情報を検索要求回答部307を介して利用者端末装置201に送信する。
つまり、検索処理部303は、インデックス記憶部304に記憶されているインデックス情報を参照して、検索要求に含まれる検索索引値と一致する保管索引値と対応付けられているタグIDを1つ以上選出する。
更に、検索処理部303は、選出したタグIDに対応するタグをデータ保管部305から抽出し、抽出したタグごとに、検索要求に含まれる検索クエリ(秘匿化された検索キーワード)との照合を行い、検索キーワードと一致する保管キーワードから生成されているタグを特定し、特定したタグと対応付けられている文書情報をデータ保管部305から抽出する。
検索処理部303は、タグID選出部及びデータ抽出部の例に相当する。
【0041】
検索要求回答部307は、検索処理部303によって検索された文書情報を検索要求元の利用者端末装置201に送信する。
【0042】
図4は、本実施の形態に係る検索要求2001のデータ構造の一例を示す。
【0043】
ここでは、この構成例を検索要求Aとする。
検索要求Aは検索クエリ2002と索引値2004から構成される。
検索クエリ2002は、文書・鍵格納領域202に保存されたユーザ秘密鍵と検索キーワード2003を用いて生成する。
生成された検索クエリ2002からは、検索キーワード2003を知ることはできない。
データセンター装置301は、検索クエリ2002を用いてタグとの一致検査を行い、検索キーワード2003と同じ保管キーワードから生成されたタグを抽出する。
索引値2004は、検索キーワード2003から図8の手順で得られるエントロピー符号値である。
【0044】
図5は、本実施の形態に係る登録データ2301のデータ構造の一例を示す。
【0045】
ここでは、この構成例を登録データAとする。
登録データAは文書情報2302、タグ2303、索引値2305から構成される。
文書情報2302は、例えば、検索システムとは別の暗号で暗号化された文書そのものや、文書名、文書を保管しているデータベースの位置情報などであり、文書情報から文書そのものを閲覧することはできない。
タグ2303は、ユーザによって付与された、文書情報2302に対する保管キーワード2304と文書・鍵格納領域202に保存された公開鍵を鍵として無意味な平文を暗号化したデータである。
索引値2305は、保管キーワード2304から図8の手順で得られるエントロピー符号値である。
【0046】
本実施の形態における索引値は2進数のビット列である。
インデックス情報の構造は索引値から検索対象のタグIDが得られればよい。
本実施の形態では、インデックス情報は、最も単純な転置インデックスの形式を例とするが、2分木やB木を用いた索引木を構成してもよい。
【0047】
図6は、インデックス記憶部304に記憶されるインデックス情報3001のデータ構造の一例を示す。
インデックス情報3001は、索引値3002とタグID3003から構成される。
索引値3002は、文書情報に設定されたキーワードの鍵付ハッシュ値をエントロピー符号化した値(保管索引値)である。
タグID3003は、索引値3002を生成するために用いた保管キーワードのタグに対応するIDである。
検索の際には、検索者が指定した検索索引値と同じ保管索引値と対応付けられているタグID群から得られるタグを一致検査対象とする。
【0048】
図7のようにデータ保管部305は、タグID3051、タグ3052、文書情報3053を列に持つような表の形式でデータを保存する。
タグID3051は、登録データ受信部308によって付与され、インデックス記憶部304に保存されるタグIDと一致する。
【0049】
図8は、本実施の形態における索引値の計算方法を説明するためのフローチャートである。
【0050】
まず、ステップS3061において、索引生成部208は、利用者I/F部204から入力されたキーワードを文書・鍵格納領域202に保存してある鍵を利用してハッシュ値を計算する(本実施の形態ではハッシュ値だが、共通鍵暗号化した値としてもよい)。
このとき、キーワードのハッシュ値を計算する際に用いるハッシュ関数は、同一のキーワードからは同じ値が計算される必要がある。
また、データセンターがキーワードのハッシュ値を計算できないように、データ登録者と、検索者のみ暗号化の鍵を保持することが望ましい。
例えば、暗号化データベースとは無関係の確定的暗号や鍵付ハッシュ関数を利用する。
本実施の形態では、用語の混乱を避け、説明を簡単にするため、キーワードの鍵付ハッシュ値を利用するものとする。
【0051】
次に、ステップS3062において、索引生成部208は、ステップS3061で生成した値に対し、エントロピー符号化を実施する。
本実施の形態では、エントロピー符号としてハフマン符号を用いることとする。
【0052】
次に、ステップS3063において、索引生成部208は、ステップS3062で出力された符号値を、索引値として通信部207に送信する。
エントロピー符号として、ハフマン符号を利用した例を次に示す。
【0053】
キーワードとして、「original」「confirm」「share」を持つ文書情報をそれぞれD(“original”)、D(“confirm”)、D(“share”)とする。
また、それぞれの文書情報に付加されるタグをtag(“original”)、tag(“confirm”)、tag(“share”)とし、そのタグに付与されるタグIDをそれぞれ1、2、3とする。
(タグ、タグID)として表すと、(tag(“original”)、1)、(tag(“confirm”)、2)、(tag(“share”)、3)となる。
【0054】
次に、キーワード「original」「confirm」「share」のハッシュ値を計算する。
例えば、ハッシュアルゴリズムであるSHA256でそれぞれのハッシュ値を取ると、図11(a)に示すような16進数(0〜9、a〜f)64桁の数値が得られる。
SHA256の性質から、このハッシュ値からキーワードを求めることはできない。
【0055】
次に、得られたハッシュ値をハフマン符号化する。
ハフマン符号化を実施すると、図11(b)に示すよう2進数の数値を得ることができる。
このキーワードのハッシュ値をハフマン符号化した2進数を索引値とする。
【0056】
上記ハフマン符号値は、符号化時の変換表がなければハッシュ値を復元することはできない。
本実施の形態では、ハフマン符号の変換表を破棄するため、符号値からハッシュ値を復元することはできない。
また、「original」と「confirm」の索引値が同じであるため、tag(“original”)とtag(“confirm”)はデータセンター装置301のインデックス情報において同一のエントリに保存されることになる。
そのため、単純な索引技術のように、索引値からタグの分布を読み取ることができなくなるため、キーワードの頻度解析を防止することが可能であり、より安全である。
【0057】
次に、秘匿検索システム100の動作について説明する。
図9は、本実施の形態のデータ登録処理の例を説明するフローチャートである。
この処理はデータセンター装置301で実施される処理である。
【0058】
まず、ステップS401において、データセンター装置301は、利用者端末装置201からネットワーク101を経由して送信される登録データAを、登録データ受信部308で受信する。
登録データAは、図5の登録データ2301のようになっている。
登録データ受信部308は、受信したタグ2303にタグIDを付与する。
そして、タグIDと文書情報2302とタグ2303をデータ保管部305に送信し、タグIDと索引値2305を索引分類部306に送信する。
【0059】
次に、ステップS402において、索引分類部306は、登録データ受信部308から受信した索引値が、既にインデックス情報に存在するかを検査するためにインデックス記憶部304を参照する。
【0060】
次に、ステップS403において、索引分類部306は、登録データ受信部308から受信した索引値がインデックス記憶部304に保存されたインデックス情報3001のエントリに含まれるかどうかを検査する。
既に該当するエントリがある場合(該当あり)、ステップS404に進む。
該当するエントリがない場合(該当なし)は、ステップS406に進む。
【0061】
次に、ステップS404において、索引分類部306は、該当するインデックス情報3001のエントリのタグID3003に、登録データ受信部308から受信したタグIDを追加する。
【0062】
次に、ステップS405おいて、データ保管部305が、登録データ受信部308から受信したタグIDと文書情報2302とタグ2303を保存する。
【0063】
次に、ステップS403で、インデックス記憶部304に保存されたインデックス情報3001に登録データ受信部308から受信した索引値が存在しない場合について説明する。
【0064】
ステップS406において、索引分類部306は、登録データ受信部308から受信した索引値と対応するタグIDから新たにエントリを作成し、インデックス情報3001に新しいエントリを追加する。
その後ステップS405を実行する。
【0065】
以上がデータ登録処理の動作の説明である。
次にデータ検索処理の説明をする。
図10は、本実施の形態のデータ検索処理の例を説明するフローチャートである。
【0066】
まず、ステップS501において、データセンター装置301は、利用者端末装置201からネットワーク101を経由して送信される検索要求Aを、検索要求受信部302で受信する。
【0067】
次に、ステップS502において、検索要求受信部302は、検索要求Aを検索処理部303に転送する。
検索処理部303はインデックス情報を参照するために、索引分類部306に検索要求Aに含まれる索引値2004を転送する。
【0068】
次に、ステップS503において、索引分類部306は、インデックス記憶部304に保存されているインデックス情報3001に、検索処理部303から受信した索引値2004が含まれているかどうか検査する。
【0069】
次に、S503の検査で検索要求Aの索引値2004がインデックス記憶部304に存在しなかった場合(該当なし)は、ステップS504において、索引分類部306は検索処理部303に対して検索要求Aに含まれる検索キーワード2003がデータ保管部305に存在しないと通知する。
検索処理部303は、データ保管部305を検索せずに、検索要求回答部307を介して、検索要求のあった利用者端末装置201へ該当データが存在しない旨を回答する。
【0070】
次に、S503の検査の結果、受信した検索要求Aの索引値2004がインデックス記憶部304に存在した場合は(該当あり)、ステップS505において、索引分類部306によってインデックス情報3001から索引値2004に対応するタグID群が返却される。
検索処理部303は、索引値2004に対応するタグID群を用いて、該当するタグをデータ保管部305から参照し、検索要求Aに含まれる検索クエリ2002を用いてキーワード一致検査を行う。
【0071】
次に、S505の検索の結果、検索要求Aに一致するタグがある場合に、検索処理部303は、ステップS504において、該当するタグに対応する文書情報をデータ保管部305から読み出し、検索要求回答部307を介して、検索要求のあった利用者端末装置201へ回答する。
データ保管部305に、検索要求に該当するデータが存在しない場合は、検索処理部303は、検索要求回答部307を介して、検索要求のあった利用者端末装置201へ該当データが存在しない旨を回答する。
【0072】
以上の手順により、暗号化データベースにおいて、暗号化したままデータを検索する方法を安全かつ高速に実施することができる。
【0073】
以上の実施の形態によれば、検索キーワードのハッシュ値のエントロピー符号を利用することで、検索キーワードに関する情報を漏らすことなく、索引を構成することが可能となり、高速な検索を実施できるという効果がある。
【0074】
また、本実施の形態で構成する索引は1つ以上のキーワードに対応する検索タグをグルーピングすることが可能であり、索引からキーワードに対応するデータの分布を秘匿するという効果がある。
【0075】
また、保存されるキーワードの種類の増加に対して、索引を再構成する必要がなく、索引の維持のための計算量を低減するという効果がある。
【0076】
本実施の形態ではキーワードの鍵付ハッシュ値をハフマン符号化した値を索引値として利用する例を開示したが、キーワードから一意に得られる値であればよく、ハッシュ関数や共通鍵暗号(確定的暗号)を利用してもよい。
【0077】
また、本実施の形態では、エントロピー符号としてハフマン符号を利用したが、エントロピー符号であればよく、例えば算術符号であっても良い。
【0078】
また、本実施の形態では、最も単純な転置インデックスの形式を例としたが、索引値から検索対象のタグIDが得られればよく、2分木やB木を用いた索引木を構成しても良い。
【0079】
以上、秘匿検索におけるエントロピー符号を利用した索引手法を開示したが、これは、文書情報のキーワード検索に限らず、任意のデータに対応した検索のためのキーデータ(検索キー)であれば、応用可能なことは明らかである。
つまり、本実施の形態で説明したキーワードとは、単語やセンテンスに限らず、あらゆる形式のキーデータを意味する。
このように、本実施の形態によれば、データを暗号化したままで複数の検索キーを用いた検索を高速に実施することができる。
したがって、画像検索、動画検索、音声検索などへの応用が可能である。
【0080】
以上、本実施の形態では、
検索キーワードおよび、文書情報に設定するキーワードから索引値を生成する索引生成部と、
新規登録対象のキーワードタグと文書情報を受信する登録データ受信部と、
前記登録データ受信部から受信した全てのキーワードタグと文書情報を保存するデータ保管部と、
キーワードから一意に得られる乱数値(暗号文やハッシュ値)をエントロピー符号化した値(索引値)と、その索引値に対応するキーワードタグを示すタグIDとからなるエントリを複数保持するインデックスを記憶するインデックス記憶部と、
検索要求に含まれる索引値が前記インデックス記憶部に存在する場合に、検索対象となるタグIDから該当するタグをデータ保管部から取り出し、キーワードが一致するタグかどうかを検査する検索処理部と、
データ検索時には、索引処理部から受信した索引値から、対応するタグIDをインデックス記憶部から取り出し、データ登録時には登録データ受信部から受信した索引値とタグを用いてインデックス記憶部に索引情報を追加する索引分類部とを備える秘匿検索システムを説明した。
【0081】
また、本実施の形態では、
前記索引生成部は、データ登録時の文書情報に設定するキーワードやデータ検索時の検索キーワードからエントロピー符号値を計算して索引値として出力し、
前記索引分類部は、前記索引生成部によって出力された索引値と、索引値に対応するタグを示すタグIDを保存および参照することを説明した。
【0082】
また、本実施の形態では、
前記索引分類部は、前記索引生成部によって出力された索引値と、索引値に対応するタグを示すタグIDを表形式でインデックス記憶部に保存および参照することを説明した。
【0083】
また、本実施の形態では、
前記索引分類部は、前記索引生成部によって出力された索引値と、索引値に対応するタグを示すタグIDを木形式(2分木、B木など)でインデックス記憶部に保存および参照することを説明した。
【0084】
最後に、本実施の形態に示した利用者端末装置201及びデータセンター装置301のハードウェア構成例について説明する。
図12は、本実施の形態に示す利用者端末装置201及びデータセンター装置301のハードウェア資源の一例を示す図である。
なお、図12の構成は、あくまでも利用者端末装置201及びデータセンター装置301のハードウェア構成の一例を示すものであり、利用者端末装置201及びデータセンター装置301のハードウェア構成は図12に記載の構成に限らず、他の構成であってもよい。
【0085】
図12において、利用者端末装置201及びデータセンター装置301は、プログラムを実行するCPU911(Central Processing Unit、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう)を備えている。
CPU911は、バス912を介して、例えば、ROM(Read Only Memory)913、RAM(Random Access Memory)914、通信ボード915、表示装置901、キーボード902、マウス903、磁気ディスク装置920と接続され、これらのハードウェアデバイスを制御する。
更に、CPU911は、FDD904(Flexible Disk Drive)、コンパクトディスク装置905(CDD)と接続していてもよい。また、磁気ディスク装置920の代わりに、SSD(Solid State Drive)、光ディスク装置、メモリカード(登録商標)読み書き装置などの記憶装置でもよい。
RAM914は、揮発性メモリの一例である。ROM913、FDD904、CDD905、磁気ディスク装置920の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
本実施の形態で説明した文書・鍵格納領域202、インデックス記憶部304及びデータ保管部305は、RAM914、磁気ディスク装置920等により実現される。
通信ボード915、キーボード902、マウス903、FDD904などは、入力装置の一例である。
また、通信ボード915、表示装置901などは、出力装置の一例である。
【0086】
通信ボード915は、図1に示すように、ネットワークに接続されている。
例えば、通信ボード915は、LAN、インターネットの他、WAN(ワイドエリアネットワーク)、SAN(ストレージエリアネットワーク)などに接続されていても構わない。
【0087】
磁気ディスク装置920には、オペレーティングシステム921(OS)、ウィンドウシステム922、プログラム群923、ファイル群924が記憶されている。
プログラム群923のプログラムは、CPU911がオペレーティングシステム921、ウィンドウシステム922を利用しながら実行する。
【0088】
また、RAM914には、CPU911に実行させるオペレーティングシステム921のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、RAM914には、CPU911による処理に必要な各種データが格納される。
【0089】
また、ROM913には、BIOS(Basic Input Output System)プログラムが格納され、磁気ディスク装置920にはブートプログラムが格納されている。
利用者端末装置201及びデータセンター装置301の起動時には、ROM913のBIOSプログラム及び磁気ディスク装置920のブートプログラムが実行され、BIOSプログラム及びブートプログラムによりオペレーティングシステム921が起動される。
【0090】
上記プログラム群923には、本実施の形態の説明において「〜部」(「インデックス記憶部304及びデータ保管部305」以外、以下同様)として説明している機能を実行するプログラムが記憶されている。プログラムは、CPU911により読み出され実行される。
【0091】
ファイル群924には、本実施の形態の説明において、「〜の判断」、「〜の計算」、「〜の暗号化」、「〜の符号化」、「〜の比較」、「〜の照合」、「〜の参照」、「〜の検索」、「〜の抽出」、「〜の検査」、「〜の生成」、「〜の設定」、「〜の登録」、「〜の選択」、「〜の入力」、「〜の受信」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。
ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU911によりメインメモリやキャッシュメモリに読み出される。
そして、読み出された情報やデータや信号値や変数値やパラメータは、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのCPUの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のCPUの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、本実施の形態で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示す。
データや信号値は、RAM914のメモリ、FDD904のフレキシブルディスク、CDD905のコンパクトディスク、磁気ディスク装置920の磁気ディスク、その他光ディスク、ミニディスク、DVD等の記録媒体に記録される。
また、データや信号は、バス912や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【0092】
また、本実施の形態の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。
すなわち、本実施の形態で説明したフローチャートに示すステップ、手順、処理により、本発明に係るデータ処理方法及びデータ保管方法を実現することができる。
また、「〜部」として説明しているものは、ROM913に記憶されたファームウェアで実現されていても構わない。
或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。
ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、DVD等の記録媒体に記憶される。
プログラムはCPU911により読み出され、CPU911により実行される。
すなわち、プログラムは、本実施の形態の「〜部」としてコンピュータを機能させるものである。あるいは、本実施の形態の「〜部」の手順や方法をコンピュータに実行させるものである。
【0093】
このように、本実施の形態に示す利用者端末装置201及びデータセンター装置301は、処理装置たるCPU、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータである。
そして、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【符号の説明】
【0094】
100 秘匿検索システム、101 ネットワーク、102 社内LAN、201 利用者端末装置、202 文書・鍵格納領域、203 文書情報管理部、204 利用者I/F部、205 検索クエリ生成部、206 タグ生成部、207 通信部、208 索引生成部、301 データセンター装置、302 検索要求受信部、303 検索処理部、304 インデックス記憶部、305 データ保管部、306 索引分類部、307 検索要求回答部、308 登録データ受信部。

【特許請求の範囲】
【請求項1】
複数の暗号化データと、各暗号化データに対応付けられている、暗号化データの検索の際に照合されるタグデータとを保管するデータ保管装置に接続され、
前記データ保管装置での保管の対象となる保管対象データのキーワードを保管キーワードとして指定するキーワード指定部と、
前記保管キーワードから一意に得られる乱数値をエントロピー符号化して、前記保管対象データの暗号化データに対応付けられるタグデータが前記データ保管装置で保管される際に前記タグデータに付される索引値を生成する索引生成部と、
前記保管対象データの暗号化データと前記タグデータと前記索引値とが含まれる保管要求を、前記データ保管装置に対して送信する通信部とを有することを特徴とするデータ処理装置。
【請求項2】
前記データ処理装置は、
秘匿化された検索キーワードと、前記秘匿化された検索キーワードとの照合の対象となるタグデータの索引値とが含まれる検索要求を受信した際に、前記検索要求に含まれる索引値と一致する索引値と対応付けられているタグデータを抽出し、抽出したタグデータと前記秘匿化された検索キーワードとを照合して暗号化データを検索するデータ保管装置に接続され、
前記索引生成部は、
前記データ保管装置において前記検索要求に含まれる索引値と比較される索引値を生成することを特徴とする請求項1に記載のデータ処理装置。
【請求項3】
前記データ処理装置は、
暗号化データとタグデータと索引値とを対応付けて保管するデータ保管装置に接続され、
前記キーワード指定部は、
前記データ保管装置に暗号化データの検索を行わせる検索キーワードを指定し、
前記データ処理装置は、更に、
前記検索キーワードを秘匿化する検索キーワード秘匿化部を有し、
前記索引生成部は、
前記検索キーワードから一意に得られる乱数値をエントロピー符号化して、前記データ保管装置において、秘匿化された検索キーワードとの照合の対象となるタグデータを選出するために、前記データ保管装置に保管されている索引値と比較される索引値を生成し、
前記通信部は、
前記秘匿化された検索キーワードと前記索引値とが含まれる検索要求を、前記データ保管装置に対して送信することを特徴とする請求項1又は2に記載のデータ処理装置。
【請求項4】
前記索引生成部は、
前記保管キーワードのハッシュ値を算出し、算出したハッシュ値をハフマン符号化して、前記保管対象データの暗号化データに対応付けられるタグデータが前記データ保管装置で保管される際に前記タグデータに付される索引値を生成し、
前記検索キーワードのハッシュ値を算出し、算出したハッシュ値をハフマン符号化して、前記データ保管装置において、前記秘匿化された検索キーワードとの照合の対象となるタグデータを選出するために、前記データ保管装置に保管されている索引値と比較される索引値を生成することを特徴とする請求項3に記載のデータ処理装置。
【請求項5】
データ処理装置に接続され、前記データ処理装置から送信された暗号化データを保管するデータ保管装置であって、
前記データ処理装置から、保管対象の暗号化データと、暗号化データの検索の際に照合されるタグデータと、前記保管対象の暗号化データに指定された保管キーワードから一意に得られる乱数値をエントロピー符号化して得られた保管索引値とが含まれる保管要求を受信し、受信した前記保管要求に含まれるタグデータのID(Identification)をタグIDとして設定する保管要求受信部と、
前記保管要求受信部により設定されたタグIDと前記保管要求に含まれる保管索引値とを対応付けるインデックス情報を生成するインデックス情報生成部と、
前記インデックス情報生成部により生成されたインデックス情報を記憶するインデックス記憶部と、
前記保管要求に含まれる保管対象の暗号化データと、前記保管要求に含まれるタグデータとを対応付けて保管するデータ保管部とを有することを特徴とするデータ保管装置。
【請求項6】
前記インデックス情報生成部は、
前記保管要求に含まれる保管索引値と同じ保管索引値が記述されている既存のインデックス情報が前記インデックス記憶部に記憶されている場合に、既存のインデックス情報において同じ保管検索値と対応付けられている他のタグIDとともに、前記保管要求に含まれるタグデータのタグIDを既存のインデックス情報において前記保管索引値と対応付けることを特徴とする請求項5に記載のデータ保管装置。
【請求項7】
前記データ保管装置は、
複数のデータ処理装置に接続されており、
前記データ保管装置は、更に、
前記複数のデータ処理装置のうち暗号化データの検索を要求するデータ処理装置から、秘匿化された検索キーワードと、秘匿化前の検索キーワードから一意に得られる乱数値をエントロピー符号化して得られた検索索引値とが含まれる検索要求を受信する検索要求受信部と、
前記インデックス記憶部に記憶されているインデックス情報を参照して、前記検索要求に含まれる検索索引値と一致する保管索引値と対応付けられているタグIDを1つ以上選出するタグID選出部と、
前記タグID選出部により選出されたタグIDに対応するタグデータを前記データ保管部から抽出し、抽出したタグデータごとに、前記検索要求に含まれる秘匿化された検索キーワードとの照合を行い、検索キーワードと一致する保管キーワードから生成されているタグデータを特定し、特定したタグデータと対応付けられている暗号化データを前記データ保管部から抽出するデータ抽出部とを有することを特徴とする請求項5又は6に記載のデータ保管装置。
【請求項8】
前記インデックス情報生成部は、
タグIDと保管索引値とを表形式で対応付けるインデックス情報を生成することを特徴とする請求項5〜7のいずれかに記載のデータ保管装置。
【請求項9】
前記インデックス情報生成部は、
タグIDと保管索引値とを木形式で対応付けるインデックス情報を生成することを特徴とする請求項5〜8のいずれかに記載のデータ保管装置。
【請求項10】
複数の暗号化データと、各暗号化データに対応付けられている、暗号化データの検索の際に照合されるタグデータとを保管するデータ保管装置に接続されているコンピュータが行うデータ処理方法であって、
前記コンピュータが、前記データ保管装置での保管の対象となる保管対象データのキーワードを保管キーワードとして指定するキーワード指定ステップと、
前記コンピュータが、前記保管キーワードから一意に得られる乱数値をエントロピー符号化して、前記保管対象データの暗号化データに対応付けられるタグデータが前記データ保管装置で保管される際に前記タグデータに付される索引値を生成する索引生成ステップと、
前記コンピュータが、前記保管対象データの暗号化データと前記タグデータと前記索引値とが含まれる保管要求を、前記データ保管装置に対して送信する通信ステップとを有することを特徴とするデータ処理方法。
【請求項11】
データ処理装置に接続され、前記データ処理装置から送信された暗号化データを保管するコンピュータが行うデータ保管方法であって、
前記コンピュータが、前記データ処理装置から、保管対象の暗号化データと、暗号化データの検索の際に照合されるタグデータと、前記保管対象の暗号化データに指定された保管キーワードから一意に得られる乱数値をエントロピー符号化して得られた保管索引値とが含まれる保管要求を受信し、受信した前記保管要求に含まれるタグデータのID(Identification)をタグIDとして設定する保管要求受信ステップと、
前記コンピュータが、前記保管要求受信ステップにより設定されたタグIDと前記保管要求に含まれる保管索引値とを対応付けるインデックス情報を生成するインデックス情報生成ステップと、
前記コンピュータが、前記インデックス情報生成ステップにより生成されたインデックス情報を記憶するインデックス記憶ステップと、
前記コンピュータが、前記保管要求に含まれる保管対象の暗号化データと、前記保管要求に含まれるタグデータとを対応付けて保管するデータ保管ステップとを有することを特徴とするデータ保管方法。
【請求項12】
複数の暗号化データと、各暗号化データに対応付けられている、暗号化データの検索の際に照合されるタグデータとを保管するデータ保管装置に接続されているコンピュータに、
前記データ保管装置での保管の対象となる保管対象データのキーワードを保管キーワードとして指定するキーワード指定ステップと、
前記保管キーワードから一意に得られる乱数値をエントロピー符号化して、前記保管対象データの暗号化データに対応付けられるタグデータが前記データ保管装置で保管される際に前記タグデータに付される索引値を生成する索引生成ステップと、
前記保管対象データの暗号化データと前記タグデータと前記索引値とが含まれる保管要求を、前記データ保管装置に対して送信する通信ステップとを実行させることを特徴とするプログラム。
【請求項13】
データ処理装置に接続され、前記データ処理装置から送信された暗号化データを保管するコンピュータに、
前記データ処理装置から、保管対象の暗号化データと、暗号化データの検索の際に照合されるタグデータと、前記保管対象の暗号化データに指定された保管キーワードから一意に得られる乱数値をエントロピー符号化して得られた保管索引値とが含まれる保管要求を受信し、受信した前記保管要求に含まれるタグデータのID(Identification)をタグIDとして設定する保管要求受信ステップと、
前記保管要求受信ステップにより設定されたタグIDと前記保管要求に含まれる保管索引値とを対応付けるインデックス情報を生成するインデックス情報生成ステップと、
前記インデックス情報生成ステップにより生成されたインデックス情報を記憶するインデックス記憶ステップと、
前記保管要求に含まれる保管対象の暗号化データと、前記保管要求に含まれるタグデータとを対応付けて保管するデータ保管ステップとを実行させることを特徴とするプログラム。

【図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

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate


【公開番号】特開2012−164031(P2012−164031A)
【公開日】平成24年8月30日(2012.8.30)
【国際特許分類】
【出願番号】特願2011−22147(P2011−22147)
【出願日】平成23年2月3日(2011.2.3)
【出願人】(000006013)三菱電機株式会社 (33,312)
【Fターム(参考)】