JP3907184B2 - データベース検索システム及びデータ共有システム - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、データベース検索システムに関し、特に所定のデータベースが所定のデータを保有しているか否かを検索するシステムに関する。
【０００２】
【従来の技術】
ネットワーク上のサービスとして、データベースに格納されたデータの検索を提供するサービスがある。データベースを利用しようとするクライアントは、ネットワーク上のデータベースサーバに検索要求（query）を送信して所望のデータがデータベースに存在するかどうかを問い合わせ、検索結果を受け取る。
【０００３】
このようなデータベースの利用法において、データベースが特定の情報を持っているかどうかのみを検索したい場合がある。この場合、データベース側では、検索要求に対し、要求されたデータを返すのではなく、当該データがあるかないかを回答する。このような状況としては、例えば、複数の技術データベースがある場合に、特定の技術情報がどの技術データベースに格納されているかを知りたい場合などが考えられる。もし、いずれかの技術データベースに所望のデータが存在することがわかれば、当該データを持つ技術データベースに対して当該データを送ってもらうように別途依頼することができる。
【０００４】
このようなシステムでは、検索要求を出すシステムのクライアント側の検索要求に関するプライバシー及びデータベースのセキュリティが問題となる。
検索要求のプライバシー：検索要求にはユーザの興味に関する情報が含まれている。例えば、同業他社の持つ技術データベースを検索する場合、当該他社に対して自社がどのような技術に興味を抱いているかを知られることは、経営戦略上大きな問題と成り得る。一方、同業者間で共有できるデータベースを公開することは、業界の活性化につながるため、検索要求の内容を秘匿したまま他社のもつデータベースを検索できれば、利用性が高いと考えられる。
データベースのセキュリティ：データベースの保有者の側からも秘匿性が重要となる場合がある。例えば、データベースに対してデータを検索し入手する際に課金を伴うシステムがある。このようなシステムにおいて、アクセス回数に応じて課金がなされる場合、一回の検索で制限なくデータベース内のデータを取得されると課金の意義がなくなるので問題がある。また、課金を伴わない場合でも、保有しているデータベースの内容自体が、データベース保有者の興味や戦略に関する情報を含むため、必要以上の検索結果をユーザに与えないようにすることが好ましい。
【０００５】
従来、この種の技術としては、いくつかのプロトコルが提案されている。
データベースに格納されているデータのリストＬｉ及び検索したいデータ番号αの値自体を秘匿してデータベース検索を行うことを目的とするなら、一方向性ハッシュ関数Ｈを用いた手法を用いることができる。図８は、この従来手法を説明する図である。つまり、データベースサーバＳｉは、リストＬｉ＝｛ｘ_i,0，．．．，ｘ_i,n-1｝をクライアントＡに秘匿し、かつクライアントＡはαを秘匿する状況を考える。この時、データベースサーバＳｉは、Ｌ'_i＝｛Ｈ（ｘ_i,0），．．．，Ｈ（ｘ_i,n-1）｝をクライアントＡに与えて、クライアントＡがＨ（α）と一致するものがあるかを調べる（Ｈ(・)は一方向性ハッシュ関数）。この場合、クライアントＡもデータベースサーバＳｉも、互いにデータ番号自体を教える必要がない。
【０００６】
また、別の手法として、次の文献１に開示された、紛失多項式計算（Oblivious Polynomial Evaluation、以後、ＯＰＥと略す）を用いた手法がある。これは、入力を秘密にしたまま、関数に代入した結果だけを受け取るという性質を持つプロトコルである。
文献１：Naor, M. and Pinkas, B., "Oblivious Transfer and Polynomial Evaluation," Proc. of STOC '99.
この手法は、より具体的には次のような性質を持つ。秘密の値αを持つ受信者Ａ、及び秘密の多項式ｆ(ｘ)を持つ送信者Ｂがいる。ＯＰＥプロトコルを実行することにより、受信者Ａは多項式ｆ(α)を知ることができるが、α以外の入力β（≠α）に対するｆ(β)に関する一切の情報を得ることができない。一方、送信者Ｂは、ＯＰＥプロトコル実行後も、αを知ることはできない。
【０００７】
図９は、文献１の従来手法を説明する図である。初めに、クライアントＡ及びデータベースサーバＳｉは、それぞれランダムなｎ次多項式ｆ_A(ｘ)，ｆ_Si(ｘ)を選ぶ。クライアントＡは、データベースサーバＳｉからｆ_Si(α)をＯＰＥにより得る。データベースサーバＳｉは、ＯＰＥにより、ｆ_A(ｘ_i,0)，．．．，ｆ_A(ｘ_i,n-1)を得る。データベースサーバＳｉは、クライアントＡに対し、Ｌ'_i＝｛ｆ_Si(ｘ_i,0)＋ｆ_A(ｘ_i,0)，．．．，ｆ_Si(ｘ_i,n-1)＋ｆ_A(ｘ_i,n-1)｝を送る。クライアントＡは、
【数１】

を計算し、
【数２】

