暗号化された情報のためのキーワード検索システム、キーワード検索方法、検索要求装置、検索代行装置、プログラム、記録媒体
【課題】例えば部分一致検索が可能な検索可能暗号技術を提供する。
【解決手段】暗号情報Ｃ１に、当たりか否かを識別可能な情報Ｒ１と、情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求側で、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成し、検索代行側で、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する。述語暗号方式における述語論理は、部分一致検索方式に対応して構成される。
【解決手段】暗号情報Ｃ１に、当たりか否かを識別可能な情報Ｒ１と、情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求側で、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成し、検索代行側で、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する。述語暗号方式における述語論理は、部分一致検索方式に対応して構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化された情報（以下、暗号情報という）に対するキーワード検索を行うことができる検索可能暗号技術に関し、より詳しくは、完全一致検索以外のキーワード検索（例えば部分一致検索）も可能な検索可能暗号技術に関する。
【背景技術】
【０００２】
暗号情報に対して当該暗号情報を復号することなくキーワード検索を行い、この検索結果を得る検索可能暗号技術としてＰＥＫＳ（Public-key Encryption with Keyword Search）が知られている（非特許文献１、２参照）。例えば非特許文献２に開示されるＰＥＫＳは、暗号情報からはどのＩＤ（identification）で暗号化したかを知ることのできないＩＤベース暗号（anonymouse IBE）を利用することでＰＥＫＳを実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, "Public key encryption with keyword search", in proceedings of Eurocrypt 2004, LNCS 3027, pp. 506-522, 2004. [平成22年1月12日検索], インターネット <URL : http://crypto.stanford.edu/~dabo/papers/encsearch.pdf>
【非特許文献２】M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, and H. Shi, "Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions", Journal of Cryptology, 21(3), July 2008. [平成22年1月12日検索], インターネット<URL : http://www.cs.washington.edu/homes/yoshi/papers/PEKS/PEKS.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来技術では、暗号情報を例えばサーチエンジンに登録する際に予め指定されたキーワードと、検索の際に用いる検索用キーワードとが最初から最後まで完全に一致していることが検索のマッチングを意味するため、完全一致検索しかできなかった。
【０００５】
そこで本発明は、キーワードの完全一致検索に加えて完全一致検索以外のキーワード検索（例えば部分一致検索）も可能な検索可能暗号技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のキーワード検索システムは、少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムであって、検索対象となるキーワードを登録用キーワードとして、暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求装置は、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、復号鍵ｋ＊を検索代行装置へ送信する送信部とを含み、検索代行装置は、復号鍵ｋ＊を受信する受信部と、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する復号判定部とを含む。
【０００７】
具体例として、情報Ｒ２は、登録用キーワードから生成される述語暗号方式の属性で情報Ｒ１を暗号化して得られ、復号鍵ｋ＊は、検索用キーワードから生成される述語暗号方式の述語から生成される。
【０００８】
例えば、述語暗号方式は、属性ベクトルと述語ベクトルとの標準内積により述語論理の真偽が与えられる内積型述語暗号方式であるとし、この場合、属性は、登録用キーワードの最大文字数をｒとして、述語論理に最大ｄ−１回の論理和が許される場合に、ｒ個の属性変数Ｘ１，…，Ｘｒからなる次数ｄ以下の単項式をすべて辞書式順序で並べた順に各成分とした変数ベクトルＸｒ，ｄに登録用キーワードに含まれる文字を設定して得られる属性ベクトルであり、述語は、述語論理を属性変数と検索用キーワードに含まれる文字を用いて多項式で表現した述語多項式の係数を、変数ベクトルＸｒ，ｄの成分に対応する順に並べたものを成分として持つ述語ベクトルである。
【０００９】
述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数、ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）として、
《１》検索方式が完全一致検索方式である場合、述語多項式は、
【数１】
で与えられ、
《２》検索方式が前方一致検索方式である場合、述語多項式は、
【数２】
で与えられ、
《３》検索方式が後方一致検索方式である場合、述語多項式は、
【数３】
で与えられ、
《４》検索方式が部分一致検索方式である場合、述語多項式は、
【数４】
で与えられる。
【００１０】
あるいは、ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を文字列終端記号ＥＤとして、属性ベクトルは、ｒ個の部分キーワードＷｉに対応してｒ個生成され、暗号情報Ｃ１には、当たりか否かを識別可能なｒ個の情報Ｒ１（以下、Ｒ１[ｉ]（１≦ｉ≦ｒ）とする）と、当該情報Ｒ１[ｉ]を部分キーワードＷｉで暗号化して得られるｒ個の情報Ｒ２（以下、Ｒ２[ｉ]（１≦ｉ≦ｒ）とする）との組である検索用情報Ｃ２（以下、Ｃ２[ｉ]＝（Ｒ１[ｉ]，Ｒ２[ｉ]）（１≦ｉ≦ｒ）とする）が添付されており、述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》検索方式が完全一致検索方式である場合、述語多項式は、
【数５】
で与えられ、
《２》検索方式が前方一致検索方式である場合、述語多項式は、
【数６】
で与えられ、
《３》検索方式が後方一致検索方式である場合、述語多項式は、
【数７】
で与えられ、
《４》検索方式が部分一致検索方式である場合、述語多項式は、
【数８】
で与えられ、
復号判定部は、１≦ｉ≦ｒの各ｉについて、情報Ｒ２[ｉ]を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１[ｉ]に一致するか否かを判定する。
【００１１】
あるいは、ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を文字列終端記号ＥＤとして、述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》検索方式が完全一致検索方式である場合、述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数９】
で与えられ、
《２》検索方式が前方一致検索方式である場合、述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数１０】
で与えられ、
《３》検索方式が後方一致検索方式である場合、述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋２）の述語多項式
【数１１】
で与えられ、
《４》検索方式が部分一致検索方式である場合、述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋３）の述語多項式
【数１２】
で与えられ、
復号鍵ｋ＊は、ｕ個の述語多項式に対応してｕ個生成され（以下、これをｋ＊[c]（１≦ｃ≦ｕ）とする）、復号判定部は、１≦ｃ≦ｕの各ｃについて、情報Ｒ２を復号鍵ｋ＊[c]で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する。
【００１２】
本発明のキーワード検索方法は、少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムおけるキーワード検索方法であって、検索対象となるキーワードを登録用キーワードとして、暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求装置の鍵生成部が、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成ステップと、検索要求装置の送信部が、復号鍵ｋ＊を検索代行装置へ送信する送信ステップと、検索代行装置の受信部が、復号鍵ｋ＊を受信する受信ステップと、検索代行装置の復号判定部が、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する復号判定ステップとを有する。
【００１３】
また本発明の検索要求装置は、検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる検索要求装置であって、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、復号鍵ｋ＊を検索代行装置へ送信する送信部とを含む。
【００１４】
また本発明の検索代行装置は、検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる検索代行装置であって、検索用キーワードを用いて生成された、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を、検索要求装置から受信する受信部と、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する復号判定部とを含む。
【００１５】
また、本発明の検索要求装置としてコンピュータを機能させるプログラムによって、コンピュータを検索要求装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを検索要求装置として機能させることや、プログラムを流通させることなどが可能になる。同様に、本発明の検索代行装置としてコンピュータを機能させるプログラムによって、コンピュータを検索代行装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを検索代行装置として機能させることや、プログラムを流通させることなどが可能になる。
【発明の効果】
【００１６】
本発明に拠れば、暗号情報Ｃ１に、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求側で、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成し、検索代行側で、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定するところ、検索方式に対応した述語論理の構成により、キーワードの完全一致検索に加えて完全一致検索以外のキーワード検索（例えば部分一致検索）も可能となっている。
【図面の簡単な説明】
【００１７】
【図１】実施形態に関るキーワード検索システムの構成図。
【図２】実施形態に関るキーワード検索方法の処理手順を示す図。
【図３】変形例１に関るキーワード検索方法の処理手順を示す図。
【図４】変形例２に関るキーワード検索方法の処理手順を示す図。
【図５】実施形態に関る暗号情報生成装置、検索要求装置、検索代行装置、保管装置の機能ブロック図。
【発明を実施するための形態】
【００１８】
図面を参照して本発明の実施形態を説明する。
なお、以下に説明する情報処理では、文字列を含む情報が暗号化の対象となるが、暗号処理の実際では、人間が意味内容を認識可能なテキスト情報である文字そのものが暗号化されるのではなく、例えば当該文字に割り当てられている文字コード情報（EUC-JP、Shift_JIS、UTF-8などのバイト表現）が暗号化の対象となる。従って、後述の説明において例えば変数Ｘに文字ｗを代入ないし設定する（Ｘ＝ｗ）とは、テキスト情報としての文字ｗを変数Ｘに代入ないし設定することではなく、文字コード情報としての文字ｗを変数Ｘに代入ないし設定することと理解するべきである。このことは暗号処理の常套手段であるから、その詳細な説明を省略する。また、この明細書では、ベクトルの表記として慣用的にベクトルであることを示す記号“→”を省略している場合がある。従って、或る記号がベクトルであるか否かは明細書全体の記載から合理的に理解されたい。
【００１９】
［キーワード検索システム］
この実施形態のキーワード検索システム１は、図１に示すように、暗号情報生成装置１００と、検索要求装置２００と、検索代行装置３００と、保管装置４００とを少なくとも含んで構成される。これらの各装置は、例えばインターネットである通信網５を介して相互に通信可能とされている。
【００２０】
キーワード検索システム１におけるキーワード検索処理を、図２を参照しながら叙述する。各装置の機能構成については、図５を参照されたい。
【００２１】
《暗号情報生成プロセス》
暗号情報生成装置１００の暗号情報生成部１０１は、文字列を含む情報Ｍを暗号化して暗号情報Ｃ１を得る（ステップＳ１）。この暗号方式（Ｅｎｃ，Ｄｅｃ）に限定はない。この暗号方式として、例えば共通鍵暗号方式や公開鍵暗号方式を利用できる。共通鍵暗号方式の場合、情報Ｍは、暗号情報生成装置１００と検索装置２００との間で共有される共通鍵で暗号化される。また、公開鍵暗号方式の場合、情報Ｍは検索装置２００の公開鍵で暗号化される。つまり、暗号情報Ｃ１を得るための情報処理は、暗号化アルゴリズムＥｎｃに従い、Ｃ１＝Ｅｎｃ(Ｍ)である。
【００２２】
暗号情報生成装置１００の検索用情報生成部１０２は、検索が当たりか否かを識別可能な情報Ｒ１を任意に設定し（例えば情報Ｒ１に数値としてのゼロを設定する）、この情報Ｒ１を登録用キーワードＷで述語暗号方式により暗号化して情報Ｒ２を得る（ステップＳ２）。登録用キーワードは、例えばユーザによって予め設定される、検索対象となるキーワードである。検索用情報Ｃ２はＣ２＝（Ｒ１，Ｒ２）である。情報Ｒ２を得る暗号化処理は例えば内積型述語暗号方式によって実現される。内積型述語暗号方式の詳細について、例えば参考文献Ａを参照されたい。
（参考文献Ａ）T. Okamoto and K. Takashima, "Hierarchical predicate encryption for inner-products", In ASIACRYPT, pp.214-231, 2009.
【００２３】
ここでは、内積型述語暗号方式を用いた暗号化処理の一例を説明する。
述語暗号は、送信者による暗号化の過程で暗号メッセージに或る情報Ｇが組み込まれ、当該情報Ｇと特定の関係を満たす情報Ｈを持つ受信者が、暗号メッセージの復号や、メッセージを知ることなくメッセージに関する情報を取得することができる方式である。送信者は、暗号化の際に、必ずしも受信者の持つ情報Ｈを知っている必要はない。また、送信者は、必ずしも、暗号化する前に受信者を特定している必要もない。送信者は、自由に、能動的に、主導権を持って、情報Ｇを決めることができる。講学的に、情報Ｇは属性Ｉ（変数）として、情報Ｈは述語論理ｆ（命題関数、ブール関数）として表される。復号に際し、情報Ｇと情報Ｈとが満たすべき特定の関係は、例えばｆ(Ｉ)＝１である。内積型述語暗号方式では、属性ベクトルと述語ベクトルとの標準内積により述語論理の真偽が与えられる。ここでは、述語論理を多変数多項式によって表現する。この多変数多項式を述語多項式とも呼ぶ。属性を表す変数を属性変数と呼ぶ。
【００２４】
例えば３個の属性変数Ｘ１，Ｘ２，Ｘ３が、（Ｘ１＝ｗ１またはＸ２＝ｗ２、かつＸ３＝ｗ３）の場合にのみ１を返す述語多項式ｐ(Ｘ１，Ｘ２，Ｘ３)は乱数ｒｄを用いて式（１）で表される。式（１）では論理和ORは積の演算で論理積ANDは和の演算で表されている。
ｐ(Ｘ１，Ｘ２，Ｘ３)＝(Ｘ１−ｗ１)(Ｘ２−ｗ２)＋rd(Ｘ３−ｗ３) （１）
【００２５】
ｒ個の属性変数Ｘ１，Ｘ２，…，Ｘｒに対してｄ−１回の論理和を扱うためには、Ｘ１，Ｘ２，…，Ｘｒからなる次数ｄ以下の単項式をすべて用意する必要がある。この単項式を１を含めて辞書式順序で並べた順に各成分としたベクトルを、属性変数Ｘ１，Ｘ２，…，Ｘｒに対するｄ次の変数ベクトルと呼び、Ｘｒ，ｄと表す。辞書式順序とは、ｄ個の同一の順序集合｛１，Ｘ１，Ｘ２，…，Ｘｒ｝の直積集合に順序を導入したものである。辞書式順序は例えば素朴集合論において論じられ公知であるから、これ以上の詳細な説明は行わない。
【００２６】
ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）とする。属性変数Ｘｉ（１≦ｉ≦ｒ）について、Ｘｉ＝ｗｉとする。このとき、ベクトルｘが変数ベクトルＸｒ，ｄ上の属性ベクトルｘであるとは、式（２）を満足する場合をいう。なお、この実施形態ではｒはシステム仕様として固定値（１≦ｒを満たす整数）に設定される。登録用キーワードＷの長さ（文字数）がｒに満たない場合は、ｒに達するまでnull文字でパディングする。具体例として、ｒ＝２，ｄ＝２，Ｘｒ，ｄ＝(１，Ｘ１，Ｘ２，Ｘ１２，Ｘ１Ｘ２，Ｘ２２)の場合、属性ベクトルｘはｘ＝(１，ｗ１，ｗ２，ｗ１２，ｗ１ｗ２，ｗ２２)となる。
【数１３】
【００２７】
ｒ個の属性変数Ｘ１，Ｘ２，…，Ｘｒで最大ｄ回の論理和が許されているとき、述語論理を表す属性変数からなる多変数多項式ｐ(Ｘα，…，Ｘβ)（１≦α≦β≦ｒ）を、変数ベクトルＸｒ，ｄ上の述語多項式と呼ぶ。
【００２８】
この変数ベクトルＸｒ，ｄ上の述語多項式ｐ(Ｘα，…，Ｘβ)を、変数ベクトルＸｒ，ｄと述語ベクトルｖとの標準内積<Ｘｒ，ｄ，ｖ>と考えて、ｐ(Ｘα，…，Ｘβ)の係数を、変数ベクトルＸｒ，ｄの成分に対応する順に述語ベクトルｖの成分とする。述語ベクトルｖのこれら以外の成分を０とする。この述語ベクトルを変数ベクトルＸｒ，ｄ上の述語ベクトルとも呼ぶ。
【００２９】
ｄは１≦ｄ≦ｒを満たす固定値にシステム仕様として設定されるが、この実施形態では、ｄ＝ｒとする。つまり、述語多項式において登録用キーワードの最大文字数相当の論理和を許容する。
【００３０】
さて、内積型述語暗号方式を用いた暗号化処理の一例は次のとおりである。検索用情報生成部１０２は、式（３）に従って登録用キーワードＷから属性ベクトルｘを生成する。この式（３）は、変数ベクトルＸｒ，ｒにおいてＸｉ＝ｗｉ（１≦ｉ≦ｒ）とすることを意味する。
【数１４】
【００３１】
ｘ＝(ｘ１，ｘ２，…，ｘｎ)∈Ｆqnとする。つまり、ｘｉ（１≦ｉ≦ｎ）はｎ次元直積Ｆqnの元とする。Ｆqは有限体であり、ｑは素数または素数の冪乗値である。検索用情報生成部１０２は、δ１，δ２，ζをＦqからランダムに選択し、式（４）を計算することにより、情報Ｒ２を得る。情報Ｒ２はＲ２＝（cipher1，cipher2）である。
【数１５】
【００３２】
公開パラメータは、例えば位数ｑの巡回群Ｇ1，Ｇ2，ＧTの生成元ｇ1，ｇ2，ｇT、非退化性を持つ双線形写像ｅ：Ｇ1×Ｇ2→ＧT（但し、e(g1,g2)=gT）、位数ｑ、（ｎ＋３）次元のベクトル空間Ｖの直交基底Ｂを含む。秘密鍵は、双対ベクトル空間Ｖ＊の直交基底Ｂ＊を含む。代数構造を有限体Ｆqとする場合、ｑは素数または素数の冪乗値である。双線形写像ｅは例えばTateペアリングやWeilペアリングである。
【００３３】
直交基底Ｂおよび直交基底Ｂ＊について説明を加える。
（ｎ＋３）次元のベクトル空間Ｖの任意の元が、式（５）のように巡回群Ｇ1の（ｎ＋３）次元直積Ｇ1n+3の元として表されるとする。（ｎ＋３）次元のベクトル空間Ｖの任意の元は、（ｎ＋３）次元のベクトル空間Ｖの標準基底Ａを用いて式（６）のように表すこともできる。ただし、ａiは（ｎ＋３）次元直積Ｇ1n+3の元、ｚiは（ｎ＋３）次元直積Ｆqn+3の元とする。また、１は加法単位元とする。
【数１６】
【００３４】
直交基底Ｂは、式（７）のように、標準基底Ａに（ｎ＋３）次正方行列Ｘを作用させたものとして得られる。記号Ｔは転置を表す。なお、行列Ｘは秘密鍵と同様に秘密とされる。
【数１７】
【００３５】
同様に、ベクトル空間Ｖと双対な双対ベクトル空間Ｖ＊の任意の元が、式（８）のように巡回群Ｇ2の（ｎ＋３）次元直積Ｇ2n+3の元として表されるとする。双対ベクトル空間Ｖ＊の任意の元は、双対ベクトル空間Ｖ＊の標準基底Ａ＊を用いて式（９）のように表すこともできる。ただし、ａi＊は（ｎ＋３）次元直積Ｇ2n+3の元、ｙi＊は（ｎ＋３）次元直積Ｆqn+3の元とする。また、１は加法単位元とする。
【数１８】
【００３６】
直交基底Ｂ＊は、式（１０）のように、標準基底Ａ＊に（ｎ＋３）次正方行列T(Ｘ-1)を作用させたものとして得られる。記号Ｅは単位行列を表す。
【数１９】
【００３７】
暗号情報生成装置１００の送信部１０８は、暗号情報Ｃ１と検索用情報Ｃ２とを一組として保管装置４００へ送信する（ステップＳ３）。保管装置４００の受信部４０９は、暗号情報と検索用情報との組（Ｃ１，Ｃ２）を受信する（ステップＳ４）。保管装置４００の記憶部４０１には、通常、暗号情報生成装置１００から受信した複数の（Ｃ１，Ｃ２）が記憶されている。さらに言えば、保管装置４００の記憶部４０１には、一般的に、複数の暗号情報生成装置から受信した複数の（Ｃ１，Ｃ２）が記憶されている。各組（Ｃ１，Ｃ２）には固有のインデックスが割り当てられている。
【００３８】
《検索要求プロセス》
検索要求装置２００の鍵生成部２０１は、上記秘密鍵（直交基底Ｂ＊）と、例えばユーザによって入力された検索用キーワードＳおよびユーザによって指定された検索方式＄の述語論理とを用いて、検索用情報Ｃ２に含まれる情報Ｒ２を復号するための復号鍵ｋ＊を生成する（ステップＳ５）。上記秘密鍵（直交基底Ｂ＊）は検索要求装置２００の秘密鍵である。
【００３９】
復号鍵ｋ＊を得るための情報処理は、暗号情報生成装置１００の検索用情報生成部１０２が実施した述語暗号方式に対応する鍵生成アルゴリズムに従う。この実施形態では、復号鍵ｋ＊を得るための情報処理は、内積型述語暗号方式によって実現される。具体的には、鍵生成部２０１は、まず、変数ベクトルＸｒ，ｒ上の述語ベクトルｖを生成する。
【００４０】
ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とする。もし、ｔ＜ｒならば、ｓｉ＝０（ｔ＜ｉ≦ｒ）とする。鍵生成部２０１は、後述するように検索方式＄に対応するＸｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)を決定して、Ｘｒ，ｒ上の述語ベクトルｖを求める。Ｘｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)からＸｒ，ｒ上の述語ベクトルｖを求める方法は既述のとおりである。
【００４１】
ここで各検索方式＄の述語多項式について説明を加える。rdi,j（１≦ｉ，ｊ≦ｒ）は乱数である。
【００４２】
《１》完全一致検索方式（ｃｍ）
完全一致検索方式は、任意のｉ（１≦ｉ≦ｒ）についてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
完全一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１１）で与えられる。
【数２０】
【００４３】
《２》前方一致検索方式（ｆｍ）
前方一致検索方式は、任意のｉ（１≦ｉ≦ｔ）についてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
前方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１２）で与えられる。
【数２１】
【００４４】
《３》後方一致検索方式（ｂｍ）
後方一致検索方式は、任意のｉ（ｒ−ｔ＋１≦ｉ≦ｒ）についてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
後方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１３）で与えられる。
【数２２】
【００４５】
《４》部分一致検索方式（ｐｍ）
部分一致検索方式は、或るｊが存在して（ｊ≦ｉ≦ｔ＋ｊ−１≦ｒ）を満たすすべてのｉについてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
部分一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１４）で与えられる。
【数２３】
【００４６】
《５》完全不一致検索方式（ｎｃｍ）
完全不一致検索方式は、すべてのｉ（１≦ｉ≦ｒ）についてｗｉ＝ｓｉが成立しない場合を検索する検索方式である。これは完全一致検索方式でヒットした検索結果の補集合として得られる。
【００４７】
《６》「含まない」検索方式（ｎｐｍ）
「含まない」検索方式は、ｊ≦ｉ≦ｔ＋ｊ−１≦ｒを満たすすべてのｉについてｗｉ＝ｓｉが成立するようなｊが存在しない場合を検索する検索方式である。これは部分一致検索方式でヒットした検索結果の補集合として得られる。
【００４８】
次に、鍵生成部２０１は、述語ベクトルｖ＝(ｖ１，ｖ２，…，ｖｎ)∈Ｆqnに対して、σ，ηをＦqからランダムに選択し、式（１５）を計算することにより、復号鍵ｋ＊を得る。
【数２４】
【００４９】
検索要求装置２００の送信部２０８は、復号鍵ｋ＊を検索代行装置３００へ送信する（ステップＳ６）。
【００５０】
《検索代行プロセス》
検索代行装置３００の受信部３０９は、復号鍵ｋ＊を受信する（ステップＳ７）。
【００５１】
検索代行装置３００の制御部３０５は、送信部３０８を制御して、保管装置４００に対して保管装置４００の記憶部４０１に記憶されているすべての検索用情報を検索代行装置３００へ送信するように要求し、これを受けて保管装置４００の送信部４０８は記憶部４０１に記憶されているすべての検索用情報をインデックスとともに検索代行装置３００へ送信し、検索代行装置３００の受信部３０９がこれらを受信する（ステップＳ８）。
【００５２】
検索代行装置３００の復号判定部３０１は、すべての検索用情報を復号判定処理の対象とし、復号鍵ｋ＊を用いて検索用情報を個別に復号して検索が当たりか否かを判定する（ステップＳ９）。具体的には、復号判定部３０２は、すべての検索用情報について、式（１６）に従って情報Ｒを求め（復号処理）、Ｒ＝Ｒ１の成否を判定する（判定処理）。
【数２５】
【００５３】
検索代行装置３００の送信部３０８は、Ｒ＝Ｒ１が成立した検索用情報のインデックスを検索要求装置２００へ送信する（ステップＳ１０）。
【００５４】
《検索結果受信プロセス》
検索要求装置２００の受信部２０９は、Ｒ＝Ｒ１が成立した検索用情報のインデックスを受信する（ステップＳ１１）。
【００５５】
検索要求装置２００の制御部２０５は、送信部２０８を制御して、保管装置４００に対して、保管装置４００の記憶部４０１に記憶されている、検索代行装置３００から受信したインデックスに対応する暗号情報を検索要求装置２００へ送信するように要求し、これを受けて保管装置４００の送信部４０８は当該インデックスに対応する暗号情報を検索要求装置２００へ送信し、検索要求装置２００の受信部２０９がこれらを受信する（ステップＳ１２）。
【００５６】
検索要求装置２００の復号部２０６は、必要に応じて、保管装置４００から受信した暗号情報Ｃ１を復号して情報Ｍを得る（ステップＳ１３）。情報Ｍを得るための情報処理は、暗号情報生成装置１００の暗号情報生成部１０１が実施した暗号方式（Ｅｎｃ，Ｄｅｃ）に対応する復号アルゴリズムＤｅｃに従う。つまり、Ｍ＝Ｄｅｃ(Ｃ１)である。
【００５７】
＜変形例＞
上記実施形態では、変数ベクトルＸｒ，ｄの次元ｎは、ｉ次以下の単項式の総和がｒ文字からｑ文字（１≦ｑ≦ｉ）を選ぶ組み合わせの和になるので、式（１７）で表される。
【数２６】
【００５８】
式（１７）によると、変数ベクトルＸｒ，ｄの次元ｎは、登録用キーワードの文字数ｒと論理和の数ｄの階乗のオーダーで増加する。そこで、各変形例では、論理和を用いる検索でありながら論理和を用いない変数ベクトルＸｒ，１を構成する。このため各変形例では、登録用キーワードと検索用キーワードに、文字列開始記号としてＳＴ、文字列終端記号としてＥＤを導入する。なお、説明の便宜からこれらの記号をＳＴ、ＥＤというように２文字で表現したが、変形例では、文字列開始記号として１文字の長さの記号、文字列終端記号として１文字の長さの記号が設定されることに留意されたい。もちろん、これらの記号の長さを任意に設定してよいが、この場合、述語多項式の表現やそこに現れる添え字が変わるものの、実用上格別の意義を有しないので、通常、１文字分の長さの記号を設定すれば足りる。なお、変形例１については図３を、変形例２については図４を参照のこと。
【００５９】
[変形例１]
登録用キーワードＷの１文字目ｗ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｗmax+1をＥＤとする。登録用キーワードＷについて、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉと定義する。ここでnullｉはｉ−１個のnullを表す。Ｗｉのｊ番目の文字をｗｉ，ｊと表すことにする。
【００６０】
変形例１では、実施形態のステップＳ２の処理は、次のように変更される。暗号情報生成装置１００の検索用情報生成部１０２は、検索が当たりか否かを識別可能なｒ個の情報Ｒ１[ｉ]（１≦ｉ≦ｒ）を任意に設定し（例えばすべて数値としてのゼロとする）、この情報Ｒ１[ｉ]を部分キーワードＷｉで暗号化して情報Ｒ２[ｉ]を得る（ステップＳ２ａ）。具体的には、検索用情報生成部１０２は、式（１８）に従って、ｒ個の部分キーワードＷｉからｒ個の属性ベクトルｘｉ（１≦ｉ≦ｒ）を生成する。ｘｉ＝(ｘ１[i]，ｘ２[i]，…，ｘｎ[i])∈Ｆqnとする。
【数２７】
【００６１】
そして、検索用情報生成部１０２は、δ１，δ２，ζをＦqからランダムに選択し、式（１９）を計算することにより、情報Ｒ２[ｉ]を得る（１≦ｉ≦ｒ）。情報Ｒ２[ｉ]はＲ２[ｉ]＝（cipher1[i]，cipher2[i]）である（１≦ｉ≦ｒ）。
【数２８】
【００６２】
変形例１では、述語ベクトルは実施形態と同じように構成される。なお、検索用キーワードＳの１文字目ｓ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｓmax+1をＥＤとする。
【００６３】
変形例１では、実施形態のステップＳ３、Ｓ４の各処理は、次のように変更される。暗号情報生成装置１００の送信部１０８は、暗号情報Ｃ１とｒ個の検索用情報Ｃ２[ｉ]＝（Ｒ１[ｉ]，Ｒ２[ｉ]）とを一組として保管装置４００へ送信する（ステップＳ３ａ）。保管装置４００の受信部４０９は、暗号情報と検索用情報との組（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）を受信する（ステップＳ４ａ）。保管装置４００の記憶部４０１には、通常、暗号情報生成装置１００から受信した複数の（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）が記憶されている。さらに言えば、保管装置４００の記憶部４０１には、一般的に、複数の暗号情報生成装置から受信した複数の（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）が記憶されている。各組（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）には固有のインデックスが対応付けられている。
【００６４】
変形例１では、実施形態のステップＳ５の処理自体に変更はないが、各検索方式に対応する述語多項式ｐ(Ｘα，…，Ｘβ)が次のとおりに変更される。
【００６５】
《１》完全一致検索方式（ｃｍ）
変形例１では、完全一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２０）で与えられる。
【数２９】
【００６６】
《２》前方一致検索方式（ｆｍ）
変形例１では、前方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２１）で与えられる。
【数３０】
【００６７】
《３》後方一致検索方式（ｂｍ）
変形例１では、後方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２２）で与えられる。
【数３１】
【００６８】
《４》部分一致検索方式（ｐｍ）
変形例１では、部分一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２３）で与えられる。
【数３２】
【００６９】
《５》完全不一致検索方式（ｎｃｍ）と《６》「含まない」検索方式（ｎｐｍ）は実施形態と同じである。
【００７０】
変形例１では、実施形態のステップＳ６以降の各処理について、１個の暗号情報にｒ個の検索用情報が添付されていることを注意すれば、実質的な変更はない。なお、実施形態におけるステップＳ９の処理は、次のように変更される。検索代行装置３００の復号判定部３０１は、すべての検索用情報を復号判定処理の対象とし、復号鍵ｋ＊を用いて検索用情報を個別に復号して検索が当たりか否かを判定する（ステップＳ９ａ）。具体的には、復号判定部３０１は、すべての検索用情報について、式（２３ａ）に従って情報Ｒ[ｉ]を求め（復号処理）、Ｒ[ｉ]＝Ｒ１[ｉ]の成否を判定する（判定処理）。
【数３３】
【００７１】
変形例１によると、復号判定処理の回数は上述の実施形態と比較して一つの暗号情報につきｒ倍になるが、論理和の使用により変数ベクトルの次元が階乗オーダーで大きくなってしまうことに比べ定数倍の処理の増加で済むので、論理和を使用する検索の場合において上述の実施形態と比較してメリットが大きい。
【００７２】
[変形例２]
論理和を用いる検索でありながら論理和を用いない変数ベクトルＸｒ，１を構成するために、変形例２では、一つの検索用キーワードから複数の述語ベクトルを生成する（なお、諸条件により必ず複数の述語ベクトルが生成されるわけではない。ここでは、特徴的な場合を説明する観点から、生成される述語ベクトルは“複数”であるとして説明する）。各述語ベクトルに対応する復号鍵ｋ＊が生成される。つまり、特徴的な場合には複数の復号鍵ｋ＊が生成される。
【００７３】
登録用キーワードＷの１文字目ｗ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｗmax+1をＥＤとする。登録用キーワードＷについて、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉと定義する。ここでnullｉはｉ−１個のnullを表す。Ｗｉのｊ番目の文字をｗｉ，ｊと表すことにする。また、検索用キーワードＳの１文字目ｓ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｓmax+1をＥＤとする。
【００７４】
変形例２では、実施形態のステップＳ２、Ｓ５、Ｓ６、Ｓ７、Ｓ９の各処理は、次のように変更される。
【００７５】
暗号情報生成装置１００の検索用情報生成部１０２は、検索が当たりか否かを識別可能な情報Ｒ１を任意に設定し（例えば数値としてのゼロ）、この情報Ｒ１を登録用キーワードＷで暗号化して情報Ｒ２を得る（ステップＳ２ｂ）。具体的には、検索用情報生成部１０２は、式（２３ｂ）に従って、登録用キーワードＷから属性ベクトルｘを生成する。ｘ＝(ｘ１，ｘ２，…，ｘｎ)∈Ｆqnとする。
【数３４】
【００７６】
そして、検索用情報生成部１０２は、δ１，δ２，ζをＦqからランダムに選択し、式（２３ｃ）を計算することにより、情報Ｒ２を得る。情報Ｒ２はＲ２＝（cipher1，cipher2）である。
【数３５】
【００７７】
検索要求装置２００の鍵生成部２０１は、上記秘密鍵（直交基底Ｂ＊）と、例えばユーザによって入力された検索用キーワードＳおよびユーザによって指定された検索方式＄の述語論理とを用いて、検索用情報Ｃ２に含まれる情報Ｒ２を復号するための複数の復号鍵ｋ＊を生成する（ステップＳ５ｂ）。
【００７８】
ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とする。もし、ｔ＜ｒならば、ｓｉ＝０（ｔ＜ｉ≦ｒ）とする。鍵生成部２０１は、後述するように検索方式＄に対応するＸｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)を決定して、Ｘｒ，ｒ上の述語ベクトルｖを求める。Ｘｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)からＸｒ，ｒ上の述語ベクトルｖを求める方法は既述のとおりである。
【００７９】
変形例２では、実施形態と異なり、各検索方式に対応する述語多項式ｐ(Ｘα，…，Ｘβ)が次のとおりに変更される。
【００８０】
《１》完全一致検索方式（ｃｍ）
変形例２では、完全一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２４）で与えられる。
【数３６】
【００８１】
《２》前方一致検索方式（ｆｍ）
変形例２では、前方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２５）で与えられる。
【数３７】
【００８２】
《３》後方一致検索方式（ｂｍ）
変形例２では、後方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２６）で与えられる。なお、この場合、ｒ−ｔ＋２個の述語多項式が得られる。
【数３８】
【００８３】
《４》部分一致検索方式（ｐｍ）
変形例２では、部分一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２７）で与えられる。なお、この場合、ｒ−ｔ＋３個の述語多項式が得られる。
【数３９】
【００８４】
《５》完全不一致検索方式（ｎｃｍ）と《６》「含まない」検索方式（ｎｐｍ）は実施形態と同じである。
【００８５】
次に、鍵生成部２０１は、ｕ個の述語ベクトルｖ[c]＝(ｖ１[c]，ｖ２[c]，…，ｖｎ[c])∈Ｆqnに対して、σ，ηをＦqからランダムに選択し、式（２８）を計算することにより、ｕ個の復号鍵ｋ＊[c]を得る（１≦ｃ≦ｕ）。《１》と《２》と《５》の場合はｕ＝１である。《３》の場合はｕ＝ｒ−ｔ＋２である。《４》と《６》の場合はｕ＝ｒ−ｔ＋３である。
【数４０】
【００８６】
検索要求装置２００の送信部２０８は、ｕ個の復号鍵ｋ＊[c]を検索代行装置３００へ送信する（ステップＳ６ｂ）。検索代行装置３００の受信部３０９は、ｕ個の復号鍵ｋ＊[c]を受信する（ステップＳ７ｂ）。
【００８７】
検索代行装置３００の復号判定部３０１は、すべての検索用情報を復号判定処理の対象とし、ｕ個の復号鍵ｋ＊[c]を用いて検索用情報を個別に復号して検索が当たりか否かを判定する（ステップＳ９ｂ）。具体的には、復号判定部３０１は、すべての検索用情報について、式（２９）に従って情報Ｒ[c]を求め（復号処理）、Ｒ[c]＝Ｒ１（１≦ｃ≦ｕ）の成否を判定する（判定処理）。
【数４１】
【００８８】
変形例２では、１個の暗号情報に１個の検索用情報が添付されているものの、１個の検索用キーワードからｕ個の復号鍵ｋ＊[c]を生成するため、復号判定処理の回数は上述の実施形態と比較して一つの暗号情報につきｕ倍になるが、論理和の使用により変数ベクトルの次元が階乗オーダーで大きくなってしまうことに比べ定数倍の処理の増加で済むので、論理和を使用する検索の場合において上述の実施形態と比較してメリットが大きい。
【００８９】
上述の実施形態と各変形例では、検索代行装置３００は、複合判定処理において検索用情報と暗号情報との結びつきのみを把握できるだけなので、暗号情報の中身（情報Ｍ）や検索用キーワードＳが何であるのかということが検索代行装置３００に漏れることがない。
【００９０】
なお、上述の実施形態と各変形例では、暗号情報生成装置１００と検索要求装置２００を同一のエンティティとして実施することも可能である。この場合、上述の実施形態と各変形例において、暗号情報生成装置１００を検索要求装置２００に読み替えればよい。また、上述の実施形態と各変形例では、検索代行装置３００と保管装置４００を同一のエンティティとして実施することも可能である。この場合、上述の実施形態と各変形例において、保管装置４００を検索代行装置３００に読み替えればよい。これら両者の形態を組み合わせた変形例としてもよい。これらの場合、上述の実施形態と各変形例で説明した、暗号情報生成装置１００と検索要求装置２００との間の通信、検索代行装置３００と保管装置４００との間の通信がそれぞれ不要になる。
【００９１】
キーワード検索システムに含まれるハードウェアエンティティ（暗号情報生成装置、検索要求装置、検索代行装置、保管装置）は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００９２】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するＲＡＭやレジスタなどの記憶装置を単に「記憶部」とした。
【００９３】
ハードウェアエンティティでは、外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（例えば、暗号情報生成部、検索用情報生成部、鍵生成部、復号部、復号判定部、制御部など）を実現する。
【００９４】
各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成22年1月13日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/〉［平成22年1月13日検索］を参照のこと。）。
また、この点に関する文献として、参考文献Ｂを挙げることができる。
（参考文献Ｂ） H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【００９５】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００９６】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００９７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００９８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１００】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【技術分野】
【０００１】
本発明は、暗号化された情報（以下、暗号情報という）に対するキーワード検索を行うことができる検索可能暗号技術に関し、より詳しくは、完全一致検索以外のキーワード検索（例えば部分一致検索）も可能な検索可能暗号技術に関する。
【背景技術】
【０００２】
暗号情報に対して当該暗号情報を復号することなくキーワード検索を行い、この検索結果を得る検索可能暗号技術としてＰＥＫＳ（Public-key Encryption with Keyword Search）が知られている（非特許文献１、２参照）。例えば非特許文献２に開示されるＰＥＫＳは、暗号情報からはどのＩＤ（identification）で暗号化したかを知ることのできないＩＤベース暗号（anonymouse IBE）を利用することでＰＥＫＳを実現している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D. Boneh, G. Di Crescenzo, R. Ostrovsky, and G. Persiano, "Public key encryption with keyword search", in proceedings of Eurocrypt 2004, LNCS 3027, pp. 506-522, 2004. [平成22年1月12日検索], インターネット <URL : http://crypto.stanford.edu/~dabo/papers/encsearch.pdf>
【非特許文献２】M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, and H. Shi, "Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions", Journal of Cryptology, 21(3), July 2008. [平成22年1月12日検索], インターネット<URL : http://www.cs.washington.edu/homes/yoshi/papers/PEKS/PEKS.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来技術では、暗号情報を例えばサーチエンジンに登録する際に予め指定されたキーワードと、検索の際に用いる検索用キーワードとが最初から最後まで完全に一致していることが検索のマッチングを意味するため、完全一致検索しかできなかった。
【０００５】
そこで本発明は、キーワードの完全一致検索に加えて完全一致検索以外のキーワード検索（例えば部分一致検索）も可能な検索可能暗号技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のキーワード検索システムは、少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムであって、検索対象となるキーワードを登録用キーワードとして、暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求装置は、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、復号鍵ｋ＊を検索代行装置へ送信する送信部とを含み、検索代行装置は、復号鍵ｋ＊を受信する受信部と、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する復号判定部とを含む。
【０００７】
具体例として、情報Ｒ２は、登録用キーワードから生成される述語暗号方式の属性で情報Ｒ１を暗号化して得られ、復号鍵ｋ＊は、検索用キーワードから生成される述語暗号方式の述語から生成される。
【０００８】
例えば、述語暗号方式は、属性ベクトルと述語ベクトルとの標準内積により述語論理の真偽が与えられる内積型述語暗号方式であるとし、この場合、属性は、登録用キーワードの最大文字数をｒとして、述語論理に最大ｄ−１回の論理和が許される場合に、ｒ個の属性変数Ｘ１，…，Ｘｒからなる次数ｄ以下の単項式をすべて辞書式順序で並べた順に各成分とした変数ベクトルＸｒ，ｄに登録用キーワードに含まれる文字を設定して得られる属性ベクトルであり、述語は、述語論理を属性変数と検索用キーワードに含まれる文字を用いて多項式で表現した述語多項式の係数を、変数ベクトルＸｒ，ｄの成分に対応する順に並べたものを成分として持つ述語ベクトルである。
【０００９】
述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数、ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）として、
《１》検索方式が完全一致検索方式である場合、述語多項式は、
【数１】
で与えられ、
《２》検索方式が前方一致検索方式である場合、述語多項式は、
【数２】
で与えられ、
《３》検索方式が後方一致検索方式である場合、述語多項式は、
【数３】
で与えられ、
《４》検索方式が部分一致検索方式である場合、述語多項式は、
【数４】
で与えられる。
【００１０】
あるいは、ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を文字列終端記号ＥＤとして、属性ベクトルは、ｒ個の部分キーワードＷｉに対応してｒ個生成され、暗号情報Ｃ１には、当たりか否かを識別可能なｒ個の情報Ｒ１（以下、Ｒ１[ｉ]（１≦ｉ≦ｒ）とする）と、当該情報Ｒ１[ｉ]を部分キーワードＷｉで暗号化して得られるｒ個の情報Ｒ２（以下、Ｒ２[ｉ]（１≦ｉ≦ｒ）とする）との組である検索用情報Ｃ２（以下、Ｃ２[ｉ]＝（Ｒ１[ｉ]，Ｒ２[ｉ]）（１≦ｉ≦ｒ）とする）が添付されており、述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》検索方式が完全一致検索方式である場合、述語多項式は、
【数５】
で与えられ、
《２》検索方式が前方一致検索方式である場合、述語多項式は、
【数６】
で与えられ、
《３》検索方式が後方一致検索方式である場合、述語多項式は、
【数７】
で与えられ、
《４》検索方式が部分一致検索方式である場合、述語多項式は、
【数８】
で与えられ、
復号判定部は、１≦ｉ≦ｒの各ｉについて、情報Ｒ２[ｉ]を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１[ｉ]に一致するか否かを判定する。
【００１１】
あるいは、ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を文字列終端記号ＥＤとして、述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》検索方式が完全一致検索方式である場合、述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数９】
で与えられ、
《２》検索方式が前方一致検索方式である場合、述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数１０】
で与えられ、
《３》検索方式が後方一致検索方式である場合、述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋２）の述語多項式
【数１１】
で与えられ、
《４》検索方式が部分一致検索方式である場合、述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋３）の述語多項式
【数１２】
で与えられ、
復号鍵ｋ＊は、ｕ個の述語多項式に対応してｕ個生成され（以下、これをｋ＊[c]（１≦ｃ≦ｕ）とする）、復号判定部は、１≦ｃ≦ｕの各ｃについて、情報Ｒ２を復号鍵ｋ＊[c]で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する。
【００１２】
本発明のキーワード検索方法は、少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムおけるキーワード検索方法であって、検索対象となるキーワードを登録用キーワードとして、暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求装置の鍵生成部が、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成ステップと、検索要求装置の送信部が、復号鍵ｋ＊を検索代行装置へ送信する送信ステップと、検索代行装置の受信部が、復号鍵ｋ＊を受信する受信ステップと、検索代行装置の復号判定部が、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する復号判定ステップとを有する。
【００１３】
また本発明の検索要求装置は、検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる検索要求装置であって、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、復号鍵ｋ＊を検索代行装置へ送信する送信部とを含む。
【００１４】
また本発明の検索代行装置は、検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる検索代行装置であって、検索用キーワードを用いて生成された、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を、検索要求装置から受信する受信部と、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定する復号判定部とを含む。
【００１５】
また、本発明の検索要求装置としてコンピュータを機能させるプログラムによって、コンピュータを検索要求装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを検索要求装置として機能させることや、プログラムを流通させることなどが可能になる。同様に、本発明の検索代行装置としてコンピュータを機能させるプログラムによって、コンピュータを検索代行装置として作動処理させることができるところ、このようなプログラムを記録した、コンピュータによって読み取り可能なプログラム記録媒体によって、他のコンピュータを検索代行装置として機能させることや、プログラムを流通させることなどが可能になる。
【発明の効果】
【００１６】
本発明に拠れば、暗号情報Ｃ１に、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、検索要求側で、検索用キーワードを用いて、情報Ｒ２を述語暗号方式により復号するための復号鍵ｋ＊を生成し、検索代行側で、述語暗号方式に従って情報Ｒ２を復号鍵ｋ＊で復号し、得られた情報が情報Ｒ１に一致するか否かを判定するところ、検索方式に対応した述語論理の構成により、キーワードの完全一致検索に加えて完全一致検索以外のキーワード検索（例えば部分一致検索）も可能となっている。
【図面の簡単な説明】
【００１７】
【図１】実施形態に関るキーワード検索システムの構成図。
【図２】実施形態に関るキーワード検索方法の処理手順を示す図。
【図３】変形例１に関るキーワード検索方法の処理手順を示す図。
【図４】変形例２に関るキーワード検索方法の処理手順を示す図。
【図５】実施形態に関る暗号情報生成装置、検索要求装置、検索代行装置、保管装置の機能ブロック図。
【発明を実施するための形態】
【００１８】
図面を参照して本発明の実施形態を説明する。
なお、以下に説明する情報処理では、文字列を含む情報が暗号化の対象となるが、暗号処理の実際では、人間が意味内容を認識可能なテキスト情報である文字そのものが暗号化されるのではなく、例えば当該文字に割り当てられている文字コード情報（EUC-JP、Shift_JIS、UTF-8などのバイト表現）が暗号化の対象となる。従って、後述の説明において例えば変数Ｘに文字ｗを代入ないし設定する（Ｘ＝ｗ）とは、テキスト情報としての文字ｗを変数Ｘに代入ないし設定することではなく、文字コード情報としての文字ｗを変数Ｘに代入ないし設定することと理解するべきである。このことは暗号処理の常套手段であるから、その詳細な説明を省略する。また、この明細書では、ベクトルの表記として慣用的にベクトルであることを示す記号“→”を省略している場合がある。従って、或る記号がベクトルであるか否かは明細書全体の記載から合理的に理解されたい。
【００１９】
［キーワード検索システム］
この実施形態のキーワード検索システム１は、図１に示すように、暗号情報生成装置１００と、検索要求装置２００と、検索代行装置３００と、保管装置４００とを少なくとも含んで構成される。これらの各装置は、例えばインターネットである通信網５を介して相互に通信可能とされている。
【００２０】
キーワード検索システム１におけるキーワード検索処理を、図２を参照しながら叙述する。各装置の機能構成については、図５を参照されたい。
【００２１】
《暗号情報生成プロセス》
暗号情報生成装置１００の暗号情報生成部１０１は、文字列を含む情報Ｍを暗号化して暗号情報Ｃ１を得る（ステップＳ１）。この暗号方式（Ｅｎｃ，Ｄｅｃ）に限定はない。この暗号方式として、例えば共通鍵暗号方式や公開鍵暗号方式を利用できる。共通鍵暗号方式の場合、情報Ｍは、暗号情報生成装置１００と検索装置２００との間で共有される共通鍵で暗号化される。また、公開鍵暗号方式の場合、情報Ｍは検索装置２００の公開鍵で暗号化される。つまり、暗号情報Ｃ１を得るための情報処理は、暗号化アルゴリズムＥｎｃに従い、Ｃ１＝Ｅｎｃ(Ｍ)である。
【００２２】
暗号情報生成装置１００の検索用情報生成部１０２は、検索が当たりか否かを識別可能な情報Ｒ１を任意に設定し（例えば情報Ｒ１に数値としてのゼロを設定する）、この情報Ｒ１を登録用キーワードＷで述語暗号方式により暗号化して情報Ｒ２を得る（ステップＳ２）。登録用キーワードは、例えばユーザによって予め設定される、検索対象となるキーワードである。検索用情報Ｃ２はＣ２＝（Ｒ１，Ｒ２）である。情報Ｒ２を得る暗号化処理は例えば内積型述語暗号方式によって実現される。内積型述語暗号方式の詳細について、例えば参考文献Ａを参照されたい。
（参考文献Ａ）T. Okamoto and K. Takashima, "Hierarchical predicate encryption for inner-products", In ASIACRYPT, pp.214-231, 2009.
【００２３】
ここでは、内積型述語暗号方式を用いた暗号化処理の一例を説明する。
述語暗号は、送信者による暗号化の過程で暗号メッセージに或る情報Ｇが組み込まれ、当該情報Ｇと特定の関係を満たす情報Ｈを持つ受信者が、暗号メッセージの復号や、メッセージを知ることなくメッセージに関する情報を取得することができる方式である。送信者は、暗号化の際に、必ずしも受信者の持つ情報Ｈを知っている必要はない。また、送信者は、必ずしも、暗号化する前に受信者を特定している必要もない。送信者は、自由に、能動的に、主導権を持って、情報Ｇを決めることができる。講学的に、情報Ｇは属性Ｉ（変数）として、情報Ｈは述語論理ｆ（命題関数、ブール関数）として表される。復号に際し、情報Ｇと情報Ｈとが満たすべき特定の関係は、例えばｆ(Ｉ)＝１である。内積型述語暗号方式では、属性ベクトルと述語ベクトルとの標準内積により述語論理の真偽が与えられる。ここでは、述語論理を多変数多項式によって表現する。この多変数多項式を述語多項式とも呼ぶ。属性を表す変数を属性変数と呼ぶ。
【００２４】
例えば３個の属性変数Ｘ１，Ｘ２，Ｘ３が、（Ｘ１＝ｗ１またはＸ２＝ｗ２、かつＸ３＝ｗ３）の場合にのみ１を返す述語多項式ｐ(Ｘ１，Ｘ２，Ｘ３)は乱数ｒｄを用いて式（１）で表される。式（１）では論理和ORは積の演算で論理積ANDは和の演算で表されている。
ｐ(Ｘ１，Ｘ２，Ｘ３)＝(Ｘ１−ｗ１)(Ｘ２−ｗ２)＋rd(Ｘ３−ｗ３) （１）
【００２５】
ｒ個の属性変数Ｘ１，Ｘ２，…，Ｘｒに対してｄ−１回の論理和を扱うためには、Ｘ１，Ｘ２，…，Ｘｒからなる次数ｄ以下の単項式をすべて用意する必要がある。この単項式を１を含めて辞書式順序で並べた順に各成分としたベクトルを、属性変数Ｘ１，Ｘ２，…，Ｘｒに対するｄ次の変数ベクトルと呼び、Ｘｒ，ｄと表す。辞書式順序とは、ｄ個の同一の順序集合｛１，Ｘ１，Ｘ２，…，Ｘｒ｝の直積集合に順序を導入したものである。辞書式順序は例えば素朴集合論において論じられ公知であるから、これ以上の詳細な説明は行わない。
【００２６】
ｒ文字の登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）とする。属性変数Ｘｉ（１≦ｉ≦ｒ）について、Ｘｉ＝ｗｉとする。このとき、ベクトルｘが変数ベクトルＸｒ，ｄ上の属性ベクトルｘであるとは、式（２）を満足する場合をいう。なお、この実施形態ではｒはシステム仕様として固定値（１≦ｒを満たす整数）に設定される。登録用キーワードＷの長さ（文字数）がｒに満たない場合は、ｒに達するまでnull文字でパディングする。具体例として、ｒ＝２，ｄ＝２，Ｘｒ，ｄ＝(１，Ｘ１，Ｘ２，Ｘ１２，Ｘ１Ｘ２，Ｘ２２)の場合、属性ベクトルｘはｘ＝(１，ｗ１，ｗ２，ｗ１２，ｗ１ｗ２，ｗ２２)となる。
【数１３】
【００２７】
ｒ個の属性変数Ｘ１，Ｘ２，…，Ｘｒで最大ｄ回の論理和が許されているとき、述語論理を表す属性変数からなる多変数多項式ｐ(Ｘα，…，Ｘβ)（１≦α≦β≦ｒ）を、変数ベクトルＸｒ，ｄ上の述語多項式と呼ぶ。
【００２８】
この変数ベクトルＸｒ，ｄ上の述語多項式ｐ(Ｘα，…，Ｘβ)を、変数ベクトルＸｒ，ｄと述語ベクトルｖとの標準内積<Ｘｒ，ｄ，ｖ>と考えて、ｐ(Ｘα，…，Ｘβ)の係数を、変数ベクトルＸｒ，ｄの成分に対応する順に述語ベクトルｖの成分とする。述語ベクトルｖのこれら以外の成分を０とする。この述語ベクトルを変数ベクトルＸｒ，ｄ上の述語ベクトルとも呼ぶ。
【００２９】
ｄは１≦ｄ≦ｒを満たす固定値にシステム仕様として設定されるが、この実施形態では、ｄ＝ｒとする。つまり、述語多項式において登録用キーワードの最大文字数相当の論理和を許容する。
【００３０】
さて、内積型述語暗号方式を用いた暗号化処理の一例は次のとおりである。検索用情報生成部１０２は、式（３）に従って登録用キーワードＷから属性ベクトルｘを生成する。この式（３）は、変数ベクトルＸｒ，ｒにおいてＸｉ＝ｗｉ（１≦ｉ≦ｒ）とすることを意味する。
【数１４】
【００３１】
ｘ＝(ｘ１，ｘ２，…，ｘｎ)∈Ｆqnとする。つまり、ｘｉ（１≦ｉ≦ｎ）はｎ次元直積Ｆqnの元とする。Ｆqは有限体であり、ｑは素数または素数の冪乗値である。検索用情報生成部１０２は、δ１，δ２，ζをＦqからランダムに選択し、式（４）を計算することにより、情報Ｒ２を得る。情報Ｒ２はＲ２＝（cipher1，cipher2）である。
【数１５】
【００３２】
公開パラメータは、例えば位数ｑの巡回群Ｇ1，Ｇ2，ＧTの生成元ｇ1，ｇ2，ｇT、非退化性を持つ双線形写像ｅ：Ｇ1×Ｇ2→ＧT（但し、e(g1,g2)=gT）、位数ｑ、（ｎ＋３）次元のベクトル空間Ｖの直交基底Ｂを含む。秘密鍵は、双対ベクトル空間Ｖ＊の直交基底Ｂ＊を含む。代数構造を有限体Ｆqとする場合、ｑは素数または素数の冪乗値である。双線形写像ｅは例えばTateペアリングやWeilペアリングである。
【００３３】
直交基底Ｂおよび直交基底Ｂ＊について説明を加える。
（ｎ＋３）次元のベクトル空間Ｖの任意の元が、式（５）のように巡回群Ｇ1の（ｎ＋３）次元直積Ｇ1n+3の元として表されるとする。（ｎ＋３）次元のベクトル空間Ｖの任意の元は、（ｎ＋３）次元のベクトル空間Ｖの標準基底Ａを用いて式（６）のように表すこともできる。ただし、ａiは（ｎ＋３）次元直積Ｇ1n+3の元、ｚiは（ｎ＋３）次元直積Ｆqn+3の元とする。また、１は加法単位元とする。
【数１６】
【００３４】
直交基底Ｂは、式（７）のように、標準基底Ａに（ｎ＋３）次正方行列Ｘを作用させたものとして得られる。記号Ｔは転置を表す。なお、行列Ｘは秘密鍵と同様に秘密とされる。
【数１７】
【００３５】
同様に、ベクトル空間Ｖと双対な双対ベクトル空間Ｖ＊の任意の元が、式（８）のように巡回群Ｇ2の（ｎ＋３）次元直積Ｇ2n+3の元として表されるとする。双対ベクトル空間Ｖ＊の任意の元は、双対ベクトル空間Ｖ＊の標準基底Ａ＊を用いて式（９）のように表すこともできる。ただし、ａi＊は（ｎ＋３）次元直積Ｇ2n+3の元、ｙi＊は（ｎ＋３）次元直積Ｆqn+3の元とする。また、１は加法単位元とする。
【数１８】
【００３６】
直交基底Ｂ＊は、式（１０）のように、標準基底Ａ＊に（ｎ＋３）次正方行列T(Ｘ-1)を作用させたものとして得られる。記号Ｅは単位行列を表す。
【数１９】
【００３７】
暗号情報生成装置１００の送信部１０８は、暗号情報Ｃ１と検索用情報Ｃ２とを一組として保管装置４００へ送信する（ステップＳ３）。保管装置４００の受信部４０９は、暗号情報と検索用情報との組（Ｃ１，Ｃ２）を受信する（ステップＳ４）。保管装置４００の記憶部４０１には、通常、暗号情報生成装置１００から受信した複数の（Ｃ１，Ｃ２）が記憶されている。さらに言えば、保管装置４００の記憶部４０１には、一般的に、複数の暗号情報生成装置から受信した複数の（Ｃ１，Ｃ２）が記憶されている。各組（Ｃ１，Ｃ２）には固有のインデックスが割り当てられている。
【００３８】
《検索要求プロセス》
検索要求装置２００の鍵生成部２０１は、上記秘密鍵（直交基底Ｂ＊）と、例えばユーザによって入力された検索用キーワードＳおよびユーザによって指定された検索方式＄の述語論理とを用いて、検索用情報Ｃ２に含まれる情報Ｒ２を復号するための復号鍵ｋ＊を生成する（ステップＳ５）。上記秘密鍵（直交基底Ｂ＊）は検索要求装置２００の秘密鍵である。
【００３９】
復号鍵ｋ＊を得るための情報処理は、暗号情報生成装置１００の検索用情報生成部１０２が実施した述語暗号方式に対応する鍵生成アルゴリズムに従う。この実施形態では、復号鍵ｋ＊を得るための情報処理は、内積型述語暗号方式によって実現される。具体的には、鍵生成部２０１は、まず、変数ベクトルＸｒ，ｒ上の述語ベクトルｖを生成する。
【００４０】
ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とする。もし、ｔ＜ｒならば、ｓｉ＝０（ｔ＜ｉ≦ｒ）とする。鍵生成部２０１は、後述するように検索方式＄に対応するＸｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)を決定して、Ｘｒ，ｒ上の述語ベクトルｖを求める。Ｘｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)からＸｒ，ｒ上の述語ベクトルｖを求める方法は既述のとおりである。
【００４１】
ここで各検索方式＄の述語多項式について説明を加える。rdi,j（１≦ｉ，ｊ≦ｒ）は乱数である。
【００４２】
《１》完全一致検索方式（ｃｍ）
完全一致検索方式は、任意のｉ（１≦ｉ≦ｒ）についてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
完全一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１１）で与えられる。
【数２０】
【００４３】
《２》前方一致検索方式（ｆｍ）
前方一致検索方式は、任意のｉ（１≦ｉ≦ｔ）についてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
前方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１２）で与えられる。
【数２１】
【００４４】
《３》後方一致検索方式（ｂｍ）
後方一致検索方式は、任意のｉ（ｒ−ｔ＋１≦ｉ≦ｒ）についてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
後方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１３）で与えられる。
【数２２】
【００４５】
《４》部分一致検索方式（ｐｍ）
部分一致検索方式は、或るｊが存在して（ｊ≦ｉ≦ｔ＋ｊ−１≦ｒ）を満たすすべてのｉについてｗｉ＝ｓｉが成立する場合を検索する検索方式である。
部分一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（１４）で与えられる。
【数２３】
【００４６】
《５》完全不一致検索方式（ｎｃｍ）
完全不一致検索方式は、すべてのｉ（１≦ｉ≦ｒ）についてｗｉ＝ｓｉが成立しない場合を検索する検索方式である。これは完全一致検索方式でヒットした検索結果の補集合として得られる。
【００４７】
《６》「含まない」検索方式（ｎｐｍ）
「含まない」検索方式は、ｊ≦ｉ≦ｔ＋ｊ−１≦ｒを満たすすべてのｉについてｗｉ＝ｓｉが成立するようなｊが存在しない場合を検索する検索方式である。これは部分一致検索方式でヒットした検索結果の補集合として得られる。
【００４８】
次に、鍵生成部２０１は、述語ベクトルｖ＝(ｖ１，ｖ２，…，ｖｎ)∈Ｆqnに対して、σ，ηをＦqからランダムに選択し、式（１５）を計算することにより、復号鍵ｋ＊を得る。
【数２４】
【００４９】
検索要求装置２００の送信部２０８は、復号鍵ｋ＊を検索代行装置３００へ送信する（ステップＳ６）。
【００５０】
《検索代行プロセス》
検索代行装置３００の受信部３０９は、復号鍵ｋ＊を受信する（ステップＳ７）。
【００５１】
検索代行装置３００の制御部３０５は、送信部３０８を制御して、保管装置４００に対して保管装置４００の記憶部４０１に記憶されているすべての検索用情報を検索代行装置３００へ送信するように要求し、これを受けて保管装置４００の送信部４０８は記憶部４０１に記憶されているすべての検索用情報をインデックスとともに検索代行装置３００へ送信し、検索代行装置３００の受信部３０９がこれらを受信する（ステップＳ８）。
【００５２】
検索代行装置３００の復号判定部３０１は、すべての検索用情報を復号判定処理の対象とし、復号鍵ｋ＊を用いて検索用情報を個別に復号して検索が当たりか否かを判定する（ステップＳ９）。具体的には、復号判定部３０２は、すべての検索用情報について、式（１６）に従って情報Ｒを求め（復号処理）、Ｒ＝Ｒ１の成否を判定する（判定処理）。
【数２５】
【００５３】
検索代行装置３００の送信部３０８は、Ｒ＝Ｒ１が成立した検索用情報のインデックスを検索要求装置２００へ送信する（ステップＳ１０）。
【００５４】
《検索結果受信プロセス》
検索要求装置２００の受信部２０９は、Ｒ＝Ｒ１が成立した検索用情報のインデックスを受信する（ステップＳ１１）。
【００５５】
検索要求装置２００の制御部２０５は、送信部２０８を制御して、保管装置４００に対して、保管装置４００の記憶部４０１に記憶されている、検索代行装置３００から受信したインデックスに対応する暗号情報を検索要求装置２００へ送信するように要求し、これを受けて保管装置４００の送信部４０８は当該インデックスに対応する暗号情報を検索要求装置２００へ送信し、検索要求装置２００の受信部２０９がこれらを受信する（ステップＳ１２）。
【００５６】
検索要求装置２００の復号部２０６は、必要に応じて、保管装置４００から受信した暗号情報Ｃ１を復号して情報Ｍを得る（ステップＳ１３）。情報Ｍを得るための情報処理は、暗号情報生成装置１００の暗号情報生成部１０１が実施した暗号方式（Ｅｎｃ，Ｄｅｃ）に対応する復号アルゴリズムＤｅｃに従う。つまり、Ｍ＝Ｄｅｃ(Ｃ１)である。
【００５７】
＜変形例＞
上記実施形態では、変数ベクトルＸｒ，ｄの次元ｎは、ｉ次以下の単項式の総和がｒ文字からｑ文字（１≦ｑ≦ｉ）を選ぶ組み合わせの和になるので、式（１７）で表される。
【数２６】
【００５８】
式（１７）によると、変数ベクトルＸｒ，ｄの次元ｎは、登録用キーワードの文字数ｒと論理和の数ｄの階乗のオーダーで増加する。そこで、各変形例では、論理和を用いる検索でありながら論理和を用いない変数ベクトルＸｒ，１を構成する。このため各変形例では、登録用キーワードと検索用キーワードに、文字列開始記号としてＳＴ、文字列終端記号としてＥＤを導入する。なお、説明の便宜からこれらの記号をＳＴ、ＥＤというように２文字で表現したが、変形例では、文字列開始記号として１文字の長さの記号、文字列終端記号として１文字の長さの記号が設定されることに留意されたい。もちろん、これらの記号の長さを任意に設定してよいが、この場合、述語多項式の表現やそこに現れる添え字が変わるものの、実用上格別の意義を有しないので、通常、１文字分の長さの記号を設定すれば足りる。なお、変形例１については図３を、変形例２については図４を参照のこと。
【００５９】
[変形例１]
登録用キーワードＷの１文字目ｗ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｗmax+1をＥＤとする。登録用キーワードＷについて、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉと定義する。ここでnullｉはｉ−１個のnullを表す。Ｗｉのｊ番目の文字をｗｉ，ｊと表すことにする。
【００６０】
変形例１では、実施形態のステップＳ２の処理は、次のように変更される。暗号情報生成装置１００の検索用情報生成部１０２は、検索が当たりか否かを識別可能なｒ個の情報Ｒ１[ｉ]（１≦ｉ≦ｒ）を任意に設定し（例えばすべて数値としてのゼロとする）、この情報Ｒ１[ｉ]を部分キーワードＷｉで暗号化して情報Ｒ２[ｉ]を得る（ステップＳ２ａ）。具体的には、検索用情報生成部１０２は、式（１８）に従って、ｒ個の部分キーワードＷｉからｒ個の属性ベクトルｘｉ（１≦ｉ≦ｒ）を生成する。ｘｉ＝(ｘ１[i]，ｘ２[i]，…，ｘｎ[i])∈Ｆqnとする。
【数２７】
【００６１】
そして、検索用情報生成部１０２は、δ１，δ２，ζをＦqからランダムに選択し、式（１９）を計算することにより、情報Ｒ２[ｉ]を得る（１≦ｉ≦ｒ）。情報Ｒ２[ｉ]はＲ２[ｉ]＝（cipher1[i]，cipher2[i]）である（１≦ｉ≦ｒ）。
【数２８】
【００６２】
変形例１では、述語ベクトルは実施形態と同じように構成される。なお、検索用キーワードＳの１文字目ｓ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｓmax+1をＥＤとする。
【００６３】
変形例１では、実施形態のステップＳ３、Ｓ４の各処理は、次のように変更される。暗号情報生成装置１００の送信部１０８は、暗号情報Ｃ１とｒ個の検索用情報Ｃ２[ｉ]＝（Ｒ１[ｉ]，Ｒ２[ｉ]）とを一組として保管装置４００へ送信する（ステップＳ３ａ）。保管装置４００の受信部４０９は、暗号情報と検索用情報との組（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）を受信する（ステップＳ４ａ）。保管装置４００の記憶部４０１には、通常、暗号情報生成装置１００から受信した複数の（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）が記憶されている。さらに言えば、保管装置４００の記憶部４０１には、一般的に、複数の暗号情報生成装置から受信した複数の（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）が記憶されている。各組（Ｃ１，Ｃ２[１]，Ｃ２[２]，…，Ｃ２[ｒ]）には固有のインデックスが対応付けられている。
【００６４】
変形例１では、実施形態のステップＳ５の処理自体に変更はないが、各検索方式に対応する述語多項式ｐ(Ｘα，…，Ｘβ)が次のとおりに変更される。
【００６５】
《１》完全一致検索方式（ｃｍ）
変形例１では、完全一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２０）で与えられる。
【数２９】
【００６６】
《２》前方一致検索方式（ｆｍ）
変形例１では、前方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２１）で与えられる。
【数３０】
【００６７】
《３》後方一致検索方式（ｂｍ）
変形例１では、後方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２２）で与えられる。
【数３１】
【００６８】
《４》部分一致検索方式（ｐｍ）
変形例１では、部分一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２３）で与えられる。
【数３２】
【００６９】
《５》完全不一致検索方式（ｎｃｍ）と《６》「含まない」検索方式（ｎｐｍ）は実施形態と同じである。
【００７０】
変形例１では、実施形態のステップＳ６以降の各処理について、１個の暗号情報にｒ個の検索用情報が添付されていることを注意すれば、実質的な変更はない。なお、実施形態におけるステップＳ９の処理は、次のように変更される。検索代行装置３００の復号判定部３０１は、すべての検索用情報を復号判定処理の対象とし、復号鍵ｋ＊を用いて検索用情報を個別に復号して検索が当たりか否かを判定する（ステップＳ９ａ）。具体的には、復号判定部３０１は、すべての検索用情報について、式（２３ａ）に従って情報Ｒ[ｉ]を求め（復号処理）、Ｒ[ｉ]＝Ｒ１[ｉ]の成否を判定する（判定処理）。
【数３３】
【００７１】
変形例１によると、復号判定処理の回数は上述の実施形態と比較して一つの暗号情報につきｒ倍になるが、論理和の使用により変数ベクトルの次元が階乗オーダーで大きくなってしまうことに比べ定数倍の処理の増加で済むので、論理和を使用する検索の場合において上述の実施形態と比較してメリットが大きい。
【００７２】
[変形例２]
論理和を用いる検索でありながら論理和を用いない変数ベクトルＸｒ，１を構成するために、変形例２では、一つの検索用キーワードから複数の述語ベクトルを生成する（なお、諸条件により必ず複数の述語ベクトルが生成されるわけではない。ここでは、特徴的な場合を説明する観点から、生成される述語ベクトルは“複数”であるとして説明する）。各述語ベクトルに対応する復号鍵ｋ＊が生成される。つまり、特徴的な場合には複数の復号鍵ｋ＊が生成される。
【００７３】
登録用キーワードＷの１文字目ｗ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｗmax+1をＥＤとする。登録用キーワードＷについて、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉと定義する。ここでnullｉはｉ−１個のnullを表す。Ｗｉのｊ番目の文字をｗｉ，ｊと表すことにする。また、検索用キーワードＳの１文字目ｓ１をＳＴとする。また、nullでない文字の最大の添え字をmaxとしたとき、(max+1)文字目ｓmax+1をＥＤとする。
【００７４】
変形例２では、実施形態のステップＳ２、Ｓ５、Ｓ６、Ｓ７、Ｓ９の各処理は、次のように変更される。
【００７５】
暗号情報生成装置１００の検索用情報生成部１０２は、検索が当たりか否かを識別可能な情報Ｒ１を任意に設定し（例えば数値としてのゼロ）、この情報Ｒ１を登録用キーワードＷで暗号化して情報Ｒ２を得る（ステップＳ２ｂ）。具体的には、検索用情報生成部１０２は、式（２３ｂ）に従って、登録用キーワードＷから属性ベクトルｘを生成する。ｘ＝(ｘ１，ｘ２，…，ｘｎ)∈Ｆqnとする。
【数３４】
【００７６】
そして、検索用情報生成部１０２は、δ１，δ２，ζをＦqからランダムに選択し、式（２３ｃ）を計算することにより、情報Ｒ２を得る。情報Ｒ２はＲ２＝（cipher1，cipher2）である。
【数３５】
【００７７】
検索要求装置２００の鍵生成部２０１は、上記秘密鍵（直交基底Ｂ＊）と、例えばユーザによって入力された検索用キーワードＳおよびユーザによって指定された検索方式＄の述語論理とを用いて、検索用情報Ｃ２に含まれる情報Ｒ２を復号するための複数の復号鍵ｋ＊を生成する（ステップＳ５ｂ）。
【００７８】
ｔ文字の検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とする。もし、ｔ＜ｒならば、ｓｉ＝０（ｔ＜ｉ≦ｒ）とする。鍵生成部２０１は、後述するように検索方式＄に対応するＸｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)を決定して、Ｘｒ，ｒ上の述語ベクトルｖを求める。Ｘｒ，ｒ上の述語多項式ｐ(Ｘα，…，Ｘβ)からＸｒ，ｒ上の述語ベクトルｖを求める方法は既述のとおりである。
【００７９】
変形例２では、実施形態と異なり、各検索方式に対応する述語多項式ｐ(Ｘα，…，Ｘβ)が次のとおりに変更される。
【００８０】
《１》完全一致検索方式（ｃｍ）
変形例２では、完全一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２４）で与えられる。
【数３６】
【００８１】
《２》前方一致検索方式（ｆｍ）
変形例２では、前方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２５）で与えられる。
【数３７】
【００８２】
《３》後方一致検索方式（ｂｍ）
変形例２では、後方一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２６）で与えられる。なお、この場合、ｒ−ｔ＋２個の述語多項式が得られる。
【数３８】
【００８３】
《４》部分一致検索方式（ｐｍ）
変形例２では、部分一致検索方式における述語多項式ｐ(Ｘα，…，Ｘβ)は、式（２７）で与えられる。なお、この場合、ｒ−ｔ＋３個の述語多項式が得られる。
【数３９】
【００８４】
《５》完全不一致検索方式（ｎｃｍ）と《６》「含まない」検索方式（ｎｐｍ）は実施形態と同じである。
【００８５】
次に、鍵生成部２０１は、ｕ個の述語ベクトルｖ[c]＝(ｖ１[c]，ｖ２[c]，…，ｖｎ[c])∈Ｆqnに対して、σ，ηをＦqからランダムに選択し、式（２８）を計算することにより、ｕ個の復号鍵ｋ＊[c]を得る（１≦ｃ≦ｕ）。《１》と《２》と《５》の場合はｕ＝１である。《３》の場合はｕ＝ｒ−ｔ＋２である。《４》と《６》の場合はｕ＝ｒ−ｔ＋３である。
【数４０】
【００８６】
検索要求装置２００の送信部２０８は、ｕ個の復号鍵ｋ＊[c]を検索代行装置３００へ送信する（ステップＳ６ｂ）。検索代行装置３００の受信部３０９は、ｕ個の復号鍵ｋ＊[c]を受信する（ステップＳ７ｂ）。
【００８７】
検索代行装置３００の復号判定部３０１は、すべての検索用情報を復号判定処理の対象とし、ｕ個の復号鍵ｋ＊[c]を用いて検索用情報を個別に復号して検索が当たりか否かを判定する（ステップＳ９ｂ）。具体的には、復号判定部３０１は、すべての検索用情報について、式（２９）に従って情報Ｒ[c]を求め（復号処理）、Ｒ[c]＝Ｒ１（１≦ｃ≦ｕ）の成否を判定する（判定処理）。
【数４１】
【００８８】
変形例２では、１個の暗号情報に１個の検索用情報が添付されているものの、１個の検索用キーワードからｕ個の復号鍵ｋ＊[c]を生成するため、復号判定処理の回数は上述の実施形態と比較して一つの暗号情報につきｕ倍になるが、論理和の使用により変数ベクトルの次元が階乗オーダーで大きくなってしまうことに比べ定数倍の処理の増加で済むので、論理和を使用する検索の場合において上述の実施形態と比較してメリットが大きい。
【００８９】
上述の実施形態と各変形例では、検索代行装置３００は、複合判定処理において検索用情報と暗号情報との結びつきのみを把握できるだけなので、暗号情報の中身（情報Ｍ）や検索用キーワードＳが何であるのかということが検索代行装置３００に漏れることがない。
【００９０】
なお、上述の実施形態と各変形例では、暗号情報生成装置１００と検索要求装置２００を同一のエンティティとして実施することも可能である。この場合、上述の実施形態と各変形例において、暗号情報生成装置１００を検索要求装置２００に読み替えればよい。また、上述の実施形態と各変形例では、検索代行装置３００と保管装置４００を同一のエンティティとして実施することも可能である。この場合、上述の実施形態と各変形例において、保管装置４００を検索代行装置３００に読み替えればよい。これら両者の形態を組み合わせた変形例としてもよい。これらの場合、上述の実施形態と各変形例で説明した、暗号情報生成装置１００と検索要求装置２００との間の通信、検索代行装置３００と保管装置４００との間の通信がそれぞれ不要になる。
【００９１】
キーワード検索システムに含まれるハードウェアエンティティ（暗号情報生成装置、検索要求装置、検索代行装置、保管装置）は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００９２】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するＲＡＭやレジスタなどの記憶装置を単に「記憶部」とした。
【００９３】
ハードウェアエンティティでは、外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（例えば、暗号情報生成部、検索用情報生成部、鍵生成部、復号部、復号判定部、制御部など）を実現する。
【００９４】
各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成22年1月13日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/〉［平成22年1月13日検索］を参照のこと。）。
また、この点に関する文献として、参考文献Ｂを挙げることができる。
（参考文献Ｂ） H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【００９５】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００９６】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００９７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００９８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１００】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【特許請求の範囲】
【請求項１】
少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムであって、
検索対象となるキーワードを登録用キーワードとして、前記暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、
前記検索要求装置は、
前記検索用キーワードを用いて、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、
前記復号鍵ｋ＊を前記検索代行装置へ送信する送信部と
を含み、
前記検索代行装置は、
前記復号鍵ｋ＊を受信する受信部と、
前記述語暗号方式に従って前記情報Ｒ２を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する復号判定部と
を含む、キーワード検索システム。
【請求項２】
請求項１に記載のキーワード検索システムにおいて、
前記情報Ｒ２は、前記登録用キーワードから生成される前記述語暗号方式の属性で前記情報Ｒ１を暗号化して得られ、
前記復号鍵ｋ＊は、前記検索用キーワードから生成される前記述語暗号方式の述語から生成される
ことを特徴とするキーワード検索システム。
【請求項３】
請求項２に記載のキーワード検索システムにおいて、
前記述語暗号方式は、属性ベクトルと述語ベクトルとの標準内積により述語論理の真偽が与えられる内積型述語暗号方式であり、
前記属性は、前記登録用キーワードの最大文字数をｒとして、前記述語論理に最大ｄ−１回の論理和が許される場合に、ｒ個の属性変数Ｘ１，…，Ｘｒからなる次数ｄ以下の単項式をすべて辞書式順序で並べた順に各成分とした変数ベクトルＸｒ，ｄに前記登録用キーワードに含まれる文字を設定して得られる属性ベクトルであり、
前記述語は、述語論理を前記属性変数と前記検索用キーワードに含まれる文字を用いて多項式で表現した述語多項式の係数を、前記変数ベクトルＸｒ，ｄの成分に対応する順に並べたものを成分として持つ述語ベクトルである
ことを特徴とするキーワード検索システム。
【請求項４】
請求項３に記載のキーワード検索システムにおいて、
前記述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数、ｒ文字の前記登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ｔ文字の前記検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）として、
《１》前記検索方式が完全一致検索方式である場合、前記述語多項式は、
【数４２】
で与えられ、
《２》前記検索方式が前方一致検索方式である場合、前記述語多項式は、
【数４３】
で与えられ、
《３》前記検索方式が後方一致検索方式である場合、前記述語多項式は、
【数４４】
で与えられ、
《４》前記検索方式が部分一致検索方式である場合、前記述語多項式は、
【数４５】
で与えられる
ことを特徴とするキーワード検索システム。
【請求項５】
請求項３に記載のキーワード検索システムにおいて、
ｒ文字の前記登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、
ｔ文字の前記検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を前記文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を前記文字列終端記号ＥＤとして、
前記属性ベクトルは、ｒ個の部分キーワードＷｉに対応してｒ個生成され、
前記暗号情報Ｃ１には、当たりか否かを識別可能なｒ個の前記情報Ｒ１（以下、Ｒ１[ｉ]（１≦ｉ≦ｒ）とする）と、当該情報Ｒ１[ｉ]を前記部分キーワードＷｉで暗号化して得られるｒ個の前記情報Ｒ２（以下、Ｒ２[ｉ]（１≦ｉ≦ｒ）とする）との組である前記検索用情報Ｃ２（以下、Ｃ２[ｉ]＝（Ｒ１[ｉ]，Ｒ２[ｉ]）（１≦ｉ≦ｒ）とする）が添付されており、
前記述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》前記検索方式が完全一致検索方式である場合、前記述語多項式は、
【数４６】
で与えられ、
《２》前記検索方式が前方一致検索方式である場合、前記述語多項式は、
【数４７】
で与えられ、
《３》前記検索方式が後方一致検索方式である場合、前記述語多項式は、
【数４８】
で与えられ、
《４》前記検索方式が部分一致検索方式である場合、前記述語多項式は、
【数４９】
で与えられ、
前記復号判定部は、１≦ｉ≦ｒの各ｉについて、前記情報Ｒ２[ｉ]を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１[ｉ]に一致するか否かを判定する
ことを特徴とするキーワード検索システム。
【請求項６】
請求項３に記載のキーワード検索システムにおいて、
ｒ文字の前記登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、
ｔ文字の前記検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を前記文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を前記文字列終端記号ＥＤとして、
前記述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》前記検索方式が完全一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数５０】
で与えられ、
《２》前記検索方式が前方一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数５１】
で与えられ、
《３》前記検索方式が後方一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋２）の述語多項式
【数５２】
で与えられ、
《４》前記検索方式が部分一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋３）の述語多項式
【数５３】
で与えられ、
前記復号鍵ｋ＊は、ｕ個の述語多項式に対応してｕ個生成され（以下、これをｋ＊[c]（１≦ｃ≦ｕ）とする）、
前記復号判定部は、１≦ｃ≦ｕの各ｃについて、前記情報Ｒ２を前記復号鍵ｋ＊[c]で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する
ことを特徴とするキーワード検索システム。
【請求項７】
少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムおけるキーワード検索方法であって、
検索対象となるキーワードを登録用キーワードとして、前記暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、
前記検索要求装置の鍵生成部が、前記検索用キーワードを用いて、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成ステップと、
前記検索要求装置の送信部が、前記復号鍵ｋ＊を前記検索代行装置へ送信する送信ステップと、
前記検索代行装置の受信部が、前記復号鍵ｋ＊を受信する受信ステップと、
前記検索代行装置の復号判定部が、前記述語暗号方式に従って前記情報Ｒ２を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する復号判定ステップと
を有するキーワード検索方法。
【請求項８】
検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、前記暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる前記検索要求装置であって、
前記検索用キーワードを用いて、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、
前記復号鍵ｋ＊を前記検索代行装置へ送信する送信部と
を含む検索要求装置。
【請求項９】
検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、前記暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる前記検索代行装置であって、
前記検索用キーワードを用いて生成された、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を、前記検索要求装置から受信する受信部と、
前記述語暗号方式に従って前記情報Ｒ２を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する復号判定部と
を含む検索代行装置。
【請求項１０】
請求項８に記載の検索要求装置として、または、請求項９に記載の検索代行装置として、コンピュータを機能させるためのプログラム。
【請求項１１】
請求項１０に記載のプログラムを記録した、コンピュータに読み取り可能な記録媒体。
【請求項１】
少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムであって、
検索対象となるキーワードを登録用キーワードとして、前記暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、
前記検索要求装置は、
前記検索用キーワードを用いて、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、
前記復号鍵ｋ＊を前記検索代行装置へ送信する送信部と
を含み、
前記検索代行装置は、
前記復号鍵ｋ＊を受信する受信部と、
前記述語暗号方式に従って前記情報Ｒ２を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する復号判定部と
を含む、キーワード検索システム。
【請求項２】
請求項１に記載のキーワード検索システムにおいて、
前記情報Ｒ２は、前記登録用キーワードから生成される前記述語暗号方式の属性で前記情報Ｒ１を暗号化して得られ、
前記復号鍵ｋ＊は、前記検索用キーワードから生成される前記述語暗号方式の述語から生成される
ことを特徴とするキーワード検索システム。
【請求項３】
請求項２に記載のキーワード検索システムにおいて、
前記述語暗号方式は、属性ベクトルと述語ベクトルとの標準内積により述語論理の真偽が与えられる内積型述語暗号方式であり、
前記属性は、前記登録用キーワードの最大文字数をｒとして、前記述語論理に最大ｄ−１回の論理和が許される場合に、ｒ個の属性変数Ｘ１，…，Ｘｒからなる次数ｄ以下の単項式をすべて辞書式順序で並べた順に各成分とした変数ベクトルＸｒ，ｄに前記登録用キーワードに含まれる文字を設定して得られる属性ベクトルであり、
前記述語は、述語論理を前記属性変数と前記検索用キーワードに含まれる文字を用いて多項式で表現した述語多項式の係数を、前記変数ベクトルＸｒ，ｄの成分に対応する順に並べたものを成分として持つ述語ベクトルである
ことを特徴とするキーワード検索システム。
【請求項４】
請求項３に記載のキーワード検索システムにおいて、
前記述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数、ｒ文字の前記登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ｔ文字の前記検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）として、
《１》前記検索方式が完全一致検索方式である場合、前記述語多項式は、
【数４２】
で与えられ、
《２》前記検索方式が前方一致検索方式である場合、前記述語多項式は、
【数４３】
で与えられ、
《３》前記検索方式が後方一致検索方式である場合、前記述語多項式は、
【数４４】
で与えられ、
《４》前記検索方式が部分一致検索方式である場合、前記述語多項式は、
【数４５】
で与えられる
ことを特徴とするキーワード検索システム。
【請求項５】
請求項３に記載のキーワード検索システムにおいて、
ｒ文字の前記登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、
ｔ文字の前記検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を前記文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を前記文字列終端記号ＥＤとして、
前記属性ベクトルは、ｒ個の部分キーワードＷｉに対応してｒ個生成され、
前記暗号情報Ｃ１には、当たりか否かを識別可能なｒ個の前記情報Ｒ１（以下、Ｒ１[ｉ]（１≦ｉ≦ｒ）とする）と、当該情報Ｒ１[ｉ]を前記部分キーワードＷｉで暗号化して得られるｒ個の前記情報Ｒ２（以下、Ｒ２[ｉ]（１≦ｉ≦ｒ）とする）との組である前記検索用情報Ｃ２（以下、Ｃ２[ｉ]＝（Ｒ１[ｉ]，Ｒ２[ｉ]）（１≦ｉ≦ｒ）とする）が添付されており、
前記述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》前記検索方式が完全一致検索方式である場合、前記述語多項式は、
【数４６】
で与えられ、
《２》前記検索方式が前方一致検索方式である場合、前記述語多項式は、
【数４７】
で与えられ、
《３》前記検索方式が後方一致検索方式である場合、前記述語多項式は、
【数４８】
で与えられ、
《４》前記検索方式が部分一致検索方式である場合、前記述語多項式は、
【数４９】
で与えられ、
前記復号判定部は、１≦ｉ≦ｒの各ｉについて、前記情報Ｒ２[ｉ]を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１[ｉ]に一致するか否かを判定する
ことを特徴とするキーワード検索システム。
【請求項６】
請求項３に記載のキーワード検索システムにおいて、
ｒ文字の前記登録用キーワードＷのｉ文字目の文字をｗｉ（１≦ｉ≦ｒ）、ただし、１文字目ｗ１を文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｗmax+1を文字列終端記号ＥＤとし、部分キーワードＷｉ（１≦ｉ≦ｒ）をＷｉ＝ｗｉｗｉ＋１…ｗｒ‖nullｉとし、ただし、nullｉはｉ−１個のnullを表し、Ｗｉのｊ番目の文字をｗｉ，ｊと表すこととし、
ｔ文字の前記検索用キーワードＳのｉ文字目の文字をｓｉ（１≦ｉ≦ｔ≦ｒ）とし、ただし、１文字目ｓ１を前記文字列開始記号ＳＴとし、nullでない文字の最大の添え字をmaxとしたときに(max+1)文字目ｓmax+1を前記文字列終端記号ＥＤとして、
前記述語多項式は検索方式に依存して決定され、rdi,j（１≦ｉ，ｊ≦ｒ）を乱数とし、
《１》前記検索方式が完全一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数５０】
で与えられ、
《２》前記検索方式が前方一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝１）の述語多項式
【数５１】
で与えられ、
《３》前記検索方式が後方一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋２）の述語多項式
【数５２】
で与えられ、
《４》前記検索方式が部分一致検索方式である場合、前記述語多項式は、ｕ個（ｕ＝ｒ−ｔ＋３）の述語多項式
【数５３】
で与えられ、
前記復号鍵ｋ＊は、ｕ個の述語多項式に対応してｕ個生成され（以下、これをｋ＊[c]（１≦ｃ≦ｕ）とする）、
前記復号判定部は、１≦ｃ≦ｕの各ｃについて、前記情報Ｒ２を前記復号鍵ｋ＊[c]で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する
ことを特徴とするキーワード検索システム。
【請求項７】
少なくとも検索要求装置と検索代行装置を含み、文字列を含む情報を暗号化して得られた暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムおけるキーワード検索方法であって、
検索対象となるキーワードを登録用キーワードとして、前記暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、
前記検索要求装置の鍵生成部が、前記検索用キーワードを用いて、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成ステップと、
前記検索要求装置の送信部が、前記復号鍵ｋ＊を前記検索代行装置へ送信する送信ステップと、
前記検索代行装置の受信部が、前記復号鍵ｋ＊を受信する受信ステップと、
前記検索代行装置の復号判定部が、前記述語暗号方式に従って前記情報Ｒ２を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する復号判定ステップと
を有するキーワード検索方法。
【請求項８】
検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、前記暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる前記検索要求装置であって、
前記検索用キーワードを用いて、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を生成する鍵生成部と、
前記復号鍵ｋ＊を前記検索代行装置へ送信する送信部と
を含む検索要求装置。
【請求項９】
検索対象となるキーワードを登録用キーワードとして、文字列を含む情報を暗号化して得られた暗号情報Ｃ１には、当たりか否かを識別可能な情報Ｒ１と、当該情報Ｒ１を前記登録用キーワードを用いて述語暗号方式により暗号化して得られる情報Ｒ２との組である検索用情報Ｃ２＝（Ｒ１，Ｒ２）が添付されており、少なくとも検索要求装置と検索代行装置を含み、前記暗号情報Ｃ１に対して検索用キーワードによりキーワード検索を行うキーワード検索システムに含まれる前記検索代行装置であって、
前記検索用キーワードを用いて生成された、前記情報Ｒ２を前記述語暗号方式により復号するための復号鍵ｋ＊を、前記検索要求装置から受信する受信部と、
前記述語暗号方式に従って前記情報Ｒ２を前記復号鍵ｋ＊で復号し、得られた情報が前記情報Ｒ１に一致するか否かを判定する復号判定部と
を含む検索代行装置。
【請求項１０】
請求項８に記載の検索要求装置として、または、請求項９に記載の検索代行装置として、コンピュータを機能させるためのプログラム。
【請求項１１】
請求項１０に記載のプログラムを記録した、コンピュータに読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１１−１４７０７４（Ｐ２０１１−１４７０７４Ａ）
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願番号】特願２０１０−８２４１（Ｐ２０１０−８２４１）
【出願日】平成２２年１月１８日（２０１０．１．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願日】平成２２年１月１８日（２０１０．１．１８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]