(57)【特許請求の範囲】
【請求項１】
サービス提供装置と、データ登録装置と、データベース装置と、ユーザ装置と、プロキシ装置とを備え、
前記サービス提供装置は、
データを暗号化するためのサービス公開鍵および該サービス公開鍵に対応したサービス秘密鍵を生成し、
データの検索を要求する前記ユーザ装置が生成したユーザ秘密鍵と前記サービス秘密鍵とを入力として、前記ユーザ装置ごとのプロキシ鍵を生成し、前記プロキシ装置に送信し、
前記データ登録装置は、前記サービス公開鍵およびデータを入力として、検索可能暗号データを生成し、
前記データベース装置は、前記検索可能暗号データを記憶し、
前記ユーザ装置は、前記データベース装置に記憶された前記検索可能暗号データに対して、データの検索を要求するためのユーザクエリを生成し、前記プロキシ装置に送信し、
前記プロキシ装置は、前記ユーザ装置から受信した前記ユーザクエリと前記サービス提供装置から受信した前記ユーザ装置ごとのプロキシ鍵とを入力として、前記データベース装置に記憶されている前記検索可能暗号データの検索を要求するための検索クエリを生成し、
前記ユーザ装置は、さらに、前記ユーザ秘密鍵を用いて前記ユーザクエリを生成する
ことを特徴とする暗号データ検索システム。
【請求項２】
サービス提供装置は、サービス秘密鍵とユーザ秘密鍵とを入力として、ユーザ装置ごとのプロキシ鍵を生成し、
プロキシ装置は、ユーザクエリおよび前記プロキシ鍵を入力として、検索クエリを生成し、
データベース装置は、前記検索クエリと当該データベース装置が記憶する検索可能暗号データとを入力として、検索結果を生成する
請求項１記載の暗号データ検索システム。
【請求項３】
データ登録装置は、
素数位数qを持つ群G，G_T、
e()をGの元2つを入力としてG_Tの群への写像であるペアリング関数、
gを群Gの生成元、
H_1を任意のビット列からG上へのハッシュ関数、
H_2をG_Tからkビットのビット列上へのハッシュ関数、
Mをメッセージ、
Z_qの乱数r、
sをサービス秘密鍵、gsをサービス公開鍵としたとき、H_2(e(H_1(M),gs)r),grを含む検索可能暗号データを生成し、
ユーザ装置は、
aをユーザ秘密鍵、gaをユーザ公開鍵とし、検索キーワードをKWとしたとき、H_1(KW)aを含むユーザクエリを生成する
請求項１記載の暗号データ検索システム。
【請求項４】
プロキシ装置は、ユーザ装置のプロキシ鍵がs/aを含み、検索キーワードをKWとしたとき、H_1(KW)sを含む検索クエリを生成する
請求項３記載の暗号データ検索システム。
【請求項５】
ユーザ装置は、
検証鍵と署名鍵とを生成し、
プロキシ装置が生成した検索クエリと前記署名鍵とを入力として、署名データを生成し、
データベース装置は、前記署名データと前記検証鍵とを入力として、署名検証を行う
請求項１から請求項４のうちのいずれか１項に記載の暗号データ検索システム。
【請求項６】
データを暗号化するためのサービス公開鍵を用いて生成された検索可能暗号データからデータを検索する暗号データ検索装置であって、
ユーザ装置が生成したユーザ秘密鍵と前記サービス公開鍵に対応したサービス秘密鍵とを用いて生成されたプロキシ鍵と、前記ユーザ装置が前記ユーザ秘密鍵を用いて生成したデータの検索を要求するユーザクエリとを入力として、データベース装置に記憶されている前記検索可能暗号データからデータを検索するための検索クエリを生成する手段を備えた
ことを特徴とする暗号データ検索装置。
【請求項７】
サービス提供装置が、
データを暗号化するためのサービス公開鍵および該サービス公開鍵に対応したサービス秘密鍵を生成し、
ユーザ装置が生成したユーザ秘密鍵と前記サービス秘密鍵とを入力として、前記ユーザ装置ごとにプロキシ鍵を生成し、
データ登録装置が、前記サービス公開鍵およびデータを入力として、検索可能暗号データを生成し、生成した前記検索可能暗号データをデータベース装置に記憶させ、
前記ユーザ装置が、前記データベース装置に記憶された前記検索可能暗号データに対して、前記ユーザ秘密鍵を用いてデータの検索を要求するためのユーザクエリを生成し、
プロキシ装置が、前記ユーザクエリと前記ユーザ装置ごとに生成されたプロキシ鍵とを入力として、前記データベース装置に記憶されている前記検索可能暗号データからデータを検索するための検索クエリを生成する
ことを特徴とする暗号データ検索方法。
【請求項８】
データを暗号化するためのサービス公開鍵を用いて生成された検索可能暗号データからデータを検索するための暗号データ検索プログラムであって、
コンピュータに、
ユーザ装置が生成したユーザ秘密鍵と前記サービス公開鍵に対応したサービス秘密鍵とを用いて生成されたプロキシ鍵と、前記ユーザ装置が前記ユーザ秘密鍵を用いて生成したデータの検索を要求するユーザクエリとを入力として、データベース装置に記憶されている前記検索可能暗号データからデータを検索するための検索クエリを生成する処理を
実行させるための暗号データ検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号データ検索システム、暗号データ検索装置、暗号データ検索方法及び暗号データ検索プログラムに関する。
【背景技術】
【０００２】
近年、クラウドサービスにおけるセキュリティの重要性が広く認識されている。例えば、クラウドネットワーク上のデータベースに暗号化されたデータを保存し、必要な時にデータベースからデータを取り出すサービスが存在する。このとき、ユーザがどの暗号データを必要としているかを確認する必要がある。例えば、データベースに保存されているすべての暗号データを取り出して復号し、必要なデータを見つけることが考えられる。しかしこの方法では、データベースからデータを取り出そうとするたびにすべての暗号データをユーザ側にダウンロードしなくてはならず、利便性や通信コストの観点で望ましくない。そのため、暗号データに対して、暗号化されたまま検索を行う検索可能暗号方式を利用したサービスが提案されている。関連する技術として、例えば、非特許文献１には、検索可能暗号方式が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, "Public Key Encryption with Keyword Search", EUROCRYPT2004, LNCS3027, pp.506--522, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一般的な検索可能暗号方式の多くは、あるユーザの公開鍵を用いてデータを暗号化することにより暗号データを生成し、そのユーザの秘密鍵を用いて検索クエリを生成することで暗号化したまま検索を可能としている。したがって、１つの暗号データに対して、検索可能なユーザは秘密鍵を有するユーザのみに限定される。
【０００５】
ところが、企業での文書管理などを考慮すると、１つのデータに対して複数人がアクセスする権限を持ち、権限を持つ複数人のみが検索可能であることが望まれる場合がある。上記の一般的な検索可能暗号方式を利用した場合、１つのデータに対して権限を持つ複数人による検索を許可するためには、権限を持つ複数人で秘密鍵を共有するなどの方法を用いて実現する必要がある。しかし、この方法は、秘密鍵漏洩の危険性を高めるため、一般に望ましくない。
【０００６】
また、秘密鍵を保有するサーバを設置し、そのサーバへのアクセス権を管理することで複数人に対して暗号データの検索を許可することを実現することも可能である。しかし、この方法では、サーバが秘密鍵を保有するため、サーバを乗っ取ることにより、すべての暗号データの検索が可能になる。そのため、サーバが攻撃の標的とされやすく、セキュリティ対策が重要となり、コスト増につながる。また、この方法では、サーバの管理者はサーバへの任意のアクセスが可能であるため、管理者が悪意を持ってアクセスした場合には、安全性を担保できない。
【０００７】
非特許文献１には、サービスプロバイダとユーザの秘密鍵からなるプロキシ鍵を用いて、１つのデータに対して複数人に検索を許可する検索可能暗号システムが記載されている。しかしながら、非特許文献１に記載された方式では、データベースにアクセスできるすべてのユーザが検索を行うことが可能である。そのため、データベースに記憶されているデータが漏洩した場合には、そのデータを入手できた人は誰でも検索を行うことができてしまうこととなり、甚大な被害が生ずる可能性がある。
【０００８】
そこで、本発明は、異なる公開鍵・秘密鍵を有する複数ユーザからの検索要求に対し検索結果を回答でき、かつデータ漏洩による被害を低減することができる暗号データ検索システム、暗号データ検索装置、暗号データ検索方法及び暗号データ検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明による暗号データ検索システムは、サービス提供装置と、データ登録装置と、データベース装置と、ユーザ装置と、プロキシ装置とを備え、サービス提供装置は、データを暗号化するためのサービス公開鍵およびサービス公開鍵に対応したサービス秘密鍵を生成し、データの検索を要求するユーザ装置が生成したユーザ秘密鍵とサービス秘密鍵とを入力として、ユーザ装置ごとのプロキシ鍵を生成し、プロキシ装置に送信し、データ登録装置は、サービス公開鍵およびデータを入力として、検索可能暗号データを生成し、データベース装置は、検索可能暗号データを記憶し、ユーザ装置は、データベース装置に記憶された検索可能暗号データに対して、データの検索を要求するためのユーザクエリを生成し、プロキシ装置に送信し、プロキシ装置は、ユーザ装置から受信したユーザクエリとサービス提供装置から受信したユーザ装置ごとのプロキシ鍵とを入力として、データベース装置に記憶されている検索可能暗号データの検索を要求するための検索クエリを生成し、ユーザ装置は、さらに、ユーザ秘密鍵を用いてユーザクエリを生成することを特徴とする。
【００１０】
本発明による暗号データ検索装置は、データを暗号化するためのサービス公開鍵を用いて生成された検索可能暗号データからデータを検索する暗号データ検索装置であって、ユーザ装置が生成したユーザ秘密鍵とサービス公開鍵に対応したサービス秘密鍵とを用いて生成されたプロキシ鍵と、ユーザ装置がユーザ秘密鍵を用いて生成したデータの検索を要求するユーザクエリとを入力として、データベース装置に記憶されている検索可能暗号データからデータを検索するための検索クエリを生成する手段を備えたことを特徴とする。
【００１１】
本発明による暗号データ検索方法は、サービス提供装置が、データを暗号化するためのサービス公開鍵および該サービス公開鍵に対応したサービス秘密鍵を生成し、ユーザ装置が生成したユーザ秘密鍵とサービス秘密鍵とを入力として、ユーザ装置ごとにプロキシ鍵を生成し、データ登録装置が、サービス公開鍵およびデータを入力として、検索可能暗号データを生成し、生成した検索可能暗号データをデータベース装置に記憶させ、ユーザ装置が、データベース装置に記憶された検索可能暗号データに対して、ユーザ秘密鍵を用いてデータの検索を要求するためのユーザクエリを生成し、プロキシ装置が、ユーザクエリとユーザ装置ごとに生成されたプロキシ鍵とを入力として、データベース装置に記憶されている検索可能暗号データからデータを検索するための検索クエリを生成することを特徴とする。
【００１２】
本発明による暗号データ検索プログラムは、データを暗号化するためのサービス公開鍵を用いて生成された検索可能暗号データからデータを検索するための暗号データ検索プログラムであって、コンピュータに、ユーザ装置が生成したユーザ秘密鍵とサービス公開鍵に対応したサービス秘密鍵とを用いて生成されたプロキシ鍵と、ユーザ装置がユーザ秘密鍵を用いて生成したデータの検索を要求するユーザクエリとを入力として、データベース装置に記憶されている検索可能暗号データからデータを検索するための検索クエリを生成する処理を実行させることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、異なる公開鍵・秘密鍵を有する複数ユーザからの検索要求に対し検索結果を回答でき、かつデータ漏洩による被害を低減することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明による暗号データ検索システムの構成例を示すブロック図である。
【図２】サービスプロバイダ装置の構成例を示すブロック図である。
【図３】プロキシサーバ装置の構成例を示すブロック図である。
【図４】ユーザ装置の構成例を示すブロック図である。
【図５】データ登録装置の構成例を示すブロック図である。
【図６】サービスプロバイダ鍵生成処理の一例を示す流れ図である。
【図７】ユーザ登録処理の一例を示す流れ図である。
【図８】データ登録処理の一例を示す流れ図である。
【図９】検索処理の一例を示す流れ図である。
【図１０】サービスプロバイダ鍵生成処理の具体例を示す流れ図である。
【図１１】ユーザ登録処理の具体例を示す流れ図である。
【図１２】データ登録処理の具体例を示す流れ図である。
【図１３】検索処理の具体例を示す流れ図である。
【図１４】第２の実施形態のデータ登録装置の構成例を示すブロック図である。
【図１５】暗号データ検索システムの最小の構成例を示すブロック図である。
【発明を実施するための形態】
【００１５】
実施形態１．
以下、本発明の実施形態について図面を参照して説明する。図１は、本発明による暗号データ検索システムの構成例を示すブロック図である。本実施形態の暗号データ検索システムは、図１に示すように、暗号データを登録するデータ登録装置10と、暗号データを記憶するデータベース装置50と、サービスプロバイダ装置20と、１つ以上のユーザ装置40-1，40-2，…，40-Nと、プロキシサーバ装置30とを含む。また、各装置は、ＬＡＮやインターネット等の通信ネットワークを介して相互に接続されている。
【００１６】
サービスプロバイダ装置20は、暗号データを生成するために用いる公開鍵pk_sおよびそれに対応する秘密鍵sk_sを生成する。サービスプロバイダ装置20は、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。
【００１７】
図２は、サービスプロバイダ装置の構成例を示すブロック図である。サービスプロバイダ装置20は、図２に示すように、鍵生成部201と、プロキシ鍵生成部202と、データ登録部203とを含む。
【００１８】
鍵生成部201は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。鍵生成部201は、データを暗号化するために用いるサービスプロバイダの公開鍵pk_sおよびそれに対応する秘密鍵sk_sを生成する機能を備えている。
【００１９】
プロキシ鍵生成部202は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。プロキシ鍵生成部202は、秘密鍵sk_sと、ユーザiの秘密鍵sk_iとを入力として、暗号化したまま暗号データの検索を可能とするプロキシ鍵rk_iを生成する機能を備えている。
【００２０】
データ登録部203は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵおよびネットワークインタフェース部によって実現される。データ登録部203は、プロキシ鍵rk_iをプロキシサーバ装置30に登録する機能を備えている。
【００２１】
プロキシサーバ装置30は、ユーザ装置40-i（ユーザ装置40-1〜40-3を包括的に表現したものであって、i＝1〜3である）から受信した検索要求に対して、サービスプロバイダの秘密鍵およびユーザiの秘密鍵から生成されたユーザiに対応するプロキシ鍵を用いて、暗号化したまま検索を可能とする検索クエリを生成する。また、プロキシサーバ装置30は、データベース装置50から検索クエリに対応した暗号データを検索する。プロキシサーバ装置30は、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。
【００２２】
図３は、プロキシサーバ装置の構成例を示すブロック図である。プロキシサーバ装置30は、図３に示すように、クエリ変換部301と、検索要求部302と、検索結果送信部303とを含む。
【００２３】
クエリ変換部301は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。クエリ変換部301は、ユーザ装置40-iから受信したユーザクエリQ_iと、記憶しているプロキシ鍵rk_iとを入力として、データベース装置50が記憶する暗号データに対して暗号化したまま検索を行うための検索クエリQ_sを生成する機能を備えている。
【００２４】
検索要求部302は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵおよびネットワークインタフェース部によって実現される。検索要求部302は、検索クエリQ_sを用いてデータベース装置50に検索要求を行う機能を備えている。
【００２５】
検索結果送信部303は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵおよびネットワークインタフェース部によって実現される。検索結果送信部303は、検索要求に応じてデータベース装置50から抽出された検索結果をユーザ装置40-iに送信する機能を備えている。
【００２６】
ユーザ装置40-iは、暗号データに対して暗号化したまま検索を行う検索要求を発行する。ユーザ装置40-iは、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。
【００２７】
図４は、ユーザ装置の構成例を示すブロック図である。ユーザ装置40-iは、図４に示すように、登録要求部401-iと、鍵生成部402-iと、プロキシ鍵生成部403-iと、クエリ生成部404-iとを含む。
【００２８】
登録要求部401-iは、具体的には、プログラムに従って動作する情報処理装置のＣＰＵおよびネットワークインタフェース部によって実現される。登録要求部401-iは、サービスへの登録を要求する機能を備えている。
【００２９】
鍵生成部402-iは、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。鍵生成部402-iは、ユーザiの公開鍵pk_iおよびそれに対応する秘密鍵sk_iを生成する機能を備えている。
【００３０】
プロキシ鍵生成部403-iは、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。プロキシ鍵生成部403-iは、サービスプロバイダの秘密鍵sk_sと、ユーザiの秘密鍵sk_iとを入力として、暗号化したまま暗号データの検索を可能とするプロキシ鍵rk_iを生成する機能を備えている。
【００３１】
クエリ生成部404-iは、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。クエリ生成部404-iは、データを検索するためのユーザクエリQ_iを生成する機能を備えている。
【００３２】
図５は、データ登録装置10の構成例を示すブロック図である。データ登録装置10は、具体的には、プログラムに従って動作するパーソナルコンピュータ等の情報処理装置によって実現される。
【００３３】
データ登録装置10は、図５に示すように、サービスプロバイダの公開鍵pk_sおよびデータM（以下、メッセージMともいう）を入力として、暗号データ（以下、検索可能暗号データともいう）を生成する検索可能暗号データ生成部101を含む。検索可能暗号データ生成部101は、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。なお、本実施形態では、検索可能暗号データとは、所定の条件下で検索可能な暗号化されたデータである。ただし、検索可能暗号データは、所定の条件下で検索可能であり、無条件に検索可能であるわけではない。
【００３４】
データベース装置50は、光ディスク装置や磁気ディスク装置等の記憶装置を備えている。データベース装置50の記憶装置は、検索可能暗号化データを含むデータベースを記憶している。データベース装置50は、例えば、データベースサーバであり、パーソナルコンピュータ等の情報処理装置によって実現される。データベース装置50は、データの検索や登録などの要求を受信して処理を行い、結果を返信する機能を備えている。
【００３５】
次に、暗号データ検索システムの動作について説明する。本実施形態の暗号データ検索システムは、サービスプロバイダ鍵生成処理、ユーザ登録処理、データ登録処理および検索処理を実行する。以下、各処理について説明する。
【００３６】
（サービスプロバイダ鍵生成処理）
サービスプロバイダ鍵生成処理について説明する。図６は、サービスプロバイダ鍵生成処理の一例を示す流れ図である。
【００３７】
サービス管理者が入力操作を行うと、サービスプロバイダ装置20は、サービス管理者の入力操作に従って、セキュリティパラメータを入力とし、サービスプロバイダの公開鍵pk_sおよび秘密鍵sk_sを生成する（図６のKEYGEN1)。
【００３８】
次いで、サービスプロバイダ装置20は、公開鍵pk_sを公開し（すなわち、ネットワークを介したアクセスに応じて配信可能とする）、秘密鍵sk_sを秘密裏に（すなわち、公開せずに）管理する(図６のKEYGEN2)。
【００３９】
（ユーザ登録処理）
次に、ユーザ登録処理について説明する。図７は、ユーザ登録処理の一例を示す流れ図である。
【００４０】
ユーザｉが入力操作を行うと、ユーザ装置40-iは、ユーザｉの入力操作に従って、セキュリティパラメータを入力し、ユーザｉの公開鍵pk_iおよび秘密鍵sk_iを生成する。図７に示す例では、ユーザ装置40-Aは、ユーザAの入力操作に従って、セキュリティパラメータを入力し、ユーザAの公開鍵pk_Aおよび秘密鍵sk_Aを生成する（図７のUREG1)。
【００４１】
次いで、ユーザ装置40-iは、サービスプロバイダ装置20に対して、ユーザ登録要求を送信する。図７に示す例では、ユーザ装置40-Aは、サービスプロバイダ装置20に対して、ユーザ登録要求を送信する（図７のUREG2）。
【００４２】
ユーザ登録要求を受信したサービスプロバイダ装置20と、ユーザ装置40-iとは、対話しながら（具体的には、相互に通信を行いながら）プロキシ鍵rk_iを生成する。このとき、ユーザ登録要求にユーザｉの秘密鍵sk_iを含めて送信することにより、サービスプロバイダ装置20は、単独でプロキシ鍵rk_iを生成することができる。その場合には、サービスプロバイダ装置20とユーザ装置40-iとは、特に対話を行わない。図７に示す例では、サービスプロバイダ装置20とユーザ装置40-Aとは、対話しながらプロキシ鍵rk_Aを生成する(図７のUREG3)。
【００４３】
次いで、サービスプロバイダ装置20は、プロキシサーバ装置30に、ユーザを識別するデータと生成したプロキシ鍵rk_iとを対応付けたデータ（ユーザi，rk_i)を送信し、記憶させる。図７に示す例では、サービスプロバイダ装置20は、プロキシサーバ装置30に、ユーザを識別するデータと生成したプロキシ鍵rk_Aとを対応付けたデータ（ユーザA，rk_A)を送信し、記憶させる(図７のUREG4)。
【００４４】
（データ登録処理）
次に、データ登録処理について説明する。図８は、データ登録処理の一例を示す流れ図である。
【００４５】
データ登録者が登録操作を行うと、データ登録装置10は、データ登録者の登録操作に従って、サービスプロバイダの公開鍵pk_sと、登録したいメッセージMとを入力として、検索可能暗号文E(pk_s,M)を生成する（図８のDREG1)。
【００４６】
次いで、データ登録装置10は、検索可能暗号文E(pk_s,M)をデータベース装置50に送信し、記憶させる（図８のDREG2）。
【００４７】
（検索処理）
次に、検索処理について説明する。図９は、検索処理の一例を示す流れ図である。
【００４８】
ユーザｉが入力操作を行うと、ユーザ装置40-iは、ユーザｉの入力操作に従って、ユーザｉの秘密鍵sk_iと、検索対象キーワードKWとを入力し、ユーザクエリTR(sk_i,KW)を生成する。そして、ユーザ装置40-iは、生成したユーザクエリTR(sk_i,KW)をプロキシサーバ装置30に送信する。
【００４９】
図９に示す例では、ユーザＡが入力操作を行うと、ユーザ装置40-Aは、ユーザＡの入力操作に従って、ユーザＡの秘密鍵sk_Aと、検索対象キーワードKWとを入力し、ユーザクエリTR(sk_A,KW)を生成する（図９のSRC1）。そして、ユーザ装置40-Aは、生成したユーザクエリTR(sk_A,KW)をプロキシサーバ装置30に送信する。
【００５０】
次いで、プロキシサーバ装置30は、受信したユーザクエリTR(sk_i,KW)と、記憶しているプロキシ鍵rk_iとを入力として、検索クエリTR(sk_s,KW)を生成し、データベース装置50に送信する。例えば、プロキシサーバ装置30は、受信したユーザクエリTR(sk_i,KW)と、記憶しているユーザを識別するデータと生成したプロキシ鍵rk_iとを対応付けたデータ（ユーザi，rk_i)とに基づいて、プロキシ鍵を特定する。そして、プロキシサーバ装置30は、受信したユーザクエリTR(sk_i,KW)と、特定したプロキシ鍵rk_iとを入力として、検索クエリTR(sk_s,KW)を生成する。
【００５１】
図９に示す例では、プロキシサーバ装置30は、受信したユーザクエリTR(sk_A,KW)と、記憶しているプロキシ鍵rk_Aとを入力として、検索クエリTR(sk_s,KW)を生成し、データベース装置50に送信する（図９のSRC2）。
【００５２】
次いで、データベース装置50は、内部に記憶した暗号文の集合および検索クエリTR(sk_s,KW)を入力として、検索結果Resultを生成し、検索結果Resultをプロキシサーバ装置30に送信する（図９のSRC3）。具体的には、データベース50装置は、記憶している検索可能暗号化データから受信した検索クエリTR(sk_s,KW)に基づいてデータを検索して抽出し、検索結果としてプロキシサーバ装置30に送信する。
【００５３】
次いで、プロキシサーバ装置30は、検索結果Resultをユーザ装置40-iに送信する。図９に示す例では、プロキシサーバ装置30は、検索結果Resultをユーザ装置40-Aに送信する（図９のSRC4）。
【００５４】
次に、具体例を用いて暗号データ検索システムの動作を説明する。なお、以降、a^bと記載することでaのb乗を表す。
【００５５】
まず、ペアリング関数について説明する。G,G_Tを位数qを持つ巡回群とし、g_1,g_2をそれぞれGの生成元としたとき、ペアリング関数e:G×G→G_Tは、任意のZ_qの元a,bに対して以下の性質を満たす2入力1出力の関数である。
・e(g_1^a,g_2^b)=e(g_1,g_2)^{ab}
・e(g_1,g_2)≠1
【００５６】
次に、非特許文献１に記載された検索可能暗号方式について説明する。非特許文献１に記載された方式は、秘密鍵を持つユーザのみが検索可能な検索可能暗号方式である。各エンティティに対してシステムパラメータとしてq,G,G_T,Gの生成元g,ペアリング関数e:G×G→G_T、任意のビット列からGへのハッシュ関数H_1、G_Tの元からkビットのビット列へのハッシュ関数H_2が与えられている。
【００５７】
（非特許文献１に記載された鍵生成処理）
ユーザは、Z_qからランダムにxを選択する。次いで、ユーザは、g^xを計算する。そして、ユーザは、秘密鍵をx、公開鍵をg^xとし、公開鍵を公開する。なお、具体的には、情報処理装置がユーザの操作に従ってこれらの処理を実行する。
【００５８】
（非特許文献１に記載された検索可能暗号データ生成処理）
データ登録者は、公開鍵g^xと、登録したいデータMとを入力として、Z_qからランダムにrを選択し、検索可能暗号データ(C_1,C_2)=(H_2(e(H_1(M),(g^x)^r)),g^r)を生成し、データベースに送信して記憶させる。なお、具体的には、情報処理装置がデータ登録者の操作に従ってこれらの処理を実行する。
【００５９】
（非特許文献１に記載された検索処理）
ユーザは、検索キーワードKWと、秘密鍵xとを入力として、Q=H_1(KW)^sを生成し、検索クエリとしてデータベースに送信する。なお、具体的には、情報処理装置がユーザの操作に従ってこれらの処理を実行する。データベースは、自身が記憶している検索可能暗号データの集合{(C_1,C_2)}の各要素に対して、C_1=H_2(e(Q,C_2))が成立するか否かを確認する。そして、データベースは、等号が成立した検索可能暗号データ(C_1,C_2)を検索結果として出力する。なお、具体的には、データベースを記憶する記憶装置を備えた情報処理装置が検索クエリを受信し、これらの処理を実行する。
【００６０】
次に、本実施形態の暗号データ検索システムが実行するサービスプロバイダ鍵生成、ユーザ登録、データ登録および検索の各処理について説明する。各エンティティに対して、システムパラメータとして、q,G,G_T,Gの生成元g,ペアリング関数e:G×G→G_T、任意のビット列からGへのハッシュ関数H_1、G_Tの元からkビットのビット列へのハッシュ関数H_2が与えられている。
【００６１】
（サービスプロバイダ鍵生成処理）
サービスプロバイダ鍵生成処理の具体例について説明する。図１０は、サービスプロバイダ鍵生成処理の具体例を示す流れ図である。
【００６２】
図１０に示すように、サービスプロバイダ装置20は、非特許文献１に記載された鍵生成処理と同様の処理を実行する（図１０のKEYGEN1）。
【００６３】
次いで、サービスプロバイダ装置20は、生成したサービスプロバイダの公開鍵をpk_s=g^sとして公開し、秘密鍵をsk_s=sとして保管する（図１０のKEYGEN2）。
【００６４】
（ユーザ登録処理）
次に、ユーザ登録処理の具体例について説明する。図１１は、ユーザ登録処理の具体例を示す流れ図である。
【００６５】
ユーザ装置40-iは、ユーザiの操作に従って、非特許文献１の鍵生成処理と同様の処理を実行し、公開鍵pk_i=g^{x_i}と、秘密鍵(x_i)とを生成する(図１１のUREG1)。
【００６６】
次いで、ユーザ装置40-iは、ユーザ登録要求をサービスプロバイダ装置20に送信する(図１１のUREG2)。
【００６７】
さらに、ユーザ装置40-iは、秘密鍵x_iをサービスプロバイダ装置20に送信する。すると、サービスプロバイダ装置20は、プロキシ鍵rk_i=s/x_iを生成し、プロキシサーバ装置30にユーザを識別するデータと生成したプロキシ鍵とを対応付けたデータ（ユーザi,rk_i）を送信する(図１１のUREG3）。
【００６８】
次いで、プロキシサーバ装置30は、ユーザを識別するデータとプロキシ鍵とを対応付けたデータ(ユーザi,rk_i）を記憶部に記憶する(図１１のUREG4)。
【００６９】
（データ登録処理）
次に、データ登録処理の具体例について説明する。図１２は、データ登録処理の具体例を示す流れ図である。
【００７０】
データ登録装置10は、データ登録者の登録操作に従って、サービスプロバイダの公開鍵pk_sおよび登録するデータMを入力として、非特許文献１の検索可能暗号データ生成処理を実行する（図１２のDREG1）。具体的には、データ登録装置10は、検索可暗号データとして(C_1,C_2)=(H_2(e(H_1(M),pk_s^r)),g^r)を生成する。
【００７１】
次いで、データ登録装置10は、検索可能暗号データ(C_1,C_2)をデータベース装置50に送信し、記憶させる（図１２のDREG2）。
【００７２】
（検索処理）
次に、検索処理の具体例について説明する。図１３は、検索処理の具体例を示す流れ図である。ここでは、データベース装置50は、データ登録処理によってN個の検索可能暗号データ{(C_1,C_2)_i}を記憶しているとする。
【００７３】
ユーザ装置40-iは、ユーザiの入力操作に従って、秘密鍵sk_iと、検索対象キーワードKWとを入力として、ユーザクエリTR(sk_i,KW)=H_1(KW)^{x_i}を生成し、プロキシサーバ装置30に送信する（図１３のSRC1）。
【００７４】
次いで、プロキシサーバ装置30は、受信したユーザクエリTR(sk_i,KW)と、プロキシ鍵rk_iとを入力として、検索クエリTR(sk_s,KW)=TR(sk_i,KW)^{rk_i}=H_1(KW)^{s}を生成し、データベース装置50に送信する（図１３のSRC2）。
【００７５】
次いで、データベース装置50は、自身が記憶している検索可能暗号データの集合{(C_1,C_2)}の各要素に対して、C_1=H_2(e(TR(sk_i,KW),C_2))が成立するか否かを確認する。そして、データベース装置50は、等号が成立した検索可能暗号データ(C_1,C_2)を検索結果としてプロキシサーバ装置30に送信する（図１３のSRC3）。
【００７６】
次いで、プロキシサーバ装置30は、受信した検索結果をユーザ装置40-iに送信する（図１３のSRC4）。
【００７７】
なお、プロキシサーバ装置30は、安全のために、検索を行う前にユーザ認証を行うことが望ましい。ユーザ認証の方法として、例えば、既存のID/Passwordを用いた方法や、電子署名を用いた方法などを用いることができる。
【００７８】
また、プロキシ鍵生成処理に関しては、マルチパーティ計算を行うことにより、サービスプロバイダの秘密鍵s、ユーザiの秘密鍵x_iを互いに秘密にしたままs/x_iを計算できることが知られている。本システムにおいても、マルチパーティ計算を利用してs/x_iを計算してもよい。
【００７９】
さらに、本実施形態では、検索可能暗号データのデータサイズを小さくするためにハッシュ関数H_2を用いているが、H_2を省略しても構わない。
【００８０】
本実施形態では、検索可能暗号データは(C_1,C_2)=(H_2(e(H_1(M),pk_s^r)),g^r)となる。秘密鍵sk_sまたはユーザiの秘密鍵sk_iおよびプロキシ鍵rk_iを用いずに、サービスプロバイダの公開鍵および(C_1,C_2)だけを用いて、検索処理を行うことは難しい。また、プロキシサーバ装置はs/aを保持するが、sまたはa（すなわち、サービスプロバイダの秘密鍵またはユーザの秘密鍵）が分からない限り、検索クエリを生成することもできない。したがって、プロキシサーバ装置の管理者が悪意を持って行動した場合でも、データベースに記憶された検索可能暗号データの集合に対して、任意のキーワードに対する検索を行うことができない。
【００８１】
以上に説明したように、本実施形態の第１の効果は、異なる公開鍵・秘密鍵を有する複数ユーザからの検索要求に対し検索結果を回答できることにある。これにより、１つのデータに対して複数ユーザが暗号化したまま検索を行うことが可能となる。
【００８２】
また、本実施形態の第２の効果は、データベース内に記憶された検索可能暗号データが漏洩した場合であっても、サービスプロバイダの秘密鍵が漏洩しなければ、データの内容に関するいかなる情報も漏えいしないことにある。これにより、万が一データベース内のデータが漏洩した場合にも、情報漏えいの被害を軽減できる。
【００８３】
したがって、本実施形態の暗号データ検索システムは、異なる公開鍵・秘密鍵を有する複数ユーザからの検索要求に対し検索結果を回答でき、かつデータ漏洩による被害を低減することができる。
【００８４】
実施形態２．
次に、本発明の第２の実施形態について説明する。本実施形態の暗号データ検索システムは、第１の実施形態と同様の構成を備えている。また、本実施形態では、ユーザ装置は、図１４に示すように、第1の実施形態の構成に加えて、署名・検証鍵生成部405-iと、署名データ生成部406-iとを含む。署名・検証鍵生成部405-iおよび署名データ生成部406-iは、具体的には、プログラムに従って動作する情報処理装置のＣＰＵによって実現される。
【００８５】
本実施形態では、電子署名を利用する。まず、電子署名について説明する。電子署名には、鍵生成、署名生成および署名検証の３つのアルゴリズムがある。
【００８６】
鍵生成アルゴリズムは、セキュリティパラメータを入力とし、署名を生成するための鍵である署名鍵skと、署名を検証するための鍵である検証鍵vkとを生成する。例えば、本実施形態では、署名・検証鍵生成部405-iが、セキュリティパラメータを入力とし、署名鍵skと検証鍵vkとを生成する。
【００８７】
署名生成アルゴリズムは、署名対象メッセージMと、署名者の署名鍵skとを入力とし、署名データ（M，σ）を出力する。例えば、本実施形態では、署名データ生成部406-iが、署名対象メッセージMと署名者の署名鍵skとを入力とし、署名データ（M，σ）を生成して出力する。
【００８８】
署名検証アルゴリズムは、署名データ（M，σ）と、署名者の検証鍵vkとを入力とし、受理または不受理を示す検証結果を出力する。例えば、本実施形態では、データベース装置５０が、署名データ（M，σ）と、署名者の検証鍵vkとを入力とし、受理または不受理を示す検証結果を出力する。
【００８９】
次に、本実施形態の暗号データ検索システムのサービスプロバイダ鍵生成、ユーザ登録、データ登録、検索の各処理について説明する。ここでは、各エンティティに対してシステムパラメータとして、q,G,G_T,Gの生成元g,ペアリング関数e:G×G→G_T、任意のビット列からGへのハッシュ関数H_1、G_Tの元からkビットのビット列へのハッシュ関数H_2が与えられている。
【００９０】
（サービスプロバイダ鍵生成処理）
本実施形態のサービスプロバイダ鍵生成処理について説明する。サービスプロバイダ装置20は、非特許文献１に記載された鍵生成処理と同様の処理を実行する。次いで、サービスプロバイダ装置20は、生成したサービスプロバイダの公開鍵をpk_s=g^sとして公開し、秘密鍵をsk_s=sとして保管する。
【００９１】
（ユーザ登録処理）
次に、ユーザ登録処理について説明する。ユーザ装置40-iは、ユーザiの操作に従って、署名生成の鍵生成を行い、検証鍵vk_iと秘密鍵sk_iとを生成する。
【００９２】
次いで、ユーザ装置40-iは、ユーザ登録要求をサービスプロバイダ装置20に送信する。さらに、ユーザ装置40-iは、検証鍵vk_iをサービスプロバイダ装置20に送信する。
【００９３】
次いで、サービスプロバイダ装置20は、サービスプロバイダの秘密鍵sk_sおよびユーザの検証鍵vk_iを、プロキシサーバ装置30に送信する。
【００９４】
次いで、プロキシサーバ装置30は、ユーザを識別する情報と検証鍵とを対応付けたデータ(ユーザi,vk_i）およびサービスプロバイダの秘密鍵sk_sを記憶部に記憶する。
【００９５】
（データ登録処理）
次に、データ登録処理について説明する。本実施形態のデータ登録処理は、第１の実施形態のデータ登録処理と同様である。
【００９６】
データ登録装置10は、データ登録者の登録操作に従って、サービスプロバイダの公開鍵pk_sおよび登録するデータMを入力として、非特許文献１の検索可能暗号データ生成処理を実行する。具体的には、データ登録装置10は、検索可能暗号データとして(C_1,C_2)=(H_2(e(H_1(M),pk_s^r)),g^r)を生成する。
【００９７】
次いで、データ登録装置10は、検索可能暗号データ(C_1,C_2)をデータベース装置50に送信し、記憶させる。
【００９８】
（検索処理）
次に、検索処理について説明する。ここでは、データベース装置50は、データ登録処理によってN個の検索可能暗号データ{(C_1,C_2)_i}を記憶しているとする。
【００９９】
ユーザ装置40-iは、ユーザiの入力操作に従って、検索対象キーワードKWを入力として、ユーザクエリH_1(KW)を生成し、プロキシサーバ装置30に送信する。
【０１００】
次いで、プロキシサーバ装置30は、受信したユーザクエリH_1(KW)と、サービスプロバイダの秘密鍵sk_sとを入力として、検索クエリTR(sk_s,KW)=H_1(KW)^{s}を生成し、ユーザ装置40-iに送信する。
【０１０１】
次いで、ユーザ装置40-iは、受信した検索クエリTR(sk_s,KW)と、署名鍵sk_iとを入力として、検索クエリTR(sk_s,KW)に対して署名データ（TR(sk_s,KW)，σ）を生成し、データベース装置50に送信する。
【０１０２】
次いで、データベース装置50は、ユーザ装置40-iから受信した署名データ（TR(sk_s,KW)，σ）と、ユーザiの検証鍵vk_iとを入力として、署名検証を行う。
【０１０３】
署名検証結果が拒否であった場合、データベース装置50は、ユーザiに署名が拒否であった旨を通知し、動作を停止する。一方、署名検証結果が受理であった場合、データベース装置50は、自身が記憶している検索可能暗号データの集合{(C_1,C_2)}の各要素に対して、C_1=H_2(e(TR(sk_i,KW),C_2))が成立するか否かを確認する。そして、データベース装置50は、等号が成立した検索可能暗号データ(C_1,C_2)を検索結果としてユーザ装置40-iに送信する。
【０１０４】
プロキシサーバ装置30は、安全のために、検索を行う前にユーザ認証を行うことが望ましい。ユーザ認証の方法として、例えば、既存のID/Passwordを用いた方法や、電子署名を用いた方法などを用いることができる。
【０１０５】
本実施形態では、データベースが検索を行う際に、検索クエリに付与された電子署名の検証を行う。また、プロキシサーバ装置はs（すなわち、サービスプロバイダの秘密鍵）を保持するため、任意のキーワードに対する検索クエリを生成できるが、ユーザの電子署名を生成することができない。そのため、プロキシサーバ装置の管理者が悪意を持って行動した場合であっても、データベースに記憶された検索可能暗号データの集合に対して、任意のキーワードに対する検索を行うことができない。
【０１０６】
したがって、本実施形態の暗号データ検索システムは、異なる公開鍵・秘密鍵を有する複数ユーザからの検索要求に対し検索結果を回答でき、かつデータ漏洩による被害を低減することができる。
【０１０７】
なお、本発明は、上記に示した実施形態に限定されるものではなく、本発明の技術思想の範囲内において、実施例を適宜変更して実施可能である。
【０１０８】
次に、本発明による暗号データ検索システムの最小構成について説明する。図１５は、暗号データ検索システムの最小の構成例を示すブロック図である。図１５に示すように、暗号データ検索システムは、最小の構成要素として、サービス提供装置２と、データ登録装置１と、データベース装置５と、ユーザ装置４と、プロキシ装置３とを備えている。
【０１０９】
図１５に示す最小構成の暗号データ検索システムでは、サービス提供装置２は、データを暗号化するためのサービス公開鍵およびサービス公開鍵に対応したサービス秘密鍵を生成する。また、サービス提供装置２は、データの検索を要求するユーザ装置４が生成したユーザ秘密鍵とサービス秘密鍵とを入力として、ユーザ装置４ごとのプロキシ鍵を生成し、プロキシ装置３に送信する。また、データベース装置５は、データ登録装置１がサービス公開鍵およびデータを入力として生成した検索可能暗号データを記憶する。
【０１１０】
ユーザ装置４は、データベース装置５に記憶された検索可能暗号データに対して、データの検索を要求するためのユーザクエリを、ユーザ秘密鍵を用いて生成し、プロキシ装置３に送信する。すると、プロキシ装置３は、ユーザ装置４から受信したユーザクエリとサービス提供装置２から受信したユーザ装置４ごとのプロキシ鍵とを入力として、データベース装置５に記憶されている検索可能暗号データの検索を要求するための検索クエリを生成する。
【０１１１】
従って、最小構成の暗号データ検索システムによれば、異なる公開鍵・秘密鍵を有する複数ユーザからの検索要求に対し検索結果を回答でき、かつデータ漏洩による被害を低減することができる。
【０１１２】
なお、本実施形態では、以下の（１）〜（５）に示すような暗号データ検索システムの特徴的構成が示されている。
【０１１３】
（１）暗号データ検索システムは、サービス提供装置（例えば、サービスプロバイダ装置20によって実現される）と、データ登録装置（例えば、データ登録装置10によって実現される）と、データベース装置（例えば、データベース装置50によって実現される）と、ユーザ装置（例えば、ユーザ装置40-iによって実現される）と、プロキシ装置（例えば、プロキシサーバ装置30によって実現される）とを備え、サービス提供装置は、データを暗号化するためのサービス公開鍵（例えば、pk_s）およびサービス公開鍵に対応したサービス秘密鍵（例えば、sk_s）を生成し（例えば、鍵生成部201によって実現される）、データの検索を要求するユーザ装置が生成したユーザ秘密鍵（例えば、pk_i）とサービス秘密鍵とを入力として、ユーザ装置ごとのプロキシ鍵（例えば、rk_i）を生成し、プロキシ装置に送信し（例えば、プロキシ鍵生成部202によって実現される）、データ登録装置は、サービス公開鍵およびデータ（例えば、データM）を入力として、検索可能暗号データを生成し（例えば、検索可能暗号データ生成部101によって実現される）、データベース装置は、検索可能暗号データを記憶し、ユーザ装置は、データベース装置に記憶された検索可能暗号データに対して、データの検索を要求するためのユーザクエリ（例えば、Q_i）を生成し、プロキシ装置に送信し（例えば、クエリ生成部404-iによって実現される）、プロキシ装置は、ユーザ装置から受信したユーザクエリとサービス提供装置から受信したユーザ装置ごとのプロキシ鍵とを入力として、データベース装置に記憶されている検索可能暗号データの検索を要求するための検索クエリ（例えば、Q_s）を生成し（例えば、クエリ変換部301によって実現される）、ユーザ装置は、さらに、ユーザ秘密鍵を用いてユーザクエリを生成することを特徴とする。
【０１１４】
（２）暗号データ検索システムにおいて、サービス提供装置は、サービス秘密鍵とユーザ秘密鍵とを入力として、ユーザ装置ごとのプロキシ鍵を生成し、プロキシ装置は、ユーザクエリおよびプロキシ鍵を入力として、検索クエリを生成し、データベース装置は、検索クエリとデータベース装置が記憶する検索可能暗号データとを入力として、検索結果を生成するように構成されていてもよい。
【０１１５】
（３）暗号データ検索システムにおいて、データ登録装置は、素数位数qを持つ群G，G_T、e()をGの元2つを入力としてG_Tの群への写像であるペアリング関数、gを群Gの生成元、H_1を任意のビット列からG上へのハッシュ関数、H_2をG_Tからkビットのビット列上へのハッシュ関数、Mをメッセージ、Z_qの乱数r、sをサービス秘密鍵、gsをサービス公開鍵としたとき、H_2(e(H_1(M),gs)r),grを含む検索可能暗号データを生成し、ユーザ装置は、aをユーザ秘密鍵、gaをユーザ公開鍵とし、検索キーワードをKWとしたとき、H_1(KW)aを含むユーザクエリを生成するように構成されていてもよい。
【０１１６】
（４）暗号データ検索システムにおいて、プロキシ装置は、ユーザ装置のプロキシ鍵がs/aを含み、検索キーワードをKWとしたとき、H_1(KW)sを含む検索クエリを生成するように構成されていてもよい。
【０１１７】
（５）暗号データ検索システムにおいて、ユーザ装置は、検証鍵と署名鍵とを生成し（例えば、検証・署名鍵生成405-iによって実現される）、プロキシ装置が生成した検索クエリと署名鍵とを入力として、署名データを生成し（例えば、署名データ生成406-iによって実現される）、データベース装置は、署名データと検証鍵とを入力として、署名検証を行うように構成されていてもよい。
【産業上の利用可能性】
【０１１８】
本発明は、通信ネットワークを介して、ユーザのＩＤを秘匿にして認証を行う匿名認証に好適に適用できる。
【符号の説明】
【０１１９】
１  データ登録装置
２  サービス提供装置
３  プロキシ装置
４  ユーザ装置
５  データベース装置
【図１】
0005799635.tif 000002
【図２】
0005799635.tif 000003
【図３】
0005799635.tif 000004
【図４】
0005799635.tif 000005
【図５】
0005799635.tif 000006
【図６】
0005799635.tif 000007
【図７】
0005799635.tif 000008
【図８】
0005799635.tif 000009
【図９】
0005799635.tif 000010
【図１０】
0005799635.tif 000011
【図１１】
0005799635.tif 000012
【図１２】
0005799635.tif 000013
【図１３】
0005799635.tif 000014
【図１４】
0005799635.tif 000015
【図１５】
0005799635.tif 000016