"クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、前記クライアント端末が、暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶する記憶手段と、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって暗号化して外部に出力する列暗号化部と、暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文を出力すると共に、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵および前記群の生成子によって生成される列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力する暗号化表自然結合要求部とを備え、前記暗号化データベースサーバが、前記暗号化された第1および第2の表を受信して記憶するデータ受信部と、前記暗号化された第1および第2の表に対して前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースシステム。前記クライアント端末の前記列暗号化部が、前記第1の表のa列目に対して、前記暗号鍵および前記第1の表の表識別子と前記a列目の列識別子から前記a列目の列秘密鍵x[a]を生成する列秘密鍵生成機能と、前記群の生成子から前記a列目の列秘密鍵に対応するa列目の列公開鍵を生成する列公開鍵生成機能と、前記第1の表のa列目の各成分と前記暗号鍵とから比較値を生成する比較値生成機能と、各々の前記比較値と前記列公開鍵から隠蔽比較値を生成する隠蔽比較値生成機能と、前記a列目のデータを前記暗号鍵によって暗号化して暗号文を生成する暗号化機能と、前記a列目のデータを前記暗号文および前記隠蔽比較値に置換して前記第1の表を暗号化してこの暗号化された前記第1の表を前記暗号化データベースサーバに送信する表更新機能とを有すると共に、前記列暗号化部が前記第2の表のb列目に対しても同様に列秘密鍵x[b]および列公開鍵を生成して、それらから前記比較値、前記隠蔽比較値、および暗号文を生成して前記第2の表を暗号化して前記暗号化データベースサーバに送信することを特徴とする、請求項1に記載の暗号化データベースシステム。前記クライアント端末の前記暗号化表自然結合要求部が、前記第1の表の表識別子と前記a列目の列識別子、前記第2の表の表識別子と前記b列目の列識別子、前記暗号鍵および前記群の生成子から表結合鍵を生成する表結合鍵生成機能と、前記第1の表の表識別子と前記a列目の列識別子、前記第2の表の表識別子と前記b列目の列識別子、および前記表結合鍵から前記自然結合要求文を出力して前記暗号化データベースサーバに送信する自然結合要求文出力機能とを有することを特徴とする、請求項2に記載の暗号化データベースシステム。前記表結合鍵が前記列秘密鍵x[a]と前記列秘密鍵x[b]との比を要素として含むことを特徴とする、請求項3に記載の暗号化データベースシステム。前記暗号化データベースサーバの前記暗号化表自然結合部が、前記暗号化された第1の表のa列目の隠蔽比較値から前記列秘密鍵x[a]と前記列秘密鍵x[b]との比の要素を用いて共通比較値を生成すると共に前記暗号化された第1の表のa列目の隠蔽比較値をこの共通比較値で置換する隠蔽比較値更新機能と、前記置換された第1の表を前記第2の表との間で前記自然結合要求文に従って前記a列目およびb列目に関して自然結合を実行してその結果を前記クライアント端末に返信する自然結合機能とを有することを特徴とする、請求項4に記載の暗号化データベースシステム。暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成するクライアント端末であって、暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶する記憶手段と、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって暗号化して外部に出力する列暗号化部と、暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文を出力すると共に、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵および前記群の生成子によって生成される列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力する暗号化表自然結合要求部とを備えることを特徴とするクライアント端末。クライアント端末と相互に接続されて暗号化データベースシステムを構成する暗号化データベースサーバであって、前記暗号化された第1および第2の表を受信して記憶するデータ受信部と、前記暗号化された第1および第2の表に対して前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースサーバ。クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号鍵および当該暗号鍵の要部をなす群の生成子を前記クライアント端末の記憶手段に予め記憶し、入力された第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって前記クライアント端末の記憶手段が暗号化して外部に出力し、前記暗号化された第1および第2の表を前記暗号化データベースサーバのデータ受信部が受信して記憶し、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵によって生成された列秘密鍵を含む表結合鍵を前記クライアント端末の暗号化表自然結合要求部が生成し、暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて前記クライアント端末の暗号化表自然結合要求部が出力し、前記暗号化された第1および第2の表に対して前記暗号化データベースサーバの暗号化表自然結合部が前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行し、前記自然結合の結果を前記暗号化データベースサーバの前記暗号化表自然結合部が前記クライアント端末に返信することを特徴とする自然結合方法。暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶しているクライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、前記クライアント端末が備えるコンピュータに、入力された第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって暗号化して外部に出力する手順、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵によって生成された列秘密鍵を含む表結合鍵を生成する手順、および暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて出力する手順を実行させることを特徴とする自然結合プログラム。クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、前記暗号化データベースサーバが備えるコンピュータに、暗号化された第1および第2の表を前記クライアント端末から受信して記憶する手順、前記暗号化された第1および第2の表に対して前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行する手順、および前記自然結合の結果を前記クライアント端末に返信する手順を実行させることを特徴とする自然結合プログラム。データベースは、大量のデータの中から単に必要なデータを抽出するだけではなく、SQLコマンドなどによって複数の表を結合することが頻繁に行われる。暗号化されたデータに対しても、この表を自然結合する演算を、セキュリティを損なうことなく容易に行えることが当然望まれる。しかしながら、前述のように暗号鍵keyは各々の表に対して固有に与えられるものであるので、異なる表には異なる暗号鍵が与えられることになる。従って、異なる表にある同一のデータは、異なる暗号鍵によって暗号化されると異なるデータとなる。このため、図11で示した暗号化データベース管理装置901で、列暗号化部921によって暗号化されたデータに関して異なる表を結合する演算を行うためには、前述したように該データを一度復号化してから結合する必要がある。このことをより具体的に説明する。図17は、図11で示した暗号化データベース管理装置901で、複数の暗号化表A941および暗号化表B942に対して自然結合の演算を行う場合の例についての説明図である。図17aが暗号化表A941を、図17bが暗号化表B942を、図17cがこれらを自然結合して得られる暗号化表A×B981を各々示す。暗号化表A941は、第1列をユーザ名、第2列をクレジットカード番号として、各ユーザ名に対応するカード番号の対応関係を示す。そして第2列クレジットカード番号は、秘密鍵key931aによって暗号化されている。暗号化表B942は、第1列をクレジットカード番号、第2列をクレジットカード有効期限として、各カードの有効期限について示している。そして第1列クレジットカード番号は、秘密鍵key’931bによって暗号化されている。ここで、該データベースの管理者がユーザ名とクレジットカード有効期限との対応について知りたい場合には、暗号化表自然結合要求部922によって、暗号化表A941および暗号化表B942を列クレジットカード番号に関して自然結合するよう自然結合命令文971を発行する。この処理によって、第1列ユーザ名、第2列クレジットカード番号、第3列クレジットカード有効期限という3列を持つ暗号化表A×B981が得られることが期待される。しかしながら、暗号化表A941および暗号化表B942は、各々異なる暗号鍵によって暗号化されているので、平文の段階では同一のデータであっても、異なる暗号鍵によって異なるデータとなる。従って、暗号化表自然結合部963は、暗号化されたデータをそのまま自然結合のキーとすることはできない。この処理を行うためには、図14に示した復号化機能963aによって列クレジットカード番号を復号化する処理が必要となる。この処理には、暗号化表A941および暗号化表B942に対する秘密鍵key931aおよび秘密鍵key’931bに各々対応する公開鍵pkey972aおよび公開鍵pkey’972bが必要である。これらの公開鍵を利用すれば、この処理を行うために列列クレジットカード番号を復号化することは可能ではある。しかしながら、この処理を行っている間は復号化された平文のデータが装置に記憶されることになるので、その間にその平文のデータが漏洩する危険性を否定することはできない。図18は、上述の問題を解決するため、key=key’、即ち同一の暗号鍵keyを利用して暗号化された暗号化表C1001および暗号化表D1002に対して自然結合の演算を行う例についての説明図である。図18aが暗号化表C1001を、図18bが暗号化表D1002を、図18cがこれらを自然結合して得られる暗号化表C×D1003を各々示す。この暗号鍵keyは、公開鍵方式のものであっても、共通鍵方式のものであってもよい。暗号化表C1001は、第1列をユーザ名、第2列をクレジットカード番号として、各ユーザ名に対応するカード番号の対応関係を示す。そして第2列クレジットカード番号は、暗号鍵keyによって暗号化されている。暗号化表D1002は、第1列をクレジットカード番号、第2列をブラックリスト登録日として、各カードの有効期限について示している。そして第1列クレジットカード番号は、表C1001と同一の暗号鍵keyによって暗号化されている。暗号鍵keyが同一であれば、暗号化表C1001の第2列クレジットカード番号と暗号化表D1002の第1列クレジットカード番号とで、暗号化前のデータが同一であれば、暗号化された後も同一データとなるので、復号化機能963aを利用しなくて暗号化表C1001および暗号化表D1002をそのまま自然結合して暗号化表C×D1003を得ることが可能である。しかしながら、このことは同時に、暗号鍵keyを持たない不当なユーザであっても、暗号化されたデータに関して暗号化表C1001および暗号化表D1002を自然結合して暗号化表C×D1003を得る処理ができてしまうことを意味する。このようなことは、暗号化データベースの管理において、望ましいことではない。即ち、正当な暗号鍵を持つユーザであれば、暗号化されたデータを復号化する処理を行わなくとも、暗号化されたデータに関して複数の表を自然結合することが可能で、かつ正当な暗号鍵を持たない不当なユーザには暗号化されたデータに関する自然結合ができない、そのような特徴を持つ暗号化データベース管理装置が求められている。かつ、データベースは膨大な量のデータを扱うものであるので、この処理を行うことによる計算量の大幅な増大も抑制されなければならない。前述の各特許文献および非特許文献は、いずれもこの問題を解決することを目的とはしておらず、当然ながらこの問題を解決しうる技術は記載されていない。本発明の目的は、暗号化されたデータベースの複数の表を、データの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータに関して自然結合することを可能とする暗号化データベースシステム、クライアント端末、暗号化データベースサーバ、自然結合方法およびプログラムを提供することにある。上記目的を達成するため、本発明に係る暗号化データベースシステムは、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、クライアント端末が、暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶する記憶手段と、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを暗号鍵および群の生成子によって暗号化して外部に出力する列暗号化部と、暗号化された第1の表および第2の表をa列目およびb列目に関して自然結合することを要求する自然結合要求文を出力すると共に、第1および第2の表の表識別子とa列目およびb列目の列識別子とから暗号鍵および群の生成子によって生成される列秘密鍵を含む表結合鍵を生成して自然結合要求文に含めて出力する暗号化表自然結合要求部とを備え、暗号化データベースサーバが、暗号化された第1および第2の表を受信して記憶するデータ受信部と、暗号化された第1および第2の表に対して自然結合要求文に従って表結合鍵中の列秘密鍵を適用して自然結合を実行する暗号化表自然結合部とを備えることを特徴とする。上記目的を達成するため、本発明に係るクライアント端末は、暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成するクライアント端末であって、暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶する記憶手段と、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを暗号鍵および群の生成子によって暗号化して外部に出力する列暗号化部と、暗号化された第1の表および第2の表をa列目およびb列目に関して自然結合することを要求する自然結合要求文を出力すると共に、第1および第2の表の表識別子とa列目およびb列目の列識別子とから暗号鍵および群の生成子によって生成される列秘密鍵を含む表結合鍵を生成して自然結合要求文に含めて出力する暗号化表自然結合要求部とを備えることを特徴とする。上記目的を達成するため、本発明に係る暗号化データベースサーバは、クライアント端末と相互に接続されて暗号化データベースシステムを構成する暗号化データベースサーバであって、暗号化された第1および第2の表を受信して記憶するデータ受信部と、暗号化された第1および第2の表に対して自然結合要求文に従って表結合鍵中の列秘密鍵を適用して自然結合を実行する暗号化表自然結合部とを備えることを特徴とする。上記目的を達成するため、本発明に係る自然結合方法は、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号鍵および当該暗号鍵の要部をなす群の生成子をクライアント端末の記憶手段に予め記憶し、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを暗号鍵および群の生成子によってクライアント端末の記憶手段が暗号化して外部に出力し、暗号化された第1および第2の表を暗号化データベースサーバのデータ受信部が受信して記憶し、第1および第2の表の表識別子とa列目およびb列目の列識別子とから暗号鍵によって生成される列秘密鍵を含む表結合鍵をクライアント端末の暗号化表自然結合要求部が生成し、暗号化された第1の表および第2の表をa列目およびb列目に関して自然結合することを要求する自然結合要求文に表結合鍵を含めてクライアント端末の暗号化表自然結合要求部が出力し、暗号化された第1および第2の表に対して暗号化データベースサーバの暗号化表自然結合部が自然結合要求文に従って表結合鍵中の列秘密鍵を適用して自然結合を実行し、自然結合の結果を暗号化データベースサーバの暗号化表自然結合部がクライアント端末に返信することを特徴とする。上記目的を達成するため、本発明に係る自然結合プログラムは、暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶しているクライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、クライアント端末が備えるコンピュータに、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを暗号鍵および群の生成子によって暗号化して外部に出力する手順、第1および第2の表の表識別子とa列目およびb列目の列識別子とから暗号鍵によって生成される列秘密鍵を含む表結合鍵を生成する手順、および暗号化された第1の表および第2の表をa列目およびb列目に関して自然結合することを要求する自然結合要求文に表結合鍵を含めて出力する手順を実行させることを特徴とする。上記目的を達成するため、本発明に係る他の自然結合プログラムは、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号化データベースサーバが備えるコンピュータに、暗号化された第1および第2の表をクライアント端末から受信して記憶する手順、暗号化された第1および第2の表に対して自然結合要求文に従って表結合鍵中の列秘密鍵を適用して自然結合を実行する手順、および自然結合の結果をクライアント端末に返信する手順を実行させることを特徴とする。本発明は、上述したようにクライアント端末の側で暗号鍵および群の生成子から列秘密鍵を含む表結合鍵を生成してこれを含む自然結合要求文を暗号化データベースサーバに送信するように構成したので、この表結合鍵を受信した暗号化データベースサーバのみが、列秘密鍵を利用して、第1の表および第2の表において指定された列のデータが等しいか否かを判断可能となる。これによって、暗号化されたデータベースの複数の表を、データの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータに関して自然結合することが可能であるという優れた特徴を持つ暗号化データベースシステム、クライアント端末、暗号化データベースサーバ、自然結合方法およびプログラムを提供することができる。第1の実施形態以下、本発明の第1の実施形態の構成について添付図1、3、7、9に基づいて説明する。最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。本実施形態に係る暗号化データベースシステム1は、クライアント端末10と暗号化データベースサーバ50とが相互に接続されて構成される。クライアント端末10は、暗号鍵秘密鍵31および当該暗号鍵の要部をなす群の生成子32を予め記憶する記憶手段12と、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを暗号鍵によって暗号化して外部に出力する列暗号化部21と、暗号化された第1の表および第2の表をa列目およびb列目に関して自然結合することを要求する自然結合要求文71を出力する暗号化表自然結合要求部22とを備える。そして、この暗号化表自然結合要求部22は、第1および第2の表の表識別子とa列目およびb列目の列識別子とから暗号鍵および群の生成子32によって生成される列公開鍵および列秘密鍵を含む表結合鍵を生成して自然結合要求文71に含めて出力する。一方の暗号化データベースサーバ50は、暗号化された第1および第2の表を受信して記憶するデータ受信部64と、暗号化された第1および第2の表に対して自然結合要求文に従って表結合鍵中の列秘密鍵を適用して自然結合を実行する暗号化表自然結合部63とを備える。ここでクライアント端末の列暗号化部21は、第1の表のa列目に対して、暗号鍵秘密鍵31および第1の表表A33の表識別子33aとa列目の列識別子33cからa列目の列秘密鍵x[a]を生成する列秘密鍵生成機能21aと、群の生成子32からa列目の列秘密鍵に対応するa列目の列公開鍵を生成する列公開鍵生成機能21bと、第1の表のa列目の各成分と暗号鍵とから比較値生成機能21cと、各々の比較値と列公開鍵から隠蔽比較値を生成する隠蔽比較値生成機能21dと、a列目のデータを暗号鍵によって暗号化して暗号文を生成する暗号化機能21eと、a列目のデータを暗号文および隠蔽比較値に置換して第1の表を暗号化してこの暗号化された第1の表を暗号化データベースサーバに送信する表更新機能21fとを有する。そして列暗号化部21は、第2の表表B34のb列目に対しても同様に列秘密鍵x[b]および列公開鍵g[b]を生成して、それらから比較値、隠蔽比較値、および暗号文を生成して第2の表を暗号化して暗号化データベースサーバに送信する処理を行う。また、クライアント端末の暗号化表自然結合要求部22は、第1の表の表識別子とa列目の列識別子、第2の表の表識別子34aとb列目の列識別子34c、暗号鍵および群の生成子から表結合鍵を生成する表結合鍵生成機能22bと、第1の表の表識別子とa列目の列識別子、第2の表の表識別子とb列目の列識別子、および表結合鍵から自然結合要求文71を出力して暗号化データベースサーバに送信する自然結合要求文出力機能22cとを有する。そして、表結合鍵は、列秘密鍵x[a]と列秘密鍵x[b]との比を要素として含む。さらに、暗号化表自然結合要求部22が、列暗号化部と同一の列秘密鍵生成機能22aを含む。そして、暗号化データベースサーバの暗号化表自然結合部63は、暗号化された第1の表のa列目の隠蔽比較値から列秘密鍵x[a]と列秘密鍵x[b]との比の要素を用いて共通比較値を生成すると共に暗号化された第1の表のa列目の隠蔽比較値をこの共通比較値で置換する隠蔽比較値更新機能63aと、置換された第1の表を第2の表との間で自然結合要求文に従ってa列目およびb列目に関して自然結合を実行してその結果をクライアント端末に返信する自然結合機能63bとを有する。以上の構成を備えることにより、暗号化データベースシステム1はデータの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータに関して自然結合することが可能となる。以下、これをより詳細に説明する。記号および用語、そしてそれらの定義について本明細書で使用する記号、その定義について説明する。なお、本明細書の数式以外の行ではAに上付き添字BAのB乗などをA^B、Aに下付き添字BをA_Bと表すことにする。pは素数である。G、G_Tは各々、位数がpの巡回群である。pairは、GとGからG_Tへの双線形写像である。gは、Gの生成元である。Hashは、任意長の文字列からZ/pZへの写像であり、たとえばハッシュ関数などである。encは、鍵と平文を入力として暗号文を出力とする暗号化関数である。データベースの各表は、自らを一意的に識別する識別子を持つ。データベースの各表の各列は、その属する表の中で自らを一意的に識別する識別子を持つ。データベースの各表の各列を取り出したものを列ベクトルという。データベースの表Aと表Bとを、表Aの列aの要素と表Bの列bの要素が等しいという条件によって等結合することを、表Aと表Bを表Aの列aと表Bの列bに関して自然結合するという。ただし、この自然結合を行う際、重複する列は削除する。図1は、本発明に係る暗号化データベース管理システム1の構成を示す説明図である。暗号化データベース管理システム1は、クライアント端末10と暗号化データベースサーバ50とが、LANLocalAreaNetworkなどを介して相互に接続されて構成される。クライアント端末10は、一般的なコンピュータ装置としての構成を備える。即ち、クライアント端末10は、コンピュータプログラムを実行する主体となる主演算制御手段CPUCentralProcessingUnit11と、データを記憶する記憶手段12と、ユーザからの操作を受け付ける入力手段13と、ユーザに処理結果を提示する出力手段14と、他のコンピュータとのデータ通信を行う通信手段15とを備える。主演算制御手段11では、ユーザからの操作命令に応じて、列暗号化部21、および暗号化表自然結合要求部22が、各々コンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。また、記憶手段12には以後に説明する処理で使用する秘密鍵key31および群の生成子g32が記憶されている。そして入力手段13には、表A33および表B34が入力される。暗号化データベースサーバ50もまた、一般的なコンピュータ装置としての構成を備える。即ち、暗号化データベースサーバ50は、コンピュータプログラムを実行する主体となる主演算制御手段CPUCentralProcessingUnit51と、データを記憶する記憶手段52と、他のコンピュータとのデータ通信を行う通信手段53とを備える。主演算制御手段51では、クライアント端末10からの操作命令に応じて、暗号化表自然結合部63と、データ受信部64とがコンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。また、記憶手段52にはデータ受信部64がクライアント端末10から受信した、各々表A33および表B34を暗号化した暗号化表A41および暗号化表B42が記憶される。ここで、クライアント端末10で使用される暗号鍵としては、暗号化と復号化で共通の鍵を使用する共通鍵を使用することもできるが、公開鍵暗号方式の秘密鍵を使用することがより望ましいので、ここでは秘密鍵key31を使用する。この秘密鍵key31は、クライアント端末10から他の装置に向けて送信されることはない。また、秘密鍵key31に対応する公開鍵は、本実施形態では使用されない。なお、物理的なコンピュータ装置の区分については、この例の通りに従う必要は特にない。たとえば、列暗号化部21および暗号化表自然結合要求部22を、各々異なるコンピュータで動作させてもよい。また、列暗号化部21、暗号化表自然結合要求部22、および暗号化表自然結合部63を全て同一のコンピュータで動作させてもよい。図2は、図1に示した表A33および表B34について詳しく説明する説明図である。図2aが表A33を、図2bが表B34を各々示す。各々の表は、表全体に対して与えられた表識別子と、特定の列の列データとその列に対して与えられた列識別子とを有する。ここでは、表A33の表識別子33a=Aとし、表A33で暗号化の対象かつ自然結合のキーとなるa列目の列データ33b=m[a、i]表A33の行数をN、iは1≦i≦Nの自然数、a列目の列識別子33c=aとする。以後、この列を単に列aという。また、表B34の表識別子34a=Aとし、表B34で暗号化の対象かつ自然結合のキーとなるb列目の列データ34b=m[b、j]表B34の行数をM、jは1≦j≦Mの自然数、b列目の列識別子34c=bとする。以後、この列を単に列bという。列暗号化部図3は、図1に示したクライアント端末10の、列暗号化装置としてのより詳しい構成を示す説明図である。クライアント端末10は、主演算制御手段11で列暗号化部21が動作することによって、表Aの列aを暗号化する列暗号化装置として機能する。列暗号化部21は、列秘密鍵生成機能21a、列公開鍵生成機能21b、比較値生成機能21c、隠蔽比較値生成機能21d、暗号化機能21e、表更新機能21f、乱数生成機能21gとを備える。これら各機能の詳細については後述する。列暗号化部21への入力データとして、記憶手段12には秘密鍵key31が記憶され、図2aに示した表A33は入力手段13から入力される。ただし、図3では表A33に対する処理だけを説明するので、表B34およびこれに関連する要素については図示しない。図4は、図3に示した列暗号化部21の処理について示すフローチャートである。列秘密鍵生成機能21aは、秘密鍵key31a、表識別子33a=A、列識別子33c=aから、以下に示す数1によって列秘密鍵43a=xを算出するステップS101。ここで、数1の右辺のハッシュ関数の第1の変数ckeyは単なる文字列であり、クライアント端末10の装置内部でハッシュ関数の用途を区別するためのものである。従って、装置内部で用途を区別できさえすれば、どのような文字列であってもよい。これ以降のハッシュ関数についても同様である。列公開鍵生成機能21bは、列秘密鍵43a=xおよび群の生成子g32から、列公開鍵43b=gを、以下に示す数2によって算出するステップS102。i=1を初期値として定義しステップS103、比較値生成機能21cは、列a33bのi番目の成分m[a、i]に関する比較値43c=c[a、i]を、以下に示す数3によって算出するステップS104。隠蔽比較値生成機能21dは、隠蔽比較値43d=d[a、i]を、以下に示す数4によって算出するステップS105。暗号化機能21eは、暗号文43f=e[a、i]を以下に示す数5によって算出する。ステップS106。表更新機能21fは、この暗号文43f=e[a、i]と隠蔽比較値43d=d[a、i]とを利用して、列ベクトルe[a、i]、d[a、i]の第i成分を生成するステップS107、以後この列ベクトルを暗号化列ベクトル41bという。以後、iを1ずつ増加させ、i=NとなるまでステップS104~107の処理を繰り返すステップS108~109。表更新機能21fは最後に、i=Nとなって、行aを暗号化列ベクトル41bで置換した表A33を、暗号化表A41として出力し、通信手段15を介して暗号化データベースサーバ50に送信するステップS110。これと同時に、表更新機能21fは表識別子33a=Aおよび列識別子33c=aを、記憶手段12に記憶する。暗号化データベースサーバ50のデータ受信部64は、通信手段53を介して受信したこの暗号化表A41を、記憶手段52に記憶する。図5は、図4に示した処理によって出力された暗号化表A41およびB42について示す説明図である。図5aは、暗号化表A41について示す。図2aに示した暗号化前の表A33と比べて、列aの列データ33b=m[a、i]表A33の行数をN、iは1≦i≦Nの自然数が、暗号化列ベクトル41b=e[a、i]、d[a、i]に置換されている。表識別子33a=Aおよび列aの列識別子33c=aは暗号化されずに保持される。表A33のデータは、列データ33bが暗号化された状態の暗号化表A41として暗号化データベースサーバ50に送信され、この状態で暗号化データベースサーバ50内部に記憶される。この暗号を解除できる暗号鍵本実施形態では秘密鍵key31に対応する公開鍵をこれとは別途に暗号化データベースサーバ50に対して送信していない限りは、暗号化データベースサーバ50の管理者でさえも暗号化表A41の暗号化を解除することはできない。即ち、たとえ暗号化データベースサーバ50の側に悪意があったとしても、クライアント端末10側のデータの秘密は守られる。列暗号化部21は、表A33に対して行った上記の処理と同様に、表B34についても、同様に列bを暗号化して、列aの列データ34b=m[b、j]表A33の行数をM、jは1≦j≦Nの自然数を暗号化列ベクトル42b=e[b、j]、d[b、j]に置換して、暗号化表B42とする。図5bは、この暗号化表B42について示す。なお、列bの列データ34b=m[b、j]に対して比較値および暗号文を算出する数3および数5に示す処理では、列aの列データ33b=m[a、i]の算出に使用されたものと同一の秘密鍵key31が使用されるが、後で説明するようにm[b、j]=m[a、i]となる値があったとしても得られる比較値および暗号文は異なる値となるので、発明が解決しようとする課題の欄の図18で説明したような問題は発生しない。図6は、図4のステップS111で送信された暗号化表A41を受信した暗号化データベースサーバ50の側での、データ受信部64の動作について示すフローチャートである。データ受信部64が通信手段53を介して暗号化表A41を受信するとステップS151、この暗号化表A41を記憶手段52に記憶するステップS155。データ受信部64が暗号化表B42を受信した場合にも、これと同様にして受信した暗号化表B42を記憶手段52に記憶する。以後に説明するクライアント端末10および暗号化データベースサーバ50の動作は、暗号化表A41および暗号化表B42が既に記憶手段52に記憶されていることが前提となる。暗号化表自然結合要求部図7は、図1に示したクライアント端末10の、暗号化表自然結合要求装置としてのより詳しい構成を示す説明図である。クライアント端末10は、主演算制御手段11で暗号化表自然結合要求部22が動作することによって、列暗号化部21によって暗号化処理された暗号化表A41および暗号化表B42を、列aおよび列bに関して自然結合する自然結合要求文71を生成して暗号化データベースサーバ50に送信する暗号化表自然結合要求装置として機能する。暗号化表自然結合要求部22は、列秘密鍵生成機能22a、表結合鍵生成機能22b、および自然結合要求文出力機能22cを備える。これら各機能の詳細については後述する。暗号化表自然結合要求部22への入力データとして、記憶手段12には秘密鍵key31、図5aに示した暗号化表A41の表識別子33a=Aと列識別子33c=a、図5bに示した暗号化表B42の表識別子33a=Bと列識別子33c=bが記憶されている。暗号化表A41および暗号化表B42の、これら以外のデータはここでは使用されない。図8は、図7に示した暗号化表自然結合要求部22の処理について示すフローチャートである。列秘密鍵生成機能22aは、秘密鍵key31と、暗号化表A41および暗号化表B42の識別子33aおよび34a、列aおよびbの列識別子33cおよび34cから、以下の数6および数7で示される列aの列秘密鍵x[a]72aおよび列bの列秘密鍵x[b]72bを生成する。ステップS201。なお、以上で述べた暗号化表自然結合要求部22の列秘密鍵生成機能22aの機能および動作は、列暗号化部21の列秘密鍵生成機能21aと同一である。暗号化表自然結合要求部22で生成される列秘密鍵72a~72bも、列暗号化部21で生成される列秘密鍵43bと同一である。従って、列暗号化部21と暗号化表自然結合要求部22とが同一のコンピュータで動作するものであれば、列暗号化部21と暗号化表自然結合要求部22とで、列秘密鍵生成機能21a22aを共通化することは可能である。また、列暗号化および自然結合要求の動作を通じて生成された列秘密鍵を共用することもできる。しかしながら、列暗号化および自然結合要求の動作を通じて生成された列秘密鍵を長時間に亘って記憶する領域を記憶手段12上に確保しておくことは、セキュリティ上の観点からして望ましいことではない。そのため、本実施形態では、列暗号化および自然結合要求の各々の作業を行うたびごとに、列秘密鍵を生成するようにしている。表結合鍵生成機能22bは、これら各々の列秘密鍵72a~72bから、数8で示される表結合鍵j[a、b]72cを算出するステップS202。自然結合要求文出力機能22cは、ここまでの計算結果から、以下のA9で示される自然結合要求文71を出力して暗号化データベースサーバ50に送信するステップS203。暗号化データベースサーバ50のデータ受信部64は、この自然結合要求文71を受信したことに反応して、暗号化表自然結合部63に後述の自然結合の動作を行わせる。暗号化表自然結合部図9は、図1に示した暗号化データベースサーバ50の、暗号化表自然結合装置としてのより詳しい構成を示す説明図である。暗号化データベースサーバ50は、主演算制御手段51で暗号化表自然結合部63が動作することによって、クライアント端末10の列暗号化部21によって暗号化された暗号化表A41および暗号化表B42を、暗号化表自然結合要求部22が発行した自然結合要求文71に基づいて列aおよび列bに関して自然結合して暗号化表A×B81を出力してクライアント端末10に返信する暗号化表自然結合装置として機能する。暗号化表自然結合部63は、隠蔽比較値更新機能63a、および自然結合機能63bを備える。これら各機能の詳細については後述する。暗号化表自然結合部63への入力データとして、記憶手段52にはクライアント端末10の列暗号化部21から受信した暗号化表A41および暗号化表B42が記憶されている。クライアント端末10の暗号化表自然結合要求部22が発行した自然結合要求文71は、通信手段53を介して受信され、暗号化表自然結合部63に入力される。前述のように、自然結合要求文71には各々の行列と暗号化された列の識別子、そして表結合鍵j[a、b]が含まれている。図10は、図9に示した暗号化表自然結合部63の処理について示すフローチャートである。i=1を初期値として定義しステップS301、隠蔽比較値更新機能63aは、暗号化表A41の列aの各i番目の成分の隠蔽比較値d[a、i]を、以下の数10で示される新たな隠蔽比較値d’[a、i]で置き換えて、これを置換済表A’63とするステップS302。以後、iを1ずつ増加させ、iが暗号化表A41の行数NとなるまでステップS302の処理を繰り返すステップS303~304。自然結合機能63bは、以上で得られた表A’および表Bを、表A’の列aの各iに関してd_b[i、a]が作る列と表Bの列bの各iに関してd_a[i、b]が作る列の値が等しい事を要求する等結合を行うステップS305。自然結合機能63bは最後に、等結合が完了した暗号化表A×B81を出力し、クライアント端末10に対して返信するステップS306。本実施形態の処理による効果以上で示した処理による効果について説明する。列暗号化装置が表Aの列aを鍵Kによって暗号化すると、i番目の要素m[i]は、以下の数11に示すe[a、i]、d[a、i]に置換される。暗号化表Aおよび暗号化表Bでは対応する列公開鍵が異なる。従って、暗号化表Aおよび暗号化表Bの各々に対応する列公開鍵をyおよびy’とすると、暗号化表Aおよび暗号化表Bで同一の平文mが含まれていた場合でも、これら二つの値が同じ表の同じ列に存在しなければ、この平文mは各々encK,y,mとencK,y’,mと暗号化され、両者は一致しない。従って、数11右辺の第1の要素の暗号文のみから、平文の同一性を判定することはできない。また、列識別子が一致してA,a=B,bとならない限り、数12で示される数11右辺の第2の要素も一致しないので、この第2の要素が同一の平文mを暗号化したものであるか否かを判別することは困難である。この判別には、DiffieHellman判別問題を解くことが必要であり、これは通常のコンピュータの計算能力で解を得るには数年~数十年程度の時間がかかる膨大な計算量を必要とするので現実的ではない。一方、暗号化表Aおよび暗号化表Bに対して自然結合を行う場合に、数8で示したように表結合鍵として暗号化表Aの列aの列秘密鍵x[a]と暗号化表Bの列bの列秘密鍵x[b]の比x[b]/x[a]が与えられたとすると、列aの第i番目の成分d[a,i]に関して数10で示した隠蔽比較値d’[b,i]を計算すると、以下の数13で示すようになる。従って、上記数13で示すm[i]は、以下の数14で示す暗号化表Bの列bの第j番目の成分の第二の要素d[b,j]におけるm[j]と等しいか否かを判別可能であるので、この判別結果に基づく暗号化表AおよびBの自然結合が可能となる。この動作には、冪乗算が必要であるが、この計算数は表Aの列aの要素数に等しい。即ち、本実施形態の動作によって、計算量が大幅に増加することはない。第1の実施形態の全体的な動作次に、上記の実施形態の全体的な動作について説明する。本実施形態に係る自然結合方法は、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号鍵をクライアント端末の記憶手段に予め記憶し、入力された第1の表のa列目のデータと第2の表のb列目のデータとを暗号鍵によってクライアント端末の記憶手段が暗号化して外部に出力し図4ステップS101~111、暗号化された第1および第2の表を暗号化データベースサーバのデータ受信部が受信して記憶し図6ステップS151~152、第1および第2の表の表識別子とa列目およびb列目の列識別子とから暗号鍵によって生成された列秘密鍵を含む表結合鍵をクライアント端末の暗号化表自然結合要求部が生成し図8ステップS201~203、暗号化された第1の表および第2の表をa列目およびb列目に関して自然結合することを要求する自然結合要求文に表結合鍵を含めてクライアント端末の暗号化表自然結合要求部が出力し図8ステップS204、暗号化された第1および第2の表に対して暗号化データベースサーバの暗号化表自然結合部が自然結合要求文に従って表結合鍵を適用して自然結合を実行し図10ステップS301~311、自然結合の結果を暗号化データベースサーバの暗号化表自然結合部がクライアント端末に返信する図10ステップS312。ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータであるクライアント端末10および暗号化データベースサーバ50に実行させるようにしてもよい。本プログラムは、非一時的な記録媒体、例えば、DVD、CD、フラッシュメモリ等に記録されてもよい。その場合、本プログラムは、記録媒体からコンピュータによって読み出され、実行される。この動作により、本実施形態は以下のような効果を奏する。本実施形態では、データベースサーバに記憶されたデータを暗号化し、異なる表にある要素は異なる値に暗号化されることで情報の漏洩を防ぐことができる一方で、データベースは必要な場合に表結合鍵を含む自然結合要求文をデータベースサーバに与えて、二つの表の自然結合を実行させることができる。本実施形態によれば、データベースシステム上の処理において頻繁に行われる処理である自然結合をデータを復号化せずに実行可能としたので、データベースシステムの利便性とセキュリティの保護とを両立させることが可能である。これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。上述した各々の実施形態について、その新規な技術内容の要点をまとめると、以下のようになる。なお、上記実施形態の一部または全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。付記1クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、前記クライアント端末が、暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶する記憶手段と、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって暗号化して外部に出力する列暗号化部と、暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文を出力すると共に、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵および前記群の生成子によって生成される列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力する暗号化表自然結合要求部とを備え、前記暗号化データベースサーバが、前記暗号化された第1および第2の表を受信して記憶するデータ受信部と、前記暗号化された第1および第2の表に対して前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースシステム。付記2前記クライアント端末の前記列暗号化部が、前記第1の表のa列目に対して、前記暗号鍵および前記第1の表の表識別子と前記a列目の列識別子から前記a列目の列秘密鍵x[a]を生成する列秘密鍵生成機能と、前記群の生成子から前記a列目の列秘密鍵に対応するa列目の列公開鍵を生成する列公開鍵生成機能と、前記第1の表のa列目の各成分と前記暗号鍵とから比較値を生成する比較値生成機能と、各々の前記比較値と前記列公開鍵から隠蔽比較値を生成する隠蔽比較値生成機能と、前記a列目のデータを前記暗号鍵によって暗号化して暗号文を生成する暗号化機能と、前記a列目のデータを前記暗号文および前記隠蔽比較値に置換して前記第1の表を暗号化してこの暗号化された前記第1の表を前記暗号化データベースサーバに送信する表更新機能とを有すると共に、前記列暗号化部が前記第2の表のb列目に対しても同様に列秘密鍵x[b]および列公開鍵を生成して、それらから前記比較値、前記隠蔽比較値、および暗号文を生成して前記第2の表を暗号化して前記暗号化データベースサーバに送信することを特徴とする、付記1に記載の暗号化データベースシステム。付記3前記クライアント端末の前記暗号化表自然結合要求部が、前記第1の表の表識別子と前記a列目の列識別子、前記第2の表の表識別子と前記b列目の列識別子、前記暗号鍵および前記群の生成子から表結合鍵を生成する表結合鍵生成機能と、前記第1の表の表識別子と前記a列目の列識別子、前記第2の表の表識別子と前記b列目の列識別子、および前記表結合鍵から前記自然結合要求文を出力して前記暗号化データベースサーバに送信する自然結合要求文出力機能とを有することを特徴とする、付記2に記載の暗号化データベースシステム。付記4前記表結合鍵が前記列秘密鍵x[a]と前記列秘密鍵x[b]との比を要素として含むことを特徴とする、付記3に記載の暗号化データベースシステム。付記5前記クライアント端末の前記暗号化表自然結合要求部が、前記列暗号化部と同一の列秘密鍵生成機能を備えることを特徴とする、付記3に記載の暗号化データベースシステム。付記6前記暗号化データベースサーバの前記暗号化表自然結合部が、前記暗号化された第1の表のa列目の隠蔽比較値から前記前記列秘密鍵x[a]と前記列秘密鍵x[b]との比の要素を用いて共通比較値を生成すると共に前記暗号化された第1の表のa列目の隠蔽比較値をこの共通比較値で置換する隠蔽比較値更新機能と、前記置換された第1の表を前記第2の表との間で前記自然結合要求文に従って前記a列目およびb列目に関して自然結合を実行してその結果を前記クライアント端末に返信する自然結合機能とを有することを特徴とする、付記4に記載の暗号化データベースシステム。付記7暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成するクライアント端末であって、暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶する記憶手段と、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって暗号化して外部に出力する列暗号化部と、暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文を出力すると共に、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵および前記群の生成子によって生成される列秘密鍵を含む表結合鍵を生成して前記自然結合要求文に含めて出力する暗号化表自然結合要求部とを備えることを特徴とするクライアント端末。付記8クライアント端末と相互に接続されて暗号化データベースシステムを構成する暗号化データベースサーバであって、前記暗号化された第1および第2の表を受信して記憶するデータ受信部と、前記暗号化された第1および第2の表に対して前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースサーバ。付記9クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号鍵および当該暗号鍵の要部をなす群の生成子を前記クライアント端末の記憶手段に予め記憶し、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって前記クライアント端末の記憶手段が暗号化して外部に出力し、前記暗号化された第1および第2の表を前記暗号化データベースサーバのデータ受信部が受信して記憶し、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵によって生成される列秘密鍵を含む表結合鍵を前記クライアント端末の暗号化表自然結合要求部が生成し、暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて前記クライアント端末の暗号化表自然結合要求部が出力し、前記暗号化された第1および第2の表に対して前記暗号化データベースサーバの暗号化表自然結合部が前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行し、前記自然結合の結果を前記暗号化データベースサーバの前記暗号化表自然結合部が前記クライアント端末に返信することを特徴とする自然結合方法。付記11暗号鍵および当該暗号鍵の要部をなす群の生成子を予め記憶しているクライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、前記クライアント端末が備えるコンピュータに、外部から入力される第1の表のa列目のデータと第2の表のb列目のデータとを前記暗号鍵および前記群の生成子によって暗号化して外部に出力する手順、前記第1および第2の表の表識別子と前記a列目およびb列目の列識別子とから前記暗号鍵によって生成される列秘密鍵を含む表結合鍵を生成する手順、および暗号化された前記第1の表および第2の表を前記a列目およびb列目に関して自然結合することを要求する自然結合要求文に前記表結合鍵を含めて出力する手順を実行させることを特徴とする自然結合プログラム。付記12クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、前記暗号化データベースサーバが備えるコンピュータに、暗号化された第1および第2の表を前記クライアント端末から受信して記憶する手順、前記暗号化された第1および第2の表に対して前記自然結合要求文に従って前記表結合鍵中の前記列秘密鍵を適用して前記自然結合を実行する手順、および前記自然結合の結果を前記クライアント端末に返信する手順を実行させることを特徴とする自然結合プログラム。"