(57)【要約】【課題】  情報提供者と利用者の間のオブリヴィアス  キーワード  サーチでやりとりするデータの通信量を削減し、さらに情報提供が手順とおりに正しく行われているかを検証可能にする。【解決手段】  鍵長サイズを１６０ビット程度で設定できる楕円曲線上の離散対数問題に基づく方式を適用することで、従来方式のＲＳＡ署名方式に比べて通信量を１／３に削減できる。また、情報提供者の不正防止のために楕円曲線上で定義されているベイユ・ペアリングあるいはテイト・ペアリングを適用することにより、情報提供者が手順とおりに正しく行われているかを検証できる。【選択図】      図３
2007013564.tif 000002
【特許請求の範囲】
【請求項１】
提供端末は複数のキーワードｗｉ（ｉ＝１，・・・，ｎ）とそのキーワードに対応するコンテンツｃｉ（ｉ＝１，・・・，ｎ）とを暗号化し、その暗号化データＥｉ（ｉ＝１，・・・，ｎ）を配布し、利用端末は暗号化データＥｉから任意のキーワードｗ＊に対応するコンテンツｃ＊の情報を得るためにキーワードｗ＊を乱数ｒを用いて暗号化し、その暗号化データＸを提供端末に送り、提供端末は利用端末から送られてきた暗号化データＸから復号化データＫ′を生成して利用端末に送り、利用端末は提供端末から送られてきた復号化データＫ′が正当なデータであるかどうかを検証し、正当なデータであるならば、その正当なデータＫ′から乱数ｒを除去してデータＫを得て、そのデータＫと配布された暗号化データＥｉ（ｉ＝１，・・・，ｎ）とを用いて、キーワードｗ＊に対応するコンテンツｃ＊の情報を得ることを特徴とするキーワードを知らせずに検索を行い、検索結果を検証することが可能なオンデマンド検索方法。
【請求項２】
オブリヴィアス・キーワード・サーチ（Oblivious Keyword Search：ＯＫＳ）を用いることを特徴とする請求項１記載のオンデマンド検索方法。
【請求項３】
複数のキーワードｗｉ（ｉ＝１，・・・，ｎ）とそのキーワードに対応するコンテンツｃｉ（ｉ＝１，・・・，ｎ）との暗号化に、楕円曲線上の離散対数問題に基づく方式に対応させることにより、提供端末と利用端末との間でやりとりされるデータの通信量を削減したことを特徴とする請求項２記載のオンデマンド検索方法。
【請求項４】
利用端末は、提供端末が算出した復号化データＫ′について、楕円曲線上で定義されている２点Ｐ、Ｑに対する双線形を持つ乗法群への写像であるベイユ・ペアリングあるいはテイト・ペアリングｅ（Ｐ，Ｑ）を用いて、その正当性を検証することにより、提供端末が手順とおりに正しく行われているか否かを検証することを特徴とする請求項３記載のオンデマンド検索方法。
【請求項５】
複数のコンテンツと該複数のコンテンツに夫々対応させたキーワードとを乱数ｓを用いて暗号化して配布データを生成するとともに、受信した質問データと前記乱数ｓとを用いて回答データを生成して返送する提供端末と、任意に選択したキーワードと乱数ｒとを用いて前記質問データを生成するとともに、返送されてくる前記回答データに含まれる前記乱数ｒを除去して復号用データを生成し、該復号用データを用いて前記配布データから前記選択したキーワードに対応するコンテンツを得る利用端末とを含むオンデマンド検索システムにおいて、
前記利用端末が、前記提供端末にて行われた前記回答データの生成が正当に行われたか否かを検証する手段を備えていることを特徴とするオンデマンド検索システム。
【請求項６】
前記配布データの生成に楕円曲線上の離散対数問題に基づく方式を採用し、前記回答データの生成が正当に行われたか否かの検証を、ベイユ・ペアリングあるいはテイト・ペアリングを利用して行うようにしたことを特徴とする請求項５に記載されたオンデマンド検索システム。
【請求項７】
複数のコンテンツと該複数のコンテンツに夫々対応させたキーワードとを乱数ｓを用いて暗号化して配布データを生成するとともに、受信した質問データと前記乱数ｓとを用いて回答データを生成して返送する提供端末を含むオンデマンド検索システムに用いられる利用端末において、
任意に選択したキーワードと乱数ｒとを用いて前記質問データを生成し前記提供端末へ送信する手段と、
前記提供端末から返送される前記回答データの生成が前記提供端末にて正当に行われたか否かを検証する手段と、
前記回答データの生成が正当に行われている場合に、当該回答データに含まれる前記乱数ｒを除去して復号用データを生成し、当該復号用データを用いて前記配布データから前記選択したキーワードに対応するコンテンツを得る手段と、を含むことを特徴とする利用端末。
【請求項８】
前記配布データの生成に楕円曲線上の離散対数問題に基づく方式を採用し、前記回答データの生成が正当に行われたか否かの検証を、ベイユ・ペアリングあるいはテイト・ペアリングを利用して行うことを特徴とする請求項７に記載された利用端末。
【請求項９】
提供端末が、複数のコンテンツと該複数のコンテンツに夫々対応させたキーワードとを乱数ｓを用いて暗号化して配布データを生成し配布するステップと、
前記配布データの配布を受けた利用端末が、任意に選択したキーワードと乱数ｒとを用いて前記質問データを生成し、前記提供端末へ送信するステップと、
前記提供端末が、前記質問データを受信し、当該質問データと前記乱数ｓとを用いて回答データを生成して返送するステップと、
前記利用端末が、返送されて来た前記回答データが正当に生成されたものか否かを検証するステップと、
前記回答データが正当に生成されたものである場合に、当該回答データに含まれる前記乱数ｒを除去して復号用データを生成し、該復号用データを用いて前記配布データから前記選択したキーワードに対応するコンテンツを得るステップと、を含むことを特徴とするオンデマンド検索方法。
【請求項１０】
前記配布データの生成に楕円曲線上の離散対数問題に基づく方式を採用し、前記回答データの生成が正当に行われたか否かの検証を、ベイユ・ペアリングあるいはテイト・ペアリングを利用して行うようにしたことを特徴とする請求項９に記載されたオンデマンド検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のキーワードに夫々対応する複数のコンテンツを保有する情報提供者に、利用者が任意に選択したキーワードを知られることなく、その選択したキーワードに関連付けされたコンテンツを得ることができるオンデマンド検索方法及びシステムに関する。
【背景技術】
【０００２】
近年、インターネットを介してのオンデマンド検索システムが相次いで実現されている。オンデマンド検索システムは、利用端末からキーワードを入力すると、提供端末からキーワードに関連付けされた情報が提供されるシステムである。
【０００３】
オンデマンド検索システムは、オープンなインターネットを利用するために、利用者が入力したキーワード（例えば、購入情報）を秘匿するなど、プライバシの保証が求められる。そこで、プライバシの保証に対応するための技術として提案されたのが、オブリヴィアス  キーワード  サーチ（Oblivious Keyword Search，以下、ＯＫＳ）である。
【０００４】
ＯＫＳとは、情報提供者と利用者の間で行われる以下のような２パーティプロトコルである。情報提供者は、情報（ここではｎ個のコンテンツとする。）を夫々キーワードに関連付けし、暗号化して管理する。また、情報提供者は、利用者に対してｎ個のキーワードｗｉ（ｉ：１，・・・，ｎ）を与える。利用者は情報提供者から与えられたｎ個のキーワードｗｉ（ｉ：１，・・・，ｎ）の中から任意のキーワードｗ＊を選択し、そのキーワードｗ＊が情報提供者に知られない状態にし（即ち、暗号化し）質問データとして情報提供者へ送る。情報提供者は、利用者からのキーワードｗ＊を含む質問データに、コンテンツの暗号化に使用した暗号鍵を用いた処理を加え、利用者に暗号鍵を知られることがない状態にし応答データとして送り返す。情報提供者から利用者に送り返された応答データには、利用者自身が選択したキーワードｗ＊と、コンテンツの暗号化に利用された暗号鍵とが含まれる。それゆえ、利用者は受け取った応答データを用いて、情報提供者により管理されている暗号化されたコンテンツを処理することにより、選択したキーワードｗ＊に関連付けられたコンテンツのみを正しく復号することができる。
【０００５】
以上のようにして、ＯＫＳでは、利用者は、選択したキーワードｗ＊を情報提供者に知られることなく、キーワードｗ＊に関連付けられた情報を得ることができる。また、利用者は、自ら選択した任意のキーワードｗ＊以外の他のキーワードに関連付けられた情報を得ることができない。
【０００６】
ＯＫＳの従来方式としては、尾形、黒澤によるＲＳＡブラインド署名方式に基づいたＯＫＳがある（非特許文献１参照。）。
【０００７】
以下、ＲＳＡブラインド署名方式に基づいたＯＫＳについて詳細に説明する。
【０００８】
ｓｔｅｐ１．
予め、情報提供者側において、キーワードｗｉ（ｉ：１，・・・，ｎ）とそれに夫々対応するコンテンツｃｉがデータベースに格納されているとする。
【０００９】
まず、情報提供者は、ＲＳＡ署名の公開鍵（Ｎ，ｅ）と秘密鍵（ｄ）を生成し、ｉ＝１からｎについて、下式によりＫｉを計算し、さらにＥｉを計算する。
【００１０】
Ｋｉ＝Ｈ（ｗｉ）ｄ  mod  Ｎ
Ｅｉ＝Ｇ（ｗｉ‖Ｋｉ‖ｉ）  XOR  （０ｌ‖ｃｉ）
ここで、Ｈ（）は暗号学的に安全なハッシュ関数（ＳＨＡ１など）、Ｇ（）は擬似乱数生成器、‖はビット列の結合、ＸＯＲはビット列の排他的論理和、０ｌは連続するｌ（エル）個の“０”ビット列である。
【００１１】
情報提供者は、公開鍵と求めたＥｉとの組である（Ｎ，ｅ，Ｅ１，・・・，Ｅｎ）を利用者に配布する。
【００１２】
ｓｔｅｐ２．
利用者はキーワードｗ＊（ｗ１〜ｗｎのいずれか）について検索したいとする。利用者は、乱数ｒを選び、
Ｙ＝ｒｅ・Ｈ（ｗ＊）  mod  Ｎ
を計算し、求めたＹを情報提供者に送る。
【００１３】
ｓｔｅｐ３．
情報提供者は利用者からＹを受け取り、ＲＳＡ署名の秘密鍵ｄを用いて、
Ｋ′＝Ｙｄ  mod  Ｎ
を計算し、求めたＫ′を利用者に送る。
【００１４】
ｓｔｅｐ４．
利用者は情報提供者からＫ′を受け取り、乱数ｒを用いて、
Ｋ＝Ｋ′／ｒ  mod  Ｎ
を計算する。それから利用者は、ｉ＝１からｎまでの全てについて、
ａｉ‖ｂｉ＝Ｅｉ  XOR  Ｇ（ｗｉ‖Ｋ‖ｉ）
を計算する。ここで、ａｉは始めのｌ（エル）ビットで、ｂｉは残りの文字列である。
【００１５】
ｓｔｅｐ５．
ａｉ＝０ｌであるとき、即ち先頭から“０”ビットがｌ（エル）個連続するとき、キーワードｗｉがｗ＊と一致するとみなす。このとき、キーワードｗ＊に対応するコンテンツｃｉは、ｂｉとして得られる。
【００１６】
以上のようにして、利用者は自ら選択した任意のキーワードｗ＊を情報提供者に知られることなく、キーワードｗ＊に関連付けされた情報を入手できるので、利用者のプライバシが保証される。また、利用者は自ら選択した任意のキーワードｗ＊に関連付けされた情報しか入手できないので、情報提供者の利益が保証される。
【００１７】
【非特許文献１】尾形わかは，黒澤馨、「オブリヴィアス  キーワード  サーチ（Oblivious keyword search）」、ジャーナル  オブ  コンプレクシティ（Journal of Complexity）、２００４、ｖｏｌ．２０、ｐｐ．３５６−３７１）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従来のオンデマンド検索システムにおいて利用者のプライバシを保護する方式は、ＲＳＡ署名方式に基づいており、ＲＳＡ署名方式の安全性を考慮すると、鍵長サイズを１０２４ビット以上に大きく設定する必要がある。その結果、情報提供者と利用者との間の通信量が大きくなってしまい、効率面に難がある。
【００１９】
そこで、本発明は、情報提供者と利用者の間のＯＫＳでやりとりするデータの通信量を削減し、さらに情報提供者が手順とおりに正しく行われているかを検証可能なオンデマンド検索システムを提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明によれば、提供端末は複数のキーワードｗｉ（ｉ＝１，・・・，ｎ）とそのキーワードに対応するコンテンツｃｉ（ｉ＝１，・・・，ｎ）とを暗号化し、その暗号化データＥｉ（ｉ＝１，・・・，ｎ）を配布し、利用端末は暗号化データＥｉから任意のキーワードｗ＊に対応するコンテンツｃ＊の情報を得るためにキーワードｗ＊を乱数ｒを用いて暗号化し、その暗号化データＸを提供端末に送り、提供端末は利用端末から送られてきた暗号化データＸから復号化データＫ′を生成して利用端末に送り、利用端末は提供端末から送られてきた復号化データＫ′が正当なデータであるかどうかを検証し、正当なデータであるならば、その正当なデータＫ′から乱数ｒを除去してデータＫを得て、そのデータＫと配布された暗号化データＥｉ（ｉ＝１，・・・，ｎ）とを用いて、キーワードｗ＊に対応するコンテンツｃ＊の情報を得ることを特徴とするキーワードを知らせずに検索を行い、検索結果を検証することが可能なオンデマンド検索方法が得られる。
【００２１】
また、本発明によれば、複数のコンテンツと該複数のコンテンツに夫々対応させたキーワードとを乱数ｓを用いて暗号化して配布データを生成するとともに、受信した質問データと前記乱数ｓとを用いて回答データを生成して返送する提供端末と、任意に選択したキーワードと乱数ｒとを用いて前記質問データを生成するとともに、返送されてくる前記回答データに含まれる前記乱数ｒを除去して復号用データを生成し、該復号用データを用いて前記配布データから前記選択したキーワードに対応するコンテンツを得る利用端末とを含むオンデマンド検索システムにおいて、前記利用端末が、前記提供端末にて行われた前記回答データの生成が正当に行われたか否かを検証する手段を備えていることを特徴とするオンデマンド検索システムが得られる。
【００２２】
さらに、本発明によれば、複数のコンテンツと該複数のコンテンツに夫々対応させたキーワードとを乱数ｓを用いて暗号化して配布データを生成するとともに、受信した質問データと前記乱数ｓとを用いて回答データを生成して返送する提供端末を含むオンデマンド検索システムに用いられる利用端末において、任意に選択したキーワードと乱数ｒとを用いて前記質問データを生成し前記提供端末へ送信する手段と、前記提供端末から返送される前記回答データの生成が前記提供端末にて正当に行われたか否かを検証する手段と、前記回答データの生成が正当に行われている場合に、当該回答データに含まれる前記乱数ｒを除去して復号用データを生成し、当該復号用データを用いて前記配布データから前記選択したキーワードに対応するコンテンツを得る手段と、を含むことを特徴とする利用端末が得られる。
【００２３】
さらにまた、本発明によれば、提供端末が、複数のコンテンツと該複数のコンテンツに夫々対応させたキーワードとを乱数ｓを用いて暗号化して配布データを生成し配布するステップと、前記配布データの配布を受けた利用端末が、任意に選択したキーワードと乱数ｒとを用いて前記質問データを生成し、前記提供端末へ送信するステップと、前記提供端末が、前記質問データを受信し、当該質問データと前記乱数ｓとを用いて回答データを生成して返送するステップと、
前記利用端末が、返送されて来た前記回答データが正当に生成されたものか否かを検証するステップと、前記回答データが正当に生成されたものである場合に、当該回答データに含まれる前記乱数ｒを除去して復号用データを生成し、該復号用データを用いて前記配布データから前記選択したキーワードに対応するコンテンツを得るステップと、を含むことを特徴とするオンデマンド検索方法が得られる。
【発明の効果】
【００２４】
本発明によれば、鍵長サイズを１６０ビット程度で設定できる楕円曲線上の離散対数問題に基づく方式を適用することで、従来方式に比べて通信量を１／３に削減でき、効率面が改良される。
【００２５】
また、本発明によれば、情報提供者と利用者の間のＯＫＳでやりとりしたデータをベイユ・ペアリングあるいはテイト・ペアリングで検証することにより、利用者は情報提供者において手順のとおりに正しく処理が行われているを検証でき、情報提供者の不正を防止できる。
【発明を実施するための最良の形態】
【００２６】
以下、図面を参照して、本発明の一実施の形態について詳細に説明する。
【００２７】
図１に、本発明に一実施の形態に係るオンデマンド検索システムの概略構成を示す。図示のシステムは、ネットワーク（ここでは、インターネット）１０を介して互いに接続された提供端末（提供者端末）２０及び利用端末（利用者端末）３０を有している。また、提供端末２０にはデータベース４０が接続されている。
【００２８】
提供端末２０は、データベースに登録されているキーワード及びコンテンツの一部または全てを暗号化し、利用端末３０に提供する。ここで、キーワードとコンテンツとは１対１で対応するものとする。また、暗号化されたキーワード及びコンテンツは、任意の記録媒体（例えば、ＣＤ−ＲＯＭやＤＶＤ）により利用端末３０に提供されるものとする。
【００２９】
利用端末３０は、任意に選択したキーワードを一方向性関数により提供端末２０に知得されない形態に変換して、ネットワーク１０を介して提供端末２０へ送る。また、提供端末２０は、利用端末３０からのキーワードを含むデータを、コンテンツの暗号化に使用した暗号鍵を用いた一方向性関数により利用端末３０に知得されない形態に変換し、ネットワーク１０を介して利用端末３０へ送り返す。ここでの利用端末３０と提供端末２０との間のデータの送受信には、鍵長サイズが比較的小さい楕円曲線上の離散対数問題に基づく方式を適用して、通信量を削減する。
【００３０】
提供端末２０からのデータを受け取った利用端末３０は、楕円曲線上で定義されている２点Ｐ、Ｑに対する双線形を持つ乗法群への写像であるベイユ・ペアリング（Weil paring）あるいはテイト・ペアリング（Tate paring）ｅ（Ｐ，Ｑ）を用いて、情報提供３０での処理が手順どおりに正しく行われているか検証する。
【００３１】
以下、図２及び図３を参照してさらに本実施の形態について説明する。
【００３２】
楕円曲線上の離散対数問題に基づくＯＫＳを実現するために、まず、有限体上の離散対数問題に基づく効率的なＯＫＳについて、図２を参照して説明する。
【００３３】
（１）有限体上の離散対数問題に基づくＯＫＳ
ｓｔｅｐ１．
位数が素数ｑのアーベル群（可換群）をＧ、その群Ｇの生成元をｇとする。また、ランダムなハッシュ関数をＨ０（）、Ｈ１（）とする。
【００３４】
データベース４０には、予めｎ個のキーワードｗｉ（ｉ：１，・・・，ｎ）とそれに１対１で対応するコンテンツｃｉがデータベースに格納されているとする。
【００３５】
ｓｔｅｐ２．
提供端末２０（情報提供者）は乱数ｓを選び、
ｙ＝ｇｓ
を計算する。また、提供端末２０は、ｉ＝１からｎの全てについて、
Ｋｉ＝Ｈ０（ｗｉ）ｓ
Ｅｉ＝Ｈ１（ｗｉ‖Ｋｉ‖ｉ）  XOR  （０ｌ‖ｃｉ）
を計算する。ここで、‖はビット列の結合、ＸＯＲはビット列の排他的論理和、０ｌは、連続するｌ（エル）個の“０”ビットである。
【００３６】
提供端末２０は、求めたｙ及びＥｉを配布データ（ｙ，Ｅ１，・・・，Ｅｎ）として、ＣＤ−ＲＯＭやＤＶＤ等の記録媒体等に記録する。提供端末２０を使用する情報提供者は、その記録媒体を利用者に配布する
ｓｔｅｐ３．
利用端末３０を使用する利用者はキーワードｗ１〜ｗｎのうちの任意のｗ＊について検索したいとする。利用端末３０は、乱数ｒを選び、
Ｙ＝ｇｒ  Ｈ０（ｗ＊）
を計算し、得られたＹをインターネット１０を介して提供端末２０に送る。
【００３７】
ｓｔｅｐ４．
提供端末２０は利用端末３０からのＹを受け取ると、乱数ｓを用いて、
Ｋ′＝Ｙｓ
を計算し、得られたＫ′をインターネット１０を介して利用端末３０に送る。
【００３８】
ｓｔｅｐ５．
利用端末３０は、提供端末２０からのＫ′を受け取ると、乱数ｒとｙとを用いて
Ｋ＝Ｋ′／ｙｒ
を計算する。さらに利用端末３０は、ｉ＝１からｎまでの全てについて、
ａｉ‖ｂｉ＝Ｅｉ  XOR  Ｈ１（ｗｉ‖Ｋ‖ｉ）
を計算する。ここでａｉは始めのｌ（エル）ビット、ｂｉは残りの文字列である。
【００３９】
ｓｔｅｐ６．
ａｉ＝０ｌであるとき、即ち、始めの連続するｌ（エル）ビットが全て“０”のとき、キーワードｗｉがｗ＊と一致するとみなす。このとき、対応するコンテンツｃｉは、ｂｉとして得られる。
【００４０】
次に、情報提供者の不正を検出可能なＯＫＳに拡張した例を、図３を参照して説明する。
【００４１】
（２）情報提供者の不正検出可能なＯＫＳ
ｓｔｅｐ１．
楕円曲線上で定義された位数が素数ｑのアーベル群（可換群）をＧ、その群Ｇの生成元をＰとする。また、ランダムなハッシュ関数をＨ０（）、Ｈ１（）とする。
【００４２】
データベース４０には、予めｎ個のキーワードｗｉ（ｉ：１，・・・，ｎ）とそれに１対１で対応するコンテンツｃｉがデータベースに格納されているとする。
【００４３】
ｓｔｅｐ２．
提供端末２０は（情報提供者）は乱数ｓを選び、
Ｙ＝ｓＰ
を計算する。また、提供端末２０は、ｉ＝１からｎの全てについて、
Ｋｉ＝ｓＨ０（ｗｉ）
Ｅｉ＝Ｈ１（ｗｉ‖Ｋｉ‖ｉ）  XOR  （０ｌ‖ｃｉ）
を計算する。ここで、‖はビット列の結合、ＸＯＲはビット列の排他的論理和、０ｌは、連続するｌ（エル）個の“０”ビットである。
【００４４】
提供端末２０は、求めたＹ及びＥｉをＣＤ−ＲＯＭやＤＶＤ等の記録媒体等に記録する。提供端末２０を使用する情報提供者は、その記録媒体を利用者に配布することによって、（Ｙ，Ｅ１，・・・，Ｅｎ）を配布する。
【００４５】
ｓｔｅｐ３．
利用端末３０を使用する利用者はキーワードｗ１〜ｗｎのうちの任意のｗ＊について検索したいとする。利用端末３０は、乱数ｒを選び、
Ｘ＝ｒＰ＋Ｈ０（ｗ＊）
を計算し、得られたＸをインターネット１０を介して提供端末２０に送る。
【００４６】
ｓｔｅｐ４．
提供端末２０は利用端末３０からのＸを受け取ると、乱数ｓを用いて、
Ｋ′＝ｓＸ
を計算し、得られたＫ′をインターネット１０を介して利用端末３０に送る。
【００４７】
ｓｔｅｐ５．
利用端末３０は提供端末２０からのＫ′を受け取ると、Ｋ′の正当性について、楕円曲線上で定義されている２点Ｐ、Ｑに対する双線形を持つ乗法群への写像であるベイユ・ペアリング（Weil paring）あるいはテイト・ペアリング（Tate paring）ｅ（Ｐ，Ｑ）を用いてｅ（Ｐ，Ｋ′）＝ｅ（Ｙ，Ｘ）が等しいかどうかを検証する。
【００４８】
ベイユ・ペアリングについては、宮地充子・菊池浩明  編著者、「ＩＴ  Ｔｅｘｔ  情報セキュリティ」、９０ページ、オーム社、２００３．１０．２５に記載されている。
【００４９】
利用端末３０は、ｅ（Ｐ，Ｋ′）＝ｅ（Ｙ，Ｘ）が等価であるならば、Ｋ′は正当であるとみなし、等価でないならば、Ｋ′は不正であるとみなす。
【００５０】
ｓｔｅｐ６．
利用端末３０はｓｔｅｐ５．の検証で正当であるとみなしたＫ′と乱数ｒとＹとを用いて、
Ｋ＝Ｋ′−ｒＹ
を計算する。さらに利用端末３０は、ｉ＝１からｎの全てについて、
ａｉ‖ｂｉ＝Ｅｉ  XOR  Ｈ1（ｗｉ‖Ｋ‖ｉ）
を計算する。ここで、ａｉは始めのｌ（エル）ビット、ｂｉは残りの文字列である。
【００５１】
ｓｔｅｐ７．
ａｉ＝０ｌであるとき、即ち、始めの連続するｌ（エル）ビットが全て“０”のとき、キーワードｗｉがｗ＊と一致するとみなす。このとき、対応するコンテンツｃｉは、ｂｉとして得られる。
【００５２】
以上のように、本実施の形態では、楕円曲線上の離散対数問題に基づく方式を採用することで、鍵長サイズ（乱数ｓ及びｒのサイズ）を１６０ビット程度に設定することができ、従来方式に比べて通信量を１／３に削減できる。
【００５３】
また、提供端末２０と利用端末３０との間のＯＫＳでやりとりしたデータをベイユ・ペアリングあるいはテイト・ペアリングで検証することにより、提供端末２０における処理が手順とおりに正しく行われているかを検証できる。
【図面の簡単な説明】
【００５４】
【図１】本発明の一実施の形態に係るオンデマンド検索システムの構成を示す概略図である。
【図２】図１のシステムを用いて行われる有限体上の離散対数問題に基づくＯＫＳの処理手順を説明するための図である。
【図３】図２のシステムを用いて行われる有限体上の離散対数問題に基づくＯＫＳの処理手順を説明するための図である。
【符号の説明】
【００５５】
１０    ネットワーク
２０    提供端末
３０    利用端末
４０    データベース
【図１】
2007013564.tif 000003
【図２】
2007013564.tif 000004
【図３】
2007013564.tif 000005