(57)【要約】  アクセス端末装置３０１は、復号鍵であるグループ判定鍵を予めデータセンタ装置４０１に提供しておき、保管対象データのキーワードから生成した暗号化されているグループ化情報を、保管対象データの暗号化データと、保管対象データの暗号化データのタグデータとともにデータセンタ装置４０１に送信し、データセンタ装置４０１は、暗号化データをタグデータと対応付けて保管し、更に、グループ化情報の一部をグループ判定鍵で復号し、復号により得られたビット値からインデックス値を導出し、導出したインデックス値とタグデータを対応付けて保管する。
2012095973.tif 000002
【特許請求の範囲】
【請求項１】
複数の暗号化データと、各暗号化データに対応付けられている、暗号化データの検索の際に照合されるタグデータとを保管するデータ保管装置に接続され、
前記データ保管装置での保管の対象となる保管対象データのキーワードを保管キーワードとして指定するキーワード指定部と、
前記データ保管装置へのビット値の開示を許可するビット位置を許可ビット位置として指定する許可ビット位置指定部と、
所定の生成手順にて、前記保管キーワードから所定のビット列を保管インデックス導出ビット列として生成するインデックス導出ビット列生成部と、
前記保管インデックス導出ビット列内の前記許可ビット位置のビット値は前記データ保管装置に開示し前記保管インデックス導出ビット列内の前記許可ビット位置以外のビット値は前記データ保管装置に秘匿する秘匿化処理を行い、前記保管対象データの暗号化データに対応付けられるタグデータを保管する際に前記データ保管装置が前記タグデータに付す保管インデックス値を、前記データ保管装置に、前記保管インデックス導出ビット列内の前記許可ビット位置の開示されたビット値から導出させる秘匿化処理部とを有することを特徴とするデータ処理装置。
【請求項２】
前記データ処理装置は、
暗号化された検索キーワードと、開示が許可されているビット位置のビット値の開示により前記暗号化された検索キーワードとの照合の対象となるタグデータのインデックス値が導出される検索インデックス導出ビット列とが含まれる検索要求を受信した際に、前記検索インデックス導出ビット列内のビット値の開示により得られるインデックス値に基づき、前記暗号化された検索キーワードとの照合の対象となるタグデータを特定し、特定したタグデータと前記暗号化された検索キーワードとを照合して暗号化データを検索するデータ保管装置に接続され、
前記インデックス導出ビット列生成部は、
前記データ保管装置において前記検索インデックス導出ビット列から得られるインデックス値と比較される保管インデックス値が、前記秘匿処理部による前記データ保管装置への前記許可ビット位置のビット値の開示により導出される保管インデックス導出ビット列を生成することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記許可ビット位置指定部は、
順次新たな許可ビット位置を指定し、
前記秘匿化処理部は、
前記許可ビット位置指定部により新たな許可ビット位置が指定された場合に、前記保管インデックス導出ビット列内の既存の許可ビット位置のビット値に加えて新たに指定された許可ビット位置のビット値を前記データ保管装置に開示する秘匿化処理を行い、保管インデックス値のビット数を増加させることを特徴とする請求項１又は２に記載のデータ処理装置。
【請求項４】
前記秘匿化処理部は、
許可ビット位置ごとに、許可ビット位置の暗号化ビットの復号に用いられる復号鍵を許可ビット復号鍵として生成し、
前記データ処理装置は、更に、
前記許可ビット復号鍵を前記データ保管装置に対して送信する許可ビット復号鍵送信部を有し、
前記秘匿化処理部は、
前記許可ビット位置の暗号化ビットは前記許可ビット復号鍵により復号され、前記許可ビット位置以外の暗号化ビットは前記許可ビット復号鍵により復号されない暗号化方式にて前記保管インデックス導出ビット列を暗号化し、
前記データ処理装置は、更に、
前記保管対象データの暗号化データと、前記保管対象データの暗号化データに対応付けられるタグデータと、暗号化された前記保管インデックス導出ビット列とが含まれる保管要求を前記データ保管装置に対して送信する保管要求送信部を有することを特徴とする請求項１〜３のいずれかに記載のデータ処理装置。
【請求項５】
前記秘匿化処理部は、
前記保管対象データに対するアクセスが許可されるユーザのユーザ情報が反映されている復号鍵を、前記許可ビット復号鍵として生成し、
前記保管対象データに対するアクセスが許可されるユーザのユーザ情報が反映されている暗号鍵を用いて、前記保管インデックス導出ビット列を暗号化することを特徴とする請求項４に記載のデータ処理装置。
【請求項６】
前記許可ビット位置指定部は、
順次新たな許可ビット位置を指定し、
前記秘匿化処理部は、
前記許可ビット位置指定部により新たな許可ビット位置が指定された場合に、新たに指定された許可ビット位置の暗号化ビットの復号に用いられる許可ビット復号鍵を生成し、
前記許可ビット復号鍵送信部は、
前記秘匿化処理部により生成された新たな許可ビット復号鍵を前記データ保管装置に対して送信することを特徴とする請求項４又は５に記載のデータ処理装置。
【請求項７】
前記データ処理装置は、
暗号化された検索キーワードとの照合の対象となるタグデータを特定し、特定したタグデータと前記暗号化された検索キーワードとを照合して暗号化データを検索するデータ保管装置に接続され、
前記キーワード指定部は、
前記データ保管装置に暗号化データの検索を行わせる検索キーワードを指定し、
前記インデックス導出ビット列生成部は、
前記保管インデックス導出ビット列と同じ生成手順にて、前記キーワード指定部により指定された前記検索キーワードから所定のビット列を検索インデックス導出ビット列として生成し、
前記秘匿化処理部は、
前記データ保管装置へのビット値の開示が許可されているビット位置である許可ビット位置の暗号化ビットは、前記データ保管装置が保有する許可ビット復号鍵により復号され、前記許可ビット位置以外の暗号化ビットは前記許可ビット復号鍵により復号されない暗号化方式にて前記検索インデックス導出ビット列を暗号化し、
暗号化された検索キーワードとの照合の対象となるタグデータを抽出する際に前記データ保管装置が保管インデックス値と比較する検索インデックス値を、前記データ保管装置に、暗号化された前記検索インデックス導出ビット列内の前記許可ビット位置の暗号化ビットの復号により前記データ保管装置に開示される前記許可ビット位置のビット値から導出させ、
前記データ処理装置は、更に、
暗号化された前記検索キーワードと、暗号化された前記検索インデックス導出ビット列とが含まれる検索要求を前記データ保管装置に対して送信する検索要求送信部を有することを特徴とする請求項６に記載のデータ処理装置。
【請求項８】
前記秘匿化処理部は、
前記データ処理装置のユーザのユーザ情報が反映されている暗号鍵を用いて、前記検索インデックス導出ビット列を暗号化することを特徴とする請求項７に記載のデータ処理装置。
【請求項９】
データ処理装置に接続され、前記データ処理装置から送信された暗号化データを保管するデータ保管装置であって、
復号が許可されている許可ビット位置ごとに、許可ビット位置の暗号化ビットの復号に用いられる許可ビット復号鍵を保管する許可ビット復号鍵管理部と、
保管対象の暗号化データと、暗号化データの検索の際に照合されるタグデータと、前記保管対象の暗号化データに指定された保管キーワードを用いて生成された暗号化されたビット列とが含まれる保管要求を前記データ処理装置から受信する保管要求受信部と、
前記保管要求に含まれる前記保管対象の暗号化データを、前記タグデータと対応付けて保管する暗号化データ管理部と、
前記保管要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを前記許可ビット復号鍵を用いて復号し、復号により得られるビット値からインデックス値を導出し、導出したインデックス値と前記保管要求に含まれる前記タグデータとを対応付けて保管するインデックス管理部とを有することを特徴とするデータ保管装置。
【請求項１０】
前記許可ビット復号鍵管理部は、
ユーザ情報と対応付けて許可ビット復号鍵を保管し、
前記保管要求受信部は、
前記保管対象の暗号化データに対するアクセスが許可されるユーザのユーザ情報が含まれる保管要求を受信し、
前記インデックス管理部は、
前記保管要求に含まれるユーザ情報と合致するユーザ情報と対応付けられている許可ビット復号鍵を用いて、前記保管要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを復号し、インデックス値を導出することを特徴とする請求項９に記載のデータ保管装置。
【請求項１１】
前記許可ビット復号鍵管理部は、
ユーザ情報が反映されている許可ビット復号鍵を、前記ユーザ情報と対応付けて保管し、
前記保管要求受信部は、
前記保管対象の暗号化データに対するアクセスが許可されるユーザのユーザ情報が反映されている暗号鍵により暗号化されたビット列が含まれる保管要求を受信することを特徴とする請求項１０に記載のデータ保管装置。
【請求項１２】
前記インデックス管理部は、
前記保管要求に含まれる前記暗号化されたビット列に対する復号により得られるビット値を連結してインデックス値を導出し、
前記保管要求に含まれるユーザ情報に、導出したインデックス値と、前記保管要求に含まれる前記タグデータと、前記暗号化されたビット列内の復号されていない暗号化ビットとを対応付けて保管し、
前記許可ビット復号鍵管理部は、
新たな許可ビット位置が指定されると、新たな許可ビット位置の暗号化ビットの復号に用いられる新たな許可ビット復号鍵と、前記新たな許可ビット復号鍵と対応付けられるユーザ情報とを取得し、
前記インデックス管理部は、
前記許可ビット復号鍵管理部により取得された前記ユーザ情報と合致するユーザ情報に対応付けられている暗号化ビットを抽出し、抽出した暗号化ビットのうち前記新たな許可ビット位置に対応する暗号化ビットを前記新たな許可ビット復号鍵を用いて復号し、復号により得られたビット値を、共通のユーザ情報に対応付けられているインデックス値に追加して新たなインデックス値を導出することを特徴とする請求項１０又は１１に記載のデータ保管装置。
【請求項１３】
前記データ保管装置は、
複数のデータ処理装置に接続され、
前記データ保管装置は、更に、
前記複数のデータ処理装置のうち暗号化データの検索を要求する検索要求データ処理装置から、暗号化された検索キーワードと、暗号化前の検索キーワードを用いて生成された暗号化されたビット列と、前記検索要求データ処理装置のユーザのユーザ情報が含まれる検索要求を受信する検索要求受信部を有し、
前記インデックス管理部は、
前記検索要求に含まれるユーザ情報と合致するユーザ情報と対応付けられている許可ビット復号鍵を用いて、前記検索要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを復号し、復号により得られる前記許可ビット位置のビット値からインデックス値を導出し、導出したインデックス値と同じインデックス値と対応付けられているタグデータを抽出し、
前記データ保管装置は、更に、
前記インデックス管理部により抽出されたタグデータと前記検索要求に含まれる前記暗号化された検索キーワードとを照合し、前記インデックス管理部により抽出されたタグデータの中から、前記検索キーワードと同じキーワードから生成されているタグデータを特定し、特定したタグデータに対応付けられている暗号化データを前記暗号化データ管理部から取得する検索処理部を有することを特徴とする請求項１０〜１２のいずれかに記載のデータ保管装置。
【請求項１４】
前記許可ビット復号鍵管理部は、
ユーザ情報が反映されている許可ビット復号鍵を、前記ユーザ情報と対応付けて保管し、
前記検索要求受信部は、
前記検索要求データ処理装置のユーザのユーザ情報が反映されている暗号鍵により暗号化されたビット列が含まれる検索要求を受信することを特徴とする請求項１３に記載のデータ保管装置。
【請求項１５】
前記インデックス管理部は、
前記保管要求に含まれるユーザ情報に、導出したインデックス値と、前記保管要求に含まれる前記タグデータとを対応付けて保管し、
前記検索要求受信部により前記検索要求が受信された場合に、
前記検索要求に含まれるユーザ情報と合致するユーザ情報と対応付けられている許可ビット復号鍵を用いて、前記検索要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを復号し、復号により得られる前記許可ビット位置のビット値からインデックス値を導出し、前記検索要求に含まれるユーザ情報と合致するユーザ情報と対応付けられているタグデータの中から、導出したインデックス値と同じインデックス値と対応付けられているタグデータを抽出することを特徴とする請求項１３又は１４に記載のデータ保管装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿検索技術に関する。
【背景技術】
【０００２】
秘匿検索とは、暗号化データを暗号化したまま検索する技術である。
近年は、クラウドサービスなどのインターネット上でデータを管理する際に、サーバ管理者による盗聴からも機密情報を守るためのセキュリティ技術として注目されている。【０００３】
秘匿検索を実現する手法は、確定的暗号を利用する方法と、確率的暗号を利用する方法の２種類がある。
確定的暗号とは、同一のキーワードを暗号化した際に、何回繰り返して暗号化しても同一の暗号文が得られるという特徴を持つ暗号化方式である。
そのため、従来のデータベースで実現されている高速化手法を利用して、検索を高速に実施することができるという特徴がある。
その一方で、暗号化データの出現頻度をカウントする事ができるため、例えばキーワードが名字であった場合、一般的に知られている名字の人口比率の情報等を元にして、暗号化データの中身が推測できてしまうという欠点も持っている（例えば非特許文献２）。【０００４】
一方、確率的暗号とは、同一のキーワードを暗号化する場合でも、暗号化のたびに異なる暗号文となるという特徴を持つ暗号化方式である。
したがって、単純に暗号化データ同士を比較してもキーワードが同一かどうか分からないため、確定的暗号で問題となっていた出現頻度のカウントによるキーワードの推測ができない様になっており、その安全性が高い事が特徴である。
その一方で、キーワードの同一性すら分からないため、従来のデータベースで実現されていた高速化手法が使えず、検索が遅いという欠点がある（例えば非特許文献１、非特許文献３、非特許文献４、非特許文献５）。【０００５】
この確率的暗号を用いた秘匿検索を高速化する手法として、検索結果をキャッシュする事によって平均応答時間を短縮するアイデアが提案されている。
これは、一般的な検索では同じキーワードで２回以上検索される事があるという特徴に着目したもので、１回目の検索では時間がかかるものの、その結果をキャッシュして２回目以降はキャッシュした結果を返すだけにする事で、検索の高速化を図るものである（例えば特許文献１）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−１３４９９０号公報
【非特許文献】
【０００７】
【非特許文献１】Ｄ．Ｂｏｎｅｈ、Ｇ．Ｄ．Ｃｒｅｓｃｅｎｚｏ、Ｒ．Ｏｓｔｒｏｖｓｋｙ、Ｇ．ＰｅｒｓｉａｎｏＧ、“Ｐｕｂｌｉｃ  Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ”、ＥＵＲＯＣＲＹＰＴ’２００４、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｖｏｌ．３０２７、２００４．
【非特許文献２】Ｍ．Ｂｅｌｌａｒｅ、Ａ．Ｂｏｌｄｙｒｅｖａ、Ａ．Ｏ’Ｎｅｉｌｌ、“Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔｌｙ  Ｓｅａｒｃｈａｂｌｅ  Ｅｎｃｒｙｐｔｉｏｎ”、ＣＲＹＰＴＯ’２００７、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｖｏｌ．４６２２、２００７．
【非特許文献３】Ｊ．Ｋａｔｚ、Ａ．Ｓａｈａｉ、Ｂ．Ｗａｔｅｒｓ、“Ｐｒｅｄｉｃａｔｅ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｕｐｐｏｒｔｉｎｇ  Ｄｉｓｊｕｎｃｔｉｏｎｓ，Ｐｏｌｙｎｏｍｉａｌ  Ｅｑｕａｔｉｏｎｓ，ａｎｄ  Ｉｎｎｅｒ  Ｐｒｏｄｕｃｔｓ”、ＥＵＲＯＣＲＹＰＴ  ２００８、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｖｏｌ．４９６５、２００８．
【非特許文献４】服部  充洋、森  拓海、伊藤  隆、松田  規、米田  健、太田  和夫、“Ａｎｏｎｙｍｏｕｓ  ＨＩＢＥ  ｗｉｔｈ  Ｗｉｌｄｃａｒｄｓ  ａｎｄ  Ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  Ｓｅｃｕｒｅ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ  ｆｏｒ  Ｇｒｏｕｐ−Ｏｒｉｅｎｔｅｄ  Ｍｕｌｔｉ−Ｕｓｅｒ  Ｓｙｓｔｅｍ”、ＳＣＩＳ’２０１０、３Ａ４−２、電子情報通信学会、２０１０．
【非特許文献５】Ｔａｔｓｕａｋｉ  Ｏｋａｍｏｔｏ、Ｋａｔｓｕｙｕｋｉ  Ｔａｋａｓｈｉｍａ、“Ｈｉｅｒａｒｃｈｉｃａｌ  Ｐｒｅｄｉｃａｔｅ  Ｅｎｃｒｙｐｔｉｏｎ  ｆｏｒ  Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔｓ”、ＡＳＩＡＣＲＹＰＴ’２００９、Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｖｏｌ．５９１２、２００９．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
秘匿検索の基本的な流れは、下記の通りである。
まず、データを暗号化するユーザ（暗号化者）は、データを暗号化して暗号化データを作成するが、それと同時に暗号化データを検索するためのキーワードを暗号化データに関連付ける。
もちろん関連付けたキーワードもデータに関する情報であるため、これも暗号化して暗号化タグを生成し、暗号化データと暗号化タグをデータセンタ装置４０１に保管する。
暗号化タグは１個である必要はなく、複数関連付ける事ができる。
また、暗号化タグからキーワードが漏れる事はない。【０００９】
検索を行うユーザ（検索者）は、検索したいキーワードを選び、そのキーワードと自身の持つ秘密鍵を用いて検索クエリを作成する。
検索クエリは、秘密鍵を用いてキーワードをランダム化したものであるため、検索クエリ自身から秘密鍵を類推するのは難しい。
そして、この検索クエリをデータセンタ装置４０１に送付し、検索を要求する。【００１０】
データセンタ装置４０１は、ユーザから保管を依頼された暗号化データと暗号化タグを関連付けて保管している。
検索者から検索クエリを受け取ったら、自身が保管する暗号化タグの中から、検索クエリの生成に用いられたキーワードと同一のキーワードを含むものを検索する。
この時、データセンタ装置４０１は秘匿検索のための特殊な演算を行う事によって、暗号化タグを復号してキーワードを取り出すことなく、暗号化タグのキーワードと、検索クエリのキーワードが同一かどうかを判定できる。
そして、キーワードが検索クエリと同一と判定された暗号化タグと関連付けられた暗号化データを検索者に返却する。【００１１】
なお、秘匿検索には、暗号化者と検索者が同一でなければならない共通鍵方式と、暗号化者は誰でも良くて検索者のみが特定ユーザに限定された公開鍵方式の２種類がある。
上述の従来技術は、いずれも公開鍵方式の秘匿検索方式である。【００１２】
非特許文献２にて開示されているのは、確定的暗号を用いた秘匿検索方式である。
これは、前述の様に、同一のキーワードを暗号化した際に、何回繰り返して暗号化しても同一の暗号化タグが得られるという特徴を持つ。
そのため、暗号化タグのデータビットを比較する事でキーワードの同一性が判定でき、かつ暗号化タグ同士で大小比較を行う事ができるため、従来のデータベースで高速化のために実現されている２分木によるインデックス情報を作成する事ができる。
また、本方式では検索クエリも公開鍵を用いて生成し、暗号化タグと検索クエリの比較もバイナリデータとして完全に一致するかどうかで判断ができるため、検索処理を高速化できるという特徴がある。【００１３】
一方、データを保管しているデータセンタ装置４０１が、暗号化タグの出現頻度を計測する事で、平文を類推できてしまうというリスクがある。
例えば、コンピュータのログファイルで、メッセージ種別としてＩｎｆｏ／Ｅｒｒｏｒの２種類が保管されている事を考える。
ここで、暗号化タグの統計を取った結果、“ＡＡＡＡＡ”という暗号化タグが９９％の出現頻度、“ＢＢＢＢＢ”という暗号化タグが１％の出現頻度であったと仮定する。
一般的に、正しく運用されたコンピュータシステムでは、Ｅｒｒｏｒが発生する頻度は極めて低いと考えられる事から、“ＡＡＡＡＡ”はＩｎｆｏを意味しており、“ＢＢＢＢＢ”はＥｒｒｏｒを意味していると推測ができてしまう。【００１４】
この様に、確定的暗号は保管されるメッセージの出現頻度が知られている場合、たとえ暗号自身を破らなくても、元のデータが類推されるという危険性がある。
そのため、検索が高速に実施できるというメリットがあるものの、高い機密性が求められるシステムでは確率的暗号をベースにした秘匿検索の方が推奨される事が多い。【００１５】
非特許文献１に記載の方式は、確率的暗号の一つであるＩＤベース暗号（以下ＩＢＥ：Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ）を用いた秘匿検索方式である。
ＩＢＥは、メールアドレスや氏名などのＩＤを公開鍵としてデータの暗号化を行う事が可能な暗号化方式である。
暗号化データは、ＩＤに対応するユーザ秘密鍵を持つユーザだけが復号できる。
なお、ユーザ秘密鍵はマスター鍵を持つＰＫＧ（Ｐｒｉｖａｔｅ−Ｋｅｙ  Ｇｅｎｅｒａｔｏｒ）によって生成され、ＩＤと対応する正規のユーザに対してのみ発行する。
秘匿検索では、暗号化データから暗号化に用いたＩＤが分からないというＩＤ秘匿性を持ったＩＢＥが利用される。
また、確率的暗号であるため、同一のＩＤで同一のメッセージを暗号化しても、常に異なる暗号文となるため、複数の暗号文を並べてみても同一のメッセージを暗号化したものかどうかの区別がつかないという特徴も持っている。【００１６】
はじめに、暗号化者は、乱数を生成した後、キーワードをＩＤとしてＩＤベース暗号を用いて乱数を暗号化して暗号化乱数を得る。
この乱数と暗号化乱数の対を暗号化タグとして、暗号化データと共にデータセンタ装置に保管する。
次に検索者は、自身が持つマスター鍵を元に、検索キーワードをＩＤとしてユーザ秘密鍵を生成する。
このユーザ秘密鍵は、キーワードを用いて暗号化されたデータを復号できる秘密鍵であり、これを検索クエリとしてデータセンタに送付して、検索を要求する。【００１７】
データセンタは、保管されている暗号化タグから暗号化乱数を取り出し、取り出した暗号化乱数を検索クエリ（ユーザ秘密鍵）を用いて復号し、暗号化タグに含まれる乱数が正しく復号されるかどうかを確認する。
もし、暗号化乱数を生成する際に用いたキーワード（ＩＤ）と、検索クエリ（ユーザ秘密鍵）を生成する際に用いたキーワード（ＩＤ）が同一であれば、正しく暗号化乱数を復号可能である事から、暗号化タグと検索クエリが同一のキーワードから生成されていた事が分かる。【００１８】
この様に、確率的暗号に基づく秘匿検索方式は、１個の暗号化タグと１個の検索クエリを比較する事で、お互いに同一のキーワードを含む事が分かる。
しかし、確率的暗号である事から、暗号化タグ同士を比較しても、同一のキーワードから生成されたかの判断がつかない。
そのため、従来のデータベースで高速化のために実現されている２分木によるインデックス情報を作成する事ができず、結果として保管されている全ての暗号化タグを、それぞれ検索クエリと比較する必要が生じてしまい、検索の速度が非常に遅くなってしまうとい課題ある。【００１９】
非特許文献３や非特許文献５は、非特許文献１に記載の方式に対して、ＡＮＤやＯＲ等の条件を用いる事を可能にした方式であり、より柔軟な検索を可能にする。
しかし、非特許文献１と同様に、保管されている全ての暗号化タグを、それぞれ検索クエリと比較する必要が生ずる点は同一であり、検索の速度が非常に遅くなってしまうという課題がある。【００２０】
非特許文献４は、非特許文献１に記載の方式に対して、検索・復号が可能なユーザを複数人に拡張する事で、暗号化データのグループ共有を可能とした方式である。
しかし、非特許文献１と同様に、保管されている全ての暗号化タグを、それぞれ検索クエリと比較する必要が生ずる点は同一であり、検索の速度が非常に遅くなってしまうとい課題がある。【００２１】
特許文献１は、前記の課題を解決するために、ユーザが検索した結果をキャッシュとして保存しておき、次回以降に同一のキーワードが検索された場合に、高速に検索結果を返すための仕組みを提案している。
本方式は、繰り返し同一キーワードで検索される場合に有効である。【００２２】
しかし、特許文献１の方法は、一度検索したキーワードに対しては高速に検索結果を検索者に返却することが可能であるが、一度も検索したことのないキーワードに対しては、非特許文献１で問題であった様に、データセンタに保存された全てのタグを検索する必要がある。
そのため、膨大なタグを保存するデータベースで、検索キーワードが初めて指定されるキーワードであった場合に、検索結果を得るのに多大な時間を要するという課題がある。【００２３】
本発明は、上記のような課題を解決することを主な目的としており、確率的暗号を利用した秘匿検索において、一度も検索を行っていないキーワードであっても、暗号化データの検索処理を高速かつ安全に行える構成を実現することを目的とする。
【課題を解決するための手段】
【００２４】
本発明に係るデータ処理装置は、
複数の暗号化データと、各暗号化データに対応付けられている、暗号化データの検索の際に照合されるタグデータとを保管するデータ保管装置に接続され、
前記データ保管装置での保管の対象となる保管対象データのキーワードを保管キーワードとして指定するキーワード指定部と、
前記データ保管装置へのビット値の開示を許可するビット位置を許可ビット位置として指定する許可ビット位置指定部と、
所定の生成手順にて、前記保管キーワードから所定のビット列を保管インデックス導出ビット列として生成するインデックス導出ビット列生成部と、
前記保管インデックス導出ビット列内の前記許可ビット位置のビット値は前記データ保管装置に開示し前記保管インデックス導出ビット列内の前記許可ビット位置以外のビット値は前記データ保管装置に秘匿する秘匿化処理を行い、前記保管対象データの暗号化データに対応付けられるタグデータを保管する際に前記データ保管装置が前記タグデータに付す保管インデックス値を、前記データ保管装置に、前記保管インデックス導出ビット列内の前記許可ビット位置の開示されたビット値から導出させる秘匿化処理部とを有することを特徴とする。
【発明の効果】
【００２５】
本発明によれば、保管キーワードから生成した保管インデックス導出ビット列のうち許可ビット位置のビット値をデータ保管装置に開示し、データ保管装置に、タグデータを保管する際にタグデータに付与する保管インデックス値を、開示したビット値から導出させることができる。
このため、データ保管装置は、保管インデックス値を付してタグデータを保管することができ、一度も検索を行っていないキーワードであっても、保管インデックス値を用いて暗号化データを高速に検索することができる。
また、許可ビット位置以外のビット値は秘匿しているため、保管キーワードに関してデータ保管装置に漏洩する情報量を限定することができる。
【図面の簡単な説明】
【００２６】
【図１】実施の形態１に係る秘匿検索システムの構成例を示す図。
【図２】実施の形態１に係る鍵管理サーバ装置の構成例を示す図。
【図３】実施の形態１に係るアクセス端末装置の構成例を示す図。
【図４】実施の形態１に係るデータセンタ装置の構成例を示す図。
【図５】実施の形態１に係るシステム初期設定処理の例を示すフローチャート図。
【図６】実施の形態１に係るユーザ秘密鍵発行処理の例を示すフローチャート図。
【図７】実施の形態１に係るデータ暗号化処理の例を示すフローチャート図。
【図８】実施の形態１に係る暗号化タグの保管処理の例を示すフローチャート図。
【図９】実施の形態１に係る暗号化データの検索処理の例を示すフローチャート図。
【図１０】実施の形態１に係る暗号化タグの取得処理の例を示すフローチャート図。
【図１１】実施の形態１に係るインデックス再構成処理の例を示すフローチャート図。
【図１２】実施の形態１に係るタグＩＤ階層構造の例を示す図。
【図１３】実施の形態１に係るグループ化情報ＩＤ階層構造の例を示す図。
【図１４】実施の形態１に係る復号者ＩＤ階層構造の例を示す図。
【図１５】実施の形態１に係るユーザＩＤ情報データベースの例を示す図。
【図１６】実施の形態１に係るタグ付き暗号化データの例を示す図。
【図１７】実施の形態１に係るグループ化情報の例を示す図。
【図１８】実施の形態１に係る暗号化データ管理部の記憶内容の例を示す図。
【図１９】実施の形態１に係るインデックス管理部の記憶内容の例を示す図。
【図２０】実施の形態１に係る２分木のノード構成例を示す図。
【図２１】実施の形態１に係る検索クエリの例を示す図。
【図２２】実施の形態１に係るインデックス再構成処理の例を示す図。
【図２３】実施の形態２に係るアクセス端末装置の構成例を示す図。
【図２４】実施の形態２に係るデータ暗号化処理の例を示すフローチャート図。
【図２５】実施の形態２に係る暗号化タグの保管処理の例を示すフローチャート図。
【図２６】実施の形態２に係る暗号化データの検索処理の例を示すフローチャート図。
【図２７】実施の形態２に係る暗号化タグの取得処理の例を示すフローチャート図。
【図２８】実施の形態２に係るインデックス再構成処理の例を示すフローチャート図。
【図２９】実施の形態２に係るタグＩＤ階層構造の例を示す図。
【図３０】実施の形態２に係るタグＩＤ述語ベクトルの生成例を示す図。
【図３１】実施の形態２に係るタグＩＤ属性ベクトルの生成例を示す図。
【図３２】実施の形態２に係る復号者ＩＤ述語ベクトルの生成例を示す図。
【図３３】実施の形態２に係る復号者ＩＤ属性ベクトルの生成例を示す図。
【図３４】実施の形態２に係るタグ付き暗号化データの例を示す図。
【図３５】実施の形態１及び２に係る鍵管理サーバ装置２０１等のハードウェア構成例を示す図。
【発明を実施するための形態】
【００２７】
実施の形態１．
実施の形態１及び２では、確率的暗号を用いた秘匿検索方式において、暗号化タグに対してキーワードの部分情報も追加で添付する事で、データセンタ装置によるインデックス作成を可能とする仕組みを説明する。
更に、実施の形態１及び２では、登録された暗号化データ数が増加して検索処理が遅くなった際に、キーワードの部分情報を更に追加で開示する仕組みを提供する事で、確率的暗号を利用した秘匿検索を安全に高速化する仕組みを説明する。
【００２８】
図１は、秘匿検索システム１００の構成例を示す図である。
【００２９】
秘匿検索システム１００は、鍵管理サーバ装置２０１、アクセス端末装置３０１（３０１ａ〜３０１ｍ）、データセンタ装置４０１を備える。
鍵管理サーバ装置２０１とアクセス端末装置３０１とは、社内ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）１０２に接続されている。
社内ＬＡＮ１０２は、ネットワーク１０１を介してデータセンタ装置４０１と接続されている。
なお、アクセス端末装置３０１はデータ処理装置の例であり、データセンタ装置４０１はデータ保管装置の例である。
なお、アクセス端末装置３０１はアクセス端末と略記する場合があり、また、データセンタ装置４０１はデータセンタと略記する場合がある。
【００３０】
鍵管理サーバ装置２０１は、暗号化などの処理を行うためにユーザ（アクセス端末装置３０１の利用者）全員が共有する公開パラメータを生成するとともに、ユーザに対してユーザ秘密鍵を発行するために用いるマスター鍵を生成する。
また、各ユーザのＩＤ（Ｉｄｅｎｔｉｆｉｃａｉｔｏｎ）を管理するとともに、そのＩＤに基づいてユーザに対してユーザ秘密鍵を発行する。
【００３１】
アクセス端末装置３０１は、例えば、企業のユーザが利用するＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）である。
アクセス端末装置３０１は、データセンタ装置４０１での保管対象となる保管対象データを作成し、生成した保管対象データを暗号化し、暗号化データをデータセンタ装置４０１に保管するとともに、データセンタ装置４０１に蓄積した暗号化データを検索し、データセンタ装置４０１から取り出した暗号化データを復号して編集する。
【００３２】
データセンタ装置４０１は、企業内で作成された暗号化データを保管する大容量の記憶装置を持つサーバ装置である。
データは暗号化された状態で保管されるため、データセンタ装置４０１では中身を閲覧することができない。
【００３３】
ネットワーク１０１は、社内ＬＡＮ１０２とデータセンタ装置４０１を接続する通信路である。
例えば、インターネットなどが代表的なネットワーク１０１の例である。
【００３４】
社内ＬＡＮ１０２は、企業内に施設された通信路であり、企業内で利用される様々なサーバやパソコンが接続される。
なお、複数の建物にオフィスを持つ場合は、ルータや専用線などを介して複雑な通信路構成となる。
【００３５】
ここで、各装置の内部構成の詳細な説明を行う前に、本実施の形態における秘匿検索システム１００の概要を説明する。
【００３６】
アクセス端末装置３０１は、保管対象データのキーワード（保管キーワードの例）を暗号鍵にして乱数を暗号化してタグデータ（以下、単にタグともいう）を生成する。
タグデータは、暗号化データの検索の際に照合されるデータである。
また、アクセス端末装置３０１は、データセンタ装置４０１へのビット値の開示を許可するビット位置を許可ビット位置として指定する。
更に、アクセス端末装置３０１は、保管対象データのキーワードに対して所定の演算を行って所定のビット列（保管インデックス導出ビット列の例）を生成する。
そして、アクセス端末装置３０１は、ビット列内の許可ビット位置のビット値はデータセンタ装置４０１に開示しビット列内の許可ビット位置以外のビット値はデータセンタ装置４０１に秘匿する秘匿化処理を行う。
アクセス端末装置３０１は、保管対象データの暗号化データに対応付けられるタグデータを保管する際にデータセンタ装置４０１がタグデータに付すインデックス値（保管インデックス値の例）を、データセンタ装置４０１に、ビット列内の許可ビット位置の開示されたビット値から導出させる。
なお、このインデックス値は、いずれかのアクセス端末装置３０１から検索要求があった場合に、データセンタ装置４０１において、検索要求に含まれるトラップドア（暗号化された検索キーワード）と照合するタグデータを特定するために用いられる。
【００３７】
ビット列に対する秘匿処理は、具体的には、アクセス端末装置３０１からデータセンタ装置４０１への復号鍵の提供及びビット列の暗号化により行われる。
アクセス端末装置３０１は、許可ビット位置ごとに、許可ビット位置の暗号化ビットの復号に用いられる復号鍵であるグループ判定鍵（許可ビット復号鍵の例）を生成し、グループ判定鍵をデータセンタ装置４０１に送信する。
本実施の形態では、１ビット単位で許可ビット位置を指定するため、例えば、アクセス端末装置３０１が上位３ビットのビット値をデータセンタ装置４０１に開示する場合は、各ビットに対応させて３つのグループ判定鍵が順にデータセンタ装置４０１に送信される。
また、アクセス端末装置３０１は、保管対象データのキーワードから生成したビット列に対して暗号化を行う。
より具体的には、アクセス端末装置３０１は、許可ビット位置の暗号化ビットはグループ判定鍵により復号され、許可ビット位置以外の暗号化ビットはグループ判定鍵により復号されない暗号化方式にてビット列を暗号化する。
暗号化されたビット列は、グループ化情報という。
【００３８】
アクセス端末装置３０１は、保管対象データの暗号化データとタグデータとグループ化情報をデータセンタ装置４０１に送信する。
データセンタ装置４０１では、タグデータと対応付けて暗号化データを保管する。
また、データセンタ装置４０１では、グループ判定鍵を用いてグループ化情報の許可ビット位置の暗号化ビットを復号し、復号により得られたビット値からインデックス値を生成し、タグデータとインデックス値とを対応付けて保管する。
なお、グループ判定鍵及びグループ化情報における“グループ”とは、タグデータのグループを意味している。
例えば、許可ビット位置が上位３ビットであり、あるタグデータのグループ化情報の上位３ビットの復号から得られたインデックス値が“０１１”であれば、当該タグデータは、“０１１”のインデックス値が得られた他のタグデータと同じグループに分類されることになる。
【００３９】
そして、データセンタ装置４０１に保管されている暗号化データを検索する際には、アクセス端末装置３０１は、検索対象のキーワード（検索キーワードの例）を暗号化してトラップドアを生成し、また、暗号化データの保管時のビット列と同様の生成手順にて、検索キーワードから所定のビット列（検索インデックス導出ビット列の例）を生成する。
また、アクセス端末装置３０１は、許可ビット位置の暗号化ビットはグループ判定鍵により復号され、許可ビット位置以外の暗号化ビットはグループ判定鍵により復号されない暗号化方式にてビット列を暗号化して、グループ化情報を生成する。
そして、アクセス端末装置３０１は、トラップドアとグループ化情報が含まれる検索クエリ（検索要求の例）をデータセンタ装置４０１に送信する。
なお、データセンタ装置４０１に暗号化データを登録するアクセス端末装置３０１と、データセンタ装置４０１に暗号化データの検索を要求するアクセス端末装置３０１は一致していなくてもよい。
【００４０】
データセンタ装置４０１は、アクセス端末装置３０１から検索クエリを受信した場合に、検索クエリに含まれているグループ化情報の許可ビット位置の暗号化ビットをグループ判定鍵で復号して、インデックス値（検索インデックス値の例）を導出する。
次に、データセンタ装置４０１は、導出したインデックス値と同じインデックス値が付されているタグデータをトラップドアとの照合対象として選出する。
例えば、グループ化情報をグループ判定鍵で復号して“０１１”のインデックス値が得られた場合には、インデックス値“０１１”が付されて保管されているタグデータが選出される。
データセンタ装置４０１は、トラップドアとタグデータとの照合の結果、トラップドアの生成に用いられたキーワードと同じキーワードで生成されているタグデータを特定し、特定したタグデータと対応付けられている暗号化データを抽出し、抽出した暗号化データを検索要求の送信元のアクセス端末装置３０１に送信する。
【００４１】
以上が、本実施の形態に係る秘匿検索システム１００における動作の概要であり、以下では、鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１の内部構成を説明し、また、各装置の動作の詳細を説明する。
【００４２】
図２は、鍵管理サーバ装置２０１の構成を示す機能ブロック図である。
鍵管理サーバ装置２０１は、マスター鍵生成部２０２、鍵保管部２０３、ユーザ秘密鍵生成部２０４、ＰＫＧ側データ送受信部２０５、ユーザＩＤ情報管理部２０６を備える。
【００４３】
マスター鍵生成部２０２は、システムで利用する鍵長を元にして、秘匿検索を利用するユーザ全員が共通で利用する公開パラメータを生成するとともに、ユーザ秘密鍵を生成する元になるマスター鍵を生成する。
【００４４】
鍵保管部２０３は、マスター鍵生成部２０２で生成したマスター鍵や公開パラメータを記憶装置に記憶する。
【００４５】
ユーザ秘密鍵生成部２０４は、ユーザにユニークに割り当てられたＩＤを用いて、マスター鍵からユーザ秘密鍵を生成し、ユーザに送付する。
【００４６】
ＰＫＧ側データ送受信部２０５は、公開パラメータをユーザが使用するアクセス端末装置３０１やデータセンタ装置４０１に送付するための通信機能である。
また、ＰＫＧ側データ送受信部２０５は、ユーザ秘密鍵をアクセス端末装置３０１へ送信するためにも用いる。
また、ＰＫＧ側データ送受信部２０５は、ユーザＩＤ情報を企業内のユーザに対して開示するために、ユーザの要求によってユーザＩＤをアクセス端末装置３０１に送信する場合もある。
【００４７】
ユーザＩＤ情報管理部２０６は、ユーザＩＤとして氏名や所属やログインＩＤやメールアドレスなどの属性情報を記憶装置で管理する。
また、ユーザＩＤ情報管理部２０６は、現時点での属性情報だけでなく、過去の属性情報も履歴として管理する。
【００４８】
図３は、アクセス端末装置３０１の構成を示す機能ブロック図である。
アクセス端末装置３０１は、データ暗号化部３０２、暗号化タグ生成部３０３、タグ付き暗号化データ生成部３０４、ユーザ秘密鍵管理部３０５、検索クエリ生成部３０６、データ復号部３０７、グループ判定鍵生成部３０８、端末側データ送受信部３０９、グループ化情報生成部３１０を備える。
【００４９】
データ暗号化部３０２は、ユーザ又はアプリケーションからデータセンタ装置４０１で保管する保管対象データとユーザＩＤを受領し、ＩＤベース暗号を用いて保管対象データを暗号化し、保管対象データの暗号化データを得る。
また、データ暗号化部３０２は、保管対象データから後で検索に利用されるキーワード（保管キーワード）を複数抽出し、またユーザからデータに関連付けるキーワードを受領する。
このように、データ暗号化部３０２は、保管対象データからのキーワード抽出又はユーザからのキーワード受領により、保管対象データのキーワード（保管キーワード）を指定しており、キーワード指定部の例に相当する。
【００５０】
暗号化タグ生成部３０３は、データ暗号化部３０２で保管対象データに関連付けた複数のキーワードと、ユーザＩＤと、自身で生成した乱数から複数のタグ（タグデータ）を生成する。
また、後述のグループ化情報生成部３１０により生成されたグループ化情報とタグを結合して、複数の暗号化タグを生成する。
【００５１】
タグ付き暗号化データ生成部３０４は、データ暗号化部３０２で生成した暗号化データと、暗号化タグ生成部３０３で生成した複数の暗号化タグを結合してタグ付き暗号化データを生成し、データセンタ装置４０１に保管を依頼する。
【００５２】
ユーザ秘密鍵管理部３０５は、ユーザに個別に発行されたユーザ秘密鍵や、公開パラメータを記憶装置に記憶する。
【００５３】
検索クエリ生成部３０６は、ユーザ秘密鍵管理部３０５が記憶したユーザ秘密鍵と公開パラメータ、ユーザから指定された検索したいキーワードを暗号化してトラップドアを生成し、更に、グループ化情報生成部３１０により生成されたグループ化情報とトラップドアを結合して検索クエリを生成し、データセンタ装置４０１に送付する。
このように、検索クエリ生成部３０６は、ユーザの指示に従って、データセンタ装置４０１に暗号化データの検索を行わせるキーワード（検索キーワード）を指定しており、キーワード指定部の例に相当する。
【００５４】
データ復号部３０７は、データセンタ装置４０１から受け取った暗号化データを、ユーザ秘密鍵管理部３０５で保管しているユーザ秘密鍵と公開パラメータを用いて復号する。
【００５５】
グループ判定鍵生成部３０８は、ユーザ秘密鍵管理部３０５で保管しているユーザ秘密鍵と公開パラメータを用いて、検索を高速化するためのインデックス値を生成するために用いるグループ判定鍵（許可ビット復号鍵の例）を生成し、後述の端末側データ送受信部３０９を介してデータセンタ装置４０１に送付する。
より具体的には、グループ判定鍵生成部３０８は、グループ化情報のうちデータセンタ装置４０１にビット値の開示を許可する許可ビット位置を指定し、許可ビット位置の暗号化ビットを復号化するための復号鍵であるグループ判定鍵を生成する。
生成されたグループ判定鍵は、後述の端末側データ送受信部３０９によりデータセンタ装置４０１に送信され、データセンタ装置４０１ではグループ判定鍵を用いてグループ化情報の許可ビット位置の暗号化ビットを復号する。
このように、グループ判定鍵生成部３０８は、許可ビット位置を指定しており、許可ビット位置指定部の例に相当する。
また、グループ判定鍵生成部３０８は、グループ判定鍵のデータセンタ装置４０１への提供により、グループ化情報の許可ビット位置のビット値をデータセンタ装置４０１の開示し、保管対象データの暗号化データに対応付けられるタグデータを保管する際にデータセンタ装置４０１がタグデータに付すインデックス値（保管インデックス値の例）を、データセンタ装置４０１に、グループ化情報の許可ビット位置の開示されたビット値から導出させる。
このように、グループ判定鍵生成部３０８は、後述するグループ化情報生成部３１０とともに、秘匿化処理部の例に相当する。
なお、後述するように、データセンタ装置４０１では許可ビット位置をノードの階層構造に対応付けて管理するため、以下では、許可ビット位置を階層としても表す。
例えば、上位ｎ番目のビット位置を、第ｎ層と表記する。
【００５６】
端末側データ送受信部３０９は、鍵管理サーバ装置２０１から公開パラメータやユーザ秘密鍵を受信する。
端末側データ送受信部３０９は、グループ判定鍵を送信する。
また、端末側データ送受信部３０９は、作成したタグ付き暗号化データ（保管要求の例）をデータセンタ装置４０１に送信する。
また、端末側データ送受信部３０９は、データセンタ装置４０１へ検索クエリ（検索要求の例）を送付したり、検索結果である暗号化データをデータセンタ装置４０１から受領したりする。
端末側データ送受信部３０９は、許可ビット復号鍵送信部、保管要求送信部及び検索要求送信部の例である。
【００５７】
グループ化情報生成部３１０は、データセンタ装置４０１でインデックス値を生成するために用いるグループ化情報を生成する。
前述したように、このインデックス値は、いずれかのアクセス端末装置３０１から検索要求があった場合に、データセンタ装置４０１において、検索要求に含まれるトラップドアと照合するタグデータを特定するために用いられる。
グループ化情報生成部３１０は、保管対象データのキーワードに対して所定の演算を行って所定のビット列（保管インデックス導出ビット列の例）を生成する。
そして、グループ化情報生成部３１０は、許可ビット位置の暗号化ビットはグループ判定鍵により復号され、許可ビット位置以外の暗号化ビットはグループ判定鍵により復号されない暗号化方式にてビット列を暗号化する。
暗号化されたビット列が、グループ化情報となる。
このように、グループ化情報生成部３１０は、保管対象データのキーワードからビット列（保管インデックス導出ビット列の例）を生成するとともに、暗号化によりビット列を秘匿する処理を行っており、インデックス導出ビット列生成部の例に相当し、更に、前述のグループ判定鍵生成部３０８とともに秘匿化処理部の例に相当する。
グループ化情報生成部３１０は、保管対象データの保管時のみならず暗号化データの検索時においてもグループ化情報を生成する。
暗号化データの検索時のグループ化情報の生成手順自体は、保管対象データの保管時のグループ化情報と同じである。
保管対象データの保管時のグループ化情報は保管対象データのキーワード（保管キーワード）から生成しているのに対し、データ検索時のグループ化情報は、ユーザから指示された検索のためのキーワード（検索キーワード）から生成しているという点が異なるのみである。
【００５８】
図４は、データセンタ装置４０１の構成を示す機能ブロック図である。
データセンタ装置４０１は、センタ側データ送受信部４０２、保管要求処理部４０３、暗号化データ管理部４０４、インデックス管理部４０５、検索処理部４０６を備える。
【００５９】
センタ側データ送受信部４０２は、アクセス端末装置３０１からグループ判定鍵を受信する。
また、センタ側データ送受信部４０２は、アクセス端末装置３０１からタグ付き暗号化データを受信する。
また、センタ側データ送受信部４０２は、アクセス端末装置３０１から検索クエリを受信し、その応答として暗号化データを送信する。
また、センタ側データ送受信部４０２は、鍵管理サーバ装置２０１から公開パラメータを介して受信する。
センタ側データ送受信部４０２は、保管要求受信部及び検索要求受信部の例に相当する。
【００６０】
保管要求処理部４０３は、受信したタグ付き暗号化データを解析し、暗号化データと複数の暗号化タグに分解し、暗号化データを暗号化データ管理部４０４に渡し、暗号化タグを暗号化データと関連付ける形でインデックス管理部４０５に渡す事で、タグ付き暗号化データの保管処理を行う。
【００６１】
暗号化データ管理部４０４は、アクセス端末装置３０１から受信した暗号化データや、鍵管理サーバ装置２０１から受信した公開パラメータなどを記憶装置に記憶する。
暗号化データ管理部４０４は、アクセス端末装置３０１から受信した暗号化データをタグと対応付けて保管する。
【００６２】
インデックス管理部４０５は、アクセス端末装置３０１から受信したグループ判定鍵を保管する。
このため、インデックス管理部４０５は、許可ビット復号鍵管理部の例に相当する。
また、インデックス管理部４０５は、アクセス端末装置３０１から受信した暗号化タグの検索に適したデータ構造にてインデックス値を生成し、インデックス値に対応付けて暗号化タグを保管する。
より具体的には、インデックス管理部４０５は、グループ化情報内の許可ビット位置の暗号化ビットをグループ判定鍵を用いて復号し、復号により得られるビット値からインデックス値を導出し、導出したインデックス値と暗号化タグとを対応付けて保管する。
また、インデックス管理部４０５は、アクセス端末装置３０１からの検索クエリが受信された場合に、グループ判定鍵を用いて、検索クエリに含まれているグループ化情報内の許可ビット位置の暗号化ビットを復号し、復号により得られるビット値からインデックス値を導出し、導出したインデックス値と同じインデックス値と対応付けられている暗号化タグを抽出する。
また、インデックス管理部４０５は、新しくグループ判定鍵を受信した際、暗号化タグを保管しているインデックス情報の再構成を実施する。
【００６３】
検索処理部４０６は、アクセス端末装置３０１から受信した検索クエリと、インデックス管理部４０５から抽出された暗号化タグ内のタグとの照合処理を行う。
検索処理部４０６は、この照合処理によって、タグに含まれるキーワードと、検索クエリに含まれるキーワードが一致するかどうかを判定する。
その後、検索処理部４０６は、検索にヒットしたタグと関連付けられた暗号化データを暗号化データ管理部４０４から取得し、センタ側データ送受信部４０２を介してアクセス端末装置３０１に返送する。
【００６４】
次に、図５に基づき、システム初期設定の処理について説明する。
システム初期設定は、鍵管理サーバ装置２０１で実施される処理であり、秘匿検索システム１００を利用する前に１回実施される処理である。
【００６５】
最初に、ステップＳ５０１にて、マスター鍵生成部２０２は、グループ化情報を利用して生成するインデックス値の最大ツリー階層数Ｌ（Ｌは任意の整数）を決定する。
データＮ個に対して関連付けられたキーワードの合計がＭ個の場合、従来方式ではＭに比例した検索時間を要するが、インデックス値を使う事でＭ／２＾Ｌに比例した検索時間に削減する事ができる。
そこで、最大ツリー階層数Ｌは、格納するデータの最大個数、データに関連付けるキーワード数、既存秘匿検索方式と既存暗号化方式の処理時間、および検索時に求められるレスポンス時間を加味して決定する。
なお、最大ツリー階層数Ｌは、許可ビット位置の最大個数に相当する。
【００６６】
次に、ステップＳ５０２にて、マスター鍵生成部２０２は、本秘匿検索システム１００で利用する確率的暗号に基づく既存秘匿検索方式や、グループ化情報を作成するための既存暗号化方式Ａや、データ本体を暗号化する既存暗号化方式Ｂを決定する。
本実施の形態では、非特許文献４に記載のグループ共有型秘匿検索方式を既存秘匿検索方式として利用し、階層型ＩＤベース暗号をグループ化情報生成に用いる既存暗号化方式Ａとして利用し、データ本体の暗号化に利用する既存暗号化方式Ｂとして利用する。
そして、既存秘匿検索方式の利用方法を決定する。
本実施の形態で利用する既存秘匿検索方式では、マスター鍵生成部２０２は、タグＩＤ階層数とタグＩＤ階層構造を決定する。
例えば、図１２のタグＩＤ階層構造に示す様に、マスター鍵生成部２０２は、タグＩＤは３階層で構成され、検索可能なユーザが所属する部や課等のグループ名称を格納するグループ名欄、氏名などを保管するユーザ名欄、データに関連付けたキーワードを設定するキーワード欄で構成する、等を決定する。
そして、マスター鍵生成部２０２は、グループ化情報生成のための既存暗号化方式Ａの利用方法を決定する。
本実施の形態で利用する既存暗号化方式Ａでは、マスター鍵生成部２０２は、グループ化情報ＩＤ階層数とグループ化情報ＩＤ階層構造を決定する。
例えば、図１３の様なグループ化情報ＩＤ階層構造を利用する事を決定する。
図１３のグループ化情報ＩＤ階層構造において、グループ名欄とユーザ名欄は図１２のタグＩＤ階層構造のグループ名欄とユーザ名欄と同一で、キーワードの代わりに階層番号を格納する点が異なる。
階層番号に、インデックス値のツリー階層の番号（許可ビット位置の番号）を入れる事で、そのツリー階層の各層に対応したグループ化情報生成鍵が生成される。
後述するように、グループ化情報生成鍵は、アクセス端末装置３０１においてグループ化情報を生成する際に用いられる暗号鍵である。
同様に、マスター鍵生成部２０２は、データ本体を暗号化するための既存暗号化方式Ｂの利用方法を決定する。
本実施の形態では、復号者ＩＤ階層数と復号者ＩＤ階層構造を決定する。
例えば、図１４の様な復号者ＩＤ階層構造を決定する。
図１４の復号者ＩＤ階層構造において、グループ名欄とユーザ名欄は図１２のタグＩＤ階層構造のグループ名欄とユーザ名欄と同一である。
【００６７】
次に、ステップＳ５０３にて、ユーザＩＤ情報管理部２０６は、ユーザＩＤや属性情報を保管するユーザＩＤ情報データベースを構築する。
ユーザＩＤ情報データベースは、ユーザ秘密鍵を作成するために必要な情報、及びアクセス端末装置３０１がデータを暗号化する際に、相手のグループ名／ユーザ名を特定するために必要な情報が保管されているものである。
例えば、図１５に示すように、ユーザＩＤ情報データベースには、グループＩＤである部名、ユーザＩＤである氏名、所属情報、役職情報、その所属／役職等にいた期間、等が格納される。
また、ユーザＩＤ情報データベースには、最新の状況だけでなく、過去の履歴を全て格納するようにしてもよい。
【００６８】
次に、ステップＳ５０４にて、マスター鍵生成部２０２は、システムで利用する既存秘匿検索方式のマスター鍵生成アルゴリズムを実行して、秘匿検索用マスター鍵と秘匿検索用公開パラメータを生成する。
同様に、マスター鍵生成部２０２は、既存暗号化方式Ａのマスター鍵生成アルゴリズムを実行してグループ化情報用マスター鍵とグループ化情報用公開パラメータを生成し、既存暗号化方式Ｂのマスター鍵生成アルゴリズムを実行して暗号化用マスター鍵と暗号化用公開パラメータを生成する。
以降、秘匿検索用マスター鍵とグループ化情報用マスター鍵と暗号化用マスター鍵をまとめてマスター鍵、秘匿検索用公開パラメータとグループ化情報用公開パラメータと暗号化用公開パラメータをまとめて公開パラメータと呼ぶ事とする。
【００６９】
次に、ステップＳ５０５にて、鍵保管部２０３は、マスター鍵生成部２０２にて生成したマスター鍵と公開パラメータを記憶装置に保管する。
【００７０】
次に、ステップＳ５０６にて、ＰＫＧ側データ送受信部２０５は、鍵保管部２０３に保管された公開パラメータをアクセス端末装置３０１に対して公開する。
【００７１】
以上の手順によって、本秘匿検索システムのセットアップが完了する。
なお、Ｓ５０３で生成したユーザＩＤ情報データベースは、システムの運用において、ユーザの人事異動や入社や退社があるたびに内容がメンテナンスされる。
【００７２】
次に、図６に基づき、ユーザ秘密鍵発行の処理について説明する。
ユーザ秘密鍵発行処理は、主に鍵管理サーバ装置２０１とアクセス端末装置３０１で実施される処理であり、新規ユーザを追加した場合や、ユーザの所属するグループ名が変わった時などに実施される。
【００７３】
最初に、ステップＳ６０１にて、鍵管理サーバ装置２０１のユーザ秘密鍵生成部２０４は、ユーザＩＤ情報管理部２０６が保持しているユーザＩＤ情報データベースからグループ名とユーザ名を取得する。
【００７４】
次に、ステップＳ６０２にて、ユーザ秘密鍵生成部２０４は、検索クエリを生成するために用いる秘匿検索用ユーザ秘密鍵、グループ判定鍵を生成するために用いるグループ化情報用ユーザ秘密鍵、暗号化データを復号するために用いる暗号化用ユーザ秘密鍵を生成する。
既存秘匿検索方式では、秘匿検索用ユーザ秘密鍵を生成する際にタグＩＤ階層構造を指定する必要があるが、Ｓ６０１にて取得したグループ名をグループ名欄に、同じくユーザ名をユーザ名に設定し、キーワードは委譲可能な要素（アクセス端末装置３０１で指定可能な要素）として指定する事で、秘匿検索用ユーザ秘密鍵が生成できる。
既存暗号化方式Ａでは、グループ化情報用ユーザ秘密鍵を生成する際にグループ化情報階層構造を指定する必要があるが、Ｓ６０１にて取得したグループ名をグループ名欄に、同じくユーザ名をユーザ名に設定し、階層番号は委譲可能な要素（アクセス端末装置３０１で指定可能な要素）として指定する事で、グループ化情報用ユーザ秘密鍵が生成できる。
同様に、既存暗号化方式Ｂで暗号化用ユーザ秘密鍵を生成する際に復号者ＩＤ階層構造を指定する必要があるが、Ｓ６０１にて取得したグループ名をグループ名欄に、同じくユーザ名をユーザ名に指定する事で、暗号化用ユーザ秘密鍵が生成できる。
上記で生成した秘匿検索用ユーザ秘密鍵、グループ化情報用ユーザ秘密鍵、暗号化用ユーザ秘密鍵の３個をまとめてユーザ秘密鍵と呼ぶ事にする。
【００７５】
次に、ステップＳ６０３にて、ＰＫＧ側データ送受信部２０５は、Ｓ６０２にて生成したユーザ秘密鍵と、鍵保管部２０３に保管された公開パラメータを、アクセス端末装置３０１に対して送付する。
【００７６】
次に、ステップＳ６０４にて、アクセス端末装置３０１は、Ｓ６０３にて鍵管理サーバ装置２０１から受領したユーザ秘密鍵と公開パラメータを、ユーザ秘密鍵管理部３０５にて保管する。
【００７７】
以上の手順によって、鍵管理サーバ装置２０１はアクセス端末装置３０１を操作するユーザに対してユーザ秘密鍵を発行する事ができる。
【００７８】
次に、図７と図８に基づき、データの暗号化処理について説明する。
データ暗号化処理は、主にアクセス端末装置３０１とデータセンタ装置４０１で実施される処理であり、保管対象データを暗号化してデータセンタ装置４０１に保管する時に実施される。
【００７９】
最初に、ステップＳ７０１にて、アクセス端末装置３０１は、アクセス端末装置３０１を操作するユーザから、保管対象データの暗号化データを検索・復号可能なユーザのグループ名およびユーザ名（保管対象データにアクセス可能なユーザのユーザ情報の例）を受領し、データ暗号化部３０２と暗号化タグ生成部３０３とグループ化情報生成部３１０に入力する。
受け取るグループ名やユーザ名は一つである必要はなく、復号可能なユーザが複数名いる場合は複数受け取る事もできる。
なお、本実施の形態で利用する既存秘匿検索方式や既存暗号化方式Ａや既存暗号化方式Ｂは、グループ名やユーザ名として誰でも良い事を意味するワイルドカードを受け取る事も可能である。
【００８０】
次に、ステップＳ７０２にて、データ暗号化部３０２は、ユーザから保管対象データを受け取り、保管対象データと関連付けるキーワードを決定する。
キーワードは、保管対象データから自動的に抽出しても良いし、ユーザから受領する様にしても良い。
また、キーワードは１個である必要はなく、複数関連付けて良い。
【００８１】
次に、ステップＳ７０３にて、データ暗号化部３０２は、Ｓ７０１にて受け取ったグループ名とユーザ名を用いて、Ｓ７０２にて受け取った保管対象データを暗号化する。
具体的には、データ暗号化部３０２は、ランダムにセッション鍵を生成し、そのセッション鍵でＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）やＣａｍｅｌｌｉａ（登録商標）等の共通鍵暗号を用いて保管対象データを暗号化し、暗号化データ本体を生成する。
次に、データ暗号化部３０２は、復号者ＩＤ階層構造のグループ名とユーザ名に、Ｓ７０１で受け取ったグループ名とユーザ名をそれぞれ指定して、これを暗号化用公開鍵として既存暗号化方式Ｂを用いてセッション鍵を暗号化し、暗号化セッション鍵を生成する。
そして、データ暗号化部３０２は、前述の２個の暗号化結果を組み合わせる事で、暗号化データを生成する。
生成した暗号化データのデータ構造を図１６に示す。
なお、Ｓ７０１にて複数のグループ名とユーザ名を受領している場合、全てのグループ名とユーザ名の組に対して暗号化セッション鍵を生成する必要がある。
【００８２】
次に、ステップＳ７０４にて、グループ化情報生成部３１０は、暗号化タグを生成するためのキーワード（保管対象データのキーワード）を受け取り、各キーワードに対してグループ化情報を生成する。
具体的には、グループ化情報生成部３１０は、グループ化情報ＩＤ階層構造（図１３）のグループ名とユーザ名に、Ｓ７０１で受け取ったグループ名とユーザ名をそれぞれ指定して、階層番号に１からＬ（図５のＳ５０１で決定されたインデックス情報の最大ツリー階層数）までの数を文字列として設定する事で、Ｌ個のグループ化情報生成鍵を作成する。
なお、階層番号に１が設定されたグループ化情報ＩＤ階層構造が第１階層のグループ化情報生成鍵となり、階層番号にＬが設定されたグループ化情報ＩＤ階層構造が第Ｌ階層のグループ化情報生成鍵となる。
次に、グループ化情報生成部３１０は、キーワードを元にＬビットのビット列を生成する。
これは例えば、ＳＨＡ−２等のハッシュ関数を用いてキーワードのハッシュ値を生成し、その中から任意のＬビットを抽出する事で作成する事ができる。
このため、ハッシュ値においてＬビットを連続させて選択してもよいし、例えばハッシュ値の１ビット目と３ビット目と６ビット目と１１ビット目というように非連続にＬビットを選択してもよい。
但し、検索時に生成するグループ化情報においても、同じビット位置でＬビットを選択する必要がある。
また、グループ化情報生成部３１０は、抽出ビット列の１つ目を第１階層グループ化情報生成鍵を用いて既存暗号化方式Ａにて暗号化して暗号化第１情報を作成し、２つ目を第２階層グループ化情報生成鍵を用いて既存暗号化方式Ａにて暗号化して暗号化第２情報を作成し、順番にＬ個目まで全てを暗号化し、これらをまとめてグループ化情報とする。
このように、グループ化情報生成部３１０は、保管対象データに対するアクセスが許可されるユーザのユーザ情報が反映されているＬ個のグループ化情報生成鍵を用いて、キーワードのハッシュ値のＬビットを暗号化して、グループ化情報を生成する。
生成したグループ化情報の構成を図１７に示す。
なお、Ｓ７０１にて複数のグループ名とユーザ名を受領している場合、全てのグループ名とユーザ名の組に対してグループ化情報を生成する。
【００８３】
次に、ステップＳ７０５にて、暗号化タグ生成部３０３は、キーワードを暗号化して暗号化タグを生成する。
具体的には、暗号化タグ生成部３０３は、タグＩＤ階層構造のグループ名とユーザ名にＳ７０１で受け取ったグループ名とユーザ名を、キーワード欄にＳ７０２にて決定したキーワードをそれぞれ指定し、このタグＩＤ階層構造を暗号鍵にして乱数を暗号化し、既存秘匿検索方式でタグを作成する。
そして、暗号化タグ生成部３０３は、このタグと、Ｓ７０４にて同じキーワードから作られたグループ化情報を結合して暗号化タグとする。
生成した暗号化タグの構成を図１６に示す。
なお、上記はキーワード１個に対する処理であるため、これをデータに関連付けられた全てのキーワードに対して実施する。
また、Ｓ７０１にて複数のグループ名とユーザ名を受領している場合、全てのグループ名とユーザ名の組に対して暗号化タグを生成する。
【００８４】
次に、ステップＳ７０６にて、タグ付き暗号化データ生成部３０４は、Ｓ７０３で生成した暗号化データと、Ｓ７０５で生成した暗号化タグを結合してタグ付き暗号化データを生成し、端末側データ送受信部３０９を介してタグ付き暗号化データをデータセンタ装置４０１に保管依頼として送付する。
この時、データセンタ装置４０１でタグ付き暗号化データの保管を容易にするため、Ｓ７０１にて受領したグループ名とユーザ名を共に送付する。
図１６では、グループ名とユーザ名をタグ付き暗号化データに含めた構成のタグ付き暗号化データを示している。
【００８５】
次に、ステップＳ７０７にて、データセンタ装置４０１の保管要求処理部４０３は、アクセス端末装置３０１から受領したタグ付き暗号化データを分解し、暗号化データと複数の暗号化タグを取り出す。
そして、暗号化データ管理部４０４にて暗号化データを保管する。
なお、暗号化データ管理部４０４は、Ｓ７０６にてタグ付き暗号化データに含められたグループ名とユーザ名ごとに暗号化データを分けて保管し、さらに保管した暗号化データに管理番号を付与して、後で管理番号から暗号化データを一意に特定できる様にする。
なお、暗号化データが複数のグループ名やユーザ名と関連付けられている場合、ぞれぞれのグループ名とユーザ名に対して暗号化データを関連付けて保管する。
複数のグループ名とユーザ名に関連付けられている場合、暗号化データは１個だけ格納し、他は参照情報のみを保管する様にすることでディスク容量の節約が可能である。
図１８は、暗号化データの保管例を示している。
図１８の様に、グループ名が“総務部”でユーザ名が“＊”（ワイルドカード）である暗号化データと管理番号をまとめて管理し、さらにグループ名が“開発部”でユーザ名が“＊”である暗号化データと管理番号をまとめて管理する、という様に保管する。
また、総務部と開発部の両方に開示されるデータがあった場合、例えば管理番号０００００２に暗号化データ本体を関連付けて保管し、管理番号１００００２には暗号化データとして管理番号０００００２を参照する様なポインタを保管する。
【００８６】
次に、ステップＳ７０８にて、保管要求処理部４０３は、Ｓ７０６にて取得した複数の暗号化タグを、対応する暗号化データの管理番号と共にインデックス管理部４０５に送付する。
インデックス管理部４０５は、Ｓ７０６にてタグ付き暗号化データに含められたグループ名とユーザ名ごとに分けて、受け取った暗号化タグと管理番号を保管する。
【００８７】
なお、インデックス管理部４０５における暗号化タグの保管処理は複雑であるため、図８を用いて詳細を説明する。
なお、図１９の例に示す様に、インデックス情報もグループ名、ユーザ名ごとに管理しているものとする。
また、図１９のインデックス情報において、グループ判定鍵セットの第１層目用のグループ判定鍵は、グループ化情報内の暗号化第１情報（図１７）を復号するための復号鍵、つまり、許可ビット位置の１ビット目の暗号化ビットを復号するための復号鍵である。
同様に、グループ判定鍵セットの第２層目用のグループ判定鍵は、グループ化情報内の暗号化第２情報（図１７）を復号するための復号鍵、つまり、許可ビット位置の２ビット目の暗号化ビットを復号するための復号鍵である。
また、インデックス情報内のノードとは、暗号化タグ（タグ＋グループ化情報）に対応付けられるインデックス値である。
例えば、ノード“０１”は、グループ化情報の暗号化第１情報を復号して得られたビット値が“０”であり、暗号化第２情報を復号して得られたビット値が“１”であり、これらを連結して“０１”が得られたことを示している。
つまり、図１９の例では、アクセス端末装置３０１からは、上位２つのビット位置しかビット値の開示が許可されておらず、２つのグループ判定鍵のみがデータセンタ装置４０１に提供されており、このため、インデックス値は２ビットになる。
【００８８】
図８のフローにおいて、はじめに、ステップＳ８０１にて、インデックス管理部４０５は、グループ名とユーザ名ごとに管理された複数のインデックス情報を検索し、Ｓ７０６にて受け取ったグループ名とユーザ名でアクセスが可能な暗号化データに対応するインデックス情報（ワイルドカードが用いられているインデックス情報を含む）を特定し、今までにアクセス端末装置３０１から受領したグループ判定鍵を取り出す。
ここでグループ判定鍵は階層ごと（許可ビット位置ごと）に１個ずつ割り当てられており、後述する様に第１階層目から順番に１個ずつアクセス端末装置３０１から開示されるため、ここでは合計Ｌ’（Ｌ’≦Ｌ）個のグループ判定鍵が保管されていたと仮定する。
アクセス端末装置３０１によるグループ判定鍵の生成、アクセス端末装置３０１からデータセンタ装置４０１へのグループ判定鍵の送付、データセンタ装置４０１におけるグループ判定鍵の保管は、図７及び図８に示すフローとは非同期に行われ、ここでは、既に、Ｌ’個のグループ判定鍵がアクセス端末装置３０１により生成され、データセンタ装置４０１のインデックス管理部４０５に保管済みであると仮定する。
なお、アクセス端末装置３０１によるグループ判定鍵の生成、データセンタ装置４０１におけるグループ判定鍵の保管の詳細は図１１を参照して後述する。
【００８９】
次に、ステップＳ８０２にて、インデックス管理部４０５は、Ｓ７０７にて受領した複数の暗号化タグの中から、保管していない暗号化タグを１個取りだし、タグとグループ化情報に分解する。
【００９０】
次に、ステップＳ８０３にて、インデックス管理部４０５は、グループ化情報を分解して暗号化第１情報から暗号化第Ｌ情報（図１７）までを取り出す。
そして、暗号化第１情報から暗号化第Ｌ’情報までを、第１層目用のグループ判定鍵から第Ｌ’層目用のグループ判定鍵までを用いて復号し、第１情報から第Ｌ’情報を取得する。
【００９１】
次に、ステップＳ８０４にて、インデックス管理部４０５は、Ｓ８０３にて取り出した第１情報から第Ｌ’情報までを元にして、第１情報を第０層ノードから第１層ノードを決定するための情報として使い、第２情報を第１層ノードから第２層ノードを決定するための情報として使う。
そして、インデックス管理部４０５は、Ｓ７０５にて受領したグループ名とユーザ名に対応した２分木の中から該当するノードを特定し、そのノードに関連付けてＳ８０２で取り出した暗号化タグと、Ｓ７０７にて受領した管理番号を保管する。
例えば、図２０に示す様に、最初はルートノード（Ｎ（Ｒ））を起点として、第１情報が０か１かによって、左右のいずれかの子ノードを取り出す。
同様に第２情報が０か１かによって、左右のいずれかの子ノードを取り出す。
これを保有する全ての情報を用いて実施する。
なお、図２０の右側の矢印内の“１”は、第１情報によって第１層のノードが選択されることを示しており、また、矢印内の“２”は、第２情報によって第２層のノードが選択されることを示している。
例えば、第１情報が０、第２情報が１の場合、図２０に示すノード０１（Ｎ（０１））が該当ノードとして検出され、そのノード０１に暗号化タグと管理番号を関連付けて保管する。
前述の図１９では、第１情報から第Ｌ’情報（図１９では、Ｌ’＝２）までを並べて作成したノードを表す番号（インデックス値）と、暗号化タグと、対応する暗号化データの管理番号を、表形式にて保管しているインデックス情報の例を示している。
【００９２】
次に、ステップＳ８０５にて、インデックス管理部４０５は、Ｓ７０７にて受領した複数の暗号化タグの中から、Ｓ８０２からＳ８０４までの処理を実施していない暗号化タグが残っているかどうかを判定する。
もし残っていればＳ８０２の処理に戻り、残っていなければ終了する。
【００９３】
以上の手順により、アクセス端末装置３０１はデータを暗号化してデータセンタ装置４０１に保管を要求し、データセンタ装置４０１は受け取ったタグ付き暗号化データの保管を行う事ができる。
【００９４】
次に、図９に基づき、暗号化データの検索処理について説明する。
暗号化データ検索処理は、主にアクセス端末装置３０１とデータセンタ装置４０１で実施される処理であり、データセンタ装置４０１に保管された暗号化データを取得する時に実施される。
【００９５】
はじめにステップＳ９０１にて、アクセス端末装置３０１の検索クエリ生成部３０６は、アクセス端末装置３０１を操作するユーザから、検索したいキーワードを受け取る。
更に、検索クエリ生成部３０６は、受け取った検索キーワードをグループ化情報生成部３１０に通知する。
【００９６】
次に、ステップＳ９０２で、グループ化情報生成部３１０は、検索クエリ生成部３０６から通知された検索キーワードからグループ化情報を生成する。
本処理は、ステップＳ７０４の処理と同一である。
つまり、グループ化情報生成部３１０は、アクセス端末装置３０１のグループ名とユーザ名（暗号化データを検索しようとするユーザの所属グループのグループ名と当該ユーザのユーザ名）を入力し、入力したグループ名とユーザ名をグループ化情報ＩＤ階層構造（図１３）のグループ名とユーザ名に指定して、階層番号に１からＬまでの数を文字列として設定する事で、Ｌ個のグループ化情報生成鍵を作成する。
次に、グループ化情報生成部３１０は、例えば、ＳＨＡ−２等のハッシュ関数を用いて検索キーワードからＬビットのビット列を生成する。
なお、ハッシュ値からのＬビットの抽出は、暗号化データ保管時と同じビット位置のハッシュ値を抽出する。
また、グループ化情報生成部３１０は、抽出ビット列の１つ目を第１階層グループ化情報生成鍵を用いて既存暗号化方式Ａにて暗号化して暗号化第１情報を作成し、２つ目を第２階層グループ化情報生成鍵を用いて既存暗号化方式Ａにて暗号化して暗号化第２情報を作成し、順番にＬ個目まで全てを暗号化し、これらをまとめてグループ化情報とする。
【００９７】
次に、ステップＳ９０３にて、検索クエリ生成部３０６は、Ｓ９０１で受け取った検索キーワードと、ユーザ秘密鍵管理部３０５で保管されているユーザ秘密鍵を用いて、検索クエリを生成する。
具体的には、秘匿検索用ユーザ秘密鍵と検索キーワードを入力として、既存秘匿検索方式の検索クエリ生成関数を実行して、トラップドアを生成する。
次に、検索クエリ生成部３０６は、Ｓ９０２にて生成したグループ化情報とトラップドアを結合して検索クエリとする。
生成した検索クエリの構成を図２１に示す。
そして、検索クエリ生成部３０６は、端末側データ送受信部３０９を介して、生成した検索クエリをデータセンタ装置４０１に送付する。
この時、ユーザ自身のグループ名とユーザ名も送付する。
【００９８】
次に、ステップＳ９０４にて、データセンタ装置４０１の検索処理部４０６は、センタ側データ送受信部４０２を介してアクセス端末装置３０１から受信した検索クエリからトラップドアとグループ化情報を取り出し、インデックス情報（図１９）から検索候補となる暗号化タグを全て取得する。
なお、インデックス管理部４０５における暗号化タグの取得処理は複雑であるため、図１０を用いて詳細を説明する。
【００９９】
ステップＳ１００１にて、インデックス管理部４０５は、グループ名とユーザ名ごとに管理された複数のインデックス情報を検索し、Ｓ９０３において検索クエリとともに受け取ったグループ名とユーザ名でアクセスが可能な暗号化データに対応するインデックス情報を特定する。
そして、未処理のインデックス情報を、これから処理を行う対象のインデックス情報として特定する。
【０１００】
ステップＳ１００２とステップ１００３は、それぞれステップＳ８０１とステップＳ８０３と同一である。
つまり、インデックス管理部４０５は、グループ化情報を分解して暗号化第１情報から暗号化第Ｌ情報（図１７）までを取り出す。
そして、暗号化第１情報から暗号化第Ｌ’情報までを、第１層目用のグループ判定鍵から第Ｌ’層目用のグループ判定鍵までを用いて復号し、第１情報から第Ｌ’情報を取得する。
【０１０１】
次に、ステップＳ１００４にて、インデックス管理部４０５は、ステップＳ８０４にて示した手順を用いて、２分木の中からＳ９０３にて取り出したグループ化情報と対応するノードを特定し、そこに処理中である事を示すポインタを設定する。
そして、そのポインタが指すノードに関連付けられた暗号化タグと管理番号の組を全て取り出し、検索処理部４０６に送付する。
つまり、インデックス管理部４０５は、第１情報から第Ｌ’情報で示されているビット値から得られる値（インデックス値）と同じ値のノード番号をＳ１００１で特定したインデックス情報において特定し、特定したノード番号に対応付けられている暗号化タグと管理番号の組を全て取り出し、検索処理部４０６に送付する。
【０１０２】
例えば、図１９の例において、総務部に所属するユーザから検索クエリが送信された場合は、Ｓ１００１において、グループ名：総務部、ユーザ名：＊のインデックス情報が選択され、また、検索クエリ内のグループ化情報を復号して得られたインデックス値が“０１”であれば、暗号化タグ“２ｊ０”＃％Ｄｑ”と管理番号“０００００１”との組、暗号化タグ“３ｕｉ８＄ＳＥ＜”と管理番号“０００００２”との組が抽出される。
【０１０３】
次に、ステップＳ１００５にて、インデックス管理部４０５は、現在ポインタが指しているノードに対して、親ノードが存在するかどうかを確認する。
もし存在する様であればステップＳ１００６へ、存在しない様ならステップＳ１００７に処理を進める。
例えば、ポインタがルートノードを指している様であれば親ノードは存在しないため、ステップＳ１００７の処理に進む。
Ｓ１００５及びＳ１００６は、図１１を用いて後述するインデックス再構成処理の最中に検索クエリを受信した場合に対処するための処理である。
つまり、インデックス再構成処理において、全ての暗号化タグと管理番号の組が新たなノード番号（Ｌ’＋１階層のノード番号）へ振り分けられる前に、検索クエリを受信した場合には、Ｌ’＋１階層のノード番号についての検索のみならず、振り分けが完了していないＬ’階層のノード番号（親ノード）についての検索も必要になるため、Ｓ１００５及びＳ１００６の処理を行う。
【０１０４】
次に、ステップＳ１００６にて、インデックス管理部４０５は、現在ポインタが指すノードの親ノードにポインタを移動させ、そのポインタが指すノードに関連付けられた暗号化タグと管理番号の組を全て取り出し、検索処理部４０６に送付する。
例えば、ポインタが図２０のノード０１（Ｎ（０１））を指している場合は、親ノードであるノード０（Ｎ（０））の暗号化タグと管理番号の組を取り出す。
その後、Ｓ１００５の処理に進む。
【０１０５】
次に、ステップＳ１００７にて、インデックス管理部４０５は、Ｓ１００１にて特定したアクセスが可能な暗号化データに対応するインデックス情報の中で、まだステップＳ１００２からＳ１００６までの処理を行っていないインデックス情報があるかどうかを判定し、存在すればステップＳ１００１の処理へ進み、存在しなければ処理を終了する。
【０１０６】
以上により、ステップＳ９０４で実施する、インデックス情報から検索の候補となる暗号化タグを全て取得する処理が終了する。
【０１０７】
次に、ステップＳ９０５にて、検索処理部４０６は、Ｓ９０４にて取得した暗号化タグからタグを取り出し、既存秘匿検索技術の判定処理を用いて、タグに含まれるキーワードと、Ｓ９０４にて取り出したトラップドアに含まれるキーワードが同一であるかどうかを判定する。
既存秘匿検索技術の判定処理は、１個のタグと、１個のトラップドアの比較しか実施できないため、これをＳ９０４にて取得した全ての暗号化タグに対して実施する。
そして、検索処理部４０６は、判定処理の結果、一致と判定された暗号化タグに関連付けられた管理番号を特定する。
【０１０８】
次に、ステップＳ９０６で、検索処理部４０６は、Ｓ９０５にて特定した管理番号に対応する暗号化データを、暗号化データ管理部４０４から全て取得し、センタ側データ送受信部４０２を介してアクセス端末装置３０１に送付する。
【０１０９】
次に、ステップＳ９０７で、アクセス端末装置３０１のデータ復号部３０７は、Ｓ９０６にてデータセンタ装置４０１から受領した暗号化データを、ユーザ秘密鍵管理部３０５で保管している暗号化用ユーザ秘密鍵を用いて、既存暗号化方式の復号処理を用いて復号する。
これを全ての暗号化データに対して実施する。
【０１１０】
以上の手順により、アクセス端末装置３０１はユーザから検索キーワードを受け取り、そのキーワードを含む暗号化データをデータセンタ装置４０１から取得し、取得した暗号化データを復号してデータを閲覧する事ができる。
【０１１１】
次に、図１１に基づき、インデックスツリーの階層数を追加する時のインデックス再構成処理について説明する。
インデックス再構成処理は、主にアクセス端末装置３０１とデータセンタ装置４０１で実施される処理である。
【０１１２】
はじめにステップＳ１１０１にて、アクセス端末装置３０１のグループ判定鍵生成部３０８は、ユーザから再構成を行うインデックス情報を特定するための情報として、グループ名とユーザ名を受け取る。
データセンタ装置４０１では、暗号化データの開示先であるグループ名とユーザ名ごとにインデックス情報を管理しているため、ここで受け取ったグループ名とユーザ名を用いて、再構成するインデックス情報を一意に特定する事ができる。
【０１１３】
次に、ステップＳ１１０２にて、グループ判定鍵生成部３０８は、ユーザ秘密鍵管理部３０５からグループ化情報用ユーザ秘密鍵と、既に発行済みのグループ判定鍵の階層数を取り出す。
そして、グループ判定鍵生成部３０８は、新たに発行するグループ判定鍵の階層Ｌ’＋１を特定する。
つまり、グループ判定鍵生成部３０８は、新たな許可ビット位置であるＬ’＋１ビット目を指定する。
グループ化情報用ユーザ秘密鍵は、グループ化情報ＩＤ階層構造（図１３）のグループ名とユーザ名が指定された状態で発行されているため、グループ判定鍵生成部３０８は、新たに階層番号Ｌ’＋１を指定して、既存暗号化方式の鍵委譲機能を実行する事で、階層Ｌ’＋１に対応するグループ判定鍵を生成する。
そして、グループ判定鍵生成部３０８は、生成したグループ判定鍵を、Ｓ１１０１にて受け取った再構成したいインデックス情報に関連付けられたグループ名とユーザ名と共に、端末側データ送受信部３０９を介してデータセンタ装置４０１に送付する。
なお、グループ判定鍵生成部３０８による新たな階層Ｌ’＋１に対応するグループ判定鍵の生成及びデータセンタ装置４０１への送付は、新たな許可ビット位置を指定すること及び新たな許可ビット位置の暗号化ビットの復号を許可することに相当する。
【０１１４】
次に、ステップＳ１１０３にて、データセンタ装置４０１のインデックス管理部４０５は、Ｓ１１０２にて受け取ったグループ名とユーザ名から対応するインデックス情報とグループ判定鍵セットを特定し、受領した階層Ｌ’＋１用のグループ判定鍵を、対応する階層番号Ｌ’＋１と共にグループ判定鍵セット内に保管する。
【０１１５】
次に、ステップＳ１１０４にて、インデックス管理部４０５は、Ｓ１１０３にて特定したインデックス情報を取り出し、その最下層（階層番号Ｌ’）のノードの中から一つのノードを選択する。
【０１１６】
次に、ステップＳ１１０５にて、インデックス管理部４０５は、ステップＳ１１０４もしくはＳ１１０７で選択した第Ｌ’階層ノードに関連付けられた暗号化タグと管理番号を取り出し、さらに暗号化タグからグループ化情報を取り出す。
そして、グループ化情報の暗号化第Ｌ’＋１情報を、階層Ｌ’＋１用のグループ判定鍵を用いて、既存暗号化方式で復号する事で、暗号化タグを第Ｌ’＋１階層に振り分けるための第Ｌ’＋１情報を取得する。
そして、暗号化タグと管理番号を、選択した第Ｌ’階層ノードの子ノードのいずれに振り分けるかを第Ｌ’＋１情報を元に決定し、第Ｌ’階層ノードの関連付けを削除して、新たに第Ｌ’＋１階層ノードに関連付けて保存する。
これを選択した第Ｌ’階層に関連付けられた全ての暗号化タグに対して実施する。
本処理のイメージを図２２に示す。
【０１１７】
次に、ステップＳ１１０６にて、インデックス管理部４０５は、第Ｌ’階層のノードから、ステップＳ１１０５の処理を実施していないノードが存在するかどうかを確認する。
もし処理をしていないノードが存在する場合はステップＳ１１０７に進み、処理を行っていないノードが無い場合は終了する。
【０１１８】
次に、ステップＳ１１０７にて、インデックス管理部４０５は、第Ｌ’階層のノードから、ステップＳ１１０５の処理を実施していないノードを選択し、ステップＳ１１０５の処理に進む。
【０１１９】
図１９に示すように、インデックス管理部４０５は、ノード番号と対応付けて暗号化タグを記憶している。
暗号化タグには、グループ化情報が含まれている。
図１９の例では、グループ化情報の上位２ビットのみが復号され、３ビット目以降は秘匿されているままの状態である。
このとき、アクセス端末装置３０１が、グループ化情報の上位３ビット目までのビット値の開示を許可した場合には、３ビット目の復号のためのグループ判定鍵（第３層目用のグループ判定鍵）がアクセス端末装置３０１からデータセンタ装置４０１に送信される。
図１９のグループ名：総務部、ユーザ名：＊のインデックス情報を例にして説明すると、１行目のレコードの暗号化タグ（“２ｊ０”＃％Ｄｑ”）に含まれているグループ化情報の３ビット目の暗号化ビット（暗号化第３情報）を第３層目用のグループ判定鍵を用いて復号し、３ビット目の復号値（第３情報）を取得する。
この結果、３ビット目の復号値が、例えば、“０”であれば、新たなノード番号として、“０１０”が設定され、この新たなノード番号“０１０”に対して、暗号化タグ“２ｊ０”＃％Ｄｑ”と管理番号“０００００１”との組が対応付けられる。
他のレコードに対しても同様の処理が行われる。
例えば、グループ名：総務部、ユーザ名：＊のインデックス情報の２行目のレコードに対してグループ化情報の３ビット目の暗号化ビットを復号して、新たなノード番号“０１１”が得られた場合には、１行目のレコードのタグと２行目のレコードのタグは異なるグループに属することになる。
このように、ノード番号のビット数が増えると、各グループに含まれるタグの数が減り、検索クエリを受信した際のトラップドアとタグとの照合処理に要する時間を低減することができる。
【０１２０】
以上の手順により、アクセス端末装置３０１はデータセンタ装置４０１に対してグループ判定鍵を新たに生成してインデックス情報の再構成を要求し、データセンタ装置４０１は自身が管理するインデックス情報の再構成を行う事で、インデックス情報の階層数を１階層増やす事ができる。
【０１２１】
以上の様に、暗号化タグに対してキーワードから生成したグループ化情報を含めておき、必要に応じてデータセンタ装置４０１がユーザからグループ判定鍵を受け取る事で、グループ化情報を用いてキーワードに応じた暗号化タグのグループ化を行う事ができる。
検索の際にも、検索クエリに含まれるキーワードに応じてグループ化情報を作成しているため、必要に応じてデータセンタ装置４０１はこのグループ化情報とグループ判定鍵を使う事で、検索したいキーワードがどの暗号化タグのグループに対応しているかを一意に特定する事ができる。
そのため、全ての暗号化タグに対して既存秘匿検索技術の判定処理を行う必要が無くなり、特定のグループに属する暗号化タグに対してのみ既存秘匿検索技術の判定処理を行えばよく、秘匿検索の時間を大きく削減する事ができる。
例えば、Ｌ’個のグループ判定鍵がデータセンタ装置４０１に開示されている状況では、暗号化タグＭ個を２＾Ｌ’個のグループに分割する事ができるため、各グループには平均的にＭ／２＾Ｌ’個の暗号化タグが含まれる。
そのため、本実施の形態によって、検索処理は２＾Ｌ’倍に高速化される。
【０１２２】
また、グループ化を行うための情報を１ビット単位などで分割して暗号化しておき、ユーザがグループ判定鍵を開示する事で、データセンタ装置４０１がグループ化に用いるための情報を取得できる様にしている。
そのため、開示するグループ判定鍵の数によって、ユーザがグループ化のレベルを調整する事ができる。
例えば、Ｌ’個のグループ判定鍵を開示している状況で、暗号化データの保管数が増えるに従って検索時間がＴ時間になり、運用に支障が生じたとする。
この時、新しくＬ’＋１階層目に対応したグループ判定鍵を開示する事で、暗号化タグを２倍のグループに分割する事ができるため、検索時間をＴ／２に削減する事ができる様になる。
一方、暗号アルゴリズム開発の世界では、暗号化データ中に含まれるキーワードによって、暗号化データのグループ化ができない事が高い安全性を持つ暗号と評価される。
そのため、データの機密性を保護したいユーザは、不必要にデータセンタ装置４０１に暗号化データをグループ化されてしまう事は望まない。
本実施の形態によれば、ユーザが求める安全性のレベルと検索処理の応答時間に応じて、必要最小限のグループ判定鍵のみをデータセンタ装置４０１に与える様にユーザ自身が制御する事ができる。
そのため、グループ化情報としてＬビットの情報を付加していたとしても、開示するグループ判定鍵の数を調整する事で、ユーザ自身によって安全性と高速性のバランスを調整する事ができる。
【０１２３】
更に、開示するグループ判定鍵の数の調整は、正規のユーザ秘密鍵を持つユーザしか実施できないため、第三者によって不正にグループ判定鍵を作成・開示する様な、安全性を低下させる不正を防止する事ができる。
【０１２４】
また、本実施の形態に示した方式は、既存秘匿検索のタグに対してグループ化情報を付加する事で、その検索性能を向上させる拡張方式である。
そのため、本実施の形態で示した既存秘匿検索方式だけでなく、提案されている様々な既存秘匿検索方式に対して適用可能であり、その検索性能を向上させる事ができる。
本実施の形態では、非特許文献４の記載の方式に適用した例を示したが、非特許文献４が実現した暗号化データのグループ共有が可能という特徴を失うことなく、秘匿検索の検索速度を高速化できる。
同様に、例えば非特許文献１に記載の方式にも適用できるし、非特許文献３に記載の方式などでも適用可能であり、あらゆる既存秘匿検索方式に対して適用可能である。
【０１２５】
また、既存秘匿検索方式だけでなく、既存暗号化方式Ａや既存暗号化方式Ｂとして何を用いるかに依存しない高速化手法とした。
そのため、一般的によく利用されているＲＳＡ（登録商標）（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）暗号などを利用する事も可能である。
【０１２６】
また、本実施の形態では確率的暗号に基づく秘匿検索技術を高速化する手法について示した。
一般的に秘匿検索の検索時間だけを見れば確定的暗号に基づく方式が早いが、暗号化データの出現頻度を分析して平文を推定できるという課題がある。
一方、確率的暗号に基づく方式は、暗号化データの出現頻度がキーワードの出現頻度と無関係なため、出現頻度の分析による平文の推定に対して安全であるが、検索処理にとても時間がかかるという課題がある。
しかし、本実施の形態では、確率的暗号に基づいているため、検索が高速化されているにもかかわらず、出現頻度による分析に対しての安全性が残っているというメリットがある。
【０１２７】
また、暗号化データやインデックスは、グループ名とユーザ名の組ごとに作成・管理を行う仕組みとした。
そのため、ユーザが検索を行う場合、元々読む事ができない暗号化データが含まれるインデックス情報を検索する必要が無くなるため、検索処理を大きく向上させる事ができる。
【０１２８】
また、グループ名やユーザ名によって暗号化データの開示範囲が決められるが、一般的に開示範囲ごとに保管される暗号化データの数が異なる事が予想される。
本実施の形態では、グループ判定鍵の開示は、グループ名とユーザ名の組と関連付けられたインデックスに対して実施する様な仕組みとした。
そのため、開示範囲ごとに安全性と高速性のバランスを調整する事ができる。
【０１２９】
また、検索クエリに含まれるグループ化情報を用いて、インデックス情報から検索対象とすべき暗号化タグを取得する際、グループ化情報に対応したノードに関連付けられた暗号化タグだけではなく、その全ての上位ノードに関連付けられた暗号化タグも検索対象とする様にした。
そのため、追加でグループ判定鍵を受け取ってインデックス情報の再構成を行っている最中に検索クエリを受け取ったとしても、検索対象とすべき暗号化タグを漏らすことなくチェックする事ができる。
【０１３０】
また、グループ化情報を生成する時に階層型ＩＤベース暗号である非特許文献４を用いているため、ユーザに対してグループ情報生成鍵を送付する通信量を削減する事ができる。
具体的には、グループ名とユーザ名と最大階層数Ｌだけを送付すれば、アクセス端末装置３０１にてグループ化情報ＩＤ階層構造に受領した値を設定する事で、Ｌ個のグループ情報生成鍵を生成する事ができるため、通信コストを削減する事ができる。
【０１３１】
また、暗号化データを生成する際に複数のグループ名とユーザ名を受け取る様な仕組みとしているため、開示先のユーザやグループが複数あったとしても、本方式で複数の開示先に暗号化データを開示すると共に、開示先数に依存せずに検索速度を向上させる事ができる。
【０１３２】
また、暗号化データに関連付けるキーワードは、本文から自動抽出しても良いし、ユーザが指定する様にしても良いし、その両者を組み合わせる事もできる様にしたため、検索時に指定されるであろうキーワードをユーザの意図通りに付加する事ができる。
【０１３３】
また、データを暗号化する際に、ＡＥＳやＣａｍｅｌｌｉａ（登録商標）等の高速な共通鍵暗号を利用できる仕組みとしたため、動画や音楽データなどの大きなサイズのデータであっても、高速に暗号化する事が可能である。
【０１３４】
また、鍵管理サーバ装置２０１にユーザＩＤ情報データベースを持たせているので、ユーザが暗号化データを復号可能なユーザのグループ名やユーザ名が分からなかったとしても、ユーザが知っているメールアドレスなどの別の情報を元にして、正しいグループ名やユーザ名を取得する事ができるので、暗号化データの開示範囲を誤って設定する事を防止する事ができる。
同様に、グループ化情報を生成したり、暗号化タグを生成したりするための補助にもなる。
【０１３５】
（２分木以外も適用可能）
なお、本実施の形態では、２分木を用いたインデックス情報を構成する例を示した。
しかし、生成するインデックスは２分木に限る必要はなく、グループ化情報から生成する事ができるものであれば、より一般的な木構造であっても良く、ハッシュテーブルであっても良い。
また、インデックス情報として作成した２分木は、その構造を保ったままディスクに保管する必要はなく、例として示した様にノード番号を割り当てて表形式で保管しても良いし、その他のデータ形式で保管しても良い。
【０１３６】
（グループ化情報は１ビットに制約する必要はない）
また、本実施の形態では、キーワードから生成したビット列の第ｉビットを暗号化する事で、グループ化情報の暗号化第ｉ情報を生成する様にした。
しかし、１ビットずつ暗号化する必要はなく、２ビット以上の情報を用いて暗号化第ｉ情報を生成する様にしても良い。
例えば、キーワードから２Ｌビットのビット列を生成し、その第２ｉ−１ビット目と第２ｉビット目を暗号化して、暗号化第ｉ情報を生成するようにすることも可能である。
【０１３７】
（グループ化情報に使う情報）
また、本実施の形態では、グループ化情報の暗号化第ｉ情報には、０や１といった１ビットの情報を含める例を示した。
しかし、グループ化情報の暗号化第ｉ情報を用いて２分木の子ノード（左）か子ノード（右）かを判断できればいいので、必ずしも０や１の１ビットの情報である必要はない。
例えば、第ｉ情報に任意の数値を指定して暗号化第ｉ情報を作成しておき、偶数の場合は子ノード（左）、奇数の場合は子ノード（右）と割り振っても良い。
他にも、第ｉ情報に０から１００までの数値を指定して暗号化第ｉ情報を作成しておき、５０未満の場合は子ノード（左）、５０以上の場合は子ノード（右）と割り振っても良い。
この様に、第ｉ情報として指定する値は、子ノードの判定方法と関連付いていれば、どの様な情報を設定しても良い。
【０１３８】
（グループ判定鍵を実施の形態２の様にしても良い）
また、本実施の形態では、グループ化情報の暗号化第ｉ情報をグループ判定鍵を用いて復号する事で、２分木の子ノード（左）か子ノード（右）かを判定する０／１の情報を得ていた。
しかし、かならずしもこの様にする必要はなく、例えば実施の形態２で示す様に、グループ判定鍵（暗号化タグ用）とグループ判定鍵（検索クエリ用）を用いて、データセンタ装置４０１側で第ｉ情報を生成する様な仕組みとしても良い。
この場合、グループ化情報に設定した値自身もデータセンタ装置４０１には分からないため、それがキーワードのハッシュ値であったとしてもキーワードの推測が困難であり、安全性を向上させる事ができる。
【０１３９】
（グループ化情報は全て暗号化する必要はない）
また、本実施の形態では、グループ化情報を作成する際に全てのビットを暗号化する様にしたが、一部もしくは全てを暗号化せずに平文のまま送っても良い。
例えば、データセンタ装置４０１側で保持するグループ判定鍵の数が分かっている場合、その対応するビットは暗号化してもデータセンタ装置４０１側で復号される事が分かるので、そこは平文のまま送る様にしても良い。
【０１４０】
（ハッシュ値以外も利用可能）
また、本実施の形態では、キーワードからＬビットのビット列を作成する際に、例えばＳＨＡ−２等のハッシュ関数を利用する事を例示したが、Ｌビットのビット列が作れるものであればアルゴリズムは何でも良い。
例えば、ＳＨＡ−２以外のハッシュ関数を用いても良いし、ＨＭＡＣ等の鍵付きハッシュや、ＡＥＳ等の共通鍵暗号や、ＲＳＡ（登録商標）暗号等の公開鍵暗号を用いても良い。
なお、鍵付きハッシュや共通鍵暗号や公開鍵暗号を用いる場合は、グループ情報生成鍵に加えてハッシュ鍵や共通鍵や秘密鍵も配布する必要がある。
また、キーワードを乱数のシードとして、疑似乱数生成アルゴリズムでＬビットの乱数を生成する様にしても良い。
他にも、キーワードとＬビット列の対応表を使う様にしても良い。
特に、Ｌビット列の対応表を用いる場合、キーワードの出現頻度を考慮してＬビット列の発生頻度を平準化できるため、安全性が更に向上する事が期待できる。
【０１４１】
（グループ判定鍵の公開数）
また、本実施の形態では、ユーザがグループ判定鍵を１個ずつ開示する事を想定した例を記載したが、１回に１個ずつと制限する必要はなく、同時に２個や３個のグループ判定鍵を公開する様にしても良い。
【０１４２】
（グループ判定鍵生成のタイミング）
また、本実施の形態では、システム利用前にグループ化情報ＩＤ階層構造を定めておき、ユーザがグループ化情報を生成するタイミングでグループ名・ユーザ名・階層番号を指定してグループ化情報生成鍵を生成していた。
しかし、グループ化情報生成鍵はシステム利用前やユーザ秘密鍵発行時などのタイミングで一括して発行しても良い。
特に、既存暗号化方式としてＡＥＳやＲＳＡ（登録商標）暗号などを使う場合は、暗号化より前のタイミングで生成する事が必要となる。
【０１４３】
（ＩＤ階層数の制約はない）
また、本実施の形態では、タグＩＤ階層構造やグループ化情報ＩＤ階層構造や復号者ＩＤ階層構造にて、グループ名とユーザ名の２種類の情報を用いて復号・検索が可能なユーザやグループを指定する例を示した。
しかし、この２種類の情報に制限する必要はなく、例えば部名・課名・氏名の３種を用いても良いし、氏名だけを用いても良い。
また、もっと多くの情報を用いて受信者を指定しても良い。
【０１４４】
（ＩＤ共通化は不要）
また、本実施の形態では、タグ付き暗号化データを生成する際、タグＩＤ階層構造やグループ化情報ＩＤ階層構造や復号者ＩＤ階層構造に、グループ名とユーザ名として同じ値を設定する例を示した。
しかし、これらは同じ値にせず、異なる値を設定しても良い。
例えば、グループ判定鍵の生成をユーザ自身に実施させずに管理者が実施する場合は、タグＩＤ階層構造と復号者ＩＤ階層構造には開示先ユーザのグループ名とユーザ名を設定しておき、グループ化情報ＩＤ階層構造にはグループ判定鍵の生成が可能な管理者のグループ名とユーザ名を指定する様にすればよい。
また、ユーザには検索だけ許可し、暗号化データ自身の復号は許可したくない場合は、タグＩＤ階層構造にはユーザのグループ名とユーザ名を設定し、復号者ＩＤ階層構造には別の復号可能なユーザのグループ名とユーザ名を設定すればよい。
【０１４５】
（鍵管理サーバ装置２０１の階層化）
また、本実施の形態では、鍵管理サーバ装置２０１が１台の例を示したが、１台に制限する必要はない。
例えば、非特許文献４の方式や、その他の秘匿検索方式では、鍵管理サーバ装置にも階層構造を持たせ、複数台に役割を分散して運用する形態も記載されている。
本実施の形態でも同様にして、鍵管理サーバ装置に階層構造を持たせた形で利用する事も可能である。
【０１４６】
（ＩＤベース暗号以外も適用可能）
また、本実施の形態では、ＩＤベース暗号に基づく既存秘匿検索方式や既存暗号化方式Ａや既存暗号化方式Ｂを用いた例を示した。
しかし、ＩＤベース暗号に基づく方式に制約するものではなく、ＡＥＳやＣａｍｅｌｌｉａ（登録商標）やＨＭＡＣなどの共通鍵暗号や、ＲＳＡ（登録商標）暗号などの公開鍵暗号を用いる事も可能である。
【０１４７】
（公開パラメータの共通化も可能）
また、本実施の形態では、ＩＤベース暗号に基づく既存秘匿検索方式や既存暗号化方式Ａや既存暗号化方式Ｂを用いた例を示したが、それぞれ異なる公開パラメータを利用する様にした。
しかし、例えば利用する楕円曲線など、公開パラメータの一部の情報を共通化して利用する事も可能である。そのため、共通化できるものは共通化して利用しても構わない。
【０１４８】
（キーワード数）
また、本実施の形態では、検索キーワードが１個の場合を示したが、必ずしも検索キーワードを１個に制限する必要はない。
例えば、複数の検索キーワードがある場合、それぞれのキーワードに対して検索クエリを生成して、全ての検索クエリをデータセンタ装置４０１に送付しても良い。
またその時、例えば１個の検索クエリでヒットと判定された暗号化データを取得するとか、検索クエリＡと検索クエリＢの両方がヒットした暗号化データを取得する等、任意の条件も送付して良い。
【０１４９】
（タグのチェック不要化）
また、本実施の形態では、インデックス管理部４０５から取得した暗号化タグの全てを検索クエリと判定する様にした。
しかし、検索にヒットしたと判定された暗号化データに関しては、それ以降、その暗号化データに関連付けられた暗号化タグのチェックをしなくても構わない。また、検索結果として例えば１０件の結果を返せばいい場合においても、規定個数以上の検索結果が見つかったら、それ以降の暗号化タグのチェックを行わなくても良い。
【０１５０】
（ユーザＩＤ情報データベースの必要有無）
また、本実施の形態では、鍵管理サーバ装置２０１にユーザＩＤ情報データベースを設け、その情報を元にユーザ秘密鍵の生成を行っていた。
しかし、ユーザＩＤ情報データベースは必ずしも必須なものではなく、ユーザ秘密鍵を発行する際に鍵管理サーバ装置２０１の管理者によって指定する様にしても良いし、アクセス端末装置３０１から受領する様にしても良い。
【０１５１】
（アクセス端末装置３０１＝ユーザとの仮定、ＩＣカードの利用）
また、本実施の形態では、アクセス端末装置３０１は一人のユーザが操作するものと仮定した記載とした。
しかし、アクセス端末装置３０１自身は一人のユーザが占有するものではなく、複数名で共有する様な仕組みでも良い。
この場合、ユーザ秘密鍵管理部３０５ではユーザごとに１個のユーザ秘密鍵が割り当てられるため、複数のユーザ秘密鍵を保管する様にして、アクセス端末装置３０１で操作者の認証をする事で、どのユーザ秘密鍵を利用すべきかを判断する事が好ましい。
また、ユーザ秘密鍵を社員証などに保管して管理する事も可能である。
この場合、ユーザ秘密鍵管理部３０５がＩＣカードに相当する機能だが、ユーザ秘密鍵を用いた処理をＩＣカードにて全て行わせる場合、必要に応じて検索クエリ生成部３０６やデータ復号部３０７やグループ判定鍵生成部３０８の一部の処理をＩＣカードに実施させても良い。
【０１５２】
（データ本体の暗号化方式）
また、本実施の形態では、データを暗号化する際にＡＥＳやＣａｍｅｌｌｉａ（登録商標）を自動的に用いる事を例示したが、これはシステム内で事前に利用する方式を決定しておいても良いし、ユーザによって設定できる様にしておいても良い。
【０１５３】
（検索結果の返却方法）
また、本実施の形態では、検索の結果、ヒットした暗号化データを全て返却する様な例を示したが、必ずしも検索時に同時に全ての暗号化データ自身を返却する必要はない。
例えば、ヒットした暗号化データのうち数個を返すだけにするとか、個数だけを返す様にするとか、暗号化データのリストだけを返却する様にしても良い。
【０１５４】
（システム構成のバリエーション）
また、本実施の形態では、鍵管理サーバ装置２０１とアクセス端末装置３０１が企業内にあり、データセンタ装置４０１がインターネットなどに接続された外部サービスとして存在した例を示した。
しかし、本発明はこの様なシステム構成に限定されるものではない。
例えば、データセンタ装置４０１が企業内にあっても良いし、鍵管理サーバ装置２０１やアクセス端末装置３０１が企業外のネットワークに接続されていても良い。
【０１５５】
なお、本実施の形態では、
アクセス端末装置３０１のグループ化情報生成部３１０は、
保管キーワードのハッシュ値から、インデックス情報のノードの最大階層数と同数であるＬビットのビット列を抽出し、抽出したＬビットのビット列をＩＤベース暗号化方式で暗号化してグループ化情報を生成していることを説明した。
換言すると、グループ化情報生成部３１０（インデックス導出ビット列生成部、秘匿化処理部）は、
保管キーワードから一意に得られる乱数値のビット列から、許可ビット位置として指定できる最大数と同数のビット数のビット列を抽出して、保管インデックス導出ビット列を生成し、生成した保管インデックス導出ビット列をＩＤベース暗号化方式で暗号化している。
【０１５６】
また、本実施の形態では、
グループ化情報生成部３１０が、
保管キーワードのハッシュ値から連続するＬビットを抽出してもよく、また、１ビット目と３ビット目と６ビット目と１１ビット目というように非連続にＬビットを抽出するようにしてもことを説明した。
換言すると、グループ化情報生成部３１０は、
保管インデックス導出ビット列の生成の際に、保管キーワードから一意に得られる乱数値のビット列から、許可ビット位置として指定できる最大数と同数の連続ビットを抽出してもよく、また、許可ビット位置として指定できる最大数と同数の非連続ビットを抽出してもよい。
【０１５７】
また、本実施の形態では、
グループ化情報生成部３１０は、
Ｌビットのビット列の各ビットで異なるグループ化情報生成鍵を用いて暗号化を行って、グループ化情報を生成していることを説明した。
換言すると、グループ化情報生成部３１０は、
保管インデックス導出ビット列の暗号化の単位ビットごとに異なる暗号鍵を用いている。
【０１５８】
また、本実施の形態では、
グループ化情報生成部３１０は、
グループ化情報ＩＤ階層構造（図１３）のグループ名及びユーザ名の少なくともいずれかにワイルドカード指定して、Ｌ個のグループ化情報生成鍵を生成できることを説明した。
換言すると、グループ化情報生成部３１０は、
保管対象データに対するアクセスが許可されるユーザのユーザ情報をワイルドカードを用いて定義し、ワイルドカードを用いて定義されたユーザ情報が反映されている暗号鍵を用いて、保管インデックス導出ビット列を暗号化することができる。
【０１５９】
また、本実施の形態では、
データセンタ装置４０１のインデックス管理部４０５は、
暗号化データ管理部４０４が保管対象の暗号化データを暗号化タグと対応付けて保管する際に、グループ化情報をグループ判定鍵を用いて復号し、復号により得られるノード番号と暗号化タグを対応付けて保管することを説明した。
換言すると、インデックス管理部４０５は、
暗号化データ管理部４０４が保管対象の暗号化データをタグデータと対応付けて保管する際に、暗号化されたビット列内の許可ビット位置の暗号化ビットを許可ビット復号鍵を用いて復号し、復号により得られるビット値からインデックス値を導出し、導出したインデックス値とタグデータとを対応付けて保管している。
【０１６０】
また、本実施の形態では、
インデックス管理部４０５は、
検索クエリを受信した際に、グループ化情報の復号により得られたノードに対応付けられている暗号化タグと管理番号の組を取り出すとともに、当該ノードの親ノードに関連付けられた暗号化タグと管理番号の組を全て取り出し、検索処理部４０６に送付することを説明した。
換言すると、インデックス管理部４０５は、
検索要求に含まれる暗号化されたビット列内の許可ビット位置の暗号化ビットを復号し、復号により得られる許可ビット位置のビット値からインデックス値を導出し、導出したインデックス値と同じインデックス値と対応付けられているタグデータを抽出し、
更に、許可ビット位置のうち最下位の許可ビット位置を除く許可ビット位置の暗号化ビットの復号により得られるビット値からインデックス値を導出し、導出したインデックス値と同じインデックス値と対応付けられているタグデータを抽出する。
【０１６１】
実施の形態２．
以上の実施の形態１では、グループ化情報生成のための既存暗号化方式Ａとして階層型ＩＤベース暗号を用いたものであるが、次に非特許文献５に記載の内積述語暗号を用いて、タグ自身にグループ化情報も含める事が可能な実施の形態を示す。
【０１６２】
はじめに、非特許文献５に記載の内積述語暗号の概要を説明する。
内積述語暗号では、属性ベクトルというベクトルを公開鍵として用いて、任意のメッセージを暗号化する事ができる。
ユーザ秘密鍵には、述語ベクトルというベクトルが埋め込まれており、この述語ベクトルはユーザごとに異なるベクトルを用いる事が多い。
そして、暗号化データに埋め込まれた属性ベクトルと、ユーザ秘密鍵に埋め込まれた述語ベクトルの内積が０となる場合にのみ、そのユーザ秘密鍵を用いて、その暗号化データを復号できる。
もし内積が０にならない場合は、正しく復号できないという方式である。
【０１６３】
従来のＩＤベース暗号では、ＩＤを公開鍵として用いており、ユーザ秘密鍵にもＩＤが埋め込まれていた。
そして、そのＩＤが一致する時にのみ、そのユーザ秘密鍵を用いて、その暗号化データが復号できた。
そのため、内積述語暗号はＩＤベース暗号を一般化したものと考える事ができる。
さらに、ＡＮＤやＯＲ等の論理式をベクトルの内積を用いて評価できるという特徴があるため、ＩＤベース暗号よりも復号条件を柔軟に指定可能であるという特徴もある。
【０１６４】
本実施の形態における秘匿検索システム１００の構成例は、実施の形態１で示した図１と同一であるため、説明は省略する。
【０１６５】
鍵管理サーバ装置２０１とデータセンタ装置４０１の機能ブロックに関しても、実施の形態１で示した図２と図３と同一であるため、説明は省略する。
【０１６６】
図２３は、アクセス端末装置３０１の構成を示す機能ブロック図である。
データ暗号化部３０２、暗号化タグ生成部３０３、タグ付き暗号化データ生成部３０４、ユーザ秘密鍵管理部３０５、検索クエリ生成部３０６、データ復号部３０７、端末側データ送受信部３０９に関しては、実施の形態１の図３で示したものと同一である。
【０１６７】
グループ化ビット列生成部２３０１は、キーワードから、暗号化タグや検索クエリに含めるキーワードのグループ化ビット列を生成する。
グループ化ビット列生成部２３０１は、実施の形態１におけるグループ化情報生成部３１０に対応する要素であり、インデックス導出ビット列生成部の例及び秘匿化処理部の例に相当する。
【０１６８】
グループ判定鍵生成部３０８は、ユーザ秘密鍵管理部３０５で管理しているユーザ秘密鍵と公開パラメータを用いて、インデックス値を生成するためにデータセンタ装置４０１に送付するグループ判定鍵を生成する。
なお、グループ判定鍵は、暗号化タグのグループ化に用いるグループ判定鍵（暗号化タグ用）と、検索クエリがどのグループの暗号化タグを参照しているかを判定するために用いるグループ判定鍵（検索クエリ用）の２種から構成される。
なお、本実施の形態においても、グループ判定鍵生成部３０８は、許可ビット位置指定部の例及び秘匿化処理部の例に相当する。
【０１６９】
次に、システム初期設定の処理の流れについて説明する。
なお、処理の流れ自体は実施の形態１で示した方式と類似しているが、既存秘匿検索方式や既存暗号化方式のアルゴリズムの相違から処理内容が若干異なっている。
そのため、実施の形態１で示した図５の処理の流れを用いて、その差異を中心に説明する。
【０１７０】
最初にステップＳ５０１の処理は、実施の形態１と同一であるため説明は省略する。
【０１７１】
次に、ステップＳ５０２にて、マスター鍵生成部２０２は、秘匿検索システム１００で利用する既存秘匿検索方式や既存暗号化方式として、非特許文献５に記載の内積述語暗号を用いる事を決定する。
なお、既存秘匿検索方式がグループ化情報を含む暗号化タグの生成に用いるもので、既存暗号化方式がデータ本体を暗号化するために用いる方式である。
【０１７２】
そして、既存秘匿検索方式の利用方法として、タグＩＤ階層数とタグＩＤ階層構造と、内積述語暗号に与えるベクトルの構成を決定する。
例えば、図２９のタグＩＤ階層構造に示す様に、タグＩＤは３階層で構成され、検索可能なユーザが所属する部や課等のグループ名称を格納するグループ名欄、氏名などを保管するユーザ名欄、データに関連付けたキーワードを設定するキーワード欄で構成する、等を決定する。
また、キーワード欄はグループ化情報とキーワード情報の２要素で構成され、グループ化情報は第１情報から第Ｌ情報までの要素で構成する、等を決定する。
【０１７３】
また、タグＩＤ階層構造の全ての要素が一致した場合に検索にヒットする事とし、それに対応したタグＩＤ述語ベクトルとタグＩＤ属性ベクトルの生成方法を決定する。
このタグＩＤ述語ベクトルｖＴの生成例を図３０に、タグＩＤ属性ベクトルｘＴの生成例を図３１に示す。
例えばタグＩＤ階層構造のグループ名からベクトルの要素を導出する場合、タグＩＤ述語ベクトルの場合は（ｖ１，ｖ２）＝（１，−“グループ名”）とし、タグＩＤ属性ベクトルの場合は（ｘ１，ｘ２）＝（“グループ名”，１）とする。両者のベクトルの内積を取ると、グループ名が同一であった場合のみ内積値が０となり、異なる場合は０以外の値となる。
同様に、ユーザ名や第ｉ情報や残ビット情報もベクトルの値に対応づける。
なお例外として、要素がワイルドカードであった場合、そのベクトルは（０，０）とする。
例えば、ユーザ名にワイルドカードが指定されている場合、タグＩＤ述語ベクトルなら（ｖ３，ｖ４）＝（０，０）とし、タグＩＤ属性ベクトルなら（ｘ３，ｘ４）＝（０，０）とする。
他の要素にワイルドカードが指定されている場合にも、同様にベクトルに対応づける事ができる。
また、図の様に対応づけた場合、非特許文献５のマスター鍵生成アルゴリズム（Ｓｅｔｕｐ）に記載の各パラメータは、ｎ＝６＋２Ｌ、ｄ＝３＋Ｌ、μ１＝２、μ２＝４、・・・、μ（３＋Ｌ）＝６＋２Ｌとなる。
【０１７４】
同様に、マスター鍵生成部２０２は、保管対象データを暗号化するための既存暗号化方式の利用方法として、復号者ＩＤ階層数と復号者ＩＤ階層構造を決定する。
本実施の形態では、復号者ＩＤ階層数が２とし、復号者ＩＤ階層構造として、実施の形態１と同様にグループ名とユーザ名からなる復号者ＩＤ階層構造を持つものと仮定する。
なお、復号者ＩＤ階層構造の全ての要素が一致した場合に検索にヒットする事とし、それに対応した復号者ＩＤ述語ベクトルと復号者ＩＤ属性ベクトルの生成方法を導出する。
この復号者ＩＤ述語ベクトルｖＤの生成例を図３２に、復号者ＩＤ属性ベクトルｘＤの生成例を図３３に示す。
ベクトルの各要素の導出方法は、タグＩＤの場合と同様である。
また、この場合、非特許文献５のマスター鍵生成アルゴリズムに記載の各パラメータは、ｎ＝４、ｄ＝２、μ１＝２、μ２＝４となる。
【０１７５】
次に、ステップＳ５０３は、実施の形態１と同様であるため説明を省略する。
【０１７６】
次に、ステップＳ５０４にて、マスター鍵生成部２０２は、システムで利用する既存秘匿検索方式のマスター鍵生成アルゴリズムを実行して、秘匿検索用マスター鍵と秘匿検索用公開パラメータを生成する。
同様に、既存暗号化方式のマスター鍵生成アルゴリズムを実行して暗号化用マスター鍵と暗号化用公開パラメータを生成する。
以降、秘匿検索用マスター鍵と暗号化用マスター鍵をまとめてマスター鍵、秘匿検索用公開パラメータと暗号化用公開パラメータをまとめて公開パラメータと呼ぶ事とする。
【０１７７】
次に、ステップＳ５０５とＳ５０６は、実施の形態１と同様であるため説明を省略する。
以上の手順によって、本秘匿検索システムのセットアップが完了する。
【０１７８】
次に、ユーザ秘密鍵発行の処理の流れについて説明する。
なお、処理の流れ自体は実施の形態１で示した方式と類似しているが、既存秘匿検索方式や既存暗号化方式のアルゴリズムの相違から処理内容が若干異なっている。
そのため、実施の形態１で示した図６の処理の流れを用いて、その差異を中心に説明する。
【０１７９】
最初に、ステップＳ６０１は、実施の形態１と同様であるため説明を省略する。
【０１８０】
次に、ステップＳ６０２にて、ユーザ秘密鍵生成部２０４は、検索クエリを生成するために用いる秘匿検索用ユーザ秘密鍵、暗号化データを復号するために用いる暗号化用ユーザ秘密鍵を生成する。
既存秘匿検索方式では、秘匿検索用ユーザ秘密鍵を生成する際にタグＩＤ階層構造を指定する必要があるが、ユーザ秘密鍵生成部２０４は、Ｓ６０１にて取得したグループ名をグループ名欄に、同じくユーザ名をユーザ名に設定し、キーワード欄内の全ての要素は委譲可能な要素として指定する。
この値を設定したタグＩＤ階層構造をステップＳ５０２で決定したベクトル生成ルールに基づいてベクトル化を行ってタグＩＤ述語ベクトルを生成し、既存秘匿検索方式のユーザ秘密鍵生成アルゴリズム（ＧｅｎＫｅｙ）を実行する事で、秘匿検索用ユーザ秘密鍵が生成できる。
同様に、既存暗号化方式で暗号化用ユーザ秘密鍵を生成する際に復号者ＩＤ階層構造を指定する必要があるが、Ｓ６０１にて取得したグループ名をグループ名欄に、同じくユーザ名をユーザ名に指定し、ユーザ秘密鍵生成部２０４は、この値を設定した復号者ＩＤ階層構造をステップＳ５０２で決定したベクトル生成ルールに基づいてベクトル化を行う事で復号者ＩＤ述語ベクトルを生成し、既存暗号化方式のユーザ秘密鍵生成アルゴリズムを実行する事で、暗号化用ユーザ秘密鍵が生成できる。
上記で生成した秘匿検索用ユーザ秘密鍵、暗号化用ユーザ秘密鍵をまとめてユーザ秘密鍵と呼ぶ事にする。
【０１８１】
次に、ステップＳ６０３とステップＳ６０４は、実施の形態１と同様であるため説明を省略する。
以上の手順によって、鍵管理サーバ装置２０１はアクセス端末装置３０１を操作するユーザに対してユーザ秘密鍵を発行する事ができる。
【０１８２】
次に、図２４と図２５を用いて、データの暗号化処理の流れについて説明する。
なお、処理の流れ自体は実施の形態１で示した方式と類似しているが、既存秘匿検索方式や既存暗号化方式のアルゴリズムの相違から処理内容が若干異なっている。
そのため、実施の形態１で示した処理の流れとの差異を中心に説明する。
【０１８３】
最初にステップＳ７０１とＳ７０２とＳ７０３は、実施の形態１と同様であるため説明を省略する。
【０１８４】
次に、ステップＳ２４０４にて、グループ化ビット列生成部２３０１は、データに関連付けるキーワードを受け取り、各キーワードに対してグループ化ビット列を生成する。
具体的には、グループ化ビット列生成部２３０１は、キーワードを元にＬビットのビット列と、任意のキーワード情報を生成する。
これは例えば、ＳＨＡ−２等のハッシュ関数を用いてキーワードのハッシュ値を生成し、その中から任意のＬビットを抽出してＬビットのビット列とし、残りのビット列を並べたもの、もしくはハッシュ値全体をキーワード情報とする事などで生成できる。
【０１８５】
次に、ステップＳ２４０５にて、暗号化タグ生成部３０３は、グループ化ビット列を暗号化して暗号化タグを生成する。
具体的には、暗号化タグ生成部３０３は、タグＩＤ階層構造のグループ名とユーザ名にＳ７０１で受け取ったグループ名とユーザ名を、キーワード欄にＳ２４０４にて生成したグループ化ビット列をそれぞれ指定して、その値が設定されたタグＩＤ階層構造からタグＩＤ属性ベクトルを生成し、既存秘匿検索方式の暗号化アルゴリズム（Ｅｎｃ）でタグを作成する。
このタグを暗号化タグとする。
非特許文献５では、秘匿検索用のタグの生成方式は明示的に記載されていないが、一般的に次の様に実施すれば良い事が知られている。
最初に、乱数Ｒを選び、この乱数ＲをタグＩＤ属性ベクトルを用いて暗号化する事で暗号文Ｃを得る。
そして、タグを（乱数Ｒ、暗号文Ｃ）の組とすれば良い。
なお、上記はキーワード１個に対する処理であるため、これをデータに関連付けられた全てのキーワードに対して実施する。
また、Ｓ７０１にて複数のグループ名とユーザ名を受領している場合、全てのグループ名とユーザ名の組に対して暗号化タグを生成する。
【０１８６】
次に、ステップＳ７０６にて、タグ付き暗号化データ生成部３０４は、Ｓ７０３で生成した暗号化データと、Ｓ２４０５で生成した暗号化タグを結合してタグ付き暗号化データを生成し、これをデータセンタ装置４０１に保管依頼として送付する。
この時、データセンタ装置４０１でタグ付き暗号化データの保管を容易にするため、タグ付き暗号化データ生成部３０４は、Ｓ７０１にて受領したグループ名とユーザ名を共に送付する。
ステップＳ２４０５での暗号化タグの生成処理が若干変更になっているため、タグ付き暗号化データの構成も図３４で示した様に、実施の形態１の図１６から暗号化タグの構成が変わった構成となっている。
【０１８７】
次に、ステップＳ７０７の処理は、実施の形態１と同一であるため説明は省略する。
【０１８８】
次に、ステップＳ７０８の処理は、図２５を用いて詳細に説明する。
なお、実施の形態１と同様に、インデックス情報もグループ名、ユーザ名ごとに管理しているものとする。
【０１８９】
次に、ステップＳ８０１の処理は、実施の形態１と同様のため説明は省略する。
【０１９０】
次に、ステップＳ２５０２にて、インデックス管理部４０５は、Ｓ７０７にて受領した複数の暗号化タグの中から、保管していない暗号化タグ（＝タグ）を１個取りだす。
【０１９１】
次に、ステップＳ２５０３にて、インデックス管理部４０５は、ステップＳ８０１で取り出したＬ’個のグループ判定鍵を用いて、それぞれのグループ判定鍵（暗号化タグ用）でタグを復号する。
具体的には、インデックス管理部４０５は、例えば第１階層に対応したグループ判定鍵（暗号化タグ用）でタグ（Ｒ，Ｃ）のうち暗号文Ｃを復号し、復号結果が乱数Ｒと同一であった場合、第１情報を０とし、同一でなかった場合は第１情報を１とする。
同様の手順にて、第１情報から第Ｌ’情報までを決定する。
【０１９２】
次に、ステップＳ８０４とＳ８０５の処理は、実施の形態１と同様であるため説明を省略する。
以上の手順により、アクセス端末装置３０１はデータを暗号化してデータセンタ装置４０１に保管を要求し、データセンタ装置４０１は受け取ったタグ付き暗号化データの保管を行う事ができる。
【０１９３】
次に、図２６と図２７に基づき、暗号化データの検索処理について説明する。
なお、処理の流れ自体は実施の形態１で示した方式と類似しているが、既存秘匿検索方式や既存暗号化方式のアルゴリズムの相違から処理内容が若干異なっている。
そのため、実施の形態１で示した処理の流れとの差異を中心に説明する。
【０１９４】
はじめに、ステップＳ９０１は実施の形態１と同様であるため説明は省略する。
【０１９５】
次に、ステップＳ２６０２で、グループ化ビット列生成部２３０１は、Ｓ９０１にて受け取った検索キーワードからグループ化ビット列を生成する。
本処理は、ステップＳ２４０４の処理と同一であるため省略する。
【０１９６】
次に、ステップＳ２６０３にて、検索クエリ生成部３０６は、Ｓ２６０２で受け取ったグループ化ビット列と、ユーザ秘密鍵管理部３０５で保管されているユーザ秘密鍵を用いて、検索クエリを生成する。
具体的には、秘匿検索用ユーザ秘密鍵には、タグＩＤ階層構造のグループ名とユーザ名に値が設定されているが、キーワード欄に関しては値が設定されておらず、後でユーザによって値の設定ができる様になっている。
そこで、検索クエリ生成部３０６は、キーワード欄に設定する値であるグループ化ビット列を指定して生成したタグＩＤ述語ベクトルと、秘匿検索用ユーザ秘密鍵と入力として、既存秘匿検索方式の検索クエリ生成関数（Ｄｅｌｅｇａｔｅ関数）を実行して、生成された秘密鍵をトラップドアとする。
このトラップドアは、タグＩＤ階層構造で示した全ての要素に値が設定された状態となっている。
このトラップドアを検索クエリとする。
そして、生成した検索クエリをデータセンタ装置４０１に送付する。
この時、ユーザ自身のグループ名とユーザ名も送付する。
【０１９７】
次に、ステップＳ９０４にて、検索処理部４０６は、Ｓ９０３にて受け取った検索クエリからトラップドアを取り出し、インデックス情報から検索候補となる暗号化タグを全て取得する。
【０１９８】
なお、インデックス管理部４０５における暗号化タグの取得処理は複雑であるため、図２７を用いて詳細を説明する。
【０１９９】
最初にステップＳ１００１とステップＳ１００２は、実施の形態１と同様であるため説明を省略する。
【０２００】
次に、ステップＳ２７０３にて、インデックス管理部４０５は、ステップＳ８０１で取り出したＬ’個のグループ判定鍵を用いて、トラップドアを用いてそれぞれのグループ判定鍵（検索クエリ用）を復号する。
具体的には、インデックス管理部４０５は、例えば第１階層に対応したグループ判定鍵（検索クエリ用）は（Ｒ，Ｃ）から構成されているため、トラップドアを用いて暗号文Ｃを復号し、復号結果が乱数Ｒと同一であった場合、第１情報を０とし、同一でなかった場合は第１情報を１とする。
同様の手順にて、第１情報から第Ｌ’情報までを決定する。
【０２０１】
次に、ステップＳ１００４にて、インデックス管理部４０５は、ステップＳ８０４にて示した手順を用いて、２分木の中から対応するノードを特定し、そこに処理中である事を示すポインタを設定する。
そして、そのポインタが指すノードに関連付けられた暗号化タグと管理番号の組を全て取り出し、検索処理部４０６に送付する。
次に、ステップＳ１００５とステップＳ１００６とステップＳ１００７は、実施の形態１と同様であるため説明を省略する。
以上により、ステップＳ２６０４で実施する、インデックス情報から検索の候補となる暗号化タグを全て取得する処理が終了する。
【０２０２】
次に、ステップＳ９０５にて、検索処理部４０６は、Ｓ９０４にて取得した暗号化タグからタグを取り出し、既存秘匿検索技術の判定処理を用いて、タグに含まれるキーワードと、Ｓ９０４にて取り出したトラップドアに含まれるキーワードが同一であるかどうかを判定する。
具体的には、検索処理部４０６は、トラップドアでタグ（Ｒ，Ｃ）のうち暗号文Ｃを復号し、復号結果が乱数Ｒと同一であった場合、キーワードが一致したと判定する。
同一でなかった場合は、キーワードが一致しなかったと判定する。
なお、既存秘匿検索技術の判定処理は、１個のタグと、１個のトラップドアの比較しか実施できないため、これをＳ９０４にて取得した全ての暗号化タグに対して実施する。
そして、判定処理の結果、一致と判定された暗号化タグに関連付けられた管理番号を特定する。
【０２０３】
次に、ステップＳ９０６とステップＳ９０７は、実施の形態１と同様であるため説明を省略する。
以上の手順により、アクセス端末装置３０１はユーザから検索キーワードを受け取り、そのキーワードを含む暗号化データをデータセンタ装置４０１から取得し、それを復号して閲覧する事ができる。
【０２０４】
次に、図２８に基づき、インデックスツリーの階層数を追加する時のインデックス再構成処理について説明する。
なお、処理の流れ自体は実施の形態１で示した方式と類似しているが、既存秘匿検索方式や既存暗号化方式のアルゴリズムの相違から処理内容が若干異なっている。
そのため、実施の形態１で示した処理の流れとの差異を中心に説明する。
【０２０５】
はじめにステップ１１０１は、実施の形態１と同様であるため説明を省略する。
【０２０６】
次に、ステップＳ２８０２にて、グループ判定鍵生成部３０８は、ユーザ秘密鍵管理部３０５から秘匿検索用ユーザ秘密鍵と公開パラメータ、既に発行済みのグループ判定鍵の階層数を取り出す。
そして、グループ判定鍵生成部３０８は、新たに発行するグループ判定鍵の階層Ｌ’＋１を特定する。
次に、グループ判定鍵生成部３０８は、タグＩＤ階層構造のグループ化情報のうち第Ｌ’＋１情報に０を指定する。
その他の第１情報から第Ｌ’情報と、第Ｌ’＋２情報から第Ｌ情報と、キーワード情報にはワイルドカードを指定する。
このタグＩＤ階層構造に対して、グループ判定鍵生成部３０８は、ユーザ秘密鍵に埋め込まれたグループ名とユーザ名を組み合わせる事でタグＩＤ述語ベクトルを生成すると共に、Ｓ１１０１にて受け取ったグループ名とユーザ名を組み合わせる事でタグＩＤ属性ベクトルを生成する。
そして、グループ判定鍵生成部３０８は、秘匿検索用ユーザ秘密鍵と、上記で生成したタグＩＤ述語ベクトルを入力として、既存秘匿検索方式の検索クエリ生成関数（Ｄｅｌｅｇａｔｅ関数）を実行する事で、第Ｌ’＋１階層に対応するグループ判定鍵（暗号化タグ用）を生成する。
更に、グループ判定鍵生成部３０８は、ステップＳ２４０５と同様の手順にて、上記で生成したタグＩＤ属性ベクトルを入力としてタグ（Ｒ，Ｃ）を生成し、これをグループ判定鍵（検索クエリ用）とする。
そして、グループ判定鍵生成部３０８は、生成したグループ判定鍵（暗号化タグ用）とグループ判定鍵（検索クエリ用）を合わせてグループ判定鍵として、再構成したいインデックスに関連付けられたグループ名とユーザ名と共にデータセンタ装置４０１に送付する。
【０２０７】
次に、ステップ１１０３とＳ１１０４は、実施の形態１と同様であるため説明を省略する。
【０２０８】
次に、ステップＳ１１０５にて、インデックス管理部４０５は、ステップＳ１１０４もしくはＳ１１０７で選択した第Ｌ’階層ノードに関連付けられた暗号化タグと管理番号を取り出し、さらに暗号化タグからタグを取り出す。
そして、インデックス管理部４０５は、ステップＳ２５０３と同様の手順にて、タグから第Ｌ’＋１階層に振り分けるための第Ｌ’＋１情報を取得する。
そして、インデックス管理部４０５は、暗号化タグと管理番号を、選択した第Ｌ’階層ノードの子ノードのいずれに振り分けるかを第Ｌ’＋１情報を元に決定し、第Ｌ’階層ノードの関連付けを削除して、新たに第Ｌ’＋１階層ノードに関連付けて保存する。
これを選択した第Ｌ’階層に関連付けられた全ての暗号化タグに対して実施する。
【０２０９】
次に、ステップＳ１１０６とＳ１１０７は、実施の形態１と同様であるため説明を省略する。
以上の手順により、アクセス端末装置３０１はデータセンタ装置４０１に対してグループ判定鍵を新たに生成してインデックス情報の再構成を要求し、データセンタ装置４０１は自身が管理するインデックス情報の再構成を行う事で、インデックス情報の階層数を１階層増やす事ができる。
【０２１０】
以上の様に、暗号化タグに対してキーワードから生成したグループ化情報を含めておき、データセンタ装置４０１がユーザからグループ判定鍵を受け取る事で、グループ化情報（暗号化タグ用）を用いてキーワードに応じた暗号化タグのグループ化を行う事ができる。
検索の際にも、検索クエリとグループ判定鍵（検索クエリ用）を用いて検索対象の暗号化タグのグループを一意に特定できる様にしているため、全ての暗号化タグに対して既存秘匿検索技術の判定処理を行う必要が無くなり、特定のグループに属する暗号化タグに対してのみ既存秘匿検索技術の判定処理を行えばよく、秘匿検索の時間を大きく削減する事ができる。
例えば、Ｌ’個のグループ判定鍵がデータセンタ装置４０１に開示されている状況では、暗号化タグＭ個を２＾Ｌ’個のグループに分割する事ができるため、各グループには平均的にＭ／２＾Ｌ’個の暗号化タグが含まれる。
そのため、本実施の形態によって、検索処理は２＾Ｌ’倍に高速化される。
【０２１１】
また、グループ化を行うための情報を１ビット単位などでタグＩＤ階層構造の異なる要素に設定して暗号化して、ユーザがタグＩＤ階層構造に含めた情報を判定するためのグループ判定鍵を開示する事で、データセンタ装置４０１がグループ化に用いるための情報を生成できる様にしている。
そのため、開示するグループ判定鍵の数によって、ユーザがグループ化のレベルを調整する事ができる。
例えば、Ｌ’個のグループ判定鍵を開示している状況で、暗号化データの保管数が増えるに従って検索時間がＴ時間になり、運用に支障が生じたとする。
この時、新しくＬ’＋１階層目に対応したグループ判定鍵を開示する事で、暗号化タグを２倍のグループに分割する事ができるため、検索時間をＴ／２に削減する事ができる様になる。
【０２１２】
一方、暗号アルゴリズム開発の世界では、暗号化データ中に含まれるキーワードによって、暗号化データのグループ化ができない事が高い安全性を持つ暗号だと評価される。
そのため、データの機密性を保護したいユーザからすれば、不必要にデータセンタ装置４０１に暗号化データをグループ化されてしまう事は望まない。
本実施の形態では、ユーザが求める安全性のレベルと検索処理の応答時間に応じて、必要最小限のグループ判定鍵のみをデータセンタ装置４０１に与える様にユーザ自身が制御する事ができる。
そのため、グループ化情報としてＬビットの情報を付加していたとしても、開示するグループ判定鍵の数を調整する事で、ユーザ自身によって安全性と高速性のバランスを調整する事ができる。
【０２１３】
更に、開示するグループ判定鍵の数の調整は、正規のユーザ秘密鍵を持つユーザしか実施できないため、第三者によって不正にグループ判定鍵を作成・開示する様な、安全性を低下させる不正を防止する事ができる。
【０２１４】
また、グループ判定鍵（暗号化タグ用）とグループ判定鍵（検索クエリ用）を用いて、データセンタ装置４０１側で第ｉ情報を生成する様な仕組みとした。
そのため、グループ化情報に設定した値自身もデータセンタ装置４０１には分からないため、それがキーワードのハッシュ値であったとしてもキーワードの推測が困難であり、安全性を向上させる事ができる。
【０２１５】
また、本実施の形態に係る方式は、内積述語暗号に基づく既存秘匿検索のタグに対してグループ化情報を含める事で、その検索性能を向上させる拡張方式である。
そのため、本実施の形態で示した既存秘匿検索方式だけでなく、提案されている様々な既存秘匿検索方式に対して適用可能であり、その検索性能を向上させる事ができる。
本実施の形態では、非特許文献５の記載の方式に適用した例を示したが、例えば非特許文献３に記載の方式にも適用できるし、その他の内積述語暗号や関数型暗号など、あらゆる既存秘匿検索方式に対して適用可能である。
【０２１６】
また、既存秘匿検索方式だけでなく、既存暗号化方式として何を用いるかに依存しない高速化手法とした。
そのため、一般的によく利用されているＲＳＡ（登録商標）暗号などを利用する事も可能である。
また、本実施の形態では確率的暗号に基づく秘匿検索技術を高速化する手法について示した。
一般的に秘匿検索の検索時間だけを見れば確定的暗号に基づく方式が早いが、暗号化データの出現頻度を分析して平文を推定できるという課題がある。
一方、確率的暗号に基づく方式は、暗号化データの出現頻度がキーワードの出現頻度と無関係なため、出現頻度の分析による平文の推定に対して安全であるが、検索処理にとても時間がかかるという課題がある。
しかし、本実施の形態は確率的暗号に基づいているため、検索が高速化されているにもかかわらず、出現頻度による分析に対しての安全性が残っているというメリットがある。
【０２１７】
また、暗号化データやインデックスは、グループ名とユーザ名の組ごとに作成・管理を行う仕組みとした。
そのため、ユーザが検索を行う場合、元々読む事ができない暗号化データが含まれるインデックス情報を検索する必要が無くなるため、検索処理を大きく向上させる事ができる。
【０２１８】
また、グループ名やユーザ名によって暗号化データの開示範囲が決められるが、一般的に開示範囲ごとに保管される暗号化データの数が異なる事が予想される。
本実施の形態では、グループ判定鍵の開示は、グループ名とユーザ名の組と関連付けられたインデックスに対して実施する様な仕組みとした。
そのため、開示範囲ごとに安全性と高速性のバランスを調整する事ができる。
【０２１９】
また、インデックス情報から検索対象とすべき暗号化タグを取得する際、検索クエリからグループ判定鍵を用いて生成された第ｉ情報を用いて特定されたノードに関連付けられた暗号化タグだけでなく、その全ての上位ノードに関連付けられた暗号化タグも検索対象とする様にした。
そのため、追加でグループ判定鍵を受け取ってインデックス情報の再構成を行っている最中に検索クエリを受け取ったとしても、検索対象とすべき暗号化タグを漏らすことなくチェックする事ができる。
【０２２０】
また、暗号化データを生成する際に複数のグループ名とユーザ名を受け取る様な仕組みとしているため、開示先のユーザやグループが複数あったとしても、本方式で複数の開示先に暗号化データを開示すると共に、開示先数に依存せずに検索速度を向上させる事ができる。
【０２２１】
また、暗号化データに関連付けるキーワードは、本文から自動抽出しても良いし、ユーザが指定する様にしても良いし、その両者を組み合わせる事もできる様にしたため、検索時に指定されるであろうキーワードをユーザの意図通りに付加する事ができる。
【０２２２】
また、タグとグループ化情報を一体化したため、グループ化情報を差し替える様な攻撃は発生せず、安全に利用する事が可能となる。
【０２２３】
また、データを暗号化する際に、ＡＥＳやＣａｍｅｌｌｉａ（登録商標）等の高速な共通鍵暗号を利用できる仕組みとしたため、動画や音楽データなどの大きなサイズのデータであっても、高速に暗号化する事が可能である。
【０２２４】
また、鍵管理サーバ装置２０１にユーザＩＤ情報データベースを持たせているので、ユーザが暗号化データを復号可能なユーザのグループ名やユーザ名が分からなかったとしても、ユーザが知っているメールアドレスなどの別の情報を元にして、正しいグループ名やユーザ名を取得する事ができるので、暗号化データの開示範囲を誤って設定する事を防止する事ができる。
同様に、暗号化タグを生成したりするための補助にもなる。
【０２２５】
（２分木以外も適用可能）
なお、本実施の形態では、２分木を用いたインデックス情報を構成する例を示した。
しかし、生成するインデックスは２分木に限る必要はなく、グループ化情報から生成する事ができるものであれば、より一般的な木構造であっても良く、ハッシュテーブルであっても良い。
また、インデックス情報として作成した２分木は、その構造を保ったままディスクに保管する必要はなく、例として示した様にノード番号を割り当てて表形式で保管しても良いし、その他のデータ形式で保管しても良い。
【０２２６】
（グループ化情報は１ビットに制約する必要はない）
また、本実施の形態では、キーワードから生成したビット列の第ｉビットを第ｉ情報として用いる様にした。
しかし、１ビットずつ利用する必要はなく、２ビット以上の情報を用いて第ｉ情報を生成する様にしても良い。
例えば、キーワードから２Ｌビットのビット列を生成し、その第２ｉ−１ビット目と第２ｉビット目を第ｉ情報として利用することも可能である。
【０２２７】
（グループ化情報に使う情報）
また、本実施の形態では、グループ化情報の第ｉ情報には、０や１といった１ビットの情報を含める例を示した。
しかし、本情報を用いて２分木の子ノード（左）か子ノード（右）かを判断できればいいので、必ずしも０や１の値である必要はない。
例えば、１と−１でも良いし、その他の値を入れる様にしても良い。
【０２２８】
同様に、第Ｌ’＋１階層目のグループ判定鍵を生成する際に、第Ｌ’＋１情報に０を指定する様な例とした。
しかし、必ずしも０を設定する必要はなく、１を設定する様にしても良い。
また、第ｉ情報が１と−１のいずれかを設定する様にした場合は−１でも良いし、その他の値を入れる様にしても良い。
【０２２９】
同様に、グループ判定鍵（暗号化タグ用）を用いてタグを復号した場合、もしくはトラップドアを用いてグループ判定鍵（検索クエリ用）を復号した場合、正しく復号した場合に第ｉ情報を０とみなし、正しく復号できなかった場合に第ｉ情報を１とみなす様にした。
しかし、この０と１の割り振りは逆であっても良い。
【０２３０】
（ハッシュ値以外も利用可能）
また、本実施の形態では、キーワードからＬビットのビット列を作成する際に、例えばＳＨＡ−２等のハッシュ関数を利用する事を例示したが、Ｌビットのビット列が作れるものであればアルゴリズムは何でも良い。
例えば、ＳＨＡ−２以外のハッシュ関数を用いても良いし、ＨＭＡＣ等の鍵付きハッシュや、ＡＥＳ等の共通鍵暗号や、ＲＳＡ（登録商標）暗号等の公開鍵暗号を用いても良い。
なお、鍵付きハッシュや共通鍵暗号や公開鍵暗号を用いる場合は、秘匿検索用ユーザ秘密鍵に加えてハッシュ鍵や共通鍵や秘密鍵も配布する必要がある。
また、キーワードを乱数のシードとして、疑似乱数生成アルゴリズムでＬビットの乱数を生成する様にしても良い。
他にも、キーワードとＬビット列の対応表を使う様にしても良い。
特に、Ｌビット列の対応表を用いる場合、キーワードの出現頻度を考慮してＬビット列の発生頻度を平準化できるため、安全性が更に向上する事が期待できる。
【０２３１】
（グループ判定鍵の公開数）
また、本実施の形態では、ユーザがグループ判定鍵を１個ずつ開示する事を想定した例を記載したが、１回に１個ずつと制限する必要はなく、同時に２個や３個のグループ判定鍵を公開する様にしても良い。
【０２３２】
（グループ判定鍵生成のタイミング）
また、本実施の形態では、ユーザがインデックス再構成を行うタイミングでグループ判定鍵を生成していた。
しかし、グループ判定鍵はインデックス再構成を行う前であればいつ生成しても良い。
更に、ユーザではなく、鍵管理サーバ装置２０１がユーザ秘密鍵発行時に代行して生成しても良い。
【０２３３】
（ＩＤ階層数の制約はない）
また、本実施の形態では、タグＩＤ階層構造や復号者ＩＤ階層構造にて、グループ名とユーザ名の２種類の情報を用いて復号・検索が可能なユーザやグループを指定する例を示した。
しかし、この２種類の情報に制限する必要はなく、例えば部名・課名・氏名の３種を用いても良いし、氏名だけを用いても良い。
また、内積述語暗号ではＡＮＤやＯＲ等の条件を用いて受信者の属性を指定できるので、その様に柔軟に受信者を指定できるようにしても良い。
【０２３４】
（ベクトル化手法は任意）
また、本実施の形態では、タグＩＤ階層構造をタグＩＤ述語ベクトルやタグＩＤ属性ベクトルに変換する方式として、タグＩＤ述語ベクトルの場合は（ｖ１，ｖ２）＝（１，−“グループ名”）とし、タグＩＤ属性ベクトルの場合は（ｘ１，ｘ２）＝（“グループ名”，１）とする例を示した。
しかし、例えば（ｖ１，ｖ２）＝（１，−“グループ名”）と（ｘ１，ｘ２）＝（“グループ名”，１）としても良いし、他の変換方法を用いても構わない。
タグＩＤ階層構造からタグＩＤ述語ベクトルやタグＩＤ属性ベクトルへの変換方法に制約はなく、一般的に知られた様々な方法を利用する事ができる。
同様に、復号者ＩＤ階層構造に関しても同様である。
【０２３５】
（ＩＤ共通化は不要）
また、本実施の形態では、タグ付き暗号化データを生成する際、タグＩＤ階層構造や復号者ＩＤ階層構造に、グループ名とユーザ名として同じ値を設定する例を示した。
しかし、これらは同じ値にせず、異なる値を設定しても良い。
例えば、ユーザには検索だけ許可し、暗号化データ自身の復号は許可したくない場合は、タグＩＤ階層構造にはユーザのグループ名とユーザ名を設定し、復号者ＩＤ階層構造には別の復号可能なユーザのグループ名とユーザ名を設定すればよい。
【０２３６】
（鍵管理サーバ装置２０１の階層化）
また、本実施の形態では、鍵管理サーバ装置２０１が１台の例を示したが、１台に制限する必要はない。
例えば、非特許文献５の方式や、その他の秘匿検索方式では、鍵管理サーバ装置にも階層構造を持たせ、複数台に役割を分散して運用する形態も記載されている。
本実施の形態でも同様にして、鍵管理サーバ装置に階層構造を持たせた形で利用する事も可能である。
【０２３７】
（内積述語暗号以外も適用可能）
また、本実施の形態では、内積述語暗号に基づく既存秘匿検索方式や既存暗号化方式を用いた例を示した。
しかし、内積述語暗号に基づく方式に制約するものではなく、同様の機能を実現した関数型暗号などを用いる事も可能であるし、ＡＥＳやＣａｍｅｌｌｉａ（登録商標）やＨＭＡＣなどの共通鍵暗号や、ＲＳＡ（登録商標）暗号などの公開鍵暗号を用いる事も可能である。
【０２３８】
（公開パラメータの共通化も可能）
また、本実施の形態では、既存秘匿検索方式や既存暗号化方式に非特許文献５に記載の内積述語暗号を用いた例を示したが、それぞれ異なる公開パラメータを利用する様にした。
しかし、例えば利用する楕円曲線など、公開パラメータの一部の情報を共通化して利用する事も可能である。そのため、共通化できるものは共通化して利用しても構わない。
【０２３９】
（キーワード数）
また、本実施の形態では、検索キーワードが１個の場合を示したが、必ずしも検索キーワードを１個に制限する必要はない。
例えば、複数の検索キーワードがある場合、それぞれのキーワードに対して検索クエリを生成して、全ての検索クエリをデータセンタ装置４０１に送付しても良い。
またその時、例えば１個の検索クエリでヒットと判定された暗号化データを取得するとか、検索クエリＡと検索クエリＢの両方がヒットした暗号化データを取得する等、任意の条件も送付して良い。
【０２４０】
（タグのチェック不要化）
また、本実施の形態では、インデックス管理部４０５から取得した暗号化タグの全てを検索クエリと判定する様にした。
しかし、検索にヒットしたと判定された暗号化データに関しては、それ以降、その暗号化データに関連付けられた暗号化タグのチェックをしなくても構わない。また、検索結果として例えば１０件の結果を返せばいい場合においても、規定個数以上の検索結果が見つかったら、それ以降の暗号化タグのチェックを行わなくても良い。
【０２４１】
（ユーザＩＤ情報データベースの必要有無）
また、本実施の形態では、鍵管理サーバ装置２０１にユーザＩＤ情報データベースを設け、その情報を元にユーザ秘密鍵の生成を行っていた。
しかし、ユーザＩＤ情報データベースは必ずしも必須なものではなく、ユーザ秘密鍵を発行する際に鍵管理サーバ装置２０１の管理者によって指定する様にしても良いし、アクセス端末装置３０１から受領する様にしても良い。
【０２４２】
（アクセス端末装置３０１＝ユーザとの仮定、ＩＣカードの利用）
また、本実施の形態では、アクセス端末装置３０１は一人のユーザが操作するものと仮定した記載とした。
しかし、アクセス端末装置３０１自身は一人のユーザが占有するものではなく、複数名で共有する様な仕組みでも良い。
この場合、ユーザ秘密鍵管理部３０５ではユーザごとに１個のユーザ秘密鍵が割り当てられるため、複数のユーザ秘密鍵を保管する様にして、アクセス端末装置３０１で操作者の認証をする事で、どのユーザ秘密鍵を利用すべきかを判断する事が好ましい。
また、ユーザ秘密鍵を社員証などに保管して管理する事も可能である。
この場合、ユーザ秘密鍵管理部３０５がＩＣカードに相当する機能だが、ユーザ秘密鍵を用いた処理をＩＣカードにて全て行わせる場合、必要に応じて検索クエリ生成部３０６やデータ復号部３０７やグループ判定鍵生成部３０８の一部の処理をＩＣカードに実施させても良い。
【０２４３】
（データ本体の暗号化方式）
また、本実施の形態では、データを暗号化する際にＡＥＳやＣａｍｅｌｌｉａ（登録商標）を自動的に用いる事を例示したが、これはシステム内で事前に利用する方式を決定しておいても良いし、ユーザによって設定できる様にしておいても良い。
【０２４４】
（検索結果の返却方法）
また、本実施の形態では、検索の結果、ヒットした暗号化データを全て返却する様な例を示したが、必ずしも検索時に同時に全ての暗号化データ自身を返却する必要はない。
例えば、ヒットした暗号化データのうち数個を返すだけにするとか、個数だけを返す様にするとか、暗号化データのリストだけを返却する様にしても良い。
【０２４５】
（システム構成のバリエーション）
また、本実施の形態では、鍵管理サーバ装置２０１とアクセス端末装置３０１が企業内にあり、データセンタ装置４０１がインターネットなどに接続された外部サービスとして存在した例を示した。
しかし、本発明はこの様なシステム構成に限定されるものではない。
例えば、データセンタ装置４０１が企業内にあっても良いし、鍵管理サーバ装置２０１やアクセス端末装置３０１が企業外のネットワークに接続されていても良い。
【０２４６】
なお、本実施の形態では、
アクセス端末装置３０１のグループ化ビット列生成部２３０１（インデックス導出ビット列、秘匿化処理部）は、実施の形態１と異なり、内積述語暗号を用いていることを説明した。
【０２４７】
また、本実施の形態では、
グループ化ビット列生成部２３０１は、
保管キーワードのハッシュ値から、インデックス情報のノードの最大階層数と同数であるＬビットのビット列を抽出するとともに、ハッシュ値の他のビット又はハッシュ値全体をキーワード情報とし、
更に、暗号化タグ生成部３０３は、Ｌビットのビット列及びキーワード情報を暗号化し、暗号化したＬビットのビット列及びキーワード情報を暗号化タグとし、暗号化タグをデータセンタ装置４０１に送信することを説明した。
換言すると、グループ化情報生成部３１０は、
保管キーワードから一意に得られる乱数値のビット列から、許可ビット位置として指定できる最大数と同数のビット数の保管インデックス導出ビット列を生成し、更に、乱数値のビット列の他のビット又は乱数値のビット列全体をキーワード情報とし、
暗号化タグ生成部３０３は、
保管インデックス導出ビット列及びキーワード情報を暗号化し、暗号化した保管インデックス導出ビット列及びキーワード情報をタグデータとし、タグデータをデータセンタ装置４０１（データ保管装置）に送信している。
【０２４８】
また、本実施の形態では、
グループ化ビット列生成部２３０１は、
検索キーワードのハッシュ値から、インデックス情報のノードの最大階層数と同数であるＬビットのビット列を抽出するとともに、ハッシュ値の他のビット又はハッシュ値全体をキーワード情報とし、
更に、暗号化タグ生成部３０３は、Ｌビットのビット列及びキーワード情報を暗号化し、暗号化したＬビットのビット列及びキーワード情報をトラップドアとし、トラップドアをデータセンタ装置４０１に送信することを説明した。
換言すると、グループ化情報生成部３１０は、
検索キーワードから一意に得られる乱数値のビット列から、許可ビット位置として指定できる最大数と同数のビット数の検索インデックス導出ビット列を生成し、更に、乱数値のビット列の他のビット又は乱数値のビット列全体をキーワード情報とし、
暗号化タグ生成部３０３は、
検索インデックス導出ビット列及びキーワード情報を暗号化し、暗号化した検索インデックス導出ビット列及びキーワード情報を暗号化した検索キーワードとし、暗号化した検索キーワードをデータセンタ装置４０１（データ保管装置）に送信している。
【０２４９】
また、本実施の形態では、
データセンタ装置４０１のインデックス管理部４０５は、
タグ付き暗号化データを受信した際に、暗号化タグをグループ判定鍵で復号し、正しく復号できた場合にビット値０とし、復号できなかった場合にビット値を１とすることで、Ｌ’個分のビット値を導出してノード番号としている。
換言すれば、インデックス管理部４０５は、
保管要求を受信した際に、タグデータ内の暗号化ビットのうち許可ビット位置の暗号化ビットを許可ビット復号鍵で復号し、正しく復号できた場合にビット値０とし、復号できなかった場合にビット値を１とすることで、復号結果から保管インデックス値の各ビットのビット値を導出し、導出した各ビットのビット値を連結して保管インデックス値を導出している。
【０２５０】
また、本実施の形態では、
データセンタ装置４０１のインデックス管理部４０５は、
検索クエリを受信した際に、トラップドアをグループ判定鍵で復号し、正しく復号できた場合にビット値０とし、復号できなかった場合にビット値を１とすることで、Ｌ’個分のビット値を導出してノード番号としている。
換言すれば、インデックス管理部４０５は、
検索要求を受信した際に、暗号化された検索キーワード内の暗号化ビットのうち許可ビット位置の暗号化ビットを許可ビット復号鍵で復号し、正しく復号できた場合にビット値０とし、復号できなかった場合にビット値を１とすることで、復号結果から検索インデックス値の各ビットのビット値を導出し、導出した各ビットのビット値を連結して検索インデックス値を導出している。
【０２５１】
最後に、実施の形態１及び２に示した鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１のハードウェア構成例について説明する。
図３５は、実施の形態１及び２に示す鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１のハードウェア資源の一例を示す図である。
なお、図３５の構成は、あくまでも鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１のハードウェア構成の一例を示すものであり、鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１のハードウェア構成は図３５に記載の構成に限らず、他の構成であってもよい。
また、鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１は、それぞれ異なるハードウェア構成であってもよい。
【０２５２】
図３５において、鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）と接続していてもよい。
また、磁気ディスク装置９２０の代わりに、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
例えば、実施の形態１及び２で説明した鍵保管部２０３、ユーザＩＤ情報管理部２０６、ユーザ秘密鍵管理部３０５、インデックス管理部４０５及び暗号化データ管理部４０４は、ＲＡＭ９１４、磁気ディスク装置９２０等に、各種鍵、インデックス情報、暗号化データ、タグデータ等を保管している。
通信ボード９１５、キーボード９０２、マウス９０３、ＦＤＤ９０４などは、入力装置の一例である。
また、通信ボード９１５、表示装置９０１などは、出力装置の一例である。
【０２５３】
通信ボード９１５は、図１に示すように、ネットワークに接続されている。
例えば、通信ボード９１５は、社内ＬＡＮ（ローカルエリアネットワーク）、インターネットの他、ＷＡＮ（ワイドエリアネットワーク）、ＳＡＮ（ストレージエリアネットワーク）などに接続されていても構わない。
【０２５４】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。
【０２５５】
また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。
【０２５６】
また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。
【０２５７】
上記プログラム群９２３には、実施の形態１及び２の説明において「〜部」として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
【０２５８】
ファイル群９２４には、実施の形態１及び２の説明において、「〜の判断」、「〜の計算」、「〜の比較」、「〜の評価」、「〜の更新」、「〜の設定」、「〜の保管」、「〜の登録」、「〜の選択」、「〜の導出」、「〜の生成」、「〜の抽出」、「〜の取得」、「〜の特定」、「〜の暗号化」、「〜の復号」、「〜の入力」、「〜の出力」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。
ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出される。
そして、読み出された情報やデータや信号値や変数値やパラメータは、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、実施の形態１及び２で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示す。
データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。
また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【０２５９】
また、実施の形態１及び２の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。
すなわち、実施の形態１及び２で説明したフローチャートに示すステップ、手順、処理により、データ処理装置及びデータ保管装置を方法として把握することができる。
また、「〜部」として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。
或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。
ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。
プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。
すなわち、プログラムは、実施の形態１及び２の「〜部」としてコンピュータを機能させるものである。あるいは、実施の形態１及び２の「〜部」の手順や方法をコンピュータに実行させるものである。
【０２６０】
このように、実施の形態１及び２に示す鍵管理サーバ装置２０１、アクセス端末装置３０１及びデータセンタ装置４０１は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータである。
そして、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【符号の説明】
【０２６１】
２０１  鍵管理サーバ装置、２０２  マスター鍵生成部、２０３  鍵保管部、２０４  ユーザ秘密鍵生成部、２０５  ＰＫＧ側データ送受信部、２０６  ユーザＩＤ情報管理部、３０１  アクセス端末装置、３０２  データ暗号化部、３０３  暗号化タグ生成部、３０４  タグ付き暗号化データ生成部、３０５  ユーザ秘密鍵管理部、３０６  検索クエリ生成部、３０７  データ復号部、３０８  グループ判定鍵生成部、３０９  端末側データ送受信部、３１０  グループ化情報生成部、４０１  データセンタ装置、４０２  センタ側データ送受信部、４０３  保管要求処理部、４０４  暗号化データ管理部、４０５  インデックス管理部、４０６  検索処理部、２３０１  グループ化ビット列生成部。
【図１】
2012095973.tif 000003
【図２】
2012095973.tif 000004
【図３】
2012095973.tif 000005
【図４】
2012095973.tif 000006
【図５】
2012095973.tif 000007
【図６】
2012095973.tif 000008
【図７】
2012095973.tif 000009
【図８】
2012095973.tif 000010
【図９】
2012095973.tif 000011
【図１０】
2012095973.tif 000012
【図１１】
2012095973.tif 000013
【図１２】
2012095973.tif 000014
【図１３】
2012095973.tif 000015
【図１４】
2012095973.tif 000016
【図１５】
2012095973.tif 000017
【図１６】
2012095973.tif 000018
【図１７】
2012095973.tif 000019
【図１８】
2012095973.tif 000020
【図１９】
2012095973.tif 000021
【図２０】
2012095973.tif 000022
【図２１】
2012095973.tif 000023
【図２２】
2012095973.tif 000024
【図２３】
2012095973.tif 000025
【図２４】
2012095973.tif 000026
【図２５】
2012095973.tif 000027
【図２６】
2012095973.tif 000028
【図２７】
2012095973.tif 000029
【図２８】
2012095973.tif 000030
【図２９】
2012095973.tif 000031
【図３０】
2012095973.tif 000032
【図３１】
2012095973.tif 000033
【図３２】
2012095973.tif 000034
【図３３】
2012095973.tif 000035
【図３４】
2012095973.tif 000036
【図３５】
2012095973.tif 000037
【手続補正書】
【提出日】平成25年5月13日(2013.5.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の暗号化データと、各暗号化データに対応付けられている、暗号化データの検索の際に照合されるタグデータとを保管するデータ保管装置に接続されたデータ処理装置であって、
前記データ保管装置での保管の対象となる保管対象データのキーワードを保管キーワードとして指定するキーワード指定部と、
前記データ保管装置へのビット値の開示を許可するビット位置を許可ビット位置として指定する許可ビット位置指定部と、
所定の生成手順にて、前記保管キーワードから所定のビット列を保管インデックス導出ビット列として生成するインデックス導出ビット列生成部と、
前記保管インデックス導出ビット列内の前記許可ビット位置のビット値は前記データ保管装置に開示し前記保管インデックス導出ビット列内の前記許可ビット位置以外のビット値は前記データ保管装置に秘匿する秘匿化処理を行い、前記保管対象データの暗号化データに対応付けられるタグデータを保管する際に前記データ保管装置が前記タグデータに付す保管インデックス値を、前記データ保管装置に、前記保管インデックス導出ビット列内の前記許可ビット位置の開示されたビット値から導出させる秘匿化処理部とを有し、
前記秘匿化処理部は、
許可ビット位置ごとに、許可ビット位置の暗号化ビットの復号に用いられる復号鍵を許可ビット復号鍵として生成し、
前記データ処理装置は、更に、
前記許可ビット復号鍵を前記データ保管装置に対して送信する許可ビット復号鍵送信部を有し、
前記秘匿化処理部は、
前記許可ビット位置の暗号化ビットは前記許可ビット復号鍵により復号され、前記許可ビット位置以外の暗号化ビットは前記許可ビット復号鍵により復号されない暗号化方式にて前記保管インデックス導出ビット列を暗号化し、
前記データ処理装置は、更に、
前記保管対象データの暗号化データと、前記保管対象データの暗号化データに対応付けられるタグデータと、暗号化された前記保管インデックス導出ビット列とが含まれる保管要求を前記データ保管装置に対して送信する保管要求送信部を有することを特徴とするデータ処理装置。
【請求項２】
前記データ処理装置は、
暗号化された検索キーワードと、開示が許可されているビット位置のビット値の開示により前記暗号化された検索キーワードとの照合の対象となるタグデータのインデックス値が導出される検索インデックス導出ビット列とが含まれる検索要求を受信した際に、前記検索インデックス導出ビット列内のビット値の開示により得られるインデックス値に基づき、前記暗号化された検索キーワードとの照合の対象となるタグデータを特定し、特定したタグデータと前記暗号化された検索キーワードとを照合して暗号化データを検索するデータ保管装置に接続され、
前記インデックス導出ビット列生成部は、
前記データ保管装置において前記検索インデックス導出ビット列から得られるインデックス値と比較される保管インデックス値が、前記秘匿処理部による前記データ保管装置への前記許可ビット位置のビット値の開示により導出される保管インデックス導出ビット列を生成することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記許可ビット位置指定部は、
順次新たな許可ビット位置を指定し、
前記秘匿化処理部は、
前記許可ビット位置指定部により新たな許可ビット位置が指定された場合に、前記保管インデックス導出ビット列内の既存の許可ビット位置のビット値に加えて新たに指定された許可ビット位置のビット値を前記データ保管装置に開示する秘匿化処理を行い、保管インデックス値のビット数を増加させることを特徴とする請求項１に記載のデータ処理装置。
【請求項４】
前記秘匿化処理部は、
前記保管対象データに対するアクセスが許可されるユーザのユーザ情報が反映されている復号鍵を、前記許可ビット復号鍵として生成し、
前記保管対象データに対するアクセスが許可されるユーザのユーザ情報が反映されている暗号鍵を用いて、前記保管インデックス導出ビット列を暗号化することを特徴とする請求項１に記載のデータ処理装置。
【請求項５】
前記許可ビット位置指定部は、
順次新たな許可ビット位置を指定し、
前記秘匿化処理部は、
前記許可ビット位置指定部により新たな許可ビット位置が指定された場合に、新たに指定された許可ビット位置の暗号化ビットの復号に用いられる許可ビット復号鍵を生成し、
前記許可ビット復号鍵送信部は、
前記秘匿化処理部により生成された新たな許可ビット復号鍵を前記データ保管装置に対して送信することを特徴とする請求項１に記載のデータ処理装置。
【請求項６】
前記データ処理装置は、
暗号化された検索キーワードとの照合の対象となるタグデータを特定し、特定したタグデータと前記暗号化された検索キーワードとを照合して暗号化データを検索するデータ保管装置に接続され、
前記キーワード指定部は、
前記データ保管装置に暗号化データの検索を行わせる検索キーワードを指定し、
前記インデックス導出ビット列生成部は、
前記保管インデックス導出ビット列と同じ生成手順にて、前記キーワード指定部により指定された前記検索キーワードから所定のビット列を検索インデックス導出ビット列として生成し、
前記秘匿化処理部は、
前記データ保管装置へのビット値の開示が許可されているビット位置である許可ビット位置の暗号化ビットは、前記データ保管装置が保有する許可ビット復号鍵により復号され、前記許可ビット位置以外の暗号化ビットは前記許可ビット復号鍵により復号されない暗号化方式にて前記検索インデックス導出ビット列を暗号化し、
暗号化された検索キーワードとの照合の対象となるタグデータを抽出する際に前記データ保管装置が保管インデックス値と比較する検索インデックス値を、前記データ保管装置に、暗号化された前記検索インデックス導出ビット列内の前記許可ビット位置の暗号化ビットの復号により前記データ保管装置に開示される前記許可ビット位置のビット値から導出させ、
前記データ処理装置は、更に、
暗号化された前記検索キーワードと、暗号化された前記検索インデックス導出ビット列とが含まれる検索要求を前記データ保管装置に対して送信する検索要求送信部を有することを特徴とする請求項５に記載のデータ処理装置。
【請求項７】
前記秘匿化処理部は、
前記データ処理装置のユーザのユーザ情報が反映されている暗号鍵を用いて、前記検索インデックス導出ビット列を暗号化することを特徴とする請求項６に記載のデータ処理装置。
【請求項８】
データ処理装置に接続され、前記データ処理装置から送信された暗号化データを保管するデータ保管装置であって、
復号が許可されている許可ビット位置ごとに、許可ビット位置の暗号化ビットの復号に用いられる許可ビット復号鍵を保管する許可ビット復号鍵管理部と、
保管対象の暗号化データと、暗号化データの検索の際に照合されるタグデータと、前記保管対象の暗号化データに指定された保管キーワードを用いて生成された暗号化されたビット列とが含まれる保管要求を前記データ処理装置から受信する保管要求受信部と、
前記保管要求に含まれる前記保管対象の暗号化データを、前記タグデータと対応付けて保管する暗号化データ管理部と、
前記保管要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを前記許可ビット復号鍵を用いて復号し、復号により得られるビット値からインデックス値を導出し、導出したインデックス値と前記保管要求に含まれる前記タグデータとを対応付けて保管するインデックス管理部とを有することを特徴とするデータ保管装置。
【請求項９】
前記許可ビット復号鍵管理部は、
ユーザ情報と対応付けて許可ビット復号鍵を保管し、
前記保管要求受信部は、
前記保管対象の暗号化データに対するアクセスが許可されるユーザのユーザ情報が含まれる保管要求を受信し、
前記インデックス管理部は、
前記保管要求に含まれるユーザ情報と合致するユーザ情報と対応付けられている許可ビット復号鍵を用いて、前記保管要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを復号し、インデックス値を導出することを特徴とする請求項８に記載のデータ保管装置。
【請求項１０】
前記許可ビット復号鍵管理部は、
ユーザ情報が反映されている許可ビット復号鍵を、前記ユーザ情報と対応付けて保管し、
前記保管要求受信部は、
前記保管対象の暗号化データに対するアクセスが許可されるユーザのユーザ情報が反映されている暗号鍵により暗号化されたビット列が含まれる保管要求を受信することを特徴とする請求項９に記載のデータ保管装置。
【請求項１１】
前記インデックス管理部は、
前記保管要求に含まれる前記暗号化されたビット列に対する復号により得られるビット値を連結してインデックス値を導出し、
前記保管要求に含まれるユーザ情報に、導出したインデックス値と、前記保管要求に含まれる前記タグデータと、前記暗号化されたビット列内の復号されていない暗号化ビットとを対応付けて保管し、
前記許可ビット復号鍵管理部は、
新たな許可ビット位置が指定されると、新たな許可ビット位置の暗号化ビットの復号に用いられる新たな許可ビット復号鍵と、前記新たな許可ビット復号鍵と対応付けられるユーザ情報とを取得し、
前記インデックス管理部は、
前記許可ビット復号鍵管理部により取得された前記ユーザ情報と合致するユーザ情報に対応付けられている暗号化ビットを抽出し、抽出した暗号化ビットのうち前記新たな許可ビット位置に対応する暗号化ビットを前記新たな許可ビット復号鍵を用いて復号し、復号により得られたビット値を、共通のユーザ情報に対応付けられているインデックス値に追加して新たなインデックス値を導出することを特徴とする請求項９又は１０に記載のデータ保管装置。
【請求項１２】
前記データ保管装置は、
複数のデータ処理装置に接続され、
前記データ保管装置は、更に、
前記複数のデータ処理装置のうち暗号化データの検索を要求する検索要求データ処理装置から、暗号化された検索キーワードと、暗号化前の検索キーワードを用いて生成された暗号化されたビット列と、前記検索要求データ処理装置のユーザのユーザ情報が含まれる検索要求を受信する検索要求受信部を有し、
前記インデックス管理部は、
前記検索要求に含まれるユーザ情報と合致するユーザ情報と対応付けられている許可ビット復号鍵を用いて、前記検索要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを復号し、復号により得られる前記許可ビット位置のビット値からインデックス値を導出し、導出したインデックス値と同じインデックス値と対応付けられているタグデータを抽出し、
前記データ保管装置は、更に、
前記インデックス管理部により抽出されたタグデータと前記検索要求に含まれる前記暗号化された検索キーワードとを照合し、前記インデックス管理部により抽出されたタグデータの中から、前記検索キーワードと同じキーワードから生成されているタグデータを特定し、特定したタグデータに対応付けられている暗号化データを前記暗号化データ管理部から取得する検索処理部を有することを特徴とする請求項９〜１１のいずれかに記載のデータ保管装置。
【請求項１３】
前記許可ビット復号鍵管理部は、
ユーザ情報が反映されている許可ビット復号鍵を、前記ユーザ情報と対応付けて保管し、
前記検索要求受信部は、
前記検索要求データ処理装置のユーザのユーザ情報が反映されている暗号鍵により暗号化されたビット列が含まれる検索要求を受信することを特徴とする請求項１２に記載のデータ保管装置。
【請求項１４】
前記インデックス管理部は、
前記保管要求に含まれるユーザ情報に、導出したインデックス値と、前記保管要求に含まれる前記タグデータとを対応付けて保管し、
前記検索要求受信部により前記検索要求が受信された場合に、
前記検索要求に含まれるユーザ情報と合致するユーザ情報と対応付けられている許可ビット復号鍵を用いて、前記検索要求に含まれる前記暗号化されたビット列内の許可ビット位置の暗号化ビットを復号し、復号により得られる前記許可ビット位置のビット値からインデックス値を導出し、前記検索要求に含まれるユーザ情報と合致するユーザ情報と対応付けられているタグデータの中から、導出したインデックス値と同じインデックス値と対応付けられているタグデータを抽出することを特徴とする請求項１２又は１３に記載のデータ保管装置。
【手続補正書】
【提出日】平成25年7月11日(2013.7.11)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
検索クエリ生成部３０６は、ユーザ秘密鍵管理部３０５が記憶したユーザ秘密鍵と公開パラメータを用いて、ユーザから指定された検索したいキーワードを暗号化してトラップドアを生成し、更に、グループ化情報生成部３１０により生成されたグループ化情報とトラップドアを結合して検索クエリを生成し、データセンタ装置４０１に送付する。
このように、検索クエリ生成部３０６は、ユーザの指示に従って、データセンタ装置４０１に暗号化データの検索を行わせるキーワード（検索キーワード）を指定しており、キーワード指定部の例に相当する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正の内容】
【００５９】
センタ側データ送受信部４０２は、アクセス端末装置３０１からグループ判定鍵を受信する。
また、センタ側データ送受信部４０２は、アクセス端末装置３０１からタグ付き暗号化データを受信する。
また、センタ側データ送受信部４０２は、アクセス端末装置３０１から検索クエリを受信し、その応答として暗号化データを送信する。
また、センタ側データ送受信部４０２は、鍵管理サーバ装置２０１から公開パラメータを受信する。
センタ側データ送受信部４０２は、保管要求受信部及び検索要求受信部の例に相当する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０２４７
【補正方法】変更
【補正の内容】
【０２４７】
また、本実施の形態では、
グループ化ビット列生成部２３０１は、
保管キーワードのハッシュ値から、インデックス情報のノードの最大階層数と同数であるＬビットのビット列を抽出するとともに、ハッシュ値の他のビット又はハッシュ値全体をキーワード情報とし、
更に、暗号化タグ生成部３０３は、Ｌビットのビット列及びキーワード情報を暗号化し、暗号化したＬビットのビット列及びキーワード情報を暗号化タグとし、暗号化タグをデータセンタ装置４０１に送信することを説明した。
換言すると、グループ化ビット列生成部２３０１は、
保管キーワードから一意に得られる乱数値のビット列から、許可ビット位置として指定できる最大数と同数のビット数の保管インデックス導出ビット列を生成し、更に、乱数値のビット列の他のビット又は乱数値のビット列全体をキーワード情報とし、
暗号化タグ生成部３０３は、
保管インデックス導出ビット列及びキーワード情報を暗号化し、暗号化した保管インデックス導出ビット列及びキーワード情報をタグデータとし、タグデータをデータセンタ装置４０１（データ保管装置）に送信している。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０２４８
【補正方法】変更
【補正の内容】
【０２４８】
また、本実施の形態では、
グループ化ビット列生成部２３０１は、
検索キーワードのハッシュ値から、インデックス情報のノードの最大階層数と同数であるＬビットのビット列を抽出するとともに、ハッシュ値の他のビット又はハッシュ値全体をキーワード情報とし、
更に、暗号化タグ生成部３０３は、Ｌビットのビット列及びキーワード情報を暗号化し、暗号化したＬビットのビット列及びキーワード情報をトラップドアとし、トラップドアをデータセンタ装置４０１に送信することを説明した。
換言すると、グループ化ビット列生成部２３０１は、
検索キーワードから一意に得られる乱数値のビット列から、許可ビット位置として指定できる最大数と同数のビット数の検索インデックス導出ビット列を生成し、更に、乱数値のビット列の他のビット又は乱数値のビット列全体をキーワード情報とし、
暗号化タグ生成部３０３は、
検索インデックス導出ビット列及びキーワード情報を暗号化し、暗号化した検索インデックス導出ビット列及びキーワード情報を暗号化した検索キーワードとし、暗号化した検索キーワードをデータセンタ装置４０１（データ保管装置）に送信している。
【国際調査報告】
2012095973.tif 000038
2012095973.tif 000039
2012095973.tif 000040
2012095973.tif 000041