(57)【要約】【課題】列データを復号化する処理を行わずに複数の表を暗号化された列に関して自然結合することを可能とする暗号化データベースシステム等を提供する。【解決手段】クライアント端末１０が、暗号鍵、表識別子と列識別子から列秘密鍵、列公開鍵、比較値を生成してそこから隠蔽比較値および暗号文を生成して特定の列を暗号化する列暗号化部２１と、暗号鍵、表識別子と列識別子から暗号化された列に関する自然結合を要求する自然結合要求文７１を発行する暗号化表自然結合要求部２２を備え、この自然結合要求文が前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成された列公開鍵および列秘密鍵を表結合鍵として含む。そして暗号化データベースサーバ５０が、この表結合鍵を利用して自然結合を実行してその結果８１を返信する。【選択図】図１
2012043012.tif 000002
【特許請求の範囲】
【請求項１】
クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、
前記クライアント端末が、
暗号鍵を予め記憶する記憶手段と、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって暗号化して外部に出力する列暗号化部と、
暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文を出力すると共に、前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力する暗号化表自然結合要求部とを備え、
前記暗号化データベースサーバが、
前記暗号化された第１および第２の表を受信して記憶するデータ受信部と、
前記暗号化された第１および第２の表に対して前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースシステム。
【請求項２】
前記クライアント端末の前記列暗号化部が、前記第１の表のａ列目に対して、
前記暗号鍵および前記第１の表の表識別子と前記ａ列目の列識別子から前記ａ列目の列秘密鍵ｘ［ａ］を生成する列秘密鍵生成機能と、
前記第１の表の表識別子と前記ａ列目の列識別子から前記ａ列目の列秘密鍵に対応するａ列目の列公開鍵ｇ［ａ］を生成する列公開鍵生成機能と、
前記第１の表のａ列目の各成分と前記暗号鍵とから比較値を生成する比較値生成機能と、
各々の前記比較値と前記暗号鍵、前記ａ列目の列秘密鍵および列公開鍵から隠蔽比較値を生成する隠蔽比較値生成機能と、
前記ａ列目のデータを前記暗号鍵によって暗号化して暗号文を生成する暗号化機能と、
前記ａ列目のデータを前記暗号文および前記隠蔽比較値に置換して前記第１の表を暗号化してこの暗号化された前記第１の表を前記暗号化データベースサーバに送信する表更新機能とを有すると共に、
前記列暗号化部が前記第２の表のｂ列目に対しても同様に列秘密鍵ｘ［ｂ］および列公開鍵ｇ［ｂ］を生成して、それらから前記比較値、前記隠蔽比較値、および暗号文を生成して前記第２の表を暗号化して前記暗号化データベースサーバに送信することを特徴とする、請求項１に記載の暗号化データベースシステム。
【請求項３】
前記クライアント端末の前記暗号化表自然結合要求部が、
前記第１の表の表識別子と前記ａ列目の列識別子、前記第２の表の表識別子と前記ｂ列目の列識別子、および前記暗号鍵から表結合鍵を生成する表結合鍵生成機能と、
前記第１の表の表識別子と前記ａ列目の列識別子、前記第２の表の表識別子と前記ｂ列目の列識別子、および前記表結合鍵から前記自然結合要求文を出力して前記暗号化データベースサーバに送信する自然結合要求文出力機能とを有することを特徴とする、請求項２に記載の暗号化データベースシステム。
【請求項４】
前記表結合鍵が前記列公開鍵ｇ［ａ］の列秘密鍵ｘ［ｂ］乗、および前記列公開鍵ｇ［ｂ］の列秘密鍵ｘ［ａ］乗を要素として含むことを特徴とする、請求項３に記載の暗号化データベースシステム。
【請求項５】
前記暗号化データベースサーバの前記暗号化表自然結合部が、
前記暗号化された第１の表のａ列目の隠蔽比較値から前記表結合鍵の前記列公開鍵ｇ［ｂ］の列秘密鍵ｘ［ａ］乗の要素を用いて第１の共通比較値を生成すると共に前記暗号化された第２の表のｂ列目の隠蔽比較値から前記表結合鍵の前記列公開鍵ｇ［ａ］の列秘密鍵ｘ［ｂ］乗の要素を用いて第２の共通比較値を生成する共通比較値生成機能と、
前記暗号化された第１の表のａ列目の隠蔽比較値を前記第１の共通比較値に置換すると共に前記暗号化された第２の表のｂ列目の隠蔽比較値を前記第２の共通比較値に置換する隠蔽比較値更新機能と、
前記置換された第１および第２の表を前記自然結合要求文に従って前記ａ列目およびｂ列目に関して自然結合を実行してその結果を前記クライアント端末に返信する自然結合機能とを有することを特徴とする、請求項４に記載の暗号化データベースシステム。
【請求項６】
暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成するクライアント端末であって、
暗号鍵を予め記憶する記憶手段と、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって暗号化して外部に出力する列暗号化部と、
暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文を出力すると共に、前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力する暗号化表自然結合要求部とを備えることを特徴とするクライアント端末。
【請求項７】
クライアント端末と相互に接続されて暗号化データベースシステムを構成する暗号化データベースサーバであって、
前記暗号化された第１および第２の表を受信して記憶するデータ受信部と、
前記暗号化された第１および第２の表に対して前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースサーバ。
【請求項８】
クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、
暗号鍵を前記クライアント端末の記憶手段に予め記憶し、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって前記クライアント端末の記憶手段が暗号化して外部に出力し、
前記暗号化された第１および第２の表を前記暗号化データベースサーバのデータ受信部が受信して記憶し、
前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を前記クライアント端末の暗号化表自然結合要求部が生成し、
暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて前記クライアント端末の暗号化表自然結合要求部が出力し、
前記暗号化された第１および第２の表に対して前記暗号化データベースサーバの暗号化表自然結合部が前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行し、
前記自然結合の結果を前記暗号化データベースサーバの前記暗号化表自然結合部が前記クライアント端末に返信することを特徴とする自然結合方法。
【請求項９】
暗号鍵を予め記憶しているクライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、
前記クライアント端末が備えるコンピュータに、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって暗号化して外部に出力する手順、
前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を生成する手順、
および暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて出力する手順
を実行させることを特徴とする自然結合プログラム。
【請求項１０】
クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、
前記暗号化データベースサーバが備えるコンピュータに、
暗号化された第１および第２の表を前記クライアント端末から受信して記憶する手順、
前記暗号化された第１および第２の表に対して前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行する手順、
および前記自然結合の結果を前記クライアント端末に返信する手順
を実行させることを特徴とする自然結合プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化データベースシステム、クライアント端末、暗号化データベースサーバ、自然結合方法およびプログラムに関し、特に、暗号化されたデータベースの複数の表を、データの各要素を完全に復号することなく、自然結合することを可能とする暗号化データベースシステム等に関する。
【背景技術】
【０００２】
企業などにおける業務の根幹がコンピュータ化されることによって、ほとんどの企業が業務で使用する大量のデータを収容する大規模データベースを持つようになっている。これらのデータは、業務上重要なデータであり、また個人情報保護の観点からも、外部に対して漏洩することは絶対にあってはならない。このため、そのような大規模データベースでは、収容されるデータが暗号化されていることが多い。【０００３】
データベースは多くの表（テーブル）の集合体として捉えることができる。ここでいう「自然結合」とは、２つの表で同一のデータを示す列がある場合に、それらの列を統一することによって、これら２つの表を１つに結合することをいう。以下、非特許文献１などに記載されている、収容されているデータが暗号化されたデータベース（以後暗号化データベースという）で２つの表を自然結合するために行われている一般的な手法について説明する。【０００４】
図１１は、暗号化データベースについての一般的な技術に係る暗号化データベースシステム９０１の構成について示す説明図である。暗号化データベースシステム９０１は、クライアント端末９１０と暗号化データベースサーバ９５０とが、ＬＡＮ（Local Area Network）などを介して相互に接続されて構成される。【０００５】
クライアント端末９１０は、一般的なコンピュータ装置としての構成を備える。即ち、クライアント端末９１０は、コンピュータプログラムを実行する主体となる主演算制御手段（ＣＰＵ: Central Processing Unit）９１１と、データを記憶する記憶手段９１２と、ユーザからの操作を受け付ける入力手段９１３と、ユーザに処理結果を提示する出力手段９１４と、他のコンピュータとのデータ通信を行う通信手段９１５とを備える。【０００６】
主演算制御手段９１１では、ユーザからの操作命令に応じて、列暗号化部９２１、および暗号化表自然結合要求部９２２が、各々コンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。また、記憶手段９１２には以後に説明する処理で使用する各々別個の秘密鍵ｋｅｙ９３１ａ、秘密鍵ｋｅｙ’９３１ｂが記憶されている。そして入力手段９１３には、暗号化および自然結合の対象となる表Ａ９３２および表Ｂ９３３が入力される。【０００７】
暗号化データベースサーバ９５０もまた、一般的なコンピュータ装置としての構成を備える。即ち、暗号化データベースサーバ９５０は、コンピュータプログラムを実行する主体となる主演算制御手段９５１と、データを記憶する記憶手段９５２と、他のコンピュータとのデータ通信を行う通信手段９５３とを備える。【０００８】
主演算制御手段９５１では、クライアント端末９１０からの操作命令に応じて、暗号化表自然結合部９６３と、データ受信部９６４とがコンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。【０００９】
また、記憶手段９５２にはデータ受信部９６４がクライアント端末９１０から受信した、各々表Ａ９３３および表Ｂ９３４を暗号化した暗号化表Ａ９４１および暗号化表Ｂ９４２、およびクライアント端末９１０の秘密鍵ｋｅｙ９３１ａおよび秘密鍵ｋｅｙ’９３１ｂに各々対応する公開鍵ｐｋｅｙ９７２ａおよび公開鍵ｐｋｅｙ’９７２ｂが記憶される。【００１０】
図１２は、図１１に示した列暗号化部９２１の機能についてより詳しく説明する説明図である。列暗号化部９２１は、暗号化機能９２１ａと表更新機能９２１ｂとを備える。暗号化機能９２１ａは、表Ａ９３２の特定の列（この列を列ａという）を、秘密鍵ｋｅｙ９３１ａを利用して暗号化して暗号文９４３を出力する。表更新機能９２１ｂは、この暗号文９４３で列ａの各データを置き換えたものを暗号化表Ａ９４１として出力して暗号化データベースサーバ９５０に送信する。暗号化データベースサーバ９５０では、データ受信部９６４がこれらを記憶手段９５２に記憶する。【００１１】
列暗号化部９２１は同様に、秘密鍵ｋｅｙ’９３１ｂを利用して、表Ｂ９３３の特定の列（この列を列ｂという）を暗号文で置き換えた暗号化表Ｂ９４２も出力して記憶手段９１２に記憶する。なお、暗号化表Ａ９４１の表識別子９３２ａ＝「Ａ」、列ａの列識別子９３２ｃ＝「ａ」、暗号化表Ｂ９４２の表識別子９３３ａ＝「Ｂ」、および列ｂの列識別子９３３ｃ＝「ｂ」は、各々暗号化の対象ではないので、暗号化表Ａ９４１および暗号化表Ｂ９４２に付随して記憶手段９５２に記憶されると同時に、クライアント端末９１０の記憶手段９１２にも記憶される。【００１２】
図１３は、図１１に示した暗号化表自然結合要求部９２２の機能についてより詳しく説明する説明図である。暗号化表自然結合要求部９２２は、暗号化表Ａ９４１の表識別子９３２ａ＝「Ａ」、列ａの列識別子９３２ｃ＝「ａ」、暗号化表Ｂ９４２の表識別子９３３ａ＝「Ｂ」、および列ｂの列識別子９３３ｃ＝「ｂ」から、列ａと列ｂに関して暗号化表Ａ９４１および暗号化表Ｂ９４２を自然結合することを命令する自然結合要求文９７１を発行して暗号化データベースサーバ９５０に送信する。暗号化データベースサーバ９５０では、これを受けたデータ受信部９６４が暗号化表自然結合部９６３を自然結合要求文９７１に従って動作させる。【００１３】
図１４は、図１１に示した暗号化表自然結合部９６３の機能についてより詳しく説明する説明図である。暗号化表自然結合部９６３は、復号化機能９６３ａ、自然結合機能９６３ｂ、および再暗号化機能９６３ｃを備える。復号化機能９６３ａは、暗号化表Ａ９４１および暗号化表Ｂ９４２で暗号化された列ａおよび列ｂのデータを、秘密鍵ｋｅｙ９３１ａおよび秘密鍵ｋｅｙ’９３１ｂに各々対応する公開鍵ｐｋｅｙ９７２ａおよび公開鍵ｐｋｅｙ’９７２ｂを利用して復号化して、暗号化される前の表Ａ９３２および表Ｂ９３３に戻す。【００１４】
自然結合機能９６３ｂは、自然結合要求文９７１で命令された通りに、表Ａ９３２の列ａと表Ｂ９３３の列ｂとに関して表Ａ９３２および表Ｂ９３３を自然結合する。再暗号化機能９６３ｃは、結合された表Ａ９３２および表Ｂ９３３のキーとなった列ａ（列ｂ）を再暗号化して、得られた暗号化表Ａ×Ｂ９８１をクライアント端末９１０に返送する。再暗号化には、ここでは公開鍵ｐｋｅｙ９７２ａを利用しているが、もちろん他の暗号鍵でもよい。【００１５】
図１５は、図１１に示した暗号化データベース管理装置９１０で、暗号化される前の表Ａ９３２の一例を示す説明図である。図１５で示されている例では、表９３２の第１列を「ユーザ名」、第２列を「クレジットカード番号」として、各ユーザ名に対応するカード番号の対応関係を示している。【００１６】
暗号化データベース管理装置９１０は、秘匿すべきデータに対して秘密鍵ｋｅｙを利用し、ハッシュ関数などのような暗号化関数ｅｎｃによって対象データを暗号化する。図１６は、図１１に示した列暗号化部９２１が、図１５に示した表Ａ９３２を暗号化した状態の暗号化表Ａ９４１を示す説明図である。ここでは、第２列「クレジットカード番号」を秘匿すべき対象とし、平文ｍを暗号鍵で暗号化したデータをｅｎｃ（ｋｅｙ、ｍ）と表している。【００１７】
秘密鍵ｋｅｙは各々の表に対して固有に与えられる。暗号化は確定的なものであるので、平文ｍと秘密鍵ｋｅｙが決定されれば、ｅｎｃ（ｋｅｙ、ｍ）の値も一意に決定される。ただし、暗号化関数ｅｎｃはハッシュ関数などのような不可逆関数である方が望ましい。【００１８】
このようにすれば、図１５に示した暗号化表Ａ９４１が外部に漏洩したとしても、秘密鍵ｋｅｙが漏洩しなければ、クレジットカード番号が漏洩することはない。また、秘密鍵ｋｅｙを持つ正当なユーザであれば、クレジットカード番号によってこの表を検索することができる。たとえば、クレジットカード番号「１２３３４」を持つユーザを検索する場合には、ｅｎｃ（ｋｅｙ、１２３３４）で検索すればよい。【００１９】
これに関連する技術文献として、次の各々がある。特許文献１には、暗号化データの送受信で、ユーザが復号鍵を紛失してもその復号鍵を回復できる鍵回復情報を持った暗号化情報を送受信できる暗号化復号化装置について記載されている。特許文献２には、２つのテーブルを結合したテーブルを高速に検索することを可能とするという自然結合高速演算方法について記載されている。【００２０】
特許文献３には、データベースの等結合にかかる計算コストを下げることが可能であるという結合サイズ評価方法について記載されている。特許文献４には、ユーザが正しいＳＱＬ（Structured Query Language）文を生成できるようユーザをガイドするというデータベース問い合わせシステムについて記載されている。【００２１】
非特許文献１には、前述した暗号化データベースについての既存の技術が記載されている。非特許文献２には、表の自然結合を含めたデータベースについての一般的な内容について記載されている。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開２０００−２６７５６５号公報
【特許文献２】特開平０２−１３２５５９号公報
【特許文献３】特開平１０−１２４５３３号公報
【特許文献４】特表平０９−５１０５６５号公報
【非特許文献】
【００２３】
【非特許文献１】Paul Needham他、「Oracle Advanced Securityテクニカル・ホワイト・ペーパー」、日本オラクル株式会社、２００７年６月、［平成２２年９月３日検索］、インターネット＜URL：http://otndnld.oracle.co.jp/products/database/oracle11g/pdf/twp_security_db_advancedsecurity_11gR1.pdf＞
【非特許文献２】北川博之、「データベースシステム」、昭晃堂、１９９６年７月
【発明の概要】
【発明が解決しようとする課題】
【００２４】
データベースは、大量のデータの中から単に必要なデータを抽出するだけではなく、ＳＱＬコマンドなどによって複数の表を結合することが頻繁に行われる。暗号化されたデータに対しても、この表を自然結合する演算を、セキュリティを損なうことなく容易に行えることが当然望まれる。【００２５】
しかしながら、前述のように暗号鍵ｋｅｙは各々の表に対して固有に与えられるものであるので、異なる表には異なる暗号鍵が与えられることになる。従って、異なる表にある同一のデータは、異なる暗号鍵によって暗号化されると異なるデータとなる。このため、図１１で示した暗号化データベース管理装置９０１で、列暗号化部９２１によって暗号化されたデータに関して異なる表を結合する演算を行うためには、前述したように該データを一度復号化してから結合する必要がある。【００２６】
このことをより具体的に説明する。図１７は、図１１で示した暗号化データベース管理装置９０１で、複数の暗号化表Ａ９４１および暗号化表Ｂ９４２に対して自然結合の演算を行う場合の例についての説明図である。暗号化表Ａ９４１は、第１列を「ユーザ名」、第２列を「クレジットカード番号」として、各ユーザ名に対応するカード番号の対応関係を示す。そして第２列「クレジットカード番号」は、秘密鍵ｋｅｙ９３１ａによって暗号化されている。暗号化表Ｂ９４２は、第１列を「クレジットカード番号」、第２列を「クレジットカード有効期限」として、各カードの有効期限について示している。そして第１列「クレジットカード番号」は、秘密鍵ｋｅｙ’９３１ｂによって暗号化されている。【００２７】
ここで、該データベースの管理者が「ユーザ名」と「クレジットカード有効期限」との対応について知りたい場合には、暗号化表自然結合要求部９２２によって、暗号化表Ａ９４１および暗号化表Ｂ９４２を列「クレジットカード番号」に関して自然結合するよう自然結合命令文９７１を発行する。この処理によって、第１列「ユーザ名」、第２列「クレジットカード番号」、第３列「クレジットカード有効期限」という３列を持つ暗号化表Ａ×Ｂ９８１が得られることが期待される。【００２８】
しかしながら、暗号化表Ａ９４１および暗号化表Ｂ９４２は、各々異なる暗号鍵によって暗号化されているので、平文の段階では同一のデータであっても、異なる暗号鍵によって異なるデータとなる。従って、暗号化表自然結合部９６３は、暗号化されたデータをそのまま自然結合のキーとすることはできない。この処理を行うためには、図１４に示した復号化機能９６３ａによって列「クレジットカード番号」を復号化する処理が必要となる。【００２９】
この処理には、暗号化表Ａ９４１および暗号化表Ｂ９４２に対する秘密鍵ｋｅｙ９３１ａおよび秘密鍵ｋｅｙ’９３１ｂに各々対応する公開鍵ｐｋｅｙ９７２ａおよび公開鍵ｐｋｅｙ’９７２ｂが必要である。これらの公開鍵を利用すれば、この処理を行うために列列「クレジットカード番号」を復号化することは可能ではある。しかしながら、この処理を行っている間は復号化された平文のデータが装置に記憶されることになるので、その間にその平文のデータが漏洩する危険性を否定することはできない。【００３０】
図１８は、上述の問題を解決するため、ｋｅｙ＝ｋｅｙ’、即ち同一の暗号鍵ｋｅｙを利用して暗号化された暗号化表Ｃ１００１および暗号化表Ｄ１００２に対して自然結合の演算を行う例についての説明図である。この暗号鍵ｋｅｙは、公開鍵方式のものであっても、共通鍵方式のものであってもよい。【００３１】
暗号化表Ｃ１００１は、第１列を「ユーザ名」、第２列を「クレジットカード番号」として、各ユーザ名に対応するカード番号の対応関係を示す。そして第２列「クレジットカード番号」は、暗号鍵ｋｅｙによって暗号化されている。暗号化表Ｄ１００２は、第１列を「クレジットカード番号」、第２列を「ブラックリスト登録日」として、各カードの有効期限について示している。そして第１列「クレジットカード番号」は、表Ｃ１００１と同一の暗号鍵ｋｅｙによって暗号化されている。【００３２】
暗号鍵ｋｅｙが同一であれば、暗号化表Ｃ１００１の第２列「クレジットカード番号」と暗号化表Ｄ１００２の第１列「クレジットカード番号」とで、暗号化前のデータが同一であれば、暗号化された後も同一データとなるので、復号化機能９６３ａを利用しなくて暗号化表Ｃ１００１および暗号化表Ｄ１００２をそのまま自然結合して暗号化表Ｃ×Ｄ１００３を得ることが可能である。しかしながら、このことは同時に、暗号鍵ｋｅｙを持たない不当なユーザであっても、暗号化されたデータに関して暗号化表Ｃ１００１および暗号化表Ｄ１００２を自然結合して暗号化表Ｃ×Ｄ１００３を得る処理ができてしまうことを意味する。このようなことは、暗号化データベースの管理において、望ましいことではない。【００３３】
即ち、正当な暗号鍵を持つユーザであれば、暗号化されたデータを復号化する処理を行わなくとも、暗号化されたデータに関して複数の表を自然結合することが可能で、かつ正当な暗号鍵を持たない不当なユーザには暗号化されたデータに関する自然結合ができない、そのような特徴を持つ暗号化データベース管理装置が求められている。かつ、データベースは膨大な量のデータを扱うものであるので、この処理を行うことによる計算量の大幅な増大も抑制されなければならない。【００３４】
前述の各特許文献および非特許文献は、いずれもこの問題を解決することを目的とはしておらず、当然ながらこの問題を解決しうる技術は記載されていない。【００３５】
本発明の目的は、暗号化されたデータベースの複数の表を、データの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータに関して自然結合することを可能とする暗号化データベースシステム、クライアント端末、暗号化データベースサーバ、自然結合方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００３６】
上記目的を達成するため、本発明に係る暗号化データベースシステムは、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、クライアント端末が、暗号鍵を予め記憶する記憶手段と、入力された第１の表のａ列目のデータと第２の表のｂ列目のデータとを暗号鍵によって暗号化して外部に出力する列暗号化部と、暗号化された第１の表および第２の表をａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文を出力すると共に、第１および第２の表の表識別子とａ列目およびｂ列目の列識別子とから暗号鍵によって生成された列公開鍵および列秘密鍵を含む表結合鍵を生成して自然結合要求文に含めて出力する暗号化表自然結合要求部とを備え、暗号化データベースサーバが、暗号化された第１および第２の表を受信して記憶するデータ受信部と、暗号化された第１および第２の表に対して自然結合要求文に従って表結合鍵を適用して自然結合を実行する暗号化表自然結合部とを備えることを特徴とする。【００３７】
上記目的を達成するため、本発明に係るクライアント端末は、暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成するクライアント端末であって、暗号鍵を予め記憶する記憶手段と、入力された第１の表のａ列目のデータと第２の表のｂ列目のデータとを暗号鍵によって暗号化して外部に出力する列暗号化部と、暗号化された第１の表および第２の表をａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文を出力すると共に、第１および第２の表の表識別子とａ列目およびｂ列目の列識別子とから暗号鍵によって生成された列公開鍵および列秘密鍵を含む表結合鍵を生成して自然結合要求文に含めて出力する暗号化表自然結合要求部とを備えることを特徴とする。【００３８】
上記目的を達成するため、本発明に係る暗号化データベースサーバは、クライアント端末と相互に接続されて暗号化データベースシステムを構成する暗号化データベースサーバであって、暗号化された第１および第２の表を受信して記憶するデータ受信部と、暗号化された第１および第２の表に対して自然結合要求文に従って表結合鍵を適用して自然結合を実行する暗号化表自然結合部とを備えることを特徴とする。【００３９】
上記目的を達成するため、本発明に係る自然結合方法は、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号鍵をクライアント端末の記憶手段に予め記憶し、入力された第１の表のａ列目のデータと第２の表のｂ列目のデータとを暗号鍵によってクライアント端末の記憶手段が暗号化して外部に出力し、暗号化された第１および第２の表を暗号化データベースサーバのデータ受信部が受信して記憶し、第１および第２の表の表識別子とａ列目およびｂ列目の列識別子とから暗号鍵によって生成された列公開鍵および列秘密鍵を含む表結合鍵をクライアント端末の暗号化表自然結合要求部が生成し、暗号化された第１の表および第２の表をａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文に表結合鍵を含めてクライアント端末の暗号化表自然結合要求部が出力し、暗号化された第１および第２の表に対して暗号化データベースサーバの暗号化表自然結合部が自然結合要求文に従って表結合鍵を適用して自然結合を実行し、自然結合の結果を暗号化データベースサーバの暗号化表自然結合部がクライアント端末に返信することを特徴とする。【００４０】
上記目的を達成するため、本発明に係る自然結合プログラムは、暗号鍵を予め記憶しているクライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、クライアント端末が備えるコンピュータに、入力された第１の表のａ列目のデータと第２の表のｂ列目のデータとを暗号鍵によって暗号化して外部に出力する手順、第１および第２の表の表識別子とａ列目およびｂ列目の列識別子とから暗号鍵によって生成された列公開鍵および列秘密鍵を含む表結合鍵を生成する手順、および暗号化された第１の表および第２の表をａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文に表結合鍵を含めて出力する手順を実行させることを特徴とする。【００４１】
上記目的を達成するため、本発明に係る他の自然結合プログラムは、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号化データベースサーバが備えるコンピュータに、暗号化された第１および第２の表をクライアント端末から受信して記憶する手順、暗号化された第１および第２の表に対して自然結合要求文に従って表結合鍵を適用して自然結合を実行する手順、および自然結合の結果をクライアント端末に返信する手順を実行させることを特徴とする。
【発明の効果】
【００４２】
本発明は、上述したようにクライアント端末の側で暗号鍵から表結合鍵を生成してこれを含む自然結合要求文を暗号化データベースサーバに送信するように構成したので、この表結合鍵を受信した暗号化データベースサーバのみが、第１の表および第２の表において指定された列のデータが等しいか否かを判断可能となる。【００４３】
これによって、暗号化されたデータベースの複数の表を、データの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータに関して自然結合することが可能であるという優れた特徴を持つ暗号化データベースシステム、クライアント端末、暗号化データベースサーバ、自然結合方法およびプログラムを提供することができる。
【図面の簡単な説明】
【００４４】
【図１】本発明に係る暗号化データベースシステムの構成を示す説明図である。
【図２】図１に示した表Ａおよび表Ｂについて詳しく説明する説明図である。
【図３】図１に示したクライアント端末の、列暗号化装置としてのより詳しい構成を示す説明図である。
【図４】図３に示した列暗号化部の処理について示すフローチャートである。
【図５】図４に示した処理によって出力された暗号化表Ａについて示す説明図である。
【図６】図４のステップＳ１１１で送信された暗号化表Ａを受信した暗号化データベースサーバの側での、図１に示したデータ受信部の動作について示すフローチャートである。
【図７】図１に示したクライアント端末の、暗号化表自然結合要求装置としてのより詳しい構成を示す説明図である。
【図８】図７に示した暗号化表自然結合要求部の処理について示すフローチャートである。
【図９】図１に示した暗号化データベースサーバの、暗号化表自然結合装置としてのより詳しい構成を示す説明図である。
【図１０】図９に示した暗号化表自然結合部の処理について示すフローチャートである。
【図１１】暗号化データベースについての一般的な技術に係る暗号化データベースシステムの構成について示す説明図である。
【図１２】図１１に示した列暗号化部の機能についてより詳しく説明する説明図である。
【図１３】図１１に示した暗号化表自然結合要求部の機能についてより詳しく説明する説明図である。
【図１４】図１１に示した暗号化表自然結合部の機能についてより詳しく説明する説明図である。
【図１５】図１１に示した暗号化データベース管理装置で、暗号化される前の表Ａの一例を示す説明図である。
【図１６】図１１に示した列暗号化部が、図１５に示した表Ａを暗号化した状態の暗号化表Ａを示す説明図である。
【図１７】図１１で示した暗号化データベース管理装置で、複数の暗号化表Ａおよび暗号化表Ｂに対して自然結合の演算を行う場合の例についての説明図である。
【図１８】上述の問題を解決するため、ｋｅｙ＝ｋｅｙ’、即ち同一の暗号鍵ｋｅｙを利用して暗号化された暗号化表Ｃおよび暗号化表Ｄに対して自然結合の演算を行う例についての説明図である。
【発明を実施するための形態】
【００４５】
（第１の実施形態）
以下、本発明の第１の実施形態の構成について添付図１、３、７、９に基づいて説明する。
最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。
本実施形態に係る暗号化データベースシステム１は、クライアント端末１０と暗号化データベースサーバ５０とが相互に接続されて構成される。クライアント端末１０は、暗号鍵（秘密鍵３１）を予め記憶する記憶手段１２と、入力された第１の表のａ列目のデータと第２の表のｂ列目のデータとを暗号鍵によって暗号化して外部に出力する列暗号化部２１と、暗号化された第１の表および第２の表をａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文７１を出力する暗号化表自然結合要求部２２とを備える。そして、この暗号化表自然結合要求部２２は、第１および第２の表の表識別子とａ列目およびｂ列目の列識別子とから暗号鍵によって生成された列公開鍵および列秘密鍵を含む表結合鍵を生成して自然結合要求文７１に含めて出力する。一方の暗号化データベースサーバ５０は、暗号化された第１および第２の表を受信して記憶するデータ受信部６４と、暗号化された第１および第２の表に対して自然結合要求文に従って表結合鍵を適用して自然結合を実行する暗号化表自然結合部６３とを備える。
【００４６】
ここでクライアント端末の列暗号化部２１は、第１の表のａ列目に対して、暗号鍵（秘密鍵３１）および第１の表（表Ａ３３）の表識別子３３ａとａ列目の列識別子３３ｃからａ列目の列秘密鍵ｘ［ａ］を生成する列秘密鍵生成機能２１ａと、第１の表の表識別子とａ列目の列識別子からａ列目の列秘密鍵に対応するａ列目の列公開鍵ｇ［ａ］を生成する列公開鍵生成機能２１ｂと、第１の表のａ列目の各成分と暗号鍵とから比較値を生成する比較値生成機能２１ｃと、各々の比較値と暗号鍵、ａ列目の列秘密鍵および列公開鍵から隠蔽比較値を生成する隠蔽比較値生成機能２１ｄと、ａ列目のデータを暗号鍵によって暗号化して暗号文を生成する暗号化機能２１ｅと、ａ列目のデータを暗号文および隠蔽比較値に置換して第１の表を暗号化してこの暗号化された第１の表を暗号化データベースサーバに送信する表更新機能２１ｆとを有する。そして列暗号化部２１は、第２の表（表Ｂ３４）のｂ列目に対しても同様に列秘密鍵ｘ［ｂ］および列公開鍵ｇ［ｂ］を生成して、それらから比較値、隠蔽比較値、および暗号文を生成して第２の表を暗号化して暗号化データベースサーバに送信する処理を行う。さらに、列暗号化部２１は、ａ列目の各成分に対応する乱数を生成する乱数生成機能２１ｇを備え、隠蔽比較値生成機能２１ｄは、各々の比較値と暗号鍵、ａ列目の列秘密鍵および列公開鍵、および乱数から隠蔽比較値を生成する。
【００４７】
また、クライアント端末の暗号化表自然結合要求部２２は、第１の表の表識別子とａ列目の列識別子、第２の表の表識別子３４ａとｂ列目の列識別子３４ｃ、および暗号鍵から表結合鍵を生成する表結合鍵生成機能２２ｃと、第１の表の表識別子とａ列目の列識別子、第２の表の表識別子とｂ列目の列識別子、および表結合鍵から自然結合要求文７１を出力して暗号化データベースサーバに送信する自然結合要求文出力機能２２ｄとを有する。そして、表結合鍵は、列公開鍵ｇ［ａ］の列秘密鍵ｘ［ｂ］乗、および列公開鍵ｇ［ｂ］の列秘密鍵ｘ［ａ］乗を要素として含む。さらに、暗号化表自然結合要求部２２が、列暗号化部と同一の列秘密鍵生成機能２２ａおよび列公開鍵生成機能２２ｂを含む。
【００４８】
そして、暗号化データベースサーバの暗号化表自然結合部６３は、暗号化された第１の表のａ列目の隠蔽比較値から表結合鍵の列公開鍵ｇ［ｂ］の列秘密鍵ｘ［ａ］乗の要素を用いて第１の共通比較値を生成すると共に暗号化された第２の表のｂ列目の隠蔽比較値から表結合鍵の列公開鍵ｇ［ａ］の列秘密鍵ｘ［ｂ］乗の要素を用いて第２の共通比較値を生成する共通比較値生成機能６３ａと、暗号化された第１の表のａ列目の隠蔽比較値を第１の共通比較値に置換すると共に暗号化された第２の表のｂ列目の隠蔽比較値を第２の共通比較値に置換する隠蔽比較値更新機能６３ｂと、置換された第１および第２の表を自然結合要求文に従ってａ列目およびｂ列目に関して自然結合を実行してその結果をクライアント端末に返信する自然結合機能６３ｃとを有する。
【００４９】
以上の構成を備えることにより、暗号化データベースシステム１はデータの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータに関して自然結合することが可能となる。
以下、これをより詳細に説明する。
【００５０】
（記号および用語、そしてそれらの定義について）
まず、本明細書で使用する記号および用語、そしてそれらの定義について説明する。本明細書の数式以外の行では「Ａに上付き添字Ｂ（ＡのＢ乗など）」を「Ａ＾Ｂ」、「Ａに下付き添字Ｂ」を「Ａ＿Ｂ」と表すことにする。
【００５１】
ｐは素数である。Ｇ、Ｇ＿Ｔは各々、位数がｐの巡回群である。ｐａｉｒは、ＧとＧからＧ＿Ｔへの双線形写像である。Ｈａｓｈは、任意長の文字列からＺ／ｐＺへの写像であり、たとえばハッシュ関数などである。ｅｎｃは、鍵と平文を入力として暗号文を出力とする暗号化関数である。
【００５２】
データベースの各表は、自らを一意的に識別する識別子を持つ。データベースの各表の各列は、その属する表の中で自らを一意的に識別する識別子を持つ。データベースの各表の各列を取り出したものを列ベクトルという。データベースの表Ａと表Ｂとを、「表Ａの列ａの要素と表Ｂの列ｂの要素が等しい」という条件によって等結合することを、「表Ａと表Ｂを表Ａの列ａと表Ｂの列ｂに関して自然結合する」という。ただし、この等結合を行う際、重複する列は削除する。
【００５３】
図１は、本発明に係る暗号化データベースシステム１の構成を示す説明図である。暗号化データベースシステム１は、クライアント端末１０と暗号化データベースサーバ５０とが、ＬＡＮ（Local Area Network）などを介して相互に接続されて構成される。
【００５４】
クライアント端末１０は、一般的なコンピュータ装置としての構成を備える。即ち、クライアント端末１０は、コンピュータプログラムを実行する主体となる主演算制御手段（ＣＰＵ: Central Processing Unit）１１と、データを記憶する記憶手段１２と、ユーザからの操作を受け付ける入力手段１３と、ユーザに処理結果を提示する出力手段１４と、他のコンピュータとのデータ通信を行う通信手段１５とを備える。
【００５５】
主演算制御手段１１では、ユーザからの操作命令に応じて、列暗号化部２１、および暗号化表自然結合要求部２２が、各々コンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。また、記憶手段１２には以後に説明する処理で使用する秘密鍵（ｋｅｙ）３１が記憶されている。そして入力手段１３には、表Ａ３３および表Ｂ３４が入力される。
【００５６】
暗号化データベースサーバ５０もまた、一般的なコンピュータ装置としての構成を備える。即ち、暗号化データベースサーバ５０は、コンピュータプログラムを実行する主体となる主演算制御手段（ＣＰＵ: Central Processing Unit）５１と、データを記憶する記憶手段５２と、他のコンピュータとのデータ通信を行う通信手段５３とを備える。
【００５７】
主演算制御手段５１では、クライアント端末１０からの操作命令に応じて、暗号化表自然結合部６３と、データ受信部６４とがコンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。また、記憶手段５２にはデータ受信部６４がクライアント端末１０から受信した、各々表Ａ３３および表Ｂ３４を暗号化した暗号化表Ａ４１および暗号化表Ｂ４２が記憶される。
【００５８】
ここで、クライアント端末１０で使用される暗号鍵としては、暗号化と復号化で共通の鍵を使用する共通鍵を使用することもできるが、セキュリティ上の観点からして公開鍵暗号方式の秘密鍵を使用することがより望ましいので、本実施形態では秘密鍵（ｋｅｙ）３１を使用する。この秘密鍵（ｋｅｙ）３１は、クライアント端末１０から他の装置に向けて送信されることはない。また、秘密鍵（ｋｅｙ）３１に対応する公開鍵は、本実施形態では使用されない。
【００５９】
なお、物理的なコンピュータ装置の区分については、この例の通りに従う必要は特にない。たとえば、列暗号化部２１および暗号化表自然結合要求部２２を、各々異なるコンピュータで動作させてもよい。また、列暗号化部２１、暗号化表自然結合要求部２２、および暗号化表自然結合部６３を全て同一のコンピュータで動作させてもよい。
【００６０】
図２は、図１に示した表Ａ３３および表Ｂ３４について詳しく説明する説明図である。各々の表は、表全体に対して与えられた表識別子と、特定の列の列データとその列に対して与えられた列識別子とを有する。
【００６１】
ここでは、表Ａ３３の表識別子３３ａ＝「Ａ」とし、表Ａ３３で暗号化の対象かつ自然結合のキーとなるａ列目の列データ３３ｂ＝ｍ［ａ、ｉ］（表Ａ３３の行数をＮ、ｉは１≦ｉ≦Ｎの自然数）、ａ列目の列識別子３３ｃ＝「ａ」とする。以後、この列を単に「列ａ」という。また、表Ｂ３４の表識別子３４ａ＝「Ａ」とし、表Ｂ３４で暗号化の対象かつ自然結合のキーとなるｂ列目の列データ３４ｂ＝ｍ［ｂ、ｊ］（表Ｂ３４の行数をＭ、ｊは１≦ｊ≦Ｍの自然数）、ｂ列目の列識別子３４ｃ＝「ｂ」とする。以後、この列を単に「列ｂ」という。
【００６２】
（列暗号化部）
図３は、図１に示したクライアント端末１０の、列暗号化装置としてのより詳しい構成を示す説明図である。クライアント端末１０は、主演算制御手段１１で列暗号化部２１が動作することによって、表Ａの列ａを暗号化する列暗号化装置として機能する。列暗号化部２１は、列秘密鍵生成機能２１ａ、列公開鍵生成機能２１ｂ、比較値生成機能２１ｃ、隠蔽比較値生成機能２１ｄ、暗号化機能２１ｅ、表更新機能２１ｆ、乱数生成機能２１ｇとを備える。これら各機能の詳細については後述する。
【００６３】
列暗号化部２１への入力データとして、記憶手段１２には秘密鍵（ｋｅｙ）３１が記憶され、図２に示した表Ａ３３は入力手段１３から入力される。ただし、図３では表Ａ３３に対する処理だけを説明するので、表Ｂ３４およびこれに関連する要素については図示しない。
【００６４】
図４は、図３に示した列暗号化部２１の処理について示すフローチャートである。列秘密鍵生成機能２１ａは、秘密鍵（ｋｅｙ）３１、表識別子３３ａ＝「Ａ」、列識別子３３ｃ＝「ａ」から、以下に示す数１によって列秘密鍵４３ａ＝ｘ［ａ］を算出する（ステップＳ１０１）。
【数１】
2012043012.tif 000003
【００６５】
列公開鍵生成機能２１ｂは、列秘密鍵４３ａ＝ｘ［ａ］に対応する列公開鍵４３ｂ＝ｇ［ａ］を、以下に示す数２によって算出する（ステップＳ１０２）。
【数２】
2012043012.tif 000004
【００６６】
ここで、数１および数２の右辺のハッシュ関数の第１の変数「"secret"」および「"public"」は単なる文字列であり、クライアント端末１０の装置内部でハッシュ関数の用途を区別するためのものである。従って、装置内部で用途を区別できさえすれば、どのような文字列であってもよい。これ以降のハッシュ関数についても同様である。
【００６７】
ｉ＝１を初期値として定義し（ステップＳ１０３）、比較値生成機能２１ｃは、列ａ３３ｂのｉ番目の成分ｍ［ａ、ｉ］に関する比較値４３ｃ＝ｆ［ａ、ｉ］を、以下に示す数３によって算出する（ステップＳ１０４）。
【数３】
2012043012.tif 000005
【００６８】
乱数生成機能２１ｇは、Ｚ／ｑＺからランダムに選んだ乱数４３ｅ＝ｒ［ａ、ｉ］を生成する（ステップＳ１０５）。隠蔽比較値生成機能２１ｄは、この乱数４３ｅ＝ｒ［ａ、ｉ］および比較値４３ｃ＝ｆ［ａ、ｉ］を利用して、隠蔽比較値４３ｄ＝ｄ［ａ、ｉ］を、以下に示す数４によって算出する（ステップＳ１０６）。
【数４】
2012043012.tif 000006
【００６９】
暗号化機能２１ｅは、列ａ３３ｂのｉ番目の成分ｍ［ａ、ｉ］および秘密鍵（ｋｅｙ）３１を利用して、暗号文４３ｆ＝ｅ［ａ、ｉ］を以下に示す数５によって算出する。ここで、ｒ’［ａ、ｉ］はランダムに選択された乱数である（ステップＳ１０７）。
【数５】
2012043012.tif 000007
【００７０】
表更新機能２１ｆは、この暗号文４３ｆ＝ｅ［ａ、ｉ］と隠蔽比較値４３ｄ＝ｄ［ａ、ｉ］とを利用して、列ベクトル（ｅ［ａ、ｉ］、ｄ［ａ、ｉ］）の第ｉ成分を生成する（ステップＳ１０８、以後この列ベクトルを暗号化列ベクトル４１ｂという）。以後、ｉを１ずつ増加させ、ｉ＝ＮとなるまでステップＳ１０３〜１０８の処理を繰り返す（ステップＳ１０９〜１１０）。
【００７１】
表更新機能２１ｆは最後に、ｉ＝Ｎとなって、行ａを暗号化列ベクトル４１ｂで置換した表Ａ３３を、暗号化表Ａ４１として出力し、通信手段１５を介して暗号化データベースサーバ５０に送信する（ステップＳ１１１）。これと同時に、表更新機能２１ｆは表識別子３３ａ＝「Ａ」および列識別子３３ｃ＝「ａ」を、記憶手段１２に記憶する。暗号化データベースサーバ５０のデータ受信部６４は、通信手段５３を介して受信したこの暗号化表Ａ４１を、記憶手段５２に記憶する。
【００７２】
図５は、図４に示した処理によって出力された暗号化表Ａ４１について示す説明図である。図２に示した暗号化前の表Ａ３３と比べて、列ａの列データ３３ｂ＝ｍ［ａ、ｉ］（表Ａ３３の行数をＮ、ｉは１≦ｉ≦Ｎの自然数）が、暗号化列ベクトル４１ｂ＝（ｅ［ａ、ｉ］、ｄ［ａ、ｉ］）に置換されている。表識別子３３ａ＝「Ａ」および列ａの列識別子３３ｃ＝「ａ」は暗号化されずに保持される。
【００７３】
表Ａ３３のデータは、列データ３３ｂが暗号化された状態の暗号化表Ａ４１として暗号化データベースサーバ５０に送信され、この状態で暗号化データベースサーバ５０内部に記憶される。この暗号を解除できる暗号鍵（本実施形態では秘密鍵（ｋｅｙ）３１に対応する公開鍵）をこれとは別途に暗号化データベースサーバ５０に対して送信していない限りは、暗号化データベースサーバ５０の管理者でさえも暗号化表Ａ４１の暗号化を解除することはできない。即ち、たとえ暗号化データベースサーバ５０の側に悪意があったとしても、クライアント端末１０側のデータの秘密は守られる。
【００７４】
列暗号化部２１は、表Ａ３３に対して行った上記の処理と同様に、表Ｂ３４についても、同様に列ｂを暗号化して、列ｂの列データ３４ｂ＝ｍ［ｂ、ｊ］（表Ａ３３の行数をＭ、ｊは１≦ｊ≦Ｎの自然数）を暗号化列ベクトル４２ｂ＝（ｅ［ｂ、ｊ］、ｄ［ｂ、ｊ］）に置換して、暗号化表Ｂ４２とし、通信手段１５を介して暗号化データベースサーバ５０に送信する。そして記憶手段１２に、表識別子３４ａ＝「Ｂ」および列識別子３４ｃ＝「ｂ」を記憶する。
【００７５】
なお、列ｂの列データ３４ｂ＝ｍ［ｂ、ｊ］に対して比較値および暗号文を算出する数３および数５に示す処理では、列ａの列データ３３ｂ＝ｍ［ａ、ｉ］の算出に使用されたものと同一の秘密鍵（ｋｅｙ）３１が使用されるが、後で説明するようにｍ［ｂ、ｊ］＝ｍ［ａ、ｉ］となる値があったとしても得られる比較値および暗号文は異なる値となるので、発明が解決しようとする課題の欄の図１８で説明したような問題は発生しない。
【００７６】
図６は、図４のステップＳ１１１で送信された暗号化表Ａ４１を受信した暗号化データベースサーバ５０の側での、図１に示したデータ受信部６４の動作について示すフローチャートである。データ受信部６４が通信手段５３を介して暗号化表Ａ４１を受信すると（ステップＳ１５１）、この暗号化表Ａ４１を記憶手段５２に記憶する（ステップＳ１５２）。
【００７７】
データ受信部６４が暗号化表Ｂ４２を受信した場合にも、これと同様にして受信した暗号化表Ｂ４２を記憶手段５２に記憶する。以後に説明するクライアント端末１０および暗号化データベースサーバ５０の動作は、暗号化表Ａ４１および暗号化表Ｂ４２が既に記憶手段５２に記憶されていることが前提となる。
【００７８】
（暗号化表自然結合要求部）
図７は、図１に示したクライアント端末１０の、暗号化表自然結合要求装置としてのより詳しい構成を示す説明図である。クライアント端末１０は、主演算制御手段１１で暗号化表自然結合要求部２２が動作することによって、列暗号化部２１によって暗号化処理された暗号化表Ａ４１および暗号化表Ｂ４２を、列ａおよび列ｂに関して自然結合する自然結合要求文７１を生成して暗号化データベースサーバ５０に送信する暗号化表自然結合要求装置として機能する。
【００７９】
暗号化表自然結合要求部２２は、列秘密鍵生成機能２２ａ、列公開鍵生成機能２２ｂ、表結合鍵生成機能２２ｃ、および自然結合要求文出力機能２２ｄを備える。これら各機能の詳細については後述する。
【００８０】
暗号化表自然結合要求部２２への入力データとして、記憶手段１２には秘密鍵（ｋｅｙ）３１、図５に示した暗号化表Ａ４１の表識別子３３ａ＝「Ａ」と列識別子３３ｃ＝「ａ」、暗号化表Ｂ４２の表識別子３３ａ＝「Ｂ」と列識別子３３ｃ＝「ｂ」が記憶されている。暗号化表Ａ４１および暗号化表Ｂ４２の、これら以外のデータはここでは使用されない。
【００８１】
図８は、図７に示した暗号化表自然結合要求部２２の処理について示すフローチャートである。列公開鍵生成機能２２ｂは、暗号化表Ａ４１および暗号化表Ｂ４２の表識別子３３ａおよび３４ａ、列ａおよびｂの列識別子３３ｃおよび３４ｃから、以下に示す数６および数７で示される計算によって、列ａの列公開鍵ｇ［ａ］７２ａおよび列ｂの列公開鍵ｇ［ｂ］７２ｂを算出する（ステップＳ２０１）。
【数６】
2012043012.tif 000008
【数７】
2012043012.tif 000009
【００８２】
列秘密鍵生成機能２２ａは、秘密鍵（ｋｅｙ）３１と、表Ａ３３および表Ｂ３４の表識別子３３ａ、および列ａおよびｂの列識別子３３ｃから、以下に示す数８および数９で示される計算によって、列公開鍵ｇ［ａ］７２ａおよび列公開鍵ｇ［ｂ］７２ｂに各々対応する、列ａの列秘密鍵ｘ［ａ］７２ｃおよび列ｂの列秘密鍵ｘ［ｂ］７２ｄを算出する（ステップＳ２０２）。
【数８】
2012043012.tif 000010
【数９】
2012043012.tif 000011
【００８３】
なお、以上で述べた暗号化表自然結合要求部２２の列秘密鍵生成機能２２ａおよび列公開鍵生成機能２２ｂの機能および動作は、列暗号化部２１の列秘密鍵生成機能２１ａおよび列公開鍵生成機能２１ｂと同一である。暗号化表自然結合要求部２２で生成される列公開鍵および列秘密鍵７２ａ〜７２ｄも、列暗号化部２１で生成される列公開鍵４３ａおよび列秘密鍵４３ｂと同一である。従って、列暗号化部２１と暗号化表自然結合要求部２２とが同一のコンピュータで動作するものであれば、列秘密鍵生成機能２１ａ（２２ａ）および列公開鍵生成機能２１ｂ（２２ｂ）を共通のモジュールとすることは可能である。
【００８４】
また、列暗号化および自然結合要求の動作を通じて生成された列公開鍵および列秘密鍵を共用することもできる。しかしながら、列公開鍵および列秘密鍵を長時間に亘って記憶する領域を記憶手段１２上に確保しておくことは、セキュリティ上の観点からして好ましいことではない。そのため、本実施形態では、列暗号化および自然結合要求の各々の動作を行うたびごとに、列公開鍵および列秘密鍵を生成するようにしている。
【００８５】
表結合鍵生成機能２２ｃは、これら各々の列公開鍵および列秘密鍵７２ａ〜７２ｄから、数１０で示される要素Ｊ＿１と数１１で示される要素Ｊ＿２とからなる表結合鍵ｊ［ａ、ｂ］７２ｅを、以下に示す数１２で示されるように算出する（ステップＳ２０３）。
【数１０】
2012043012.tif 000012
【数１１】
2012043012.tif 000013
【数１２】
2012043012.tif 000014
【００８６】
自然結合要求文出力機能２２ｄは、ここまでの計算結果から、以下のＡ１３で示される自然結合要求文７１を出力して暗号化データベースサーバ５０に送信する（ステップＳ２０４）。暗号化データベースサーバ５０のデータ受信部６４は、この自然結合要求文７１を受信したことに反応して、暗号化表自然結合部６３に後述の自然結合の動作を行わせる。
【数１３】
2012043012.tif 000015
【００８７】
（暗号化表自然結合部）
図９は、図１に示した暗号化データベースサーバ５０の、暗号化表自然結合装置としてのより詳しい構成を示す説明図である。暗号化データベースサーバ５０は、主演算制御手段５１で暗号化表自然結合部６３が動作することによって、クライアント端末１０の列暗号化部２１によって暗号化された暗号化表Ａ４１および暗号化表Ｂ４２を、暗号化表自然結合要求部２２が発行した自然結合要求文７１に基づいて列ａおよび列ｂに関して自然結合して暗号化表Ａ×Ｂ８１を出力してクライアント端末１０に返信する暗号化表自然結合装置として機能する。
【００８８】
暗号化表自然結合部６３は、共通比較値生成機能６３ａ、隠蔽比較値更新機能６３ｂ、および自然結合機能６３ｃを備える。これら各機能の詳細については後述する。
【００８９】
暗号化表自然結合部６３への入力データとして、記憶手段５２にはクライアント端末１０の列暗号化部２１から受信した暗号化表Ａ４１および暗号化表Ｂ４２が記憶されている。クライアント端末１０の暗号化表自然結合要求部２２が発行した自然結合要求文７１は、通信手段５３を介して受信され、暗号化表自然結合部６３に入力される。前述のように、自然結合要求文７１には各々の行列と暗号化された列の識別子、そして表結合鍵ｊ［ａ、ｂ］が含まれている。
【００９０】
図１０は、図９に示した暗号化表自然結合部６３の処理について示すフローチャートである。ｉ＝１を初期値として定義し（ステップＳ３０１）、共通比較値生成機能６３ａは、暗号化表Ａ４１の列ａの各ｉ番目の成分ｄ［ａ、ｉ］と、以下の数１４（数１１〜１３と等価）で示される表結合鍵ｊ［ａ、ｂ］から、数１５で示される共通比較値ｄ＿ｂ［ａ、ｉ］８２ａを算出する（ステップＳ３０２）。
【数１４】
2012043012.tif 000016
【数１５】
2012043012.tif 000017
【００９１】
隠蔽比較値更新機能６３ｂは、暗号化表Ａ４１の列ａの各ｉ番目の成分の隠蔽比較値ｄ［ａ、ｉ］を、このｄ＿ｂ［ａ、ｉ］で置き換えて、これを置換済表Ａ’８３とする（ステップＳ３０３）。以後、ｉを１ずつ増加させ、ｉが暗号化表Ａ４１の行数ＮとなるまでステップＳ３０２〜３０３の処理を繰り返す（ステップＳ３０４〜３０５）。
【００９２】
共通比較値生成機能６３ａは、ｉ＝１を初期値として定義し（ステップＳ３０６）、暗号化表Ｂ４２の列ａの各ｉ番目の成分ｄ［ｂ、ｉ］と、数１４で示した表結合鍵ｊ［ａ、ｂ］から、数１６で示される共通比較値ｄ＿ａ［ｂ、ｉ］８２ｂを算出する（ステップＳ３０７）。
【数１６】
2012043012.tif 000018
【００９３】
隠蔽比較値更新機能６３ｂは、暗号化表Ｂの列ｂの各ｉ番目の成分の隠蔽比較値ｄ［ｂ、ｉ］を、このｄ＿ａ［ｂ、ｉ］で置き換えて、これを置換済表Ｂ’８４とする（ステップＳ３０８）。以後、ｉを１ずつ増加させ、ｉが暗号化表Ｂ４２の行数ＭとなるまでステップＳ１０７〜３０８の処理を繰り返す（ステップＳ３０９〜３１０）。
【００９４】
自然結合機能６３ｃは、以上で得られた置換済表Ａ’Ｂ’を、置換済表Ａ’の列ａの各ｉに関してｄ＿ｂ［ｉ、ａ］が作る列と置換済暗号化表Ｂ’の列ｂの各ｉに関してｄ＿ａ［ｉ、ｂ］が作る列の値が等しい事を要求する等結合を行う（ステップＳ３１１）。自然結合機能６３ｃは最後に、等結合が完了した暗号化表Ａ×Ｂ８１を出力し、クライアント端末１０に対して返信する（ステップＳ３１２）。クライアント端末１０は、通信手段１５を介して受信した暗号化表Ａ×Ｂ８１を、出力手段１４を介してユーザに提示する。
【００９５】
（本実施形態の処理による効果）
以上で示した処理による効果について説明する。
列暗号化装置が表Ａの列ａを鍵ｋｅｙによって暗号化すると、ｉ番目の要素ｍ［ｉ］は、以下の数１７に示す暗号文と隠蔽比較値（ｅ［ａ、ｉ］、ｄ［ａ、ｉ］）に置換される。
【数１７】
2012043012.tif 000019
【００９６】
暗号化表Ａおよび暗号化表Ｂで、同一の平文ｍが含まれていたとしても、以下の数１８に示す、数１７右辺の第１の要素（暗号文）にはランダムに選ばれた乱数ｒ’［ａ、ｉ］が暗号化される平文に含まれているので、結果として得られる暗号文も異なる。従って、暗号文のみから平文の同一性を判定することはできない。
【数１８】
2012043012.tif 000020
【００９７】
また、数１７右辺の第２の要素（隠蔽比較値）からも、以下の数１９に示す表ＡおよびＢについての同一要素が等しいか否かを判別することは、たとえ（ｇ［ｃ］）＾ｘ［ａ］や（ｇ［ｄ］）＾ｘ［ｂ］などのようなｘ［ａ］やｘ［ｂ］に関する情報を別に得ることができたとしても、ｃ＝ｂやｄ＝ａであることを証明できない限りは困難である。従って、暗号化表Ａおよび暗号化表Ｂのみを与えられた状態では、これらに対して自然結合を行うことはできない。
【数１９】
2012043012.tif 000021
【００９８】
一方、暗号化表Ａおよび暗号化表Ｂに対して自然結合を行う場合に、（ｇ［ａ］）＾ｘ［ｂ］および（ｇ［ｂ］）＾ｘ［ａ］、即ち表結合鍵が与えられたとすると、表Ａの列ａ第ｉ番目の成分ｄ［ａ、ｉ］に関して数１５で示された共通比較値ｄ＿ｂ［ａ、ｉ］を計算すると、以下の数２０のようになる。
【数２０】
2012043012.tif 000022
【００９９】
そして、表Ｂの列ｂ第ｊ番目の成分ｄ［ｂ、ｊ］に関して数１６で示された共通比較値ｄ＿ａ［ｂ、ｊ］を計算すると、以下の数２１のようになる。
【数２１】
2012043012.tif 000023
【０１００】
即ち、表結合鍵が与えられていれば、これらの共通比較値ｄ＿ａおよびｄ＿ｂを比較することによって、ｆ［ａ、ｉ］とｆ［ｂ、ｊ］とが等しいか否か、すなわちｍ［ａ、ｉ］とｍ［ｂ、ｊ］とが等しいか否かが判別可能となるので、この判別結果に基づいて表ＡおよびＢの自然結合が可能となる。
【０１０１】
この動作には、双線形写像の計算とスカラー倍算が必要であるが、これらの計算数は、各々、表Ａの列ａの要素数と表Ｂの列ｂの要素数の和の個数である。即ち、本実施形態の動作によって、計算量が大幅に増加することはない。
【０１０２】
（第１の実施形態の全体的な動作）
次に、上記の実施形態の全体的な動作について説明する。本実施形態に係る自然結合方法は、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号鍵をクライアント端末の記憶手段に予め記憶し、入力された第１の表のａ列目のデータと第２の表のｂ列目のデータとを暗号鍵によってクライアント端末の記憶手段が暗号化して外部に出力し（図４・ステップＳ１０１〜１１１）、暗号化された第１および第２の表を暗号化データベースサーバのデータ受信部が受信して記憶し（図６・ステップＳ１５１〜１５２）、第１および第２の表の表識別子とａ列目およびｂ列目の列識別子とから暗号鍵によって生成された列公開鍵および列秘密鍵を含む表結合鍵をクライアント端末の暗号化表自然結合要求部が生成し（図８・ステップＳ２０１〜２０３）、暗号化された第１の表および第２の表をａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文に表結合鍵を含めてクライアント端末の暗号化表自然結合要求部が出力し（図８・ステップＳ２０４）、暗号化された第１および第２の表に対して暗号化データベースサーバの暗号化表自然結合部が自然結合要求文に従って表結合鍵を適用して自然結合を実行し（図１０・ステップＳ３０１〜３１１）、自然結合の結果を暗号化データベースサーバの暗号化表自然結合部がクライアント端末に返信する（図１０・ステップＳ３１２）。
【０１０３】
ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータであるクライアント端末１０および暗号化データベースサーバ５０に実行させるようにしてもよい。本プログラムは、非一時的な記録媒体、例えば、ＤＶＤ、ＣＤ、フラッシュメモリ等に記録されてもよい。その場合、本プログラムは、記録媒体からコンピュータによって読み出され、実行される。
この動作により、本実施形態は以下のような効果を奏する。
【０１０４】
本実施形態では、データベースサーバに記憶されたデータを暗号化し、異なる表にある要素は異なる値に暗号化されることで情報の漏洩を防ぐことができる一方で、データベースは必要な場合に表結合鍵を含む自然結合要求文をデータベースサーバに与えて、二つの表の自然結合を実行させることができる。本実施形態によれば、データベースシステム上の処理において頻繁に行われる処理である自然結合をデータを復号化せずに実行可能としたので、データベースシステムの利便性とセキュリティの保護とを両立させることが可能である。
【０１０５】
これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。
【０１０６】
上述した各々の実施形態について、その新規な技術内容の要点をまとめると、以下のようになる。なお、上記実施形態の一部または全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。
【０１０７】
（付記１）  クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、
前記クライアント端末が、
暗号鍵を予め記憶する記憶手段と、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって暗号化して外部に出力する列暗号化部と、
暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文を出力する暗号化表自然結合要求部とを備えると共に、
前記暗号化表自然結合要求部が、前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力し、
前記暗号化データベースサーバが、
前記暗号化された第１および第２の表を受信して記憶するデータ受信部と、
前記暗号化された第１および第２の表に対して前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースシステム。
【０１０８】
（付記２）  前記クライアント端末の前記列暗号化部が、前記第１の表のａ列目に対して、
前記暗号鍵および前記第１の表の表識別子と前記ａ列目の列識別子から前記ａ列目の列秘密鍵ｘ［ａ］を生成する列秘密鍵生成機能と、
前記第１の表の表識別子と前記ａ列目の列識別子から前記ａ列目の列秘密鍵に対応するａ列目の列公開鍵ｇ［ａ］を生成する列公開鍵生成機能と、
前記第１の表のａ列目の各成分と前記暗号鍵とから比較値を生成する比較値生成機能と、
各々の前記比較値と前記暗号鍵、前記ａ列目の列秘密鍵および列公開鍵から隠蔽比較値を生成する隠蔽比較値生成機能と、
前記ａ列目のデータを前記暗号鍵によって暗号化して暗号文を生成する暗号化機能と、
前記ａ列目のデータを前記暗号文および前記隠蔽比較値に置換して前記第１の表を暗号化してこの暗号化された前記第１の表を前記暗号化データベースサーバに送信する表更新機能とを有すると共に、
前記列暗号化部が前記第２の表のｂ列目に対しても同様に列秘密鍵ｘ［ｂ］および列公開鍵ｇ［ｂ］を生成して、それらから前記比較値、前記隠蔽比較値、および暗号文を生成して前記第２の表を暗号化して前記暗号化データベースサーバに送信することを特徴とする、付記１に記載の暗号化データベースシステム。
【０１０９】
（付記３）  前記クライアント端末の前記列暗号化部が、前記ａ列目の各成分に対応する乱数を生成する乱数生成機能を備えると共に、
前記列暗号化部の前記隠蔽比較値生成機能が、各々の前記比較値と前記暗号鍵、前記ａ列目の列秘密鍵および列公開鍵、および前記乱数から前記隠蔽比較値を生成することを特徴とする、付記２に記載の暗号化データベースシステム。
【０１１０】
（付記４）  前記クライアント端末の前記暗号化表自然結合要求部が、
前記第１の表の表識別子と前記ａ列目の列識別子、前記第２の表の表識別子と前記ｂ列目の列識別子、および前記暗号鍵から表結合鍵を生成する表結合鍵生成機能と、
前記第１の表の表識別子と前記ａ列目の列識別子、前記第２の表の表識別子と前記ｂ列目の列識別子、および前記表結合鍵から前記自然結合要求文を出力して前記暗号化データベースサーバに送信する自然結合要求文出力機能とを有することを特徴とする、付記２に記載の暗号化データベースシステム。
【０１１１】
（付記５）  前記表結合鍵が前記列公開鍵ｇ［ａ］の列秘密鍵ｘ［ｂ］乗、および前記列公開鍵ｇ［ｂ］の列秘密鍵ｘ［ａ］乗を要素として含むことを特徴とする、付記４に記載の暗号化データベースシステム。
【０１１２】
（付記６）  前記クライアント端末の前記暗号化表自然結合要求部が、前記列暗号化部と同一の列秘密鍵生成機能および列公開鍵生成機能を備えることを特徴とする、付記４に記載の暗号化データベースシステム。
【０１１３】
（付記７）  前記暗号化データベースサーバの前記暗号化表自然結合部が、
前記暗号化された第１の表のａ列目の隠蔽比較値から前記表結合鍵の前記列公開鍵ｇ［ｂ］の列秘密鍵ｘ［ａ］乗の要素を用いて第１の共通比較値を生成すると共に前記暗号化された第２の表のｂ列目の隠蔽比較値から前記表結合鍵の前記列公開鍵ｇ［ａ］の列秘密鍵ｘ［ｂ］乗の要素を用いて第２の共通比較値を生成する共通比較値生成機能と、
前記暗号化された第１の表のａ列目の隠蔽比較値を前記第１の共通比較値に置換すると共に前記暗号化された第２の表のｂ列目の隠蔽比較値を前記第２の共通比較値に置換する隠蔽比較値更新機能と、
前記置換された第１および第２の表を前記自然結合要求文に従って前記ａ列目およびｂ列目に関して自然結合を実行してその結果を前記クライアント端末に返信する自然結合機能とを有することを特徴とする、付記５に記載の暗号化データベースシステム。
【０１１４】
（付記８）  暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成するクライアント端末であって、
暗号鍵を予め記憶する記憶手段と、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって暗号化して外部に出力する列暗号化部と、
暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文を出力する暗号化表自然結合要求部とを備えると共に、
前記暗号化表自然結合要求部が、前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力することを特徴とするクライアント端末。
【０１１５】
（付記９）  クライアント端末と相互に接続されて暗号化データベースシステムを構成する暗号化データベースサーバであって、
前記暗号化された第１および第２の表を受信して記憶するデータ受信部と、
前記暗号化された第１および第２の表に対して前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースサーバ。
【０１１６】
（付記１０）  クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、
暗号鍵を前記クライアント端末の記憶手段に予め記憶し、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって前記クライアント端末の記憶手段が暗号化して外部に出力し、
前記暗号化された第１および第２の表を前記暗号化データベースサーバのデータ受信部が受信して記憶し、
前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を前記クライアント端末の暗号化表自然結合要求部が生成し、
暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて前記クライアント端末の暗号化表自然結合要求部が出力し、
前記暗号化された第１および第２の表に対して前記暗号化データベースサーバの暗号化表自然結合部が前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行し、
前記自然結合の結果を前記暗号化データベースサーバの前記暗号化表自然結合部が前記クライアント端末に返信することを特徴とする自然結合方法。
【０１１７】
（付記１１）  暗号鍵を予め記憶しているクライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、
前記クライアント端末が備えるコンピュータに、
外部から入力される第１の表のａ列目のデータと第２の表のｂ列目のデータとを前記暗号鍵によって暗号化して外部に出力する手順、
前記第１および第２の表の表識別子と前記ａ列目およびｂ列目の列識別子とから前記暗号鍵によって生成される列公開鍵および列秘密鍵を含む表結合鍵を生成する手順、
および暗号化された前記第１の表および第２の表を前記ａ列目およびｂ列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて出力する手順
を実行させることを特徴とする自然結合プログラム。
【０１１８】
（付記１２）  クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、
前記暗号化データベースサーバが備えるコンピュータに、
暗号化された第１および第２の表を前記クライアント端末から受信して記憶する手順、
前記暗号化された第１および第２の表に対して前記自然結合要求文に従って前記表結合鍵を適用して前記自然結合を実行する手順、
および前記自然結合の結果を前記クライアント端末に返信する手順
を実行させることを特徴とする自然結合プログラム。
【０１１９】
この出願は２０１０年９月２８日に出願された日本出願特願２０１０−２１７００８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１２０】
本発明は、暗号化データベースシステムにおいて利用可能である。特に、大量のデータを収容する暗号化データベースシステムにおいて、顕著な効果を発揮する。
【符号の説明】
【０１２１】
１  暗号化データベースシステム
１０  クライアント端末
１１、５１  主演算制御手段
１２、５２  記憶手段
１３  入力手段
１４  出力手段
１５、５３  通信手段
２１  列暗号化部
２１ａ、２２ａ  列秘密鍵生成機能
２１ｂ、２２ｂ  列公開鍵生成機能
２１ｃ  比較値生成機能
２１ｄ  隠蔽比較値生成機能
２１ｅ  暗号化機能
２１ｆ  表更新機能
２１ｇ  乱数生成機能
２２  暗号化表自然結合要求部
２２ｃ  表結合鍵生成機能
２２ｄ  自然結合要求文出力機能
３１  秘密鍵
３３  表Ａ
３３ａ、３４ａ  表識別子
３３ｂ、３４ｂ  列データ
３３ｃ、３４ｃ  列識別子
３４  表Ｂ
４１  暗号化表Ａ
４１ｂ、４２ｂ  暗号化列ベクトル
４２  暗号化表Ｂ
５０  暗号化データベースサーバ
６３  暗号化表自然結合部
６３ａ  共通比較値生成機能
６３ｂ  隠蔽比較値更新機能
６３ｃ  自然結合機能
６４  データ受信部
７１  自然結合要求文
８１  暗号化表Ａ×Ｂ
８３  置換済表Ａ’
８４  置換済表Ｂ’
【図１】
2012043012.tif 000024
【図２】
2012043012.tif 000025
【図３】
2012043012.tif 000026
【図４】
2012043012.tif 000027
【図５】
2012043012.tif 000028
【図６】
2012043012.tif 000029
【図７】
2012043012.tif 000030
【図８】
2012043012.tif 000031
【図９】
2012043012.tif 000032
【図１０】
2012043012.tif 000033
【図１１】
2012043012.tif 000034
【図１２】
2012043012.tif 000035
【図１３】
2012043012.tif 000036
【図１４】
2012043012.tif 000037
【図１５】
2012043012.tif 000038
【図１６】
2012043012.tif 000039
【図１７】
2012043012.tif 000040
【図１８】
2012043012.tif 000041
【国際調査報告】
2012043012.tif 000042
2012043012.tif 000043
2012043012.tif 000044
2012043012.tif 000045