かどうかを調べることにより、α∈Ｌ_iを調査することができる。この方法では、α∈Ｌ_i に関して余分な情報は一切露呈しない。
【０００８】
また、次の文献２には、Decisional Diffie-Hellman（ＤＤＨ）問題に基づく特殊な形のＯＰＥに対するプロトコルが示されている。
文献２：Lindell, Y. and Pinkas, B., "Privacy Preserving Data Mining," Proc. of CRYPTO2000, LNCS.
ＤＤＨ問題とは、ｇ，ｈ∈ＧＦ(ｑ)、ａ，ｂ∈Ｚ_qをランダムに選んだとき、ＧＦ(ｑ)上において、Ｄ＝＜ｇ，ｈ，ｇ^a，ｈ^a＞（この形を「Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎの組」と呼ぶ）と、Ｒ＝＜ｇ，ｈ，ｇ^a，ｈ^b＞を有意な確率を持って区別する判定問題である。この問題をｑのサイズの多項式時間で解くアルゴリズムは知られていない。これにより、暗号の安全性を帰着する手段として頻繁に用いられる。文献２に開示されたＯＰＥを用いた手法は、クライアントＡの入力αに対して、多項式ｆ(ｘ)を持つＢが（ｆ(ｘ)そのものではなく）ｇ^f(x)を返す点が文献１に記載された手法と異なる。
【０００９】
【発明が解決しようとする課題】
上記のように、データベースに対して検索要求を行う場合において、検索要求のプライバシーやデータベースのセキュリティを考慮した検索手法は、従来から提案がなされているが、それぞれ、次のような欠点があった。
一方向性ハッシュ関数を用いた従来手法は、クライアントＡが、無制限に様々なアイテムに対する検索を行うことが可能であった。例えば、クライアントＡが、α'（≠α）がリストＬ_iに含まれているかどうかを知りたい場合、Ｈ（α'）∈Ｌ'_iを調べれば良い。これを繰り返すことにより、クライアントＡは、最終的にはリストＬｉに何が含まれるのかを絞ることが可能である。すなわち、データベースの秘匿性（セキュリティ）の実現性に問題があった。
【００１０】
また、ＯＰＥを用いた従来手法は、図９に示したように、検索要求のプライバシーやデータベースのセキュリティを確保した通信を行うために、４回以上の通信パスを必要とする。このため、非常に大きな通信コストを必要とし、処理が煩雑になるという問題があった。
【００１１】
そこで、本発明は、検索要求のプライバシーやデータベースのセキュリティを確保し、かつ処理効率の高いデータベース検索システムを提供することを目的とする。
【００１２】
【課題を解決するための手段】
上記の目的を達成する本発明は、次のように構成されたデータベース検索システムとして提供される。すなわち、このデータベース検索システムは、ネットワーク上に設けられた所定のデータを格納したデータベースサーバと、このデータベースサーバに対し所望のデータの有無に関する検索要求をこの所望のデータを秘匿して行うクライアント端末とを備える。
そして、このデータベースサーバは、所定のデータを格納したデータベースと、ネットワークを介して検索対象であるデータ自体が秘匿されたデータの検索要求を取得し、この検索要求及びデータベースに格納されたデータのリストに基づいて、この検索要求にかかるデータ項目を秘匿したまま所定の計算によりデータベース検索を行い、この検索要求に対する応答を生成する検索応答メッセージ生成部とを備えることを特徴とする。
具体的には、このデータベースサーバの検索応答メッセージ生成部は、ネットワークを介して所定のデータの検索要求を取得し、この検索要求及びデータベースに格納されたデータのリストに基づいて、この検索要求にかかるデータ項目を根とする多項式を生成し、かかるデータ項目をこの多項式に代入した結果が０になるという評価問題を紛失多項式計算（Oblivious Polynomial Evaluation）にて解き、この検索要求に対する応答を生成する。
さらに好ましくは、このデータベースサーバの検索応答メッセージ生成部は、乱数を用いて前記多項式をランダムに生成する。
一方、このクライアント端末は、所望のデータを暗号化し、データベースサーバに対して所望のデータの有無を問い合わせる検索要求を生成する検索要求メッセージ生成部と、紛失多項式計算（Oblivious Polynomial Evaluation）により得られた検索要求に対する評価結果をデータベースサーバから受信し、この評価結果に基づいてデータベースサーバが所望のデータを保有するか否かを示す情報を取得する検索結果判定部とを備えることを特徴とする。
【００１３】
また、上記の目的を達成する他の本発明は、ピア・ツー・ピア（Peer-to-Peer）型のネットワークシステムでデータを共有する、次のように構成されたデータ共有システムとしても実現される。このデータ共有システムは、他のピアに対して所望のデータの有無に関する検索要求をこの所望のデータを秘匿して行う第１のピアと、この第１のピアから受信した検索要求及び自装置が持つデータベースに格納されたデータのリストに基づいて、検索要求に含まれる所望のデータを秘匿したまま所定の計算によりデータベース検索を行い、得られた検索結果を第１のピアに送信することを特徴とする第２のピアとを備えたことを特徴とする。
ここで、ピア・ツー・ピア型のネットワークにおけるピアは、そのいずれもが上述した第１のピアとなることが可能である。また、この場合、その他のピア（特に制限が設定されていない限り、通常は全てのピア）が上述した第２のピアとなる。
第２のピアは、より詳しくは、第１のピアから受信した検索要求及び自装置が持つデータベースに格納されたデータのリストに基づいて、検索要求にかかるデータ項目を根とする多項式を生成し、このデータ項目をこの多項式に代入した結果が０になるという評価問題を解き、得られた評価結果を第１のピアに送信する。
【００１４】
上記の目的を達成するさらに他の本発明は、所定のデータを格納したデータベースに対して、所望のデータの有無を検索する、次のようなデータ検索方法として実現される。このデータ検索方法は、データベースに対して所望のデータの有無を問い合わせる検索要求を生成するステップと、この検索要求及びデータベースに格納されたデータのリストに基づいて、この検索要求にかかるデータ項目を根とする多項式を生成し、このデータ項目をこの多項式に代入した結果が０になるという評価問題を解くステップと、評価結果に基づいてデータベースに所望のデータが格納されているか否かを示す情報を求めるステップとを含むことを特徴とする。
【００１５】
また、本発明の他のデータ検索方法は、第１の鍵を用いて所望のデータを暗号化し、データベースに対してかかる所望のデータの有無を問い合わせる検索要求を生成するステップと、この検索要求及びデータベースに格納されたデータのリストに基づいて、検索要求に含まれる所望のデータを秘匿したまま所定の計算によりデータベース検索を行うステップと、データベース検索の結果に基づいて第１の鍵に対応する第２の鍵を用いた所定の計算を行うことにより、データベースに所望のデータが格納されているか否かを示す情報を求めるステップとを含むことを特徴とする。
【００１６】
さらに本発明は、コンピュータを制御して上述したデータベースサーバあるいはクライアント端末（端末装置）として機能させるプログラムとして実現することができる。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより、提供することができる。
【００１７】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
図１は、本実施の形態によるデータベース検索システムの概略構成を説明する図である。
図１を参照すると、本実施の形態のデータベース検索システムは、データベースサーバ１０と、クライアント端末２０とを備える。
データベースサーバ１０は、ネットワークを介してデータベースに格納されたデータの検索サービスを提供するサーバである。
クライアント端末２０は、データベースサーバ１０のサービスに対するクライアントが使用する端末装置であり、データベースサーバ１０に対して所望のデータを保有しているかどうかを調べるための検索要求を当該データベースサーバ１０に対して行う。
【００１８】
本実施の形態において、データベースサーバ１０は、ワークステーションやパーソナルコンピュータ、その他のネットワーク機能を備えたコンピュータ装置にて実現される。また、クライアント端末２０は、ワークステーションやパーソナルコンピュータ、ＰＤＡ（personal digital assistants）その他のネットワーク機能を備えた情報処理装置にて実現される。これらの装置は、図示しないネットワークを介してメッセージの交換を行う。ネットワークの通信回線は有線であると無線であるとを問わない。
なお、図示のように、本実施の形態では、Ｎ個のデータベースサーバ１０が存在し、クライアント端末２０は、当該Ｎ個のデータベースサーバ１０に対してブロードキャストにより検索要求を送信する。そこで以下の説明では、必要に応じて、各データベースサーバ１０に対して１〜Ｎの添字を加えてデータベースサーバ１０１、・・・、１０Ｎのように表記する。また、個々のデータベースサーバ１０１、・・・、１０Ｎを区別しないときには、データベースサーバ１０ｉ（１≦ｉ≦Ｎ）のように表記する。
【００１９】
図７は、本実施の形態によるデータベースサーバ１０ｉ及びクライアント端末２０を実現するのに好適なコンピュータ装置のハードウェア構成の例を模式的に示した図である。
図７に示すコンピュータ装置は、演算手段であるＣＰＵ（Central Processing Unit：中央処理装置）７０１と、Ｍ／Ｂ（マザーボード）チップセット７０２及びＣＰＵバスを介してＣＰＵ７０１に接続されたメインメモリ７０３と、同じくＭ／Ｂチップセット７０２及びＡＧＰ（Accelerated Graphics Port）を介してＣＰＵ７０１に接続されたビデオカード７０４と、ＰＣＩ（Peripheral Component Interconnect）バスを介してＭ／Ｂチップセット７０２に接続されたハードディスク７０５、ネットワークインターフェイス７０６及びＵＳＢポート７０７と、さらにこのＰＣＩバスからブリッジ回路７０８及びＩＳＡ（Industry Standard Architecture）バスなどの低速なバスを介してＭ／Ｂチップセット７０２に接続されたフロッピーディスクドライブ７０９及びキーボード／マウス７１０とを備える。
なお、図１は本実施の形態を実現するコンピュータ装置のハードウェア構成を例示するに過ぎず、本実施の形態を適用可能であれば、他の種々の構成を取ることができる。例えば、ビデオカード７０４を設ける代わりに、ビデオメモリのみを搭載し、ＣＰＵ７０１にてイメージデータを処理する構成としても良いし、ＡＴＡ（AT Attachment）などのインターフェイスを介してＣＤ−ＲＯＭ（Compact Disc Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disc Read Only Memory）のドライブを設けても良い。
【００２０】
図２は、本実施の形態におけるデータベースサーバ１０ｉ及びクライアント端末２０の構成を示す図である。
図２を参照すると、クライアント端末２０は、後述する検索要求メッセージ生成アルゴリズムＧにより、検索項目であるデータ番号（データベースサーバ１０が保有するデータに振られた番号）αから検索要求メッセージｒｅｑを生成する検索要求メッセージ生成部２１と、同じく後述する検索結果判定アルゴリズムＤにより、データベースサーバ１０ｉから受信した検索応答メッセージａｎｓ_iに基づいて検索結果である１または０の値を出力する検索結果判定部２２とを備える。これら検索要求メッセージ生成部２１及び検索結果判定部２２は、クライアント端末２０を構成する情報処理装置におけるプログラム制御されたＣＰＵにて実現される仮想的なソフトウェアブロックである。また、特に図示しないが、クライアント端末２０は、プログラム制御されたＣＰＵ及びネットワークインターフェイスにて実現される送受信手段を備える。ＣＰＵを制御するプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。また、データベースサーバ１０ｉは、データベース１１と、後述する検索応答メッセージ生成アルゴリズムＲにより、検索要求メッセージｒｅｑ及びデータベース１１に格納されているデータのリストとに基づいて検索応答メッセージａｎｓ_iを生成する検索応答メッセージ生成部１２とを備える。このうち、データベース１１は、データベースサーバ１０を構成するコンピュータ装置の記憶装置（磁気ディスク装置や光ディスク装置など）にて実現される。また、検索応答メッセージ生成部１２は、当該コンピュータ装置におけるプログラム制御されたＣＰＵにて実現される仮想的なソフトウェアブロックである。また、特に図示しないが、データベースサーバ１０ｉは、プログラム制御されたＣＰＵ及びネットワークインターフェイスにて実現される送受信手段を備える。ＣＰＵを制御するプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
【００２１】
次に、本実施の形態によるリスト検索（データベース検索）を定式化する。
データベースサーバ１０ｉの集合（以下、サーバ集合と称す）をＳ＝｛１０１，．．．，１０Ｎ｝とする。各データベースサーバ１０１、・・・、１０Ｎは、それぞれｎ個のデータをデータベースに保持しているものとし、全てのデータには一意に区別できるデータ番号が割り振られているものとする。また、データ番号全体の集合をＬとする。データベース１１に格納されているｎ個のデータのデータ番号のリストをＬ_i＝｛ｘ_i,0，．．．，ｘ_i,n-1｝とする。
さらに、次の３つのアルゴリズムの記述を用いる。
・Ｇ（α）：検索要求メッセージ生成アルゴリズムであり、データ番号α（∈Ｌ）を入力として検索要求メッセージｒｅｑを出力する。
・Ｒ（ｒｅｑ，Ｌ_i）：検索応答メッセージ生成アルゴリズムであり、検索要求メッセージｒｅｑ及びデータベース１１の保持するリストＬ_iを入力として、検索応答メッセージａｎｓ_iを出力する。
・Ｄ（ａｎｓ_i）：検索結果判定アルゴリズムであり、検索応答メッセージａｎｓ_iを入力として、検索結果｛０，１｝を出力する。ここで、ｒｅｑ＝Ｇ（α），ａｎｓ_i＝Ｒ（ｒｅｑ，Ｌ_i）としたとき、α∈Ｌ_iならば１を、そうでないならば０を出力する
【００２２】
以上の定義に基づいて、本実施の形態が対象とする「リスト検索」は、次のように定式化される。
１．クライアント端末２０による検索要求メッセージの生成・送信
（ａ）クライアント端末２０は、検索を希望するデータのデータ番号α∈Ｌを選択する。
（ｂ）クライアント端末２０は、検索要求メッセージ生成アルゴリズムＧを用いて、αを検索するための検索要求メッセージｒｅｑ＝Ｇ（α）を生成し、サーバ集合Ｓ全体に送信する。
２．データベースサーバ１０ｉによる検索応答メッセージの生成・送信
検索要求メッセージｒｅｑを受け取った各データベースサーバ１０１，．．．，１０Ｎは、各々次の処理を行う。データベースサーバ１０ｉは、検索要求メッセージｒｅｑ及びリストＬ_iから、検索応答メッセージ生成アルゴリズムＲを用いて、検索応答メッセージａｎｓ_i＝Ｒ（ｒｅｑ，Ｌ_i）を生成し、クライアント端末２０に送信する。
３．クライアント端末２０による検索結果判定
検索応答メッセージａｎｓ_iを受け取ったクライアント端末２０は、検索結果判定アルゴリズムＤを用いて、ｒｅｓ_i＝Ｄ（ａｎｓ_i）を得る。
【００２３】
上記の定式化に基づき、本実施の形態では、次に挙げる３つの条件を満たす「リスト検索」の（１）検索要求メッセージ生成アルゴリズムＧ、（２）検索応答生成アルゴリズムＲ、（３）検索結果判定アルゴリズムＤ、を示す。
要件１．任意のデータベースサーバ１０ｉは、検索要求メッセージｒｅｑ＝Ｇ（α）から検索対象のデータ番号αに関する情報を一切得ることができない。
要件２．クライアント端末２０は、検索要求メッセージｒｅｑ＝Ｇ（α）に対してデータベースサーバ１０ｉから送られる検索応答メッセージａｎｓ_iから、α∈Ｌ_iが成立するか否か以外の情報を一切得ることはできない。
要件３．検索要求メッセージｒｅｑのサイズは、検索要求を受信するデータベースサーバ１０ｉの数Ｎに依存しない。
以上の３つの性質を満たす「リスト検索」を、「検索要求を秘匿した秘密リスト検索」と呼ぶ。
【００２４】
上述した要件１は、クライアント端末２０がどのデータ番号を検索しているかという情報を、データベースサーバ１０ｉが検索要求メッセージから知ることを防ぐ要件であり、クライアント端末２０のプライバシーを保護するために必要となる。要件２は、クライアント端末２０に対してデータベースサーバ１０ｉが持つリストに関する情報を必要以上に与えることを防ぐ要件であり、データベースサーバ１０ｉの持つデータベースの秘匿性を実現するために必要となる。要件３は、効率上の要件である。リスト検索の性質上、クライアント端末２０が希望するデータ番号にマッチするデータを持つデータベースサーバ１０ｉを特定するため、ネットワーク上の多くのデータベースサーバ１０ｉに問い合わせる必要がある。検索要求メッセージのサイズがデータベースサーバ１０ｉの数に依存しないならば、非常に多くのデータベースサーバ１０ｉに対して検索要求を送ることが可能となるので、要件３はサービスのスケーラビリティの観点から強く望まれる性質である。
【００２５】
本実施の形態は、「検索要求を秘匿した秘密リスト検索」を実現するとともに、上述した３要件全てを解決する。以下では、次のパラメータを用いる。ｐ及びｑは、ｑ｜ｐ−１を満たす大きな素数であり、ｇは、有限体Ｚ_p上の位数ｑの元とする。ｐ及びｑのサイズは、ｇを生成元として構成される群ＧＦ(ｑ)上での離散対数問題が計算量的に困難であるように設定するものとする。また、以下の説明において特に記述のない場合、演算は全てｍｏｄ ｐ上で行われるものとする。なお、位数ｐの素体の上での構成法以外にも、本発明で示される構成法は離散対数問題が計算量的に困難となるような任意の群ＧＦ(ｑ)上で定義される。例えば（１）位数ｐの素体上での乗法演算を、任意の有限体上の楕円曲線などの曲線上の加法演算に対応させることにより構成される群、（２）前記素数ｐに代えて素数ｐ'のべき乗数とし、前記素数ｐ'を法とする剰余演算に代えてＧＦ(ｐ')の拡大体上での演算を行うことにより構成される群、などがある。
【００２６】
図３は、本実施の形態によるリスト検索の概念を説明する図である。
図３に示すように、本実施の形態では、次の手順で上述のリスト検索を実現する。
１．データベースサーバ１０ｉは、自分の持つデータ番号ｘ_i,0，．．．，ｘ_i,n-1を根に持つようなｎ次の多項式ｆ_Si(ｘ)を作る（すなわち、ｊ＝０，．．．，ｎ−１に対してｆ_Si(ｘ_i,j)＝０）。
２．クライアント端末２０は、データベースサーバ１０ｉがα（∈Ｌ_i）を持っているかどうかを知るために、ＯＰＥを用いて、サーバ集合Ｓの個々のデータベースサーバ１０ｉに、
【数３】

を計算してもらう。ここで、ｔは、データベースサーバ１０ｉにより応答ごとにランダムに生成される非零かつ秘密の乱数である。またαは、次の数４式ようになる。
【数４】

【００２７】
本実施の形態におけるリスト検索では、クライアント端末２０がデータベースサーバ１０ｉからｇ^{tfSi( α )}を受信するときに、αをデータベースサーバ１０ｉに知られたくない（検索要求のプライバシーを守るため）。一方、データベースサーバ１０ｉは、ｇ^{tfSi( α ')}（α'≠α）をクライアント端末２０に知られたくない（リストに関する余分な情報を与えないため）。このように考えることで、文献２に示されたような、ＤＤＨ問題に基づく特殊な形のＯＰＥ（紛失多項式計算）に適した評価問題を設定することができる。
ＯＰＥの性質から、αの情報は、データベースサーバ１０ｉに対して全く漏れない。また、このときα∈Ｌ_iであれば、ｔの値によらずＴ_i＝１となる。そうでない場合は、ｔが応答ごとにランダムに選ばれることから、Ｔ_iは、１以外かつ検索要求ごとに無相関なランダムな値となる。これにより、本実施の形態によるリスト検索のためのプロトコルは、何回（ｑのサイズに対して多項式で表される回数で、事実上無限）の検索要求が実行されても、多項式に関する情報が漏れないプロトコルとなる。
【００２８】
次に、検索要求メッセージ生成アルゴリズムＧ、検索応答メッセージ生成アルゴリズムＲ、検索結果判定アルゴリズムＤの構成法を示す。
初期状態として、クライアント端末２０は、秘密鍵ｄ∈Ｚ_qに対する公開鍵＜ｇ，ｅ＝ｇ^d＞を、またサーバ集合Ｓは、リストのデータの数ｎを公開しているものとする。
〔検索要求メッセージ生成アルゴリズムＧ〕
図４は、検索要求メッセージ生成アルゴリズムＧを説明する図である。
このアルゴリズムＧは、クライアント端末２０の検索要求メッセージ生成部２１にて実行され、図４に示すように、検索を要求するデータ番号αを入力とし、検索要求メッセージｒｅｑを出力とする。また、ｊ＝１，．．．，ｎに関して以下の処理を行う。
１．ｒ_j（∈Ｚ_q）をランダムに選ぶ。
２．公開鍵ｇ、ｅを用いた次の数５式により、（ｖ_j，ｕ_j）を計算する。
【数５】

検索要求メッセージ生成部２１は、以上のようにして計算された２ｎ個の値（ｖ₁，ｕ₁），．．．，（ｖ_n，ｕ_n）をｒｅｑとして出力する。出力された検索要求メッセージｒｅｑは、クライアント端末２０に設けられている送信手段であるネットワークインターフェイス及びネットワークを介して、ｎ個のデータベースサーバ１０ｉへ送信される。
【００２９】
〔検索応答メッセージ生成アルゴリズムＲ〕
図５は、検索応答メッセージ生成アルゴリズムＲを説明する図である。
このアルゴリズムＲは、データベースサーバ１０ｉの検索応答メッセージ生成部１２にて実行され、図５に示すように、検索要求メッセージｒｅｑ及びデータベース１１の持つデータのデータ番号のリストＬ_iを入力とし、検索応答メッセージａｎｓ_iを出力とする。また、ＯＰＥによる次の処理を実行する。
１．ｎ次の多項式
【数６】

を、次の数７式を展開することにより求める。
【数７】

２．ｔ，ｓ（∈Ｚ_q）をランダムに選ぶ。
３．次の数８式により、ｃ₁及びｃ₂を計算する。
【数８】

検索応答メッセージ生成部１２は、以上のようにして計算されたＯＰＥによる評価結果である２個の値（ｃ₁，ｃ₂）をａｎｓ_iとして出力する。出力された検索応答メッセージａｎｓ_iは、データベースサーバ１０ｉに設けられている送信手段であるネットワークインターフェイス及びネットワークを介して、検索要求メッセージｒｅｑを送信したクライアント端末２０へ返送される。
【００３０】
〔検索結果判定アルゴリズムＤ〕
図６は、検索結果判定アルゴリズムＤを説明する図である。
このアルゴリズムＤは、クライアント端末２０の検索結果判定部２２にて実行され、図６に示すように、検索応答メッセージａｎｓ_iを入力とし、検索結果ｒｅｓ_iを出力とする。また、次の処理を実行する。
１．秘密鍵ｄを用いた次の数９式により、Ｔを求める
【数９】

２．Ｔ＝１であれば１を、Ｔ≠１であれば０をｒｅｓ_iとして出力する。
出力された検索結果ｒｅｓ_iにより、クライアント端末２０を使用するクライアントは、所望のデータがどのデータベースサーバ１０ｉに設けられているかを知ることができる。この後、クライアントは、所望のデータを保有するデータベースサーバ１０ｉに対し、改めて当該データの取得要求を行うことができる。
【００３１】
次に、本実施の形態を適用可能なデータベースシステムの具体例を説明する。
１：スキルデータベース
個人のスキルをデータベース化することで、個人どうしの間での情報の共有、個人対個人のコミュニケーションに用いることができる。いわゆる電子情報による名刺交換的な用法である。この場合に、個人の持つスキルは個人のプライバシー情報であることから、必要以上の情報を提供することは円滑なデータベースの運用のためにも望ましくない。また、派遣会社の人材データベースなどでは、特定のスキルを持つ人を抽出する場面があるが、この際に、全てのスキルに関する情報を提供してしまうのは、派遣会社の重要な企業秘密を明かすことになり問題となる。
そこで、データベースに格納されたスキルをデータ番号でリスト化して当該データベースの管理サーバを本実施の形態のデータベースサーバ１０ｉとし、クライアント端末２０に相当する端末装置から必要なスキルのデータ番号を秘匿して検索要求を出すことができる。この場合、データベースサーバ１０ｉは、クライアント端末２０からどのようなスキル（データ項目）に関する検索要求が行われたのかを知ることはできない。またクライアント端末２０においても、データベースサーバ１０ｉが検索要求にかかるスキル以外にどのようなスキルをデータとして格納しているのかを知ることはできない。したがって、プライバシーを保護した形でデータベースを運用することができる。
【００３２】
２：分散型データベース
近年、インターネットなどの外部ネットワークと接続可能な家庭用電気器具が増加している。とりわけハードディスク装置に放送番組を録画し、ネットワークを介して録画データを他者と共有することで分散データベースを作るという概念が実用化に向かっている。この際、録画データを取得しようとするクライアントは、ネットワークに接続されたハードディスク装置に格納されている録画データを検索する必要がある。しかし、クライアントにとって、どのような番組を検索しているかはプライバシー情報のため秘匿しておきたい。また、ハードディスク装置に格納されている録画データのリスト自体も個人のプライバシーなので秘匿しておきたい。
そこで、ハードディスク装置に格納されている録画データに一意なデータ番号を付け、当該ハードディスク装置のホストコンピュータを本実施の形態のデータベースサーバ１０ｉとし、クライアント端末２０に相当する端末装置から所望する録画データのデータ番号を秘匿して検索要求を出すことができる。この場合、データベースサーバ１０ｉは、クライアント端末２０からどのような録画データ（データ項目）に関する検索要求が行われたのかを知ることはできない。またクライアント端末２０においても、データベースサーバ１０ｉが検索要求にかかる録画データ以外にどのような録画データを格納しているのかを知ることはできない。したがって、プライバシーを保護した形でデータベースを運用することができる。
また、この種のデータベースでは、データ検索に対して課金を行う場合があるが、この場合、課金を正当に行うために、一回の検索で得られる検索結果を制限する必要がある。本実施の形態によれば、クライアントは、検索要求を行ったデータ以外のデータに関する情報は全く得られないので、このような課金システムを正当に運営することが可能となる。
【００３３】
３：論文データベース
論文投稿の電子化に伴い、インターネット上のホームページなどで保有する論文のリストが掲示されることが多くなっている。だが、論文の著作権に関する制約上、論文データ自体を公開されたデータベースに登録するのは望ましくない場合がある。一方、個人対個人のやりとりで論文を提供することは可能な場合が多い。このような事情から、配布できる論文のリストを秘匿しておきたいという要求がある。反対に、論文を検索する側にとっては、広い範囲に対してどんな論文を探しているかを知られるのはプライバシー上問題がある。
そこで、データベースに格納された論文をデータ番号（論文番号）でリスト化して当該データベースの管理サーバを本実施の形態のデータベースサーバ１０ｉとし、クライアント端末２０に相当する端末装置から必要な論文のデータ番号を秘匿して検索要求を出すことができる。この場合、データベースサーバ１０ｉは、クライアント端末２０からどのような論文（データ項目）に関する検索要求が行われたのかを知ることはできない。またクライアント端末２０においても、データベースサーバ１０ｉが検索要求にかかる論文以外にどのような論文をデータとして保有しているのかを知ることはできない。これにより、データベースサーバ１０ｉは論文リストを秘匿し、検索者は検索対象の論文番号を秘匿したまま論文を交換することができる。
【００３４】
４：ピア・ツー・ピア型データベース
近年、ピア・ツー・ピア（Peer-to-Peer：Ｐ２Ｐ）型のネットワーク技術を用いたデータベースの利用が爆発的に普及している。ピア・ツー・ピア型ネットワークでは、不特定多数のピアが、それぞれ異なるデータを保有し、互いに共有することで、全体として巨大なデータベースを築いている。このデータベースに対して、所望のデータがどこに存在するかを検索する際に、本実施の形態によるデータベース検索を利用することができる。
すなわち、データベース検索を行うピアを本実施の形態におけるクライアント端末２０とし、ネットワーク上の他のピアをデータベースサーバ１０ｉとして、クライアント端末２０に相当するピアから他のピアへ、所望のデータが秘匿された検索要求をブロードキャストにより一斉配信する。本実施の形態の手法によれば、データベースサーバ１０ｉの数に関わらず、共通の（すなわちデータベースサーバ１０ｉの数に依存しないサイズの）検索要求を用いることができるため、このような場合のデータベース検索に好適である。
本実施の形態を用いることにより、検索要求にかかるデータ項目を秘匿し、検索される側のデータベースにおけるデータ項目のリストも秘匿できるので、ピア・ツー・ピア型ネットワークを利用したデータベースの健全な発展に貢献することができる。
【００３５】
【発明の効果】
以上説明したように、本発明によれば、検索要求のプライバシーやデータベースのセキュリティを確保し、かつ処理効率の高いデータベース検索システムを提供することができる。
【図面の簡単な説明】
【図１】 本実施の形態によるデータベース検索システムの概略構成を説明する図である。
【図２】 本実施の形態におけるデータベースサーバ及びクライアント端末の構成を示す図である。
【図３】 本実施の形態によるリスト検索の概念を説明する図である。
【図４】 本実施の形態における検索要求メッセージ生成アルゴリズムＧを説明する図である。
【図５】 本実施の形態における検索応答メッセージ生成アルゴリズムＲを説明する図である。
【図６】 本実施の形態における検索結果判定アルゴリズムＤを説明する図である。
【図７】 本実施の形態によるデータベースサーバ及びクライアント端末を実現するのに好適なコンピュータ装置のハードウェア構成の例を模式的に示した図である。
【図８】 一方向性ハッシュ関数を用いたデータベース検索の手法を説明する図である。
【図９】 ＯＰＥプロトコルを用いたデータベース検索の従来手法を説明する図である。
【符号の説明】
１０…データベースサーバ、１１…データベース、１２…検索応答メッセージ生成部、２０…クライアント端末、２１…検索要求メッセージ生成部、２２…検索結果判定部

Claims (11)

1. ネットワーク上に設けられた所定のデータを格納したデータベースサーバと、
   前記データベースサーバに対し所望のデータの有無に関する検索要求を当該所望のデータを秘匿して行うクライアント端末とを備え、
   前記データベースサーバは、前記クライアント端末から受信した前記検索要求及びデータベースに格納されたデータのリストに基づいて、当該検索要求にかかるデータ項目を根とする多項式を生成し、当該データ項目を当該多項式に代入した結果が０になるという評価問題を紛失多項式計算（Oblivious Polynomial Evaluation）にて解き、得られた評価結果を検索の結果として前記クライアント端末に送信し、
   前記クライアント端末は、
   自分の公開鍵を用いて前記所望のデータを暗号化して前記検索要求を生成する検索要求メッセージ生成手段と、
   前記データベースサーバから送信された前記評価結果に対して自分の秘密鍵を用いた所定の計算を行うことにより、当該データベースサーバが前記所望のデータを保有するか否かを示す情報を取得する検索結果判定手段と
   を備えることを特徴とするデータベース検索システム。
2. 所定のデータを格納したデータベースと、
   ネットワークを介して所定のデータの検索要求を取得し、当該検索要求及び前記データベースに格納されたデータのリストに基づいて、当該検索要求にかかるデータ項目を根とする多項式を生成し、当該データ項目を当該多項式に代入した結果が０になるという評価問題を紛失多項式計算（Oblivious Polynomial Evaluation）にて解き、当該検索要求に対する応答を生成する検索応答メッセージ生成部と
   を備えることを特徴とするデータベースサーバ。
3. 前記検索応答メッセージ生成部は、乱数を用いて前記多項式をランダムに生成することを特徴とする請求項２に記載のデータベースサーバ。
4. ネットワークを介して所定のデータベースサーバに対して検索要求を行う端末装置において、
   所望のデータを暗号化し、前記データベースサーバに対して所望のデータの有無を問い合わせる検索要求を生成する検索要求メッセージ生成部と、
   紛失多項式計算（Oblivious Polynomial Evaluation）により得られた前記検索要求に対する評価結果を前記データベースサーバから受信し、当該評価結果に基づいて当該データベースサーバが前記所望のデータを保有するか否かを示す情報を取得する検索結果判定部と
   を備えることを特徴とする端末装置。
5. ピア・ツー・ピア（Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ）型のネットワークシステムでデータを共有するデータ共有システムにおいて、
   他のピアに対して所望のデータの有無に関する検索要求を当該所望のデータを秘匿して行う第１のピアと、
   前記第１のピアから受信した検索要求及び自装置が持つデータベースに格納されたデータのリストに基づいて、当該検索要求にかかるデータ項目を根とする多項式を生成し、当該データ項目を当該多項式に代入した結果が０になるという評価問題を紛失多項式計算（Oblivious Polynomial Evaluation）にて解き、得られた評価の結果を検索結果として前記第１のピアに送信する第２のピアとを備え、
   前記第１のピアは、
   自分の公開鍵を用いて前記所望のデータを暗号化して前記検索要求を生成する検索要求メッセージ生成手段と、
   前記第２のピアから送信された前記評価の結果に対して自分の秘密鍵を用いた所定の計算を行うことにより、当該第２のピアが前記所望のデータを保有するか否かを示す情報を取得する検索結果判定手段とを備えたことを特徴とするデータ共有システム。
6. 前記第１のピアは、前記ネットワークシステムを構成するいずれかのピアであり、
   前記第２のピアは、前記ネットワークシステムを構成するピアのうち前記第１のピア以外のピアであることを特徴とする請求項５に記載のデータ共有システム。
7. コンピュータを制御して、記憶装置に格納されたデータを管理するデータベースとして機能させるプログラムであって、
   所定のデータの検索要求を受信する受信手段と、
   前記検索要求及び前記データベースに格納されたデータのリストに基づいて、当該検索要求にかかるデータ項目を根とする多項式を生成し、当該データ項目を当該多項式に代入した結果が０になるという評価問題を紛失多項式計算（Oblivious Polynomial Evaluation）にて解く評価手段として、
   前記コンピュータを機能させることを特徴とするプログラム。
8. 前記プログラムによる前記評価手段は、乱数を用いて前記多項式をランダムに生成する処理を前記コンピュータに実行させることを特徴とする請求項７に記載のプログラム。
9. コンピュータを制御して、記憶装置に格納されたデータを管理するデータベースとして機能させるプログラムであって、
   所望のデータを暗号化し、データベースサーバに対して所望のデータの有無を問い合わせる検索要求を生成する検索要求生成手段と、
   紛失多項式計算（Oblivious Polynomial Evaluation）により得られた前記検索要求に対する評価結果を前記データベースサーバから受信し、当該評価結果に基づいて当該データベースサーバが前記所望のデータを保有するか否かを示す情報を取得する検索結果判定手段として、
   前記コンピュータを機能させることを特徴とするプログラム。
10. コンピュータを制御して実行プログラムをコンパイルして機械語コードを生成するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
    前記プログラムは、
    所定のデータの検索要求を受信する受信手段と、
    前記検索要求及びデータベースに格納されたデータのリストに基づいて、当該検索要求にかかるデータ項目を根とする多項式を生成し、当該データ項目を当該多項式に代入した結果が０になるという評価問題を紛失多項式計算（Oblivious Polynomial Evaluation）にて解く評価手段として、
    前記コンピュータを機能させることを特徴とする記録媒体。
11. コンピュータを制御して実行プログラムをコンパイルして機械語コードを生成するプログラムを、当該コンピュータが読み取り可能に記録した記録媒体であって、
    前記プログラムは、
    所望のデータを暗号化し、データベースサーバに対して所望のデータの有無を問い合わせる検索要求を生成する検索要求生成手段と、
    紛失多項式計算（Oblivious Polynomial Evaluation）により得られた前記検索要求に対する評価結果を前記データベースサーバから受信し、当該評価結果に基づいて当該データベースサーバが前記所望のデータを保有するか否かを示す情報を取得する検索結果判定手段として、
    前記コンピュータを機能させることを特徴とする記録媒体。

Images