(57)【特許請求の範囲】
【請求項１】
平文と、前記平文を参照する権限を有する利用者の複数の属性を識別する複数の属性値を示す属性情報と、検索クエリを生成するためのユーザ鍵の生成時に使用される鍵と同じ登録鍵と、を受け付ける受付部と、
前記属性情報に含まれる複数の属性値を集約することによって、それぞれに１つ以上の属性値で構成される１つ以上の集約値を示す集約情報を生成する集約情報生成部と、
前記集約情報に含まれる各集約値に対して集約値の中のゼロ個以上の属性値を代替するゼロ個以上のワイルドカードと集約値の中の残りの属性値とで構成される汎化値を複数生成し、前記集約情報に含まれる各集約値に対する複数の汎化値を示す汎化情報を生成する汎化情報生成部と、
前記平文と前記属性情報と前記汎化情報と前記登録鍵とを用いて、暗号化された前記平文を含んだ暗号文データを生成する暗号文データ生成部と、
前記平文に関するキーワードと前記属性情報と前記汎化情報と前記登録鍵とを用いて、暗号化された前記キーワードを含んだ暗号化タグを生成する暗号化タグ生成部と、
前記暗号文データと前記暗号化タグとの組をデータベースに登録する登録部と、
を備える登録装置。
【請求項２】
検索キーワードとユーザ鍵とを受け付ける受付部と、
前記検索キーワードと前記ユーザ鍵に含まれるユーザタグ鍵とを用いて検索クエリを生成する生成部と、
を備え、
前記ユーザタグ鍵は、利用者の複数の属性を識別する複数の属性値に基づく複数のフラグ値と、前記複数の属性値を集約することによって生成される１つ以上の集約値に基づく１つ以上のタグ属性鍵と、を有し、
前記生成部は、
前記ユーザタグ鍵に含まれる前記複数のフラグ値を集約することによって、それぞれに１つ以上のフラグ値で構成される１つ以上の集約値を示す検索用の集約フラグを生成し、
データベースに暗号文データと共に登録される暗号化タグに含まれる複数の属性要素のうち検索時に使用される１つ以上の属性要素を特定する検索位置情報を、前記検索用の集約フラグを用いて生成し、
前記検索キーワードと前記ユーザタグ鍵に含まれる前記１つ以上のタグ属性鍵と前記検索位置情報とを用いて前記検索クエリを生成する
検索操作装置。
【請求項３】
前記検索操作装置は、
前記検索クエリを送信し、前記検索クエリに合致する暗号文データを含んだ暗号化検索結果を受信する要求部と、
前記ユーザ鍵に含まれるユーザデータ鍵を用いて、前記暗号化検索結果に含まれる前記暗号文データから平文を復号する復号部と、
を備え、
前記ユーザデータ鍵は、前記複数の属性値に基づく複数のフラグ値と、前記複数の属性値を集約することによって生成される１つ以上の集約値に基づく１つ以上のデータ属性鍵と、を有し、
前記復号部は、
前記ユーザデータ鍵に含まれる前記複数のフラグ値を集約することによって、それぞれに１つ以上のフラグ値で構成される１つ以上の集約値を示す復号用の集約フラグを生成し、
前記暗号化検索結果の中の前記暗号文データに含まれる複数の属性要素のうち復号時に使用される１つ以上の属性要素を特定する復号位置情報を、前記復号用の集約フラグを用いて生成し、
前記ユーザデータ鍵に含まれる前記１つ以上のデータ属性鍵と前記復号位置情報とを用いて、前記暗号化検索結果に含まれる前記暗号文データから前記平文を復号する
請求項２に記載の検索操作装置。
【請求項４】
暗号文データと複数の属性要素を有する暗号化タグとの組が複数登録されるデータベースを管理するデータ管理装置であって、
暗号化キーワードと検索位置情報とを有する検索クエリを受信する受付部と、
前記検索クエリを各暗号化タグと照合する照合部と、
前記検索クエリに合致する暗号化タグに対応する暗号文データを含んだ暗号化検索結果を送信する出力部と、
を備え、
前記検索位置情報は、各暗号化タグに含まれる複数の属性要素のうち検索時に使用される１つ以上の属性要素を特定する情報であり、
前記照合部は、前記検索位置情報によって特定される１つ以上の属性要素を各暗号化タグから選択し、各暗号化タグから選択された１つ以上の属性要素と前記検索クエリに含まれる前記暗号化キーワードとを用いて前記検索クエリを各暗号化タグと照合する
データ管理装置。
【請求項５】
平文と、前記平文を参照する権限を有する利用者の複数の属性を識別する複数の属性値を示す属性情報と、検索クエリを生成するためのユーザ鍵の生成時に使用される鍵と同じ登録鍵と、を受け付ける受付処理と、
前記属性情報に含まれる複数の属性値を集約することによって、それぞれに１つ以上の属性値で構成される１つ以上の集約値を示す集約情報を生成する集約情報生成処理と、
前記集約情報に含まれる各集約値に対して集約値の中のゼロ個以上の属性値を代替するゼロ個以上のワイルドカードと集約値の中の残りの属性値とで構成される汎化値を複数生成し、前記集約情報に含まれる各集約値に対する複数の汎化値を示す汎化情報を生成する汎化情報生成処理と、
前記平文と前記属性情報と前記汎化情報と前記登録鍵とを用いて、暗号化された前記平文を含んだ暗号文データを生成する暗号文データ生成処理と、
前記平文に関するキーワードと前記属性情報と前記汎化情報と前記登録鍵とを用いて、暗号化された前記キーワードを含んだ暗号化タグを生成する暗号化タグ生成処理と、
前記暗号文データと前記暗号化タグとの組をデータベースに登録する登録処理と、
をコンピュータに実行させるための登録プログラム。
【請求項６】
検索キーワードとユーザ鍵とを受け付ける受付処理と、
前記検索キーワードと前記ユーザ鍵に含まれるユーザタグ鍵とを用いて検索クエリを生成する生成処理と、
をコンピュータに実行させるための検索操作プログラムであって、
前記ユーザタグ鍵は、利用者の複数の属性を識別する複数の属性値に基づく複数のフラグ値と、前記複数の属性値を集約することによって生成される１つ以上の集約値に基づく１つ以上のタグ属性鍵と、を有し、
前記生成処理は、
前記ユーザタグ鍵に含まれる前記複数のフラグ値を集約することによって、それぞれに１つ以上のフラグ値で構成される１つ以上の集約値を示す検索用の集約フラグを生成し、
データベースに暗号文データと共に登録される暗号化タグに含まれる複数の属性要素のうち検索時に使用される１つ以上の属性要素を特定する検索位置情報を、前記検索用の集約フラグを用いて生成し、
前記検索キーワードと前記ユーザタグ鍵に含まれる前記１つ以上のタグ属性鍵と前記検索位置情報とを用いて前記検索クエリを生成する
検索操作プログラム。
【請求項７】
前記検索操作プログラムは、
前記検索クエリを送信し、前記検索クエリに合致する暗号文データを含んだ暗号化検索結果を受信する要求処理と、
前記ユーザ鍵に含まれるユーザデータ鍵を用いて、前記暗号化検索結果に含まれる前記暗号文データから平文を復号する復号処理と、
をコンピュータに実行させるためのプログラムであり、
前記ユーザデータ鍵は、前記複数の属性値に基づく複数のフラグ値と、前記複数の属性値を集約することによって生成される１つ以上の集約値に基づく１つ以上のデータ属性鍵と、を有し、
前記復号処理は、
前記ユーザデータ鍵に含まれる前記複数のフラグ値を集約することによって、それぞれに１つ以上のフラグ値で構成される１つ以上の集約値を示す復号用の集約フラグを生成し、
前記暗号化検索結果の中の前記暗号文データに含まれる複数の属性要素のうち復号時に使用される１つ以上の属性要素を特定する復号位置情報を、前記復号用の集約フラグを用いて生成し、
前記ユーザデータ鍵に含まれる前記１つ以上のデータ属性鍵と前記復号位置情報とを用いて、前記暗号化検索結果に含まれる前記暗号文データから前記平文を復号する
請求項６に記載の検索操作プログラム。
【請求項８】
暗号文データと複数の属性要素を有する暗号化タグとの組が複数登録されるデータベースを管理するために、
暗号化キーワードと検索位置情報とを有する検索クエリを受信する受付処理と、
前記検索クエリを各暗号化タグと照合する照合処理と、
前記検索クエリに合致する暗号化タグに対応する暗号文データを含んだ暗号化検索結果を送信する出力処理と、
をコンピュータに実行させるためのデータ管理プログラムであって、
前記検索位置情報は、各暗号化タグに含まれる複数の属性要素のうち検索時に使用される１つ以上の属性要素を特定する情報であり、
前記照合処理は、前記検索位置情報によって特定される１つ以上の属性要素を各暗号化タグから選択し、各暗号化タグから選択された１つ以上の属性要素と前記検索クエリに含まれる前記暗号化キーワードとを用いて前記検索クエリを各暗号化タグと照合する
データ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、秘匿検索技術に関するものである。
【背景技術】
【０００２】
秘匿検索とは、暗号化データを暗号化したまま検索する技術である。
つまり、秘匿検索は、暗号化データを復号せずに検索する技術である。【０００３】
近年、秘匿検索は、クラウドサービスにおいてサーバ管理者による盗聴から機密情報を守るためのセキュリティ技術として注目されている。
つまり、秘匿検索は、インターネットにおいてデータを管理するためのセキュリティ技術として注目されている。【０００４】
秘匿検索方式として、共通鍵方式と公開鍵方式との２種類が存在する。
共通鍵方式では、共通暗号鍵技術が利用され、登録者および検索者が限定される。
公開鍵方式では、公開鍵暗号技術が利用され、検索者は限定されるが登録者は限定されない。【０００５】
特許文献１は、マルチユーザ型の共通鍵方式を開示している。
マルチユーザ型の共通鍵方式において、登録者は、各検索者の秘密鍵を使ってデータを暗号化する。登録される暗号化データには暗号化タグが付加される。暗号化タグには、キーワードと検索権限とを埋め込むことができる。
例えば、検索者Ａのみが検索できるという権限が暗号化タグに埋め込まれる。また、検索者Ｂが、自身の秘密鍵と検索キーワードとを使って検索クエリを生成する。この場合、検索者Ｂには検索権限がないため、検索者Ｂの検索クエリの中の検索キーワードが暗号化タグの中のキーワードと同じであっても、暗号化データが検索結果として得られない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】国際公開第２０１９／１４２６５１号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
マルチユーザ型の共通鍵方式には、複数の正規ユーザによる結託攻撃に対する脆弱性という課題がある。
例えば、正規ユーザＸと正規ユーザＹが結託すれば、正規ユーザＸの秘密鍵ＳＫ＿Ｘと正規ユーザＹのＳＫ＿Ｙとの両方を使用することができる。その場合、正規ユーザＸまたは正規ユーザＹが単独では検索できないはずの暗号化データを検索することが可能な秘密鍵を生成することが可能となる。具体的には、総務課の課長と人事課の担当者が結託することによって、人事課の課長の秘密鍵が生成される可能性がある。【０００８】
本開示は、マルチユーザ型の共通鍵方式の安全性を向上できるようにすることを目的とする。
【課題を解決するための手段】
【０００９】
本開示の登録装置は、
平文と、前記平文を参照する権限を有する利用者の複数の属性を識別する複数の属性値を示す属性情報と、検索クエリを生成するためのユーザ鍵の生成時に使用される鍵と同じ登録鍵と、を受け付ける受付部と、
前記属性情報に含まれる複数の属性値を集約することによって、それぞれに１つ以上の属性値で構成される１つ以上の集約値を示す集約情報を生成する集約情報生成部と、
前記集約情報に含まれる各集約値に対して集約値の中のゼロ個以上の属性値を代替するゼロ個以上のワイルドカードと集約値の中の残りの属性値とで構成される汎化値を複数生成し、前記集約情報に含まれる各集約値に対する複数の汎化値を示す汎化情報を生成する汎化情報生成部と、
前記平文と前記属性情報と前記汎化情報と前記登録鍵とを用いて、暗号化された前記平文を含んだ暗号文データを生成する暗号文データ生成部と、
前記平文に関するキーワードと前記属性情報と前記汎化情報と前記登録鍵とを用いて、暗号化された前記キーワードを含んだ暗号化タグを生成する暗号化タグ生成部と、
前記暗号文データと前記暗号化タグとの組をデータベースに登録する登録部と、を備える。
【発明の効果】
【００１０】
本開示によれば、平文を参照する権限を有する利用者の複数の属性値が集約され１つ以上の集約値に基づいて暗号文データおよび暗号化タグが生成される。
これにより、複数の正規ユーザによる結託攻撃に対する耐性を向上できる。つまり、マルチユーザ型の共通鍵方式の安全性を向上できる。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１における秘匿検索システム１００の構成図。
【図２】実施の形態１におけるマスター鍵装置２００の構成図。
【図３】実施の形態１における登録鍵装置３００の構成図。
【図４】実施の形態１におけるユーザ鍵装置４００の構成図。
【図５】実施の形態１における登録装置５００の構成図。
【図６】実施の形態１における検索操作装置６００の構成図。
【図７】実施の形態１におけるデータ管理装置７００の構成図。
【図８】実施の形態１における秘匿検索方法のフローチャート。
【図９】実施の形態１におけるマスター鍵生成（Ｓ１２０）のフローチャート。
【図１０】実施の形態１における登録鍵生成（Ｓ１３０）のフローチャート。
【図１１】実施の形態１におけるユーザ鍵生成（Ｓ１４０）のフローチャート。
【図１２】実施の形態１における属性情報の一例を示す図。
【図１３】実施の形態１における集約情報の一例を示す図。
【図１４】実施の形態１におけるデータ登録（Ｓ１５０）のフローチャート。
【図１５】実施の形態１における登録データベース７９１を示す図。
【図１６】実施の形態１における検索操作（Ｓ１６０）のフローチャート。
【図１７】実施の形態１におけるステップＳ１７３のフローチャート。
【図１８】実施の形態１におけるステップＳ１７６のフローチャート。
【図１９】実施の形態１におけるデータ検索（Ｓ１７０）のフローチャート。
【図２０】実施の形態１におけるデータ削除（Ｓ１８０）のフローチャート。
【図２１】実施の形態１におけるマスター鍵装置２００のハードウェア構成図。
【図２２】実施の形態１における登録鍵装置３００のハードウェア構成図。
【図２３】実施の形態１におけるユーザ鍵装置４００のハードウェア構成図。
【図２４】実施の形態１における登録装置５００のハードウェア構成図。
【図２５】実施の形態１における検索操作装置６００のハードウェア構成図。
【図２６】実施の形態１におけるデータ管理装置７００のハードウェア構成図。
【発明を実施するための形態】
【００１２】
実施の形態および図面において、同じ要素または対応する要素には同じ符号を付している。説明した要素と同じ符号が付された要素の説明は適宜に省略または簡略化する。図中の矢印はデータの流れ又は処理の流れを主に示している。
【００１３】
実施の形態１．
マルチユーザ型の共通鍵方式で秘匿検索を行う形態について、図１から図２６に基づいて説明する。
【００１４】
＊＊＊構成の説明＊＊＊
図１に基づいて、秘匿検索システム１００の構成を説明する。
秘匿検索システム１００は、マスター鍵装置２００と、登録鍵装置３００と、ユーザ鍵装置４００と、登録装置５００と、検索操作装置６００と、データ管理装置７００と、を備える。
秘匿検索システム１００の各装置は、ネットワーク１０１を介して互いに通信を行う。
【００１５】
図２に基づいて、マスター鍵装置２００の構成を説明する。
マスター鍵装置２００は、プロセッサ２０１とメモリ２０２と補助記憶装置２０３と入出力インタフェース２０４と通信装置２０５といったハードウェアを備えるコンピュータである。これらのハードウェアは、信号線を介して互いに接続されている。
【００１６】
プロセッサ２０１は、演算処理を行うＩＣであり、他のハードウェアを制御する。例えば、プロセッサ２０１は、ＣＰＵ、ＤＳＰまたはＧＰＵである。
ＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略称である。
ＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略称である。
ＤＳＰは、Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒの略称である。
ＧＰＵは、Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略称である。
【００１７】
メモリ２０２は揮発性または不揮発性の記憶装置である。メモリ２０２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ２０２はＲＡＭである。メモリ２０２に記憶されたデータは必要に応じて補助記憶装置２０３に保存される。
ＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略称である。
【００１８】
補助記憶装置２０３は不揮発性の記憶装置である。例えば、補助記憶装置２０３は、ＲＯＭ、ＨＤＤまたはフラッシュメモリである。補助記憶装置２０３に記憶されたデータは必要に応じてメモリ２０２にロードされる。
ＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略称である。
ＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略称である。
【００１９】
入出力インタフェース２０４は、入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース２０４はＵＳＢ端子であり、入力装置はキーボードおよびマウスであり、出力装置はディスプレイである。
ＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略称である。
【００２０】
通信装置２０５はレシーバ及びトランスミッタである。例えば、通信装置２０５は通信チップまたはＮＩＣである。
ＮＩＣは、Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄの略称である。
【００２１】
マスター鍵装置２００は、受付部２１０と生成部２２０と出力部２３０といった要素を備える。これらの要素はソフトウェアで実現される。
【００２２】
補助記憶装置２０３には、受付部２１０と生成部２２０と出力部２３０としてコンピュータを機能させるためのマスター鍵プログラムが記憶されている。マスター鍵プログラムは、メモリ２０２にロードされて、プロセッサ２０１によって実行される。
補助記憶装置２０３には、さらに、ＯＳが記憶されている。ＯＳの少なくとも一部は、メモリ２０２にロードされて、プロセッサ２０１によって実行される。
プロセッサ２０１は、ＯＳを実行しながら、マスター鍵プログラムを実行する。
ＯＳは、Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍの略称である。
【００２３】
マスター鍵プログラムの入出力データは記憶部２９０に記憶される。
補助記憶装置２０３は記憶部２９０として機能する。但し、メモリ２０２、プロセッサ２０１内のレジスタおよびプロセッサ２０１内のキャッシュメモリなどの記憶装置が、補助記憶装置２０３の代わりに、又は、補助記憶装置２０３と共に、記憶部２９０として機能してもよい。
【００２４】
マスター鍵装置２００は、プロセッサ２０１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ２０１の機能を分担する。
【００２５】
マスター鍵プログラムは、光ディスクまたはフラッシュメモリ等の不揮発性の記録媒体にコンピュータ読み取り可能に記録（格納）することができる。
【００２６】
図３に基づいて、登録鍵装置３００の構成を説明する。
登録鍵装置３００は、プロセッサ３０１とメモリ３０２と補助記憶装置３０３と入出力インタフェース３０４と通信装置３０５といったハードウェアを備えるコンピュータである。これらのハードウェアは、信号線を介して互いに接続されている。
【００２７】
プロセッサ３０１は、演算処理を行うＩＣであり、他のハードウェアを制御する。例えば、プロセッサ３０１はＣＰＵ、ＤＳＰまたはＧＰＵである。
メモリ３０２は揮発性または不揮発性の記憶装置である。メモリ３０２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ３０２はＲＡＭである。メモリ３０２に記憶されたデータは必要に応じて補助記憶装置３０３に保存される。
補助記憶装置３０３は不揮発性の記憶装置である。例えば、補助記憶装置３０３は、ＲＯＭ、ＨＤＤまたはフラッシュメモリである。補助記憶装置３０３に記憶されたデータは必要に応じてメモリ３０２にロードされる。
入出力インタフェース３０４は、入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース３０４はＵＳＢ端子であり、入力装置はキーボードおよびマウスであり、出力装置はディスプレイである。
通信装置３０５はレシーバ及びトランスミッタである。例えば、通信装置３０５は通信チップまたはＮＩＣである。
【００２８】
登録鍵装置３００は、受付部３１０と生成部３２０と出力部３３０といった要素を備える。これらの要素はソフトウェアで実現される。
【００２９】
補助記憶装置３０３には、受付部３１０と生成部３２０と出力部３３０としてコンピュータを機能させるための登録鍵プログラムが記憶されている。登録鍵プログラムは、メモリ３０２にロードされて、プロセッサ３０１によって実行される。
補助記憶装置３０３には、さらに、ＯＳが記憶されている。ＯＳの少なくとも一部は、メモリ３０２にロードされて、プロセッサ３０１によって実行される。
プロセッサ３０１は、ＯＳを実行しながら、登録鍵プログラムを実行する。
【００３０】
登録鍵プログラムの入出力データは記憶部３９０に記憶される。
補助記憶装置３０３は記憶部３９０として機能する。但し、メモリ３０２、プロセッサ３０１内のレジスタおよびプロセッサ３０１内のキャッシュメモリなどの記憶装置が、補助記憶装置３０３の代わりに、又は、補助記憶装置３０３と共に、記憶部３９０として機能してもよい。
【００３１】
登録鍵装置３００は、プロセッサ３０１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ３０１の機能を分担する。
【００３２】
登録鍵プログラムは、光ディスクまたはフラッシュメモリ等の不揮発性の記録媒体にコンピュータ読み取り可能に記録（格納）することができる。
【００３３】
図４に基づいて、ユーザ鍵装置４００の構成を説明する。
ユーザ鍵装置４００は、プロセッサ４０１とメモリ４０２と補助記憶装置４０３と入出力インタフェース４０４と通信装置４０５といったハードウェアを備えるコンピュータである。これらのハードウェアは、信号線を介して互いに接続されている。
【００３４】
プロセッサ４０１は、演算処理を行うＩＣであり、他のハードウェアを制御する。例えば、プロセッサ４０１はＣＰＵ、ＤＳＰまたはＧＰＵである。
メモリ４０２は揮発性または不揮発性の記憶装置である。メモリ４０２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ４０２はＲＡＭである。メモリ４０２に記憶されたデータは必要に応じて補助記憶装置４０３に保存される。
補助記憶装置４０３は不揮発性の記憶装置である。例えば、補助記憶装置４０３は、ＲＯＭ、ＨＤＤまたはフラッシュメモリである。補助記憶装置４０３に記憶されたデータは必要に応じてメモリ４０２にロードされる。
入出力インタフェース４０４は、入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース４０４はＵＳＢ端子であり、入力装置はキーボードおよびマウスであり、出力装置はディスプレイである。
通信装置４０５はレシーバ及びトランスミッタである。例えば、通信装置４０５は通信チップまたはＮＩＣである。
【００３５】
ユーザ鍵装置４００は、受付部４１０と生成部４２０と出力部４３０といった要素を備える。
生成部４２０は、集約情報生成部４２１とユーザ鍵生成部４２２といった要素を備える。
これらの要素はソフトウェアで実現される。
【００３６】
補助記憶装置４０３には、受付部４１０と生成部４２０と出力部４３０としてコンピュータを機能させるためのユーザ鍵プログラムが記憶されている。ユーザ鍵プログラムは、メモリ４０２にロードされて、プロセッサ４０１によって実行される。
補助記憶装置４０３には、さらに、ＯＳが記憶されている。ＯＳの少なくとも一部は、メモリ４０２にロードされて、プロセッサ４０１によって実行される。
プロセッサ４０１は、ＯＳを実行しながら、ユーザ鍵プログラムを実行する。
【００３７】
ユーザ鍵プログラムの入出力データは記憶部４９０に記憶される。
補助記憶装置４０３は記憶部４９０として機能する。但し、メモリ４０２、プロセッサ４０１内のレジスタおよびプロセッサ４０１内のキャッシュメモリなどの記憶装置が、メモリ４０２の代わりに、又は、メモリ４０２と共に、記憶部４９０として機能してもよい。
【００３８】
ユーザ鍵装置４００は、プロセッサ４０１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ４０１の機能を分担する。
【００３９】
ユーザ鍵プログラムは、光ディスクまたはフラッシュメモリ等の不揮発性の記録媒体にコンピュータ読み取り可能に記録（格納）することができる。
【００４０】
図５に基づいて、登録装置５００の構成を説明する。
登録装置５００は、プロセッサ５０１とメモリ５０２と補助記憶装置５０３と入出力インタフェース５０４と通信装置５０５といったハードウェアを備えるコンピュータである。これらのハードウェアは、信号線を介して互いに接続されている。
【００４１】
プロセッサ５０１は、演算処理を行うＩＣであり、他のハードウェアを制御する。例えば、プロセッサ５０１はＣＰＵ、ＤＳＰまたはＧＰＵである。
メモリ５０２は揮発性または不揮発性の記憶装置である。メモリ５０２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ５０２はＲＡＭである。メモリ５０２に記憶されたデータは必要に応じて補助記憶装置５０３に保存される。
補助記憶装置５０３は不揮発性の記憶装置である。例えば、補助記憶装置５０３は、ＲＯＭ、ＨＤＤまたはフラッシュメモリである。補助記憶装置５０３に記憶されたデータは必要に応じてメモリ５０２にロードされる。
入出力インタフェース５０４は、入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース５０４はＵＳＢ端子であり、入力装置はキーボードおよびマウスであり、出力装置はディスプレイである。
通信装置５０５はレシーバ及びトランスミッタである。例えば、通信装置５０５は通信チップまたはＮＩＣである。
【００４２】
登録装置５００は、受付部５１０と生成部５２０と登録部５３０といった要素を備える。
生成部５２０は、乱数生成部５２１と集約情報生成部５２２と汎化情報生成部５２３と暗号文データ生成部５２４とキーワード生成部５２５と暗号化タグ生成部５２６といった要素を備える。
これらの要素はソフトウェアで実現される。
【００４３】
補助記憶装置５０３には、受付部５１０と生成部５２０と登録部５３０としてコンピュータを機能させるための登録プログラムが記憶されている。登録プログラムは、メモリ５０２にロードされて、プロセッサ５０１によって実行される。
補助記憶装置５０３には、さらに、ＯＳが記憶されている。ＯＳの少なくとも一部は、メモリ５０２にロードされて、プロセッサ５０１によって実行される。
プロセッサ５０１は、ＯＳを実行しながら、登録プログラムを実行する。
【００４４】
登録プログラムの入出力データは記憶部５９０に記憶される。
補助記憶装置５０３は記憶部５９０として機能する。但し、メモリ５０２、プロセッサ５０１内のレジスタおよびプロセッサ５０１内のキャッシュメモリなどの記憶装置が、メモリ５０２の代わりに、又は、メモリ５０２と共に、記憶部５９０として機能してもよい。
【００４５】
登録装置５００は、プロセッサ５０１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ５０１の機能を分担する。
【００４６】
登録プログラムは、光ディスクまたはフラッシュメモリ等の不揮発性の記録媒体にコンピュータ読み取り可能に記録（格納）することができる。
【００４７】
図６に基づいて、検索操作装置６００の構成を説明する。
検索操作装置６００は、プロセッサ６０１とメモリ６０２と補助記憶装置６０３と入出力インタフェース６０４と通信装置６０５といったハードウェアを備えるコンピュータである。これらのハードウェアは、信号線を介して互いに接続されている。
【００４８】
プロセッサ６０１は、演算処理を行うＩＣであり、他のハードウェアを制御する。例えば、プロセッサ６０１はＣＰＵ、ＤＳＰまたはＧＰＵである。
メモリ６０２は揮発性または不揮発性の記憶装置である。メモリ６０２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ６０２はＲＡＭである。メモリ６０２に記憶されたデータは必要に応じて補助記憶装置６０３に保存される。
補助記憶装置６０３は不揮発性の記憶装置である。例えば、補助記憶装置６０３は、ＲＯＭ、ＨＤＤまたはフラッシュメモリである。補助記憶装置６０３に記憶されたデータは必要に応じてメモリ６０２にロードされる。
入出力インタフェース６０４は、入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース６０４はＵＳＢ端子であり、入力装置はキーボードおよびマウスであり、出力装置はディスプレイである。
通信装置６０５はレシーバ及びトランスミッタである。例えば、通信装置６０５は通信チップまたはＮＩＣである。
【００４９】
検索操作装置６００は、受付部６１０と生成部６２０と要求部６３０と復号部６４０と出力部６５０といった要素を備える。
生成部６２０は、集約フラグ生成部６２１と位置情報生成部６２２と検索クエリ生成部６２３といった要素を備える。
復号部６４０は、集約フラグ生成部６４１と位置情報生成部６４２と検索結果復号部６４３といった要素を備える。
これらの要素はソフトウェアで実現される。
【００５０】
補助記憶装置６０３には、受付部６１０と生成部６２０と要求部６３０と復号部６４０と出力部６５０としてコンピュータを機能させるための検索操作プログラムが記憶されている。検索操作プログラムは、メモリ６０２にロードされて、プロセッサ６０１によって実行される。
補助記憶装置６０３には、さらに、ＯＳが記憶されている。ＯＳの少なくとも一部は、メモリ６０２にロードされて、プロセッサ６０１によって実行される。
プロセッサ６０１は、ＯＳを実行しながら、検索操作プログラムを実行する。
【００５１】
検索操作プログラムの入出力データは記憶部６９０に記憶される。
補助記憶装置６０３は記憶部６９０として機能する。但し、メモリ６０２、プロセッサ６０１内のレジスタおよびプロセッサ６０１内のキャッシュメモリなどの記憶装置が、補助記憶装置６０３の代わりに、又は、補助記憶装置６０３と共に、記憶部６９０として機能してもよい。
【００５２】
検索操作装置６００は、プロセッサ６０１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ６０１の機能を分担する。
【００５３】
検索操作プログラムは、光ディスクまたはフラッシュメモリ等の不揮発性の記録媒体にコンピュータ読み取り可能に記録（格納）することができる。
【００５４】
図７に基づいて、データ管理装置７００の構成を説明する。
データ管理装置７００は、プロセッサ７０１とメモリ７０２と補助記憶装置７０３と入出力インタフェース７０４と通信装置７０５といったハードウェアを備えるコンピュータである。これらのハードウェアは、信号線を介して互いに接続されている。
【００５５】
プロセッサ７０１は、演算処理を行うＩＣであり、他のハードウェアを制御する。例えば、プロセッサ７０１はＣＰＵ、ＤＳＰまたはＧＰＵである。
メモリ７０２は揮発性または不揮発性の記憶装置である。メモリ７０２は、主記憶装置またはメインメモリとも呼ばれる。例えば、メモリ７０２はＲＡＭである。メモリ７０２に記憶されたデータは必要に応じて補助記憶装置７０３に保存される。
補助記憶装置７０３は不揮発性の記憶装置である。例えば、補助記憶装置７０３は、ＲＯＭ、ＨＤＤまたはフラッシュメモリである。補助記憶装置７０３に記憶されたデータは必要に応じてメモリ７０２にロードされる。
入出力インタフェース７０４は、入力装置および出力装置が接続されるポートである。例えば、入出力インタフェース７０４はＵＳＢ端子であり、入力装置はキーボードおよびマウスであり、出力装置はディスプレイである。
通信装置７０５はレシーバ及びトランスミッタである。例えば、通信装置７０５？は通信チップまたはＮＩＣである。
【００５６】
データ管理装置７００は、受付部７１０と検索部７２０と出力部７３０と管理部７４０といった要素を備える。
検索部７２０は、照合部７２１と抽出部７２２といった要素を備える。
これらの要素はソフトウェアで実現される。
【００５７】
補助記憶装置７０３には、受付部７１０と検索部７２０と出力部７３０としてコンピュータを機能させるためのデータ管理プログラムが記憶されている。データ管理プログラムは、メモリ７０２にロードされて、プロセッサ７０１によって実行される。
補助記憶装置７０３には、さらに、ＯＳが記憶されている。ＯＳの少なくとも一部は、メモリ７０２にロードされて、プロセッサ７０１によって実行される。
プロセッサ７０１は、ＯＳを実行しながら、データ管理プログラムを実行する。
【００５８】
データ管理プログラムの入出力データは記憶部７９０に記憶される。
補助記憶装置７０３は記憶部７９０として機能する。但し、メモリ７０２、プロセッサ７０１内のレジスタおよびプロセッサ７０１内のキャッシュメモリなどの記憶装置が、補助記憶装置７０３の代わりに、又は、補助記憶装置７０３と共に、記憶部７９０として機能してもよい。
【００５９】
データ管理装置７００は、プロセッサ７０１を代替する複数のプロセッサを備えてもよい。複数のプロセッサは、プロセッサ７０１の機能を分担する。
【００６０】
データ管理プログラムは、光ディスクまたはフラッシュメモリ等の不揮発性の記録媒体にコンピュータ読み取り可能に記録（格納）することができる。
【００６１】
＊＊＊動作の説明＊＊＊
秘匿検索システム１００の動作の手順は秘匿検索方法に相当する。
【００６２】
図８に基づいて、秘匿検索方法の概要を説明する。
ステップＳ１０１において、マスター鍵装置２００はマスター鍵ＭＫを生成する。
【００６３】
ステップＳ１０２において、登録鍵装置３００はマスター鍵ＭＫを用いて登録鍵ＥＫを生成する。
【００６４】
ステップＳ１０３において、ユーザ鍵装置４００は登録鍵ＥＫを用いてユーザ鍵ＵＫを生成する。
【００６５】
ステップＳ１１１において、登録装置５００は、登録鍵ＥＫを用いて暗号文データＣと暗号化タグＣＴとの組を生成し、生成した組をデータベースに登録する。
暗号文データＣは、平文Ｍを暗号化することによって生成される。
暗号化タグＣＴは、暗号文データＣを検索するためのキーワードを暗号化することによって生成される。暗号化タグＣＴからキーワードが漏洩することはない。
データベースには、暗号文データＣと暗号化タグＣＴとの組が複数登録される。
【００６６】
ステップＳ１１２において、検索操作装置６００はユーザ鍵ＵＫを用いて検索クエリＳＱを生成する。
検索クエリＳＱは、ユーザ鍵ＵＫを用いて、指定されたキーワードをランダム化することによって生成される。
【００６７】
ステップＳ１１３において、検索操作装置６００は、検索クエリＳＱをデータ管理装置７００へ送信することによって検索を要求する。
データ管理装置７００は、検索クエリＳＱを受信し、検索クエリＳＱに合致する暗号化タグＣＴを特殊な演算によって検索する。
特殊な演算において、各暗号化タグＣＴが復号されずに、検索クエリＳＱのキーワードが各暗号化タグＣＴのキーワードと比較される。
【００６８】
ステップＳ１１４において、データ管理装置７００は、検索クエリＳＱに合致する暗号化タグＣＴに対応する暗号文データＣを検索操作装置６００へ送信することによって、検索結果を応答する。
検索操作装置６００は、暗号文データＣを受信し、ユーザ鍵ＵＫを用いて暗号文データＣから平文Ｍを復号する。
【００６９】
図９に基づいて、マスター鍵生成（Ｓ１２０）を説明する。
マスター鍵生成（Ｓ１２０）は、マスター鍵装置２００によって実行される処理である。
【００７０】
ステップＳ１２１において、受付部２１０は鍵長ＢＩＴを受け付ける。
例えば、受付部２１０は、マスター鍵装置２００に入力される鍵長ＢＩＴを入出力インタフェース２０４を介して受け付ける。受付部２１０は、マスター鍵装置２００において実行されるアプリケーションプログラムから、鍵長ＢＩＴを受け付けてもよい。
【００７１】
鍵長ＢＩＴは、マスター鍵ＭＫのビット長さである。
【００７２】
ステップＳ１２２において、生成部２２０はマスター鍵ＭＫを生成する。
具体的には、生成部２２０は、鍵長ＢＩＴと同じ長さを有するランダムなビット列を生成する。生成されるビット列がマスター鍵ＭＫである。
例えば、鍵長ＢＩＴが２５６ビットである場合、生成部２２０は、２５６ビットのランダムなビット列を生成する。これにより、２５６ビットのマスター鍵ＭＫが得られる。
【００７３】
ステップＳ１２３において、生成部２２０はマスター鍵ＭＫを記憶部２９０に記憶する。これにより、マスター鍵ＭＫが記憶部２９０に保管される。
【００７４】
ステップＳ１２４において、出力部２３０はマスター鍵ＭＫを出力する。
例えば、出力部２３０は、通信装置２０５を用いて、マスター鍵ＭＫを登録鍵装置３００へ送信する。
【００７５】
図１０に基づいて、登録鍵生成（Ｓ１３０）を説明する。
登録鍵生成（Ｓ１３０）は、登録鍵装置３００によって実行される処理である。
【００７６】
ステップＳ１３１において、受付部３１０はマスター鍵ＭＫを受け付ける。
例えば、受付部３１０は、通信装置３０５を用いて、マスター鍵装置２００からマスター鍵ＭＫを受信する。受付部３１０は、登録鍵装置３００に入力されるマスター鍵ＭＫを入出力インタフェース３０４を介して受け付けてもよい。
【００７７】
ステップＳ１３２において、生成部３２０は、マスター鍵ＭＫを用いて、データ鍵ＤＫとタグ鍵ＴＫとを生成する。
【００７８】
具体的には、生成部３２０は、マスター鍵ＭＫを入力として関数Ｆ＿１を実行することによって、２つの乱数を生成する。各乱数はランダムなビット列である。
関数Ｆ＿１の一例は、擬似ランダム関数である。
擬似ランダム関数は、暗号学的な関数であり、鍵が決まると入力値に応じて確定的に乱数を返す。
関数Ｆ＿１は、ＳＨＡ−１のような暗号学的なハッシュ関数またはＡＥＳのような共通鍵暗号方式の関数であってもよい。
【００７９】
関数Ｆ＿１によって生成される２つの乱数のうちの一方の乱数がデータ鍵ＤＫである。データ鍵ＤＫは次のように表すことができる。
ＤＫ  ＝  Ｆ＿１（ＭＫ，１）
【００８０】
関数Ｆ＿１によって生成される２つの乱数のうちの他方の乱数がタグ鍵ＴＫである。タグ鍵ＴＫは次のように表すことができる。
ＴＫ  ＝  Ｆ＿１（ＭＫ，２）
【００８１】
データ鍵ＤＫとタグ鍵ＴＫとの組を「登録鍵ＥＫ」と呼ぶ。登録鍵ＥＫは次のように表すことができる。
ＥＫ  ＝  （ＤＫ，ＴＫ）
【００８２】
ステップＳ１３３において、生成部３２０は登録鍵ＥＫを記憶部３９０に記憶する。これにより、登録鍵ＥＫが記憶部３９０に保管される。
【００８３】
ステップＳ１３４において、出力部３３０は登録鍵ＥＫを出力する。
例えば、出力部３３０は、通信装置３０５を用いて、登録鍵ＥＫをユーザ鍵装置４００と登録装置５００とのそれぞれに送信する。
【００８４】
図１１に基づいて、ユーザ鍵生成（Ｓ１４０）を説明する。
ユーザ鍵生成（Ｓ１４０）は、ユーザ鍵装置４００によって実行される処理である。
【００８５】
ステップＳ１４１において、受付部４１０は登録鍵ＥＫを受け付ける。
例えば、受付部４１０は、通信装置４０５を用いて、登録鍵装置３００から登録鍵ＥＫを受信する。受付部４１０は、ユーザ鍵装置４００に入力される登録鍵ＥＫを入出力インタフェース４０４を介して受け付けてもよい。
【００８６】
そして、受付部４１０は、登録鍵ＥＫを記憶部４９０に記憶する。これにより、登録鍵ＥＫが記憶部４９０に保管される。
【００８７】
登録鍵ＥＫが記憶部４９０に既に保管されている場合、ステップＳ１４１は不要である。
【００８８】
登録鍵ＥＫは、データ鍵ＤＫとタグ鍵ＴＫとを有する。
【００８９】
ステップＳ１４２において、受付部４１０は属性情報Ａを受け付ける。
例えば、受付部４１０は、ユーザ鍵装置４００に入力される属性情報Ａを入出力インタフェース４０４を介して受け付ける。受付部４１０は、ユーザ鍵装置４００において実行されるアプリケーションプログラムから、属性情報Ａを受け付けてもよい。
【００９０】
属性情報Ａは、検索者の属性情報である。
検索者は、検索操作装置６００の利用者であり、暗号文Ｃ′を検索する。
利用者は、階層を成す複数の属性を有する。
属性情報は、複数の属性に対応する複数の属性値を示す。
各属性値は、各層における利用者の属性を識別する。
【００９１】
図１２に基づいて、属性情報の例を説明する。
属性情報は、４つの層に対応する４つの属性値を示している。
第１層の属性（第１属性）は事業部である。
第２層の属性（第２属性）は部である。
第３層の属性（第３属性）は課である。
第４層の属性（第４属性）は氏名である。
【００９２】
１番の属性情報は、Ｎｅさんの属性情報である。Ｎｅさんは、Ｄｉ事業部のＤｅ部のＳｃ課に所属する。
２番の属性情報は、Ｎｆさんの属性情報である。Ｎｆさんは、Ｄｉ事業部のＤｅ部のＳｄ課に所属する。
３番の属性情報は、Ｓｃ課員の属性情報である。Ｓｃ課員は、Ｄｉ事業部のＤｅ部のＳｃ課に所属する。第４属性値がワイルドカード「＊」であるため、氏名は限定されない。
４番の属性情報は、Ｄｅ部員の属性情報である。Ｄｅ部員は、Ｄｉ事業部のＤｅ部に所属する。第３属性値および第４属性値がワイルドカード「＊」であるため、課および氏名は限定されない。
【００９３】
図１１に戻り、ステップＳ１４２の説明を続ける。
利用者の属性を表現するための階層の層数を「Ｌ」と記す。Ｌは２以上の整数である。
属性情報はＬ個の属性値を示す。
【００９４】
属性情報Ａは次のように表すことができる。
Ａ  ＝  （Ａ＿１，・・・，Ａ＿Ｌ）
【００９５】
属性情報Ａは、検索および復号の権限制御に関わる。
具体的には、属性情報Ａに基づくデータを用いて、検索権限および復号権限が設定される。
属性情報Ａは、検索権限用の属性情報と復号権限用の属性情報との２つの属性情報であってもよい。
【００９６】
ステップＳ１４３において、集約情報生成部４２１は、属性情報Ａに含まれる複数の属性値を１組以上のブロックに集約する。これにより、集約情報Ａ′が生成される。
集約情報Ａ′は、集約後の属性情報Ａである。
集約情報Ａ′の各ブロックは、１つ以上の属性値で構成される。
集約情報Ａ′の各ブロックが示す値を集約値と呼ぶ。
【００９７】
図１３に基づいて、属性情報（図１２参照）を集約して得られる集約情報の例を説明する。「｜」は連結を意味する記号である。
集約情報の第１要素は、第１属性と第２属性とを連結したものである。
集約情報の第２要素は、第３属性と第４属性とを連結したものである。
【００９８】
１番の集約情報は、Ｎｅさんの集約情報である。
Ｎｅさんの属性情報（図１２参照）は（Ｄｉ，Ｄｅ，Ｓｃ，Ｎｅ）である。
Ｎｅさんの集約情報（図１３参照）は（Ｄｉ｜Ｄｅ，Ｓｃ｜Ｎｅ）である。
第１属性値Ｄｉと第２属性値Ｄｅは、連結されることによって１つの文字列Ｄｉ｜Ｄｅに集約されている。
第３属性値Ｓｃと第４属性値Ｎｅは、連結されることによって１つの文字列Ｓｃ｜Ｎｅに集約されている。
他の集約情報も１番の集約情報と同様に表現される。
【００９９】
図１１に戻り、ステップＳ１４２の説明を続ける。
利用者の属性を表現するための階層の集約後の層数を「ｋ」と記す。ｋは１以上の整数である。
集約情報はｋ個の集約値を示す。
集約値は、１つ以上の属性値を集約して得られる値である。具体的には、集約値は、１つ以上の属性値を連結して得られる文字列である。
【０１００】
集約情報Ａ′は次のように表すことができる。ｍは１以上の整数である。ｉ＿１，・・・，ｉ＿ｍは正の整数である。
Ａ′  ＝  （Ａ′＿１，・・・，Ａ′＿ｋ）
Ａ′＿ｉ  ＝  Ａ＿（ｉ＿１）｜Ａ＿（ｉ＿２）｜・・・｜Ａ＿（ｉ＿ｍ）
ｉ＿１＜・・・＜ｉ＿ｍ、及び、ｉ＿１＋１＝ｉ＿２，ｉ＿２＋１＝ｉ＿３，・・・，ｉ＿（ｍ−１）＋１＝ｉ＿ｍ、ｉ＿ｍ＋１＝（ｉ＋１）＿１が成り立つ。
【０１０１】
ここで、図１２における１番の属性情報を属性情報Ａと呼ぶ。
また、図１３における１番の集約情報を集約情報Ａ１′と呼ぶ。
集約情報Ａ１′は次のように表すことができる。
Ａ１′＝（Ａ１′＿１，Ａ１′＿２）＝（Ａ１＿１｜Ａ１＿２，Ａ１＿３｜Ａ１＿４）＝（Ｄｉ｜Ｄｅ，Ｓｃ｜Ｎｅ）
【０１０２】
集約方法に対する制約はない。但し、秘匿検索システム１００において、１つの集約方法が使用される。つまり、ユーザ鍵装置４００と他の装置は同じ集約方法を使用する。
【０１０３】
ステップＳ１４４において、ユーザ鍵生成部４２２は、データ鍵ＤＫと属性情報Ａと集約情報Ａ′とを用いて、ユーザデータ鍵ＵＤＫを生成する。データ鍵ＤＫは登録鍵ＥＫに含まれる。
【０１０４】
ユーザデータ鍵ＵＤＫは、データ属性鍵ＵＤＫ＿ｉとフラグ値Ｄｂ＿ｊとを有する。
ｉは１以上ｋ以下の整数である。ｊは１以上Ｌ以下の整数である。
【０１０５】
ユーザ鍵生成部４２２は、データ属性鍵ＵＤＫ＿ｉを以下のように算出する。
まず、ユーザ鍵生成部４２２は、集約値Ａ′＿ｉと番号ｉとを連結する。得られるビット列が表す値を連結値Ａ′＿ｉ｜ｉと呼ぶ。
そして、ユーザ鍵生成部４２２は、データ鍵ＤＫと連結値Ａ′＿ｉ｜ｉとを入力として関数Ｆ＿２を実行する。得られる値がデータ属性鍵ＵＤＫ＿ｉである。
関数Ｆ＿２は、関数Ｆ＿１と同様に、擬似ランダム関数、ハッシュ関数または共通鍵暗号方式の関数である。
【０１０６】
ユーザ鍵生成部４２２は、フラグ値Ｄｂ＿ｊを以下のように決定する。
ユーザ鍵生成部４２２は、属性値Ａ＿ｊがワイルドカード「＊」であるか判定する。
属性値Ａ＿ｊがワイルドカード「＊」である場合、フラグ値Ｄｂ＿ｊは１である。
属性値Ａ＿ｊがワイルドカード「＊」でない場合、フラグ値Ｄｂ＿ｊは０である。
フラグ値Ｄｂ＿ｊは、属性値Ａ＿ｊがワイルドカード「＊」であるか否かを示す。
【０１０７】
ユーザデータ鍵ＵＤＫは次のように表すことができる。ｉは１以上ｋ以下の整数である。ｊは１以上Ｌ以下の整数である。
ＵＤＫ  ＝  （ＵＤＫ＿１，・・・，ＵＤＫ＿ｋ，Ｄｂ＿１，・・・，Ｄｂ＿Ｌ）
Ａ＿ｊ＝＊である場合、Ｄｂ＿ｊ  ＝  １
Ａ＿ｊ≠＊である場合、Ｄｂ＿ｊ  ＝  ０
ＵＤＫ＿ｉ  ＝  Ｆ＿２（ＤＫ，Ａ′＿ｉ｜ｉ）
【０１０８】
ステップＳ１４５において、ユーザ鍵生成部４２２は、タグ鍵ＴＫと属性情報Ａと集約情報Ａ′とを用いて、ユーザタグ鍵ＵＴＫを生成する。タグ鍵ＴＫは登録鍵ＥＫに含まれる。
【０１０９】
ユーザタグ鍵ＵＴＫは、タグ属性鍵ＵＴＫ＿ｉとフラグ値Ｔｂ＿ｊとを有する。
ｉは１以上ｋ以下の整数である。ｊは１以上Ｌ以下の整数である。
【０１１０】
ユーザ鍵生成部４２２は、タグ属性鍵ＵＴＫ＿ｉを以下のように算出する。
まず、ユーザ鍵生成部４２２は、集約値Ａ′＿ｉと番号ｉとを連結する。得られるビット列が表す値を連結値Ａ′＿ｉ｜ｉと呼ぶ。
そして、ユーザ鍵生成部４２２は、タグ鍵ＴＫと連結値Ａ′＿ｉ｜ｉとを入力として関数Ｆ＿２を実行する。得られる値がタグ属性鍵ＵＴＫ＿ｉである。
【０１１１】
ユーザ鍵生成部４２２は、フラグ値Ｔｂ＿ｊを以下のように決定する。
ユーザ鍵生成部４２２は、属性値Ａ＿ｊがワイルドカード「＊」であるか判定する。
属性値Ａ＿ｊがワイルドカード「＊」である場合、フラグ値Ｔｂ＿ｊは１である。
属性値Ａ＿ｊがワイルドカード「＊」でない場合、フラグ値Ｔｂ＿ｊは０である。
フラグ値Ｔｂ＿ｊは、属性値Ａ＿ｊがワイルドカード「＊」であるか否かを示す。
【０１１２】
ユーザタグ鍵ＵＴＫは次のように表すことができる。ｉは１以上ｋ以下の整数である。ｊは１以上Ｌ以下の整数である。
ＵＴＫ  ＝  （ＵＴＫ＿１，・・・，ＵＴＫ＿ｋ，Ｔｂ＿１，・・・，Ｔｂ＿Ｌ）
Ａ＿ｊ＝＊である場合、Ｔｂ＿ｊ  ＝  １
Ａ＿ｊ≠＊である場合、Ｔｂ＿ｊ  ＝  ０
ＵＴＫ＿ｉ  ＝  Ｆ＿２（ＴＫ，Ａ′＿ｉ｜ｉ）
【０１１３】
ユーザデータ鍵ＵＤＫとユーザタグ鍵ＵＴＫとの組を「ユーザ鍵ＵＫ」と呼ぶ。ユーザ鍵ＵＫは次のように表すことができる。
ＵＫ  ＝  （ＵＤＫ，ＵＴＫ）
【０１１４】
ステップＳ１４６において、生成部４２０はユーザ鍵ＵＫを記憶部４９０に記憶する。これにより、ユーザ鍵ＵＫが記憶部４９０に保管される。
【０１１５】
ステップＳ１４７において、出力部４３０はユーザ鍵ＵＫを出力する。
例えば、出力部４３０は、通信装置４０５を用いて、ユーザ鍵ＵＫを検索操作装置６００へ送信する。
【０１１６】
図１４に基づいて、データ登録（Ｓ１５０）を説明する。
データ登録（Ｓ１５０）は、登録装置５００によって実行される処理である。
【０１１７】
ステップＳ１５１において、受付部５１０は登録鍵ＥＫを受け付ける。
例えば、受付部５１０は、通信装置５０５を用いて、登録鍵装置３００から登録鍵ＥＫを受信する。受付部５１０は、登録装置５００に入力される登録鍵ＥＫを入出力インタフェース５０４を介して受け付けてもよい。
【０１１８】
そして、受付部５１０は、登録鍵ＥＫを記憶部５９０に記憶する。これにより、登録鍵ＥＫが記憶部５９０に保管される。
【０１１９】
登録鍵ＥＫが記憶部５９０に既に保管されている場合、ステップＳ１５１は不要である。
【０１２０】
登録鍵ＥＫは、データ鍵ＤＫとタグ鍵ＴＫとを有する。
【０１２１】
ステップＳ１５２において、受付部５１０は、平文Ｍと属性情報Ｂとを受け付ける。
例えば、受付部５１０は、登録装置５００に入力される平文Ｍと属性情報Ｂとを入出力インタフェース５０４を介して受け付ける。受付部５１０は、登録装置５００において実行されるアプリケーションプログラムから、平文Ｍと属性情報Ｂとを受け付けてもよい。
【０１２２】
平文Ｍは、暗号化されていないデータである。
平文Ｍには、ファイル名Ｆｉｌｅ（Ｍ）がメタデータとして含まれる。
【０１２３】
属性情報Ｂは、権限者の属性情報である。
権限者は、検索操作装置６００の利用者の一部であり、平文Ｍを参照する権限を有する。
例えば、属性情報Ｂは図１２に示された属性情報である。
【０１２４】
属性情報Ｂは次のように表すことができる。
Ｂ  ＝  （Ｂ＿１，・・・，Ｂ＿Ｌ）
【０１２５】
属性情報Ｂは、属性情報Ａと同様に、検索および復号の権限制御に関わる。
【０１２６】
ステップＳ１５３において、乱数生成部５２１は、データ乱数群ｒ＝（ｒ＿１，・・・，ｒ＿ｋ，ｒｓ）とタグ乱数群Ｒ＝（Ｒ＿１，・・・，Ｒ＿ｋ，ＲＳ）とを生成する。
データ乱数群ｒとタグ乱数群Ｒはそれぞれ（ｋ＋１）個の乱数からなる。各乱数は一様ランダムに生成される。
【０１２７】
ステップＳ１５４において、集約情報生成部５２２は、属性情報Ｂに含まれる複数の属性値を１組以上のブロックに集約する。これにより、集約情報Ｂ′が生成される。
集約情報Ｂ′は、集約後の属性情報Ｂである。
集約情報Ｂ′の各ブロックは、１つ以上の属性値で構成される。
集約情報Ｂ′の各ブロックが示す値を集約値と呼ぶ。
集約情報Ｂ′のための集約方法は、集約情報Ａ′のための集約方法（図１１のステップＳ１４３を参照）と同じである。
例えば、集約情報Ｂ′は図１３に示された集約情報である。
【０１２８】
集約情報Ｂ′は以下のように表すことができる。ｍは１以上の整数である。ｉ＿１，・・・，ｉ＿ｍは正の整数である。
Ｂ′  ＝  （Ｂ′＿１，・・・，Ｂ′＿ｋ）
Ｂ′＿ｉ  ＝  Ｂ＿（ｉ＿１）｜Ｂ＿（ｉ＿２）｜・・・｜Ｂ＿（ｉ＿ｍ）
ｉ＿１＜・・・＜ｉ＿ｍ、及び、ｉ＿１＋１＝ｉ＿２，ｉ＿２＋１＝ｉ＿３，・・・，ｉ＿（ｍ−１）＋１＝ｉ＿ｍ、ｉ＿ｍ＋１＝（ｉ＋１）＿１が成り立つ。
【０１２９】
ステップＳ１５５において、汎化情報生成部５２３は、集約情報Ｂ′に含まれる各集約値をワイルドカードを用いて汎化する。これにより、汎化情報Ｂ＾が生成される。
汎化情報Ｂ＾は、各集約値に対する複数の汎化値を示す。
汎化値は、集約値の中のゼロ個以上の属性値を代替するゼロ個以上のワイルドカードと集約値の中の残りの属性値とで構成される。
【０１３０】
具体的には、汎化情報生成部５２３は、集約情報Ｂ′に含まれるｉ番目の集約値Ｂ′＿ｉに対して、Ｉｉ個の汎化値Ｂ′＿ｉ＾を以下のように生成する。
Ｂ′＿ｉ＾０  ＝  Ｂ′＿ｉ
＝  Ｂ＿（ｉ＿１）｜Ｂ＿（ｉ＿２）｜・・・｜Ｂ＿（ｉ＿ｍ）
Ｂ′＿ｉ＾１  ＝  ＊｜Ｂ＿（ｉ＿２）｜・・・｜Ｂ＿（ｉ＿ｍ）
Ｂ′＿ｉ＾２  ＝  Ｂ＿（ｉ＿１）｜＊｜Ｂ＿（ｉ＿３）｜・・・｜Ｂ＿（ｉ＿ｍ）
Ｂ′＿ｉ＾３  ＝  ＊｜＊｜Ｂ＿（ｉ＿３）｜・・・｜Ｂ＿（ｉ＿ｍ）
Ｂ′＿ｉ＾４  ＝  Ｂ＿（ｉ＿１）｜Ｂ＿（ｉ＿２）｜＊｜Ｂ＿（ｉ＿４）｜・・・｜Ｂ＿（ｉ＿ｍ）
・・・
Ｂ′＿ｉ＾Ｉｉ  ＝  ＊｜＊｜・・・｜＊
Ｉｉ  ＝  ２（（ｉ＿ｍ）−（ｉ＿１）＋１）
【０１３１】
ここで、図１３における１番の集約情報を集約情報Ｂ′と呼ぶ。
また、集約情報Ｂ′に含まれる第１集約値を集約値Ｂ′＿１と呼ぶ。
集約値Ｂ′＿１に対して以下の４つの汎化値Ｂ′＿１＾が生成される。
Ｂ′＿１＾０  ＝  Ｂ′＿１  ＝  Ｄｉ｜Ｄｅ
Ｂ′＿１＾１  ＝  ＊｜Ｄｅ
Ｂ′＿１＾２  ＝  Ｄｉ｜＊
Ｂ′＿１＾３  ＝  ＊｜＊
【０１３２】
ここで、集約情報Ｂ′に含まれる第２集約値を集約値Ｂ′＿２と呼ぶ。
集約値Ｂ′＿２に対して以下の４つの汎化値Ｂ′＿２＾が生成される。
Ｂ′＿２＾０  ＝  Ｂ′＿２  ＝  Ｓｃ｜Ｎｅ
Ｂ′＿２＾１  ＝  ＊｜Ｎｅ
Ｂ′＿２＾２  ＝  Ｓｃ｜＊
Ｂ′＿２＾３  ＝  ＊｜＊
【０１３３】
図１４に戻り、ステップＳ１５６から説明を続ける。
ステップＳ１５６において、暗号文データ生成部５２４は、データ鍵ＤＫと平文Ｍと属性情報Ｂと汎化情報Ｂ＾とデータ乱数群ｒとを用いて、暗号文データＣを生成する。データ鍵ＤＫは登録鍵ＥＫに含まれる。
【０１３４】
暗号文データＣは、属性要素Ｃ＿｛ｉ，ｈ｝と乱数要素Ｃ＿ｒｓと暗号文Ｃ′を有する。
ｉは１以上ｋ以下の整数である。ｈは０以上２（（ｉ＿ｍ）−（ｉ＿１）＋１）−１以下の整数である。
【０１３５】
暗号文データ生成部５２４は、属性要素Ｃ＿｛ｉ，ｈ｝を以下のように算出する。
まず、暗号文データ生成部５２４は、汎化情報Ｂ＾に含まれる汎化値Ｂ′＿ｉ＾ｈと番号ｉとを連結する。得られるビット列が表す値を連結値Ｂ′＿ｉ＾ｈ｜ｉと呼ぶ。
次に、暗号文データ生成部５２４は、データ鍵ＤＫと連結値Ｂ′＿ｉ＾ｈ｜ｉとを入力として関数Ｆ＿２を実行する。得られる値を関数値（ＤＫ，Ｂ′＿ｉ＾ｈ｜ｉ）と呼ぶ。
次に、暗号文データ生成部５２４は、関数値（ＤＫ，Ｂ′＿ｉ＾ｈ｜ｉ）とデータ乱数群ｒに含まれる乱数ｒｓとを入力として関数Ｆ＿３を実行する。得られる値を関数値（ＤＫ，Ｂ′＿ｉ＾ｈ｜ｉ，ｒｓ）と呼ぶ。
関数Ｆ＿３は、関数Ｆ＿１と関数Ｆ＿２と同様に、擬似ランダム関数、ハッシュ関数または共通鍵暗号方式の関数である。
そして、暗号文データ生成部５２４は、関数値（ＤＫ，Ｂ′＿ｉ＾ｈ｜ｉ，ｒｓ）とデータ乱数群ｒに含まれる乱数ｒ＿ｉとの排他的論理和を算出する。得られる値が属性要素Ｃ＿｛ｉ，ｊ｝である。
【０１３６】
暗号文データ生成部５２４は、データ乱数群ｒに含まれる乱数ｒｓを乱数要素Ｃ＿ｒｓに設定する。
【０１３７】
暗号文データ生成部５２４は、暗号文Ｃ′を以下のように算出する。
まず、暗号文データ生成部５２４は、データ乱数群ｒに含まれるｋ個の乱数（ｒ＿１，・・・，ｒ＿ｋ）の排他的論理和を算出する。得られる値を乱数和ｒ＋と呼ぶ。
次に、暗号文データ生成部５２４は、乱数和ｒ＋を入力として関数Ｆ＿４を実行する。得られる値を関数値（ｒ＋）と呼ぶ。
関数Ｆ＿４は、関数Ｆ＿３と同様に、擬似ランダム関数、ハッシュ関数または共通鍵暗号方式の関数である。
そして、暗号文データ生成部５２４は、関数値（ｒ＋）と平文Ｍとの排他的論理和を算出する。得られる値が暗号文Ｃ′である。
暗号文Ｃ′は、暗号化された平文Ｍである。
【０１３８】
暗号文データＣは以下のように表すことができる。但し、実施の形態１において（＋）は排他的論理和（ＸＯＲ）を意味する。ｉは１以上ｋ以下の整数である。ｍは１以上の整数である。
Ｃ  ＝  （（Ｃ＿｛１，０｝，Ｃ＿｛１，１｝，・・・，Ｃ＿｛１，Ｉ１｝），（Ｃ＿｛２，０｝，Ｃ＿｛２，１｝，・・・，Ｃ＿｛２，Ｉ２｝），・・・，（Ｃ＿｛ｋ，０｝，Ｃ＿｛ｋ，１｝，・・・，Ｃ＿｛ｋ，Ｉｋ｝），Ｃ＿ｒｓ，Ｃ′）
Ｃ＿｛ｉ，ｈ｝  ＝  Ｆ＿３（Ｆ＿２（ＤＫ，Ｂ′＿ｉ＾ｈ｜ｉ），ｒｓ）（＋）ｒ＿ｉ
Ｃ＿ｒｓ  ＝  ｒｓ
Ｃ′  ＝  Ｆ＿４（ｒ＿１（＋）・・・（＋）ｒ＿ｋ）（＋）Ｍ
Ｉｉ  ＝  ２（（ｉ＿ｍ）−（ｉ＿１）＋１）
【０１３９】
ステップＳ１５７において、キーワード生成部５２５は、平文Ｍに関するキーワードを生成する。
具体的には、キーワード生成部５２５は、平文Ｍに対して形態素解析または自然言語処理などを行うことによって、平文Ｍからキーワードを抽出する。
但し、キーワード生成部５２５は、登録装置５００に入力されるキーワードを入出力インタフェース５０４を介して受け付けてもよい。また、キーワード生成部５２５は、登録装置５００において実行されるアプリケーションプログラムから、平文Ｍに関するキーワードを受け付けてもよい。
【０１４０】
平文Ｍに関するキーワードを「登録キーワードＷ」と呼ぶ。
登録キーワードＷは複数あってもよい。複数の登録キーワードＷがある場合、各登録キーワードＷに対して暗号化タグＣＴが生成される。
【０１４１】
ステップＳ１５８において、暗号化タグ生成部５２６は、タグ鍵ＴＫと属性情報Ｂと汎化情報Ｂ＾とタグ乱数群Ｒと登録キーワードＷとを用いて、暗号化タグＣＴを生成する。タグ鍵ＴＫは登録鍵ＥＫに含まれる。
【０１４２】
暗号化タグＣＴは、属性要素ＣＴ＿｛ｉ，ｈ｝と乱数要素ＣＴ＿ＲＳと検証要素ＣＴ＿Ｖとを有する。
ｉは１以上ｋ以下の整数である。ｈは０以上２（（ｉ＿ｍ）−（ｉ＿１）＋１）−１以下の整数である。
【０１４３】
暗号化タグ生成部５２６は、属性要素ＣＴ＿｛ｉ，ｈ｝を以下のように算出する。
まず、暗号化タグ生成部５２６は、汎化情報Ｂ＾に含まれる汎化値Ｂ′＿ｉ＾ｈと番号ｉとを連結する。得られるビット列が表す値を連結値Ｂ′＿ｉ＾ｈ｜ｉと呼ぶ。
次に、暗号化タグ生成部５２６は、タグ鍵ＴＫと連結値Ｂ′＿ｉ＾ｈ｜ｉとを入力として関数Ｆ＿２を実行する。得られる値を関数値（ＴＫ，Ｂ′＿ｉ＾ｈ｜ｉ）と呼ぶ。
次に、暗号化タグ生成部５２６は、関数値（ＴＫ，Ｂ′＿ｉ＾ｈ｜ｉ）と登録キーワードＷとを入力として関数Ｆ＿５を実行する。得られる値を関数値（ＴＫ，Ｂ′＿ｉ＾ｈ｜ｉ，Ｗ）と呼ぶ。
関数Ｆ＿５は、関数Ｆ＿１と関数Ｆ＿２と同様に、擬似ランダム関数、ハッシュ関数または共通鍵暗号方式の関数である。
次に、暗号化タグ生成部５２６は、関数値（ＴＫ，Ｂ′＿ｉ＾ｈ｜ｉ，Ｗ）とタグ乱数群Ｒに含まれる乱数ＲＳとを入力として関数Ｆ＿６を実行する。得られる値を関数値（ＴＫ，Ｂ′＿ｉ＾ｈ｜ｉ，Ｗ，ＲＳ）と呼ぶ。
関数Ｆ＿６は、関数Ｆ＿５と同様に、擬似ランダム関数、ハッシュ関数または共通鍵暗号方式の関数である。
そして、暗号化タグ生成部５２６は、関数値（ＴＫ，Ｂ′＿ｉ＾ｈ｜ｉ，Ｗ，ＲＳ）とタグ乱数群Ｒに含まれる乱数Ｒ＿ｉとの排他的論理和を算出する。得られる値が属性要素ＣＴ＿｛ｉ，ｈ｝である。
【０１４４】
暗号化タグ生成部５２６は、タグ乱数群Ｒに含まれる乱数ＲＳを乱数要素ＣＴ＿ＲＳに設定する。
【０１４５】
暗号化タグ生成部５２６は、検証要素ＣＴ＿Ｖを以下のように算出する。
まず、暗号化タグ生成部５２６は、タグ乱数群Ｒに含まれるｋ個の乱数（Ｒ＿１，・・・，Ｒ＿ｋ）の排他的論理和を算出する。得られる値を乱数和Ｒ＋と呼ぶ。
そして、暗号化タグ生成部５２６は、乱数和Ｒ＋を入力として関数Ｆ＿６を実行する。得られる値が検証要素ＣＴ＿Ｖである。
関数Ｆ＿７は、関数Ｆ＿６と同様に、擬似ランダム関数、ハッシュ関数または共通鍵暗号方式の関数である。
【０１４６】
暗号化タグＣＴは以下のように表すことができる。但し、実施の形態１において（＋）は排他的論理和（ＸＯＲ）を意味する。ｉは１以上ｋ以下の整数である。ｍは１以上の整数である。
ＣＴ  ＝  （（ＣＴ＿｛１，０｝，ＣＴ＿｛１，１｝，・・・，ＣＴ＿｛１，Ｉ１｝），（ＣＴ＿｛２，０｝，ＣＴ＿｛２，１｝，・・・，ＣＴ＿｛２，Ｉ２｝），・・・，（ＣＴ＿｛ｋ，０｝，ＣＴ＿｛ｋ，１｝，・・・，ＣＴ＿｛ｋ，Ｉｋ｝），ＣＴ＿ＲＳ，ＣＴ＿Ｖ）
ＣＴ＿｛ｉ，ｈ｝  ＝  Ｆ＿６（Ｆ＿５（Ｆ＿２（ＴＫ，Ｂ′＿ｉ＾ｈ｜ｉ），Ｗ），ＲＳ）（＋）Ｒ＿ｉ
ＣＴ＿ＲＳ  ＝  ＲＳ
ＣＴ＿Ｖ  ＝  Ｆ＿７（Ｒ＿１（＋）・・・（＋）Ｒ＿ｋ）
Ｉｉ  ＝  ２（（ｉ＿ｍ）−（ｉ＿１）＋１）
【０１４７】
ステップＳ１５９において、登録部５３０は、ファイル名Ｆｉｌｅ（Ｍ）と暗号文データＣと暗号化タグＣＴとの組をデータ管理装置７００の登録データベース７９１に登録する。
ファイル名Ｆｉｌｅ（Ｍ）と暗号文データＣと暗号化タグＣＴとの組を「秘匿検索データ」と呼ぶ。
【０１４８】
図１５に基づいて、登録データベース７９１を説明する。
登録データベース７９１は、検索のためのデータベースであり、データ管理装置７００の記憶部７９０に記憶される。
登録データベース７９１には、ファイル名Ｆｉｌｅ（Ｍ）と暗号文データＣと暗号化タグＣＴとの組（秘匿検索データ）が登録される。
【０１４９】
図１４に戻り、ステップＳ１５９の説明を続ける。
秘匿検索データは以下のように登録される。
登録部５３０は、通信装置５０５を用いて、秘匿検索データをデータ管理装置７００へ送信する。データ管理装置７００において、受付部７１０が秘匿検索データを受信し、管理部７４０が秘匿検索データを登録データベース７９１に登録する。
これにより、ファイル名Ｆｉｌｅ（Ｍ）と暗号文データＣと暗号化タグＣＴとが互いに対応付けて保管される。
【０１５０】
図１６に基づいて、検索操作（Ｓ１６０）を説明する。
検索操作（Ｓ１６０）は、検索操作装置６００によって実行される処理である。
【０１５１】
ステップＳ１６１において、受付部６１０はユーザ鍵ＵＫを受け付ける。
例えば、受付部６１０は、通信装置６０５を用いて、ユーザ鍵装置４００からユーザ鍵ＵＫを受信する。受付部６１０は、検索操作装置６００に入力されるユーザ鍵ＵＫを入出力インタフェース６０４を介して受け付けてもよい。
【０１５２】
そして、受付部６１０は、ユーザ鍵ＵＫを記憶部６９０に記憶する。これにより、ユーザ鍵ＵＫが記憶部６９０に保管される。
【０１５３】
ユーザ鍵ＵＫが記憶部６９０に既に保管されている場合、ステップＳ１６１は不要である。
【０１５４】
ユーザ鍵ＵＫは、ユーザデータ鍵ＵＤＫとユーザタグ鍵ＵＴＫとを有する。
【０１５５】
ステップＳ１６２において、受付部６１０は検索キーワードｗを受け付ける。
例えば、受付部６１０は、検索操作装置６００に入力される検索キーワードｗを入出力インタフェース６０４を介して受け付ける。受付部６１０は、検索操作装置６００において実行されるアプリケーションプログラムから、検索キーワードｗを受け付けてもよい。
【０１５６】
ステップＳ１６３において、生成部６２０は、ユーザタグ鍵ＵＴＫと検索キーワードｗとを用いて、検索クエリＳＱを生成する。ユーザタグ鍵ＵＴＫはユーザ鍵ＵＫに含まれる。
【０１５７】
ユーザタグ鍵ＵＴＫは、以下のようにｋ個のタグ属性鍵｛ＵＴＫ＿１，・・・，ＵＴＫ＿ｋ｝とＬ個のフラグ値｛Ｔｂ＿１，・・・，Ｔｂ＿Ｌ｝を有する。
ＵＴＫ  ＝  （ＵＴＫ＿１，・・・，ＵＴＫ＿ｋ，Ｔｂ＿１，・・・，Ｔｂ＿Ｌ）
Ｌ個のフラグ値｛Ｔｂ＿１，・・・，Ｔｂ＿Ｌ｝をフラグ情報Ｔｂと呼ぶ。
【０１５８】
図１７に基づいて、ステップＳ１６３の手順を説明する。
ステップＳ１６３１において、集約フラグ生成部６２１は、フラグ情報Ｔｂに含まれる複数のフラグ値を１組以上のブロックに集約する。これにより、集約フラグＴｂ′が生成される。
集約フラグＴｂ′は、集約後のフラグ情報Ｔｂである。
集約フラグＴｂ′の各ブロックは、１つ以上のフラグ値で構成される。
集約フラグＴｂ′の各ブロックが示す値を集約値と呼ぶ。
集約フラグＴｂ′のための集約方法は、集約情報Ａ′（図１１のステップＳ１４３を参照）と集約情報Ｂ′（図１４のステップＳ１５４を参照）のための集約方法と同じである。
【０１５９】
集約フラグＴｂ′は以下のように表すことができる。ｍは１以上の整数である。ｉ＿１，・・・，ｉ＿ｍは正の整数である。
Ｔｂ′  ＝  （Ｔｂ′＿１，・・・，Ｔｂ′＿ｋ）
Ｔｂ′＿ｉ  ＝  （Ｔｂ＿（ｉ＿１）｜Ｔｂ＿（ｉ＿２）｜・・・｜Ｔｂ＿（ｉ＿ｍ）
ｉ＿１＜・・・＜ｉ＿ｍ、及び、ｉ＿１＋１＝ｉ＿２，ｉ＿２＋１＝ｉ＿３，・・・，ｉ＿（ｍ−１）＋１＝ｉ＿ｍ、ｉ＿ｍ＋１＝（ｉ＋１）＿１が成り立つ。
【０１６０】
集約フラグＴｂ′は、ｋ個の集約値Ｔｂ′＿ｉを有する。
【０１６１】
例えば、１番の集約情報（図１３参照）に対応する集約フラグＴｂ１′は以下のように表すことができる。
Ｔｂ１′＝（Ｔｂ１′＿１，Ｔｂ１′＿２）＝（Ｔｂ１＿１｜Ｔｂ１＿２，Ｔｂ１＿３｜Ｔｂ１＿４）＝（０｜０，０｜０）
【０１６２】
例えば、３番の集約情報（図１３参照）に対応する集約フラグＴｂ３′は以下のように表すことができる。
Ｔｂ３′＝（Ｔｂ３′＿１，Ｔｂ３′＿２）＝（Ｔｂ３＿１｜Ｔｂ３＿２，Ｔｂ３＿３｜Ｔｂ３＿４）＝（０｜０，０｜１）
【０１６３】
例えば、４番の集約情報（図１３参照）に対応する集約フラグＴｂ４′は以下のように表すことができる。
Ｔｂ４′＝（Ｔｂ４′＿１，Ｔｂ４′＿２）＝（Ｔｂ４＿１｜Ｔｂ４＿２，Ｔｂ４＿３｜Ｔｂ４＿４）＝（０｜０，１｜１）
【０１６４】
ステップＳ１６３２において、位置情報生成部６２２は、集約フラグＴｂ′を用いて、検索位置情報ＳＰを生成する。
【０１６５】
検索位置情報ＳＰは、暗号化タグＣＴに含まれる複数の属性要素ＣＴ＿のうち検索時に使用される１つ以上の属性要素ＣＴ＿｛ｉ，ｈ｝を特定する情報である。
具体的には、検索位置情報ＳＰは１組以上の整数（ｉ，ｈ）を示す。
【０１６６】
検索位置情報ＳＰは以下のように表すことができる。
ＳＰ  ＝  （（１，ＳＰ１），・・・，（ｋ，ＳＰｋ））
ＳＰ＿ｉ  ＝  Ｔｂ′＿（ｉ＿１）×２０＋Ｔｂ′＿（ｉ＿２）×２１＋・・・＋Ｔｂ′＿（ｉ＿ｍ）×２（ｉ＿ｍ）−（ｉ＿１）＋１
【０１６７】
例えば、１番の集約情報（図１３参照）に対応する集約フラグＴｂ１′は以下のように表すことができる。
Ｔｂ１′＝（Ｔｂ１′＿１，Ｔｂ１′＿２）＝（Ｔｂ１＿１｜Ｔｂ１＿２，Ｔｂ１＿３｜Ｔｂ１＿４）＝（０｜０，０｜０）
この場合、集約フラグＴｂ１′に対応する検索位置情報ＳＰ１は以下のように表すことができる。
ＳＰ１  ＝  （ＳＰ１＿１，ＳＰ１＿２）
ＳＰ１＿１  ＝  ０×２０＋０×２１  ＝  ０
ＳＰ１＿２  ＝  ０×２０＋０×２１  ＝  ０
【０１６８】
例えば、３番の集約情報（図１３参照）に対応する集約フラグＴｂ３′は以下のように表すことができる。
Ｔｂ３′＝（Ｔｂ３′＿１，Ｔｂ３′＿２）＝（Ｔｂ３＿１｜Ｔｂ３＿２，Ｔｂ３＿３｜Ｔｂ３＿４）＝（０｜０，０｜１）
この場合、集約フラグＴｂ３′に対応する検索位置情報ＳＰ３は以下のように表すことができる。
ＳＰ３  ＝  （ＳＰ３＿１，ＳＰ３＿２）
ＳＰ３＿１  ＝  ０×２０＋０×２１  ＝  ０
ＳＰ３＿２  ＝  ０×２０＋１×２１  ＝  ２
【０１６９】
例えば、４番の集約情報（図１３参照）に対応する集約フラグＴｂ４′は以下のように表すことができる。
Ｔｂ４′＝（Ｔｂ４′＿１，Ｔｂ４′＿２）＝（Ｔｂ４＿１｜Ｔｂ４＿２，Ｔｂ４＿３｜Ｔｂ４＿４）＝（０｜０，１｜１）
この場合、集約フラグＴｂ４′に対応する検索位置情報ＳＰ４は以下のように表すことができる。
ＳＰ４  ＝  （ＳＰ４＿１，ＳＰ４＿２）
ＳＰ４＿１  ＝  ０×２０＋０×２１  ＝  ０
ＳＰ４＿２  ＝  １×２０＋１×２１  ＝  ３
【０１７０】
ステップＳ１６３３において、検索クエリ生成部６２３は、タグ属性鍵ＵＴＫ＿ｉと検索キーワードｗと検索位置情報ＳＰとを用いて、検索クエリＳＱを生成する。
【０１７１】
検索クエリＳＱは、属性キーワード要素ＳＱ＿ｉと検索位置要素ＳＱＰ＿ｉとを有する。
【０１７２】
検索クエリ生成部６２３は、属性キーワード要素ＳＱ＿ｉを以下のように算出する。
検索クエリ生成部６２３は、タグ属性鍵ＵＴＫ＿ｉと検索キーワードｗとを入力として関数Ｆ＿５を実行する。得られる値が属性キーワード要素ＳＱ＿ｉである。
属性キーワード要素ＳＱ＿ｉは、暗号化された検索キーワードｗ（暗号化キーワード）である。
【０１７３】
検索クエリ生成部６２３は、検索位置要素ＳＱＰ＿ｉを以下のように算出する。
検索クエリ生成部６２３は、検索位置情報ＳＰからｉ番目の要素ＳＰ＿ｉを抽出する。抽出される要素ＳＰ＿ｉが検索位置要素ＳＱＰ＿ｉである。
【０１７４】
検索クエリＳＱは以下のように表すことができる。ｉは１以上ｋ以下の整数である。
ＳＱ  ＝  （（ＳＱ＿１，ＳＱＰ＿１），・・・，（ＳＱ＿ｋ，ＳＱＰ＿ｋ））
ＳＱ＿ｉ  ＝  Ｆ＿５（ＵＴＫ＿ｉ，ｗ）
ＳＱＰ＿ｉ  ＝  ＳＰ＿ｉ
【０１７５】
図１６に戻り、ステップＳ１６４から説明を続ける。
ステップＳ１６４において、要求部６３０は、通信装置６０５を用いて、検索クエリＳＱをデータ管理装置７００へ送信する。
【０１７６】
ステップＳ１６５において、要求部６３０は、通信装置６０５を用いて、暗号化検索結果｛Ｃ｝をデータ管理装置７００から受信する。
暗号化検索結果｛Ｃ｝は、検索クエリＳＱに合致する暗号文データＣの集合である。
【０１７７】
暗号化検索結果｛Ｃ｝が暗号文データＣを有しない場合、つまり、検索クエリＳＱを用いた検索でヒットした暗号文データＣが無い場合、ステップＳ１６６は不要である。
【０１７８】
ステップＳ１６６において、復号部６４０は、ユーザデータ鍵ＵＤＫを用いて、暗号化検索結果｛Ｃ｝から検索結果｛Ｍ｝を復号する。ユーザデータ鍵ＵＤＫはユーザ鍵ＵＫに含まれる。
検索結果｛Ｍ｝は、検索クエリＳＱに合致する平文Ｍの集合である。
【０１７９】
ユーザデータ鍵ＵＤＫは、以下のようにｋ個のデータ属性鍵｛ＵＤＫ＿１，・・・，ＵＤＫ＿ｋ｝とＬ個のフラグ値｛Ｄｂ＿１，・・・，Ｄｂ＿Ｌ｝を有する。
ＵＤＫ  ＝  （ＵＤＫ＿１，・・・，ＵＤＫ＿ｋ，Ｄｂ＿１，・・・，Ｄｂ＿Ｌ）
Ｌ個のフラグ値｛Ｄｂ＿１，・・・，Ｄｂ＿Ｌ｝をフラグ情報Ｄｂと呼ぶ。
【０１８０】
図１８に基づいて、ステップＳ１６６の手順を説明する。
ステップＳ１６６１において、集約フラグ生成部６４１は、フラグ情報Ｄｂに含まれる複数のフラグ値を１組以上のブロックに集約する。これにより、集約フラグＤｂ′が生成される。
集約フラグＤｂ′は、集約後のフラグ情報Ｄｂである。
集約フラグＤｂ′の各ブロックは、１つ以上のフラグ値で構成される。
集約フラグＤｂ′の各ブロックが示す値を集約値と呼ぶ。
集約フラグＤｂ′のための集約方法は、集約フラグＴｂ′（図１７のステップＳ１６３１を参照）と同じである。
【０１８１】
集約フラグＤｂ′は以下のように表すことができる。ｍは１以上の整数である。ｉ＿１，・・・，ｉ＿ｍは正の整数である。
Ｄｂ′  ＝  （Ｄｂ′＿１，・・・，Ｄｂ′＿ｋ）
Ｄｂ′＿ｉ  ＝  （Ｄｂ＿（ｉ＿１）｜Ｄｂ＿（ｉ＿２）｜・・・｜Ｄｂ＿（ｉ＿ｍ）
ｉ＿１＜・・・＜ｉ＿ｍ、及び、ｉ＿１＋１＝ｉ＿２，ｉ＿２＋１＝ｉ＿３，・・・，ｉ＿（ｍ−１）＋１＝ｉ＿ｍ、ｉ＿ｍ＋１＝（ｉ＋１）＿１が成り立つ
【０１８２】
集約フラグＤｂ′は、ｋ個の集約値Ｄｂ′＿ｉを有する。
【０１８３】
ステップＳ１６６２において、位置情報生成部６４２は、集約フラグＤｂ′を用いて、復号位置情報ＤＰを生成する。
【０１８４】
復号位置情報ＤＰは、暗号文データＣに含まれる複数の属性要素Ｃ＿のうち復号時に使用される属性要素Ｃ＿｛ｉ，ｈ｝を特定する情報である。
具体的には、復号位置情報ＤＰは１組以上の整数（ｉ，ｈ）を示す。
【０１８５】
復号位置情報ＤＰは以下のように表すことができる。
ＤＰ  ＝  （（１，ＤＰ＿１），・・・，（ｋ，ＤＰ＿ｋ））
ＤＰ＿ｉ  ＝  Ｄｂ′＿（ｉ＿１）×２０＋Ｄｂ′＿（ｉ＿２）×２１＋・・・＋Ｄｂ′＿（ｉ＿ｍ）×２（ｉ＿ｍ）−（ｉ＿１）＋１
【０１８６】
ステップＳ１６６３において、検索結果復号部６４３は、ユーザデータ鍵ＵＤＫと復号位置情報ＤＰとを用いて、暗号化検索結果｛Ｃ｝から検索結果｛Ｍ｝を復号する。
具体的には、検索結果復号部６４３は、暗号化検索結果｛Ｃ｝の各暗号文データＣから平文Ｍを復号する。
【０１８７】
復号部６４０は、各暗号文データＣから平文Ｍを以下のように復号する。
まず、復号部６４０は、ユーザデータ鍵ＵＤＫに含まれるデータ属性鍵ＵＤＫ＿ｉと暗号文データＣに含まれる乱数要素Ｃ＿ｒｓとを入力として関数Ｆ＿３を実行する。得られる値を関数値（ＵＤＫ＿ｉ，Ｃ＿ｒｓ）と呼ぶ。
次に、復号部６４０は、暗号文データＣからｋ個の属性要素（Ｃ＿｛１，ＤＰ＿１｝，・・・，Ｃ＿｛ｋ，ＤＰ＿ｋ｝）を選択する。ＤＰ＿ｉは復号位置情報ＤＰに含まれる値である。
次に、復号部６４０は、関数値（ＵＤＫ＿ｉ，Ｃ＿ｒｓ）と属性要素Ｃ＿｛ｉ，ＤＰ＿ｉ｝との排他的論理和を算出する。得られる値を抽出乱数ｒ＿ｉ＾と呼ぶ。
次に、復号部６４０は、ｋ個の抽出乱数（ｒ＿１＾，・・・，ｒ＿ｋ＾）の排他的論理和を算出する。得られる値を乱数和ｒ＾＋と呼ぶ。
次に、復号部６４０は、乱数和ｒ＾＋を入力として関数Ｆ＿４を実行する。得られる値を関数値（ｒ＾＋）と呼ぶ。
そして、復号部６４０は、関数値（ｒ＾＋）と暗号文データＣに含まれる暗号文Ｃ′との排他的論理和を算出する。得られる値が平文Ｍである。
【０１８８】
平文Ｍは以下のように表すことができる。ｉは１以上ｋ以下の整数である。
Ｍ  ＝  Ｆ＿４（ｒ＿１＾（＋）・・・（＋）ｒ＿ｋ＾）（＋）Ｃ′
ｒ＿ｉ＾  ＝  Ｆ＿３（ＵＤＫ＿ｉ，Ｃ＿ｒｓ）（＋）Ｃ＿｛ｉ，ＤＰ＿ｉ｝
【０１８９】
図１６に戻り、ステップＳ１６７を説明する。
ステップＳ１６７において、出力部６５０は検索結果｛Ｍ｝を出力する。
例えば、出力部６５０は、入出力インタフェース６０４を介して、検索結果｛Ｍ｝をディスプレイに表示する。
【０１９０】
暗号化検索結果｛Ｃ｝が暗号文データＣを有しないためステップＳ１６６が実行されなかった場合、検索結果｛Ｍ｝は得られない。
検索結果｛Ｍ｝が得られなかった場合、出力部６５０は、検索結果｛Ｍ｝の代わりに、検索エラーメッセージを出力する。
検索エラーメッセージは、秘匿検索でヒットした平文Ｍが無いことを示す。
【０１９１】
図１９に基づいて、データ検索（Ｓ１７０）を説明する。
データ検索（Ｓ１７０）は、データ管理装置７００によって実行される処理である。
【０１９２】
ステップＳ１７１において、受付部７１０は、通信装置７０５を用いて、検索クエリＳＱを検索操作装置６００から受信する。
【０１９３】
ステップＳ１７２において、照合部７２１は、検索クエリＳＱを各暗号化タグＣＴと照合することによって、検索クエリＳＱに合致する暗号化タグＣＴを選択する。
検索クエリＳＱに合致する各暗号化タグＣＴを「該当暗号化タグＣＴ」と呼ぶ。
【０１９４】
具体的には、照合部７２１は、検索クエリＳＱを各暗号化タグＣＴと以下のように照合する。
まず、照合部７２１は、暗号化タグＣＴからｋ個の属性要素（ＣＴ＿｛１，ＳＱＰ＿１｝，・・・，ＣＴ＿｛ｋ，ＳＱＰ＿ｋ｝）を選択する。ＳＱＰ＿ｉは検索クエリＳＱに含まれる要素である。
次に、照合部７２１は、検索クエリＳＱに含まれる属性キーワード要素ＳＱ＿ｉと暗号化タグＣＴに含まれる乱数要素ＣＴ＿ＲＳとを入力として関数Ｆ＿６を実行する。得られる値を関数値（ＳＱ＿ｉ，ＣＴ＿ＲＳ）と呼ぶ。
次に、照合部７２１は、関数値（ＳＱ＿ｉ，ＣＴ＿ＲＳ）と属性要素ＣＴ＿｛ｉ，ＳＱＰ＿ｉ｝との排他的論理和を算出する。得られる値を抽出乱数Ｒ＿ｉ＾と呼ぶ。
次に、照合部７２１は、ｋ個の抽出乱数（Ｒ＿１＾，・・・，Ｒ＿ｋ＾）の排他的論理和を算出する。得られる値を乱数和Ｒ＾＋と呼ぶ。
次に、照合部７２１は、乱数和Ｒ＾＋を入力として関数Ｆ＿７を実行する。得られる値を関数値（Ｒ＾＋）と呼ぶ。
そして、照合部７２１は、関数値（Ｒ＾＋）を暗号化タグＣＴに含まれる検証要素ＣＴ＿Ｖと比較する。
関数値（Ｒ＾＋）と検証要素ＣＴ＿Ｖの一致は、暗号化タグＣＴに埋め込まれた登録キーワードＷが属性情報Ａと一致して、且つ、検索クエリＳＱに埋め込まれた検索キーワードｗが属性情報Ｂと一致することを意味する。
関数値（Ｒ＾＋）と一致する検証要素ＣＴ＿Ｖを有する暗号化タグＣＴが該当暗号化タグＣＴである。
【０１９５】
検証式は以下のように表すことができる。ｉは１以上ｋ以下の整数である。
ＣＴ＿Ｖ  ＝  Ｆ＿７（Ｒ＿１＾（＋）・・・（＋）Ｒ＿ｋ＾）
Ｒ＿ｉ＾  ＝  Ｆ＿６（ＳＱ＿ｉ，ＣＴ＿ＲＳ）（＋）ＣＴ＿｛ｉ，ＳＱＰ＿ｉ｝
【０１９６】
ステップＳ１７３において、抽出部７２２は、各該当暗号化タグＣＴに対応する暗号文データＣを抽出する。抽出される暗号文データＣを該当暗号文データＣと呼ぶ。
【０１９７】
ステップＳ１７４において、出力部７３０は、通信装置７０５を用いて、暗号化検索結果｛Ｃ｝を検索操作装置６００へ送信する。
暗号化検索結果｛Ｃ｝は、該当暗号文データＣの集合である。
【０１９８】
図２０に基づいて、データ削除（Ｓ１８０）を説明する。
データ削除（Ｓ１８０）は、登録装置５００とデータ管理装置７００とによって実行される処理である。但し、登録装置５００の代わりに検索操作装置６００が動作してもよい。
【０１９９】
ステップＳ１８１において、登録装置５００の受付部５１０は削除ファイル名を受け付ける。例えば、検索操作（Ｓ１６０）によって得られる平文Ｍの中のファイル名Ｆｉｌｅ（Ｍ）が削除ファイル名として使用される。
例えば、受付部５１０は、登録装置５００に入力される削除ファイル名を入出力インタフェース５０４を介して受け付ける。受付部５１０は、登録装置５００において実行されるアプリケーションプログラムから、削除ファイル名を受け付けてもよい。
但し、検索操作装置６００の受付部６１０が削除ファイル名を受け付けてもよい。
【０２００】
ステップＳ１８２において、登録装置５００の登録部５５０は、通信装置５０５を用いて、削除ファイル名をデータ管理装置７００へ送信する。
但し、検索操作装置６００の出力部６５０が通信装置６０５を用いて削除ファイル名をデータ管理装置７００へ送信してもよい。
【０２０１】
ステップＳ１８３において、データ管理装置７００の受付部７１０は、通信装置７０５を用いて、削除ファイル名を受信する。
【０２０２】
ステップＳ１８４において、データ管理装置７００の管理部７４０は、削除ファイル名に対応する秘匿検索データを登録データベース７９１から削除する。
削除ファイル名に対応する秘匿検索データは、削除ファイル名と同じファイル名Ｆｉｌｅ（Ｍ）を有する。
【０２０３】
＊＊＊実施の形態１の効果＊＊＊
実施の形態１によって以下のような効果を奏する。
暗号文を復号することなくキーワード検索ができる。
利用者の属性情報毎に異なる鍵を生成できる。そのため、マルチユーザ型の共通鍵方式を構成できる。
利用者の鍵を用いて暗号文の復号権限を制御できる。鍵に含まれる属性情報を分離しにくいため、複数の正規ユーザによる結託攻撃に対する耐性を向上できる。つまり、マルチユーザ型の共通鍵方式の安全性を向上できる。
属性情報の中の複数の属性値がいくつかのブロックに集約された後に鍵が生成される。これにより、鍵の長さを属性情報に比例しないように抑えることができる。
検索位置情報および復号位置情報を生成することによって、検索および復号を効率化することができる。
【０２０４】
実施の形態１によって以下のような効果を奏する。
ユーザ鍵装置４００は、属性情報をいくつかの部分にまとめてベクトル化したデータ（集約情報、汎化情報）を不可逆変換してユーザ鍵を生成する。
登録装置５００は、このユーザ鍵を用いて暗号文データおよび暗号化タグを生成する。
検索操作装置６００は、このユーザ鍵を用いて検索クエリを生成する。
これにより、結託攻撃に対してマルチユーザ型の共通鍵方式の安全性が向上する。
【０２０５】
＊＊＊実施の形態の補足＊＊＊
図２１に基づいて、マスター鍵装置２００のハードウェア構成を説明する。
マスター鍵装置２００は処理回路２０９を備える。
処理回路２０９は、受付部２１０と生成部２２０と出力部２３０とを実現するハードウェアである。
処理回路２０９は、専用のハードウェアであってもよいし、メモリ２０２に格納されるプログラムを実行するプロセッサ２０１であってもよい。
【０２０６】
処理回路２０９が専用のハードウェアである場合、処理回路２０９は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。
ＡＳＩＣは、Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略称である。
ＦＰＧＡは、Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙの略称である。
【０２０７】
マスター鍵装置２００は、処理回路２０９を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路２０９の機能を分担する。
【０２０８】
処理回路２０９において、一部の機能が専用のハードウェアで実現されて、残りの機能がソフトウェアまたはファームウェアで実現されてもよい。
【０２０９】
このように、マスター鍵装置２００の機能はハードウェア、ソフトウェア、ファームウェアまたはこれらの組み合わせで実現することができる。
【０２１０】
図２２に基づいて、登録鍵装置３００のハードウェア構成を説明する。
登録鍵装置３００は処理回路３０９を備える。
処理回路３０９は、受付部３１０と生成部３２０と出力部３３０とを実現するハードウェアである。
処理回路３０９は、専用のハードウェアであってもよいし、メモリ３０２に格納されるプログラムを実行するプロセッサ３０１であってもよい。
【０２１１】
処理回路３０９が専用のハードウェアである場合、処理回路３０９は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。
【０２１２】
登録鍵装置３００は、処理回路３０９を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路３０９の機能を分担する。
【０２１３】
処理回路３０９において、一部の機能が専用のハードウェアで実現されて、残りの機能がソフトウェアまたはファームウェアで実現されてもよい。
【０２１４】
このように、登録鍵装置３００の機能はハードウェア、ソフトウェア、ファームウェアまたはこれらの組み合わせで実現することができる。
【０２１５】
図２３に基づいて、ユーザ鍵装置４００のハードウェア構成を説明する。
ユーザ鍵装置４００は処理回路４０９を備える。
処理回路４０９は、受付部４１０と生成部４２０と出力部４３０とを実現するハードウェアである。
処理回路４０９は、専用のハードウェアであってもよいし、メモリ４０２に格納されるプログラムを実行するプロセッサ４０１であってもよい。
【０２１６】
処理回路４０９が専用のハードウェアである場合、処理回路４０９は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。
【０２１７】
ユーザ鍵装置４００は、処理回路３０９を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路４０９の機能を分担する。
【０２１８】
処理回路４０９において、一部の機能が専用のハードウェアで実現されて、残りの機能がソフトウェアまたはファームウェアで実現されてもよい。
【０２１９】
このように、ユーザ鍵装置４００の機能はハードウェア、ソフトウェア、ファームウェアまたはこれらの組み合わせで実現することができる。
【０２２０】
図２４に基づいて、登録装置５００のハードウェア構成を説明する。
登録装置５００は処理回路５０９を備える。
処理回路５０９は、受付部５１０と生成部５２０と登録部５３０とを実現するハードウェアである。
処理回路５０９は、専用のハードウェアであってもよいし、メモリ５０２に格納されるプログラムを実行するプロセッサ５０１であってもよい。
【０２２１】
処理回路５０９が専用のハードウェアである場合、処理回路５０９は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。
【０２２２】
登録装置５００は、処理回路５０９を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路５０９の機能を分担する。
【０２２３】
処理回路５０９において、一部の機能が専用のハードウェアで実現されて、残りの機能がソフトウェアまたはファームウェアで実現されてもよい。
【０２２４】
このように、登録装置５００の機能はハードウェア、ソフトウェア、ファームウェアまたはこれらの組み合わせで実現することができる。
【０２２５】
図２５に基づいて、検索操作装置６００のハードウェア構成を説明する。
検索操作装置６００は処理回路６０９を備える。
処理回路６０９は、受付部６１０と生成部６２０と要求部６３０と復号部６４０と出力部６５０とを実現するハードウェアである。
処理回路６０９は、専用のハードウェアであってもよいし、メモリ６０２に格納されるプログラムを実行するプロセッサ６０１であってもよい。
【０２２６】
処理回路６０９が専用のハードウェアである場合、処理回路６０９は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。
【０２２７】
検索操作装置６００は、処理回路６０９を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路６０９の機能を分担する。
【０２２８】
処理回路６０９において、一部の機能が専用のハードウェアで実現されて、残りの機能がソフトウェアまたはファームウェアで実現されてもよい。
【０２２９】
このように、検索操作装置６００の機能はハードウェア、ソフトウェア、ファームウェアまたはこれらの組み合わせで実現することができる。
【０２３０】
図２６に基づいて、データ管理装置７００のハードウェア構成を説明する。
データ管理装置７００は処理回路７０９を備える。
処理回路７０９は、受付部７１０と検索部７２０と出力部７３０と管理部７４０とを実現するハードウェアである。
処理回路７０９は、専用のハードウェアであってもよいし、メモリ７０２に格納されるプログラムを実行するプロセッサ７０１であってもよい。
【０２３１】
処理回路７０９が専用のハードウェアである場合、処理回路７０９は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡまたはこれらの組み合わせである。
【０２３２】
データ管理装置７００は、処理回路７０９を代替する複数の処理回路を備えてもよい。複数の処理回路は、処理回路７０９の機能を分担する。
【０２３３】
処理回路７０９において、一部の機能が専用のハードウェアで実現されて、残りの機能がソフトウェアまたはファームウェアで実現されてもよい。
【０２３４】
このように、データ管理装置７００の機能はハードウェア、ソフトウェア、ファームウェアまたはこれらの組み合わせで実現することができる。
【０２３５】
各実施の形態は、好ましい形態の例示であり、本開示の技術的範囲を制限することを意図するものではない。各実施の形態は、部分的に実施してもよいし、他の形態と組み合わせて実施してもよい。フローチャート等を用いて説明した手順は、適宜に変更してもよい。
【０２３６】
実施の形態で説明された各装置の要素である「部」は、「処理」または「工程」と読み替えてもよい。
【符号の説明】
【０２３７】
１００  秘匿検索システム、１０１  ネットワーク、２００  マスター鍵装置、２０１  プロセッサ、２０２  メモリ、２０３  補助記憶装置、２０４  入出力インタフェース、２０５  通信装置、２０９  処理回路、２１０  受付部、２２０  生成部、２３０  出力部、２９０  記憶部、３００  登録鍵装置、３０１  プロセッサ、３０２  メモリ、３０３  補助記憶装置、３０４  入出力インタフェース、３０５  通信装置、３０９  処理回路、３１０  受付部、３２０  生成部、３３０  出力部、３９０  記憶部、４００  ユーザ鍵装置、４０１  プロセッサ、４０２  メモリ、４０３  補助記憶装置、４０４  入出力インタフェース、４０５  通信装置、４０９  処理回路、４１０  受付部、４２０  生成部、４２１  集約情報生成部、４２２  ユーザ鍵生成部、４３０  出力部、４９０  記憶部、５００  登録装置、５０１  プロセッサ、５０２  メモリ、５０３  補助記憶装置、５０４  入出力インタフェース、５０５  通信装置、５０９  処理回路、５１０  受付部、５２０  生成部、５２１  乱数生成部、５２２  集約情報生成部、５２３  汎化情報生成部、５２４  暗号文データ生成部、５２５  キーワード生成部、５２６  暗号化タグ生成部、５３０  登録部、５９０  記憶部、６００  検索操作装置、６０１  プロセッサ、６０２  メモリ、６０３  補助記憶装置、６０４  入出力インタフェース、６０５  通信装置、６０９  処理回路、６１０  受付部、６２０  生成部、６２１  集約フラグ生成部、６２２  位置情報生成部、６２３  検索クエリ生成部、６３０  要求部、６４０  復号部、６４１  集約フラグ生成部、６４２  位置情報生成部、６４３  検索結果復号部、６５０  出力部、６９０  記憶部、７００  データ管理装置、７０１  プロセッサ、７０２  メモリ、７０３  補助記憶装置、７０４  入出力インタフェース、７０５  通信装置、７０９  処理回路、７１０  受付部、７２０  検索部、７２１  照合部、７２２  抽出部、７３０  出力部、７４０  管理部、７９０  記憶部、７９１  登録データベース。
【要約】
登録装置（５００）は、平文と、前記平文を参照する権限を有する利用者の属性情報と、検索クエリを生成するためのユーザ鍵の生成時に使用される登録鍵と、を受け付ける。前記登録装置は、前記属性情報に含まれる複数の属性値を集約することによって、１つ以上の集約値を示す集約情報を生成する。前記登録装置は、前記集約情報に含まれる各集約値を汎化することによって、各集約値に対する複数の汎化値を示す汎化情報を生成する。前記登録装置は、前記平文と前記属性情報と前記汎化情報と前記登録鍵とを用いて、暗号化された前記平文を含んだ暗号文データを生成する。前記登録装置は、前記暗号文データをデータベースに登録する。【図１】
0006987330.tif 000002
【図２】
0006987330.tif 000003
【図３】
0006987330.tif 000004
【図４】
0006987330.tif 000005
【図５】
0006987330.tif 000006
【図６】
0006987330.tif 000007
【図７】
0006987330.tif 000008
【図８】
0006987330.tif 000009
【図９】
0006987330.tif 000010
【図１０】
0006987330.tif 000011
【図１１】
0006987330.tif 000012
【図１２】
0006987330.tif 000013
【図１３】
0006987330.tif 000014
【図１４】
0006987330.tif 000015
【図１５】
0006987330.tif 000016
【図１６】
0006987330.tif 000017
【図１７】
0006987330.tif 000018
【図１８】
0006987330.tif 000019
【図１９】
0006987330.tif 000020
【図２０】
0006987330.tif 000021
【図２１】
0006987330.tif 000022
【図２２】
0006987330.tif 000023
【図２３】
0006987330.tif 000024
【図２４】
0006987330.tif 000025
【図２５】
0006987330.tif 000026
【図２６】
0006987330.tif 000027