(57)【要約】【課題】情報漏洩を抑制した秘匿検索技術を提供する。【解決手段】本データ検索装置は、（Ａ）他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信する受信部と、（Ｂ）グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部と、（Ｃ）データ格納部から、受信された検索要求に含まれるグループの識別子に対応付けられたデータの識別子を読み出す検索部と、（Ｄ）読み出されたデータの識別子を他の装置に送信する送信部とを有する。【選択図】図７
2016062530.tif 000002
【特許請求の範囲】
【請求項１】
他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信する受信部と、
グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部と、
前記データ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられたデータの識別子を読み出す検索部と、
読み出された前記データの識別子を前記他の装置に送信する送信部と、
を有するデータ検索装置。
【請求項２】
前記データ格納部は、前記グループの識別子に対応付けて前記データにおける当該グループに属する各語句の出現位置を暗号化した暗号化位置情報をさらに格納しており、
前記検索部は、前記データ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられた暗号化位置情報をさらに読み出し、
前記送信部は、読み出された前記暗号化位置情報を、前記他の装置にさらに送信する
請求項１記載のデータ検索装置。
【請求項３】
前記データ格納部は、データの識別子に対応付けて暗号化された当該データである暗号化データをさらに格納しており、
前記検索部は、
前記データ格納部から、読み出した前記データの識別子に対応付けられた暗号化データをさらに読み出し、
前記送信部は、
読み出された前記暗号化データを、前記他の装置にさらに送信する
請求項１又は２記載のデータ検索装置。
【請求項４】
前記データ格納部は、データの識別子に対応付けて暗号化された当該データである暗号化データをさらに格納しており、
前記受信部が、前記他の装置から、データの識別子を含むデータ要求を受信すると、
前記検索部は、前記データ格納部から、受信された前記データの識別子に対応付けられた暗号化データを読み出し、
前記送信部は、読み出された前記暗号化データを、前記他の装置に送信する
請求項１又は２記載のデータ検索装置。
【請求項５】
前記データ格納部は、
前記グループの識別子に対応付けて前記データにおける当該グループに属する各語句の出現位置を暗号化した暗号化位置情報をさらに格納しており、
さらに、データの識別子に対応付けて、暗号化された当該データである暗号化データと当該データに含まれる語句が属するグループの識別子とを格納しており、
前記受信部が、ある装置から、あるデータの識別子を含む削除要求を受信すると、
前記検索部は、
前記データ格納部から、受信された前記あるデータの識別子に対応付けられたグループの識別子を読み出し、
前記データ格納部において、受信された前記あるデータの識別子に対応付けられた暗号化データ及びグループの識別子を削除し、
前記データ格納部において、読み出した前記グループの識別子及び前記あるデータの識別子に対応付けられた暗号化位置情報を削除する
請求項１記載のデータ検索装置。
【請求項６】
請求項１乃至５のいずれか１つ記載のデータ検索装置と、
前記データ検索装置を利用する検索要求システムに含まれる前記他の装置と
を有し、
前記他の装置は、出力空間が限定されたハッシュ関数によって、前記検索すべき語句が属するグループの識別子を得る
検索システム。
【請求項７】
前記ハッシュ関数が、順序保存最小完全ハッシュ関数である
請求項６記載の検索システム。
【請求項８】
前記他の装置又は前記検索要求システムにおけるさらに他の装置が、
グループに分類すべき語句の第１のリストと、前記第１のリスト内の各語句に対する指定グループの識別子の第２のリストとから、前記第１のリストに含まれる語句を入力すると前記第２のリストにおいて同一順番の指定グループの識別子を出力するハッシュ関数を生成する生成部
を有する請求項６記載の検索システム。
【請求項９】
前記生成部が、
前記第１のリストを閉路を有さないようにグラフに変換し且つ前記第１のリストに含まれる語句を引数とする変換写像を生成し、
前記グラフのエッジの値を前記第２のリストに基づき変更し、
変更後の前記グラフに基づき、前記変換写像のための変換リストを生成し、
前記変換写像と前記変換リストと前記グループの数ｍとから、前記第１のリストに含まれる語句を引数とした場合における前記変換写像の出力に対応する、前記変換リストにおける値から算出される値の法ｍを出力する前記ハッシュ関数を生成する
請求項８記載の検索システム。
【請求項１０】
他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信し、
グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられたデータの識別子を読み出し、
読み出された前記データの識別子を前記他の装置に送信する
処理をコンピュータに実行させるためのプログラム。
【請求項１１】
他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信し、
グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられたデータの識別子を読み出し、
読み出された前記データの識別子を前記他の装置に送信する
処理を含み、コンピュータが実行するデータ検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを秘匿化したまま検索する技術に関する。
【背景技術】
【０００２】
クラウドサービスなどが提供する外部ストレージに、情報漏洩のリスクを低く抑えながら、機密情報を検索できる形で置くことが期待されている。このようにすれば、自組織内でのストレージ運用を行わずに済み、コスト面などで有利な場合がある。
【０００３】
このような目的のため、ある文献ではおおよそ以下のような構成が採用されている。
【０００４】
まず、説明のための表記について説明しておく。
［ｅ］：ｅが取る各値を要素とする集合又はリスト。例えば、ｅ＝１又は２であれば、［ｅ］は１，２を要素とする集合又はリストとなる。
｛ｋ：ｖk｝：ｋが取る各値から、それに対応付けられた値ｖkへの写像又はハッシュ表。例えば、ｋ＝１又は２で、ｖk：＝ｆ（ｋ）ならば、｛ｋ：ｖk｝は図１に相当する写像又はハッシュ表となる。
Ｅ（ｘ）：ｘを確定的暗号化した値（復号不可能でも良い）。暗号鍵があれば、ｘからＥ（ｘ）を一意に求められる。暗号鍵を知らなくても、どの２つの暗号文の平文が同じか又は異なるのかが分かる。具体的には、ＡＥＳ（Advanced Encryption Standard）による暗号化やＨＭＡＣ（Hash-based Message Authentication Code）などで実現できる。
Ｅr（ｘ）：ｘを復号可能な不確定的暗号化した値。暗号鍵があれば、ｘから異なるＥr（ｘ）を求められ、どのＥr（ｘ）からもｘを求められる。暗号鍵を知らなければ、どの２つの暗号文についても、平文が同じかどうかもわからない。具体的には、乱数をＩＶ（Initialization Vector）にしたＡＥＳによる暗号化などで実現できる。
ｗ：単語又は単語識別子。例えば、「秘匿」や「検索」などである。なお、検索で指定され得るキーワード（語句とも呼ぶ）に対応する。
ｆ：ファイル識別子。例えば、ファイルパスなど。
*ｆ：ファイル識別子ｆに対応付けられたデータ（ファイルの内容）。
ｉf,w：*ｆ中のｗの出現位置集合に含まれる要素。
【０００５】
ある文献では、転置索引のキーを確定的暗号化する。この方式では、例えば次のような２つのテーブルを使う。
索引表：｛Ｅ（ｗ）：｛ｆw：Ｅr（［ｉf,w］）｝｝
データ表：｛ｆ：Ｅr（*ｆ）｝
ここで、ｆwはｗを含むファイルのファイル識別子集合に含まれる要素である。
【０００６】
この索引表が暗号化した転置索引に相当する。これらの表をサーバに保持させておく。暗号鍵を知っているクライアントは、登録したいファイルについて、これらの表を更新する。
【０００７】
例えば、ｆ＝１、*ｆ＝「今日は晴れ晴れ」を登録すると、索引表は図２に示すようになり、データ表は図３に示すようになる。
【０００８】
なお、図２において出現位置（ｉf,w）は何文字目にその単語が出現したのかを表す情報である。例えば、ｆ＝１のｗ＝「今日」は１文字目だけにあるので、［ｉf,w］＝１となる。
【０００９】
さらに、ｆ＝２、*ｆ＝「明日も晴れ」を登録すると、索引用は図４のようになり、データ表は図５のようになる。
【００１０】
このように、ファイルを追加する際、登録済のファイルについてのデータを修正することはない。
【００１１】
クライアントは、検索する場合、検索語ｗに対しＥ（ｗ）を生成して、サーバに送信する。サーバは、索引表からＥ（ｗ）に該当するエントリを読み出し、またデータ表から、読み出された各ｆwについて該当するエントリを読み出し、それらをまとめて［（ｆw,Ｅr（［ｉf,w］），Ｅr（*ｆw））］をクライアントに返信する。クライアントは、受信データを復号して、検索語ｗに該当するファイル識別子、検索語の出現位置、ファイルの内容を得る。
【００１２】
例えば、図４及び図５の状態で、ｗ＝「晴れ」を検索すると、［（ｆw，Ｅr（［ｉf,w］），Ｅr（*ｆw））］＝（１，Ｅr（４，６），Ｅr（今日は晴れ晴れ）），（２，Ｅr（４），Ｅr（明日も晴れ））が得られる。
【００１３】
また、ｗ＝「今日」を検索すると、［（ｆw，Ｅr（［ｉf,w］），Ｅr（*ｆw））］＝（１，Ｅr（１），Ｅr（今日は晴れ晴れ））が得られる。
【００１４】
このように、ファイルを検索する際、検索語を含まないデータへのアクセスは行われない。よって、この方式によれば、データを秘匿化したまま、効率的な単語検索が行われる。
【００１５】
しかし、この方式では、検索単語やファイル中の単語出現割合が、サーバ等に漏れやすいという問題がある。例えば、索引表を参照することで、各ファイルが含む単語種類数が分かってしまう。また、索引表の出現位置集合Ｅr（［ｉf,w］）のサイズは要素数が多いほど大きくなるため、ある程度頻度分布が分かってしまう。そのため、あるファイルの情報が漏れると、他のファイルの情報も漏れやすい。
【００１６】
例えば、ｆ＝１の内容*ｆが「今日も晴れ晴れ」であることをサーバが知ったものとする。このような状況は、例えばクライアントが保存するであろう情報を含むファイルを、サーバがクライアントに送付することなどにより起き得る。このとき、サーバはＥr（１）とＥr（４，６）のサイズを見ることで、Ｅr（１）が「今日」に相当する、すなわちＥ（今日）が「今日」の暗号文だと知ることができる。また、Ｅ（晴れ）が「晴れ」の暗号文だと知ることもできるため、ｆ＝２の内容*ｆが「晴れ」を含むことを知ることもできてしまう。
【００１７】
なお、索引表を、｛Ｅ（ｗ）：Ｅr,w（｛ｆw：Ｅr（［ｉf,w］）｝）｝とする場合もある。すなわち、図４のＥ（ｗ）以外の部分を再度暗号化するものである。そして、クライアントは、検索するときにＥ（ｗ）だけでなく、該当する値（すなわちＥr,w（...））を復号する鍵もサーバに送信する。
【００１８】
しかしながら、このようにしたとしても、多くの単語で検索をした後では、検索単語やファイル中の単語出現割合が、サーバ等に漏れやすいという点は同じである。
【先行技術文献】
【非特許文献】
【００１９】
【非特許文献１】Seny Kamara, Charalampos Papamanthou, and Tom Roeder, "Dynamic Searchable Symmetric Encryption", In Proceedings of the 2012 ACM Conference on Computer and Communications Security (CCS'12), pp. 965-976, 2012
【発明の概要】
【発明が解決しようとする課題】
【００２０】
従って、本発明の目的は、一側面として、情報漏洩を抑制した秘匿検索技術を提供することである。
【課題を解決するための手段】
【００２１】
本発明に係るデータ検索装置は、（Ａ）他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信する受信部と、（Ｂ）グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部と、（Ｃ）データ格納部から、受信された検索要求に含まれるグループの識別子に対応付けられたデータの識別子を読み出す検索部と、（Ｄ）読み出されたデータの識別子を他の装置に送信する送信部とを有する。
【発明の効果】
【００２２】
一側面としては、情報漏洩を抑制した秘匿検索が実現される。
【図面の簡単な説明】
【００２３】
【図１】図１は、表記の一例を説明するための図である。
【図２】図２は、従来例の検索表を説明するための図である。
【図３】図３は、従来例のデータ表を説明するための図である。
【図４】図４は、従来例の検索表を説明するための図である。
【図５】図５は、従来例のデータ表を説明するための図である。
【図６】図６は、実施の形態に係るシステムの概要を示す図である。
【図７】図７は、実施の形態に係るデータ検索装置の機能構成例を示す図である。
【図８】図８は、実施の形態に係る組み合わせ表の一例を示す図である。
【図９】図９は、実施の形態に係る索引表の一例を示す図である。
【図１０】図１０は、実施の形態に係るデータ表の一例を示す図である。
【図１１】図１１は、実施の形態に係る登録装置の機能構成例を示す図である。
【図１２】図１２は、実施の形態に係る検索端末の機能構成例を示す図である。
【図１３】図１３は、登録装置により実行される処理の処理フローを示す図である。
【図１４】図１４は、第１の実施の形態に係る検索処理の処理フローを示す図である。
【図１５】図１５は、データを削除する際の処理の処理フローを示す図である。
【図１６】図１６は、削除処理後のデータ表の例を示す図である。
【図１７】図１７は、削除処理後の索引表の例を示す図である。
【図１８】図１８は、第２の実施の形態に係る検索処理の処理フローを示す図である。
【図１９】図１９は、データ表の他の例を示す図である。
【図２０】図２０は、組み合わせ表のためのハッシュ関数を生成するための処理フローを示す図である。
【図２１】図２１は、マッピング処理の処理フローを示す図である。
【図２２】図２２は、初期的なグラフの例を示す図である。
【図２３】図２３は、生成されたグラフの例を示す図である。
【図２４】図２４は、変更されたグラフの例を示す図である。
【図２５】図２５は、アサイメント処理の処理フローを示す図である。
【図２６】図２６は、トラバース処理の処理フローを示す図である。
【図２７】図２７は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００２４】
［実施の形態１］
図６に、本実施の形態に係るシステムの概要を示す。インターネットなどのネットワーク１００には、クラウド等に設けられるデータ検索装置２００と、クラウド等を利用する企業システム３００とが接続されている
【００２５】
企業システム３００には、データ検索装置２００に対して検索要求を送信する検索端末３５０と、データ検索装置２００に対してデータを登録するための処理を実行する登録装置３１０とが含まれる。
【００２６】
図７にデータ検索装置２００の機能構成例を示す。データ検索装置２００は、登録処理部２０１と、データ格納部２０３と、検索処理部２０５と、受信部２０７と、送信部２０９とを有する。
【００２７】
登録処理部２０１は、企業システム３００からの指示に応じてデータをデータ格納部２０３に登録する処理、登録されたデータをデータ格納部２０３から削除するための処理を実行する。
【００２８】
データ格納部２０３は、以下で述べるような本実施の形態に係るデータ構造を有するデータを格納する。
【００２９】
本実施の形態では、検索に用いられる単語をグループに分ける。図８に示すように、各単語ｗに対して、所属するグループの識別子ｇwが対応付けられる。図８に示すようなテーブルを、組み合わせ表と呼ぶものとする。組み合わせ表は、｛ｗ：ｇw｝と表される。なお、関数表現にする場合には、ｃ（ｗ）＝ｇwと表される。また、組み合わせ表は、暗号化してデータ格納部２０３に格納してもよいし、企業システム３００で管理してもよい。
【００３０】
このような単語のグループを導入するため、索引表及びデータ表を、図９及び図１０に示すような形に変更する。図９の索引表の例では、グループの識別子に対応付けて、当該グループに属する単語を含むファイルの識別子と、当該グループに属する単語のうち当該ファイルに出現する単語とその出現位置とを暗号化した結果である暗号化位置情報とが対応付けられている。すなわち、索引表は、｛ｇ：｛ｆw: Ｅr（ｗ：［ｉf,w］）｝｝と表される。
【００３１】
図１０のデータ表の例では、ファイルの識別子に対応付けて、暗号化されたファイルの内容と、当該ファイルに含まれる単語が属するグループの識別子とが対応付けられている。すなわち、データ表は、｛ｆ：Ｅr（*ｆ），［ｇw］｝と表される。
【００３２】
受信部２０７及び送信部２０９は、検索端末３５０に対する通信インターフェースであって、受信部２０７は、検索端末３５０からの検索要求などを受信すると、検索処理部２０５に出力する。送信部２０９は、受信部２０７などから検索要求などの送信元に対して、検索処理部２０５からのデータを送信する。検索処理部２０５は、データ格納部２０３に対して検索処理を実行する。
【００３３】
次に、登録装置３１０の機能構成例を図１１に示す。登録装置３１０は、入力部３１１と、データ格納部３１３と、生成部３１５と、登録処理部３１７とを有する。
【００３４】
入力部３１１は、企業システム３００の管理者から、検索に用いられる単語のリスト等の入力、データ検索装置２００で検索に供すべきファイルのデータ、削除すべきファイルの識別子などの入力を受け付け、データ格納部３１３に格納する。
【００３５】
生成部３１５は、検索に用いられる単語のリスト等から、組み合わせ表のデータを生成し、データ格納部３１３に格納する。
【００３６】
登録処理部３１７は、登録すべきファイルのデータから、データ検索装置２００に登録すべきエントリのデータを生成し、データ検索装置２００に送信する。また、登録処理部３１７は、削除すべきファイルの識別子を、データ検索装置２００に送信する。
【００３７】
図１２に、検索端末３５０の機能構成例を示す。検索端末３５０は、ディスプレイや印刷装置などの出力装置３７０に接続されており、入力部３５１と、変換部３５２と、データ格納部３５３と、送信部３５４と、受信部３５５と、出力処理部３５６とを有する。なお、出力装置３７０は、他のコンピュータの場合もある。
【００３８】
入力部３５１は、検索者からの検索キーワード（すなわち単語）の入力を受け付け、変換部３５２に出力する。データ格納部３５３は、組み合わせ表のデータ及び暗号キーなどを格納している。変換部３５２は、組み合わせ表から検索キーワードに対応するグループの識別子を生成し、送信部３５４に出力する。
【００３９】
送信部３５４は、グループの識別子を含む検索要求などを、データ検索装置２００に送信する。
【００４０】
受信部３５５は、データ検索装置２００から受信したデータを出力処理部３５６に出力する。出力処理部３５６は、データ検索装置２００から受信したデータから、検索キーワードについてのデータを抽出して、出力装置３７０へ出力する。出力処理部３５６は、データ格納部３５３に格納されている暗号キーを用いて復号処理も行う。
【００４１】
次に、図１３乃至図１７を用いて、図６に示したシステムの処理内容について説明する。
【００４２】
まず、登録装置３１０が、データ検索装置２００に対してデータ（ここではファイル）を登録する際の処理について図１３を用いて説明する。
【００４３】
登録装置３１０の入力部３１１は、ファイルの識別子ｆ及びその内容*ｆの入力を、例えば管理者から受け付け、データ格納部３１３に格納する（図１３：ステップＳ１）。ここでは、ｆ＝１、*ｆ＝「今日は晴れ晴れ」を登録する場合を例に説明する。
【００４４】
そうすると、登録処理部３１７は、ファイルの内容*ｆについての転置索引を生成する（ステップＳ３）。上で述べた例では、転置索引は｛ｗ：｛ｆw：［ｉf,w］｝｝＝（今日：（１：１）），（晴れ：（１：４，６））となる。より具体的には、ファイルに含まれる単語毎に出現位置を抽出して、単語毎にファイルの識別子と出現位置とを対応付けることで得られる。
【００４５】
さらに、登録処理部３１７は、データ格納部３１３に格納されている組み合わせ表を用いて、転置索引を索引表及びデータ表のエントリに変換する（ステップＳ５）。
【００４６】
組み合わせ表ｃより、ｃ（今日）＝ｃ（晴れ）＝１なので、索引表のエントリは｛ｇ：｛ｆw：Ｅr（ｗ：［ｉf,w］）｝｝＝（１：（１：Ｅr（（今日：（１：１）），（晴れ：（１：４，６）））））となる。暗号化キーなどもデータ格納部３１３に格納されているものとする。さらに、データ表のエントリは、｛ｆ：（Ｅr（*ｆ），［ｇw］）｝＝（１：（Ｅr（今日は晴れ晴れ），（１）））となる。ファイルの内容*ｆをデータ格納部３１３から読み出して暗号化する。
【００４７】
そして、登録処理部３１７は、生成したエントリのデータ（索引表及びデータ表のエントリのデータ）を、データ検索装置２００に送信する（ステップＳ７）。
【００４８】
これに対して、データ検索装置２００の登録処理部２０１は、登録装置３１０から登録すべきエントリのデータ（索引表及びデータ表のエントリのデータ）を受信すると、データ格納部２０３における索引表及びデータ表に登録する。
【００４９】
次に、図１４を用いて検索を行う際の処理について説明する。
【００５０】
まず、入力部３５１は、検索者から検索語（検索キーワードとも呼ぶ）ｗsの入力を受け付け、変換部３５２に出力する（図１４：ステップＳ１１）。例えば、ｗs＝「今日」が入力された場合について説明する。
【００５１】
次に、変換部３５２は、データ格納部３５３に格納されている組み合わせ表ｃから、検索語ｗsが属するグループの識別子ｇs＝ｃ（ｗ）を取得し、送信部３５４に出力する（ステップＳ１３）。この例では、ｇs＝ｃ（今日）＝１が得られる。
【００５２】
組み合わせ表ｃのデータについては、例えば、データ検索装置２００にＥr（｛ｗ，ｇw｝）を保持させておき、検索実行前に、データ検索装置２００から取得して、復号しておくようにしても良い。
【００５３】
送信部３５４は、検索語が属するグループの識別子ｇsを含む検索要求を、データ検索装置２００に送信する（ステップＳ１５）。
【００５４】
これに対して、データ検索装置２００の受信部２０７は、グループの識別子ｇsを含む検索要求を、検索端末３５０から受信し、検索処理部２０５に出力する（ステップＳ１７）。
【００５５】
検索処理部２０５は、データ格納部２０３に格納されている索引表から、ｇ＝ｇsとなるエントリ｛ｆw：Ｅr（｛ｗ：［ｉf,w］｝）｝を読み出す（ステップＳ１９）。
【００５６】
ｇs＝１を受信したので、図９から［（ｆw，Ｅr（ｗ：［ｉf,w］））］＝［（１，Ｅr（（今日：１），（晴れ：４，６）））,（２，Ｅｒ（晴れ：４））］が得られる。
【００５７】
さらに、検索処理部２０５は、データ格納部２０３に格納されているデータ表から、ステップＳ１９で得られた各ｆwについてのエントリＥr（*ｆ）を読み出す（ステップＳ２１）。
【００５８】
ｆw＝１，２であるから、データ表（図１０）から［Ｅr（*ｆ）］＝「今日は晴れ晴れ」，「明日も晴れ」を読み出す。
【００５９】
そして、検索処理部２０５は、読み出したデータを送信部２０９に出力する。
【００６０】
送信部２０９は、読み出した［（ｆw，Ｅr（ｗ：［ｉf,w］），Ｅr（*ｆw））］を、検索要求の送信元へ送信する（ステップＳ２３）。なお、検索要求の送信元のデータについては、例えば受信部２０７から取得する。
【００６１】
上で述べた例では、［（ｆw，Ｅr（ｗ：［ｉf,w］），Ｅr（*ｆw））］＝（（１，Ｅr（（今日：１），（晴れ：４，６）），Ｅr（今日は晴れ晴れ））,（２，Ｅｒ（晴れ：４），Ｅr（明日も晴れ）））が得られる。
【００６２】
これに対して、検索端末３５０の受信部３５５は、データ検索装置２００からデータ［（ｆw，Ｅr（ｗ：［ｉf,w］），Ｅr（*ｆw））］を受信し、出力処理部３５６に出力する（ステップＳ２５）。
【００６３】
出力処理部３５６は、受信データのうち暗号化された部分に対して復号処理を実行する（ステップＳ２７）。さらに、出力処理部３５６は、復号したデータ｛ｗ：［ｉf,w］｝のうちｗ≠ｗsとなるエントリのデータを削除する（ステップＳ２９）。
【００６４】
上で述べた例では、（１，（（今日：１），（晴れ：４，６）），（今日は晴れ晴れ）），（２，（晴れ：４），（明日も晴れ））が復号によって得られる。ｗs＝「今日」であるから、（２，（晴れ：４），（明日も晴れ））はｗ≠ｗsとなっているため削除される。
【００６５】
そして、出力処理部３５６は、残余の復号化データを出力装置３７０に出力する（ステップＳ３１）。上の例では、（１，（（今日：１），（晴れ：４，６）），（今日は晴れ晴れ））から、「「今日」は晴れ晴れ」といったように検索語の「今日」を強調するようなデータを生成して、出力装置３７０に出力する。
【００６６】
このようにすれば、検索効率をある程度高く保ったまま、検索単語やファイル中の単語出現割合が、サーバ等に漏れにくくすることができる。検索効率は、単語検索の際その単語を含んでいないファイルも含めた全ファイルから検索を行わずに済む点などから決定されるものである。
【００６７】
たとえ組み合わせ表の一部又は全部が漏洩しても、検索単語やファイル中の単語出現割合は、グループ単位までしかわからない。
【００６８】
例えば、ｆ＝１の内容が「今日は晴れ晴れ」であることをデータ検索装置２００が知っていたとする。さらに、データ検索装置２００は、グループ識別子「１」が、「今日」と「晴れ」を含むことを知ったとする。その場合でも、ｆ＝２の内容が「今日」又は「晴れ」を含むことまでは分かっても、そのどちらを含むか（又は両方含むか）までは分からない。
【００６９】
次に、データ検索装置２００に登録したファイルのデータを削除する際の処理について、図１５乃至図１７を用いて説明する。
【００７０】
登録装置３１０の入力部３１１は、管理者から、削除すべきファイルの識別子ｆdの入力を受け付け、データ格納部３１３に格納する（図１５：ステップＳ４１）。ここでｆ＝１が入力されたものとする。
【００７１】
登録処理部３１７は、データ格納部３１３に格納されたファイルの識別子ｆdを含む削除要求を、データ検索装置２００に送信する（ステップＳ４３）。
【００７２】
これに対して、データ検索装置２００の登録処理部２０１は、登録装置３１０から、ファイルの識別子ｆdを含む削除要求を受信する（ステップＳ４５）。そうすると、登録処理部２０１は、データ格納部２０３に格納されたデータ表から、ｆ＝ｆdのエントリの一部（グループの識別子［ｇd］）を読み出し、ｆ＝ｆdのエントリを削除する（ステップＳ４７）。
【００７３】
ｆ＝１のエントリを削除することになるので、データ表は、図１０の状態から図１６の状態になる。なお、ｇdは１である。
【００７４】
登録処理部２０１は、読み出した各グループの識別子ｇdについて、データ格納部２０３に格納された索引表において、ｇ＝ｇdとなるエントリから、ｆ＝ｆdとなるデータを削除する（ステップＳ４９）。
【００７５】
図９のような索引表の場合、ｇd＝１のエントリから、ｆw＝１についてのデータＥr（今日：１，晴れ：４，６）を削除する。このようにすれば、図９の索引表は、図１７に示すような索引表に変化する。ｆw＝１についてのデータが削除されている。
【００７６】
この処理後、登録処理部２０１は、処理完了を、削除要求の送信元に送信する（ステップＳ５１）。登録装置３１０の登録処理部３１７は、処理完了通知を受信する（ステップＳ５３）。
【００７７】
このように、削除すべきファイルに関連するエントリのみが削除される。
【００７８】
［実施の形態２］
本実施の形態では、検索端末３５０とデータ検索装置２００との間の通信量を削減するために、処理の一部を第１の実施の形態とは変更している。
【００７９】
図１８に本実施の形態に係る処理フローを示す。
【００８０】
まず、入力部３５１は、検索者から検索語（検索キーワードとも呼ぶ）ｗsの入力を受け付け、変換部３５２に出力する（図１８：ステップＳ６１）。ここでも、ｗs＝「今日」が入力された場合について説明する。
【００８１】
次に、変換部３５２は、データ格納部３５３に格納されている組み合わせ表ｃから、検索語ｗsが属するグループの識別子ｇs＝ｃ（ｗ）を取得し、送信部３５４に出力する（ステップＳ６３）。この例では、ｇs＝ｃ（今日）＝１が得られる。
【００８２】
送信部３５４は、検索語が属するグループの識別子ｇsを含む検索要求を、データ検索装置２００に送信する（ステップＳ６５）。
【００８３】
これに対して、データ検索装置２００の受信部２０７は、グループの識別子ｇsを含む検索要求を、検索端末３５０から受信し、検索処理部２０５に出力する（ステップＳ６７）。
【００８４】
検索処理部２０５は、データ格納部２０３に格納されている索引表から、ｇ＝ｇsとなるエントリ｛ｆw：Ｅr（｛ｗ：［ｉf,w］｝）｝を読み出す（ステップＳ６９）。
【００８５】
ｇs＝１を受信したので、図９から［（ｆw，Ｅr（ｗ：［ｉf,w］））］＝（１，Ｅr（（今日：１），（晴れ：４，６）））,（２，Ｅｒ（晴れ：４））が得られる。
【００８６】
ここまでは、第１の実施の形態と同様である。
【００８７】
この後、検索処理部２０５は、読み出したデータを送信部２０９に出力する。そして、送信部２０９は、検索要求の送信元へ送信する（ステップＳ７１）。なお、検索要求の送信元のデータについては、例えば受信部２０７から取得する。
【００８８】
これに対して、検索端末３５０の受信部３５５は、データ検索装置２００からデータ［（ｆw，Ｅr（ｗ：［ｉf,w］））］を受信し、出力処理部３５６に出力する（ステップＳ７３）。
【００８９】
出力処理部３５６は、受信データのうち暗号化された部分を復号する（ステップＳ７５）。そうすると、出力処理部３５６は、復号したデータ｛ｗ：［ｉf,w］｝のうちｗ≠ｗsとなるエントリのデータを削除する（ステップＳ７７）。
【００９０】
上で述べた例では、（１，（（今日：１），（晴れ：４，６））），（２，（晴れ：４））が復号によって得られ、ｗs＝「今日」であるから、（２，（晴れ：４））はｗ≠ｗsとなっているため削除される。残余の復号化データは、（１，（（今日：１），（晴れ：４，６）））である。
【００９１】
よって、出力処理部３５６は、残余の復号化データに係るファイルの識別子ｆwを送信部３５４に出力する。そうすると、送信部３５４は、ファイルの識別子ｆwを含むデータ要求を、データ検索装置２００へ送信する（ステップＳ７９）。
【００９２】
データ検索装置２００の受信部２０７は、ファイルの識別子ｆwを含むデータ要求を受信し、検索処理部２０５に出力する（ステップＳ８１）。
【００９３】
検索処理部２０５は、受け取ったファイルの識別子ｆwについてのエントリのデータ［（ｆw，Ｅr（*ｆw））］をデータ表から読み出し、送信部２０９に出力する。そして、送信部２０９は、読み出したデータを、データ要求の送信元に送信する（ステップＳ８３）。上の例では、ｆw＝１のみがデータ要求に含まれるので、データ表（図１０）から［ｆw，Ｅr（*ｆw）］＝（１，Ｅr（今日は晴れ晴れ））を読み出し、検索端末３５０へ送信する。
【００９４】
これに対して、検索端末３５０の受信部３５５は、データ検索装置２００からデータ［（ｆw，Ｅr（*ｆw））］を受信し、出力処理部３５６に出力する（ステップＳ８５）。
【００９５】
出力処理部３５６は、受信データのうち暗号化された部分に対して復号処理を実行する（ステップＳ８７）。Ｅr（今日は晴れ晴れ）を復号化する。
【００９６】
このように、ｆw＝２についてのＥｒ（明日も晴れ）については、送信されないので、ネットワーク１００の通信量を削減できている。
【００９７】
そして、出力処理部３５６は、残余の復号化データ及びその内容を出力装置３７０に出力する（ステップＳ８９）。上の例では、（１，（（今日：１），（晴れ：４，６）），（今日は晴れ晴れ））から、「「今日」は晴れ晴れ」といったように検索語の「今日」を強調するようなデータを生成して、出力装置３７０に出力する。
【００９８】
［その他の実施の形態］
上で述べた実施の形態では、データ表においてファイルの識別子ｆに対応付けて関連するグループの識別子ｇwを登録するようになっているが、これはファイル削除の際の処理を高速化するためであって、図１９に示すように、ｇwを登録しないようにしても良い。
【００９９】
［組み合わせ表について］
上では説明を分かりやすくするために組み合わせ表については所与のものとして説明した。しかしながら、組み合わせ表は各検索端末３５０に保持されることになるので、サイズが小さい方が好ましい。
【０１００】
組み合わせ表として保持するよりも計算が簡単な写像が望ましい。そのため、例えば以下のような写像ｃ：ｗ→ｇを用いる。
ｃ（ｗ）＝Ｈ（ｓ，ｗ）  ｍｏｄ  ｜Ｇ｜
ここで、Ｈは鍵付ハッシュ関数、ｓは暗号鍵、｜Ｇ｜はグループ総数を表す。
【０１０１】
より具体的には、Ｈには、ＨＭＡＣ（Hash-based Message Authentication Code。但し、値を自然数とみなしたもの）を使う。ｓは、Ｅr（...）で用いる暗号鍵と同一でも良く、ＰＢＫＤＦ２（Password-Based Key Derivation Function 2）などを使ってパスワードから導出しても良い。｜Ｇ｜は、グループの平均要素数をｋとし、全単語数を｜Ｗ｜とすると、｜Ｇ｜≒｜Ｗ｜／ｋとなる。すなわち、この写像ｃにより、各単語は平均要素数ｋのグループに分類される。
【０１０２】
この場合、写像のデータ全体を暗号化してデータ検索装置２００に保持させておき、検索端末３５０が検索時にダウンロードするようにしても良いし、｜Ｇ｜だけをデータ検索装置２００に保持させておき、検索時に検索端末３５０が｜Ｇ｜をダウンロードして写像ｃを再構成するようにしても良い。
【０１０３】
但し、この写像は、ランダムに単語がグループ化されるので、グループサイズに偏りが生ずる可能性がある点（１単語しかないグループができる点）、単語が属するグループを決めることができない点で、好ましくない性質も有する。
【０１０４】
このため、単語群を任意にグループ化する写像が好ましい。そのため、組み合わせ表のための写像に、順序保存最小完全ハッシュ関数（ＯＭＰＨＦ：Order Preserving Minimal Perfect Hash Function）を用いる。
【０１０５】
以下、順序保存最小完全ハッシュ関数を用いる際に、組み合わせ表のための写像の生成方法の一例について説明する。なお、この方法は、Zbigniew J. Czech, George Havas, and Bohdan S. Majewski, "An Optimal Algorithm for Generating Minimal Perfect Hash Functions", Information Processing Letters, Volume 43, Issue 5, pp. 257-264, Oct. 5, 1992 に基づく。
【０１０６】
登録装置３１０の生成部３１５の処理を、図２０乃至図２６を用いて説明する。
【０１０７】
まず、生成部３１５は、単語リストＷ、インデックス変換Ｉ及びノード数ｎを、データ格納部３１３から読み出す（図２０：ステップＳ１０１）。これらのデータは、入力部３１１から既に入力されているものとする。
【０１０８】
例えば、Ｗ＝｛ａｐｅ，ｂｅａｒ，ｃｏｗ，ｄｅａｒ｝、Ｉ＝｛０：０，１：０，２：１，３：１｝、ｎ＝８であるものとして具体的に説明する。なお、インデックス変換Ｉとは、Ｗ内の単語のインデックスからグループの識別子への写像であり、Ｉ：ｉ→ｇwである。例えば、Ｗ［２］であるｃｏｗのグループ識別子が「１」である場合には、Ｉ（２）＝１となる。ノード数ｎは、｜Ｗ｜より大きな値とする。小さいほど結果となる写像ｃのサイズが小さくなるが、生成に時間が掛かるようになる。
【０１０９】
次に、生成部３１５は、変換写像Ｔ1及びＴ2並びにグラフＧを生成するためのマッピング処理を実行する（ステップＳ１０３）。マッピング処理については、図２１を用いて説明する。
【０１１０】
生成部３１５は、ノード数ｎ及び乱数から、変換写像Ｔ1及びＴ2を生成する（ステップＳ１１１）。
【０１１１】
例えば、文字種類数（以下の例では２６）の長さを有し且つ要素に範囲［０，ｎ）内の整数を有するリストＡ1及びＡ2を乱数を使って生成し、さらにｎと互いに素な値ｐ1及びｐ2を適切に決める。そして、以下に示すようなＴ1及びＴ2を生成する。
【数１】
2016062530.tif 000003
【０１１２】
なお、一般的には変換写像Ｔは同じ単語ｗが入力された場合に同じ出力ｊ（０≦ｊ＜ｎ，ｊは整数）を返す写像なら何でも良いが、違う単語が入力された場合にできるだけバラバラな値を返すことが望ましい。Ｔは上で述べた例に限定されず、たとえば空間ｎの値を返すハッシュ関数を採用しても良い。
【０１１３】
また、生成部３１５は、空の無向グラフＧを用意し（ステップＳ１１５）、カウンタｉを０に初期化する（ステップＳ１１７）。
【０１１４】
そして、生成部３１５は、ｉ＜｜Ｗ｜であるか判断する（ステップＳ１１９）。この条件を満たす場合には、生成部３１５は、ノードｖ1にＴ1（Ｗ［ｉ］）を設定し、ノードｖ2にＴ2（Ｗ［ｉ］）を設定する（ステップＳ１２１）。
【０１１５】
さらに、生成部３１５は、グラフＧにおいてノードｖ1とノードｖ2の間に、値ｉのエッジを追加する（ステップＳ１２３）。
【０１１６】
そして、生成部３１５は、カウンタｉを１インクリメントする（ステップＳ１２５）。そして処理はステップＳ１１９に戻る。
【０１１７】
上で述べた定義式から、ｖ1＝Ｔ1（Ｗ［ｉ］）＝Ｔ1（ape）＝３、ｖ2＝Ｔ2（Ｗ［ｉ］）＝Ｔ2（ape）＝７を得る。そして、ノードｖ1とノードｖ2の間に、値ｉ＝０のエッジを追加する。そうすると、図２２に示すようなグラフＧが得られる。値「３」のノードｖ1と値「７」のノードｖ2とが、値「０」のエッジで接続されている。
【０１１８】
ステップＳ１１９の条件を満たさない場合には、Ｗ内の各単語について処理が一旦完了したことになるので、生成部３１５は、グラフＧが閉路（ループ）を有するか否かを判断する（ステップＳ１２７）。
【０１１９】
グラフＧが閉路を有する場合には、処理をやり直すので、処理はステップＳ１１１に戻る。
【０１２０】
一方、グラフＧが閉路を有しない場合には、生成部３１５は、変換写像Ｔ1及びＴ2とグラフＧのデータを、データ格納部３１３に格納する（ステップＳ１２９）。そして処理は呼び出し元の処理に戻る。
【０１２１】
なお、上で述べた例では、図２３に示すようなグラフＧが得られる。グラフＧでは、図２２の状態に対して、値「０」のノードと、値「６」のノードと、値「４」のノードと、値「５」のノードが追加され、値「０」のノードと値「７」のノードとの間に値「３」のエッジと、値「４」のノードと値「５」のノードとの間に値「２」のエッジと、値「７」のノードと値「６」のノードとの間に値「１」のエッジとが追加されている。なお、変換写像Ｔ1及びＴ2については上で示したままである。
【０１２２】
図２０の処理の説明に戻って、生成部３１５は、グラフＧのエッジ値を、インデックス変換Ｉで変換し、データ格納部３１３に格納する（ステップＳ１０５）。上で述べた例では、Ｉ＝｛０：０，１：０，２：１，３：１｝であるから、エッジ値「０」は「０」に変換され、エッジ値「１」は「０」に変換され、エッジ値「２」は「１」に変換され、エッジ値「３」は「１」に変換される。そうすると、図２４に示すような変更後のグラフＧが得られる。
【０１２３】
そして、生成部３１５は、グループ数ｍ及び変換リストｇcを生成するためのアサイメント処理を実行する（ステップＳ１０７）。アサイメント処理については、図２５を用いて説明する。
【０１２４】
生成部３１５は、データ格納部３１３から、ノード数ｎとグラフＧとを読み出す（ステップＳ１３１）。さらに、生成部３１５は、ｍに、（グラフＧのエッジの最大値）＋１を設定する（ステップＳ１３３）。上で述べた例では、エッジの最大値は「１」なのでｍ＝２となる。
【０１２５】
また、生成部３１５は、長さｎを有する変換リストｇc及び訪問フラグｖｉｓｉｔｅｄを用意する（ステップＳ１３５）。なお、変換リストｇc及び訪問フラグｖｉｓｉｔｅｄの各要素の初期値は「０」とする。
【０１２６】
生成部３１５は、グラフＧにおいて未処理のノード値ｖを１つ特定する（ステップＳ１３７）。例えば、小さい順にノード値を特定する。
【０１２７】
そして、生成部３１５は、訪問フラグｖｉｓｉｔｅｄ［ｖ］＝０であるか否かを判断する（ステップＳ１３９）。訪問フラグｖｉｓｉｔｅｄ［ｖ］＝０でない場合には、処理はステップＳ１４３に移行する。
【０１２８】
一方、訪問フラグｖｉｓｉｔｅｄ［ｖ］＝０であれば、生成部３１５は、ｇc、ｖｉｓｉｔｅｄ、Ｇ及びｖを入力とするトラバース処理を実行する（ステップＳ１４１）。トラバース処理については、図２６を用いて説明する。
【０１２９】
まず、生成部３１５は、データ格納部３１３から、変換リストｇc、訪問リストｖｉｓｉｔｅｄ、グループ数ｍ、グラフＧ及びノード値ｖを取得する（ステップＳ１５１）。そして、生成部３１５は、訪問フラグｖｉｓｉｔｅｄ［ｖ］に「１」を設定する（ステップＳ１５３）。
【０１３０】
さらに、生成部３１５は、グラフＧにおいて、値ｖのノードに隣接するノード値ｒを抽出する（ステップＳ１５５）。
【０１３１】
そして、生成部３１５は、未処理のノード値ｒを１つ特定する（ステップＳ１５７）。そうすると、生成部３１５は、訪問フラグｖｉｓｉｔｅｄ［ｒ］＝０であるか否かを判断する（ステップＳ１５９）。この条件を満たす場合には、生成部３１５は、変換フラグｇc［ｒ］に、（グラフＧの（ｖ，ｒ）間のエッジ値）−ｇc［ｖ］  ｍｏｄ  ｍ  を設定する（ステップＳ１６１）。さらに、生成部３１５は、ｇc、ｖｉｓｉｔｅｄ、ｍ、Ｇ及びｒを入力とするトラバース処理を実行する（ステップＳ１６３）。トラバース処理の再帰呼び出しを行う。そして処理はステップＳ１６５に移行する。ステップＳ１５９の条件を満たさない場合も、処理はステップＳ１６５に移行する。
【０１３２】
そして、生成部３１５は、未処理のｒがあるか否かを判断する（ステップＳ１６５）。未処理のｒが存在する場合には処理はステップＳ１５７に戻る。一方、未処理のｒが存在しない場合には、処理は呼び出し元の処理に戻る。
【０１３３】
図２５の処理の説明に戻って、ステップＳ１４１の後又はステップＳ１３９の条件が満たされていない場合には、生成部３１５は、未処理のノード値ｖが存在するか否かを判断する（ステップＳ１４３）。未処理のノード値ｖが存在する場合には、処理はステップＳ１３７に戻る。一方、未処理のノード値ｖが存在しない場合には、生成部３１５は、グループ数ｍ及び変換リストｇcを、データ格納部３１３に格納する（ステップＳ１４５）。そして処理は呼び出し元の処理に戻る。
【０１３４】
ここで上で述べた例についてアサイメント処理の具体例を説明する。
【０１３５】
まず、ノード値ｖ＝０の場合、ｖｉｓｉｔｅｄ［０］＝０であるので、ステップＳ１４１でトラバース処理が実行される。トラバース処理では、ステップＳ１５３においてｖｉｓｉｔｅｄ［０］＝１と設定される。そして、ステップＳ１５５でｒ＝７が得られる。
【０１３６】
ｖｉｓｉｔｅｄ［７］＝０であるから、ステップＳ１６１で、ｇc［７］＝（（０，７）間のエッジ値：１）−ｇc［０］  ｍｏｄ  ｍ  ＝１が設定される。
【０１３７】
そして、ノード値ｒ＝７について、トラバース処理を再帰的に実行する。そうすると、ステップＳ１５３においてｖｉｓｉｔｅｄ［７］＝１と設定される。そして、ステップＳ１５５でｒ＝３，６が得られる。
【０１３８】
まず、ｒ＝３を処理すると、ｇc［３］＝（（３，７）間のエッジ値：０）−ｇc［７］  ｍｏｄ  ｍ  ＝１と設定される。なお、ｒ＝３についてトラバース処理を再帰的に実行することになるが、ノード値「３」の隣接ノードは、ノード値「７」のノードのみであるから、ｖｉｓｉｔｅｄ［３］＝１に設定した後ｒ＝３についての処理は直ぐに終了する。
【０１３９】
また、ｒ＝６を処理すると、ｇc［６］＝（（６，７）間のエッジ値：０）−ｇc［７］  ｍｏｄ  ｍ  ＝１と設定される。なお、ｒ＝６についてトラバース処理を再帰的に実行することになるが、ノード値「６」の隣接ノードは、ノード値「７」のノードのみであるから、ｖｉｓｉｔｅｄ［６］＝１に設定した後ｒ＝６についての処理は直ぐに終了する。
【０１４０】
次に、アサイメント処理に戻って、ｖ＝３についての処理を行うことになる。しかしながら、ｖｉｓｉｔｅｄ［３］＝１に設定されているので、処理は直ぐに終了する。
【０１４１】
さらに、ｖ＝４の処理に移行して、ｖｉｓｉｔｅｄ［４］＝０であるから、ステップＳ１４１でトラバース処理が実行される。トラバース処理では、ステップＳ１５３においてｖｉｓｉｔｅｄ［４］＝１と設定される。そして、ステップＳ１５５でｒ＝５が得られる。
【０１４２】
ｖｉｓｉｔｅｄ［５］＝０であるから、ステップＳ１６１で、ｇc［５］＝（（４，５）間のエッジ値：１）−ｇc［４］  ｍｏｄ  ｍ  ＝１が設定される。
【０１４３】
そして、ノード値ｒ＝５について、トラバース処理を再帰的に実行する。そうすると、ステップＳ１５３においてｖｉｓｉｔｅｄ［５］＝１と設定される。しかし、ノード値ｒ＝５の隣接ノードは、ノード値「４」のノードしかないので、ｖｉｓｉｔｅｄ［５］＝１に設定した後ｒ＝５の処理は直ぐに終了する。
【０１４４】
以上を実行すると、既に訪問フラグｖｉｓｉｔｅｄの要素値は１となったノードしかないので、処理が終了することになる。
【０１４５】
以上のことから、変換リストｇc＝［０，０，０，１，０，１，１，１］となり、ｍ＝２が得られるようになる。
【０１４６】
以上のような処理を行うことで、データ格納部３１３には、グループ数ｍ、変換リストｇc並びに変換写像Ｔ1及びＴ2が格納されることになるので、以下に示すような組み合わせ表に相当するハッシュ関数が得られる。
ｃ（ｗ）＝（ｇc［Ｔ1（ｗ）］＋ｇc［Ｔ2（ｗ）］）  ｍｏｄ  ｜Ｇ｜
【０１４７】
このようなハッシュ関数を用いることによって、図８のような表を用いるよりもデータサイズが圧縮される。また、このようなハッシュ関数は、出力範囲が制限されたハッシュ関数の一例である。
【０１４８】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で述べた機能ブロック構成は一例であって、プログラムモジュール構成とは一致しない場合もある。また、１台のコンピュータで実現するのではなく、複数台のコンピュータで機能を分担する場合もある。
【０１４９】
また、処理フローについても、処理結果が変わらない限り、処理順番を入れ替えたり、複数の処理ステップを並列に実行するようにしても良い。
【０１５０】
なお、検索端末３５０が登録装置３１０の機能を有する場合もある。また、登録装置３１０が検索端末３５０の機能を有する場合もある。検索端末３５０は、企業システム３００に複数設けられる場合もある。
【０１５１】
なお、上で述べた登録装置３１０、検索端末３５０及びデータ検索装置２００は、コンピュータ装置であって、図２７に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１５２】
以上述べた本実施の形態をまとめると以下のようになる。
【０１５３】
本実施の形態に係るデータ検索装置は、（Ａ）他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信する受信部と、（Ｂ）グループの識別子に対応付けて当該グループに属する語句を含むデータ（例えばファイル）の識別子と当該データにおける当該グループに属する各語句の出現位置を暗号化した暗号化位置情報とを格納するデータ格納部と、（Ｃ）データ格納部から、受信された検索要求に含まれるグループの識別子に対応付けられたデータの識別子及び暗号化位置情報を読み出す検索部と、（Ｄ）読み出されたデータの識別子及び暗号化位置情報を他の装置に送信する送信部とを有する。
【０１５４】
データ格納部に上で述べたようなデータを保持して検索を行うようにすれば、データ検索装置では、語句の出現頻度は不明であり、例えあるデータの内容が漏洩しても他のデータにどのような語句が含まれるかまでは漏洩しない。なお、暗号化位置情報については、データ格納部への格納、検索部による検索及び送信部による送信を、任意としてもよい。
【０１５５】
なお、上で述べたデータ格納部は、データの識別子に対応付けて暗号化された当該データである暗号化データをさらに格納している場合もある。この場合、上で述べた検索部は、データ格納部から、読み出したデータの識別子に対応付けられた暗号化データをさらに読み出し、上で述べた送信部は、読み出された暗号化データを、他の装置にさらに送信するようにしても良い。このようにすれば、他の装置とデータ検索装置とのトランザクションは１回で済む。
【０１５６】
なお、上で述べたデータ格納部は、データの識別子に対応付けて暗号化された当該データである暗号化データをさらに格納している場合もある。この場合、上で述べた受信部が、他の装置から、データの識別子を含むデータ要求を受信すると、上で述べた検索部は、データ格納部から、受信されたデータの識別子に対応付けられた暗号化データを読み出し、上で述べた送信部は、読み出された暗号化データを、他の装置に送信するようにしても良い。このようにすれば無駄な暗号化データを送信せずに済む。
【０１５７】
さらに、上で述べたデータ格納部は、データの識別子に対応付けて、さらに当該データに含まれる語句が属するグループの識別子を格納している場合もある。この場合、上で述べた受信部が、ある装置から、あるデータの識別子を含む削除要求を受信すると、上で述べた検索部は、データ格納部から、受信された上記あるデータの識別子に対応付けられたグループの識別子を読み出し、データ格納部において、受信された上記あるデータの識別子に対応付けられた暗号化データ及びグループの識別子を削除し、データ格納部において、読み出したグループの識別子及び上記あるデータの識別子に対応付けられた暗号化位置情報を削除するようにしても良い。このようにすれば、容易にデータ削除が行われる。
【０１５８】
さらに、上で述べたようなデータ検索装置と、データ検索装置を利用する検索要求システムに含まれる他の装置とを有するような検索システムを設けるようにしても良い。そして、上で述べた他の装置は、出力空間が限定されたハッシュ関数によって、検索すべき語句が属するグループの識別子を得るようにしても良い。これによって少ないデータでグループの識別子を得ることができるようになる。
【０１５９】
なお、上で述べたハッシュ関数が、順序保存最小完全ハッシュ関数である場合もある。
【０１６０】
さらに、上記他の装置又は検索要求システムにおけるさらに他の装置が、（Ｅ）グループに分類すべき語句の第１のリストと、第１のリスト内の各語句に対する指定グループの識別子の第２のリストとから、第１のリストに含まれる語句を入力すると第２のリストにおいて同一順番の指定グループの識別子を出力するハッシュ関数を生成する生成部を有するようにしても良い。このようにすれば、順序保存最小完全ハッシュ関数を生成できるようになる。
【０１６１】
より詳しくは、上で述べた生成部が、（ｅ１）第１のリストを閉路を有さないようにグラフに変換し且つ第１のリストに含まれる語句を引数とする変換写像を生成し、（ｅ２）グラフのエッジの値を前記第２のリストに基づき変更し、（ｅ３）変更後のグラフに基づき、変換写像のための変換リストを生成し、（ｅ４）変換写像と変換リストとグループの数ｍとから、第１のリストに含まれる語句を引数とした場合における変換写像の出力に対応する、変換リストにおける値から算出される値の法ｍを出力するハッシュ関数を生成するようにしても良い。
【０１６２】
なお、上で述べた処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。また、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【０１６３】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１６４】
（付記１）
他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信する受信部と、
グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部と、
前記データ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられたデータの識別子を読み出す検索部と、
読み出された前記データの識別子を前記他の装置に送信する送信部と、
を有するデータ検索装置。
【０１６５】
（付記２）
前記データ格納部は、前記グループの識別子に対応付けて前記データにおける当該グループに属する各語句の出現位置を暗号化した暗号化位置情報をさらに格納しており、
前記検索部は、前記データ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられた暗号化位置情報をさらに読み出し、
前記送信部は、読み出された前記暗号化位置情報を、前記他の装置にさらに送信する
付記１記載のデータ検索装置。
【０１６６】
（付記３）
前記データ格納部は、データの識別子に対応付けて暗号化された当該データである暗号化データをさらに格納しており、
前記検索部は、
前記データ格納部から、読み出した前記データの識別子に対応付けられた暗号化データをさらに読み出し、
前記送信部は、
読み出された前記暗号化データを、前記他の装置にさらに送信する
付記１又は２記載のデータ検索装置。
【０１６７】
（付記４）
前記データ格納部は、データの識別子に対応付けて暗号化された当該データである暗号化データをさらに格納しており、
前記受信部が、前記他の装置から、データの識別子を含むデータ要求を受信すると、
前記検索部は、前記データ格納部から、受信された前記データの識別子に対応付けられた暗号化データを読み出し、
前記送信部は、読み出された前記暗号化データを、前記他の装置に送信する
付記１又は２記載のデータ検索装置。
【０１６８】
（付記５）
前記データ格納部は、
前記グループの識別子に対応付けて前記データにおける当該グループに属する各語句の出現位置を暗号化した暗号化位置情報をさらに格納しており、
さらに、データの識別子に対応付けて、暗号化された当該データである暗号化データと当該データに含まれる語句が属するグループの識別子とを格納しており、
前記受信部が、ある装置から、あるデータの識別子を含む削除要求を受信すると、
前記検索部は、
前記データ格納部から、受信された前記あるデータの識別子に対応付けられたグループの識別子を読み出し、
前記データ格納部において、受信された前記あるデータの識別子に対応付けられた暗号化データ及びグループの識別子を削除し、
前記データ格納部において、読み出した前記グループの識別子及び前記あるデータの識別子に対応付けられた暗号化位置情報を削除する
付記１記載のデータ検索装置。
【０１６９】
（付記６）
付記１乃至５のいずれか１つ記載のデータ検索装置と、
前記データ検索装置を利用する検索要求システムに含まれる前記他の装置と
を有し、
前記他の装置は、出力空間が限定されたハッシュ関数によって、前記検索すべき語句が属するグループの識別子を得る
検索システム。
【０１７０】
（付記７）
前記ハッシュ関数が、順序保存最小完全ハッシュ関数である
付記６記載の検索システム。
【０１７１】
（付記８）
前記他の装置又は前記検索要求システムにおけるさらに他の装置が、
グループに分類すべき語句の第１のリストと、前記第１のリスト内の各語句に対する指定グループの識別子の第２のリストとから、前記第１のリストに含まれる語句を入力すると前記第２のリストにおいて同一順番の指定グループの識別子を出力するハッシュ関数を生成する生成部
を有する付記６記載の検索システム。
【０１７２】
（付記９）
前記生成部が、
前記第１のリストを閉路を有さないようにグラフに変換し且つ前記第１のリストに含まれる語句を引数とする変換写像を生成し、
前記グラフのエッジの値を前記第２のリストに基づき変更し、
変更後の前記グラフに基づき、前記変換写像のための変換リストを生成し、
前記変換写像と前記変換リストと前記グループの数ｍとから、前記第１のリストに含まれる語句を引数とした場合における前記変換写像の出力に対応する、前記変換リストにおける値から算出される値の法ｍを出力する前記ハッシュ関数を生成する
付記８記載の検索システム。
【０１７３】
（付記１０）
他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信し、
グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられたデータの識別子を読み出し、
読み出された前記データの識別子を前記他の装置に送信する
処理をコンピュータに実行させるためのプログラム。
【０１７４】
（付記１１）
他の装置から、検索すべき語句が属するグループの識別子を含む検索要求を受信し、
グループの識別子に対応付けて当該グループに属する語句を含むデータの識別子を格納するデータ格納部から、受信された前記検索要求に含まれる前記グループの識別子に対応付けられたデータの識別子を読み出し、
読み出された前記データの識別子を前記他の装置に送信する
処理を含み、コンピュータが実行するデータ検索方法。
【符号の説明】
【０１７５】
２０１  登録処理部
２０３  データ格納部
２０５  検索処理部
２０７  受信部
２０９  送信部
３１５  生成部
【図１】
2016062530.tif 000004
【図２】
2016062530.tif 000005
【図３】
2016062530.tif 000006
【図４】
2016062530.tif 000007
【図５】
2016062530.tif 000008
【図６】
2016062530.tif 000009
【図７】
2016062530.tif 000010
【図８】
2016062530.tif 000011
【図９】
2016062530.tif 000012
【図１０】
2016062530.tif 000013
【図１１】
2016062530.tif 000014
【図１２】
2016062530.tif 000015
【図１３】
2016062530.tif 000016
【図１４】
2016062530.tif 000017
【図１５】
2016062530.tif 000018
【図１６】
2016062530.tif 000019
【図１７】
2016062530.tif 000020
【図１８】
2016062530.tif 000021
【図１９】
2016062530.tif 000022
【図２０】
2016062530.tif 000023
【図２１】
2016062530.tif 000024
【図２２】
2016062530.tif 000025
【図２３】
2016062530.tif 000026
【図２４】
2016062530.tif 000027
【図２５】
2016062530.tif 000028
【図２６】
2016062530.tif 000029
【図２７】
2016062530.tif 000030