"クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、前記クライアント端末が、暗号鍵および当該暗号鍵の要部をなす第1および第2の群の生成子を予め記憶する記憶手段と、外部から入力される第1の表の第1のラベルによって示される列のデータを前記暗号鍵および前記第1の群の生成子とによって暗号化すると共に、同じく外部から入力される第2の表の第2のラベルによって示される列のデータを前記暗号鍵および前記第2の群の生成子によって暗号化し、これら暗号化された第1および第2の表を外部に出力する列暗号化部と、前記暗号鍵と前記第1のラベルとから第1のラベル内鍵を生成すると共に、前記暗号鍵と前記第2のラベルとから第2のラベル内鍵を生成し、これら第1および第2のラベル内鍵を外部に出力するラベル内射影要求部と、前記暗号鍵と前記第1の群の生成子と前記第1および第2のラベル内鍵とから第1のラベル間射影鍵を生成すると共に、前記暗号鍵と前記第2の群の生成子と前記第1および第2のラベル内鍵とから第2のラベル間射影鍵を生成し、これら第1および第2のラベル間射影鍵を外部に出力するラベル間射影要求部とを備え、前記暗号化データベースサーバが、前記暗号化された第1および第2の表を受信して記憶すると共に、前記第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵とを受信するデータ受信部と、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成すると共に、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成するラベル内射影部と、前記第1のラベル内比較値に前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成すると共に、前記第2のラベル内比較値に前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成するラベル間射影部と、前記出力された第1および第2のラベル間比較値を利用して、前記暗号化された第1および第2の表に対する自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースシステム。前記列暗号化部が、前記秘密鍵と前記ラベルとからラベル間鍵を生成するラベル間鍵生成機能と、前記群の生成子と前記ラベル間射影鍵とから第一ラベル公開鍵を生成する第一ラベル公開鍵生成機能と、前記秘密鍵と前記列のデータとから単純比較値を生成する比較値生成機能と、前記第一ラベル公開鍵と前記単純比較値と前記ラベル間鍵とからラベル内比較値を生成する隠蔽比較値生成機能と、前記秘密鍵と前記ラベルとから前記ラベル内鍵を生成するラベル内鍵生成機能と、前記ラベル内鍵によって前記ラベル内比較値を暗号化すると同時に前記秘密鍵によって前記列のデータを暗号化する暗号化機能とを備えることを特徴とする、請求項1に記載の暗号化データベースシステム。前記ラベル内射影要求部が、前記秘密鍵と前記第1のラベルとから前記ラベル内鍵を生成するラベル内鍵生成機能を備えると共に、前記ラベル間射影要求部が、前記秘密鍵と前記第2のラベルとから前記ラベル間鍵を生成するラベル間射影鍵生成機能と、前記群の生成子と前記ラベル間鍵とから第二ラベル公開鍵を生成する第二ラベル公開鍵生成機能と、前記第1および第2のラベルと前記秘密鍵とから補間値を生成する補間値生成機能と、前記第二ラベル公開鍵と前記補間値とからラベル間射影鍵を生成する射影鍵生成機能とを備えることを特徴とする、請求項1に記載の暗号化データベースシステム。前記ラベル内射影部が、前記ラベル内鍵と前記暗号化された第1および第2の表の暗号化された列データから第1および第2のラベル内比較値を生成するラベル内比較値生成機能を備えると共に、前記ラベル間射影部が、前記ラベル間射影鍵と前記第1および第2のラベル内比較値とを双線形写像の入力として、その出力を各々前記第1および第2のラベル間比較値として出力するラベル間比較値生成機能を備えることを特徴とする、請求項1に記載の暗号化データベースシステム。暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成されるクライアント端末であって、暗号鍵および当該暗号鍵の要部をなす第1および第2の群の生成子を予め記憶する記憶手段と、外部から入力される第1の表の第1のラベルによって示される列のデータを前記暗号鍵および前記第1の群の生成子とによって暗号化すると共に、同じく外部から入力される第2の表の第2のラベルによって示される列のデータを前記暗号鍵および前記第2の群の生成子によって暗号化し、これら暗号化された第1および第2の表を外部に出力する列暗号化部と、前記暗号鍵と前記第1のラベルとから第1のラベル内鍵を生成すると共に、前記暗号鍵と前記第2のラベルとから第2のラベル内鍵を生成し、これら第1および第2のラベル内鍵を外部に出力するラベル内射影要求部と、前記暗号鍵と前記第1の群の生成子と前記第1および第2のラベル内鍵とから第1のラベル間射影鍵を生成すると共に、前記暗号鍵と前記第2の群の生成子と前記第1および第2のラベル内鍵とから第2のラベル間射影鍵を生成し、これら第1および第2のラベル間射影鍵を外部に出力するラベル間射影要求部とを備えることを特徴とするクライアント端末。クライアント端末と相互に接続されて暗号化データベースシステムを構成される暗号化データベースサーバであって、前記クライアント端末から送信される第1のラベルによって示される列が暗号化された第1の表および第2のラベルによって示される列が暗号化された第2の表を受信して記憶すると共に、前記クライアント端末から送信される第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵とを受信するデータ受信部と、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成すると共に、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成するラベル内射影部と、前記第1のラベル内比較値に前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成すると共に、前記第2のラベル内比較値に前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成するラベル間射影部と、前記出力された第1および第2のラベル間比較値を利用して、前記暗号化された第1および第2の表に対する自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースサーバ。クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、外部から入力される第1の表の第1のラベルによって示される列のデータを前記クライアント端末の列暗号化部があらかじめ記憶された暗号鍵および当該暗号鍵の要部をなす第1の群の生成子とによって暗号化して外部に出力し、外部から入力される第2の表の第2のラベルによって示される列のデータを前記クライアント端末の列暗号化部が前記暗号鍵およびあらかじめ記憶された前記暗号鍵の要部をなす第2の群の生成子とによって暗号化して外部に出力し、前記暗号鍵と前記第1のラベルとから前記クライアント端末のラベル内射影要求部が第1のラベル内鍵を生成して外部に出力し、前記暗号鍵と前記第2のラベルとから前記クライアント端末のラベル内射影要求部が第2のラベル内鍵を生成して外部に出力し、前記暗号鍵と前記第1の群の生成子と、前記第1および第2のラベル内鍵から前記クライアント端末のラベル間射影要求部が第1のラベル間射影鍵を生成して外部に出力し、前記暗号鍵と前記第2の群の生成子と、前記第1および第2のラベル内鍵から前記クライアント端末のラベル間射影要求部が第2のラベル間射影鍵を生成して外部に出力し、前記暗号化された第1および第2の表、前記第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵を前記暗号化データベースサーバのデータ受信部が受信し、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記暗号化データベースサーバのラベル内射影部が前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成し、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記暗号化データベースサーバのラベル内射影部が前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成し、前記第1のラベル内比較値に前記暗号化データベースサーバのラベル間射影部が前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成し、前記第2のラベル内比較値に前記暗号化データベースサーバのラベル間射影部が前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成し、前記第1および第2のラベル間比較値を利用して、前記暗号化データベースサーバの暗号化表自然結合部が前記暗号化された第1および第2の表に対する自然結合を実行することを特徴とする暗号化表の自然結合方法。クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、前記クライアント端末が備えているコンピュータに、外部から入力される第1の表の第1のラベルによって示される列のデータをあらかじめ記憶された暗号鍵および当該暗号鍵の要部をなす第1の群の生成子とによって暗号化して外部に出力する手順、外部から入力される第2の表の第2のラベルによって示される列のデータを前記暗号鍵およびあらかじめ記憶された前記暗号鍵の要部をなす第2の群の生成子とによって暗号化して外部に出力する手順、前記暗号鍵と前記第1のラベルとから第1のラベル内鍵を生成して外部に出力する手順、前記暗号鍵と前記第2のラベルとから第2のラベル内鍵を生成して外部に出力する手順、前記暗号鍵と前記第1の群の生成子と、前記第1および第2のラベル内鍵から第1のラベル間射影鍵を生成して外部に出力する手順、および前記暗号鍵と前記第2の群の生成子と、前記第1および第2のラベル内鍵から第2のラベル間射影鍵を生成して外部に出力する手順を実行させることを特徴とする暗号化表の自然結合プログラム。クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号化データベースサーバが備えているコンピュータに、前記暗号化された第1および第2の表、前記第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵を受信する手順、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成する手順、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成する手順、前記第1のラベル内比較値に前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成する手順、前記第2のラベル内比較値に前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成する手順、および前記第1および第2のラベル間比較値を利用して、前記暗号化された第1および第2の表に対する自然結合を実行する手順を実行させることを特徴とする暗号化表の自然結合プログラム。データベースは、大量のデータの中から単に必要なデータを抽出するだけではなく、SQLStructuredQueryLanguageコマンドなどによって複数の表を結合することが頻繁に行われる。暗号化されたデータに対しても、この表を自然結合する演算を、セキュリティを損なうことなく容易に行えることが当然望まれる。しかしながら、前述のように暗号鍵keyは各々の表に対して固有に与えられるものであるので、異なる表には異なる暗号鍵が与えられることになる。従って、異なる表にある同一の値を持つデータは、異なる暗号鍵によって暗号化されると異なるデータとなる。このため、図18で示した暗号化データベース管理システム901で、列暗号化部921によって暗号化されたデータをキーとして異なる表を結合する演算を行うためには、前述したように該データを一度復号化してから結合する必要がある。このことをより具体的に説明する。図24は、図18で示した暗号化データベース管理装置901で、複数の暗号化表A941および暗号化表B942に対して自然結合の演算を行う場合の例についての説明図である。図24aは暗号化表A941を、図24bは暗号化表B942を、図24cは表A×B981について各々示す。暗号化表A941は、第1列932aをユーザ名、第2列932bをクレジットカード番号として、各ユーザ名に対応するカード番号の対応関係を示す。そして第2列941bは、秘密鍵key931aによって暗号化されている。暗号化表B942は、第1列933aをクレジットカード番号、第2列933bをクレジットカード有効期限として、各カードの有効期限について示している。そして第1列942aは、秘密鍵key’931bによって暗号化されている。ここで、該データベースの管理者がユーザ名とクレジットカード有効期限との対応について知りたい場合には、暗号化表自然結合要求部922によって、暗号化表A941および暗号化表B942を列941bおよび942aのクレジットカード番号をキーとして自然結合するよう自然結合命令文971を発行する。この処理によって、第1列981aユーザ名、第2列981bクレジットカード番号、第3列981cクレジットカード有効期限という3列を持つ暗号化表A×B981が得られることが期待される。しかしながら、暗号化表A941および暗号化表B942は、各々異なる暗号鍵によって暗号化されているので、平文の段階では同一のデータであっても、異なる暗号鍵によって異なるデータとなる。従って、暗号化表自然結合部963は、暗号化されたデータをそのまま自然結合のキーとすることはできない。この処理を行うためには、図21に示した復号化機能963aによって列941bおよび942aを復号化する処理が必要となる。この処理には、暗号化表A941および暗号化表B942に対する秘密鍵key931aおよび秘密鍵key’931bに各々対応する公開鍵pkey972aおよび公開鍵pkey’972bが必要である。これらの公開鍵を利用すれば、この処理を行うために列941bおよび942aを復号化することは可能ではある。しかしながら、この処理を行っている間は復号化された平文のデータが装置に記憶されることになるので、その間にその平文のデータが漏洩する危険性を否定することはできない。図25は、上述の問題を解決するため、key=key’、即ち同一の暗号鍵keyを利用して暗号化された暗号化表C1001および暗号化表D1002に対して自然結合の演算を行う例についての説明図である。図25aは暗号化表C1001を、図25bは暗号化表D1002を、図25cは暗号化表C×D1003について各々示す。この暗号鍵keyは、公開鍵方式のものであっても、共通鍵方式のものであってもよい。暗号化表C1001は、第1列1001aをユーザ名、第2列1001bをクレジットカード番号として、各ユーザ名に対応するカード番号の対応関係を示す。そして第2列1001bは、暗号鍵keyによって暗号化されている。暗号化表D1002は、第1列1002aをクレジットカード番号、第2列1002bをブラックリスト登録日として、各カードの有効期限について示している。そして第1列1002aは、表C1001と同一の暗号鍵keyによって暗号化されている。暗号鍵keyが同一であれば、暗号化表C1001の第2列1001bと暗号化表D1002の第1列1002aとで、暗号化前のデータが同一であれば、暗号化された後も同一データとなるので、復号化機能963aを利用しなくて暗号化表C1001および暗号化表D1002をそのまま自然結合して暗号化表C×D1003を得ることが可能である。しかしながら、このことは同時に、暗号鍵keyを持たない不当なユーザであっても、暗号化されたデータをキーとして暗号化表C1001および暗号化表D1002を自然結合して暗号化表C×D1003を得る処理ができてしまうことを意味する。このようなことは、暗号化データベースの管理において、望ましいことではない。即ち、正当な暗号鍵を持つユーザであれば、暗号化されたデータを復号化する処理を行わなくとも、暗号化されたデータをキーとして複数の表を自然結合することが可能で、かつ正当な暗号鍵を持たない不当なユーザには暗号化されたデータをキーとする自然結合ができない、そのような特徴を持つ暗号化データベース管理装置が求められている。かつ、データベースは膨大な量のデータを扱うものであるので、この処理を行うことによる計算量の大幅な増大も抑制されなければならない。前述の各特許文献および非特許文献は、いずれもこの問題を解決することを目的とはしていないので、当然ながらこの問題を解決しうる技術は記載されていない。本発明の目的は、暗号化されたデータベースの複数の表を、データの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータをキーとして自然結合することを可能とする暗号化データベース管理システム、クライアントおよびサーバ、自然結合方法およびプログラムを提供することにある。上記目的を達成するため、本発明に係る暗号化データベース管理システムは、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、クライアント端末が、暗号鍵および当該暗号鍵の要部をなす第1および第2の群の生成子を予め記憶する記憶手段と、外部から入力される第1の表の第1のラベルによって示される列のデータを暗号鍵および第1の群の生成子とによって暗号化すると共に、同じく外部から入力される第2の表の第2のラベルによって示される列のデータを暗号鍵および第2の群の生成子によって暗号化し、これら暗号化された第1および第2の表を外部に出力する列暗号化部と、暗号鍵と第1のラベルとから第1のラベル内鍵を生成すると共に、暗号鍵と第2のラベルとから第2のラベル内鍵を生成し、これら第1および第2のラベル内鍵を外部に出力するラベル内射影要求部と、暗号鍵と第1の群の生成子と第1および第2のラベル内鍵とから第1のラベル間射影鍵を生成すると共に、暗号鍵と第2の群の生成子と第1および第2のラベル内鍵とから第2のラベル間射影鍵を生成し、これら第1および第2のラベル間射影鍵を外部に出力するラベル間射影要求部とを備え、暗号化データベースサーバが、暗号化された第1および第2の表を受信して記憶すると共に、第1および第2のラベル内鍵と第1および第2のラベル間射影鍵とを受信するデータ受信部と、暗号化された第1の表の第1のラベルによって示される列のデータに第1のラベルと第1のラベル内鍵とを作用させて第1のラベル内比較値を生成すると共に、暗号化された第2の表の第2のラベルによって示される列のデータに第2のラベルと第2のラベル内鍵とを作用させて第2のラベル内比較値を生成するラベル内射影部と、第1のラベル内比較値に第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成すると共に、第2のラベル内比較値に第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成するラベル間射影部と、出力された第1および第2のラベル間比較値を利用して、暗号化された第1および第2の表に対する自然結合を実行する暗号化表自然結合部とを備えることを特徴とする。上記目的を達成するため、本発明に係るクライアント端末は、暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成されるクライアント端末であって、暗号鍵および当該暗号鍵の要部をなす第1および第2の群の生成子を予め記憶する記憶手段と、外部から入力される第1の表の第1のラベルによって示される列のデータを暗号鍵および第1の群の生成子とによって暗号化すると共に、同じく外部から入力される第2の表の第2のラベルによって示される列のデータを暗号鍵および第2の群の生成子によって暗号化し、これら暗号化された第1および第2の表を外部に出力する列暗号化部と、暗号鍵と第1のラベルとから第1のラベル内鍵を生成すると共に、暗号鍵と第2のラベルとから第2のラベル内鍵を生成し、これら第1および第2のラベル内鍵を外部に出力するラベル内射影要求部と、暗号鍵と第1の群の生成子と第1および第2のラベル内鍵とから第1のラベル間射影鍵を生成すると共に、暗号鍵と第2の群の生成子と第1および第2のラベル内鍵とから第2のラベル間射影鍵を生成し、これら第1および第2のラベル間射影鍵を外部に出力するラベル間射影要求部とを備えることを特徴とする。上記目的を達成するため、本発明に係る暗号化データベースサーバは、クライアント端末と相互に接続されて暗号化データベースシステムを構成される暗号化データベースサーバであって、クライアント端末から送信される第1のラベルによって示される列が暗号化された第1の表および第2のラベルによって示される列が暗号化された第2の表を受信して記憶すると共に、クライアント端末から送信される第1および第2のラベル内鍵と第1および第2のラベル間射影鍵とを受信するデータ受信部と、暗号化された第1の表の第1のラベルによって示される列のデータに第1のラベルと第1のラベル内鍵とを作用させて第1のラベル内比較値を生成すると共に、暗号化された第2の表の第2のラベルによって示される列のデータに第2のラベルと第2のラベル内鍵とを作用させて第2のラベル内比較値を生成するラベル内射影部と、第1のラベル内比較値に第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成すると共に、第2のラベル内比較値に第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成するラベル間射影部と、出力された第1および第2のラベル間比較値を利用して、暗号化された第1および第2の表に対する自然結合を実行する暗号化表自然結合部とを備えることを特徴とする。上記目的を達成するため、本発明に係る自然結合方法は、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、外部から入力される第1の表の第1のラベルによって示される列のデータをクライアント端末の列暗号化部があらかじめ記憶された暗号鍵および当該暗号鍵の要部をなす第1の群の生成子とによって暗号化して外部に出力し、外部から入力される第2の表の第2のラベルによって示される列のデータをクライアント端末の列暗号化部が暗号鍵および暗号鍵の要部をなすあらかじめ記憶された第2の群の生成子とによって暗号化して外部に出力し、暗号鍵と第1のラベルとからクライアント端末のラベル内射影要求部が第1のラベル内鍵を生成して外部に出力し、暗号鍵と第2のラベルとからクライアント端末のラベル内射影要求部が第2のラベル内鍵を生成して外部に出力し、暗号鍵と第1の群の生成子と、第1および第2のラベル内鍵からクライアント端末のラベル間射影要求部が第1のラベル間射影鍵を生成して外部に出力し、暗号鍵と第2の群の生成子と、第1および第2のラベル内鍵からクライアント端末のラベル間射影要求部が第2のラベル間射影鍵を生成して外部に出力し、暗号化された第1および第2の表、第1および第2のラベル内鍵と第1および第2のラベル間射影鍵を暗号化データベースサーバのデータ受信部が受信し、暗号化された第1の表の第1のラベルによって示される列のデータに暗号化データベースサーバのラベル内射影部が第1のラベルと第1のラベル内鍵とを作用させて第1のラベル内比較値を生成し、暗号化された第2の表の第2のラベルによって示される列のデータに暗号化データベースサーバのラベル内射影部が第2のラベルと第2のラベル内鍵とを作用させて第2のラベル内比較値を生成し、第1のラベル内比較値に暗号化データベースサーバのラベル間射影部が第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成し、第2のラベル内比較値に暗号化データベースサーバのラベル間射影部が第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成し、第1および第2のラベル間比較値を利用して、暗号化データベースサーバの暗号化表自然結合部が暗号化された第1および第2の表に対する自然結合を実行することを特徴とする。上記目的を達成するため、本発明に係る自然結合プログラムは、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、クライアント端末が備えているコンピュータに、外部から入力される第1の表の第1のラベルによって示される列のデータをあらかじめ記憶された暗号鍵および当該暗号鍵の要部をなす第1の群の生成子とによって暗号化して外部に出力する手順、外部から入力される第2の表の第2のラベルによって示される列のデータを暗号鍵およびあらかじめ記憶された暗号鍵の要部をなす第2の群の生成子とによって暗号化して外部に出力する手順、暗号鍵と第1のラベルとから第1のラベル内鍵を生成して外部に出力する手順、暗号鍵と第2のラベルとから第2のラベル内鍵を生成して外部に出力する手順、暗号鍵と第1の群の生成子と、第1および第2のラベル内鍵から第1のラベル間射影鍵を生成して外部に出力する手順、および暗号鍵と第2の群の生成子と、第1および第2のラベル内鍵から第2のラベル間射影鍵を生成して外部に出力する手順を実行させることを特徴とする。上記目的を達成するため、本発明に係る他の自然結合プログラムは、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号化データベースサーバが備えているコンピュータに、暗号化された第1および第2の表、第1および第2のラベル内鍵と第1および第2のラベル間射影鍵を受信する手順、暗号化された第1の表の第1のラベルによって示される列のデータに第1のラベルと第1のラベル内鍵とを作用させて第1のラベル内比較値を生成する手順、暗号化された第2の表の第2のラベルによって示される列のデータに第2のラベルと第2のラベル内鍵とを作用させて第2のラベル内比較値を生成する手順、第1のラベル内比較値に第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成する手順、第2のラベル内比較値に第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成する手順、および第1および第2のラベル間比較値を利用して、暗号化された第1および第2の表に対する自然結合を実行する手順を実行させることを特徴とする。本発明は、上述したようにクライアント端末の側で暗号鍵と結合対象となる列を示すラベルからラベル内鍵とラベル間鍵とを生成して暗号化データベースサーバに送信するように構成したので、このラベル内鍵とラベル間鍵とを受信した暗号化データベースサーバのみが、第1の表および第2の表において指定された列のデータが等しいか否かを判断可能となる。これによって、暗号化されたデータベースの複数の表を、データの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータをキーとして自然結合することが可能であるという優れた特徴を持つ暗号化データベース管理システム、クライアントおよびサーバ、自然結合方法およびプログラムを提供することができる。第1の実施形態以下、本発明の第1の実施形態の構成について添付図1、4、7、9、11、13、15に基づいて説明する。最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。本実施形態に係る暗号化データベースシステム暗号化データベース管理システム1は、クライアント端末暗号化データベースクライアント10と暗号化データベースサーバ50とが相互に接続されて構成される暗号化データベースシステムである。クライアント端末暗号化データベースクライアント10は、暗号鍵秘密鍵31および第1および第2の群の生成子32a~bを予め記憶する記憶手段12と、外部から入力される第1の表表A35の第1のラベルラベル33aによって示される列のデータを暗号鍵および第1の群の生成子とによって暗号化し、同じく外部から入力される第2の表表B36の第2のラベルラベル33bによって示される列のデータを暗号鍵および第2の群の生成子によって暗号化してこれら暗号化された第1および第2の表を外部に出力する列暗号化部21と、暗号鍵と第1のラベルとから第1のラベル内鍵を生成し、暗号鍵と第2のラベルとから第2のラベル内鍵を生成してこれら第1および第2のラベル内鍵を外部に出力するラベル内射影要求部22と、暗号鍵と第1の群の生成子と、第1および第2のラベル内鍵から第1のラベル間射影鍵を生成し、暗号鍵と第2の群の生成子と、第1および第2のラベル内鍵から第2のラベル間射影鍵を生成してこれら第1および第2のラベル間射影鍵を外部に出力するラベル間射影要求部23とを備え、暗号化データベースサーバ50が、暗号化された第1および第2の表を受信して記憶し、第1および第2のラベル内鍵と第1および第2のラベル間射影鍵とを受信するデータ受信部64と、暗号化された第1の表の第1のラベルによって示される列のデータに第1のラベルと第1のラベル内鍵とを作用させて第1のラベル内比較値を生成し、暗号化された第2の表の第2のラベルによって示される列のデータに第2のラベルと第2のラベル内鍵とを作用させて第2のラベル内比較値を生成するラベル内射影部61と、第1のラベル内比較値に第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成し、第2のラベル内比較値に第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成するラベル間射影部62と、出力された第1および第2のラベル間比較値を利用して、暗号化された第1および第2の表に対する自然結合を実行する暗号化表自然結合部63とを備える。ここで列暗号化部21は、秘密鍵とラベルとからラベル間鍵を生成するラベル間鍵生成機能21bと、群の生成子とラベル間射影鍵とから第一ラベル公開鍵を生成する第一ラベル公開鍵生成機能21cと、秘密鍵と列のデータとから単純比較値を生成する比較値生成機能21dと、第一ラベル公開鍵と単純比較値とラベル間鍵とからラベル内比較値を生成する隠蔽比較値生成機能21eと、秘密鍵とラベルとからラベル内鍵を生成するラベル内鍵生成機能21aと、ラベル内鍵によってラベル内比較値を暗号化すると同時に秘密鍵によって列のデータを暗号化する暗号化機能21fとを備える。また、ラベル内射影要求部22が、秘密鍵と第1のラベルとからラベル内鍵を生成するラベル内鍵生成機能を備えると共に、ラベル間射影要求部23が、秘密鍵と第2のラベルとからラベル間鍵を生成するラベル間射影鍵生成機能23aと、群の生成子とラベル間鍵とから第二ラベル公開鍵を生成する第二ラベル公開鍵生成機能23bと、第1および第2のラベルと秘密鍵とから補間値を生成する補間値生成機能23cと、第二ラベル公開鍵と補間値とからラベル間射影鍵を生成する射影鍵生成機能23dとを備える。そしてラベル内射影部61が、ラベル内鍵と暗号化された第1および第2の表の暗号化された列データから第1および第2のラベル内比較値を生成するラベル内比較値生成機能61aを備えると共に、ラベル間射影部62が、ラベル間射影鍵と第1および第2のラベル内比較値とを双線形写像の入力として、その出力を各々第1および第2のラベル間比較値として出力するラベル間比較値生成機能62aを備える。この構成を備えることにより、暗号化データベース管理システム1はデータの各要素を復号化する処理を行わず、かつ計算量を大幅に増大させることもなく、暗号化されたデータをキーとして自然結合することが可能となる。以下、これをより詳細に説明する。記号などの定義まず、本明細書で使用する記号および用語、そしてそれらの定義について説明する。本明細書の数式以外の行ではAに上付き添字BAのB乗などをA^B、Aに下付き添字BをA_Bと表すことにする。pは素数である。G_1、G_2、G_Tは各々、位数がpの巡回群である。pairは、G_1×G_2からG_Tへの双線形写像である。σはG_2からG_1への準同型写像である。G_1としては、その上でのディフィヘルマンDiffieHellman判別問題を解くことが困難である群が想定される。例えば、超特異でない楕円曲線で双線形写像を持つものが、このような群に該当する。g_1はG_1の、g_2はG_2の各々生成元であり、かつσg_2=g_1である。Hashは、任意長の文字列からencの鍵空間への写像であり、暗号学的ハッシュ関数等などが想定される。HashZは、任意長の文字列からZ/pZへの写像であり、暗号学的ハッシュ関数等などが想定される。HashGは、任意長の文字列からG_1への写像であり、暗号学的ハッシュ関数等などが想定される。encは、鍵とイニシャルベクター初期ベクトルと平文とを入力として暗号文を出力とする暗号化関数である。decは、鍵とイニシャルベクターと暗号文とを入力として平文を出力とする復号化関数である。即ち、秘密鍵とこれに対応する公開鍵、イニシャルベクター、平文、暗号文を各々key、pkey、iv、m、eとすると、以下の数1に示す関係で表される。ここで、秘密鍵keyとこれに対応する公開鍵pkeyは、公開鍵暗号方式の公開鍵と秘密鍵の対である。公開鍵暗号方式で、秘密鍵keyを使用して暗号化された暗号文は、この秘密鍵に対応する公開鍵pkey以外で復号化して平文を得ることはできない。また、公開鍵pkeyを使用して暗号化された暗号文は、秘密鍵key以外で復号化して平文を得ることはできない。データベースの各表は、各列ごとにその属する表の中で自らを一意的に識別するラベルを持つ。データベースの各表の各列を取り出したものを列ベクトルという。データベースの表Aと表Bとを、表Aの列aの要素と表Bの列bの要素が等しいという条件によって等結合することを、表Aと表Bを表Aの列aと表Bの列bに関して自然結合するという。ただし、この等結合を行う際、重複する列は削除される。機器の構成図1は、本発明に係る暗号化データベース管理システム1の構成を示す説明図である。暗号化データベース管理システム1は、暗号化データベースクライアント10と、暗号化データベースサーバ50と、別のクライアント100とが、LANLocalAreaNetworkなどを介して相互に接続されて構成される。暗号化データベースクライアント10は、一般的なコンピュータ装置としての構成を備える。即ち、暗号化データベースクライアント10は、コンピュータプログラムを実行する主体となる主演算制御手段CPUCentralProcessingUnit11と、データを記憶する記憶手段12と、ユーザからの操作を受け付ける入力手段13と、ユーザに処理結果を提示する出力手段14と、他のコンピュータとのデータ通信を行う通信手段15とを備える。主演算制御手段11では、ユーザからの操作命令に応じて、暗号化部21、ラベル内射影要求部22、およびラベル間射影要求部23が、各々コンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。また、記憶手段12には以後に説明する処理で使用する秘密鍵key31と、群の生成子32a~bとが記憶されている。そして入力手段13には、自然結合の対象となる表A35および表B36と、自然結合の対象となる表および列を識別するラベル33a~bが入力される。ここで、群の生成子32a~b、ラベル33a~bの各々で、表A35に対応するものを群の生成子32a、ラベル33aといい、表B36に対応するものを群の生成子32b、ラベル33bという。暗号化データベースサーバ50もまた、一般的なコンピュータ装置としての構成を備える。即ち、暗号化データベースサーバ50は、コンピュータプログラムを実行する主体となる主演算制御手段CPUCentralProcessingUnit51と、データを記憶する記憶手段52と、他のコンピュータとのデータ通信を行う通信手段53とを備える。主演算制御手段51では、暗号化データベースクライアント10からの操作命令に応じて、ラベル内射影部61、ラベル間射影部62、暗号化表自然結合部63と、データ受信部64とがコンピュータプログラムとして後述するそれぞれの機能を実行されるように構成されている。また、記憶手段52にはデータ受信部64が暗号化データベースクライアント10から受信した、各々表A35および表B36を暗号化した暗号化表A37および暗号化表B38が記憶される。ここで、暗号化データベースクライアント10で使用される暗号鍵としては、暗号化と復号化で共通の鍵を使用する共通鍵を使用することもできるが、セキュリティ上の観点から公開鍵暗号方式の秘密鍵を使用することがより望ましいので、本実施形態では秘密鍵key31を使用する。この秘密鍵key31は、暗号化データベースクライアント10から他の装置に向けて送信されることはない。秘密鍵key31に対応する公開鍵pkey131は、暗号化データベースクライアント10から別のクライアント100に向けてのみ送付され、暗号化データベースサーバ50には送付されない。別のクライアント100は、ハードウェア的には暗号化データベースクライアント10と同様に一般的なコンピュータ装置としての構成、即ち主演算制御手段101と、記憶手段102と、通信手段103とを備えるが、主演算制御手段101で復号化部121が動作する。復号化部121は、後述するように暗号化データベースクライアント10の列暗号化部21で暗号化されたデータを、秘密鍵key31に対応する公開鍵pkey131を用いて復号化する。公開鍵pkey131は、暗号化データベースクライアント10から予め送付され、記憶手段102に記憶される。なお、物理的なコンピュータ装置の区分については、この例の通りに従う必要は特にない。たとえば、列暗号化部21、ラベル内射影要求部22、およびラベル内射影要求部23を、各々異なるコンピュータで動作させてもよい。また、列暗号化部21、ラベル内射影要求部22、ラベル内射影要求部23と、ラベル内射影部61、ラベル間射影部62、暗号化表自然結合部63、データ受信部64とを全て同一のコンピュータで動作させてもよい。図2は、図1に示した表A35および表B36について詳しく説明する説明図である。図2aは表A35を、図2bは表B36について各々示す。表A35で、自然結合の対象とされる列にはラベル33a=L[1]が与えられている。同様に、表B36で、自然結合の対象とされる列には、ラベル33b=L[2]が与えられている。ここでいうラベルとは、特定の表の特定の列を一意的に識別しうるデータである。ここでは、表A35で暗号化の対象かつラベル33aで示される列の列データ34a=ma[i]iは1≦i≦Nの自然数とする。また、表B36で暗号化の対象かつラベル33bで示される列の列データ34b=mb[j]jは1≦j≦Mの自然数とする。暗号化部図3は、図1に示した暗号化データベースクライアント10の、暗号化装置としてのより詳しい構成を示す説明図である。暗号化データベースクライアント10は、主演算制御手段11で暗号化部21が動作することによって、表Aの列aを暗号化する暗号化装置として機能する。暗号化部21は、ラベル内鍵生成機能21a、ラベル間鍵生成機能21b、第一ラベル公開鍵生成機能21c、比較値生成機能21d、隠蔽比較値生成機能21e、暗号化機能21f、乱数生成機能21gとを備える。これら各機能の詳細については後述する。暗号化部21への入力データとして、記憶手段12には秘密鍵key31および群の生成子g_132aが記憶され、図2に示した表A35およびラベル33a=L[1]は入力手段13から入力される。ただし、図3では表A35に対する処理だけを説明するので、表B36およびこれに関連する要素については図示しない。このため、ラベル33a=L[1]については、表B36の自然結合の対象とされる列に対して与えられたラベル33b=L[2]について言及する必要がある場合を除いて、単にラベル33a=Lという。以後の図においても同様である。図4は、図3に示した暗号化部21の処理について示すフローチャートである。ラベル間鍵生成機能21bは、秘密鍵31=keyおよびラベル33a=Lから、以下に示す数2の処理でラベル間鍵41a=x[L]を算出するステップS101。ここでHashZ関数の第一要素secretは、処理の種類を識別するための任意の文字列である。以後の数式で使用されるHashZ関数においても同様である。これに引き続いて、第一ラベル公開鍵生成機能21cは、秘密鍵31=key、群の生成子32a=g_1、およびラベル33a=Lから、以下に示す数3の処理で第一ラベル公開鍵41b=g[L]を算出するステップS102。i=1に初期設定してステップS103、乱数生成機能21gは、Z/qZからランダムに乱数イニシャルベクター41g=iv[1]およびiv[2]を生成するステップS104。そして、比較値生成機能21dが、秘密鍵31=keyおよび列データ34a=mから、以下に示す数4の処理で単純比較値41c=f[m]を算出するステップS105。以後図4のフローチャートでは、i行目の列データ34a=ma[i]を、単に列データ34a=mと表記する。これに引き続いて、隠蔽比較値生成機能21eが、ラベル間鍵41a、第一ラベル公開鍵41b、および単純比較値41cから、以下に示す数5の処理でラベル内比較値41d=dを算出するステップS106。以上の処理と並行して、ラベル内鍵生成機能21aが、秘密鍵31=keyおよびラベル33a=Lから、以下に示す数6の処理でラベル内鍵41e=key[L]を算出するステップS107。そして最後に、暗号化機能21fが、秘密鍵31=key、列データ34a=m、ラベル内比較値41d、および前述の乱数41g=iv[1]およびiv[2]から、以下に示す数7の処理で暗号文41f=e[i]:=e[1],e[2],e[3],e[4]を算出するステップS108。暗号化部21は、iの値が表A35の全行数Nに到達したか否かを判断しステップS109、到達したら処理の完了した暗号化表A37を出力し、通信手段15を介して暗号化データベースサーバ50に送信してステップS111処理を終了する。iの値がNに到達していなければ、iの値を1してステップS110ステップS103~108の処理を繰り返す。そして、暗号化部21が暗号化表A37を出力すると同時に、暗号化機能21fがラベル33a=Lを記憶手段12に記憶する。図5は、図4に示した処理によって暗号化が完了した暗号化表A37および暗号化表B38について示す説明図である。図5aは暗号化表A37を、図5bは暗号化表B38について各々示す。暗号化表A37は、列データ34a=ma[i]の各々が、数7で示す各々の要素を持つ暗号文41f39a=ea[i]に置換されている。暗号化表B38も同様に、列データ39b=mb[j]の各々が、数7で示す各々の要素を持つ暗号文41f39b=eb[j]に置換されている。図6は、暗号化データベースサーバ50のデータ受信部64が暗号化表A37を記憶する動作について示すフローチャートである。データ受信部64は、通信手段53を介して受信したこの暗号化表A37をステップS141、記憶手段52に記憶するステップS142。同様に、暗号化表B38についても受信して記憶手段52に記憶する。復号化部図7は、図1に示した別のクライアント100の、復号化装置としてのより詳しい構成を示す説明図である。別のクライアント100は、主演算制御手段11で復号化部121が動作することによって、暗号化表A37の暗号文43a=ea[i]を復号化する復号化装置として機能する。図8は、図7に示した復号化部121の処理について示すフローチャートである。復号化部121への入力データとして、記憶手段102には秘密鍵31=key[L]に対応する公開鍵131=pkey[L]が記憶され、数7に示した暗号文41f39aの後半部=e[3],e[4]は通信手段103を経由して入力される。復号化部121は、i=1と初期設定した後ステップS151、これらの入力データから、以下に示す数8の処理で平文の列データ34a=mを算出する処理をステップS152i=Nとなるまで全ての行に対してくり返しステップS153~4、これを出力するステップS155。ラベル内射影要求部図9は、図1に示した暗号化データベースクライアント10の、ラベル内射影要求装置としてのより詳しい構成を示す説明図である。暗号化データベースクライアント10は、主演算制御手段11でラベル内射影要求部22が動作することによって、同一のラベルの元に暗号化された平文の同一性を比較することを要求する要求文を生成して暗号化データベースサーバ50に送信するためのラベル内射影要求装置として機能する。図10は、図9に示したラベル内射影要求部22の処理について示すフローチャートである。ラベル内射影要求部22への入力データとして、記憶手段12には秘密鍵key31およびラベル33a=LL[1]が記憶されている。なお、ラベル内射影要求部22は、図3で示した暗号化部21のラベル内鍵生成機能21aと同一の機能を有するので、プログラム内の同一モジュールを共用することができる。ラベル内射影要求部22は、これらの入力データから、以下に示す数9の処理で、第1のラベル内鍵41e=key[L]を算出しステップS201、これを暗号化データベースサーバ50に向けて出力するステップS202。ここで数9のHash関数の第一要素labelkeyは、処理の種類を識別するための任意の文字列である。ラベル内射影要求部22はこれと同様に、秘密鍵key31、ラベル33b=LL[2]から、第2のラベル内鍵を算出し、これも暗号化データベースサーバ50に向けて出力する。ラベル間射影要求部図11は、図1に示した暗号化データベースクライアント10の、ラベル間射影要求装置としてのより詳しい構成を示す説明図である。暗号化データベースクライアント10は、主演算制御手段11でラベル間射影要求部23が動作することによって、異なるラベルの元に暗号化された平文の同一性を比較することを要求する要求文を生成して暗号化データベースサーバ50に送信するためのラベル間射影要求装置として機能する。ラベル間射影要求部23は、ラベル間射影鍵生成機能23a、第二ラベル公開鍵生成機能23b、補間値生成機能23c、射影鍵生成機能23dを備える。これら各機能の詳細については後述する。ラベル間射影要求部23への入力データとして、記憶手段12には秘密鍵key31、群の生成子g_132a、ラベル33a=L[1]およびラベル33b=L[2]が記憶されている。図12は、図11に示したラベル間射影要求部23の処理について示すフローチャートである。ラベル間射影鍵生成機能23aは、秘密鍵31=keyおよびラベル33a=L[1]から、以下に示す数10の処理でラベル間鍵41a=x[L[2]]を算出するステップS251。なお、ラベル間射影鍵生成機能23aは、図3で示した暗号化部21のラベル間鍵生成機能21bと同一の機能を有するので、プログラム内の同一モジュールを共用することができる。これに続いて、第二ラベル公開鍵生成機能23bは、秘密鍵31=key、群の生成子32a=g_1、およびラベル33a=L[1]から、以下に示す数11の処理で第二ラベル公開鍵42a=q[L[2]]を算出するステップS252。これに続いて、補間値生成機能23cは、秘密鍵31=key、ラベル33a=L[1]およびラベル33b=L[2]から、以下に示す数12の処理で補間値42b=p{L[1],L[2]}を算出するステップS253。ここで、{L[1],L[2]}は、L[1]とL[2]とを辞書順序で並べ替えた文字列であり、{L[1],L[2]}={L[2],L[1]}である。これに続いて、射影鍵生成機能23dは、第二ラベル公開鍵42a=q[L[2]]、ラベル間鍵41a=x[L[1]]および補間値42b=p{L[1],L[2]}から、以下に示す数13の処理でラベル間射影鍵42c=P第1のラベル間射影鍵P[1]を算出しステップS254、これを暗号化データベースサーバ50に向けて出力するステップS255。ラベル間射影要求部23はこれと同様に、秘密鍵key31、群の生成子g_232b、ラベル33b=L[2]およびラベル33a=L[1]から、第2のラベル間射影鍵P[2]を算出し、これも暗号化データベースサーバ50に向けて出力する。ラベル内射影部図13は、図1に示した暗号化データベースサーバ50の、ラベル内射影装置としてのより詳しい構成を示す説明図である。暗号化データベースサーバ50は、主演算制御手段51でラベル内射影部61が動作することによって、暗号化データベースクライアント10で生成されたラベル内鍵41eを受けて異なるラベルの元に暗号化された平文の同一性を比較するためのラベル内比較値43を出力するラベル内射影装置として機能する。ラベル内射影部61は、ラベル内比較値生成機能61aを備える。図14は、図13に示したラベル内射影部61の処理について示すフローチャートである。ラベル内比較値生成機能61aへの入力データとして、暗号文41fの後半部=e[1],e[2]、ラベル33a=L=L[1]、および第1のラベル内鍵41eが暗号化データベースクライアント10から入力される。ラベル内射影部61のラベル内比較値生成機能61aは、i=1と初期設定した後ステップS301、これらの入力データから、以下に示す数14の処理でラベル内比較値43=dを算出しステップS302、この処理をi=Nとなるまで全ての行に対してくり返した後ステップS303~304、図5の暗号化表A37のラベル33a=L[1]に該当する列の値をこのラベル内比較値43=dで置換した行列を出力してステップS305後述のラベル間射影部62に渡す。ラベル内射影部61はこれと同様に、暗号文41fの後半部=e[1],e[2]、ラベル33b=L[2]、および第2のラベル内鍵から、図5の暗号化表B38のラベル33b=L[2]に該当する列の値を算出したラベル内比較値で置換した行列を出力して、ラベル間射影部62に渡す。ラベル間射影部図15は、図1に示した暗号化データベースサーバ50の、ラベル間射影装置としてのより詳しい構成を示す説明図である。暗号化データベースサーバ50は、主演算制御手段51でラベル間射影部62が動作することによって、暗号化データベースクライアント10で生成されたラベル間鍵41a=x[L[1]]を受けて異なるラベルの元に暗号化された平文の同一性を比較するためのラベル間比較値44を出力するラベル間射影装置として機能する。ラベル間射影部62は、ラベル間比較値生成機能62aを備える。図16は、図15に示したラベル間射影部62の処理について示すフローチャートである。ラベル間比較値生成機能62aへの入力データとして、ラベル間射影鍵42c=P=P[1]が暗号化データベースクライアント10から入力され、また図5の暗号化表A37のラベル33a=L[1]に該当する列の値をラベル内比較値43=dで置換した行列もラベル内射影部61から入力される。ラベル間射影部62のラベル間比較値生成機能62aは、i=1と初期設定した後ステップS351、これらの入力データから、以下に示す数15の処理でラベル間比較値44=hを算出しステップS352、この処理をi=Nとなるまで全ての行に対してくり返した後ステップS353~354、図5の暗号化表A37のラベル33a=L[1]に該当する列の値をこのラベル間比較値44=hで置換した行列を出力してステップS355暗号化表自然結合部63に渡す。ラベル内射影部62はこれと同様に、暗号化データベースクライアント10から入力されたラベル間射影鍵=P[2]と、図5の暗号化表B38のラベル33b=L[2]に該当する列の値をラベル内比較値で置換した行列を入力として、このラベル内比較値をラベル間比較値に置換する。暗号化表自然結合部63は、この値によって表A35および表B36の自然結合を行う。本実施形態の処理による効果以上で示した処理による効果について説明する。暗号化装置がラベルLに関連づけられた平文データmを秘密鍵keyを用いて暗号化すると、前述の数7で示した暗号文eが得られる。この暗号文eの後半部e[3],e[4]は平文データmの確率的な暗号文であるので、これからmの情報が漏洩することはない。また、暗号文eの前半部e[3],e[4]も平文データmの確率的な暗号文であるので、これからmの情報が漏洩することはない。もちろん、数7で使用された鍵key[L]は、元々の暗号化に使用された秘密鍵keyがなければ得ることはできない。また、図1で示した別のクライアント100は、主演算制御手段11で復号化部121が動作することによって、単純に暗号文eを復号化して平文データmを得ることができる。ラベル内射影要求部22は、秘密鍵31=keyおよびラベル33a=Lから、数9に示したラベル内鍵41e=key[L]を算出し、これをラベル内射影部61に対して出力する。これを受けたラベル内射影部61は、数14に示したラベル内比較値43=dを算出し、このラベル内比較値43=dについては以下の数16に示す関係が成立する。このラベル内比較値43=dは、ラベルLが同一であれば、同じ平文mから必ず同一のラベル内比較値43=dが得られる。このため、同一のラベルLの暗号文同士で平文が一致するか否かを判定することができるなお、自然結合では同一のラベルLの暗号文同士での比較を行うことはない。続いて、表A35にラベルL[1]が、表B36にラベルL[2]が各々与えられているものとする。表A35のラベルL[1]で示される列の平文データm[1]がこのラベルL[1]に関して暗号化され、表B36のラベルL[2]で示される列の平文データm[2]がこのラベルL[2]に関して暗号化されているものとする。そして、これら各々に対応するラベル内鍵41e=key[L[1]]およびkey[L[2]]がラベル内射影要求部22で算出され、ラベル内射影部61に対して出力されているものとする。ラベル内射影要求部22およびラベル内射影部61にこれらのデータを通して以下の数17に示す各々のラベル内比較値d[1]およびd[2]を得たとしても、このままではg[L[1]]^x[L[1]]およびg[L[2]]^x[L[2]]の離散対数が不明であるので、平文データm[1]とm[2]が等しいか否かをこれらのラベル内比較値d[1]およびd[2]から判断することはできない。そこで、これらに加えてラベル間射影要求部23がラベルL[1]およびL[2]と秘密鍵=keyから、数13によって示した処理によって、以下の数18~19に示すラベル間射影鍵P[1]およびP[2]を生成する。これらのラベル内比較値d[1]およびd[2]と、ラベル間射影鍵P[1]およびP[2]とがラベル間射影部62に入力されると、前述の数15ステップS351で示した処理で、以下の数20~21に示されるような双線形写像の演算で、ラベル間比較値paird[1],P[1]およびpaird[2],P[2]が算出される。ここで、以下の数22に示す関係が成立するので、ラベル間比較値paird[1],P[1]およびpaird[2],P[2]が等しければ元の平文データm[1]とm[2]が等しく、またpaird[1],P[1]およびpaird[2],P[2]が等しくなければ元の平文データm[1]とm[2]が等しくないと判断できる。図17は、暗号化表自然結合部63が、暗号化表A37および暗号化表B38を自然結合する処理について示すフローチャートである。暗号化表自然結合部63は、ラベル間射影部62に対して暗号化表A37のラベル間比較値を算出する処理を行わせステップS401、続いて暗号化表B38のラベル間比較値を算出する処理を行わせるステップS402。ステップS401および402で行われる具体的な処理は、図14および図16に示された通りである。そして暗号化表自然結合部63は、算出されたラベル間比較値h[1]およびh[2]をキーとして暗号化表A37および暗号化表B38の自然結合処理を行いステップS403、自然結合されて作成された暗号化表A×B81を暗号化データベースクライアント10に返すステップS404。第1の実施形態の全体的な動作次に、上記の実施形態の全体的な動作について説明する。本実施形態に係る自然結合方法は、クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステム1にあって、外部から入力される第1の表の第1のラベルによって示される列のデータをクライアント端末の列暗号化部があらかじめ記憶された暗号鍵および第1の群の生成子とによって暗号化して外部に出力し図4ステップS101~110、外部から入力される第2の表の第2のラベルによって示される列のデータをクライアント端末の列暗号化部が暗号鍵およびあらかじめ記憶された第2の群の生成子とによって暗号化して外部に出力し図4ステップS101~110、暗号鍵と第1のラベルとからクライアント端末のラベル内射影要求部が第1のラベル内鍵を生成して外部に出力し図10ステップS201~202、暗号鍵と第2のラベルとからクライアント端末のラベル内射影要求部が第2のラベル内鍵を生成して外部に出力し図10ステップS201~202、暗号鍵と第1の群の生成子と、第1および第2のラベル内鍵からクライアント端末のラベル間射影要求部が第1のラベル間射影鍵を生成して外部に出力し図11ステップS251~255、暗号鍵と第2の群の生成子と、第1および第2のラベル内鍵からクライアント端末のラベル間射影要求部が第2のラベル間射影鍵を生成して外部に出力し図11ステップS251~255、暗号化された第1および第2の表、第1および第2のラベル内鍵と第1および第2のラベル間射影鍵を暗号化データベースサーバのデータ受信部が受信し図6ステップS141~142、暗号化された第1の表の第1のラベルによって示される列のデータに暗号化データベースサーバのラベル内射影部が第1のラベルと第1のラベル内鍵とを作用させて第1のラベル内比較値を生成し図14ステップS301~305、暗号化された第2の表の第2のラベルによって示される列のデータに暗号化データベースサーバのラベル内射影部が第2のラベルと第2のラベル内鍵とを作用させて第2のラベル内比較値を生成し図14ステップS301~305、第1のラベル内比較値に暗号化データベースサーバのラベル間射影部が第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成し図16ステップS351~355、第2のラベル内比較値に暗号化データベースサーバのラベル間射影部が第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成し図16ステップS351~355、第1および第2のラベル間比較値を利用して、暗号化データベースサーバの暗号化表自然結合部が暗号化された第1および第2の表に対する自然結合を実行する図17ステップS403。ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータである暗号化データベースクライアント10および暗号化データベースサーバ50に実行させるようにしてもよい。本プログラムは、非一時的な記録媒体、例えば、DVD、CD、フラッシュメモリ等に記録されてもよい。その場合、本プログラムは、記録媒体からコンピュータによって読み出され、実行される。この動作により、本実施形態は以下のような効果を奏する。本実施形態によれば、そのままでは他と比較することは不可能である暗号化されたデータを、ラベル間射影鍵P[1]およびP[2]を利用してそのデータを復号化せずに2つの平文データが等しいか否かを判断することができ、それによってデータの自然結合を行うことが可能となる暗号化データベースシステムを実現することが可能となる。自然結合はデータベースにおいて頻繁に行われる処理である。従って、この自然結合をデータを復号化せずに実行できるということは、データベースから機密情報が漏洩する機会を少なくすることが可能であることを意味する。その際、必要となるデータの処理量は、比較する対象となる二つの列のデータ量に単純に比例する。即ち、データ量の2乗に比例するなどのような大幅な処理量の増大を招くものではない。また、ここで自然結合の対象となる列を示すラベルは、特定の表の特定の列を一意的に識別しうるデータである。従って、表と列の各々に識別子を与えてこの識別子によって自然結合の処理を行う必要はないので、より処理を簡略化でき、より汎用的に適用できるものとなる。これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。上述した各々の実施形態について、その新規な技術内容の要点をまとめると、以下のようになる。なお、上記実施形態の一部または全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。付記1クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムであって、前記クライアント端末が、暗号鍵および当該暗号鍵の要部をなす第1および第2の群の生成子を予め記憶する記憶手段と、外部から入力される第1の表の第1のラベルによって示される列のデータを前記暗号鍵および前記第1の群の生成子とによって暗号化すると共に、同じく外部から入力される第2の表の第2のラベルによって示される列のデータを前記暗号鍵および前記第2の群の生成子によって暗号化し、これら暗号化された第1および第2の表を外部に出力する列暗号化部と、前記暗号鍵と前記第1のラベルとから第1のラベル内鍵を生成すると共に、前記暗号鍵と前記第2のラベルとから第2のラベル内鍵を生成し、これら第1および第2のラベル内鍵を外部に出力するラベル内射影要求部と、前記暗号鍵と前記第1の群の生成子と前記第1および第2のラベル内鍵とから第1のラベル間射影鍵を生成すると共に、前記暗号鍵と前記第2の群の生成子と前記第1および第2のラベル内鍵とから第2のラベル間射影鍵を生成し、これら第1および第2のラベル間射影鍵を外部に出力するラベル間射影要求部とを備え、前記暗号化データベースサーバが、前記暗号化された第1および第2の表を受信して記憶すると共に、前記第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵とを受信するデータ受信部と、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成すると共に、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成するラベル内射影部と、前記第1のラベル内比較値に前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成すると共に、前記第2のラベル内比較値に前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成するラベル間射影部と、前記出力された第1および第2のラベル間比較値を利用して、前記暗号化された第1および第2の表に対する自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースシステム。付記2前記列暗号化部が、前記秘密鍵と前記ラベルとからラベル間鍵を生成するラベル間鍵生成機能と、前記群の生成子と前記ラベル間射影鍵とから第一ラベル公開鍵を生成する第一ラベル公開鍵生成機能と、前記秘密鍵と前記列のデータとから単純比較値を生成する比較値生成機能と、前記第一ラベル公開鍵と前記単純比較値と前記ラベル間鍵とからラベル内比較値を生成する隠蔽比較値生成機能と、前記秘密鍵と前記ラベルとから前記ラベル内鍵を生成するラベル内鍵生成機能と、前記ラベル内鍵によって前記ラベル内比較値を暗号化すると同時に前記秘密鍵によって前記列のデータを暗号化する暗号化機能とを備えることを特徴とする、付記1に記載の暗号化データベースシステム。付記3前記ラベル内射影要求部が、前記秘密鍵と前記第1のラベルとから前記ラベル内鍵を生成するラベル内鍵生成機能を備えると共に、前記ラベル間射影要求部が、前記秘密鍵と前記第2のラベルとから前記ラベル間鍵を生成するラベル間射影鍵生成機能と、前記群の生成子と前記ラベル間鍵とから第二ラベル公開鍵を生成する第二ラベル公開鍵生成機能と、前記第1および第2のラベルと前記秘密鍵とから補間値を生成する補間値生成機能と、前記第二ラベル公開鍵と前記補間値とからラベル間射影鍵を生成する射影鍵生成機能とを備えることを特徴とする、付記1に記載の暗号化データベースシステム。付記4前記ラベル内射影部が、前記ラベル内鍵と前記暗号化された第1および第2の表の暗号化された列データから第1および第2のラベル内比較値を生成するラベル内比較値生成機能を備えると共に、前記ラベル間射影部が、前記ラベル間射影鍵と前記第1および第2のラベル内比較値とを双線形写像の入力として、その出力を各々前記第1および第2のラベル間比較値として出力するラベル間比較値生成機能を備えることを特徴とする、付記1に記載の暗号化データベースシステム。付記5暗号化データベースサーバと相互に接続されて暗号化データベースシステムを構成されるクライアント端末であって、暗号鍵および当該暗号鍵の要部をなす第1および第2の群の生成子を予め記憶する記憶手段と、外部から入力される第1の表の第1のラベルによって示される列のデータを前記暗号鍵および前記第1の群の生成子とによって暗号化すると共に、同じく外部から入力される第2の表の第2のラベルによって示される列のデータを前記暗号鍵および前記第2の群の生成子によって暗号化し、これら暗号化された第1および第2の表を外部に出力する列暗号化部と、前記暗号鍵と前記第1のラベルとから第1のラベル内鍵を生成すると共に、前記暗号鍵と前記第2のラベルとから第2のラベル内鍵を生成し、これら第1および第2のラベル内鍵を外部に出力するラベル内射影要求部と、前記暗号鍵と前記第1の群の生成子と前記第1および第2のラベル内鍵とから第1のラベル間射影鍵を生成すると共に、前記暗号鍵と前記第2の群の生成子と前記第1および第2のラベル内鍵とから第2のラベル間射影鍵を生成し、これら第1および第2のラベル間射影鍵を外部に出力するラベル間射影要求部とを備えることを特徴とするクライアント端末。付記6クライアント端末と相互に接続されて暗号化データベースシステムを構成される暗号化データベースサーバであって、前記クライアント端末から送信される第1のラベルによって示される列が暗号化された第1の表および第2のラベルによって示される列が暗号化された第2の表を受信して記憶すると共に、前記クライアント端末から送信される第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵とを受信するデータ受信部と、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成すると共に、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成するラベル内射影部と、前記第1のラベル内比較値に前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成すると共に、前記第2のラベル内比較値に前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成するラベル間射影部と、前記出力された第1および第2のラベル間比較値を利用して、前記暗号化された第1および第2の表に対する自然結合を実行する暗号化表自然結合部とを備えることを特徴とする暗号化データベースサーバ。付記7クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、外部から入力される第1の表の第1のラベルによって示される列のデータを前記クライアント端末の列暗号化部があらかじめ記憶された暗号鍵および当該暗号鍵の要部をなす第1の群の生成子とによって暗号化して外部に出力し、外部から入力される第2の表の第2のラベルによって示される列のデータを前記クライアント端末の列暗号化部が前記暗号鍵およびあらかじめ記憶された前記暗号鍵の要部をなす第2の群の生成子とによって暗号化して外部に出力し、前記暗号鍵と前記第1のラベルとから前記クライアント端末のラベル内射影要求部が第1のラベル内鍵を生成して外部に出力し、前記暗号鍵と前記第2のラベルとから前記クライアント端末のラベル内射影要求部が第2のラベル内鍵を生成して外部に出力し、前記暗号鍵と前記第1の群の生成子と、前記第1および第2のラベル内鍵から前記クライアント端末のラベル間射影要求部が第1のラベル間射影鍵を生成して外部に出力し、前記暗号鍵と前記第2の群の生成子と、前記第1および第2のラベル内鍵から前記クライアント端末のラベル間射影要求部が第2のラベル間射影鍵を生成して外部に出力し、前記暗号化された第1および第2の表、前記第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵を前記暗号化データベースサーバのデータ受信部が受信し、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記暗号化データベースサーバのラベル内射影部が前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成し、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記暗号化データベースサーバのラベル内射影部が前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成し、前記第1のラベル内比較値に前記暗号化データベースサーバのラベル間射影部が前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成し、前記第2のラベル内比較値に前記暗号化データベースサーバのラベル間射影部が前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成し、前記第1および第2のラベル間比較値を利用して、前記暗号化データベースサーバの暗号化表自然結合部が前記暗号化された第1および第2の表に対する自然結合を実行することを特徴とする暗号化表の自然結合方法。付記8クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、前記クライアント端末が備えているコンピュータに、外部から入力される第1の表の第1のラベルによって示される列のデータをあらかじめ記憶された暗号鍵および当該暗号鍵の要部をなす第1の群の生成子とによって暗号化して外部に出力する手順、外部から入力される第2の表の第2のラベルによって示される列のデータを前記暗号鍵およびあらかじめ記憶された前記暗号鍵の要部をなす第2の群の生成子とによって暗号化して外部に出力する手順、前記暗号鍵と前記第1のラベルとから第1のラベル内鍵を生成して外部に出力する手順、前記暗号鍵と前記第2のラベルとから第2のラベル内鍵を生成して外部に出力する手順、前記暗号鍵と前記第1の群の生成子と、前記第1および第2のラベル内鍵から第1のラベル間射影鍵を生成して外部に出力する手順、および前記暗号鍵と前記第2の群の生成子と、前記第1および第2のラベル内鍵から第2のラベル間射影鍵を生成して外部に出力する手順を実行させることを特徴とする暗号化表の自然結合プログラム。付記9クライアント端末と暗号化データベースサーバとが相互に接続されて構成される暗号化データベースシステムにあって、暗号化データベースサーバが備えているコンピュータに、前記暗号化された第1および第2の表、前記第1および第2のラベル内鍵と前記第1および第2のラベル間射影鍵を受信する手順、前記暗号化された第1の表の第1のラベルによって示される列のデータに前記第1のラベルと前記第1のラベル内鍵とを作用させて第1のラベル内比較値を生成する手順、前記暗号化された第2の表の第2のラベルによって示される列のデータに前記第2のラベルと前記第2のラベル内鍵とを作用させて第2のラベル内比較値を生成する手順、前記第1のラベル内比較値に前記第1のラベル間射影鍵を作用させて第1のラベル間比較値を生成する手順、前記第2のラベル内比較値に前記第2のラベル間射影鍵を作用させて第2のラベル間比較値を生成する手順、および前記第1および第2のラベル間比較値を利用して、前記暗号化された第1および第2の表に対する自然結合を実行する手順を実行させることを特徴とする暗号化表の自然結合プログラム。この出願は2010年12月13日に出願された日本出願特願2010-277070を基礎とする優先権を主張し、その開示の全てをここに取り込む。"