データ検索システム、情報処理装置、データ検索方法、及び、プログラム。
【課題】プライバシ機能を強化した、データ検索システム、情報処理装置、データ検索方法及びプログラムを提供する。
【解決手段】データ検索システム１００において、データ検索装置１０１は、データベースのデータのインデックスを利用者用端末１０３に公開する。利用者用端末１０３は、利用者によって選択されたインデックスに基づいて暗号化鍵・復号化鍵、インデックス削除鍵を生成する。データ検索装置１０１は、暗号化鍵に基づいて、データベースのデータを暗号化し、暗号化データを中間サーバ１０２に送信する。複数台の中間サーバ１０２は、協働して暗号化データをインデックス削除鍵に基づいて削除する。最終的に、利用者用端末１０３には、利用者が選択したデータのみ転送される。利用者用端末１０３は、暗号化データを復号化する。
【解決手段】データ検索システム１００において、データ検索装置１０１は、データベースのデータのインデックスを利用者用端末１０３に公開する。利用者用端末１０３は、利用者によって選択されたインデックスに基づいて暗号化鍵・復号化鍵、インデックス削除鍵を生成する。データ検索装置１０１は、暗号化鍵に基づいて、データベースのデータを暗号化し、暗号化データを中間サーバ１０２に送信する。複数台の中間サーバ１０２は、協働して暗号化データをインデックス削除鍵に基づいて削除する。最終的に、利用者用端末１０３には、利用者が選択したデータのみ転送される。利用者用端末１０３は、暗号化データを復号化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ検索システム、情報処理装置、データ検索方法、及び、プログラムに関する。
【背景技術】
【０００２】
近年、様々なデータが電子化されるようになっている。その電子化されたデータはデータベースに蓄積され、管理される。
また、これらの電子化されたデータをネットワークを介して不特定多数の人や組織に提供するシステムが多く利用されるようになった。例えば、新薬開発などへの利用を目的に、医療・診療情報をデータベースに蓄積しておき、これを外部に提供するといったシステムがある。このシステムの利用者は、データベースに蓄積されたデータの中から所望のデータを検索し、閲覧することができる。
【０００３】
そして、このようなデータの中には、プライバシ情報が含まれる場合も多い。例えば、新薬を開発している企業（システムの利用者）は、データベースのデータを検索した検索内容が、他の競合する企業等に知られた場合、大きな不利益を被る可能性がある。このような不利益を考慮すると、データベースのデータを検索した検索内容は、プライバシ情報として秘匿されなければならない。
【０００４】
そこで、検索内容（プライバシ情報）を秘匿しながら、所望のデータを外部に提供するデータ検索システムが要求されるようになった。例えば、特許文献１には、データベース内のデータを秘匿化（暗号化）し、秘匿化（暗号化）したデータを外部に提供する方法（ＳＰＩＲ（Symmetrically Private Information Retrieval））が開示されている。具体的には、データ検索システムは、利用者用端末等を用いてシステムの利用者によって入力された検索内容を暗号化し、暗号化した検索内容に従って、データベースにアクセスする。また、データ検索システムは、データベースに格納された全てのデータを暗号化し、暗号化したデータを利用者に提供するために、利用者用端末等へ送信する。さらに、データ検索システムは、送信したデータのうち、検索内容に対応したデータのみを復号する。
【特許文献１】特開２００３−２９６３３号公報
【０００５】
現在の計算機では、検索内容以外の復号鍵を持たない暗号化データを解読することは、計算機の処理速度が遅いために非常に困難であると考えられている。そのため、特許文献１に開示されるデータ検索システムは、データベースに格納された全ての暗号化データを利用者用端末等へ送信したとしても、プライバシ情報を秘匿するのに十分なシステムとされている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来のデータ検索システムは、将来的には計算機の処理速度の向上等により、検索内容以外の復号鍵を持たない暗号化データが解読される可能性が高くなり、プライバシが侵害される虞がある。
【０００７】
本発明は、上記実状に鑑みてなされたものであり、プライバシの侵害を防御するためのプライバシ保護機能を強化したデータ検索システム、情報処理装置、データ検索方法、及び、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の第１の観点に係るデータ検索システムは、第１の情報処理装置と、第２の情報処理装置と、第３の情報処理装置と、から構成されるデータ検索システムであって、
前記第１の情報処理装置は、
情報を記憶するデータベースと、
前記データベースに記憶されている情報のインデックスを前記第２の情報処理装置に公開するインデックス公開手段と、
を備え、
前記第２の情報処理装置は、
前記インデックスを取得し、取得したインデックスの少なくとも一部に対応する暗号鍵及び復号鍵を生成する暗号鍵・復号鍵生成手段と、
前記第３の情報処理装置が前記情報を削除するために必要な削除鍵を生成する削除鍵生成手段と、
前記暗号鍵・復号鍵生成手段が生成した暗号鍵を前記第１の情報処理装置に送信する暗号鍵送信手段と、
前記削除鍵生成手段が生成した削除鍵を前記第２の情報処理装置に送信する削除鍵送信手段と、
を備え、
前記第１の情報処理装置は、さらに、
前記暗号鍵送信手段が送信した暗号鍵を受信し、受信した暗号鍵に基づいて、前記データベースに記憶される情報を暗号化する暗号化手段と、
前記暗号化手段が暗号化した暗号化情報を前記第３の情報処理装置に送信する暗号化情報送信手段と、
を備え、
前記第３の情報処理装置は、
前記暗号化情報送信手段が送信した暗号化情報を受信する暗号化情報受信手段と、
前記削除鍵送信手段が送信した削除鍵を受信する削除鍵受信手段と、
前記削除鍵受信手段が受信した削除鍵に基づいて、前記暗号化情報受信手段が受信した暗号化情報の所定数の情報を削除する情報削除手段と、
前記情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信する入れ替え情報送信手段と、
を備え、
前記第２の情報処置装置は、さらに、
前記入れ替え情報送信手段が送信した情報を受信し、前記暗号鍵・復号鍵生成手段が生成した復号鍵に基づいて、受信した前記情報を復号化する復号化手段と、
を備える、
ことを特徴とする。
【０００９】
また、前記データ検索システムにおいて、
前記第３の情報処理装置は、複数の装置から構成され、
前記情報順序入れ替え手段が情報を入れ替えた後、前記情報の残数が前記暗号鍵・復号鍵生成手段が取得したインデックスの少なくとも一部に対応するインデックス数と等しいか否かを判別する残数判別手段と、
前記残数判別手段が、前記情報の残数が前記インデックス数と等しいと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信し、前記残数判別手段が、前記情報の残数が前記インデックス数と等しくないと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を別の前記第３の情報処理装置に送信する第２の入れ替え情報送信手段と、
を備えることを特徴とするようにしてもよい。
【００１０】
上記目的を達成するため、本発明の第２の観点に係る情報処理装置は
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手段と、
前記削除鍵記憶手段が記憶する削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手段と、
前記暗号化情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
を備えることを特徴とする。
【００１１】
上記目的を達成するため、本発明の第３の観点に係るデータ検索方法は、
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶ステップと、
前記削除鍵記憶ステップで記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除ステップと、
前記暗号化情報削除ステップで情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替えステップと、
を備えることを特徴とする。
【００１２】
上記目的を達成するため、本発明の第４の観点に係るプログラムは、
コンピュータに、
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手順と、
前記削除鍵記憶手順で記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手順と、
前記暗号化情報削除手順で情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手順と、
を実行させる。
【発明の効果】
【００１３】
本発明のシステムによれば、プライバシの侵害を防御するためのプライバシ保護機能を強化して、データベースに蓄積したデータから所望のデータを検索することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施形態に係るデータ検索システム１００を説明する。
【００１５】
本実施形態に係るデータ検索システム１００は、図１に示すように、データ検索装置１０１と、複数台の中間サーバ１０２と、利用者用端末１０３と、から構成される。また、中間サーバ１０２は、単一のサーバで構成してもよい。データ検索装置１０１、各中間サーバ１０２、利用者用端末１０３は、それぞれネットワーク１０４を介して接続される。このような構成からなるデータ検索システム１００は、データ検索装置１０１内のデータベースに格納されたデータのうち、利用者用端末１０３からの要求に応じた所望のデータを利用者に提供するシステムである。
【００１６】
ここで、ネットワーク１０４は、一般的な通信手段を用いることが可能である。本実施形態において、一般的に使用されているＴＣＰ／ＩＰ（トランスミッション・コントロール・プロトコル／インターネット・プロトコル）が使用される。なお、他のプロトコルが使用されてもよい。また、ネットワーク１０４は、ローカル・エリア・ネットワークでも、ワイド・エリア・ネットワークでもよい。バーチャル・プライベート・ネットワーク（ＶＰＮ）やワイヤレス接続のような通信手段も同じように使用可能である。
【００１７】
データ検索装置１０１は、図２（Ａ）に示すように、制御部２０１、ＲＡＭ（Random Access Memory）２０２、ＲＯＭ（Read Only Memory）２０３、データベース２０４、通信部２０５及びシステムバス２０６を含む。データ検索装置１０１は、データベース２０４にデータを格納し、通信部２０５を介して、利用者用端末１０３からの要求に応じてデータを利用者用端末１０３へ送信する装置である。
なお、データ検索装置１０１は、病院やオフィス内に配置されることはもちろん、ネットワーク１０４を介して利用者用端末１０３等に接続できればどこに配置されてもよい。
【００１８】
データベース２０４は、利用者用端末１０３に送信するデータを格納するデータベースであり、例えば、図３に示すように、データを識別するためのインデックス番号（例えば、数字、等）、データ種別（例えば、性別、年齢、等）、データ内容（例えば、病歴、等）等を対応づけて記憶する。
【００１９】
制御部２０１は、ＣＰＵ（Central Processing Unit）等の演算処理装置から構成され、データ検索装置１０１の全体の制御を行う。また、制御部２０１は、ＲＯＭ２０３に格納されるプログラムを読み出して、プログラムに基づいて所定の処理を実行する。例えばデータベース２０４に格納されたデータを暗号化する処理を行う。制御部２０１が実行する処理の詳細については後述する。
【００２０】
ＲＡＭ２０２は、制御部２０１が所定の処理（例えば、暗号化処理、等）を実行するために読み出したプログラムや、制御部２０１が当該プログラムを実行するために必要なデータを格納する揮発性メモリである。
【００２１】
ＲＯＭ２０３は、制御部２０１が所定の処理を実行するためのプログラム等を予め格納する不揮発性メモリである。制御部２０１は、ＲＯＭ２０３から必要に応じてプログラム等を読み出して、ＲＡＭ２０２に展開し、当該プログラム等に基づいて所定の処理を実行する。具体的には、ＲＯＭ２０３に格納するプログラムは、図２（Ｂ）に示すように、データを暗号化するデータ暗号化プログラム２１０、暗号化データを送信するための送信プログラム２１１等である。
【００２２】
データ暗号化プログラム２１０は、データベース２０４のインデックス（公開データ）及びデータ内容をそれぞれ暗号化するためのプログラムである。暗号化の具体的な処理については、後述する。
【００２３】
送信プログラム２１１は、データ暗号化プログラム２１０で暗号化したデータを、中間サーバ（１）１０２へ送信するためのプログラムである。具体的な処理については、後述する。
【００２４】
通信部２０５は、ＮＩＣ（Network Interface Card）等から構成され、ネットワーク１０４に接続するためのインタフェースを備え、ネットワーク１０４との間で、ＴＣＰ／ＩＰプロトコルに基づく通信を行う。通信部２０５は、例えば、モデム装置や赤外線通信装置等を含んでいてもよい。
【００２５】
システムバス２０６は、制御部２０１、ＲＡＭ２０２、ＲＯＭ２０３、データベース２０４及び通信部２０５の間で命令やデータを転送するための伝送経路である。
【００２６】
このように、データ検索装置１０１は、一般的に普及しているコンピュータ等を用いて構成することができる。
【００２７】
次に、図１に示すネットワーク１０４に接続される中間サーバ１０２について説明する。中間サーバ１０２は、複数台（例えば、Ｎ台）で構成される。
各中間サーバ１０２に、例えば、所定のＩＰアドレスを割り振り、データ検索装置１０１及び各中間サーバ１０２は、ＩＰアドレスを指定して所望の中間サーバ１０２にネットワーク１０４を介してアクセスする。
具体的には、中間サーバ（１）２０１にＩＰアドレス：１９２．１６８．０．１、中間サーバ（２）２０１にＩＰアドレス：１９２．１６８．０．２、…、中間サーバ（Ｎ）２０１にＩＰアドレス：１９２．１６８．０．Ｎ等といった静的アドレスを割り当てる。データ検索装置１０１及び各中間サーバ１０２は、この静的アドレスを指定して送信先の中間サーバ１０２を決定し、順次、暗号化データを転送する。また、各中間サーバ１０２は、暗号化データに対して、削除・シャッフル処理を施してから、それらデータを転送する。削除・シャッフル処理等の具体的な内容の詳細については後述する。
また、各中間サーバ１０２に、静的なＩＰアドレスを割り当てる必要はなく、ＤＮＳ（Domain Name Sever）やＤＨＣＰ（Dynamic Host Configuration Protocol）サーバ等を協働して利用し、動的なＩＰアドレスを割り当てるようにしてもよい。
【００２８】
各中間サーバ１０２は、それぞれ同様の構成からなり、図４（Ａ）に示すように、制御部４０１、ＲＡＭ（Random Access Memory）４０２、ＲＯＭ（Read Only Memory）４０３、記憶部４０４、通信部４０５及びシステムバス４０６を含む。
【００２９】
制御部４０１は、ＣＰＵ（Central Processing Unit）等の演算処理装置から構成され、中間サーバ１０２の全体の制御を行う。また、制御部４０１は、ＲＯＭ４０３に格納されるプログラムを読み出して、プログラムに基づいて所定の処理を実行する。例えば、記憶部４０４に格納された暗号化データに対して削除・シャッフル処理、転送処理等を行う。
【００３０】
ＲＡＭ４０２は、制御部４０１が所定の処理（例えば、削除・シャッフル処理、転送処理等）を実行するために読み出したプログラムや、制御部４０１が当該プログラムを実行するために必要なデータを格納する揮発性メモリである。
【００３１】
ＲＯＭ４０３は、制御部４０１が所定の処理を実行するためのプログラム等を予め格納する不揮発性メモリである。制御部４０１は、ＲＯＭ４０３から必要に応じてプログラム等を読み出して、ＲＡＭ４０２に展開し、当該プログラム等に基づいて所定の処理を実行する。具体的には、ＲＯＭ４０３に格納するプログラムは、図４（Ｂ）に示すように、所定の暗号化データを削除して、シャッフルする削除・シャッフルプログラム４１０、暗号化データを転送するための転送プログラム４１１等である。また、ＲＯＭ４０３は、ネットワーク１０４に接続される装置が共通に利用するパラメータ（プログラム）である公開用共通パラメータ４１２等も格納する。
【００３２】
削除・シャッフルプログラム４１０は、受信した暗号化データのうち、削除対象となるデータをインデックスから検索し、該当するデータを削除するためのプログラムである。また、削除対象のデータを削除した後、残ったデータをシャッフルするためのプログラムである。具体的な処理については、後述する。
【００３３】
転送プログラム４１１は、削除・シャッフルプログラム４１０によって処理されたデータの転送先を決定し、決定した転送先にデータを転送するためのプログラムである。具体的な処理については、後述する。
【００３４】
公開用共通パラメータ４１２は、後述する各処理で用いられる双線型写像ｅ：（Ｇ１×Ｇ１→Ｇ２）を生成するためプログラムを含む。ここで、Ｇ１、Ｇ２は、位数ｑ（ｑは１以上の整数）を持つ巡回群を表す。なお、ｑは十分に大きい素数であることが望ましい。また、公開用共通パラメータ４１２は、ハッシュ関数Ｈにより任意のビット列を巡回群Ｇ１のサイズのデータ（例えば、疑似乱数等）を生成するためのプログラムを含む。さらに、公開用共通パラメータ４１２は、巡回群Ｇ１の任意の元Ｐを含む。また、公開用共通パラメータ４１２は、暗号化関数によりデータベース２０４のデータを暗号化するためのプログラムや、復号化関数により暗号化されたデータを復号化するためのプログラムを含む。
これらの公開用共通パラメータ４１２は、データ検索装置１０１、中間サーバ１０２、利用者用端末１０３で共通して用いられる共通パラメータ（共通プログラム）であり、必要に応じて提供される公開情報である。
【００３５】
記憶部４０４は、ハードディスクドライブ等の記憶装置から構成され、データ検索装置１０１や他の中間サーバ１０２から送信された暗号化データを格納する。また、記憶部４０４は、制御部４０１がＲＯＭ４０３等に格納されたプログラムに従って処理を行った結果として得られるデータを所定の場所に格納する。また、記憶部４０４は、中間サーバ１０２に固有のデータや鍵（中間サーバの番号ｊ、中間サーバ固有の値ｒ＿ｊ、中間サーバ公開鍵ｒ＿ｊＰ、中間サーバ公開情報Ｒ＿ｊ）等も記憶する。
【００３６】
通信部４０５は、ＮＩＣ（Network Interface Card）等から構成され、ネットワーク１０４に接続するためのインタフェースを備え、ネットワーク１０４との間で、ＴＣＰ／ＩＰプロトコルに基づく通信を行う。転送プログラム４１１に従って指定したＩＰアドレスを持つ他の中間サーバ１０２や、利用者用端末１０３と通信を行う。
また、通信部４０５は、例えば、モデム装置や赤外線通信装置等を含んでいてもよい。
【００３７】
システムバス４０６は、制御部４０１、ＲＡＭ４０２、ＲＯＭ４０３、記憶部４０４及び通信部４０５の間で命令やデータを転送するための伝送経路である。
【００３８】
このように、中間サーバ１０２は、一般的に普及しているコンピュータ等を用いて構成することができる。
【００３９】
次に、図１に示すネットワーク１０４に接続される利用者用端末１０３について説明する。利用者用端末１０３は、図５（Ａ）に示すように、制御部５０１、ＲＡＭ（Random Access Memory）５０２、ＲＯＭ（Read Only Memory）５０３、記憶部５０４、通信部５０５、表示部５０６、入力部５０７及びシステムバス５０８を含む。利用者用端末１０３は、データ検索システム１００を利用する利用者がデータ検索装置１０１への指示入力等を行う端末である。利用者用端末１０３は、データ検索装置１０１のデータベース２０４に格納されたデータの中から所望のデータを取り込み、そのデータのデータ内容を表示部５０６に表示する。
なお、利用者用端末１０３は、病院やオフィス、家庭内に配置されることはもちろん、ネットワーク１０４を介して利用者用端末１０３等に接続できればどこに配置されてもよい。
【００４０】
制御部５０１は、ＣＰＵ（Central Processing Unit）等の演算処理装置から構成され、利用者用端末１０３の全体の制御を行う。また、制御部５０１は、ＲＯＭ５０３に格納されるプログラムを読み出して、プログラムに基づいて所定の処理を実行する。例えば、データ検索装置１０１から送信された暗号化データを復号化する処理や、復号化したデータを表示部５０６に表示する処理を行う。制御部５０１が実行する処理の詳細については後述する。
【００４１】
ＲＡＭ５０２は、制御部５０１が所定の処理（例えば、鍵生成処理、復号化処理、表示処理、等）を実行するために読み出したプログラムや、制御部５０１が当該プログラムを実行するために必要なデータを格納する揮発性メモリである。
【００４２】
ＲＯＭ５０３は、制御部５０１が所定の処理を実行するためのプログラム等を予め格納する不揮発性メモリである。制御部５０１は、ＲＯＭ５０３から必要に応じてプログラム等を読み出して、ＲＡＭ５０２に展開し、当該プログラム等に基づいて所定の処理を実行する。具体的には、ＲＯＭ５０３に格納するプログラムは、図５（Ｂ）に示すように、暗号化・復号化等に用いる所定の鍵を生成するための鍵生成プログラム５１０、データ検索装置１０１から送信された暗号化データを復号化するデータ復号化プログラム５１１、復号化したデータのデータ内容を表示するための表示プログラム５１２等である。
【００４３】
鍵生成プログラム５１０は、例えば、Ｑｕｅｒｙ（暗号化鍵）、復号化鍵、中間サーバ暗号化鍵、中間サーバ復号化鍵、インデックス削除鍵等を生成するためのプログラムである。Ｑｕｅｒｙ（暗号化鍵）は、データベース２０４内のデータを暗号化するための暗号化鍵である。復号化鍵は、Ｑｕｅｒｙ（暗号化鍵）で暗号化されたデータを復号化するための復号化鍵である。中間サーバ暗号化鍵は、中間サーバのサーバ番号（例えば、１〜Ｎ、等）を暗号化するための暗号化鍵である。中間サーバ復号化鍵は、中間サーバ暗号化鍵で暗号化されたサーバ番号を復号化するための復号化鍵である。インデックス削除鍵は、中間サーバ１０２に転送された暗号化データのうち、削除対象のデータを検索するための鍵である。
【００４４】
データ復号化プログラム５１１は、利用者が選択した所望の暗号化データを復号化するためのプログラムである。具体的な処理については、後述する。
【００４５】
表示プログラム５１２は、利用者が操作するために必要な文字列や画像を表示したり、データベース２０４のデータから検索した検索結果（データ内容）を表示するためのプログラムである。
【００４６】
記憶部５０４は、ハードディスクドライブ等の記憶装置から構成され、中間サーバ１０２から送信された暗号化データを格納する。また、記憶部５０４は、制御部５０１がＲＯＭ５０３等に格納されたプログラムに従って処理を行った結果として得られるデータを所定の場所に格納する。例えば、鍵生成プログラム５１０で生成された各種鍵等（例えば、利用者を特定するための利用者秘密鍵Ｕｓｅｒ＿ｓｅｃｒｅｔ、利用者公開鍵Ｕ＿ｐｕｂ、等）を記憶する。
【００４７】
通信部５０５は、ＮＩＣ（Network Interface Card）等から構成され、ネットワーク１０４に接続するためのインタフェースを備え、ネットワーク１０４との間で、ＴＣＰ／ＩＰプロトコルに基づく通信を行う。
また、通信部５０５は、例えば、モデム装置や赤外線通信装置等を含んでいてもよい。
【００４８】
表示部５０６は、ＬＣＤ（Liquid Crystal Display）等の出力装置から構成される。利用者は、ＬＣＤに表示される画像や文字列等を見ることによって、データ検索装置１０１から送信されたデータのデータ内容を知ることができる。ここで、ＬＣＤは、ドットマトリクスタイプの表示素子であり、任意の文字、記号、数字、図形を表示する。
【００４９】
入力部５０７は、キーボード、マウス等の入力装置から構成される。これら入力装置を用いて利用者によって入力されるデータを受け付けて、入力されたデータを制御部５０１に供給する。
【００５０】
システムバス５０８は、制御部５０１、ＲＡＭ５０２、ＲＯＭ５０３、記憶部５０４、通信部５０５、表示部５０６及び入力部５０７の間で命令やデータを転送するための伝送経路である。
【００５１】
このように、中間サーバ１０２は、一般的に普及しているコンピュータ等を用いて構成することができる。
【００５２】
（データ検索システムの全体の動作）
次に、本実施の形態に係るデータ検索システム１００のシステム全体の大まかな動作について、図６、図７を参照して説明する。
【００５３】
図６のシーケンス図に示すように、まず、データ検索システム１００のセットアップとして、データ検索装置１０１は、ＲＯＭ２０３に格納した公開用共通パラメータ４１２を公開する（ステップＳ１）。この公開用共通パラメータ４１２の公開により、データ検索装置１０１、中間サーバ１０２、利用者用端末１０３のどの計算機も、公開用共通パラメータ４１２を利用できる。
【００５４】
データ検索装置１０１は、図３に示すデータベース２０４のデータから公開用データを利用者用端末１０３に公開する（ステップＳ２）。
【００５５】
利用者用端末１０３は、図７（Ａ）に示すように、ステップＳ２で公開された公開用データの選択画面を表示部５０６に表示し、利用者に選択させる。
このとき、利用者用端末１０３は、ｋアウトオブｎ（k out of n）紛失通信（Oblivious Transfer）方式によって、データ検索装置１０１と通信を開始する。ｋアウトオブｎ紛失通信方式による通信において、利用者が選択したデータがどれかを、データ検索装置１０１側に知られることはない。また、利用者は、選択したｋ個のデータ以外のデータ内容を入手することはできない。
利用者用端末１０３は、選択されたｋ個のデータに対応するＱｕｅｒｙを生成し、その生成したＱｕｅｒｙを暗号化したＱｅｕｒｙ（暗号化鍵）を生成する（ステップＳ３）。次に、利用者端末１０３は、生成したＱｕｅｒｙ（暗号化鍵）をデータ検索装置１０１に送信する（ステップＳ４）。ここで、Ｑｕｅｒｙ（暗号化鍵）は、データ検索装置１０１側に、利用者が選択したデータがどれかを知られないようにするために、利用者に選択されたインデックスに対して所定の演算を施して暗号化した暗号化鍵である。また、利用者用端末１０３は、Ｑｕｅｒｙ（暗号化鍵）を生成する前に、暗号化鍵で暗号化したデータを復号化するための復号化鍵も生成しておく。
【００５６】
さらに、利用者用端末１０３は、中間サーバ復号化鍵、中間サーバ暗号化鍵、インデックス削除鍵を生成し（ステップＳ５）、生成したインデックス削除鍵を中間サーバ１０２に送信する（ステップＳ６）。
【００５７】
Ｑｕｅｒｙ（暗号化鍵）を受信したデータ検索装置１０１は、このＱｕｅｒｙ（暗号化鍵）に基づいて、図３に示すデータベース２０４内の全てのデータ内容を暗号化する（ステップＳ７）。さらに、データ検索装置１０１は、図３に示すデータベース２０４内の全てのインデックス（公開用データ）を、公開用共通パラメータ４１２（公開情報）を用いて暗号化する（ステップＳ８）。
【００５８】
データ検索装置１０１は、ステップＳ７とステップＳ８でそれぞれ暗号化したデータ内容とインデックスとを対にしたまま、これらをランダムにシャッフルする（ステップＳ９）。そして、データ検索装置１０１は、ＲＯＭ２０３に格納された送信プログラム２１１に従って、暗号化したデータを中間サーバ（１）１０２に送信する（ステップＳ１０）。
【００５９】
暗号化されたデータを受信した中間サーバ（１）１０２は、受信したデータの中から、所定の条件を満たす削除対象の暗号化されたインデックスを検索する（ステップＳ１１）。中間サーバ（１）１０２は、ステップＳ１１で検索した結果に基づいて、所定の条件を満たす削除対象の暗号化されたインデックスに付属するデータを削除する（ステップＳ１２）。
【００６０】
このとき、中間サーバ（１）１０２は、全ての中間サーバ１０２で削除した総データ数をカウントするために、中間サーバ（１）１０２で削除したデータ数を記憶部４０４に記憶する（ステップＳ１３）。
【００６１】
さらに、中間サーバ（１）１０２は、ステップＳ１１で検索した結果、削除対象ではなかった各インデックスを、再度、暗号化する（ステップＳ１４）。その後、中間サーバ（１）１０２は、残ったデータを、ランダムにシャッフルする（ステップＳ１５）。
【００６２】
次に、中間サーバ（１）１０２は、シャッフルしたデータを中間サーバ（２）１０２に転送し（ステップＳ１６）、データを受信した中間サーバ（２）１０２は、ステップＳ１１からステップＳ１５までの処理を受信したデータに対して実行する。
【００６３】
以上のステップＳ１１からステップＳ１６までの処理が、全ての中間サーバ１０２（中間サーバ（１）、中間サーバ（２）、…、中間サーバ（Ｎ））で実行されるまで、順次、データを転送していく。
【００６４】
最後の中間サーバ（Ｎ）１０２は、ステップＳ１５を実行した後、データを利用者用端末１０３に送信する（ステップＳ１７）。
【００６５】
データを受信した利用者用端末１０３は、受信したデータを、予め作成しておいた復号化鍵で復号し（ステップＳ１８）、図７（Ｂ）に示すように、復号化したデータ内容を表示部５０６に表示する。
【００６６】
以上の一連の処理を実行するデータ検索システム１００は、暗号化したデータを各中間サーバ１０２で削除・シャッフルし、利用者用端末１０３へは、利用者が選択した所望のデータだけを転送する。これにより、従来のように、利用者用端末１０３へ利用者が選択したデータ以外のデータを転送することはないため、プライバシ保護機能は強化される。
【００６７】
以下に、図６のシーケンス図で説明した各処理について、より具体的に説明する。
【００６８】
（鍵生成処理）
まず、利用者用端末１０３の制御部５０１が、ＲＯＭ５０３に格納される鍵生成プログラム５１０に従って各種鍵を生成する「鍵生成処理」（図６のステップＳ３〜ステップＳ６に対応）について、図８のフローチャートを参照して説明する。
【００６９】
鍵生成処理で生成する鍵は、復号化鍵、Ｑｕｅｒｙ（暗号化鍵）、中間サーバ暗号化鍵、中間サーバ復号化鍵、インデックス削除鍵である。
【００７０】
鍵生成処理は、入力部５０７に配置されるキー或いはマウスボタンの押下による入力割り込みによって開始される。制御部５０１は、例えば、暗号化方式としてよく知られるＥｌＧａｍａｌ暗号方式の復号化鍵を生成する（ステップＳ１０１）。具体的には、制御部５０１は、素数ｐおよび乗法群Ｚ＿ｐでの原始元ｇを生成する。それに対して、ｘ∈Ｚ＿ｐ−１を満たす整数ｘを計算し、このｘを復号鍵とする。
【００７１】
次に、制御部５０１は、ステップＳ１０１で生成した復号化鍵に対する暗号化鍵を生成する（ステップＳ１０２）。具体的には、制御部５０１は、ｙ＝ｇ＾ｘ ｍｏｄ ｐを生成する。そして、利用者がｉ番目のインデックスを選択した場合、（ｐ，ｇ，ｙ−ｉ）をＱｕｅｒｙ（暗号化鍵）とする。
【００７２】
このＱｕｅｒｙ（暗号化鍵）は、データ検索装置１０１側に、利用者が選択したデータがどれかを知られずに対応するデータ内容を得ることを目的とする。加えて、このＱｕｅｒｙ（暗号化鍵）は、利用者が、選択したデータ以外のデータを取得できないように、選択したデータ数がわかるようにすることを目的とする。この目的を達成できれば、生成する暗号化鍵は、任意の暗号化鍵でよい。
【００７３】
制御部５０１は、ステップＳ１０２で生成したＱｕｅｒｙ（暗号化鍵）を、通信部５０５を介して、データ検索装置１０１に送信する（ステップＳ１０３）。
【００７４】
次に、制御部５０１は、各中間サーバの処理負担を軽減するために、各中間サーバ１０２が図６のステップＳ１１で検索するインデックス数をなるべく均等になるように設定する。具体的には、全インデックス数を中間サーバ数Ｎで除算した値、若しくは、その値に１加算した値にする。
【００７５】
さらに、制御部５０１は、各中間サーバ１０２を特定する値（若しくは、名前）を復号化するための数１に示す復号化鍵ｓ＿ｊを生成する（ステップＳ１０４）。ただし、ｊはサーバ番号、Ｎは中間サーバ数。
【数１】
【００７６】
また、制御部５０１は、各中間サーバ１０２を特定する値（若しくは、名前）を暗号化するための中間サーバ暗号化鍵Ｓ＿ｊを生成する（ステップＳ１０５）。具体的には、中間サーバ復号化鍵ｓ＿ｊと、中間サーバ１０２に記憶される公開情報Ｇ１上の任意の元Ｐとを取得して、数２を用いて中間サーバ暗号化鍵Ｓ＿ｊを生成する。すなわち、中間サーバ暗号化鍵Ｓ＿ｊは、中間サーバ復号化鍵ｓ＿ｊと、公開情報Ｇ１上の任意の元Ｐと、の論理積により生成される。
ここで、ステップＳ１０４、ステップＳ１０５で生成した中間サーバ復号化鍵、中間サーバ暗号化鍵は、ともに公開されない秘密の値である。
【数２】
【００７７】
さらに、制御部５０１は、各中間サーバ１０２が図６のステップＳ１１、ステップＳ１２で削除対象の暗号化データを検索・削除するときに必要となるインデックス削除鍵Ｓｅａｒｃｈ＿ｊを生成する（ステップＳ１０６）。具体的には、利用者秘密鍵Ｕｓｅｒ＿ｓｅｃｒｅｔ、中間サーバ復号鍵ｓ＿ｊと、中間サーバ１０２に記憶される公開情報Ｇ１であるハッシュ関数Ｈ及び双線型写像ｅと、中間サーバ１０２が所有する公開情報Ｒ＿ｊと、中間サーバ固有の値ｒ＿ｊとから、数３を用いてインデックス削除鍵を生成する。
【数３】
【００７８】
一般に、ハッシュ関数Ｈは不可逆な一方向関数であり、得られたハッシュ値からは元データを生成することができない。そのため、通信の暗号化やデジタル署名などの分野で広く用いられている。なお、本発明は、ハッシュ関数Ｈの具体的な数式（あるいは論理式等）を定めるものではない。また、ハッシュ関数Ｈは、似た情報から近いハッシュ値が得られず、値域に偏りがなく、異なる情報から同じハッシュ値が容易に生成されないように定義されることが望ましい。
【００７９】
次に、制御部５０１は、ステップＳ１０６で生成したインデックス削除鍵を、通信部５０５を介して、各中間サーバ１０２に送信し（ステップＳ１０７）、鍵生成処理を終了する。
【００８０】
なお、上述の各種鍵を生成するための各数式等は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【００８１】
（暗号化処理）
次に、データ検索装置１０１の制御部２０１が、ＲＯＭ２０３に格納されるデータ暗号化プログラム２１０に従って、データベース２０４のインデックス（公開データ）及びデータ内容を暗号化する「暗号化処理」（図６のステップＳ７〜ステップＳ９に対応）について、図９のフローチャートを参照して説明する。
【００８２】
暗号化処理は、図６のステップＳ４で、制御部２０１が、Ｑｕｅｒｙ（暗号化鍵）を受信することよって開始される。
【００８３】
制御部２０１は、まず、利用者に選択されなかったデータのインデックスを暗号化するためのダミー鍵を生成しておく。ダミー鍵の生成には、ダミー鍵に対応する復号鍵を容易に作成できないように、例えば、離散対数問題等を利用する。
【００８４】
次に、制御部２０１は、受信したＱｕｅｒｙ（暗号化鍵）及び、生成したダミー鍵を用いて、データベース２０４に格納してあるデータ内容を暗号化する（ステップＳ２０１）。具体的には、制御部２０１は、中間サーバ１０２が公開した公開用共通パラメータ４１２に含まれる暗号化関数により、データベース２０４に格納してあるデータ内容を暗号化する。例えば、制御部２０１は、受信したＱｕｅｒｙ（ｐ，ｇ，ｙ−ｉ）から、全てのインデックスＩＮＤＥＸに対して暗号化鍵ｙ−ｉ＋ＩＮＤＥＸを計算する。また、乱数ｒ∈Ｚ＿ｐ−１を生成する。これらを用いて、データベース２０４のデータ内容をＥｌＧａｍａｌ暗号化方式を用いて暗号化する。
【００８５】
以上の暗号化により、データ内容を対応する復号鍵なしで、復号することは困難となる。また、ダミー鍵を設けて、全てのデータ内容を暗号化することで、データ検索装置１０１側から、利用者がどのデータを閲覧しようとしているのか知ることはできない。
【００８６】
上述の暗号化関数は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【００８７】
次に、制御部２０１は、ステップＳ２０１で行った暗号化とは別に、データベース２０４のインデックス（公開情報）を暗号化する（ステップＳ２０２）。具体的には、制御部２０１は、中間サーバ１０２に記憶される公開情報であるハッシュ関数Ｈ及び双線型写像ｅとを取得し、中間サーバ１０２が公開する公開情報Ｒ＿ｊ、利用者用端末１０３が所有する中間サーバ暗号鍵Ｓ＿ｊ及び利用者公開鍵Ｕ＿ｐｕｄ、データベース２０４のインデックスを用いて、数４に示す数式でインデックス（公開情報）を暗号化する。
【数４】
【００８８】
ステップＳ２０１、ステップＳ２０２にあるように、データ内容とインデックスを別にして暗号化することにより、インデックスとデータ内容を結合したまま暗号化する手法と比較して、セキュリティをより強化した暗号化方式となる。
【００８９】
さらに、制御部２０１は、データベース２０４に格納される順序を、ランダムに入れ替える（ステップＳ２０３）。例えば、制御部２０１は、一様乱数等を用いて各データにデータ順序を表す番号を割り振ればよい。これにより、ステップＳ２０２で暗号化されたインデックスを復号化しない限り、データベース２０４に格納された順序を知ることはできない。順序を知られないようにすることは、不正にデータを取得しようとする人等が、必要なデータを効率よく取得することができないようにする意図が含まれる。
続いて、制御部２０１は、暗号化処理を終了し、ＲＯＭ２０３に格納される送信プログラム２１１に従って、暗号化したデータを中間サーバ１０２へ送信する処理に移行する。
【００９０】
なお、上述の暗号化のための数式や手法等は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【００９１】
（削除・シャッフル処理）
次に、各中間サーバ１０２の制御部４０１が、ＲＯＭ４０３に格納される削除・シャッフルプログラム４１０に従って、他の中間サーバ１０２から転送された暗号化データを、削除・シャッフルする「削除・シャッフル処理」（図６のステップＳ１１〜ステップＳ１７に対応）について、図１０のフローチャートを参照して説明する。
【００９２】
削除・シャッフル処理は、図６のステップＳ１０で、制御部４０１が、暗号化データを受信することよって開始される。
【００９３】
制御部４０１は、先に図６のステップＳ６で利用者用端末１０３から受信したインデックス削除鍵Ｓｅａｒｃｈ＿ｊに基づいて、データ検索装置１０１から受信した暗号化インデックスＥ＿ＩＮＤＥＸの中から、削除対象のインデックスを検索する（ステップＳ３０１）。具体的には、制御部４０１は、数３で表すインデックス削除鍵Ｓｅａｒｃｈ＿ｊと、中間サーバ公開鍵ｒ＿ｊＰとを双線型写像ｅにより写像したビット列のハッシュ値ＨＫと一致する暗号化インデックスＥ＿ＩＮＤＥＸを検索する。ここでのハッシュ値ＨＫを数５に表す。また、中間サーバ公開鍵ｒ＿ｊＰは、制御部４０１が、記憶部４０４に記憶される公開情報Ｇ１上の任意の元Ｐと、中間サーバ固有の値ｒ＿ｊとし、Ｐのｒ＿ｊ倍の演算により生成される。
【数５】
【００９４】
ハッシュ値ＨＫは、各中間サーバ１０２において、削除対象のデータを特定するための条件値となる。また、暗号化インデックスＥ＿ＩＮＤＥＸ、インデックス削除鍵Ｓｅａｒｃｈ＿ｊは、ともに暗号化されているので、各中間サーバ１０２は、インデックスに関して何の情報も得ることができず、利用者のプライバシを保護する。
【００９５】
制御部４０１は、データ検索装置１０１から受信した全ての暗号化インデックスＥ＿ＩＮＤＥＸについて、上述したハッシュ値ＨＫと一致するか否かを判別していく。ここで、制御部４０１は、全ての暗号化インデックスＥ＿ＩＮＤＥＸが、ハッシュ値ＨＫと一致しないと判別した場合（ステップＳ３０２；Ｎｏ）、データ検索装置１０１から受信した暗号化データを削除せずに、ステップＳ３０５の処理に移行させる。
【００９６】
一方、制御部４０１は、暗号化インデックスＥ＿ＩＮＤＥＸの中に、ハッシュ値ＨＫと一致するインデックスが有ると判別した場合（ステップＳ３０２；Ｙｅｓ）、一致したインデックスと、そのインデックスに結合したデータ内容を削除する（ステップＳ３０３）。
【００９７】
また、制御部４０１は、削除した暗号化インデックスの数Ｄｅｌを記憶部４０４に記憶する（ステップＳ３０４）。各中間サーバ１０２で登録したこの削除数Ｄｅｌの値は、例えば、一つの中間サーバ１０２で集計される。
【００９８】
次に、制御部４０１は、ステップＳ３０３で削除したデータ以外のデータのインデックス、すなわち、記憶部４０４に残っているインデックスを、再度、暗号化する（ステップＳ３０５）。具体的には、制御部４０１は、削除・シャッフルプログラム４１０に従って、中間サーバ１０２に記憶される公開情報であるハッシュ関数Ｈ及び双線型写像ｅとを取得する。そして、中間サーバ１０２が公開する公開情報Ｒ＿ｊ、利用者用端末１０３が所有する中間サーバ暗号鍵Ｓ＿ｊ及び利用者公開鍵Ｕ＿ｐｕｄ、各暗号化インデックスを用いて、数６に示す数式でインデックス（公開情報）を暗号化する。
【数６】
【００９９】
ここでの暗号化において、各中間サーバ１０２は、他の中間サーバ１０２で暗号化されたインデックスに基づいて、インデックスを暗号化する。そして、数６で暗号化されたインデックスでなければ、ステップＳ３０１で、適切に、削除対象のインデックスを検索することができない仕組みになっている。
【０１００】
次に、制御部４０１は、暗号化データの記憶部４０４に記憶される順序を、ランダムに入れ替える（ステップ３０６）。例えば、制御部４０１は、一様乱数等を用いて各データにデータ順序を表す番号を割り振ればよい。
【０１０１】
続いて、制御部４０１は、各中間サーバ１０２のステップＳ３０４で集計してきた暗号化データの削除数Ｄｅｌを参照し、最後の中間サーバ（Ｎ）１０２であるか否かを判別する（ステップＳ３０７）。制御部４０１は、最後の中間サーバ（Ｎ）１０２ではないと判別した場合（ステップＳ３０７；Ｎｏ）、ＲＯＭ４０３に格納される転送プログラム４１１に従って、ＩＰアドレスを参照して、ｊ＋１番目の中間サーバ（ｊ＋１）１０２に、残っている暗号化データを転送する（ステップＳ３０８）。
【０１０２】
以上のステップＳ３０１からステップＳ３０８の処理を、各中間サーバ１０２が実行することにより、利用者に選択されなかったデータを各中間サーバ１０２で削除していく。そして、最後の中間サーバ（Ｎ）１０２には、利用者に選択されたデータだけが残る。
【０１０３】
一方、ステップＳ３０７で、制御部４０１は、最後の中間サーバ１０２であると判別した場合（ステップＳ３０７；Ｙｅｓ）、ＲＯＭ４０３に格納される転送プログラム４１１に従って、残っている暗号化データを、通信部４０５を介して利用者用端末１０３に転送する（ステップＳ３０９）。その後、制御部４０１は、削除・シャッフル処理を終了する。
【０１０４】
なお、上述の暗号化のための数式等は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【０１０５】
（復号化処理）
次に、利用者用端末１０３の制御部５０１が、ＲＯＭ５０３に格納されるデータ復号化プログラム５１１に従って、中間サーバ（Ｎ）１０２から転送された暗号化データを復号化する「復号化処理」（図６のステップＳ１８に対応）について、図１１のフローチャートを参照して説明する。
【０１０６】
復号化処理は、図６のステップＳ１８で、制御部５０１が、暗号化データを受信することよって開始される。
【０１０７】
制御部５０１は、上述した鍵生成処理で生成した復号鍵（ｄ，ｎ）を用いて、受信した暗号化データを復号化する（ステップＳ４０１）。具体的には、制御部５０１は、中間サーバ１０２が公開した公開用共通パラメータ４１２に含まる復号化関数により、受信した暗号化データを復号化する。例えば、制御部５０１は、中間サーバ１０２からハッシュ関数Ｈを取得し、暗号化に用いた乱数Ｒ＿ＤＢ、別の乱数ｒ、ｉ（インデックス、又は、データ内容）を連結した値のハッシュ値ＨＢを求める。そして、このハッシュ値ＨＢと暗号化処理で求めた排他的論理和Ｅとの排他的論理和を求めることで、データを復号化する。
【０１０８】
上述したデータの暗号化・復号化に用いる鍵や、暗号化関数・復号化関数は、将来開発されるものも含めて任意のものでよい。
【０１０９】
次に、制御部５０１は、ＲＯＭ５０３に格納される表示プログラム５１２に従って、表示部５０６に、図７（Ｂ）に示すような、検索結果を表示させる（ステップＳ４０２）。
その後、制御部５０１は、復号化処理を終了する。
【０１１０】
このように、本実施形態のデータ検索システム１００によれば、プライバシの侵害を防御するためのプライバシ保護機能を強化して、データベースに蓄積したデータから所望のデータを検索できる効果が得られる。
【０１１１】
すなわち、データ検索装置１０１のデータベース２０４に格納されるデータのうち、インデックスとデータ内容とを、それぞれ別個に暗号化するため、データ間の関係性が秘匿され、データベース２０４のプライバシの保護は強化される。
【０１１２】
そして、暗号化データは、データ検索装置１０１と、利用者用端末１０３の間に配置された複数の中間サーバ１０２によって、暗号化データのシャッフルが繰り返されるために、中間サーバ１０２で暗号データが解読されても、利用者の選択したデータがどれであるか特定することは困難である。
【０１１３】
また、中間サーバ１０２によって、暗号化インデックスに基づいた削除が繰り返されるために、利用者用端末１０３に転送される暗号化データは、利用者が選択したデータに制限される。これにより、計算機の処理能力が向上して、利用者が選択したデータ以外のデータ内容が他人に知られてしまうようなプライバシの侵害を防ぐ効果がある。
【０１１４】
さらに、中間サーバ１０２において、削除対象のデータは、インデックス削除鍵に基づいて削除され、インデックスも暗号化されている。これにより、中間サーバ１０２から、インデックスに関する情報を得ることはできないため、利用者のプライバシの保護は強化される。
【０１１５】
この発明は上記実施の形態に限定されず、種々の変形及び応用が可能である。
【０１１６】
例えば、鍵生成処理で生成される各種鍵（暗号化鍵、復号化鍵、インデックス削除鍵）に有効期限を設定し、この有効期限内の場合にのみ、この各種鍵を用いた復号化ができるように構成することもできる。
この場合、例えば、利用者用端末１０３の制御部５０１は、暗号化鍵、復号化鍵、インデックス削除鍵に有効期限を含めて生成する。利用者用端末１０３の制御部５０１は、復号化処理を開始するときに有効期限が過ぎていれば復号を許可しないようにすればよい。
これにより、生成した各種鍵が本来の所有者の意に反して流出した場合でも、有効期限を過ぎていれば復号化ができないようにすることができ、データベースのデータや利用者が選択した情報の機密性を強化することができる。
【０１１７】
また、例えば、中間サーバ１０２に記憶される公開用共通パラメータ４１２を、定期的に変更するように構成することもできる。
この場合、中間サーバ１０２の制御部４０１は、所定のタイミング（例えば、１週間など）で、ハッシュ関数Ｈ、双線型写像ｅ及び公開情報Ｇ１のうちの一部又は全部を設定し直せばよい。また、データ検索装置１０１、中間サーバ１０２及び利用者用端末１０３は、上述の各処理を開始するときに逐次これらの公開用共通パラメータ４１２のセットを取り込み直して用いればよい。あるいは、制御部４０１は、公開用共通パラメータ４１２を設定し直したタイミングで、データ検索装置１０１、中間サーバ１０２及び利用者用端末１０３に公開用共通パラメータ４１２が再設定された旨の通知を行って、公開用共通パラメータ４１２の再取得を促す（あるいは自動的に取得する）ようにすればよい。
これにより、データ検索システム１００内でのデータの機密性を強化することができる。
【０１１８】
上記実施形態では、各中間サーバ１０２が削除する暗号化データの数は均等になるようにしていた。しかしながら、これに限定されず、処理能力の高い中間サーバ１０２に、多くの暗号化データを削除させるようにしてもよい。
【０１１９】
また、上記実施形態では、暗号化データを転送する中間サーバ１０２の順番については述べなかった。暗号化データは、各中間サーバ１０２間で、削除しながら転送されていくので、中間サーバ１０２が処理しなければならないデータ数はしだいに減少していく。そこで、暗号化データを転送する中間サーバ１０２の順番を、処理能力の高い中間サーバ１０２が最初にくるようにしてもよい。
【０１２０】
さらに、上記実施形態では、中間サーバ１０２が複数台（Ｎ台）の場合について説明したが、中間サーバ１０２は、１台であってもよい。中間サーバ１０２が１台の場合、１台の中間サーバ１０２が上述した削除・シャッフル処理を一度実施するか、複数回実施すればよい。
【０１２１】
また、上記実施形態では、公開用共通パラメータ４１２は中間サーバ１０２の記憶部４０４に格納していた。しかしながら、これに限定されず、公開用共通パラメータ４１２を、ネットワーク１０４に接続された他のサーバ等に格納して、公開するようにしてもよい。
【０１２２】
上記実施形態では、プログラムがＲＯＭ２０３、ＲＯＭ４０３及びＲＯＭ５０３等に予め記憶されているものとして説明した。しかし、データ検索装置１０１、中間サーバ１０２、利用者用端末１０３を、各々の全部又は一部として動作させ、あるいは、上述の処理を実行させるためのプログラムを、メモリカード、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory）、ＤＶＤ（Digital Versatile Disk）、ＭＯ（Magneto Optical disk）などのコンピュータ読み取り可能な記録媒体に格納して配布し、これを別のコンピュータにインストールし、上述の手段として動作させ、あるいは、上述の工程を実行させてもよい。
【０１２３】
さらに、インターネット上のサーバ装置が有するディスク装置等にプログラムを格納しておき、例えば、搬送波に重畳させて、コンピュータにダウンロード等するものとしてもよい。
【図面の簡単な説明】
【０１２４】
【図１】本実施形態に係るデータ検索システムの構成を説明するための図である。
【図２】データ検索装置の構成を説明するためのブロック図である。
【図３】データ検索装置のデータベースに記憶される情報の例を示す図である。
【図４】中間サーバの構成を説明するためのブロック図である。
【図５】利用者用端末の構成を説明するためのブロック図である。
【図６】本実施形態に係るデータ検索システムの全体の動作を説明するための図である。
【図７】（Ａ）はデータ選択画面の表示例を示す図である。（Ｂ）は検索結果の表示例を示す図である。
【図８】データ選択による割り込み入力によって開始する鍵生成処理を説明するためのフローチャートである。
【図９】暗号化鍵を受信することによって開始する暗号化処理を説明するためのフローチャートである。
【図１０】暗号化データを受信することによって開始する削除・シャッフル処理を説明するためのフローチャートである。
【図１１】暗号化データを受信することによって開始する復号化処理を説明するためのフローチャートである。
【符号の説明】
【０１２５】
１００ データ検索システム
１０１ データ検索装置
１０２ 中間サーバ
１０３ 利用者用端末
１０４ ネットワーク
２０１ 制御部（データ検索装置）
２０３ ＲＯＭ（データ検索装置）
２０４ データベース
２１０ データ暗号化プログラム
４０１ 制御部（中間サーバ）
４０３ ＲＯＭ（中間サーバ）
４１０ 削除・シャッフルプログラム
４１２ 公開用共通パラメータ
５０１ 制御部（利用者用端末）
５０３ ＲＯＭ（利用者用端末）
５０６ 表示部
５０７ 入力部
５１０ 鍵生成プログラム
５１１ データ復号化プログラム
【技術分野】
【０００１】
本発明は、データ検索システム、情報処理装置、データ検索方法、及び、プログラムに関する。
【背景技術】
【０００２】
近年、様々なデータが電子化されるようになっている。その電子化されたデータはデータベースに蓄積され、管理される。
また、これらの電子化されたデータをネットワークを介して不特定多数の人や組織に提供するシステムが多く利用されるようになった。例えば、新薬開発などへの利用を目的に、医療・診療情報をデータベースに蓄積しておき、これを外部に提供するといったシステムがある。このシステムの利用者は、データベースに蓄積されたデータの中から所望のデータを検索し、閲覧することができる。
【０００３】
そして、このようなデータの中には、プライバシ情報が含まれる場合も多い。例えば、新薬を開発している企業（システムの利用者）は、データベースのデータを検索した検索内容が、他の競合する企業等に知られた場合、大きな不利益を被る可能性がある。このような不利益を考慮すると、データベースのデータを検索した検索内容は、プライバシ情報として秘匿されなければならない。
【０００４】
そこで、検索内容（プライバシ情報）を秘匿しながら、所望のデータを外部に提供するデータ検索システムが要求されるようになった。例えば、特許文献１には、データベース内のデータを秘匿化（暗号化）し、秘匿化（暗号化）したデータを外部に提供する方法（ＳＰＩＲ（Symmetrically Private Information Retrieval））が開示されている。具体的には、データ検索システムは、利用者用端末等を用いてシステムの利用者によって入力された検索内容を暗号化し、暗号化した検索内容に従って、データベースにアクセスする。また、データ検索システムは、データベースに格納された全てのデータを暗号化し、暗号化したデータを利用者に提供するために、利用者用端末等へ送信する。さらに、データ検索システムは、送信したデータのうち、検索内容に対応したデータのみを復号する。
【特許文献１】特開２００３−２９６３３号公報
【０００５】
現在の計算機では、検索内容以外の復号鍵を持たない暗号化データを解読することは、計算機の処理速度が遅いために非常に困難であると考えられている。そのため、特許文献１に開示されるデータ検索システムは、データベースに格納された全ての暗号化データを利用者用端末等へ送信したとしても、プライバシ情報を秘匿するのに十分なシステムとされている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来のデータ検索システムは、将来的には計算機の処理速度の向上等により、検索内容以外の復号鍵を持たない暗号化データが解読される可能性が高くなり、プライバシが侵害される虞がある。
【０００７】
本発明は、上記実状に鑑みてなされたものであり、プライバシの侵害を防御するためのプライバシ保護機能を強化したデータ検索システム、情報処理装置、データ検索方法、及び、プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の第１の観点に係るデータ検索システムは、第１の情報処理装置と、第２の情報処理装置と、第３の情報処理装置と、から構成されるデータ検索システムであって、
前記第１の情報処理装置は、
情報を記憶するデータベースと、
前記データベースに記憶されている情報のインデックスを前記第２の情報処理装置に公開するインデックス公開手段と、
を備え、
前記第２の情報処理装置は、
前記インデックスを取得し、取得したインデックスの少なくとも一部に対応する暗号鍵及び復号鍵を生成する暗号鍵・復号鍵生成手段と、
前記第３の情報処理装置が前記情報を削除するために必要な削除鍵を生成する削除鍵生成手段と、
前記暗号鍵・復号鍵生成手段が生成した暗号鍵を前記第１の情報処理装置に送信する暗号鍵送信手段と、
前記削除鍵生成手段が生成した削除鍵を前記第２の情報処理装置に送信する削除鍵送信手段と、
を備え、
前記第１の情報処理装置は、さらに、
前記暗号鍵送信手段が送信した暗号鍵を受信し、受信した暗号鍵に基づいて、前記データベースに記憶される情報を暗号化する暗号化手段と、
前記暗号化手段が暗号化した暗号化情報を前記第３の情報処理装置に送信する暗号化情報送信手段と、
を備え、
前記第３の情報処理装置は、
前記暗号化情報送信手段が送信した暗号化情報を受信する暗号化情報受信手段と、
前記削除鍵送信手段が送信した削除鍵を受信する削除鍵受信手段と、
前記削除鍵受信手段が受信した削除鍵に基づいて、前記暗号化情報受信手段が受信した暗号化情報の所定数の情報を削除する情報削除手段と、
前記情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信する入れ替え情報送信手段と、
を備え、
前記第２の情報処置装置は、さらに、
前記入れ替え情報送信手段が送信した情報を受信し、前記暗号鍵・復号鍵生成手段が生成した復号鍵に基づいて、受信した前記情報を復号化する復号化手段と、
を備える、
ことを特徴とする。
【０００９】
また、前記データ検索システムにおいて、
前記第３の情報処理装置は、複数の装置から構成され、
前記情報順序入れ替え手段が情報を入れ替えた後、前記情報の残数が前記暗号鍵・復号鍵生成手段が取得したインデックスの少なくとも一部に対応するインデックス数と等しいか否かを判別する残数判別手段と、
前記残数判別手段が、前記情報の残数が前記インデックス数と等しいと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信し、前記残数判別手段が、前記情報の残数が前記インデックス数と等しくないと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を別の前記第３の情報処理装置に送信する第２の入れ替え情報送信手段と、
を備えることを特徴とするようにしてもよい。
【００１０】
上記目的を達成するため、本発明の第２の観点に係る情報処理装置は
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手段と、
前記削除鍵記憶手段が記憶する削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手段と、
前記暗号化情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
を備えることを特徴とする。
【００１１】
上記目的を達成するため、本発明の第３の観点に係るデータ検索方法は、
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶ステップと、
前記削除鍵記憶ステップで記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除ステップと、
前記暗号化情報削除ステップで情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替えステップと、
を備えることを特徴とする。
【００１２】
上記目的を達成するため、本発明の第４の観点に係るプログラムは、
コンピュータに、
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手順と、
前記削除鍵記憶手順で記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手順と、
前記暗号化情報削除手順で情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手順と、
を実行させる。
【発明の効果】
【００１３】
本発明のシステムによれば、プライバシの侵害を防御するためのプライバシ保護機能を強化して、データベースに蓄積したデータから所望のデータを検索することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施形態に係るデータ検索システム１００を説明する。
【００１５】
本実施形態に係るデータ検索システム１００は、図１に示すように、データ検索装置１０１と、複数台の中間サーバ１０２と、利用者用端末１０３と、から構成される。また、中間サーバ１０２は、単一のサーバで構成してもよい。データ検索装置１０１、各中間サーバ１０２、利用者用端末１０３は、それぞれネットワーク１０４を介して接続される。このような構成からなるデータ検索システム１００は、データ検索装置１０１内のデータベースに格納されたデータのうち、利用者用端末１０３からの要求に応じた所望のデータを利用者に提供するシステムである。
【００１６】
ここで、ネットワーク１０４は、一般的な通信手段を用いることが可能である。本実施形態において、一般的に使用されているＴＣＰ／ＩＰ（トランスミッション・コントロール・プロトコル／インターネット・プロトコル）が使用される。なお、他のプロトコルが使用されてもよい。また、ネットワーク１０４は、ローカル・エリア・ネットワークでも、ワイド・エリア・ネットワークでもよい。バーチャル・プライベート・ネットワーク（ＶＰＮ）やワイヤレス接続のような通信手段も同じように使用可能である。
【００１７】
データ検索装置１０１は、図２（Ａ）に示すように、制御部２０１、ＲＡＭ（Random Access Memory）２０２、ＲＯＭ（Read Only Memory）２０３、データベース２０４、通信部２０５及びシステムバス２０６を含む。データ検索装置１０１は、データベース２０４にデータを格納し、通信部２０５を介して、利用者用端末１０３からの要求に応じてデータを利用者用端末１０３へ送信する装置である。
なお、データ検索装置１０１は、病院やオフィス内に配置されることはもちろん、ネットワーク１０４を介して利用者用端末１０３等に接続できればどこに配置されてもよい。
【００１８】
データベース２０４は、利用者用端末１０３に送信するデータを格納するデータベースであり、例えば、図３に示すように、データを識別するためのインデックス番号（例えば、数字、等）、データ種別（例えば、性別、年齢、等）、データ内容（例えば、病歴、等）等を対応づけて記憶する。
【００１９】
制御部２０１は、ＣＰＵ（Central Processing Unit）等の演算処理装置から構成され、データ検索装置１０１の全体の制御を行う。また、制御部２０１は、ＲＯＭ２０３に格納されるプログラムを読み出して、プログラムに基づいて所定の処理を実行する。例えばデータベース２０４に格納されたデータを暗号化する処理を行う。制御部２０１が実行する処理の詳細については後述する。
【００２０】
ＲＡＭ２０２は、制御部２０１が所定の処理（例えば、暗号化処理、等）を実行するために読み出したプログラムや、制御部２０１が当該プログラムを実行するために必要なデータを格納する揮発性メモリである。
【００２１】
ＲＯＭ２０３は、制御部２０１が所定の処理を実行するためのプログラム等を予め格納する不揮発性メモリである。制御部２０１は、ＲＯＭ２０３から必要に応じてプログラム等を読み出して、ＲＡＭ２０２に展開し、当該プログラム等に基づいて所定の処理を実行する。具体的には、ＲＯＭ２０３に格納するプログラムは、図２（Ｂ）に示すように、データを暗号化するデータ暗号化プログラム２１０、暗号化データを送信するための送信プログラム２１１等である。
【００２２】
データ暗号化プログラム２１０は、データベース２０４のインデックス（公開データ）及びデータ内容をそれぞれ暗号化するためのプログラムである。暗号化の具体的な処理については、後述する。
【００２３】
送信プログラム２１１は、データ暗号化プログラム２１０で暗号化したデータを、中間サーバ（１）１０２へ送信するためのプログラムである。具体的な処理については、後述する。
【００２４】
通信部２０５は、ＮＩＣ（Network Interface Card）等から構成され、ネットワーク１０４に接続するためのインタフェースを備え、ネットワーク１０４との間で、ＴＣＰ／ＩＰプロトコルに基づく通信を行う。通信部２０５は、例えば、モデム装置や赤外線通信装置等を含んでいてもよい。
【００２５】
システムバス２０６は、制御部２０１、ＲＡＭ２０２、ＲＯＭ２０３、データベース２０４及び通信部２０５の間で命令やデータを転送するための伝送経路である。
【００２６】
このように、データ検索装置１０１は、一般的に普及しているコンピュータ等を用いて構成することができる。
【００２７】
次に、図１に示すネットワーク１０４に接続される中間サーバ１０２について説明する。中間サーバ１０２は、複数台（例えば、Ｎ台）で構成される。
各中間サーバ１０２に、例えば、所定のＩＰアドレスを割り振り、データ検索装置１０１及び各中間サーバ１０２は、ＩＰアドレスを指定して所望の中間サーバ１０２にネットワーク１０４を介してアクセスする。
具体的には、中間サーバ（１）２０１にＩＰアドレス：１９２．１６８．０．１、中間サーバ（２）２０１にＩＰアドレス：１９２．１６８．０．２、…、中間サーバ（Ｎ）２０１にＩＰアドレス：１９２．１６８．０．Ｎ等といった静的アドレスを割り当てる。データ検索装置１０１及び各中間サーバ１０２は、この静的アドレスを指定して送信先の中間サーバ１０２を決定し、順次、暗号化データを転送する。また、各中間サーバ１０２は、暗号化データに対して、削除・シャッフル処理を施してから、それらデータを転送する。削除・シャッフル処理等の具体的な内容の詳細については後述する。
また、各中間サーバ１０２に、静的なＩＰアドレスを割り当てる必要はなく、ＤＮＳ（Domain Name Sever）やＤＨＣＰ（Dynamic Host Configuration Protocol）サーバ等を協働して利用し、動的なＩＰアドレスを割り当てるようにしてもよい。
【００２８】
各中間サーバ１０２は、それぞれ同様の構成からなり、図４（Ａ）に示すように、制御部４０１、ＲＡＭ（Random Access Memory）４０２、ＲＯＭ（Read Only Memory）４０３、記憶部４０４、通信部４０５及びシステムバス４０６を含む。
【００２９】
制御部４０１は、ＣＰＵ（Central Processing Unit）等の演算処理装置から構成され、中間サーバ１０２の全体の制御を行う。また、制御部４０１は、ＲＯＭ４０３に格納されるプログラムを読み出して、プログラムに基づいて所定の処理を実行する。例えば、記憶部４０４に格納された暗号化データに対して削除・シャッフル処理、転送処理等を行う。
【００３０】
ＲＡＭ４０２は、制御部４０１が所定の処理（例えば、削除・シャッフル処理、転送処理等）を実行するために読み出したプログラムや、制御部４０１が当該プログラムを実行するために必要なデータを格納する揮発性メモリである。
【００３１】
ＲＯＭ４０３は、制御部４０１が所定の処理を実行するためのプログラム等を予め格納する不揮発性メモリである。制御部４０１は、ＲＯＭ４０３から必要に応じてプログラム等を読み出して、ＲＡＭ４０２に展開し、当該プログラム等に基づいて所定の処理を実行する。具体的には、ＲＯＭ４０３に格納するプログラムは、図４（Ｂ）に示すように、所定の暗号化データを削除して、シャッフルする削除・シャッフルプログラム４１０、暗号化データを転送するための転送プログラム４１１等である。また、ＲＯＭ４０３は、ネットワーク１０４に接続される装置が共通に利用するパラメータ（プログラム）である公開用共通パラメータ４１２等も格納する。
【００３２】
削除・シャッフルプログラム４１０は、受信した暗号化データのうち、削除対象となるデータをインデックスから検索し、該当するデータを削除するためのプログラムである。また、削除対象のデータを削除した後、残ったデータをシャッフルするためのプログラムである。具体的な処理については、後述する。
【００３３】
転送プログラム４１１は、削除・シャッフルプログラム４１０によって処理されたデータの転送先を決定し、決定した転送先にデータを転送するためのプログラムである。具体的な処理については、後述する。
【００３４】
公開用共通パラメータ４１２は、後述する各処理で用いられる双線型写像ｅ：（Ｇ１×Ｇ１→Ｇ２）を生成するためプログラムを含む。ここで、Ｇ１、Ｇ２は、位数ｑ（ｑは１以上の整数）を持つ巡回群を表す。なお、ｑは十分に大きい素数であることが望ましい。また、公開用共通パラメータ４１２は、ハッシュ関数Ｈにより任意のビット列を巡回群Ｇ１のサイズのデータ（例えば、疑似乱数等）を生成するためのプログラムを含む。さらに、公開用共通パラメータ４１２は、巡回群Ｇ１の任意の元Ｐを含む。また、公開用共通パラメータ４１２は、暗号化関数によりデータベース２０４のデータを暗号化するためのプログラムや、復号化関数により暗号化されたデータを復号化するためのプログラムを含む。
これらの公開用共通パラメータ４１２は、データ検索装置１０１、中間サーバ１０２、利用者用端末１０３で共通して用いられる共通パラメータ（共通プログラム）であり、必要に応じて提供される公開情報である。
【００３５】
記憶部４０４は、ハードディスクドライブ等の記憶装置から構成され、データ検索装置１０１や他の中間サーバ１０２から送信された暗号化データを格納する。また、記憶部４０４は、制御部４０１がＲＯＭ４０３等に格納されたプログラムに従って処理を行った結果として得られるデータを所定の場所に格納する。また、記憶部４０４は、中間サーバ１０２に固有のデータや鍵（中間サーバの番号ｊ、中間サーバ固有の値ｒ＿ｊ、中間サーバ公開鍵ｒ＿ｊＰ、中間サーバ公開情報Ｒ＿ｊ）等も記憶する。
【００３６】
通信部４０５は、ＮＩＣ（Network Interface Card）等から構成され、ネットワーク１０４に接続するためのインタフェースを備え、ネットワーク１０４との間で、ＴＣＰ／ＩＰプロトコルに基づく通信を行う。転送プログラム４１１に従って指定したＩＰアドレスを持つ他の中間サーバ１０２や、利用者用端末１０３と通信を行う。
また、通信部４０５は、例えば、モデム装置や赤外線通信装置等を含んでいてもよい。
【００３７】
システムバス４０６は、制御部４０１、ＲＡＭ４０２、ＲＯＭ４０３、記憶部４０４及び通信部４０５の間で命令やデータを転送するための伝送経路である。
【００３８】
このように、中間サーバ１０２は、一般的に普及しているコンピュータ等を用いて構成することができる。
【００３９】
次に、図１に示すネットワーク１０４に接続される利用者用端末１０３について説明する。利用者用端末１０３は、図５（Ａ）に示すように、制御部５０１、ＲＡＭ（Random Access Memory）５０２、ＲＯＭ（Read Only Memory）５０３、記憶部５０４、通信部５０５、表示部５０６、入力部５０７及びシステムバス５０８を含む。利用者用端末１０３は、データ検索システム１００を利用する利用者がデータ検索装置１０１への指示入力等を行う端末である。利用者用端末１０３は、データ検索装置１０１のデータベース２０４に格納されたデータの中から所望のデータを取り込み、そのデータのデータ内容を表示部５０６に表示する。
なお、利用者用端末１０３は、病院やオフィス、家庭内に配置されることはもちろん、ネットワーク１０４を介して利用者用端末１０３等に接続できればどこに配置されてもよい。
【００４０】
制御部５０１は、ＣＰＵ（Central Processing Unit）等の演算処理装置から構成され、利用者用端末１０３の全体の制御を行う。また、制御部５０１は、ＲＯＭ５０３に格納されるプログラムを読み出して、プログラムに基づいて所定の処理を実行する。例えば、データ検索装置１０１から送信された暗号化データを復号化する処理や、復号化したデータを表示部５０６に表示する処理を行う。制御部５０１が実行する処理の詳細については後述する。
【００４１】
ＲＡＭ５０２は、制御部５０１が所定の処理（例えば、鍵生成処理、復号化処理、表示処理、等）を実行するために読み出したプログラムや、制御部５０１が当該プログラムを実行するために必要なデータを格納する揮発性メモリである。
【００４２】
ＲＯＭ５０３は、制御部５０１が所定の処理を実行するためのプログラム等を予め格納する不揮発性メモリである。制御部５０１は、ＲＯＭ５０３から必要に応じてプログラム等を読み出して、ＲＡＭ５０２に展開し、当該プログラム等に基づいて所定の処理を実行する。具体的には、ＲＯＭ５０３に格納するプログラムは、図５（Ｂ）に示すように、暗号化・復号化等に用いる所定の鍵を生成するための鍵生成プログラム５１０、データ検索装置１０１から送信された暗号化データを復号化するデータ復号化プログラム５１１、復号化したデータのデータ内容を表示するための表示プログラム５１２等である。
【００４３】
鍵生成プログラム５１０は、例えば、Ｑｕｅｒｙ（暗号化鍵）、復号化鍵、中間サーバ暗号化鍵、中間サーバ復号化鍵、インデックス削除鍵等を生成するためのプログラムである。Ｑｕｅｒｙ（暗号化鍵）は、データベース２０４内のデータを暗号化するための暗号化鍵である。復号化鍵は、Ｑｕｅｒｙ（暗号化鍵）で暗号化されたデータを復号化するための復号化鍵である。中間サーバ暗号化鍵は、中間サーバのサーバ番号（例えば、１〜Ｎ、等）を暗号化するための暗号化鍵である。中間サーバ復号化鍵は、中間サーバ暗号化鍵で暗号化されたサーバ番号を復号化するための復号化鍵である。インデックス削除鍵は、中間サーバ１０２に転送された暗号化データのうち、削除対象のデータを検索するための鍵である。
【００４４】
データ復号化プログラム５１１は、利用者が選択した所望の暗号化データを復号化するためのプログラムである。具体的な処理については、後述する。
【００４５】
表示プログラム５１２は、利用者が操作するために必要な文字列や画像を表示したり、データベース２０４のデータから検索した検索結果（データ内容）を表示するためのプログラムである。
【００４６】
記憶部５０４は、ハードディスクドライブ等の記憶装置から構成され、中間サーバ１０２から送信された暗号化データを格納する。また、記憶部５０４は、制御部５０１がＲＯＭ５０３等に格納されたプログラムに従って処理を行った結果として得られるデータを所定の場所に格納する。例えば、鍵生成プログラム５１０で生成された各種鍵等（例えば、利用者を特定するための利用者秘密鍵Ｕｓｅｒ＿ｓｅｃｒｅｔ、利用者公開鍵Ｕ＿ｐｕｂ、等）を記憶する。
【００４７】
通信部５０５は、ＮＩＣ（Network Interface Card）等から構成され、ネットワーク１０４に接続するためのインタフェースを備え、ネットワーク１０４との間で、ＴＣＰ／ＩＰプロトコルに基づく通信を行う。
また、通信部５０５は、例えば、モデム装置や赤外線通信装置等を含んでいてもよい。
【００４８】
表示部５０６は、ＬＣＤ（Liquid Crystal Display）等の出力装置から構成される。利用者は、ＬＣＤに表示される画像や文字列等を見ることによって、データ検索装置１０１から送信されたデータのデータ内容を知ることができる。ここで、ＬＣＤは、ドットマトリクスタイプの表示素子であり、任意の文字、記号、数字、図形を表示する。
【００４９】
入力部５０７は、キーボード、マウス等の入力装置から構成される。これら入力装置を用いて利用者によって入力されるデータを受け付けて、入力されたデータを制御部５０１に供給する。
【００５０】
システムバス５０８は、制御部５０１、ＲＡＭ５０２、ＲＯＭ５０３、記憶部５０４、通信部５０５、表示部５０６及び入力部５０７の間で命令やデータを転送するための伝送経路である。
【００５１】
このように、中間サーバ１０２は、一般的に普及しているコンピュータ等を用いて構成することができる。
【００５２】
（データ検索システムの全体の動作）
次に、本実施の形態に係るデータ検索システム１００のシステム全体の大まかな動作について、図６、図７を参照して説明する。
【００５３】
図６のシーケンス図に示すように、まず、データ検索システム１００のセットアップとして、データ検索装置１０１は、ＲＯＭ２０３に格納した公開用共通パラメータ４１２を公開する（ステップＳ１）。この公開用共通パラメータ４１２の公開により、データ検索装置１０１、中間サーバ１０２、利用者用端末１０３のどの計算機も、公開用共通パラメータ４１２を利用できる。
【００５４】
データ検索装置１０１は、図３に示すデータベース２０４のデータから公開用データを利用者用端末１０３に公開する（ステップＳ２）。
【００５５】
利用者用端末１０３は、図７（Ａ）に示すように、ステップＳ２で公開された公開用データの選択画面を表示部５０６に表示し、利用者に選択させる。
このとき、利用者用端末１０３は、ｋアウトオブｎ（k out of n）紛失通信（Oblivious Transfer）方式によって、データ検索装置１０１と通信を開始する。ｋアウトオブｎ紛失通信方式による通信において、利用者が選択したデータがどれかを、データ検索装置１０１側に知られることはない。また、利用者は、選択したｋ個のデータ以外のデータ内容を入手することはできない。
利用者用端末１０３は、選択されたｋ個のデータに対応するＱｕｅｒｙを生成し、その生成したＱｕｅｒｙを暗号化したＱｅｕｒｙ（暗号化鍵）を生成する（ステップＳ３）。次に、利用者端末１０３は、生成したＱｕｅｒｙ（暗号化鍵）をデータ検索装置１０１に送信する（ステップＳ４）。ここで、Ｑｕｅｒｙ（暗号化鍵）は、データ検索装置１０１側に、利用者が選択したデータがどれかを知られないようにするために、利用者に選択されたインデックスに対して所定の演算を施して暗号化した暗号化鍵である。また、利用者用端末１０３は、Ｑｕｅｒｙ（暗号化鍵）を生成する前に、暗号化鍵で暗号化したデータを復号化するための復号化鍵も生成しておく。
【００５６】
さらに、利用者用端末１０３は、中間サーバ復号化鍵、中間サーバ暗号化鍵、インデックス削除鍵を生成し（ステップＳ５）、生成したインデックス削除鍵を中間サーバ１０２に送信する（ステップＳ６）。
【００５７】
Ｑｕｅｒｙ（暗号化鍵）を受信したデータ検索装置１０１は、このＱｕｅｒｙ（暗号化鍵）に基づいて、図３に示すデータベース２０４内の全てのデータ内容を暗号化する（ステップＳ７）。さらに、データ検索装置１０１は、図３に示すデータベース２０４内の全てのインデックス（公開用データ）を、公開用共通パラメータ４１２（公開情報）を用いて暗号化する（ステップＳ８）。
【００５８】
データ検索装置１０１は、ステップＳ７とステップＳ８でそれぞれ暗号化したデータ内容とインデックスとを対にしたまま、これらをランダムにシャッフルする（ステップＳ９）。そして、データ検索装置１０１は、ＲＯＭ２０３に格納された送信プログラム２１１に従って、暗号化したデータを中間サーバ（１）１０２に送信する（ステップＳ１０）。
【００５９】
暗号化されたデータを受信した中間サーバ（１）１０２は、受信したデータの中から、所定の条件を満たす削除対象の暗号化されたインデックスを検索する（ステップＳ１１）。中間サーバ（１）１０２は、ステップＳ１１で検索した結果に基づいて、所定の条件を満たす削除対象の暗号化されたインデックスに付属するデータを削除する（ステップＳ１２）。
【００６０】
このとき、中間サーバ（１）１０２は、全ての中間サーバ１０２で削除した総データ数をカウントするために、中間サーバ（１）１０２で削除したデータ数を記憶部４０４に記憶する（ステップＳ１３）。
【００６１】
さらに、中間サーバ（１）１０２は、ステップＳ１１で検索した結果、削除対象ではなかった各インデックスを、再度、暗号化する（ステップＳ１４）。その後、中間サーバ（１）１０２は、残ったデータを、ランダムにシャッフルする（ステップＳ１５）。
【００６２】
次に、中間サーバ（１）１０２は、シャッフルしたデータを中間サーバ（２）１０２に転送し（ステップＳ１６）、データを受信した中間サーバ（２）１０２は、ステップＳ１１からステップＳ１５までの処理を受信したデータに対して実行する。
【００６３】
以上のステップＳ１１からステップＳ１６までの処理が、全ての中間サーバ１０２（中間サーバ（１）、中間サーバ（２）、…、中間サーバ（Ｎ））で実行されるまで、順次、データを転送していく。
【００６４】
最後の中間サーバ（Ｎ）１０２は、ステップＳ１５を実行した後、データを利用者用端末１０３に送信する（ステップＳ１７）。
【００６５】
データを受信した利用者用端末１０３は、受信したデータを、予め作成しておいた復号化鍵で復号し（ステップＳ１８）、図７（Ｂ）に示すように、復号化したデータ内容を表示部５０６に表示する。
【００６６】
以上の一連の処理を実行するデータ検索システム１００は、暗号化したデータを各中間サーバ１０２で削除・シャッフルし、利用者用端末１０３へは、利用者が選択した所望のデータだけを転送する。これにより、従来のように、利用者用端末１０３へ利用者が選択したデータ以外のデータを転送することはないため、プライバシ保護機能は強化される。
【００６７】
以下に、図６のシーケンス図で説明した各処理について、より具体的に説明する。
【００６８】
（鍵生成処理）
まず、利用者用端末１０３の制御部５０１が、ＲＯＭ５０３に格納される鍵生成プログラム５１０に従って各種鍵を生成する「鍵生成処理」（図６のステップＳ３〜ステップＳ６に対応）について、図８のフローチャートを参照して説明する。
【００６９】
鍵生成処理で生成する鍵は、復号化鍵、Ｑｕｅｒｙ（暗号化鍵）、中間サーバ暗号化鍵、中間サーバ復号化鍵、インデックス削除鍵である。
【００７０】
鍵生成処理は、入力部５０７に配置されるキー或いはマウスボタンの押下による入力割り込みによって開始される。制御部５０１は、例えば、暗号化方式としてよく知られるＥｌＧａｍａｌ暗号方式の復号化鍵を生成する（ステップＳ１０１）。具体的には、制御部５０１は、素数ｐおよび乗法群Ｚ＿ｐでの原始元ｇを生成する。それに対して、ｘ∈Ｚ＿ｐ−１を満たす整数ｘを計算し、このｘを復号鍵とする。
【００７１】
次に、制御部５０１は、ステップＳ１０１で生成した復号化鍵に対する暗号化鍵を生成する（ステップＳ１０２）。具体的には、制御部５０１は、ｙ＝ｇ＾ｘ ｍｏｄ ｐを生成する。そして、利用者がｉ番目のインデックスを選択した場合、（ｐ，ｇ，ｙ−ｉ）をＱｕｅｒｙ（暗号化鍵）とする。
【００７２】
このＱｕｅｒｙ（暗号化鍵）は、データ検索装置１０１側に、利用者が選択したデータがどれかを知られずに対応するデータ内容を得ることを目的とする。加えて、このＱｕｅｒｙ（暗号化鍵）は、利用者が、選択したデータ以外のデータを取得できないように、選択したデータ数がわかるようにすることを目的とする。この目的を達成できれば、生成する暗号化鍵は、任意の暗号化鍵でよい。
【００７３】
制御部５０１は、ステップＳ１０２で生成したＱｕｅｒｙ（暗号化鍵）を、通信部５０５を介して、データ検索装置１０１に送信する（ステップＳ１０３）。
【００７４】
次に、制御部５０１は、各中間サーバの処理負担を軽減するために、各中間サーバ１０２が図６のステップＳ１１で検索するインデックス数をなるべく均等になるように設定する。具体的には、全インデックス数を中間サーバ数Ｎで除算した値、若しくは、その値に１加算した値にする。
【００７５】
さらに、制御部５０１は、各中間サーバ１０２を特定する値（若しくは、名前）を復号化するための数１に示す復号化鍵ｓ＿ｊを生成する（ステップＳ１０４）。ただし、ｊはサーバ番号、Ｎは中間サーバ数。
【数１】
【００７６】
また、制御部５０１は、各中間サーバ１０２を特定する値（若しくは、名前）を暗号化するための中間サーバ暗号化鍵Ｓ＿ｊを生成する（ステップＳ１０５）。具体的には、中間サーバ復号化鍵ｓ＿ｊと、中間サーバ１０２に記憶される公開情報Ｇ１上の任意の元Ｐとを取得して、数２を用いて中間サーバ暗号化鍵Ｓ＿ｊを生成する。すなわち、中間サーバ暗号化鍵Ｓ＿ｊは、中間サーバ復号化鍵ｓ＿ｊと、公開情報Ｇ１上の任意の元Ｐと、の論理積により生成される。
ここで、ステップＳ１０４、ステップＳ１０５で生成した中間サーバ復号化鍵、中間サーバ暗号化鍵は、ともに公開されない秘密の値である。
【数２】
【００７７】
さらに、制御部５０１は、各中間サーバ１０２が図６のステップＳ１１、ステップＳ１２で削除対象の暗号化データを検索・削除するときに必要となるインデックス削除鍵Ｓｅａｒｃｈ＿ｊを生成する（ステップＳ１０６）。具体的には、利用者秘密鍵Ｕｓｅｒ＿ｓｅｃｒｅｔ、中間サーバ復号鍵ｓ＿ｊと、中間サーバ１０２に記憶される公開情報Ｇ１であるハッシュ関数Ｈ及び双線型写像ｅと、中間サーバ１０２が所有する公開情報Ｒ＿ｊと、中間サーバ固有の値ｒ＿ｊとから、数３を用いてインデックス削除鍵を生成する。
【数３】
【００７８】
一般に、ハッシュ関数Ｈは不可逆な一方向関数であり、得られたハッシュ値からは元データを生成することができない。そのため、通信の暗号化やデジタル署名などの分野で広く用いられている。なお、本発明は、ハッシュ関数Ｈの具体的な数式（あるいは論理式等）を定めるものではない。また、ハッシュ関数Ｈは、似た情報から近いハッシュ値が得られず、値域に偏りがなく、異なる情報から同じハッシュ値が容易に生成されないように定義されることが望ましい。
【００７９】
次に、制御部５０１は、ステップＳ１０６で生成したインデックス削除鍵を、通信部５０５を介して、各中間サーバ１０２に送信し（ステップＳ１０７）、鍵生成処理を終了する。
【００８０】
なお、上述の各種鍵を生成するための各数式等は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【００８１】
（暗号化処理）
次に、データ検索装置１０１の制御部２０１が、ＲＯＭ２０３に格納されるデータ暗号化プログラム２１０に従って、データベース２０４のインデックス（公開データ）及びデータ内容を暗号化する「暗号化処理」（図６のステップＳ７〜ステップＳ９に対応）について、図９のフローチャートを参照して説明する。
【００８２】
暗号化処理は、図６のステップＳ４で、制御部２０１が、Ｑｕｅｒｙ（暗号化鍵）を受信することよって開始される。
【００８３】
制御部２０１は、まず、利用者に選択されなかったデータのインデックスを暗号化するためのダミー鍵を生成しておく。ダミー鍵の生成には、ダミー鍵に対応する復号鍵を容易に作成できないように、例えば、離散対数問題等を利用する。
【００８４】
次に、制御部２０１は、受信したＱｕｅｒｙ（暗号化鍵）及び、生成したダミー鍵を用いて、データベース２０４に格納してあるデータ内容を暗号化する（ステップＳ２０１）。具体的には、制御部２０１は、中間サーバ１０２が公開した公開用共通パラメータ４１２に含まれる暗号化関数により、データベース２０４に格納してあるデータ内容を暗号化する。例えば、制御部２０１は、受信したＱｕｅｒｙ（ｐ，ｇ，ｙ−ｉ）から、全てのインデックスＩＮＤＥＸに対して暗号化鍵ｙ−ｉ＋ＩＮＤＥＸを計算する。また、乱数ｒ∈Ｚ＿ｐ−１を生成する。これらを用いて、データベース２０４のデータ内容をＥｌＧａｍａｌ暗号化方式を用いて暗号化する。
【００８５】
以上の暗号化により、データ内容を対応する復号鍵なしで、復号することは困難となる。また、ダミー鍵を設けて、全てのデータ内容を暗号化することで、データ検索装置１０１側から、利用者がどのデータを閲覧しようとしているのか知ることはできない。
【００８６】
上述の暗号化関数は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【００８７】
次に、制御部２０１は、ステップＳ２０１で行った暗号化とは別に、データベース２０４のインデックス（公開情報）を暗号化する（ステップＳ２０２）。具体的には、制御部２０１は、中間サーバ１０２に記憶される公開情報であるハッシュ関数Ｈ及び双線型写像ｅとを取得し、中間サーバ１０２が公開する公開情報Ｒ＿ｊ、利用者用端末１０３が所有する中間サーバ暗号鍵Ｓ＿ｊ及び利用者公開鍵Ｕ＿ｐｕｄ、データベース２０４のインデックスを用いて、数４に示す数式でインデックス（公開情報）を暗号化する。
【数４】
【００８８】
ステップＳ２０１、ステップＳ２０２にあるように、データ内容とインデックスを別にして暗号化することにより、インデックスとデータ内容を結合したまま暗号化する手法と比較して、セキュリティをより強化した暗号化方式となる。
【００８９】
さらに、制御部２０１は、データベース２０４に格納される順序を、ランダムに入れ替える（ステップＳ２０３）。例えば、制御部２０１は、一様乱数等を用いて各データにデータ順序を表す番号を割り振ればよい。これにより、ステップＳ２０２で暗号化されたインデックスを復号化しない限り、データベース２０４に格納された順序を知ることはできない。順序を知られないようにすることは、不正にデータを取得しようとする人等が、必要なデータを効率よく取得することができないようにする意図が含まれる。
続いて、制御部２０１は、暗号化処理を終了し、ＲＯＭ２０３に格納される送信プログラム２１１に従って、暗号化したデータを中間サーバ１０２へ送信する処理に移行する。
【００９０】
なお、上述の暗号化のための数式や手法等は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【００９１】
（削除・シャッフル処理）
次に、各中間サーバ１０２の制御部４０１が、ＲＯＭ４０３に格納される削除・シャッフルプログラム４１０に従って、他の中間サーバ１０２から転送された暗号化データを、削除・シャッフルする「削除・シャッフル処理」（図６のステップＳ１１〜ステップＳ１７に対応）について、図１０のフローチャートを参照して説明する。
【００９２】
削除・シャッフル処理は、図６のステップＳ１０で、制御部４０１が、暗号化データを受信することよって開始される。
【００９３】
制御部４０１は、先に図６のステップＳ６で利用者用端末１０３から受信したインデックス削除鍵Ｓｅａｒｃｈ＿ｊに基づいて、データ検索装置１０１から受信した暗号化インデックスＥ＿ＩＮＤＥＸの中から、削除対象のインデックスを検索する（ステップＳ３０１）。具体的には、制御部４０１は、数３で表すインデックス削除鍵Ｓｅａｒｃｈ＿ｊと、中間サーバ公開鍵ｒ＿ｊＰとを双線型写像ｅにより写像したビット列のハッシュ値ＨＫと一致する暗号化インデックスＥ＿ＩＮＤＥＸを検索する。ここでのハッシュ値ＨＫを数５に表す。また、中間サーバ公開鍵ｒ＿ｊＰは、制御部４０１が、記憶部４０４に記憶される公開情報Ｇ１上の任意の元Ｐと、中間サーバ固有の値ｒ＿ｊとし、Ｐのｒ＿ｊ倍の演算により生成される。
【数５】
【００９４】
ハッシュ値ＨＫは、各中間サーバ１０２において、削除対象のデータを特定するための条件値となる。また、暗号化インデックスＥ＿ＩＮＤＥＸ、インデックス削除鍵Ｓｅａｒｃｈ＿ｊは、ともに暗号化されているので、各中間サーバ１０２は、インデックスに関して何の情報も得ることができず、利用者のプライバシを保護する。
【００９５】
制御部４０１は、データ検索装置１０１から受信した全ての暗号化インデックスＥ＿ＩＮＤＥＸについて、上述したハッシュ値ＨＫと一致するか否かを判別していく。ここで、制御部４０１は、全ての暗号化インデックスＥ＿ＩＮＤＥＸが、ハッシュ値ＨＫと一致しないと判別した場合（ステップＳ３０２；Ｎｏ）、データ検索装置１０１から受信した暗号化データを削除せずに、ステップＳ３０５の処理に移行させる。
【００９６】
一方、制御部４０１は、暗号化インデックスＥ＿ＩＮＤＥＸの中に、ハッシュ値ＨＫと一致するインデックスが有ると判別した場合（ステップＳ３０２；Ｙｅｓ）、一致したインデックスと、そのインデックスに結合したデータ内容を削除する（ステップＳ３０３）。
【００９７】
また、制御部４０１は、削除した暗号化インデックスの数Ｄｅｌを記憶部４０４に記憶する（ステップＳ３０４）。各中間サーバ１０２で登録したこの削除数Ｄｅｌの値は、例えば、一つの中間サーバ１０２で集計される。
【００９８】
次に、制御部４０１は、ステップＳ３０３で削除したデータ以外のデータのインデックス、すなわち、記憶部４０４に残っているインデックスを、再度、暗号化する（ステップＳ３０５）。具体的には、制御部４０１は、削除・シャッフルプログラム４１０に従って、中間サーバ１０２に記憶される公開情報であるハッシュ関数Ｈ及び双線型写像ｅとを取得する。そして、中間サーバ１０２が公開する公開情報Ｒ＿ｊ、利用者用端末１０３が所有する中間サーバ暗号鍵Ｓ＿ｊ及び利用者公開鍵Ｕ＿ｐｕｄ、各暗号化インデックスを用いて、数６に示す数式でインデックス（公開情報）を暗号化する。
【数６】
【００９９】
ここでの暗号化において、各中間サーバ１０２は、他の中間サーバ１０２で暗号化されたインデックスに基づいて、インデックスを暗号化する。そして、数６で暗号化されたインデックスでなければ、ステップＳ３０１で、適切に、削除対象のインデックスを検索することができない仕組みになっている。
【０１００】
次に、制御部４０１は、暗号化データの記憶部４０４に記憶される順序を、ランダムに入れ替える（ステップ３０６）。例えば、制御部４０１は、一様乱数等を用いて各データにデータ順序を表す番号を割り振ればよい。
【０１０１】
続いて、制御部４０１は、各中間サーバ１０２のステップＳ３０４で集計してきた暗号化データの削除数Ｄｅｌを参照し、最後の中間サーバ（Ｎ）１０２であるか否かを判別する（ステップＳ３０７）。制御部４０１は、最後の中間サーバ（Ｎ）１０２ではないと判別した場合（ステップＳ３０７；Ｎｏ）、ＲＯＭ４０３に格納される転送プログラム４１１に従って、ＩＰアドレスを参照して、ｊ＋１番目の中間サーバ（ｊ＋１）１０２に、残っている暗号化データを転送する（ステップＳ３０８）。
【０１０２】
以上のステップＳ３０１からステップＳ３０８の処理を、各中間サーバ１０２が実行することにより、利用者に選択されなかったデータを各中間サーバ１０２で削除していく。そして、最後の中間サーバ（Ｎ）１０２には、利用者に選択されたデータだけが残る。
【０１０３】
一方、ステップＳ３０７で、制御部４０１は、最後の中間サーバ１０２であると判別した場合（ステップＳ３０７；Ｙｅｓ）、ＲＯＭ４０３に格納される転送プログラム４１１に従って、残っている暗号化データを、通信部４０５を介して利用者用端末１０３に転送する（ステップＳ３０９）。その後、制御部４０１は、削除・シャッフル処理を終了する。
【０１０４】
なお、上述の暗号化のための数式等は１つの例であり、これに限定されるものではなく種々の変形が可能である。
【０１０５】
（復号化処理）
次に、利用者用端末１０３の制御部５０１が、ＲＯＭ５０３に格納されるデータ復号化プログラム５１１に従って、中間サーバ（Ｎ）１０２から転送された暗号化データを復号化する「復号化処理」（図６のステップＳ１８に対応）について、図１１のフローチャートを参照して説明する。
【０１０６】
復号化処理は、図６のステップＳ１８で、制御部５０１が、暗号化データを受信することよって開始される。
【０１０７】
制御部５０１は、上述した鍵生成処理で生成した復号鍵（ｄ，ｎ）を用いて、受信した暗号化データを復号化する（ステップＳ４０１）。具体的には、制御部５０１は、中間サーバ１０２が公開した公開用共通パラメータ４１２に含まる復号化関数により、受信した暗号化データを復号化する。例えば、制御部５０１は、中間サーバ１０２からハッシュ関数Ｈを取得し、暗号化に用いた乱数Ｒ＿ＤＢ、別の乱数ｒ、ｉ（インデックス、又は、データ内容）を連結した値のハッシュ値ＨＢを求める。そして、このハッシュ値ＨＢと暗号化処理で求めた排他的論理和Ｅとの排他的論理和を求めることで、データを復号化する。
【０１０８】
上述したデータの暗号化・復号化に用いる鍵や、暗号化関数・復号化関数は、将来開発されるものも含めて任意のものでよい。
【０１０９】
次に、制御部５０１は、ＲＯＭ５０３に格納される表示プログラム５１２に従って、表示部５０６に、図７（Ｂ）に示すような、検索結果を表示させる（ステップＳ４０２）。
その後、制御部５０１は、復号化処理を終了する。
【０１１０】
このように、本実施形態のデータ検索システム１００によれば、プライバシの侵害を防御するためのプライバシ保護機能を強化して、データベースに蓄積したデータから所望のデータを検索できる効果が得られる。
【０１１１】
すなわち、データ検索装置１０１のデータベース２０４に格納されるデータのうち、インデックスとデータ内容とを、それぞれ別個に暗号化するため、データ間の関係性が秘匿され、データベース２０４のプライバシの保護は強化される。
【０１１２】
そして、暗号化データは、データ検索装置１０１と、利用者用端末１０３の間に配置された複数の中間サーバ１０２によって、暗号化データのシャッフルが繰り返されるために、中間サーバ１０２で暗号データが解読されても、利用者の選択したデータがどれであるか特定することは困難である。
【０１１３】
また、中間サーバ１０２によって、暗号化インデックスに基づいた削除が繰り返されるために、利用者用端末１０３に転送される暗号化データは、利用者が選択したデータに制限される。これにより、計算機の処理能力が向上して、利用者が選択したデータ以外のデータ内容が他人に知られてしまうようなプライバシの侵害を防ぐ効果がある。
【０１１４】
さらに、中間サーバ１０２において、削除対象のデータは、インデックス削除鍵に基づいて削除され、インデックスも暗号化されている。これにより、中間サーバ１０２から、インデックスに関する情報を得ることはできないため、利用者のプライバシの保護は強化される。
【０１１５】
この発明は上記実施の形態に限定されず、種々の変形及び応用が可能である。
【０１１６】
例えば、鍵生成処理で生成される各種鍵（暗号化鍵、復号化鍵、インデックス削除鍵）に有効期限を設定し、この有効期限内の場合にのみ、この各種鍵を用いた復号化ができるように構成することもできる。
この場合、例えば、利用者用端末１０３の制御部５０１は、暗号化鍵、復号化鍵、インデックス削除鍵に有効期限を含めて生成する。利用者用端末１０３の制御部５０１は、復号化処理を開始するときに有効期限が過ぎていれば復号を許可しないようにすればよい。
これにより、生成した各種鍵が本来の所有者の意に反して流出した場合でも、有効期限を過ぎていれば復号化ができないようにすることができ、データベースのデータや利用者が選択した情報の機密性を強化することができる。
【０１１７】
また、例えば、中間サーバ１０２に記憶される公開用共通パラメータ４１２を、定期的に変更するように構成することもできる。
この場合、中間サーバ１０２の制御部４０１は、所定のタイミング（例えば、１週間など）で、ハッシュ関数Ｈ、双線型写像ｅ及び公開情報Ｇ１のうちの一部又は全部を設定し直せばよい。また、データ検索装置１０１、中間サーバ１０２及び利用者用端末１０３は、上述の各処理を開始するときに逐次これらの公開用共通パラメータ４１２のセットを取り込み直して用いればよい。あるいは、制御部４０１は、公開用共通パラメータ４１２を設定し直したタイミングで、データ検索装置１０１、中間サーバ１０２及び利用者用端末１０３に公開用共通パラメータ４１２が再設定された旨の通知を行って、公開用共通パラメータ４１２の再取得を促す（あるいは自動的に取得する）ようにすればよい。
これにより、データ検索システム１００内でのデータの機密性を強化することができる。
【０１１８】
上記実施形態では、各中間サーバ１０２が削除する暗号化データの数は均等になるようにしていた。しかしながら、これに限定されず、処理能力の高い中間サーバ１０２に、多くの暗号化データを削除させるようにしてもよい。
【０１１９】
また、上記実施形態では、暗号化データを転送する中間サーバ１０２の順番については述べなかった。暗号化データは、各中間サーバ１０２間で、削除しながら転送されていくので、中間サーバ１０２が処理しなければならないデータ数はしだいに減少していく。そこで、暗号化データを転送する中間サーバ１０２の順番を、処理能力の高い中間サーバ１０２が最初にくるようにしてもよい。
【０１２０】
さらに、上記実施形態では、中間サーバ１０２が複数台（Ｎ台）の場合について説明したが、中間サーバ１０２は、１台であってもよい。中間サーバ１０２が１台の場合、１台の中間サーバ１０２が上述した削除・シャッフル処理を一度実施するか、複数回実施すればよい。
【０１２１】
また、上記実施形態では、公開用共通パラメータ４１２は中間サーバ１０２の記憶部４０４に格納していた。しかしながら、これに限定されず、公開用共通パラメータ４１２を、ネットワーク１０４に接続された他のサーバ等に格納して、公開するようにしてもよい。
【０１２２】
上記実施形態では、プログラムがＲＯＭ２０３、ＲＯＭ４０３及びＲＯＭ５０３等に予め記憶されているものとして説明した。しかし、データ検索装置１０１、中間サーバ１０２、利用者用端末１０３を、各々の全部又は一部として動作させ、あるいは、上述の処理を実行させるためのプログラムを、メモリカード、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory）、ＤＶＤ（Digital Versatile Disk）、ＭＯ（Magneto Optical disk）などのコンピュータ読み取り可能な記録媒体に格納して配布し、これを別のコンピュータにインストールし、上述の手段として動作させ、あるいは、上述の工程を実行させてもよい。
【０１２３】
さらに、インターネット上のサーバ装置が有するディスク装置等にプログラムを格納しておき、例えば、搬送波に重畳させて、コンピュータにダウンロード等するものとしてもよい。
【図面の簡単な説明】
【０１２４】
【図１】本実施形態に係るデータ検索システムの構成を説明するための図である。
【図２】データ検索装置の構成を説明するためのブロック図である。
【図３】データ検索装置のデータベースに記憶される情報の例を示す図である。
【図４】中間サーバの構成を説明するためのブロック図である。
【図５】利用者用端末の構成を説明するためのブロック図である。
【図６】本実施形態に係るデータ検索システムの全体の動作を説明するための図である。
【図７】（Ａ）はデータ選択画面の表示例を示す図である。（Ｂ）は検索結果の表示例を示す図である。
【図８】データ選択による割り込み入力によって開始する鍵生成処理を説明するためのフローチャートである。
【図９】暗号化鍵を受信することによって開始する暗号化処理を説明するためのフローチャートである。
【図１０】暗号化データを受信することによって開始する削除・シャッフル処理を説明するためのフローチャートである。
【図１１】暗号化データを受信することによって開始する復号化処理を説明するためのフローチャートである。
【符号の説明】
【０１２５】
１００ データ検索システム
１０１ データ検索装置
１０２ 中間サーバ
１０３ 利用者用端末
１０４ ネットワーク
２０１ 制御部（データ検索装置）
２０３ ＲＯＭ（データ検索装置）
２０４ データベース
２１０ データ暗号化プログラム
４０１ 制御部（中間サーバ）
４０３ ＲＯＭ（中間サーバ）
４１０ 削除・シャッフルプログラム
４１２ 公開用共通パラメータ
５０１ 制御部（利用者用端末）
５０３ ＲＯＭ（利用者用端末）
５０６ 表示部
５０７ 入力部
５１０ 鍵生成プログラム
５１１ データ復号化プログラム
【特許請求の範囲】
【請求項１】
第１の情報処理装置と、第２の情報処理装置と、第３の情報処理装置と、から構成されるデータ検索システムであって、
前記第１の情報処理装置は、
情報を記憶するデータベースと、
前記データベースに記憶されている情報のインデックスを前記第２の情報処理装置に公開するインデックス公開手段と、
を備え、
前記第２の情報処理装置は、
前記インデックスを取得し、取得したインデックスの少なくとも一部に対応する暗号鍵及び復号鍵を生成する暗号鍵・復号鍵生成手段と、
前記第３の情報処理装置が前記情報を削除するために必要な削除鍵を生成する削除鍵生成手段と、
前記暗号鍵・復号鍵生成手段が生成した暗号鍵を前記第１の情報処理装置に送信する暗号鍵送信手段と、
前記削除鍵生成手段が生成した削除鍵を前記第２の情報処理装置に送信する削除鍵送信手段と、
を備え、
前記第１の情報処理装置は、さらに、
前記暗号鍵送信手段が送信した暗号鍵を受信し、受信した暗号鍵に基づいて、前記データベースに記憶される情報を暗号化する暗号化手段と、
前記暗号化手段が暗号化した暗号化情報を前記第３の情報処理装置に送信する暗号化情報送信手段と、
を備え、
前記第３の情報処理装置は、
前記暗号化情報送信手段が送信した暗号化情報を受信する暗号化情報受信手段と、
前記削除鍵送信手段が送信した削除鍵を受信する削除鍵受信手段と、
前記削除鍵受信手段が受信した削除鍵に基づいて、前記暗号化情報受信手段が受信した暗号化情報の所定数の情報を削除する情報削除手段と、
前記情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信する入れ替え情報送信手段と、
を備え、
前記第２の情報処置装置は、さらに、
前記入れ替え情報送信手段が送信した情報を受信し、前記暗号鍵・復号鍵生成手段が生成した復号鍵に基づいて、受信した前記情報を復号化する復号化手段と、
を備える、
ことを特徴とするデータ検索システム。
【請求項２】
前記第３の情報処理装置は、複数の装置から構成され、
前記情報順序入れ替え手段が情報を入れ替えた後、前記情報の残数が前記暗号鍵・復号鍵生成手段が取得したインデックスの少なくとも一部に対応するインデックス数と等しいか否かを判別する残数判別手段と、
前記残数判別手段が、前記情報の残数が前記インデックス数と等しいと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信し、前記残数判別手段が、前記情報の残数が前記インデックス数と等しくないと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を別の前記第３の情報処理装置に送信する第２の入れ替え情報送信手段と、
を備えることを特徴とする請求項１に記載のデータ検索システム。
【請求項３】
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手段と、
前記削除鍵記憶手段が記憶する削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手段と、
前記暗号化情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
を備えることを特徴とする情報処理装置。
【請求項４】
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶ステップと、
前記削除鍵記憶ステップで記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除ステップと、
前記暗号化情報削除ステップで情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替えステップと、
を備えることを特徴とするデータ検索方法。
【請求項５】
コンピュータに、
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手順と、
前記削除鍵記憶手順で記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手順と、
前記暗号化情報削除手順で情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手順と、
を実行させるプログラム。
【請求項１】
第１の情報処理装置と、第２の情報処理装置と、第３の情報処理装置と、から構成されるデータ検索システムであって、
前記第１の情報処理装置は、
情報を記憶するデータベースと、
前記データベースに記憶されている情報のインデックスを前記第２の情報処理装置に公開するインデックス公開手段と、
を備え、
前記第２の情報処理装置は、
前記インデックスを取得し、取得したインデックスの少なくとも一部に対応する暗号鍵及び復号鍵を生成する暗号鍵・復号鍵生成手段と、
前記第３の情報処理装置が前記情報を削除するために必要な削除鍵を生成する削除鍵生成手段と、
前記暗号鍵・復号鍵生成手段が生成した暗号鍵を前記第１の情報処理装置に送信する暗号鍵送信手段と、
前記削除鍵生成手段が生成した削除鍵を前記第２の情報処理装置に送信する削除鍵送信手段と、
を備え、
前記第１の情報処理装置は、さらに、
前記暗号鍵送信手段が送信した暗号鍵を受信し、受信した暗号鍵に基づいて、前記データベースに記憶される情報を暗号化する暗号化手段と、
前記暗号化手段が暗号化した暗号化情報を前記第３の情報処理装置に送信する暗号化情報送信手段と、
を備え、
前記第３の情報処理装置は、
前記暗号化情報送信手段が送信した暗号化情報を受信する暗号化情報受信手段と、
前記削除鍵送信手段が送信した削除鍵を受信する削除鍵受信手段と、
前記削除鍵受信手段が受信した削除鍵に基づいて、前記暗号化情報受信手段が受信した暗号化情報の所定数の情報を削除する情報削除手段と、
前記情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信する入れ替え情報送信手段と、
を備え、
前記第２の情報処置装置は、さらに、
前記入れ替え情報送信手段が送信した情報を受信し、前記暗号鍵・復号鍵生成手段が生成した復号鍵に基づいて、受信した前記情報を復号化する復号化手段と、
を備える、
ことを特徴とするデータ検索システム。
【請求項２】
前記第３の情報処理装置は、複数の装置から構成され、
前記情報順序入れ替え手段が情報を入れ替えた後、前記情報の残数が前記暗号鍵・復号鍵生成手段が取得したインデックスの少なくとも一部に対応するインデックス数と等しいか否かを判別する残数判別手段と、
前記残数判別手段が、前記情報の残数が前記インデックス数と等しいと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を前記第２の情報処理装置に送信し、前記残数判別手段が、前記情報の残数が前記インデックス数と等しくないと判別した場合、前記情報順序入れ替え手段が入れ替えた情報を別の前記第３の情報処理装置に送信する第２の入れ替え情報送信手段と、
を備えることを特徴とする請求項１に記載のデータ検索システム。
【請求項３】
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手段と、
前記削除鍵記憶手段が記憶する削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手段と、
前記暗号化情報削除手段が情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手段と、
を備えることを特徴とする情報処理装置。
【請求項４】
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶ステップと、
前記削除鍵記憶ステップで記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除ステップと、
前記暗号化情報削除ステップで情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替えステップと、
を備えることを特徴とするデータ検索方法。
【請求項５】
コンピュータに、
暗号化された暗号化情報を削除するために必要な削除鍵を記憶する削除鍵記憶手順と、
前記削除鍵記憶手順で記憶した削除鍵に基づいて、前記暗号化情報の所定数の情報を削除する暗号化情報削除手順と、
前記暗号化情報削除手順で情報を削除した後、削除されずに残った情報の順序を入れ替える情報順序入れ替え手順と、
を実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００７−１２４５２０（Ｐ２００７−１２４５２０Ａ）
【公開日】平成１９年５月１７日（２００７．５．１７）
【国際特許分類】
【出願番号】特願２００５−３１６８６５（Ｐ２００５−３１６８６５）
【出願日】平成１７年１０月３１日（２００５．１０．３１）
【出願人】（０００１０２７２８）株式会社エヌ・ティ・ティ・データ (438)
【Ｆターム（参考）】
【公開日】平成１９年５月１７日（２００７．５．１７）
【国際特許分類】
【出願日】平成１７年１０月３１日（２００５．１０．３１）
【出願人】（０００１０２７２８）株式会社エヌ・ティ・ティ・データ (438)
【Ｆターム（参考）】
[ Back to top ]