(57)【特許請求の範囲】
【請求項１】
補助タグ記憶部に記憶された補助タグであって、タグ生成装置によって検索ワードが変換されて生成された補助タグのうち、キーワードが変換されて得られた補助クエリに対応する補助タグの対応数をカウントする補助照合部と、
暗号化タグ記憶部に記憶された暗号化タグであって、前記タグ生成装置によってアクセス可能な属性を示すアクセス条件と前記検索ワードとが設定されて生成された暗号化タグのうち、ユーザの属性を示す属性情報と前記キーワードとが設定された検索クエリに対応する暗号化タグを、特定された暗号化タグの数が前記補助照合部によってカウントされた前記対応数になるまで特定する主照合部と
を備える検索装置。
【請求項２】
前記補助タグは、共通鍵暗号又はハッシュ関数である対象方式に補助鍵と前記検索ワードとが入力されて、前記検索ワードが変換されて生成され、
前記補助クエリは、前記対象方式に前記補助鍵と前記キーワードとを入力して、前記キーワードが変換して生成される
請求項１に記載の検索装置。
【請求項３】
前記主照合部は、ペアリング演算を行うことにより、前記検索クエリに対応する前記暗号化タグを特定する
請求項１又は２に記載の検索装置。
【請求項４】
タグ生成装置とクエリ生成装置と検索装置とを備える秘匿検索システムであり、
前記タグ生成装置は、
検索ワードを変換して補助タグを生成する補助タグ生成部と、
アクセス可能な属性を示すアクセス条件と前記検索ワードとを設定して、暗号化タグを生成する暗号化タグ生成部と
を備え、
前記クエリ生成装置は、
キーワードを変換して補助クエリを生成する補助クエリ生成部と、
ユーザの属性を示す属性情報と前記キーワードとを設定して、検索クエリを生成する検索クエリ生成部と
を備え、
前記検索装置は、
前記補助タグ生成部によって生成された前記補助タグを記憶する補助タグ記憶部と、
前記暗号化タグ生成部によって生成された前記暗号化タグを記憶する暗号化タグ記憶部と、
前記補助タグ記憶部に記憶された前記補助タグのうち、前記補助クエリ生成部によって生成された補助クエリに対応する前記補助タグの対応数をカウントする補助照合部と、
前記暗号化タグ記憶部に記憶された前記暗号化タグのうち、前記検索クエリ生成部によって生成された前記検索クエリに対応する前記暗号化タグを、特定された暗号化タグの数が前記補助照合部によってカウントされた前記対応数になるまで特定する主照合部と
を備える秘匿検索システム。
【請求項５】
補助タグ記憶部に記憶された補助タグであって、タグ生成装置によって検索ワードが変換されて生成された補助タグのうち、キーワードが変換されて得られた補助クエリに対応する補助タグの対応数をカウントする補助照合処理と、
暗号化タグ記憶部に記憶された暗号化タグであって、前記タグ生成装置によってアクセス可能な属性を示すアクセス条件と前記検索ワードとが設定されて生成された暗号化タグのうち、ユーザの属性を示す属性情報と前記キーワードとが設定された検索クエリに対応する暗号化タグを、特定された暗号化タグの数が前記補助照合処理によってカウントされた前記対応数になるまで特定する主照合処理と
をコンピュータに実行させる検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データが暗号化された状態で検索処理を実行可能な秘匿検索技術に関する。
【背景技術】
【０００２】
近年、ネットワーク、特にインターネットにおける演算資源を用いて、様々なサービスを実行し提供するクラウドコンピューティング技術が存在する。これらのサービスとして、ネットワークに様々なデータを保管しておき、データの利用が許可された検索者のみがそのデータをダウンロードし利用する、といったサービスが考えられる。
しかし、ネットワークに保管するデータの中には、ユーザの個人情報といった第三者に漏洩することのない様に秘匿する必要があるデータが存在する場合がある。このようなデータは、秘密鍵暗号や公開鍵暗号といった暗号により秘匿可能である。【０００３】
このように、暗号化したデータをネットワークに置くことで、データの秘匿化とクラウドコンピューティングの活用の両立をすることができる。しかし、データは暗号化してしまうことで検索ができなくなってしまうという課題がある。この課題を解決する技術として秘匿検索技術がある。秘匿検索技術では、特別な暗号化方法を用いることによって、暗号化された状態のデータが検索可能である。【０００４】
秘匿検索技術においては、検索するユーザが、検索可能な情報にのみアクセスできることが重要である。
特許文献１及び非特許文献１には、ＩＤベース暗号や内積述語暗号といった公開鍵暗号技術を用いることによって、アクセス制御可能な秘匿検索技術について記載されている。非特許文献２には、共通鍵を用いた秘匿検索技術について記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特願２０１１−５４９８２２号公報
【非特許文献】
【０００６】
【非特許文献１】松田規，  伊藤隆，  柴田秀哉，  服部充洋，  ａｎｄ  平野貴人．  検索可能暗号の高速化とＷｅｂ  アプリケーションへの適用方式に関する提案．  Ｉｎ  ＤＩＣＯＭＯ  ２０１３  （ＤＳ−２），  ２０１３．
【非特許文献２】Ｒ．Ｃｕｒｔｍｏｌａ，Ｊ．Ｇａｒａｙ，Ｓ．Ｋａｍａｒａ，ａｎｄ  Ｒ．Ｏｓｔｒｏｖｓｋｙ．“Ｓｅａｒｃｈａｂｌｅ  Ｓｙｍｍｅｔｒｉｃ  Ｅｎｃｒｙｐｔｉｏｎ：Ｉｍｐｒｏｖｅｄ  Ｄｅｆｉｎｉｔｉｏｎｓ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ”．ＡＣＭ  ＣＣＳ  ２００６．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１及び非特許文献１に記載された秘匿検索技術は、検索処理時間が長くかかることが知られている。非特許文献２に記載された秘匿検索技術は、特許文献１及び非特許文献１に記載された秘匿検索技術に比べて検索処理が速いものの、暗号学的なアクセス制御ができない。
この発明は、柔軟なアクセス制御を実現しつつ、検索にかかる処理時間を短くすることを可能とすることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る検索装置は、
補助タグ記憶部に記憶された補助タグであって、検索ワードが変換されて得られた補助タグに、キーワードが変換されて得られた補助クエリに対応する前記補助タグがあるか否か判定する補助照合部と、
前記補助クエリに対応する前記補助タグがあると前記補助照合部によって判定された場合に、暗号化タグ記憶部に記憶された暗号化タグであって、アクセス可能な属性を示すアクセス条件と前記検索ワードとが設定された暗号化タグのうち、ユーザの属性を示す属性情報と前記キーワードとが設定された検索クエリに対応する前記暗号化タグを特定する主照合部と
を備える。
【発明の効果】
【０００９】
この発明では、検索クエリに対応する暗号化タグを検索する前に、補助クエリに対応する補助タグがあるか否か判定する。これにより、補助クエリに対応する補助タグがない場合に、処理時間が長くかかる検索クエリに対応する暗号化タグを検索する処理を実行する必要がなくなり、検索にかかる処理時間を短くすることが可能になる。また、検索クエリに対応する暗号化タグについては、柔軟なアクセス制御を行うことが可能である。
【図面の簡単な説明】
【００１０】
【図１】実施の形態１に係る秘匿検索システム１の構成図。
【図２】実施の形態１に係る共通パラメータ生成装置１０の構成図。
【図３】実施の形態１に係る補助鍵生成装置２０の構成図。
【図４】実施の形態１に係るユーザ鍵生成装置３０の構成図。
【図５】実施の形態１に係るタグ生成装置４０の構成図。
【図６】実施の形態１に係るクエリ生成装置５０の構成図。
【図７】実施の形態１に係る検索装置６０の構成図。
【図８】実施の形態１に係る共通パラメータ生成処理のフローチャート。
【図９】実施の形態１に係る補助鍵生成処理のフローチャート。
【図１０】実施の形態１に係るユーザ鍵生成処理のフローチャート。
【図１１】実施の形態１に係るタグ生成処理のフローチャート。
【図１２】実施の形態１に係るクエリ生成処理のフローチャート。
【図１３】実施の形態１に係る検索処理のフローチャート。
【図１４】変形例２に係る共通パラメータ生成装置１０の構成図。
【図１５】変形例２に係る補助鍵生成装置２０の構成図。
【図１６】変形例２に係るユーザ鍵生成装置３０の構成図。
【図１７】変形例２に係るタグ生成装置４０の構成図。
【図１８】変形例２に係るクエリ生成装置５０の構成図。
【図１９】変形例２に係る検索装置６０の構成図。
【発明を実施するための形態】
【００１１】
実施の形態１．
＊＊＊構成の説明＊＊＊
図１を参照して、実施の形態１に係る秘匿検索システム１の構成を説明する。
秘匿検索システム１は、共通パラメータ生成装置１０と、補助鍵生成装置２０と、１つ以上のユーザ鍵生成装置３０と、１つ以上のタグ生成装置４０と、１つ以上のクエリ生成装置５０と、検索装置６０とを備える。
共通パラメータ生成装置１０と、補助鍵生成装置２０と、各ユーザ鍵生成装置３０と、各タグ生成装置４０と、各クエリ生成装置５０と、各検索装置６０とは、伝送路７０を介して接続されている。伝送路７０は、具体例としては、インターネット、又は、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）である。
【００１２】
なお、共通パラメータ生成装置１０と補助鍵生成装置２０とユーザ鍵生成装置３０との少なくとも２つ以上が１つの装置として実現されてもよい。また、１つの装置がタグ生成装置４０とクエリ生成装置５０との両方の機能を備えていてもよい。
【００１３】
図２を参照して、実施の形態１に係る共通パラメータ生成装置１０の構成を説明する。
共通パラメータ生成装置１０は、コンピュータである。
共通パラメータ生成装置１０は、プロセッサ１１と、メモリ１２と、ストレージ１３と、通信インタフェース１４とのハードウェアを備える。プロセッサ１１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１４】
共通パラメータ生成装置１０は、機能構成要素として、セキュリティパラメータ受付部１１１と、パラメータ生成部１１２と、パラメータ送信部１１３とを備える。共通パラメータ生成装置１０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ１３には、共通パラメータ生成装置１０の各機能構成要素の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ１１によりメモリ１２に読み込まれ、プロセッサ１１によって実行される。これにより、共通パラメータ生成装置１０の各機能構成要素の機能が実現される。
【００１５】
図３を参照して、実施の形態１に係る補助鍵生成装置２０の構成を説明する。
補助鍵生成装置２０は、コンピュータである。
補助鍵生成装置２０は、プロセッサ２１と、メモリ２２と、ストレージ２３と、通信インタフェース２４とのハードウェアを備える。プロセッサ２１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１６】
補助鍵生成装置２０は、機能構成要素として、セキュリティパラメータ受付部２１１と、補助鍵生成部２１２と、補助鍵送信部２１３とを備える。補助鍵生成装置２０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ２３には、補助鍵生成装置２０の各機能構成要素の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ２１によりメモリ２２に読み込まれ、プロセッサ２１によって実行される。これにより、補助鍵生成装置２０の各機能構成要素の機能が実現される。
【００１７】
図４を参照して、実施の形態１に係るユーザ鍵生成装置３０の構成を説明する。
ユーザ鍵生成装置３０は、コンピュータである。
ユーザ鍵生成装置３０は、プロセッサ３１と、メモリ３２と、ストレージ３３と、通信インタフェース３４とのハードウェアを備える。プロセッサ３１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００１８】
ユーザ鍵生成装置３０は、機能構成要素として、パラメータ受付部３１１と、属性受付部３１２と、乱数生成部３１３と、ユーザ鍵生成部３１４と、ユーザ鍵送信部３１５とを備える。ユーザ鍵生成装置３０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ３３には、ユーザ鍵生成装置３０の各機能構成要素の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ３１によりメモリ３２に読み込まれ、プロセッサ３１によって実行される。これにより、ユーザ鍵生成装置３０の各機能構成要素の機能が実現される。
また、ストレージ３３は、パラメータ記憶部３３１の機能を実現する。
【００１９】
図５を参照して、実施の形態１に係るタグ生成装置４０の構成を説明する。
タグ生成装置４０は、コンピュータである。
タグ生成装置４０は、プロセッサ４１と、メモリ４２と、ストレージ４３と、通信インタフェース４４とのハードウェアを備える。プロセッサ４１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２０】
タグ生成装置４０は、機能構成要素として、パラメータ受付部４１１と、アクセス条件受付部４１２と、検索ワード受付部４１３と、乱数生成部４１４と、補助タグ生成部４１５と、暗号化タグ生成部４１６と、タグ送信部４１７とを備える。タグ生成装置４０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ４３には、タグ生成装置４０の各機能構成要素の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ４１によりメモリ４２に読み込まれ、プロセッサ４１によって実行される。これにより、タグ生成装置４０の各機能構成要素の機能が実現される。
また、ストレージ４３は、パラメータ記憶部４３１の機能を実現する。
【００２１】
図６を参照して、実施の形態１に係るクエリ生成装置５０の構成を説明する。
クエリ生成装置５０は、コンピュータである。
クエリ生成装置５０は、プロセッサ５１と、メモリ５２と、ストレージ５３と、通信インタフェース５４とのハードウェアを備える。プロセッサ５１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２２】
クエリ生成装置５０は、機能構成要素として、パラメータ受付部５１１と、キーワード受付部５１２と、乱数生成部５１３と、補助クエリ生成部５１４と、検索クエリ生成部５１５と、クエリ送信部５１６とを備える。クエリ生成装置５０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ５３には、クエリ生成装置５０の各機能構成要素の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ５１によりメモリ５２に読み込まれ、プロセッサ５１によって実行される。これにより、クエリ生成装置５０の各機能構成要素の機能が実現される。
また、ストレージ５３は、パラメータ記憶部５３１の機能を実現する。
【００２３】
図７を参照して、実施の形態１に係る検索装置６０の構成を説明する。
検索装置６０は、コンピュータである。
検索装置６０は、プロセッサ６１と、メモリ６２と、ストレージ６３と、通信インタフェース６４とのハードウェアを備える。プロセッサ６１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
【００２４】
検索装置６０は、機能構成要素として、パラメータ受付部６１１と、タグ受付部６１２と、クエリ受付部６１３と、補助照合部６１４と、主照合部６１５と、結果出力部６１６とを備える。検索装置６０の各機能構成要素の機能はソフトウェアにより実現される。
ストレージ６３には、検索装置６０の各機能構成要素の機能を実現するプログラムが記憶されている。このプログラムは、プロセッサ６１によりメモリ６２に読み込まれ、プロセッサ６１によって実行される。これにより、検索装置６０の各機能構成要素の機能が実現される。
ストレージ６３は、パラメータ記憶部６３１と、補助タグ記憶部６３２と、暗号化タグ記憶部６３３との機能を実現する。
【００２５】
＊＊＊動作の説明＊＊＊
図８から図１３を参照して、実施の形態１に係る秘匿検索システム１の動作を説明する。
実施の形態１に係るタグ生成装置４０の動作は、実施の形態１に係るタグ生成方法に相当する。また、実施の形態１に係るタグ生成装置４０の動作は、実施の形態１に係るタグ生成プログラムの処理に相当する。
実施の形態１に係るクエリ生成装置５０の動作は、実施の形態１に係るクエリ生成方法に相当する。実施の形態１に係るクエリ生成装置５０の動作は、実施の形態１に係るクエリ生成プログラムの処理に相当する。
実施の形態１に係る検索装置６０の動作は、実施の形態１に係る検索方法に相当する。また、実施の形態１に係る検索装置６０の動作は、実施の形態１に係る検索プログラムの処理に相当する。
【００２６】
実施の形態１では、アクセス制御可能な秘匿検索方式として、特許文献１に記載された方式を用いる例を説明する。但し、アクセス制御可能な秘匿検索方式としては、他の方式が用いられてもよい。他の方式が用いられる場合には、以下の説明における特許文献１の方式の記述を用いる方式に合わせて適宜修正すればよい。
【００２７】
図８を参照して、実施の形態１に係る共通パラメータ生成処理を説明する。
（ステップＳ１１：セキュリティパラメータ受付処理）
共通パラメータ生成装置１０のセキュリティパラメータ受付部１１１は、セキュリティパラメータλ１の入力を受け付ける。
セキュリティパラメータλ１は、秘匿検索システム１で用いるユーザ鍵ｕｋのビット数を決めるための情報である。セキュリティパラメータλ１は、共通パラメータ生成装置１０の管理者等により入力される。
【００２８】
（ステップＳ１２：パラメータ生成処理）
共通パラメータ生成装置１０のパラメータ生成部１１２は、ステップＳ１１で受け付けられたセキュリティパラメータλ１に基づき、アクセス制御可能な秘匿検索方式における共通パラメータを生成する。
実施の形態１では、パラメータ生成部１１２は、特許文献１に記載されたシステムの初期設定の処理を実行して、基底Ｂ＊＝（ｂ＊１，ｂ＊２，．．．，ｂ＊Ｎ）を含むマスター鍵と、基底Ｂ＝（ｂ１，ｂ２，．．．，ｂＮ）を含む公開パラメータを生成する。そして、パラメータ生成部１１２は、マスター鍵及び公開パラメータを共通パラメータとして扱う。
【００２９】
（ステップＳ１３：パラメータ送信処理）
共通パラメータ生成装置１０のパラメータ送信部１１３は、ステップＳ１２で生成された共通パラメータを他の装置に伝送路７０を介して送信する。
実施の形態１では、パラメータ送信部１１３は、マスター鍵をユーザ鍵生成装置３０に秘密裡に送信する。秘密裡に送信するとは、例えば、既存の暗号方式によりデータを暗号化して、暗号化されたデータを送信するという意味である。また、パラメータ送信部１１３は、公開パラメータをユーザ鍵生成装置３０とタグ生成装置４０とクエリ生成装置５０と検索装置６０とに送信する。
すると、ユーザ鍵生成装置３０のパラメータ受付部３１１は、送信されたマスター鍵及び公開パラメータを受け付ける。そして、パラメータ受付部３１１は、マスター鍵及び公開パラメータをパラメータ記憶部３３１に書き込む。タグ生成装置４０のパラメータ受付部４１１は、送信された公開パラメータを受け付ける。そして、パラメータ受付部４１１は、公開パラメータをパラメータ記憶部４３１に書き込む。クエリ生成装置５０のパラメータ受付部５１１は、送信された公開パラメータを受け付ける。そして、パラメータ受付部５１１は、公開パラメータをパラメータ記憶部５３１に書き込む。検索装置６０のパラメータ受付部６１１は、送信された公開パラメータを受け付ける。そして、パラメータ受付部６１１は、公開パラメータをパラメータ記憶部６３１に書き込む。
【００３０】
秘匿検索システム１が複数のユーザ鍵生成装置３０を備える場合には、ステップＳ１３でパラメータ生成部１１２は、各ユーザ鍵生成装置３０について、特許文献１に記載された中間秘密鍵生成の処理を実行する。これにより、パラメータ生成部１１２は、各ユーザ鍵生成装置３０用の中間秘密鍵を生成する。そして、ステップＳ１３でパラメータ送信部１１３は、マスター鍵に代えて、中間秘密鍵を対応するユーザ鍵生成装置３０に送信する。
【００３１】
図９を参照して、実施の形態１に係る補助鍵生成処理を説明する。
（ステップＳ２１：セキュリティパラメータ受付処理）
補助鍵生成装置２０のセキュリティパラメータ受付部２１１は、セキュリティパラメータλ２の入力を受け付ける。
セキュリティパラメータλ２は、秘匿検索システム１で用いる補助鍵ａｋのビット数を決めるための情報である。セキュリティパラメータλ２は、補助鍵生成装置２０の管理者等により入力される。
【００３２】
（ステップＳ２２：鍵生成処理）
補助鍵生成装置２０の補助鍵生成部２１２は、ステップＳ２１で受け付けられたセキュリティパラメータλ２に基づき、共通鍵暗号又はハッシュ関数の鍵である補助鍵ａｋを生成する。以下の説明では、共通鍵暗号又はハッシュ関数を対象方式と呼ぶ。共通鍵暗号は、ブロック暗号又はストリーム暗号等である。例えば、補助鍵ａｋは、セキュリティパラメータλ２が示すビット数のランダムなビット列である。
【００３３】
（ステップＳ２３：補助鍵送信処理）
補助鍵生成装置２０の補助鍵送信部２１３は、ステップＳ２２で生成された補助鍵ａｋを他の装置に伝送路７０を介して送信する。
実施の形態１では、補助鍵送信部２１３は、補助鍵ａｋをタグ生成装置４０及びクエリ生成装置５０に秘密裡に送信する。
すると、タグ生成装置４０のパラメータ受付部４１１は、送信された補助鍵ａｋを受け付ける。そして、パラメータ受付部４１１は、補助鍵ａｋをパラメータ記憶部４３１に書き込む。クエリ生成装置５０のパラメータ受付部５１１は、送信された補助鍵ａｋを受け付ける。そして、パラメータ受付部５１１は、補助鍵ａｋをパラメータ記憶部５３１に書き込む。
【００３４】
図１０を参照して、実施の形態１に係るユーザ鍵生成処理を説明する。
（ステップＳ３１：属性受付処理）
ユーザ鍵生成装置３０の属性受付部３１２は、ユーザの属性を示す属性情報ｘの入力を受け付ける。ユーザの属性は、例えば、ユーザが所属する会社、部門と、役職と等である。
【００３５】
（ステップＳ３２：乱数生成処理）
ユーザ鍵生成装置３０の乱数生成部３１３は、ユーザ鍵ｕｋに必要な乱数Ｒ１を生成する。
【００３６】
（ステップＳ３３：鍵生成処理）
ユーザ鍵生成装置３０のユーザ鍵生成部３１４は、ステップＳ３１で受け付けられた属性情報ｘと、ステップＳ３２で生成された乱数Ｒ１と、パラメータ記憶部３３１に記憶された共通パラメータとを用いて、属性情報ｘが設定されたユーザ鍵ｕｋを生成する。
実施の形態１では、ユーザ鍵生成部３１４は、特許文献１に記載されたユーザ秘密鍵生成処理を実行して、ユーザ秘密鍵を生成する。そして、ユーザ鍵生成部３１４は、ユーザ秘密鍵をユーザ鍵ｕｋとして扱う。つまり、ユーザ鍵生成部３１４は、マスター鍵あるいは中間秘密鍵に含まれる基底Ｂ＊の基底ベクトルの係数に、属性情報ｘ及び乱数Ｒ１を設定することにより、ユーザ鍵ｕｋを生成する。
【００３７】
（ステップＳ３４：ユーザ鍵送信処理）
ユーザ鍵生成装置３０のユーザ鍵送信部３１５は、ステップＳ３３で生成されたユーザ鍵ｕｋを、対応するクエリ生成装置５０に伝送路７０を介して秘密裡に送信する。対応するクエリ生成装置５０とは、ステップＳ３１で受け付けられた属性情報ｘが示すユーザが使用するクエリ生成装置５０という意味である。
【００３８】
図１１を参照して、実施の形態１に係るタグ生成処理を説明する。
（ステップＳ４１：アクセス条件受付処理）
タグ生成装置４０のアクセス条件受付部４１２は、アクセス可能な属性を示すアクセス条件ｖの入力を受け付ける。アクセス条件ｖは、例えば、論理式を使って、アクセス可能な属性の集合を表す。アクセス可能な属性とは、アクセスが許可される属性を意味する。
【００３９】
（ステップＳ４２：検索ワード受付処理）
タグ生成装置４０の検索ワード受付部４１３は、ｎ個の検索ワードｗ１，．．．，ｗｎの入力を受け付ける。ｎは、１以上の整数である。検索ワードは、１文字以上の文字列である。
【００４０】
（ステップＳ４３：乱数生成処理）
タグ生成装置４０の乱数生成部４１４は、暗号化タグＥＴに必要な乱数Ｒ２を生成する。
【００４１】
（ステップＳ４４：補助タグ生成処理）
タグ生成装置４０の補助タグ生成部４１５は、ステップＳ４２で受け付けられた検索ワードｗ１，．．．，ｗｎの順序をランダムに入れ替える。順序が入れ替えられた検索ワードをｗ’１，．．．，ｗ’ｎとする。
そして、補助タグ生成部４１５は、検索ワードｗ’１，．．．，ｗ’ｎに対応する補助タグＡＴ１，．．．，ＡＴｎを生成する。具体的には、補助タグ生成部４１５は、共通鍵暗号又はハッシュ関数である対象方式に、ｉ＝１，．．．，ｎの各整数ｉについての検索ワードｗ’ｉと、補助鍵ａｋとを入力して、検索ワードｗ’ｉを変換して補助タグＡＴｉを生成する。
具体例としては、補助タグ生成部４１５は、対象方式としてハッシュ関数Ｈを用いる。そして、補助タグ生成部４１５は、ｉ＝１，．．．，ｎの各整数ｉについて、ＡＴｉ＝Ｈ（ａｋ，ｗ’ｉ）を計算する。
【００４２】
（ステップＳ４５：暗号化タグ生成処理）
タグ生成装置４０の暗号化タグ生成部４１６は、ステップＳ４２で受け付けられた検索ワードｗ１，．．．，ｗｎに対応する暗号化タグＥＴ１，．．．，ＥＴｎを生成する。具体的には、暗号化タグ生成部４１６は、ステップＳ４１で受け付けられたアクセス条件ｖと、ｉ＝１，．．．，ｎの各整数ｉについての検索ワードｗｉと、ステップＳ４３で生成された乱数Ｒ２とを設定して、暗号化タグＥＴｉを生成する。
実施の形態１では、暗号化タグ生成部４１６は、ｉ＝１，．．．，ｎの各整数ｉについて、アクセス条件ｖと検索ワードｗｉと乱数Ｒ２とを入力として、特許文献１に記載されたタグ兼暗号化データ暗号化鍵ｔａｇを生成する。そして、暗号化タグ生成部４１６は、タグ兼暗号化データ暗号化鍵ｔａｇを、暗号化タグＥＴｉとして扱う。
【００４３】
（ステップＳ４６：タグ送信部処理）
タグ生成装置４０のタグ送信部４１７は、ステップＳ４４で生成された補助タグＡＴ１，．．．，ＡＴｎと、ステップＳ４５で生成された暗号化タグＥＴ１，．．．，ＥＴｎと、暗号化タグＥＴ１，．．．，ＥＴｎそれぞれの識別子であるインデックスｊ（例えば、インデックス１，．．．，ｎ）とを検索用のタグとして、検索装置６０に送信する。
すると、検索装置６０のタグ受付部６１２は、送信された補助タグＡＴ１，．．．，ＡＴｎと、暗号化タグＥＴ１，．．．，ＥＴｎと、インデックスｊとを受け付ける。そして、タグ受付部６１２は、補助タグＡＴ１，．．．，ＡＴｎを補助タグ記憶部６３２に書き込む。また、タグ受付部６１２は、暗号化タグＥＴ１，．．．，ＥＴｎと、インデックスｊと関連付けて暗号化タグ記憶部６３３に書き込む。
【００４４】
図１２を参照して、実施の形態１に係るクエリ生成処理を説明する。
（ステップＳ５１：キーワード受付処理）
クエリ生成装置５０のキーワード受付部５１２は、検索を行うキーワードｗの入力を受け付ける。キーワードｗは、１文字以上の文字列である。
【００４５】
（ステップＳ５２：乱数生成処理）
クエリ生成装置５０の乱数生成部５１３は、検索クエリＳＱに必要な乱数Ｒ３を生成する。
【００４６】
（ステップＳ５３：補助クエリ生成処理）
クエリ生成装置５０の補助クエリ生成部５１４は、ステップＳ５１で受け付けられたキーワードｗに対応する補助クエリＡＱを生成する。具体的には、補助クエリ生成部５１４は、共通鍵暗号又はハッシュ関数である対象方式に、キーワードｗと、補助鍵ａｋとを入力して、キーワードｗを変換して補助クエリＡＱを生成する。
この際、補助クエリ生成部５１４は、ステップＳ４４で用いられた対象方式と同じ関数を用いて、補助クエリＡＱを生成する。具体例としては、補助クエリ生成部５１４は、対象方式としてハッシュ関数Ｈを用いる。そして、補助クエリ生成部５１４は、ＡＱ＝Ｈ（ａｋ，ｗ）を計算する。
【００４７】
（ステップＳ５４：検索クエリ生成処理）
クエリ生成装置５０の検索クエリ生成部５１５は、ステップＳ５１で受け付けられたキーワードｗに対応する検索クエリＳＱを生成する。具体的には、検索クエリ生成部５１５は、ユーザの属性を示す属性情報であるアクセス条件ｖとキーワードｗと乱数Ｒ３とを設定して、検索クエリＳＱを生成する。
実施の形態１では、検索クエリ生成部５１５は、キーワードｗとユーザ鍵ｕｋとを入力として、特許文献１に記載されたトラップドアを生成する。検索クエリ生成部５１５は、トラップドアを検索クエリＳＱとして扱う。
【００４８】
（ステップＳ５５：クエリ送信処理）
クエリ生成装置５０のクエリ送信部５１６は、ステップＳ５３で生成された補助クエリＡＱと、ステップＳ５４で生成された検索クエリＳＱとを検索用のクエリとして、検索装置６０に送信する。
【００４９】
図１３を参照して、実施の形態１に係る検索処理を説明する。
（ステップＳ６１：クエリ受付処理）
検索装置６０のクエリ受付部６１３は、ステップＳ５５で送信された補助クエリＡＱ及び検索クエリＳＱを受け付ける。
【００５０】
（ステップＳ６２：補助照合処理）
検索装置６０の補助照合部６１４は、ステップＳ６１で受け付けられた補助クエリＡＱと、補助タグ記憶部６３２に記憶された各補助タグＡＴとを照合する。
具体的には、補助照合部６１４は、補助クエリＡＱと、各補助タグＡＴとが対応するか否かを判定することにより、補助クエリＡＱと各補助タグＡＴとを照合する。補助照合部６１４は、補助クエリＡＱに対応する補助タグＡＴの対応数ｍをカウントする。対応するとは、対象方式に応じて異なるが、例えば一致するということである。
【００５１】
（ステップＳ６３：補助判定処理）
検索装置６０の補助照合部６１４は、補助クエリＡＱに対応する補助タグＡＴがあったか否かを判定する。具体的には、補助照合部６１４は、ステップＳ６２でカウントされた対応数ｍが１以上であるか否かを判定する。
補助照合部６１４は、補助クエリＡＱに対応する補助タグＡＴがあった場合には、処理をステップＳ６４に進める。一方、補助照合部６１４は、補助クエリＡＱに対応する補助タグＡＴがなかった場合には、処理をステップＳ６７に進める。
【００５２】
（ステップＳ６４：主照合処理）
検索装置６０の主照合部６１５は、ステップＳ６１で受け付けられた検索クエリＳＱと、暗号化タグ記憶部６３３に記憶された各暗号化タグＥＴとを照合する。
具体的には、主照合部６１５は、特許文献１に記載されたタグ兼暗号化データ暗号化鍵とトラップドアの比較処理と同様に、検索クエリＳＱと、各暗号化タグＥＴとのペアリング演算を行うことにより、検索クエリＳＱと各暗号化タグＥＴとを照合する。つまり、主照合部６１５は、Ｖ＝ｅ（ＳＱ，ＥＴ）を計算する。そして、主照合部６１５は、Ｖ＝１であれば、検索クエリＳＱと暗号化タグＥＴとが対応していると判定する。また、主照合部６１５は、Ｖ≠１であれば、検索クエリＳＱと暗号化タグＥＴとが対応していないと判定する。
【００５３】
この際、主照合部６１５は、対応していると判定された暗号化タグＥＴの数が、対応数ｍになった場合には、ステップＳ６４の処理を終了して、処理をステップＳ６５に進める。
【００５４】
（ステップＳ６５：主判定処理）
検索装置６０の主照合部６１５は、検索クエリＳＱに対応する暗号化タグＥＴがあったか否かを判定する。
主照合部６１５は、検索クエリＳＱに対応する暗号化タグＥＴがあった場合には、処理をステップＳ６６に進める。一方、検索クエリＳＱに対応する暗号化タグＥＴがなかった場合には、処理をステップＳ６７に進める。
【００５５】
（ステップＳ６６：第１出力処理）
検索装置６０の結果出力部６１６は、ステップＳ６４で検索クエリＳＱに対応すると判定された暗号化タグＥＴに関連付けられたインデックスｊの集合Ｊを出力する。例えば、結果出力部６１６は、集合Ｊを、伝送路７０を介して検索用のクエリの送信元のクエリ生成装置５０に送信する。
【００５６】
（ステップＳ６７：第２出力処理）
検索装置６０の結果出力部６１６は、キーワードｗにより検索されるデータがないことを示す情報を出力する。例えば、結果出力部６１６は、キーワードｗにより検索されるデータがないことを示す情報を伝送路７０を介して検索用のクエリの送信元のクエリ生成装置５０に送信する。
【００５７】
＊＊＊実施の形態１の効果＊＊＊
以上のように、実施の形態１に係る秘匿検索システム１は、補助クエリＡＱに対応する補助タグＡＴがある場合に、検索クエリＳＱに対応する暗号化タグＥＴを特定する。検索クエリＳＱに対応する暗号化タグＥＴを特定する処理は、暗号学的なアクセス制御が行われるため、処理時間が長い。キーワードｗにより検索されるデータがない場合には、処理時間が長い処理を実行する必要がないため、処理時間を短くすることができる。
【００５８】
また、実施の形態１に係る秘匿検索システム１は、補助クエリＡＱに対応する補助タグＡＴの対応数ｍをカウントしておく。そして、秘匿検索システム１は、対応していると判定された暗号化タグＥＴの数が、対応数ｍになった場合には、検索クエリＳＱに対応する暗号化タグＥＴを特定する処理を終了する。これにより、処理時間が長い処理の実行数を減らすことができるため、処理時間を短くすることができる。
【００５９】
また、実施の形態１に係る秘匿検索システム１は、検索クエリＳＱに対応する暗号化タグＥＴを特定する処理を実行することにより、キーワードｗにより検索されるデータを特定する。そのため、暗号学的な柔軟なアクセス制御を行うことが可能である。
【００６０】
また、実施の形態１に係る秘匿検索システム１は、補助タグＡＴを生成する際、検索ワードの順序をランダムに入れ替える。そのため、検索装置６０は、補助タグＡＴと暗号化タグＥＴとの対応関係を特定することができない。これにより、検索ワードの情報が漏えいすることを防止できる。
【００６１】
＊＊＊他の構成＊＊＊
＜変形例１＞
実施の形態１では、アクセス制御可能な秘匿検索方式として、特許文献１に記載された方式を用いる例を説明した。しかし、アクセス制御可能な秘匿検索方式としては、特許文献１に記載された方式に限らず、他の方式が用いられてもよい。
他の方式が用いられる場合であっても、補助クエリＡＱに対応する補助タグＡＴがある場合に、検索クエリＳＱに対応する暗号化タグＥＴを特定するというキーテクニックを用いることができる。そして、このキーテクニックによる効果を得ることができる。
【００６２】
＜変形例２＞
実施の形態１では、共通パラメータ生成装置１０と補助鍵生成装置２０とユーザ鍵生成装置３０とタグ生成装置４０とクエリ生成装置５０と検索装置６０との機能構成要素がソフトウェアで実現された。しかし、変形例２として、機能構成要素はハードウェアで実現されてもよい。この変形例２について、実施の形態１と異なる点を説明する。
【００６３】
図１４を参照して、変形例２に係る共通パラメータ生成装置１０の構成を説明する。
機能がハードウェアで実現される場合、共通パラメータ生成装置１０は、プロセッサ１１とメモリ１２とストレージ１３とに代えて、処理回路１５を備える。処理回路１５は、共通パラメータ生成装置１０の機能構成要素と、メモリ１２とストレージ１３との機能とを実現する専用の電子回路である。
【００６４】
図１５を参照して、変形例２に係る補助鍵生成装置２０の構成を説明する。
機能がハードウェアで実現される場合、補助鍵生成装置２０は、プロセッサ２１とメモリ２２とストレージ２３とに代えて、処理回路２５を備える。処理回路２５は、補助鍵生成装置２０の機能構成要素と、メモリ２２とストレージ２３との機能とを実現する専用の電子回路である。
【００６５】
図１６を参照して、変形例２に係るユーザ鍵生成装置３０の構成を説明する。
機能がハードウェアで実現される場合、ユーザ鍵生成装置３０は、プロセッサ３１とメモリ３２とストレージ３３とに代えて、処理回路３５を備える。処理回路３５は、ユーザ鍵生成装置３０の機能構成要素と、メモリ３２とストレージ３３との機能とを実現する専用の電子回路である。
【００６６】
図１７を参照して、変形例２に係るタグ生成装置４０の構成を説明する。
機能がハードウェアで実現される場合、タグ生成装置４０は、プロセッサ４１とメモリ４２とストレージ４３とに代えて、処理回路４５を備える。処理回路４５は、タグ生成装置４０の機能構成要素と、メモリ４２とストレージ４３との機能とを実現する専用の電子回路である。
【００６７】
図１８を参照して、変形例２に係るクエリ生成装置５０の構成を説明する。
機能がハードウェアで実現される場合、クエリ生成装置５０は、プロセッサ５１とメモリ５２とストレージ５３とに代えて、処理回路５５を備える。処理回路５５は、クエリ生成装置５０の機能構成要素と、メモリ５２とストレージ５３との機能とを実現する専用の電子回路である。
【００６８】
図１９を参照して、変形例２に係る検索装置６０の構成を説明する。
機能がハードウェアで実現される場合、検索装置６０は、プロセッサ６１とメモリ６２とストレージ６３とに代えて、処理回路６５を備える。処理回路６５は、検索装置６０の機能構成要素と、メモリ６２とストレージ６３との機能とを実現する専用の電子回路である。
【００６９】
処理回路１５，２５，３５，４５，５５，６５は、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）が想定される。
共通パラメータ生成装置１０の各機能構成要素の機能を１つの処理回路１５で実現してもよいし、各機能構成要素の機能を複数の処理回路１５に分散させて実現してもよい。同様に、補助鍵生成装置２０とユーザ鍵生成装置３０とタグ生成装置４０とクエリ生成装置５０と検索装置６０とのそれぞれについて、各機能構成要素の機能を１つの処理回路２５，３５，４５，５５，６５で実現してもよいし、各機能構成要素の機能を複数の処理回路２５，３５，４５，５５，６５に分散させて実現してもよい。
【００７０】
＜変形例３＞
変形例３として、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。つまり、各機能構成要素のうち、一部の機能がハードウェアで実現され、他の機能がソフトウェアで実現されてもよい。
【００７１】
プロセッサ１１，２１，３１，４１，５１，６１とメモリ１２，２２，３２，４２，５２，６２とストレージ１３，２３，３３，４３，５３，６３と処理回路１５，２５，３５，４５，５５，６５とを、総称して「プロセッシングサーキットリー」という。つまり、各機能構成要素の機能は、プロセッシングサーキットリーにより実現される。
【符号の説明】
【００７２】
１  秘匿検索システム、１０  共通パラメータ生成装置、１１  プロセッサ、１２  メモリ、１３  ストレージ、１４  通信インタフェース、１５  処理回路、１１１  セキュリティパラメータ受付部、１１２  パラメータ生成部、１１３  パラメータ送信部、２０  補助鍵生成装置、２１  プロセッサ、２２  メモリ、２３  ストレージ、２４  通信インタフェース、２５  処理回路、２１１  セキュリティパラメータ受付部、２１２  補助鍵生成部、２１３  補助鍵送信部、３０  ユーザ鍵生成装置、３１  プロセッサ、３２  メモリ、３３  ストレージ、３４  通信インタフェース、３５  処理回路、３１１  パラメータ受付部、３１２  属性受付部、３１３  乱数生成部、３１４  ユーザ鍵生成部、３１５  ユーザ鍵送信部、３３１  パラメータ記憶部、４０  タグ生成装置、４１  プロセッサ、４２  メモリ、４３  ストレージ、４４  通信インタフェース、４５  処理回路、４１１  パラメータ受付部、４１２  アクセス条件受付部、４１３  検索ワード受付部、４１４  乱数生成部、４１５  補助タグ生成部、４１６  暗号化タグ生成部、４１７  タグ送信部、４３１  パラメータ記憶部、５０  クエリ生成装置、５１  プロセッサ、５２  メモリ、５３  ストレージ、５４  通信インタフェース、５５  処理回路、５１１  パラメータ受付部、５１２  キーワード受付部、５１３  乱数生成部、５１４  補助クエリ生成部、５１５  検索クエリ生成部、５１６  クエリ送信部、５３１  パラメータ記憶部、６０  検索装置、６１  プロセッサ、６２  メモリ、６３  ストレージ、６４  通信インタフェース、６５  処理回路、６１１  パラメータ受付部、６１２  タグ受付部、６１３  クエリ受付部、６１４  補助照合部、６１５  主照合部、６１６  結果出力部、６３１  パラメータ記憶部、６３２  補助タグ記憶部、６３３  暗号化タグ記憶部、７０  伝送路。
【要約】
検索装置（６０）は、補助タグ記憶部（６３２）に記憶された補助タグＡＴであって、検索ワードが変換されて得られた補助タグＡＴに、キーワードが変換されて得られた補助クエリＡＱに対応する補助タグＡＴがあるか否か判定する。検索装置（６０）は、補助クエリＡＱに対応する補助タグＡＴがあると判定された場合に、暗号化タグ記憶部（６３３）に記憶された暗号化タグＥＴであって、アクセス可能な属性を示すアクセス条件ｖと検索ワードとが設定された暗号化タグＥＴのうち、ユーザの属性を示す属性情報ｘとキーワードとが設定された検索クエリＳＱに対応する暗号化タグＥＴを特定する。【図１】
0006351890.tif 000002
【図２】
0006351890.tif 000003
【図３】
0006351890.tif 000004
【図４】
0006351890.tif 000005
【図５】
0006351890.tif 000006
【図６】
0006351890.tif 000007
【図７】
0006351890.tif 000008
【図８】
0006351890.tif 000009
【図９】
0006351890.tif 000010
【図１０】
0006351890.tif 000011
【図１１】
0006351890.tif 000012
【図１２】
0006351890.tif 000013
【図１３】
0006351890.tif 000014
【図１４】
0006351890.tif 000015
【図１５】
0006351890.tif 000016
【図１６】
0006351890.tif 000017
【図１７】
0006351890.tif 000018
【図１８】
0006351890.tif 000019
【図１９】
0006351890.tif 000020