(57)【要約】  複数の表を復号化する事なく結合し、データの関連性が漏洩する危険性を軽減する暗号化データベースシステム等を提供する。  クライアント端末１０は、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバ５０に出力し、暗号化された第１の表と第２の表をａ列目の値がｑであるデータについてｂ列目およびｃ列目をキーとして結合させる部分結合命令を秘密鍵から生成された検索鍵と共に暗号化データベースサーバ５０に送信する。暗号化データベースサーバ５０は、暗号化された第１および第２の表を受信して記憶し、検索鍵を利用して暗号化された第１および第２の表からａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対してｂ列目およびｃ列目をキーとして結合して返送する。
2013145627.tif 000002
【特許請求の範囲】
【請求項１】
入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバに出力し、前記暗号化された第１の表と第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信するクライアント端末と、
前記暗号化された第１および第２の表を受信して記憶し、前記部分結合命令に応じて前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する前記暗号化データベースサーバとを備え、
前記暗号化データベースサーバが、
前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合する、
暗号化データベースシステム。
【請求項２】
前記クライアント端末が、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素を検索するための鍵である第１の検索鍵と、前記第１の表の前記ｂ列目の要素を検索するための鍵である第２の検索鍵とを生成する検索鍵生成手段と、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素が特定の値で検索されるための鍵である第１の被検索鍵と、前記第２の表の前記ｃ列目の要素が特定の値で検索されるための鍵である第２の被検索鍵とを生成する被検索鍵生成手段と、
前記秘密鍵を利用して、前記第１および第２の表の各要素を暗号化する暗号化手段と、
前記第１の表の前記ａ列目の要素を前記第１の被検索鍵と暗号化された前記ａ列目の要素、前記ｂ列目の要素を前記第１および第２の検索鍵から生成した検索暗号文と暗号化された前記ｂ列目の要素とでそれぞれ置換し、前記第２の表の前記ｃ列目の要素を前記第２の被検索鍵と暗号化された前記ｃ列目の要素で置換して、前記暗号化された第１および第２の表として前記暗号化データベースサーバに送信する検索暗号文生成手段と
を有し、
前記検索鍵生成手段が、前記秘密鍵を利用して前記第１の表の前記ａ列目の値がｑである要素を検索するための鍵である第３の検索鍵を生成し、前記部分結合命令と共に前記暗号化データベースサーバに送信する、
請求項１に記載の暗号化データベースシステム。
【請求項３】
前記暗号化データベースサーバが、
前記暗号化された第１の表で前記第３の検索鍵と前記第１の被検索鍵が一致する行を抽出する検索手段と、
前記第１の検索鍵と前記検索暗号文とから対象検索鍵を生成する導出手段と
を有し、
前記検索手段が、当該生成した対象検索鍵を用いて前記暗号化された第１および第２の表の前記抽出された行について前記ｂ列目およびｃ列目が等しいか否かを判断して前記結合を行う、
請求項２に記載の暗号化データベースシステム。
【請求項４】
前記クライアント端末が、
さらに、前記秘密鍵を利用して、前記第１の表のｂ列目と前記第２の表のｃ列目とを対応づけるための鍵である許可鍵を生成する許可鍵生成手段を有し、
前記検索暗号文生成手段が前記検索暗号文を前記第１および第２の検索鍵と前記許可鍵とから生成し、
前記暗号化データベースサーバの前記導出手段が前記第１の検索鍵と前記検索暗号文と前記許可鍵とから前記対象検索鍵を生成する、
請求項３に記載の暗号化データベースシステム。
【請求項５】
入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバに出力する暗号化手段と、
前記秘密鍵を利用して検索鍵を生成する検索鍵生成手段と
を備え、
前記検索鍵生成手段が、前記秘密鍵を利用して前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記検索鍵と共に前記暗号化データベースサーバに送信する、
クライアント端末。
【請求項６】
暗号化されたａ列目およびｂ列目のデータを有する第１の表およびｃ列目のデータを有する第２の表をクライアント端末から受信して記憶し、前記クライアント端末から受信した検索鍵を含む部分結合命令に応じて前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合して、前記クライアント端末に出力する検索手段を備え、
前記検索手段が、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合する、
暗号化データベースサーバ。
【請求項７】
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記クライアント端末が、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して前記暗号化データベースサーバに出力し、
前記暗号化データベースサーバが、前記暗号化された第１および第２の表を受信して記憶し、
前記クライアント端末が、前記暗号化された第１の表の前記ａ列目の値がｑであるデータについて前記暗号化された第１および第２の表を前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信し、
前記暗号化データベースサーバが、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する、
暗号化データ結合方法。
【請求項８】
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記クライアント端末が備えるコンピュータに、
入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して前記暗号化データベースサーバに出力する手順と、
前記暗号化された第１の表の前記ａ列目の値がｑであるデータについて前記暗号化された第１および第２の表を前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信する手順と、
を実行させる暗号化データ結合プログラムを格納する、コンピュータが読み取り可能な記録媒体。
【請求項９】
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記暗号化データベースサーバが備えるコンピュータに、
前記クライアント端末から暗号化されたａ列目およびｂ列目のデータを有する第１の表およびｃ列目のデータを有する第２の表を受信して記憶する手順と、
前記クライアント端末から受信した検索鍵を含む部分結合命令に応じて、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する手順と、
を実行させる暗号化データ結合プログラムを格納する、コンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化データベースシステム、クライアント端末、データベースサーバ、データ結合方法、および、プログラムに関し、特に、データの関連性が漏洩する危険性を軽減することを可能とする暗号化データベースシステム等に関する。
【背景技術】
【０００２】
企業などにおける業務の根幹がコンピュータ化されることによって、ほとんどの企業が業務で使用する大量のデータを収容する大規模データベースを持つようになっている。これらのデータは、業務上重要なデータであり、また個人情報保護の観点からも、外部に対して漏洩することは絶対にあってはならない。このため、そのような大規模データベースでは、収容されるデータが暗号化されていることが多い。【０００３】
データベースは、多くの表（テーブル）の集合体として捉えることができる。以下、非特許文献１に記載されている、収容されているデータが暗号化されたデータベース（以後暗号化データベースと記載する）で、各要素を復号化することなく２つの表を結合するために行われている、検索可能暗号と呼ばれる暗号方式について説明する。【０００４】
この方式では、暗号学的ハッシュ関数Ｈａｓｈと共通鍵暗号（Ｅｎｃ，Ｄｅｃ）を使用する。暗号化関数Ｅｎｃは、平文をｍ、暗号鍵をｋとすると、ｃ＝Ｅｎｃ（ｋ，ｍ）で暗号文ｃを生成し、復号化関数Ｄｅｃは、暗号文をｃ、暗号鍵をｋとすると、ｍ＝Ｄｅｃ（k，c）で暗号文ｃを復号化する。【０００５】
検索可能暗号では、秘密鍵の組（Ｋ，ｋ）を使用して、平文ｍを以下の数１に示すように暗号化する。復号化は以下の数２に示す形で処理可能である。【０００６】
【数１】
2013145627.tif 000003
【０００７】
【数２】
2013145627.tif 000004
【０００８】
この方式では、平文ｍが同一であれば、それらの暗号文の第一の要素Ｃ［１］は同一となる。即ち、暗号文を復号しなくても平文の同一性を判定することが可能であり、同一の要素について表を自然結合することが可能となる。【０００９】
図１４および１５は、検索可能暗号で、結合される前の表データについて示す説明図である。図１４は表「Ｉ」９０１を、図１５は表「ＩＩ」９０２を各々示す。表「Ｉ」９０１には列「ＩＡ」９０１ａおよび列「ＩＢ」９０１ｂがあり、表「ＩＩ」９０２には列「ＩＩＢ」９０２ａおよび列「ＩＩＣ」９０２ｂがある。【００１０】
図１６は、図１４および１５に示した表「Ｉ」９０１および表「ＩＩ」９０２を結合して得られる表「ＩＩＩ」９０３について示す説明図である。表「Ｉ」９０１の列「ＩＢ」９０１ｂ、および表「ＩＩ」９０２の列「ＩＩＢ」９０２ａは、いずれも「カード番号」についての列であるので、列「ＩＢ」＝列「ＩＩＢ」の条件で結合する（列「ＩＢ」および列「ＩＩＢ」で、要素の値が等しいデータ同士を結合する）ことが可能であり、これによって表「ＩＩＩ」９０３を得ることが可能である。【００１１】
図１７は、図１６に示した表「ＩＩＩ」９０３から、列「ＩＡ（名前）」が「上田」である行を抽出した表「ＩＩＩ’」９０４について示す説明図である。以上で示した処理では、表「Ｉ」９０１および表「ＩＩ」９０２の各要素は暗号化されていない。【００１２】
しかしながら、実際にはこれらが暗号化された状態で、各要素を復号化することなく、以上に示した処理を行う必要がある。そのためには、列「ＩＢ」および列「ＩＩＢ」で要素の値が等しいか否かを判断可能である必要がある。そこで、前述の検索可能暗号という暗号方式を利用する。【００１３】
図１８および１９は、図１４および１５に示した表「Ｉ」９０１および表「ＩＩ」９０２を、各々検索可能暗号によって暗号化した暗号化表「Ｉ」９１１および暗号化表「ＩＩ」９１２について示す説明図である。暗号化表「Ｉ」９１１および暗号化表「ＩＩ」９１２では、各要素が前述の数１に示した方式で、秘密鍵の組（Ｋ，ｋ）を利用して暗号化されている。【００１４】
図２０は、図１８および１９に示した暗号化表「Ｉ」９１１および暗号化表「ＩＩ」９１２を結合して得られる暗号化表「ＩＩＩ」９１３について示す説明図である。暗号化表「Ｉ」９１１および暗号化表「ＩＩ」９１２を結合するには、暗号化される前の列「ＩＢ」９０１ｂと列「ＩＩＢ」９０２ａの要素の値が等しいか否かを判断する必要がある。【００１５】
検索可能暗号によれば、暗号化された要素のＨａｓｈ（Ｋ，ｍ）とＨａｓｈ（Ｋ，ｍ’）とが等しいか否かを判断することによって、暗号化される前のｍとｍ’とが等しいか否かを判断することができるので、これによって暗号化表「ＩＩＩ」９１３を得ることができる。【００１６】
図２１は、図２０に示した暗号化表「ＩＩＩ」９１３から、列「ＩＡ（名前）」が「Ｈａｓｈ（Ｋ，上田）」である行を抽出した暗号化表「ＩＩＩ’」９１４について示す説明図である。以上で説明したように、ここまでで各要素を復号化することなく、暗号化表「ＩＩＩ’」９１４を得ることができる。秘密鍵の組（Ｋ，ｋ）を持つ正当なユーザであれば、これに対応する列「ＩＩＣ」９０２ｂの要素、この場合は「上田」さんのクレジットカードの「有効期限」について、その要素を復号化して知ることが可能である。【００１７】
これに関連する他の技術文献として、次の各々がある。特許文献１には、キーワードが暗号化されたままの状態でマッチング処理を行う暗号化データベース検索装置について記載されている。特許文献２には、暗号化されたキーワードによってインデックスファイルを生成して、これによって暗号化された状態のファイルの検索を可能とする技術が記載されている。【００１８】
特許文献３および４には、分散データベースシステムで表結合にかかる時間を低減する技術が記載されている。特許文献５には、検索が当たりか否かを識別可能な情報と、その情報を暗号化して得られる検索情報によって、部分一致検索が可能なキーワード検索システムについて記載されている。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特開２００５−１３４９９０号公報
【特許文献２】特開２０１０−０６１１０３号公報
【特許文献３】特開２０１０−２７２０３０号公報
【特許文献４】特開平０４−２１３７６５号公報
【特許文献５】特開２０１１−１４７０７４号公報
【非特許文献】
【００２０】
【非特許文献１】G.Amanatidis, A.Boldyreva, and A.O'Neill. Provably-secure schemes for basic query support in outsourced databases. In S.~Barker and G.-J. Ahn, editors, DBSec, volume 4602 of Lecture Notes in Computer Science, pages 14--30. Springer, 2007.
【発明の概要】
【発明が解決しようとする課題】
【００２１】
以上で説明したように、非特許文献１に記載された検索可能暗号による方式を利用すれば、暗号化したまま表を結合し、条件に一致する（特定の列の要素が指定された値と一致する）行を取り出すことが可能である。【００２２】
しかしながら、この方式では、最終的に得られる行以外の行に関しても表が結合される。前述の例でいえば、ユーザは「上田」さんのクレジットカードの有効期限について知ることができればよく、他のメンバの有効期限について知る必要は無い。それにもかかわらず、この方式では、「上田」さん以外のメンバの有効期限についても結合された、図１６や図２０に示したような表が作成される。【００２３】
通常、このようなデータベースシステムはクライアント−サーバ方式で運用されるので、この処理を行っている間は図１６や図２０に示したような「上田」さん以外のメンバの有効期限についても結合された表のデータがサーバ側の装置に記憶される。このため、その間にそのデータが漏洩する危険性を否定できない。【００２４】
図２０に示したように各データが暗号化されている場合、秘密鍵の組（Ｋ，ｋ）を持っていないユーザは具体的な名前や有効期限を知ることはできないが、結合関係からその暗号文同士の対応を推測することはできる。即ち、最終的に得られる行以外の行に関しても表が結合されるということは、データの関連性に関して必要以上に情報が漏洩する危険性があることを意味する。【００２５】
この問題を解決することが可能な技術は、前述の特許文献１〜５にも記載されていない。そもそもこれらの文献の中で、以上で説明した問題点について言及したものは無いので、当然ながらこれらの文献に記載された技術でこの問題を解決することはできない。【００２６】
本発明の目的は、データベースの暗号化された複数の表を復号化する事なく結合し、さらにデータの関連性が漏洩する危険性を軽減することを可能とする暗号化データベースシステム、クライアント端末、データベースサーバ、データ結合方法、および、プログラムを提供することにある。
【課題を解決するための手段】
【００２７】
本発明の一態様における暗号化データベースシステムは、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバに出力し、前記暗号化された第１の表と第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信するクライアント端末と、前記暗号化された第１および第２の表を受信して記憶し、前記部分結合命令に応じて前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する前記暗号化データベースサーバとを備えた暗号化データベースシステムであって、前記暗号化データベースサーバが、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合する。【００２８】
本発明の一態様におけるクライアント端末は、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバに出力する暗号化手段と、前記秘密鍵を利用して検索鍵を生成する検索鍵生成手段とを備え、前記検索鍵生成手段が、前記秘密鍵を利用して前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記検索鍵と共に前記暗号化データベースサーバに送信する。【００２９】
本発明の一態様における暗号化データベースサーバは、暗号化されたａ列目およびｂ列目のデータを有する第１の表およびｃ列目のデータを有する第２の表をクライアント端末から受信して記憶し、前記クライアント端末から受信した検索鍵を含む部分結合命令に応じて前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合して、前記クライアント端末に出力する暗号化データベースサーバであって、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合する検索手段を備える。【００３０】
本発明の一態様における暗号化データ結合方法は、クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、前記クライアント端末が、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して前記暗号化データベースサーバに出力し、前記暗号化データベースサーバが、前記暗号化された第１および第２の表を受信して記憶し、前記クライアント端末が、前記暗号化された第１の表の前記ａ列目の値がｑであるデータについて前記暗号化された第１および第２の表を前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信し、前記暗号化データベースシステムが、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する。【００３１】
本発明の一態様における第１のコンピュータが読み取り可能な記録媒体は、クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、前記クライアント端末が備えるコンピュータに、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して前記暗号化データベースサーバに出力する手順と、前記暗号化された第１の表の前記ａ列目の値がｑであるデータについて前記暗号化された第１および第２の表を前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信する手順と、を実行させる暗号化データ結合プログラムを格納する。【００３２】
本発明の一態様における第２のコンピュータが読み取り可能な記録媒体は、クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、前記暗号化データベースサーバが備えるコンピュータに、前記クライアント端末から暗号化されたａ列目およびｂ列目のデータを有する第１の表およびｃ列目のデータを有する第２の表を受信して記憶する手順と、前記クライアント端末から受信した検索鍵を含む部分結合命令に応じて、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する手順と、を実行させる。
【発明の効果】
【００３３】
本発明の効果は、データベースの暗号化された複数の表を復号化する事なく結合し、さらにデータの関連性が漏洩する危険性を軽減できることである。
【図面の簡単な説明】
【００３４】
【図１】本発明の第１の実施形態に係る暗号化データベースシステムの構成を示す説明図である。
【図２】図１に示したクライアント端末が表「Ｘ」および表「Ｙ」を暗号化して暗号化データベースサーバに送付する動作について説明する説明図である。
【図３】図２に示した暗号化される前の表「Ｘ」について示す説明図である。
【図４】図２に示した暗号化される前の表「Ｙ」について示す説明図である。
【図５】図３に示した表「Ｘ」が、図２に示した処理によって暗号化された暗号化表「Ｘ」について示す説明図である。
【図６】図４に示した表「Ｙ」が、図２に示した処理によって暗号化された暗号化表「Ｙ」について示す説明図である。
【図７】図１で示した暗号化データベースサーバが行う、図５〜６で示した暗号化表「Ｘ」および暗号化表「Ｙ」を結合して列「Ａ」の値がｑである行を抽出する処理について示す説明図である。
【図８】図１に示したクライアント端末および暗号化データベースサーバが行う処理について示すフローチャートである。
【図９】本発明の第２の実施形態に係る暗号化データベースシステムの構成を示す説明図である。
【図１０】図９に示したクライアント端末が図３〜４に示した表「Ｘ」および表「Ｙ」を暗号化して暗号化データベースサーバに送付する動作について説明する説明図である。
【図１１】図１０に示した暗号化／復号化部によって置換された暗号化表「Ｘ」について示す説明図である。
【図１２】図９で示した暗号化データベースサーバが行う、図６および図１１で示した暗号化表「Ｘ」および暗号化表「Ｙ」を結合して列「Ａ」の値がｑである行を抽出する処理について示す説明図である。
【図１３】図９に示したクライアント端末および暗号化データベースサーバが行う処理について示すフローチャートである。
【図１４】検索可能暗号で、結合される前の表「Ｉ」について示す説明図である。
【図１５】検索可能暗号で、結合される前の表「ＩＩ」について示す説明図である。
【図１６】図１４および１５に示した表「Ｉ」および表「ＩＩ」を結合して得られる表「ＩＩＩ」について示す説明図である。
【図１７】図１６に示した表「ＩＩＩ」から、列「ＩＡ（名前）」が「上田」である行を抽出した表「ＩＩＩ’」について示す説明図である。
【図１８】図１４に示した表「Ｉ」を、検索可能暗号によって暗号化した暗号化表「Ｉ」について示す説明図である。
【図１９】図１５に示した表「ＩＩ」を、検索可能暗号によって暗号化した暗号化表「ＩＩ」について示す説明図である。
【図２０】図１８および１９に示した暗号化表「Ｉ」９１１および暗号化表「ＩＩ」９１２を結合して得られる暗号化表「ＩＩＩ」について示す説明図である。
【図２１】図２０に示した暗号化表「ＩＩＩ」から、列「ＩＡ（名前）」が「Ｈａｓｈ（Ｋ，上田）」である行を抽出した暗号化表「ＩＩＩ’」について示す説明図である。
【図２２】本発明の第１の実施形態に係る暗号化データベースシステムの基本的な構成を示す説明図である。
【発明を実施するための形態】
【００３５】
（第１の実施形態）
以下、本発明の第１の実施形態の構成について、図１、２、７、２２に基づいて説明する。
【００３６】
最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。
【００３７】
図２２は、本発明の第１の実施形態に係る暗号化データベースシステム１の基本的な構成を示す説明図である。
【００３８】
本実施形態に係る暗号化データベースシステム１は、クライアント端末１０と暗号化データベースサーバ５０とを備える。クライアント端末１０は、入力されたａ列目およびｂ列目のデータを有する第１の表（表「Ａ」３１）とｃ列目のデータを有する第２の表（表「Ｂ」３２）とを予め記憶された秘密鍵３３によって暗号化して暗号化データベースサーバ５０に出力し、暗号化された第１の表と第２の表をａ列目の値がｑであるデータについてｂ列目およびｃ列目をキーとして結合させる部分結合命令を秘密鍵から生成された検索鍵と共に暗号化データベースサーバ５０に送信する。暗号化データベースサーバ５０は、暗号化された第１および第２の表を受信して記憶し、部分結合命令に応じて暗号化された第１および第２の表をａ列目の値がｑであるデータについてｂ列目およびｃ列目をキーとして結合し、クライアント端末に返送する。ここで、暗号化データベースサーバ５０は、検索鍵を利用して暗号化された第１および第２の表からａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対してｂ列目およびｃ列目をキーとして結合する。
【００３９】
ここでクライアント端末１０は、検索鍵生成部２１と、被検索鍵生成部２２と、暗号化部２５と、検索暗号文生成部２４と、を備える。検索鍵生成部２１は、秘密鍵３３を利用して、第１の表のａ列目の要素を検索するための鍵である第１の検索鍵と、第１の表のｂ列目の要素を検索するための鍵である第２の検索鍵とを生成する。被検索鍵生成部２２は、秘密鍵３３を利用して、第１の表のａ列目の要素が特定の値で検索されるための鍵である第１の被検索鍵と、第２の表のｃ列目の要素が特定の値で検索されるための鍵である第２の被検索鍵とを生成する。暗号化部２５は、秘密鍵を利用して、第１および第２の表の各要素を暗号化する。検索暗号文生成部２４は、第１の表のａ列目の要素を第１の被検索鍵と暗号化されたａ列目の要素、ｂ列目の要素を第１および第２の検索鍵から生成した検索暗号文と暗号化されたｂ列目の要素とでそれぞれ置換し、第２の表のｃ列目の要素を第２の被検索鍵と暗号化されたｃ列目の要素で置換して、暗号化された第１および第２の表として暗号化データベースサーバ５０に送信する。そして、検索鍵生成部２１は、秘密鍵３３を利用して第１の表のａ列目の値がｑである要素を検索するための鍵である第３の検索鍵を生成し、部分結合命令と共に暗号化データベースサーバ５０に送信する。
【００４０】
これに対する暗号化データベースサーバ５０は、検索部６１と、導出部６２と、を備える。検索部６１は、暗号化された第１の表で第３の検索鍵と第１の被検索鍵が一致する行を抽出する。導出部６２は、第１の検索鍵と検索暗号文とから対象検索鍵を生成する。そして、検索部６１は、この対象検索鍵を用いて暗号化された第１および第２の表の抽出された行についてｂ列目およびｃ列目が等しいか否かを判断して結合を行う。
【００４１】
この構成を備えることにより、暗号化データベースシステム１はデータベースの暗号化された複数の表を復号化する事なく結合し、さらにデータの関連性が漏洩する危険性を軽減することが可能となる。
【００４２】
以下、これをより詳細に説明する。
【００４３】
図１は、本発明の第１の実施形態に係る暗号化データベースシステム１の構成を示す説明図である。暗号化データベースシステム１は、クライアント端末１０と暗号化データベースサーバ５０とが、ＬＡＮ（Local Area Network）などを介して相互に接続されて構成される。
【００４４】
クライアント端末１０は、一般的なコンピュータ装置としての構成を備える。即ち、クライアント端末１０は、コンピュータプログラムを実行する主体となるプロセッサ１１と、データを記憶する記憶手段１２と、ユーザからの操作を受け付ける入力手段１３と、ユーザに処理結果を提示する出力手段１４と、他のコンピュータとのデータ通信を行う通信手段１５とを備える。
【００４５】
プロセッサ１１では、ユーザからの操作命令に応じて、初期設定部２０、検索鍵生成部２１、被検索鍵生成部２２、検索暗号文生成部２４、および暗号化／復号化部２５が、各々コンピュータプログラムとして後述するそれぞれの機能を実行するように構成されている。また、記憶手段１２には以後に説明する処理で使用する秘密鍵３３が記憶されている。
【００４６】
そして入力手段１３には、名称が各々「Ｘ」および「Ｙ」である表「Ｘ」３１および表「Ｙ」３２が入力される。以後、本明細書では、名称「Ｘ」である表の名称「Ａ」である列の、値が「ａ」である要素を、表「Ｘ」の列「Ａ」の要素「ａ」と記載する。
【００４７】
暗号化データベースサーバ５０もまた、一般的なコンピュータ装置としての構成を備える。即ち、暗号化データベースサーバ５０は、コンピュータプログラムを実行する主体となるプロセッサ５１と、データを記憶する記憶手段５２と、他のコンピュータとのデータ通信を行う通信手段５３とを備える。
【００４８】
プロセッサ５１では、クライアント端末１０からの操作命令に応じて、検索部６１、および導出部６２が、コンピュータプログラムとして後述するそれぞれの機能を実行するように構成されている。また、記憶手段５２には表「Ｘ」３１および表「Ｙ」３２を各々暗号化してクライアント端末１０から送付された暗号化表「Ｘ」４１および暗号化表「Ｙ」４２が記憶される。
【００４９】
上述した各手段の、基本的な動作について説明する。クライアント端末１０と暗号化データベースサーバ５０には、各種のシステム変数が入力されるか、もしくは予め記憶されている。以下の説明では、それらのシステム変数については当業者にとって公知の事項であるので、必要なシステム変数以外は特に説明しない。
【００５０】
まずクライアント端末１０の側で、初期設定部２０は、各部の動作に必要な初期値を設定する。この詳細については後述する。
【００５１】
検索鍵生成部２１は、表「Ｘ」３１の列「Ａ」、列「Ａ」の要素「ａ」に対して、表「Ｘ」３１の列「Ａ」の要素「ａ」を検索するための鍵である「検索鍵（Ｘ，Ａ，ａ）」を、秘密鍵３３を利用して生成する。この検索鍵生成部２１を関数と考えると、以下の数３のように表現される。
【００５２】
【数３】
2013145627.tif 000005
【００５３】
被検索鍵生成部２２は、表「Ｘ」３１の列「Ａ」、列「Ａ」の要素「ａ」に対して、表「Ｘ」３１の列「Ａ」の要素「ａ」として検索される鍵である「被検索鍵（Ｘ，Ａ，ａ）」を、秘密鍵３３を利用して生成する。この被検索鍵生成部２２を関数と考えると、以下の数４のように表現される。
【００５４】
【数４】
2013145627.tif 000006
【００５５】
検索暗号文生成部２４は、２つの検索鍵「Ｋ１」および「Ｋ２」に対して、検索鍵「Ｋ１」を検索鍵「Ｋ２」に対応させるための情報である「検索暗号文（Ｋ１，Ｋ２）」を、秘密鍵を用いて生成する。この検索暗号文生成部２４を関数と考えると、以下の数５のように表現される。
【００５６】
【数５】
2013145627.tif 000007
【００５７】
暗号化データベースサーバ５０の側で、検索部６１は、表「Ｘ」３１の列「Ａ」の要素「ａ」に対して生成された「被検索鍵（Ｘ，Ａ，ａ）」と、表「Ｘ」３１の列「Ａ」の要素「ａ’」に対して生成された「検索鍵（Ｘ，Ａ，ａ’）」との間で、ａ＝ａ’であるか否かを「被検索鍵（Ｘ，Ａ，ａ）」と「検索鍵（Ｘ，Ａ，ａ’）」から判定する。この検索部６１を関数と考えると、以下の数６のように表現される。ここで、０を一致、１を不一致と解釈する。
【００５８】
【数６】
2013145627.tif 000008
【００５９】
導出部６２は、表「Ｘ」３１の列「Ａ」、列「Ａ」の要素「ａ」、表「Ｙ」３２の列「Ｂ」、および列「Ｂ」の存在を仮定する要素「ｂ」に関する検索鍵を各々「Ｋ１＝検索鍵（Ｘ，Ａ，ａ）」および「Ｋ２＝検索鍵（Ｙ，Ｂ，ｂ）」として、このＫ２を対象検索鍵として、検索鍵「Ｋ１」と「検索暗号文（Ｋ１，Ｋ２）」とから対象検索鍵「Ｋ２」を導出する。この導出部６２を関数と考えると、以下の数７のように表現される。
【００６０】
【数７】
2013145627.tif 000009
【００６１】
クライアント端末１０側に戻って、暗号化／復号化部２５は、暗号文ｃを秘密鍵によって復号する。また、暗号化／復号化部２５は、逆に、要素ｍを秘密鍵によって暗号化することもできる。この暗号化／復号化部２５を関数と考えると、以下の数８〜９のように表現される。
【００６２】
【数８】
2013145627.tif 000010
【００６３】
【数９】
2013145627.tif 000011
【００６４】
（暗号化表の作成および送付）
図２は、図１に示したクライアント端末１０が表「Ｘ」３１および表「Ｙ」３２を暗号化して暗号化データベースサーバ５０に送付する動作について説明する説明図である。図３〜４は、図２に示した暗号化される前の表「Ｘ」３１および表「Ｙ」３２について示す説明図である。図３は表「Ｘ」３１、図４は表「Ｙ」３２について各々示している。
【００６５】
クライアント端末１０に入力手段１３を介して入力される表「Ｘ」３１および表「Ｙ」３２は、表「Ｘ」３１には列「Ａ」３１ａと列「Ｂ」３１ｂ、表「Ｙ」３２には列「Ｃ」３２ｃが存在する。列「Ｂ」３１ｂと列「Ｃ」３２ｃが値を取る領域は同一である。
【００６６】
表「Ｘ」３１の行数は自然数ｎであり、表「Ｘ」３１の列「Ａ」３１ａおよび列「Ｂ」３１ｂのｉ番目の要素（１≦ｉ≦ｎ）を各々「ａ［ｉ］」，「ｂ［ｉ］」と記載する。表「Ｙ」３２の行数は自然数ｍであり、表「Ｙ」３２の列「Ｃ」３２ｃのｉ番目の要素（１≦ｉ≦ｎ）を「ｃ［ｉ］」と記載する。
【００６７】
被検索鍵生成部２２は、ｉの取りうる１〜ｎの全ての値に対して、表「Ｘ」３１、列「Ａ」３１ａ、要素「ａ［ｉ］」、および秘密鍵３３から、数４で示した「被検索鍵（Ｘ，Ａ，ａ［ｉ］）」を生成する。これを図２では第１の被検索鍵３４ａで示す。
【００６８】
検索鍵生成部２１は、ｉの取りうる１〜ｎの全ての値に対して、表「Ｘ」３１、列「Ａ」３１ａ、要素「ａ［ｉ］」、および秘密鍵３３から、数３で示した「検索鍵（Ｘ，Ａ，ａ［ｉ］）」を生成する。これを図２では第１の検索鍵３４ｂで示す。
【００６９】
また、検索鍵生成部２１は、ｉの取りうる１〜ｎの全ての値に対して、表「Ｙ」３２、列「Ｃ」３２ｃ、列Ｂの要素「ｂ［ｉ］」、および秘密鍵３３から、数３で示した「検索鍵（Ｙ，Ｃ，ｂ［ｉ］）」を生成する。これを図２では第２の検索鍵３４ｃで示す。
【００７０】
なお、図面の錯綜を回避するため、図２では検索鍵生成部２１および被検索鍵生成部２２をそれぞれ２カ所ずつ表出している。これらはそれぞれ、同一の構成要素を示している。
【００７１】
検索暗号文生成部２４は、ｉの取りうる１〜ｎの全ての値に対して、第１の検索鍵３４ｂ、第２の検索鍵３４ｃ、および秘密鍵３３から、数５で示した「検索暗号文（第１の検索鍵，第２の検索鍵)」を生成する。これを図２では検索暗号文３４ｆで示す。
【００７２】
暗号化／復号化部２５は、ｉの取りうる１〜ｎの全ての値に対して、要素「ａ［ｉ］」、および秘密鍵３３から、数８に示した各要素の暗号文「ｅｎｃ（ａ［ｉ］）」を生成し、また同様に、要素「ｂ［ｉ］」、および秘密鍵３３から、数８に示した各要素の暗号文「ｅｎｃ（ｂ［ｉ］）」を生成する。
【００７３】
また、暗号化／復号化部２５は、ｉの取りうる１〜ｎの全ての値に対して、表「Ｘ」３１で、列「Ａ」３１ａの要素「ａ［ｉ］」を（第１の被検索鍵，ｅｎｃ（ａ［ｉ］））に置換し、同様に列「Ｂ」３１ｂの要素「ｂ［ｉ］」を（検索暗号文（第１の検索鍵，第２の検索鍵)，ｅｎｃ（ｂ［ｉ］））に置換する。この置換された表「Ｘ」３１を、暗号化表「Ｘ」４１で示す。
【００７４】
一方で、被検索鍵生成部２２は、ｉの取りうる１〜ｍの全ての値に対して、表「Ｙ」３２、列「Ｃ」３２ｃ、列Ｃの要素「ｃ［ｉ］」、および秘密鍵３３から、数４で示した「被検索鍵（Ｙ，Ｃ，ｃ［ｉ］）」を生成する。これを図２では第２の被検索鍵３４ｄで示す。
【００７５】
暗号化／復号化部２５は、ｉの取りうる１〜ｍの全ての値に対して、要素「ｃ［ｉ］」、および秘密鍵３３から、数８に示した各要素の暗号文「ｅｎｃ（ｃ［ｉ］）」を生成する。また、ｉの取りうる１〜ｍの全ての値に対して、表「Ｙ」３２で、列「Ｃ」３２ｃの要素「ｃ［ｉ］」を（第２の被検索鍵，ｅｎｃ（ｃ［ｉ］））に置換する。この置換された表「Ｙ」３２を、暗号化表「Ｙ」４２で示す。
【００７６】
暗号化／復号化部２５は、以上で作成された暗号化表「Ｘ」４１および暗号化表「Ｙ」４２を、暗号化データベースサーバ５０に送付する。図５〜６は、図３〜４に示した表「Ｘ」３１および表「Ｙ」３２が、図２に示した処理によって暗号化された暗号化表「Ｘ」４１および暗号化表「Ｙ」４２について示す説明図である。図５は暗号化表「Ｘ」４１、図６は暗号化表「Ｙ」４２について各々示している。
【００７７】
暗号化データベースサーバ５０は、クライアント端末１０から受信した暗号化表「Ｘ」４１および暗号化表「Ｙ」４２を、記憶手段５２に保存する。そして、クライアント端末１０からのコマンドによって、暗号化表「Ｘ」４１および暗号化表「Ｙ」４２に対して結合処理を行い、この結果を依頼元のクライアント端末１０に返す。以下、その処理について説明する。
【００７８】
（暗号化表に対する結合処理）
ここでは、暗号化表「Ｘ」４１および暗号化表「Ｙ」４２の、列「Ｂ」の要素「ｂ［ｉ］」と列「Ｃ」の要素「ｃ［ｉ］」とが等しくなるデータに対して結合を行うことを考える。より具体的には、暗号化表「Ｘ」４１の列「Ａ」３１ａの値がｑである行を暗号化表「Ｚ」４３から抽出する処理について本実施形態では説明する。
【００７９】
一般的に、暗号化表「Ｚ」４３から、ｑの他に複数の値を指定することによって、列「Ａ」３１ａの値を限定した表を生成することが可能となる。このような結合処理を、本明細書では「部分結合」と記載する。
【００８０】
クライアント端末１０は、暗号化表「Ｘ」４１および暗号化表「Ｙ」４２を暗号化する際に使用された秘密鍵３３を保持しているが、暗号化データベースサーバ５０はこれを保持していない。
【００８１】
図７は、図１で示した暗号化データベースサーバ５０が行う、図５〜６で示した暗号化表「Ｘ」４１および暗号化表「Ｙ」４２を結合して列「Ａ」の値がｑである行を抽出する処理について示す説明図である。まずクライアント端末１０の検索鍵生成部２１が、表「Ｘ」３１、列「Ａ」３１ａ、要素「ａ［ｉ］」、および秘密鍵３３から、数３で示した「検索鍵（Ｘ，Ａ，ｑ）」を生成する。
【００８２】
クライアント端末１０から、以上の「検索鍵（Ｘ，Ａ，ｑ）」が、部分結合コマンドと共に暗号化データベースサーバ５０に送信される。図８では、これを第３の検索鍵３５ａとして示している。
【００８３】
これを受けた暗号化データベースサーバ５０では、検索部６１が、第３の検索鍵３５ａ＝検索鍵（Ｘ，Ａ，ｑ）および被検索鍵３４ａ＝被検索鍵（Ｘ，Ａ，ａ［ｉ］）を入力として、これが暗号化表「Ｘ」４１の列「Ａ」３１ａの要素である第１の被検索鍵３４ａ＝被検索鍵（Ｘ，Ａ，ａ［ｉ］）と一致するｉを、ｉの取りうる１〜ｎの全ての値に対して検索し、判定結果＝０（一致）が出力されるｉを全て発見する。このようなｉの集合をＳと記載する。ここでｉ∈Ｓならａ［ｉ］＝ｑである。
【００８４】
引き続いて導出部６２が、集合Ｓの全ての要素ｉに関して、第３の検索鍵３５ａ＝（Ｘ，Ａ，ｑ）、検索暗号文３４ｆ＝（検索鍵（Ｘ，Ａ，ａ［ｉ］），検索鍵（Ｙ，Ｃ，ｂ［ｉ］））から、数７に示された対象検索鍵４４ａ＝検索鍵（Ｙ，Ｃ，ｂ［ｉ］）を生成する。
【００８５】
そして検索部６１が、集合Ｓの全ての要素ｉに対して、対象検索鍵４４ａ＝検索鍵（Ｙ，Ｃ，ｂ［ｉ］）と、暗号化表「Ｙ」４２の列Ｃの要素である第２の被検索鍵３４ｄ＝被検索鍵（Ｙ，Ｃ，ｃ［ｊ］）で、一致するか否かの判定結果＝０（一致する）である行番号ｊを対応づける。このようなｊをｊ［ｉ］と表記する。検索部６１は、一致すると判定した暗号化表「Ｘ」４１のｉ行目と暗号化表「Ｙ」４２のｊ行目とを結合して、新たな行Ｒ［ｉ］を作成する。検索部６１は、全てのｉ∈ＳについてＲ［ｉ］をクライアント端末１０に返送する。
【００８６】
なお、図面の錯綜を回避するため、図２と同様に図７でも検索部６１を２カ所に表出している。図２と同様に、これらも同一の構成要素を示している。後述する図１０および図１２においても同様である。
【００８７】
クライアント端末１０は、暗号化／復号化部２５によって、Ｒ［ｉ］の要素であるｅｎｃ（ａ［ｉ］），ｅｎｃ（ｂ［ｉ］），ｅｎｃ（ｃ［ｉ］）を復号化して、各列要素の原文ａ［ｉ］，ｂ［ｉ］，ｃ［ｉ］を得ることができる。また、適切な検索暗号文３４ｆが予め作成されていれば、対象検索鍵４４ａ＝検索鍵（Ｙ，Ｃ，ｂ［ｉ］）を利用して、列「Ｃ」とさらに他の列との間で結合を取ることもできる。
【００８８】
（より詳細な実施形態の説明）
以上で説明した各手段の動作について、それらの動作をより詳細に説明する。
【００８９】
図８は、図１に示したクライアント端末１０および暗号化データベースサーバ５０が行う処理について示すフローチャートである。クライアント端末１０の側で、初期設定部２０は、入力手段１３を介して入力された安全変数κから、以下の数１０で示される秘密鍵ＭＫをランダムに選択する（ステップＳ１０１）。
【００９０】
【数１０】
2013145627.tif 000012
【００９１】
そして初期設定部２０はさらに、システム変数ＰＭを、以下の数１１で示されるハッシュ関数、表の名前の空間、列の名前の空間、列の要素の空間の表現方法の記述として定義し、これらのシステム変数ＰＭおよび秘密鍵ＭＫを出力する（ステップＳ１０２）。
【００９２】
【数１１】
2013145627.tif 000013
【００９３】
検索鍵生成部２１は、システム変数ＰＭ、秘密鍵ＭＫ、表の名前ＴＮ（図３〜４でいう「Ｘ」「Ｙ」）、列の名前ＣＮ（図３〜４でいう「Ａ」「Ｂ」「Ｃ」）、および要素の値ＥＶ（図３〜４でいう「ａ［ｉ］」「ｂ［ｉ］」「ｃ［ｉ］」）を入力として、以下の数１２で示される検索鍵ＳＫを生成して出力する（ステップＳ１０３）。
【００９４】
【数１２】
2013145627.tif 000014
【００９５】
被検索鍵生成部２２は、システム変数ＰＭ、秘密鍵ＭＫ、表の名前ＴＮ（同上）、列の名前ＣＮ（同上）、および要素の値ＥＶ（同上）を入力として、以下の数１３で示される被検索鍵ＳＫＤを生成して出力する（ステップＳ１０４）。
【００９６】
【数１３】
2013145627.tif 000015
【００９７】
検索暗号文生成部２４は、システム変数ＰＭ、第１の検索鍵ＳＫ、および第２の検索鍵ＳＫ’を入力として、以下の数１４で示される検索暗号文ＣＰを生成して出力する（ステップＳ１０５）。
【００９８】
【数１４】
2013145627.tif 000016
【００９９】
暗号化／復号化部２５は、前述した（図５〜６に示した）ように表「Ｘ」３１および表「Ｙ」３２の各要素を置換して暗号化表「Ｘ」４１および暗号化表「Ｙ」４２を作成する（ステップＳ１０６）。そして、暗号化／復号化部２５は、これらの暗号化表「Ｘ」４１および暗号化表「Ｙ」４２を暗号化データベースサーバ５０に送付する。暗号化データベースサーバ５０では、これらを受信して記憶手段５２に記憶する（ステップＳ１５１）。
【０１００】
クライアント端末１０では、その後で、検索鍵生成部２１が数１２で示される検索鍵ＳＫ＝第３の検索鍵３５ａを生成して、部分結合コマンドと共に暗号化データベースサーバ５０に送信する（ステップＳ１０７）。
【０１０１】
暗号化データベースサーバ５０で、検索部６１は、システム変数ＰＭ、検索鍵ＳＫ、および被検索鍵ＳＫＤを入力として、以下の数１５で示されるように検索鍵ＳＫと被検索鍵ＳＫＤとを比較し、一致すれば０、一致しなければ１を出力する処理を、全ての行に対して行う。検索部６１は、０が出力される、即ち第３の検索鍵ＳＫ＝検索鍵（Ｘ，Ａ，ｑ）と第１の被検索鍵ＳＫＤ＝被検索鍵（Ｘ，Ａ，ａ［ｉ］）とが一致する行番号ｉの集合Ｓを求める（ステップＳ１５２）。
【０１０２】
【数１５】
2013145627.tif 000017
【０１０３】
導出部６２は、全てのｉ∈Ｓに対して、システム変数ＰＭ、検索鍵ＳＫ、および検索暗号文ＣＰを入力として、以下の数１６で示される対象検索鍵ＳＫ’＝検索鍵（Ｙ，Ｃ，ｂ［ｉ］）を生成して出力する（ステップＳ１５３）。
【０１０４】
【数１６】
2013145627.tif 000018
【０１０５】
そして検索部６１は、ここで算出された対象検索鍵ＳＫ’を利用して、全てのｉ∈Ｓに対して、この対象検索鍵ＳＫ’と第２の被検索鍵３４ｄ＝被検索鍵（Ｙ，Ｃ，ｃ［ｊ］）が一致するか否かを判定する。検索部６１は、一致すると判定した暗号化表「Ｘ」４１のｉ行目と暗号化表「Ｙ」４２のｊ行目とを結合して、新たな行Ｒ［ｉ］を作成する。検索部６１は、全てのｉ∈ＳについてＲ［ｉ］をクライアント端末１０に返送する（ステップＳ１５４）。
【０１０６】
クライアント端末１０では、このＲ［ｉ］を暗号化／復号化部２５が秘密鍵３３によって復号化することによって、表「Ｘ」３１と表「Ｙ」３２とが結合され、かつ列「Ａ」の値がｑである行を得る（ステップＳ１０８）。
【０１０７】
（第１の実施形態の全体的な動作）
次に、上記の実施形態の全体的な動作について説明する。
【０１０８】
クライアント端末１０は、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバ５０に出力する（図８・ステップＳ１０１〜１０６）。暗号化データベースサーバ５０は、暗号化された第１および第２の表を受信して記憶する（図８・ステップＳ１５１）。クライアント端末１０は、暗号化された第１の表のａ列目の値がｑであるデータについて暗号化された第１および第２の表をｂ列目およびｃ列目をキーとして結合させる部分結合命令を秘密鍵から生成された検索鍵と共に暗号化データベースサーバ５０に送信する（図８・ステップＳ１０７）。暗号化データベースサーバ５０は、検索鍵を利用して暗号化された第１および第２の表からａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対してｂ列目およびｃ列目をキーとして結合して、クライアント端末１０に返送する（図８・ステップＳ１５２〜１５４）。
【０１０９】
ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータであるクライアント端末１０および暗号化データベースサーバ５０に実行させてもよい。本プログラムは、非一時的な記録媒体、例えば、ＤＶＤ、ＣＤ、フラッシュメモリ等に記録されてもよい。その場合、本プログラムは、記録媒体からコンピュータによって読み出され、実行される。
【０１１０】
この動作により、本実施形態は以下のような効果を奏する。
【０１１１】
本実施形態において、検索暗号文ＣＰは、検索鍵ＳＫから対象検索鍵ＳＫ’を導出することができる。即ち、前述した結合の例にあるように、ある表の検索暗号文ＣＰを含む行は、他の表の結合されるべき行を検索するための対象検索鍵ＳＫ’を導出するために使用することが可能である。
【０１１２】
同時に、この導出は検索鍵ＳＫを必要とする。即ち、生成される被検索鍵の値が列の名前に依存することから帰結される事であるが、同じ値でも異なる列にある場合は対応する被検索鍵からその同一性が判断できない。したがって、検索鍵ＳＫが与えられなければどの表のどの列と結合するかを知ることは不可能となる。
【０１１３】
従って、本実施形態に示した方法を利用すれば、表を復号化することなく、必要な行だけについて部分結合した表を得ることができる。必要の無い行については結合が行われることはないので、対応関係が類推される危険性が生じることもない。これによって、前述したような「データの関連性に関する情報が漏洩する危険性」を軽減することが可能となる。
【０１１４】
本発明は、上述したように、クライアント端末で秘密鍵から生成された検索鍵を利用して、データベースサーバが第１および第２の表で要素の値がｑであるデータを判定して抽出し、それらのデータについてのみ第１および第２の表を結合してクライアント端末に返送するように構成したので、各々の表が復号化されることはなく、かつ必要以上にデータの結合が行われることもない。
【０１１５】
（第２の実施形態）
本発明の第２の実施形態は、第１の実施形態の構成に加えて、クライアント端末２１０が、さらに、秘密鍵を利用して、第１の表のｂ列目と第２の表のｃ列目とを対応づけるための鍵である許可鍵を生成する許可鍵生成部２２３を備えると共に、検索暗号文生成部２２４が検索暗号文を第１および第２の検索鍵と許可鍵とから生成する。そして、暗号化データベースサーバ２５０の導出部２６２が第１の検索鍵と検索暗号文と許可鍵とから対象検索鍵を生成する。
【０１１６】
この構成によっても、第１の実施形態と同一の効果が得られるのに加えて、３つ以上の表においてデータ間の対応関係が芋蔓式に発見されることを防止して、管理者がデータの結合が可能な範囲を適切に設定することが可能となる。
【０１１７】
以下、これをより詳細に説明する。
【０１１８】
図９は、本発明の第２の実施形態に係る暗号化データベースシステム２０１の構成を示す説明図である。暗号化データベースシステム２０１は、前述した第１の実施形態の暗号化データベースシステム１の、クライアント端末１０および暗号化データベースサーバ５０が、各々別のクライアント端末２１０および暗号化データベースサーバ２５０に置換されている。
【０１１９】
クライアント端末２１０は、ハードウェア的には第１の実施形態のクライアント端末１０と同一の構成を備える。そしてソフトウェア的にも、プロセッサ１１で動作する各機能部に許可鍵生成部２２３が追加され、かつ検索暗号文生成部２４が別の検索暗号文生成部２２４に置換されている点以外は、第１の実施形態と同一の構成である。
【０１２０】
一方の暗号化データベースサーバ２５０も、ハードウェア的には第１の実施形態の暗号化データベースサーバ５０と同一の構成を備える。そしてソフトウェア的にも、プロセッサ５１で動作する導出部６２が別の導出部２６２に置換されている点以外は、第１の実施形態と同一の構成である。従って、第１の実施形態と同一の構成については同一の呼称と参照番号を用い、相違点のみをここでは説明する。
【０１２１】
クライアント端末２１０の側で、許可鍵生成部２２３は、表「Ｘ」３１の列「Ａ」、表「Ｙ」３２の列「Ｂ」に対して、表「Ｘ」３１の列「Ａ」の特定の要素から、これに対応する表「Ｙ」３２の列「Ｂ」の特定の要素を導くことを許可する情報「許可鍵（（Ｘ，Ａ）→（Ｙ，Ｂ））」を、秘密鍵を用いて生成する。この許可鍵生成部２２３を関数と考えると、以下の数１７のように表現される。
【０１２２】
【数１７】
2013145627.tif 000019
【０１２３】
検索暗号文生成部２２４は、２つの検索鍵「Ｋ１」および「Ｋ２」に加えて許可鍵「Ｐ」を必要とする場合の「検索暗号文（Ｋ１，Ｋ２，Ｐ）」を、秘密鍵を用いて生成する。この検索暗号文生成部２２４を関数と考えると、以下の数１８のように表現される。
【０１２４】
【数１８】
2013145627.tif 000020
【０１２５】
暗号化データベースサーバ２５０の側で、導出部２６２は、表「Ｘ」３１の列「Ａ」、列「Ａ」の要素「ａ」、表「Ｙ」３２の列「Ｂ」、および列「Ｂ」の存在を仮定する要素「ｂ」に関する検索鍵「Ｋ１＝検索鍵（Ｘ，Ａ，ａ）」、「Ｋ２＝検索鍵（Ｙ，Ｂ，ｂ）」および許可鍵「Ｐ」に対して、検索鍵「Ｋ１」と「検索暗号文（Ｋ１，Ｋ２，Ｐ）」とから対象検索鍵「Ｋ２」を導出する。この導出部２６２を関数と考えると、以下の数１９のように表現される。
【０１２６】
【数１９】
2013145627.tif 000021
【０１２７】
（暗号化表の作成および送付）
図１０は、図９に示したクライアント端末２１０が図３〜４に示した表「Ｘ」３１および表「Ｙ」３２を暗号化して暗号化データベースサーバ２５０に送付する動作について説明する説明図である。
【０１２８】
なお、図面の錯綜を回避するため、図２と同様に図１０でも検索鍵生成部２１および被検索鍵生成部２２をそれぞれ２カ所ずつ表出している。図２と同様に、これらもそれぞれ、同一の構成要素を示している。
【０１２９】
許可鍵生成部２２３は、表「Ｘ」３１、列「Ｂ」３１ｂ、表「Ｙ」３２、列「Ｃ」３２ｃ、および秘密鍵３３から、数１７で示した「許可鍵（（Ｘ，Ｂ）→（Ｙ，Ｃ））」を生成する。これを図１０では許可鍵２３４ｅで示す。
【０１３０】
検索暗号文生成部２２４は、ｉの取りうる１〜ｎの全ての値に対して、第１の検索鍵３４ｂ、第２の検索鍵３４ｃ、許可鍵２３４ｅ、および秘密鍵３３から、数１８で示した「検索暗号文（第１の検索鍵，第２の検索鍵，許可鍵)」を生成する。これを図１０では検索暗号文２３４ｆで示す。ここで、許可鍵を検索暗号文２３４ｆに含めるか否か、即ち許可鍵の要否は、クライアント端末１０側でユーザが任意に指定できる。
【０１３１】
図１１は、図１０に示した暗号化／復号化部２５によって置換された暗号化表「Ｘ」２４１について示す説明図である。暗号化／復号化部２５は、第１の実施形態と同じ処理で、表「Ｘ」３１で、列「Ａ」３１ａの要素「ａ［ｉ］」を（第１の被検索鍵，ｅｎｃ（ａ［ｉ］））に置換し、同様に列「Ｂ」３１ｂの要素「ｂ［ｉ］」を（検索暗号文（第１の検索鍵，第２の検索鍵，許可鍵)，ｅｎｃ（ｂ［ｉ］））に置換して、暗号化表「Ｘ」２４１を作成する。暗号化／復号化部２５が表「Ｙ」３２の要素を置換して暗号化表「Ｙ」４２を作成する処理については、第１の実施形態と全く同一である。
【０１３２】
暗号化データベースサーバ２５０は、クライアント端末２１０から受信した暗号化表「Ｘ」２４１および暗号化表「Ｙ」４２を、記憶手段５２に保存する。そして、クライアント端末２１０からのコマンドによって、暗号化表「Ｘ」２４１および暗号化表「Ｙ」４２に対して結合処理を行い、この結果を依頼元のクライアント端末２１０に返す。以下、その処理について説明する。
【０１３３】
（暗号化表に対する結合処理）
ここでは、第１の実施形態と同様に、暗号化表「Ｘ」２４１および暗号化表「Ｙ」４２の、列「Ｂ」の要素「ｂ［ｉ］」と列「Ｃ」の要素「ｃ［ｉ］」とが等しくなるデータに対して結合を行うことを考える。
【０１３４】
クライアント端末１０は、暗号化表「Ｘ」２４１および暗号化表「Ｙ」４２を暗号化する際に使用された秘密鍵３３を保持しているが、暗号化データベースサーバ２５０はこれを保持していない。そして暗号化データベースサーバ２５０は、これらの暗号化表を結合して列「Ａ」３１ａの値がｑである行を抽出する処理を、これらの表を復号化せずに行う。
【０１３５】
図１２は、図９で示した暗号化データベースサーバ２５０が行う、図６および図１１で示した暗号化表「Ｘ」２４１および暗号化表「Ｙ」４２を結合して列「Ａ」の値がｑである行を抽出する処理について示す説明図である。まずクライアント端末２１０の検索鍵生成部２１が、第１の実施形態と同様に、数３で示した「検索鍵（Ｘ，Ａ，ａ［ｉ］）」を生成する。
【０１３６】
そして、許可鍵生成部２２３は、表「Ｘ」３１、列「Ｂ」３１ｂ、表「Ｙ」３２、列「Ｃ」３２ｃ、および秘密鍵３３から、数１７で示した「許可鍵（（Ｘ，Ｂ）→（Ｙ，Ｃ））」を生成する。
【０１３７】
クライアント端末２１０から、以上の「検索鍵（Ｘ，Ａ，ａ［ｉ］）」と「許可鍵（（Ｘ，Ｂ）→（Ｙ，Ｃ））」が、部分結合コマンドと共に暗号化データベースサーバ２５０に送信される。図１２では、これらを各々検索鍵３５ａ、許可鍵２３５ｂとして示している。
【０１３８】
これを受けた暗号化データベースサーバ２５０では、検索部６１が、第１の実施形態と同様に、検索鍵３５ａ＝検索鍵（Ｘ，Ａ，ａ［ｉ］）および被検索鍵３４ａ＝被検索鍵（Ｘ，Ａ，ａ［ｉ］）を入力として、これが暗号化表「Ｘ」４１の列「Ａ」３１ａの要素である第１の被検索鍵３４ａ＝被検索鍵（Ｘ，Ａ，ａ［ｉ］）と一致するｉを、ｉの取りうる１〜ｎの全ての値に対して検索し、判定結果＝０（一致）が出力されるｉを全て発見する。このようなｉの集合をＳと記載する。ここでｉ∈Ｓならａ［ｉ］＝ｑである。
【０１３９】
引き続いて導出部２６２が、集合Ｓの全ての要素ｉに関して、検索鍵３５ａ＝（Ｘ，Ａ，ｑ）、検索暗号文３４ｆ＝（検索鍵（Ｘ，Ａ，ａ［ｉ］），検索鍵（Ｙ，Ｃ，ｂ［ｉ］），許可鍵（（Ｘ，Ｂ）→（Ｙ，Ｃ）））、および許可鍵３５ｂ＝許可鍵（（Ｘ，Ｂ）→（Ｙ，Ｃ））から、数７に示された第３の検索鍵４４ａ＝検索鍵（Ｙ，Ｃ，ｂ［ｉ］）を生成する。
【０１４０】
そして検索部６１が、集合Ｓの全ての要素ｉに対して、第３の検索鍵４４ａ＝検索鍵（Ｙ，Ｃ，ｂ［ｉ］）と、暗号化表「Ｙ」４２の列Ｃの要素である第２の被検索鍵３４ｄ＝被検索鍵（Ｙ，Ｃ，ｃ［ｊ］）で、一致するか否かの判定結果＝０（一致する）である行番号ｊを対応づける。このようなｊをｊ［ｉ］と表記する。検索部６１は、一致すると判定した暗号化表「Ｘ」４１のｉ行目と暗号化表「Ｙ」４２のｊ行目とを結合して、新たな行Ｒ［ｉ］を作成する。検索部６１は、全てのｉ∈ＳについてＲ［ｉ］をクライアント端末１０に返送する。
【０１４１】
なお、図面の錯綜を回避するため、図７と同様に図１２でも検索部６１を２カ所に表出している。図７と同様に、これらも同一の構成要素を示している。
【０１４２】
クライアント端末１０は、暗号化／復号化部２５によって、Ｒ［ｉ］の要素であるｅｎｃ（ａ［ｉ］），ｅｎｃ（ｂ［ｉ］），ｅｎｃ（ｃ［ｉ］）を復号化して、各列要素の原文ａ［ｉ］，ｂ［ｉ］，ｃ［ｉ］を得ることができる。また、適切な検索暗号文３４ｆが予め作成されていれば、第３の検索鍵４４ａ＝検索鍵（Ｙ，Ｃ，ｂ［ｉ］）を利用して、列「Ｃ」とさらに他の列との間で結合を取ることもできる。
【０１４３】
（より詳細な実施形態の説明）
以上で説明した各手段の動作について、それらの動作をより詳細に説明する。
【０１４４】
図１３は、図９に示したクライアント端末２１０および暗号化データベースサーバ２５０が行う処理について示すフローチャートである。ステップＳ１０１〜１０４については、図８に示した第１の実施形態の場合の動作と同一である。
【０１４５】
ステップＳ１０１〜１０４の動作に続いて、許可鍵生成部２２３は、システム変数ＰＭ、秘密鍵ＭＫ、第１の表の名前ＴＮとその列の名前ＣＮ、および第２の表の名前ＴＮ’とその列の名前ＣＮ’を入力として、以下の数２０で示される許可鍵ＧＴを生成して出力する（ステップＳ３０５）。
【０１４６】
【数２０】
2013145627.tif 000022
【０１４７】
検索暗号文生成部２２４は、システム変数ＰＭ、第１の検索鍵ＳＫ、第２の検索鍵ＳＫ’、および許可鍵ＧＴを入力として、以下の数２１で示される検索暗号文ＣＰを生成して出力する（ステップＳ３０６）。
【０１４８】
【数２１】
2013145627.tif 000023
【０１４９】
暗号化／復号化部２５は、前述した（図６および図１１に示した）ように表「Ｘ」３１および表「Ｙ」３２の各要素を置換して暗号化表「Ｘ」２４１および暗号化表「Ｙ」４２を作成する（ステップＳ１０６）。そして、暗号化／復号化部２５は、これらの暗号化表「Ｘ」２４１および暗号化表「Ｙ」４２を暗号化データベースサーバ２５０に送付する。
【０１５０】
暗号化データベースサーバ２５０の側の処理も、ステップＳ１５１〜１５３について、図８に示した第１の実施形態の場合の動作と同一である。そして、クライアント端末２１０からは、ステップＳ１０７と同様に、検索鍵生成部２１が数１２で示される検索鍵ＳＫ＝第３の検索鍵３５ａを生成し、さらに許可鍵生成部２２３が新たに許可鍵を生成して、それらと部分結合コマンドとを共に暗号化データベースサーバ２５０に送信する（ステップＳ３０７）。
【０１５１】
これを受けた暗号化データベースサーバ２５０で、検索部６１はステップＳ１５２と同一の動作で第３の検索鍵ＳＫ＝検索鍵（Ｘ，Ａ，ｑ）と第１の被検索鍵ＳＫＤ＝被検索鍵（Ｘ，Ａ，ａ［ｉ］）とが一致する行番号ｉの集合Ｓを求める。そして、導出部２６２は、全てのｉ∈Ｓに対して、システム変数ＰＭ、検索鍵ＳＫ、検索暗号文ＣＰ、および許可鍵ＧＴを入力として、以下の数２２で示される対象検索鍵ＳＫ’を生成して出力する（ステップＳ３５３）。
【０１５２】
【数２２】
2013145627.tif 000024
【０１５３】
以後の動作は、ステップＳ１５４およびＳ１０８と同一である。
【０１５４】
（許可鍵ＧＴの具体的な意味）
以上で示した許可鍵ＧＴのより具体的な意味合いについて説明する。
【０１５５】
表「Ｉ」「ＩＩ」「ＩＩＩ」の３つの表があり、それらの各々に行「Ａ」「Ｂ」「Ｃ」が存在する例について考える。表「Ｉ」の行「Ａ」と表「ＩＩ」の行「Ｂ」との間で結合相手を定める検索暗号文ＣＰが存在する。そして表「ＩＩ」の行「Ｂ」と表「ＩＩＩ」の行「Ｃ」との間で結合相手を定める検索暗号文ＣＰ’が存在する。検索暗号文ＣＰは行「Ａ」から「Ｂ」への許可鍵を必要とはせず、同様に検索暗号文ＣＰ’も行「Ｂ」から「Ｃ」への許可鍵を必要とはしない。
【０１５６】
ここで表「Ｉ」の行「Ａ」の要素を検索する検索鍵ＳＫが与えられた。すると、この検索鍵ＳＫによって、この表「Ｉ」の行「Ａ」から表「ＩＩ」の行「Ｂ」への対応関係が発見され、この時にこの対応する行の検索鍵ＳＫ’が導出される。この検索鍵ＳＫ’と検索暗号文ＣＰ’を組み合わせると、今度は表「ＩＩ」の行「Ｂ」から表「ＩＩＩ」の行「Ｃ」への対応関係も発見されることになる。
【０１５７】
このように、許可鍵が設定されていない場合、データ間の対応関係が芋蔓式に発見される危険性がある。当該データの作成者もしくは管理者が、表「Ｉ」と表「ＩＩ」とは結合したいが表「ＩＩ」と表「ＩＩＩ」とは結合したくないと考えている場合には、その意図に反する結果となる。
【０１５８】
そのようなことを防止するには、検索暗号文ＣＰ’で行「Ｂ」から「Ｃ」への許可鍵を設定しておくとよい。即ち、許可鍵を利用することによって、データの結合を許可したい（もしくはしたくない）範囲を当該データの作成者もしくは管理者が適切に設定することが可能となる。
【０１５９】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１６０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１６１】
（付記１）
入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバに出力し、前記暗号化された第１の表と第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信するクライアント端末と、
前記暗号化された第１および第２の表を受信して記憶し、前記部分結合命令に応じて前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する前記暗号化データベースサーバとを備え、
前記暗号化データベースサーバが、
前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合する、
暗号化データベースシステム。
【０１６２】
（付記２）
前記クライアント端末が、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素を検索するための鍵である第１の検索鍵と、前記第１の表の前記ｂ列目の要素を検索するための鍵である第２の検索鍵とを生成する検索鍵生成手段と、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素が特定の値で検索されるための鍵である第１の被検索鍵と、前記第２の表の前記ｃ列目の要素が特定の値で検索されるための鍵である第２の被検索鍵とを生成する被検索鍵生成手段と、
前記秘密鍵を利用して、前記第１および第２の表の各要素を暗号化する暗号化手段と、
前記第１の表の前記ａ列目の要素を前記第１の被検索鍵と暗号化された前記ａ列目の要素、前記ｂ列目の要素を前記第１および第２の検索鍵から生成した検索暗号文と暗号化された前記ｂ列目の要素とでそれぞれ置換し、前記第２の表の前記ｃ列目の要素を前記第２の被検索鍵と暗号化された前記ｃ列目の要素で置換して、前記暗号化された第１および第２の表として前記暗号化データベースサーバに送信する検索暗号文生成手段と
を有し、
前記検索鍵生成手段が、前記秘密鍵を利用して前記第１の表の前記ａ列目の値がｑである要素を検索するための鍵である第３の検索鍵を生成し、前記部分結合命令と共に前記暗号化データベースサーバに送信する、
付記１に記載の暗号化データベースシステム。
【０１６３】
（付記３）
前記暗号化データベースサーバが、
前記暗号化された第１の表で前記第３の検索鍵と前記第１の被検索鍵が一致する行を抽出する検索手段と、
前記第１の検索鍵と前記検索暗号文とから対象検索鍵を生成する導出手段と
を有し、
前記検索手段が、当該生成した対象検索鍵を用いて前記暗号化された第１および第２の表の前記抽出された行について前記ｂ列目およびｃ列目が等しいか否かを判断して前記結合を行う、
付記２に記載の暗号化データベースシステム。
【０１６４】
（付記４）
前記クライアント端末が、
さらに、前記秘密鍵を利用して、前記第１の表のｂ列目と前記第２の表のｃ列目とを対応づけるための鍵である許可鍵を生成する許可鍵生成手段を有し、
前記検索暗号文生成手段が前記検索暗号文を前記第１および第２の検索鍵と前記許可鍵とから生成し、
前記暗号化データベースサーバの前記導出手段が前記第１の検索鍵と前記検索暗号文と前記許可鍵とから前記対象検索鍵を生成する、
付記３に記載の暗号化データベースシステム。
【０１６５】
（付記５）
入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して暗号化データベースサーバに出力する暗号化手段と、
前記秘密鍵を利用して検索鍵を生成する検索鍵生成手段と
を備え、
前記検索鍵生成手段が、前記秘密鍵を利用して前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記検索鍵と共に前記暗号化データベースサーバに送信する、
クライアント端末。
【０１６６】
（付記６）
前記検索鍵生成手段が、前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素を検索するための鍵である第１の検索鍵と、前記第１の表の前記ｂ列目の要素を検索するための鍵である第２の検索鍵とを生成し、
さらに、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素が特定の値で検索されるための鍵である第１の被検索鍵と、前記第２の表の前記ｃ列目の要素が特定の値で検索されるための鍵である第２の被検索鍵とを生成する被検索鍵生成手段と、
前記第１の表の前記ａ列目の要素を前記第１の被検索鍵と暗号化された前記ａ列目の要素、前記ｂ列目の要素を前記第１および第２の検索鍵から生成した検索暗号文と暗号化された前記ｂ列目の要素とでそれぞれ置換し、前記第２の表の前記ｃ列目の要素を前記第２の被検索鍵と暗号化された前記ｃ列目の要素で置換して、前記暗号化された第１および第２の表として前記暗号化データベースサーバに送信する検索暗号文生成手段と
を備える、
付記５に記載のクライアント端末。
【０１６７】
（付記７）
暗号化されたａ列目およびｂ列目のデータを有する第１の表およびｃ列目のデータを有する第２の表をクライアント端末から受信して記憶し、前記クライアント端末から受信した検索鍵を含む部分結合命令に応じて前記暗号化された第１および第２の表を前記ａ列目の値がｑであるデータについて前記ｂ列目およびｃ列目をキーとして結合して、前記クライアント端末に出力する検索手段を備え、
前記検索手段は、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合する、
暗号化データベースサーバ。
【０１６８】
（付記８）
さらに、前記検索鍵と前記暗号化された第１の表に含まれる検索暗号文とから対象検索鍵を生成する導出手段を備え、
前記検索手段が、前記検索鍵と前記暗号化された第１の表に含まれる第１の被検索鍵が一致する行を抽出し、前記対象検索鍵を用いて前記暗号化された第１および第２の表の前記抽出された行について前記ｂ列目およびｃ列目が等しいか否かを判断して前記結合を行う、
付記７に記載の暗号化データベースサーバ。
【０１６９】
（付記９）
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記クライアント端末が、入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して前記暗号化データベースサーバに出力し、
前記暗号化データベースサーバが、前記暗号化された第１および第２の表を受信して記憶し、
前記クライアント端末が、前記暗号化された第１の表の前記ａ列目の値がｑであるデータについて前記暗号化された第１および第２の表を前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信し、
前記暗号化データベースサーバが、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する、
暗号化データ結合方法。
【０１７０】
（付記１０）
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素を検索するための鍵である第１の検索鍵と、前記第１の表の前記ｂ列目の要素を検索するための鍵である第２の検索鍵とを前記クライアント端末の検索鍵生成手段が生成し、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素が特定の値で検索されるための鍵である第１の被検索鍵と、前記第２の表の前記ｃ列目の要素が特定の値で検索されるための鍵である第２の被検索鍵とを前記クライアント端末の被検索鍵生成手段が生成し、
前記秘密鍵を利用して、前記第１および第２の表の各要素を前記クライアント端末の暗号化手段が暗号化し、
前記第１の表の前記ａ列目の要素を前記第１の被検索鍵と暗号化された前記ａ列目の要素、前記ｂ列目の要素を前記第１および第２の検索鍵から生成した検索暗号文と暗号化された前記ｂ列目の要素とで前記クライアント端末の検索暗号文生成手段がそれぞれ置換して、前記暗号化された第１の表とし、
前記第２の表の前記ｃ列目の要素を前記第２の被検索鍵と暗号化された前記ｃ列目の要素で前記クライアント端末の前記検索暗号文生成手段が置換して、前記暗号化された第２の表とし、
前記暗号化された第１および第２の表を前記クライアント端末の前記検索暗号文生成手段が前記暗号化データベースサーバに送信し、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の値がｑである要素を検索するための鍵である第３の検索鍵を前記クライアント端末の前記検索鍵生成手段が生成し、
前記第３の検索鍵を前記部分結合命令と共に前記クライアント端末の前記検索鍵生成手段が前記暗号化データベースサーバに送信する、
付記９に記載の暗号化データ結合方法。
【０１７１】
（付記１１）
前記暗号化された第１の表で前記第３の検索鍵と前記第１の被検索鍵が一致する行を前記暗号化データベースサーバの検索手段が抽出し、
前記第１の検索鍵と前記検索暗号文とから前記暗号化データベースサーバの導出手段が対象検索鍵を生成し、
当該生成した対象検索鍵を用いて、前記暗号化された第１および第２の表の前記抽出された行について前記ｂ列目およびｃ列目が等しいか否かを前記暗号化データベースサーバの前記検索手段が判断して前記結合を行う、
付記１０に記載の暗号化データ結合方法。
【０１７２】
（付記１２）
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記クライアント端末が備えるコンピュータに、
入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して前記暗号化データベースサーバに出力する手順と、
前記暗号化された第１の表の前記ａ列目の値がｑであるデータについて前記暗号化された第１および第２の表を前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信する手順と、
を実行させる暗号化データ結合プログラム。
【０１７３】
（付記１３）
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素を検索するための鍵である第１の検索鍵と、前記第１の表の前記ｂ列目の要素を検索するための鍵である第２の検索鍵とを生成する手順と、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の要素が特定の値で検索されるための鍵である第１の被検索鍵と、前記第２の表の前記ｃ列目の要素が特定の値で検索されるための鍵である第２の被検索鍵とを生成する手順と、
前記秘密鍵を利用して、前記第１および第２の表の各要素を暗号化する手順と、
前記第１の表の前記ａ列目の要素を前記第１の被検索鍵と暗号化された前記ａ列目の要素、前記ｂ列目の要素を前記第１および第２の検索鍵から生成した検索暗号文と暗号化された前記ｂ列目の要素とでそれぞれ置換して、前記暗号化された第１の表とする手順と、
前記第２の表の前記ｃ列目の要素を前記第２の被検索鍵と暗号化された前記ｃ列目の要素で置換して、前記暗号化された第２の表とする手順と、
前記暗号化された第１および第２の表を前記暗号化データベースサーバに送信する手順と、
前記秘密鍵を利用して、前記第１の表の前記ａ列目の値がｑである要素を検索するための鍵である第３の検索鍵を生成する手順と、
前記第３の検索鍵を前記部分結合命令と共に前記暗号化データベースサーバに送信する手順と、
を実行させる、付記１２に記載の暗号化データ結合プログラム。
【０１７４】
（付記１４）
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記暗号化データベースサーバが備えるコンピュータに、
前記クライアント端末から暗号化されたａ列目およびｂ列目のデータを有する第１の表およびｃ列目のデータを有する第２の表を受信して記憶する手順と、
前記クライアント端末から受信した検索鍵を含む部分結合命令に応じて、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する手順と、
を実行させる暗号化データ結合プログラム。
【０１７５】
（付記１５）
前記検索鍵と前記暗号化された第１の表に含まれる第１の被検索鍵が一致する行を抽出する手順と、
前記検索鍵と前記暗号化された第１の表に含まれる検索暗号文とから対象検索鍵を生成する手順と、
当該生成した対象検索鍵を用いて、前記暗号化された第１および第２の表の前記抽出された行について前記ｂ列目およびｃ列目が等しいか否かを判断して前記結合を行う手順と、
を実行させる、付記１４に記載の暗号化データ結合プログラム。
【０１７６】
この出願は、２０１２年３月２９日に出願された日本出願特願２０１２−０７８２２２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１７７】
本発明は、暗号化データベースシステムにおいて利用可能である。特に、大量の機密データを収容する暗号化データベースシステムにおいて、顕著な効果を発揮する。
【符号の説明】
【０１７８】
１、２０１  暗号化データベースシステム
１０、２１０  クライアント端末
１１、５１  プロセッサ
１２、５２  記憶手段
１３  入力手段
１４  出力手段
１５、５３  通信手段
２０  初期設定部
２１  検索鍵生成部
２２  被検索鍵生成部
２４、２２４  検索暗号文生成部
２５  暗号化／復号化部
３３  秘密鍵
３４ａ  第１の被検索鍵
３４ｂ  第１の検索鍵
３４ｃ  第２の検索鍵
３４ｄ  第２の被検索鍵
３４ｆ  検索暗号文
３５ａ  第３の検索鍵
４４ａ  対象検索鍵
５０、２５０  暗号化データベースサーバ
６１  検索部
６２、２６２  導出部
２２３  許可鍵生成部
２３４ｅ、２３５ｂ  許可鍵
【図１】
2013145627.tif 000025
【図２】
2013145627.tif 000026
【図３】
2013145627.tif 000027
【図４】
2013145627.tif 000028
【図５】
2013145627.tif 000029
【図６】
2013145627.tif 000030
【図７】
2013145627.tif 000031
【図８】
2013145627.tif 000032
【図９】
2013145627.tif 000033
【図１０】
2013145627.tif 000034
【図１１】
2013145627.tif 000035
【図１２】
2013145627.tif 000036
【図１３】
2013145627.tif 000037
【図１４】
2013145627.tif 000038
【図１５】
2013145627.tif 000039
【図１６】
2013145627.tif 000040
【図１７】
2013145627.tif 000041
【図１８】
2013145627.tif 000042
【図１９】
2013145627.tif 000043
【図２０】
2013145627.tif 000044
【図２１】
2013145627.tif 000045
【図２２】
2013145627.tif 000046
【手続補正書】
【提出日】平成26年9月11日(2014.9.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項８
【補正方法】変更
【補正の内容】
【請求項８】
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記クライアント端末が備えるコンピュータに、
入力されたａ列目およびｂ列目のデータを有する第１の表とｃ列目のデータを有する第２の表とを予め記憶された秘密鍵によって暗号化して前記暗号化データベースサーバに出力する手順と、
前記暗号化された第１の表の前記ａ列目の値がｑであるデータについて前記暗号化された第１および第２の表を前記ｂ列目およびｃ列目をキーとして結合させる部分結合命令を前記秘密鍵から生成された検索鍵と共に前記暗号化データベースサーバに送信する手順と、
を実行させる暗号化データ結合プログラム。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
クライアント端末と、暗号化データベースサーバとを含む暗号化データベースシステムにあって、
前記暗号化データベースサーバが備えるコンピュータに、
前記クライアント端末から暗号化されたａ列目およびｂ列目のデータを有する第１の表およびｃ列目のデータを有する第２の表を受信して記憶する手順と、
前記クライアント端末から受信した検索鍵を含む部分結合命令に応じて、前記検索鍵を利用して前記暗号化された第１および第２の表から前記ａ列目の値がｑであるデータを各々抽出し、当該抽出されたデータに対して前記ｂ列目およびｃ列目をキーとして結合し、前記クライアント端末に返送する手順と、
を実行させる暗号化データ結合プログラム。
【国際調査報告】
2013145627.tif 000047
2013145627.tif 000048
2013145627.tif 000049
2013145627.tif 000050
2013145627.tif 000051
2013145627.tif 000052