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