(57)【要約】  データベースサーバにおいて、複数の要素をそれぞれ、暗号化前の演算と暗号化後の演算との準同型を保つ暗号化により暗号化した暗号化ベクトルデータを格納する。データベースサーバは、難読化クエリ（Ｎ−ランダム化クエリ）を端末装置より受信し、難読化クエリのベクトルの複数のセグメントごとに、暗号化ベクトルデータのセグメントとの計算を行ない、端末装置へ返信する。端末装置は、返信された計算を復号装置より、復号された計算の結果を取得することができる。
2016129390.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータを有するクエリを取得するクエリ取得部と、
前記クエリから複数のＮ−ランダム化ベクトルを生成する生成部であり、前記クエリおよび前記複数のＮ−ランダム化ベクトルそれぞれをＮ個のセグメントに分割した場合、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントは、前記クエリの第ｉ番目のセグメントまたはランダムなデータを含むセグメントであり、前記クエリのセグメントそれぞれは、前記複数のＮ−ランダム化ベクトルのいずれか１以上のセグメントとして含まれる、生成部と、
前記クエリの前記セグメントそれぞれを含む前記複数のＮ−ランダム化ベクトルの識別情報を格納する生成情報格納部と、
前記複数のＮ−ランダム化ベクトルをデータベースサーバへ送信する送信部であり、前記データベースサーバは、暗号化の前における第１の演算の結果が前記暗号化の後における第２の演算の結果を復号化して得られる結果となる暗号化により、複数の要素それぞれを前記暗号化して得られる暗号化ベクトルを格納し、前記複数のＮ−ランダム化ベクトルに対して、前記暗号化ベクトルを、Ｎ個の暗号化セグメントに分割し、第ｉ番目の暗号化セグメントの各要素を暗号化する前の各要素に対して、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントの各データに基づいて前記第１の演算を行なって得られる計算結果を前記暗号化した暗号化計算結果を、前記暗号化ベクトルの第ｉ番目の暗号化セグメントの各要素に対して、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントの各データに基づいて前記第２の演算を行ない、生成するデータベースサーバである送信部と、
前記送信部による送信に対応して、前記暗号化計算結果を前記暗号化に対応する復号化した計算結果を受信する計算結果受信部と、
前記計算結果受信部により受信される計算結果と前記生成情報格納部に格納された識別情報に基づいて、前記クエリと前記暗号化ベクトルの各要素を前記暗号化する前の各要素との計算結果を計算する計算部と
を備える、端末装置。
【請求項２】
前記計算結果受信部は、
前記データベースサーバより前記暗号化計算結果を受信する暗号化計算結果受信部と、
前記暗号化計算結果受信部により受信された前記暗号化計算結果を復号化する装置へ送信する暗号化計算結果送信部と、
前記装置より復号化した計算結果を受信する計算結果受信部とを備える、請求項１に記載の端末装置。
【請求項３】
前記複数の要素のそれぞれは、１ビットの情報を表わし、前記クエリは、ビット列を表わす、請求項１に記載の端末装置。
【請求項４】
前記第１の演算は加算であり、前記第２の演算は乗算である請求項１に記載の端末装置。
【請求項５】
前記第２の演算は、生成元を有する群における乗算である請求項４に記載の端末装置。
【請求項６】
前記生成元の位数は有限である請求項５に記載の端末装置。
【請求項７】
暗号化の前における第１の演算の結果が前記暗号化の後における第２の演算の結果を復号化して得られる結果となる暗号化の処理により、複数の要素それぞれを暗号化して得られる暗号化要素を含む暗号化ベクトルを格納するデータベースと、
複数のデータを有するクエリから生成された複数のＮ−ランダム化ベクトルを受信する受信部であり、前記クエリおよび前記複数のＮ−ランダム化ベクトルそれぞれをＮ個のセグメントに分割した場合、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントは、前記クエリの第ｉ番目のセグメントまたはランダムなデータを含むセグメントであり、前記クエリのセグメントそれぞれは、前記複数のＮ−ランダム化ベクトルのいずれか１以上のセグメントとして含まれる、受信部と、
前記暗号化ベクトルをＮ個のセグメントに分割して得られる第ｉ番目の暗号化セグメントの各要素を暗号化する前の各要素に対して、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントの各データに基づいて前記第１の演算を行なって得られる計算結果を前記暗号化した暗号化計算結果を、前記暗号化ベクトルの第ｉ番目のセグメントの各要素に対して、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントの各データに基づいて前記第２の演算を行ない計算する計算処理部と、
前記暗号化計算結果を送信する送信部と、
を備えるデータベースサーバ。
【請求項８】
前記暗号化計算結果は、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントＳ（ｉ）の各データに基づく計算結果であり、前記セグメントＳ（ｉ）の各データに基づく演算結果は、前記暗号化ベクトルの第ｉ番目のセグメントの第ｊ番目の暗号化要素ｄｉｊに、前記セグメントＳ（ｉ）に含まれる第ｊ番目のデータの表わす整数Ｓｉｊの回数前記第２の演算を適用した冪ｄｉｊＳｉｊを計算した結果に前記第２の演算を適用した演算結果ΠｊｄｉｊＳｉｊと等価である、請求項７に記載のデータベースサーバ。
【請求項９】
前記複数の要素のそれぞれは、１ビットの情報を表わし、前記クエリは、ビット列を表わす、請求項７に記載のデータベースサーバ。
【請求項１０】
前記第１の演算を用いて計算される計算結果は、前記セグメントＳ（ｉ）と、前記暗号化ベクトルの第ｉ番目のセグメントの各要素を暗号化する前の要素を含むセグメントとのＴｖｅｒｓｋｙ  Ｉｎｄｅｘに対応する値である請求項９に記載のデータベースサーバ。
【請求項１１】
前記第１の演算は加算であり、前記第２の演算は乗算である、請求項７に記載のデータベースサーバ。
【請求項１２】
前記第２の演算は、生成元を有する群における乗算である、請求項１１に記載のデータベースサーバ。
【請求項１３】
前記生成元の位数は有限である、請求項１２に記載のデータベースサーバ。
【請求項１４】
前記暗号化の処理においては確率暗号を用いる、請求項７に記載のデータベースサーバ。
【請求項１５】
前記データベースに格納される暗号化ベクトルに関連づけられた復号鍵を格納する復号鍵格納部と、
前記データベースに格納される暗号化ベクトルの暗号化要素の範囲と前記範囲の暗号化された要素に置き換える暗号化要素とを暗号化した情報を受信する第２受信部と、
前記第２受信部で受信された情報を前記復号鍵格納部に格納されている復号鍵により復号した結果に基づいて、前記範囲内の前記暗号化ベクトルの暗号化要素を更新する更新部と、
を有する、請求項７に記載のデータベースサーバ。
【請求項１６】
前記更新部は、前記暗号化ベクトルの暗号化要素を、前記暗号化ベクトルの暗号化要素と前記復号した結果に含まれる暗号化要素とに対する前記第２の演算の結果に更新する、請求項１５に記載のデータベースサーバ。
【請求項１７】
データベースサーバと、情報提供装置と、復号装置と、端末装置とを有する計算システムであり、
前記情報提供装置は、
複数の要素を有する要素の組を取得する要素取得部と、
暗号化の前の第１の演算の結果が前記暗号化の後における第２の演算の結果を復号化して得られる結果となる暗号化により、前記複数の要素それぞれを暗号化し、暗号化ベクトルを生成する要素暗号化部と、
前記要素暗号化部により生成された暗号化ベクトルを前記データベースサーバに送信する暗号化データ送信部と、
を備え、
前記復号装置は、
前記暗号化されたデータを受信するデータ受信部と、
前記データ受信部により受信されたデータを復号化する復号部と、
前記復号部により復号された結果を送信する復号結果送信部と
を備え、
前記端末装置は、
複数のデータを有するクエリを取得するクエリ取得部と、
前記クエリ取得部により取得されたクエリから複数のＮ−ランダム化ベクトルを生成する生成部であり、前記クエリおよび前記複数のＮ−ランダム化ベクトルそれぞれをＮ個のセグメントに分割した場合、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントは、前記クエリの第ｉ番目のセグメントまたはランダムなデータを含むセグメントであり、前記クエリのセグメントそれぞれは、前記複数のＮ−ランダム化ベクトルのいずれか１以上のセグメントとして含まれる、生成部と、
前記クエリの前記セグメントそれぞれを含む前記複数のランダム化ベクトルの識別情報を格納する生成情報格納部と、
前記複数のＮ−ランダム化ベクトルを、前記データベースサーバへ送信するクエリ送信部と、
前記クエリ送信部による前記Ｎ−ランダム化ベクトルの送信に対応して、前記復号装置から前記複数のＮ−ランダム化ベクトルの各セグメントについての前記データベースサーバでの計算結果を復号した結果を受信する計算結果受信部と、
前記計算結果受信部により受信された計算結果と前記生成情報格納部に格納された識別情報に基づいて前記クエリと前記暗号化ベクトルの各要素を前記暗号化する前の各要素との計算結果を計算する計算部と
を備え、
前記データベースサーバは、
前記情報提供装置から送信される暗号化ベクトルを格納するデータベースと、
前記端末装置から送信される複数のＮ−ランダム化ベクトルを受信するクエリ受信部と、
前記暗号化ベクトルをＮ個のセグメントに分割して得られる第ｉ番目の暗号化セグメントの各要素を暗号化する前の各要素に対して、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントの各データに基づいて前記第１の演算を行なって得られる計算結果を前記暗号化した暗号化計算結果を、前記暗号化ベクトルの第ｉ番目のセグメントの各要素に対して、前記複数のＮ−ランダム化ベクトルそれぞれの第ｉ番目のセグメントの各データに基づいて前記第２の演算を行ない計算する計算処理部と、
前記暗号化計算結果を送信する送信部と、
を備える計算システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースサーバ、クエリ装置（端末装置）、データベースシステムおよび計算システムなどに関する。特に、データベースサーバが格納するデータの情報提供者およびデータベースサーバ管理者にクエリの内容を知られずにクエリの処理を行うことができ、また、復号化の処理をすることなくクエリに応じた計算結果を情報提供者の暗号鍵により暗号化して得ることができるデータベースサーバ、クエリ装置、データベースシステムなどに関する。
【背景技術】
【０００２】
クラウドサービスが利用可能となり、様々なデータベースサービスがインターネットを介して提供可能である。すなわち、情報提供者は、クラウドサービス提供者が提供するデータベースサーバに種々のデータを格納し、データベースサービスを提供することが可能となってきている。この場合、情報提供者自らがデータベースサーバを管理する必要はなく、クラウドサービス提供者が管理するデータベースサーバを借りることとなる。【０００３】
このようなデータベースサービスの提供においては、情報提供者と異なるクラウドサービス提供者がデータベースサーバを管理するので、データの漏えいが発生する危険が高くなる可能性がある。例えば、クラウドサービス提供者は、提供するデータベースサーバに格納されたデータに直接アクセスしてデータを入手することが可能であり、情報提供者は価値の高いデータの提供を躊躇する場合がある。また、データベースサービスの利用者にしても、どのようなクエリをデータベースに対して発行したかをクラウドサービス提供者および情報提供者が知ることが可能である。このため、データベースサービスの利用者の意図が、他者により推測される可能性があるので、データベースサービスの利用を躊躇する場合がある。【０００４】
このような問題を解決する技術として、データベースサーバに格納されるデータおよびクエリの両方またはいずれか一つを暗号化した状態でクエリを処理することを可能とする秘匿計算の技術が提案されている（例えば、特許文献１〜９参照。）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２０１３／０３８６９８号
【特許文献２】特許第５４１２４１４号公報
【特許文献３】特開２０１２−２２７８０１号公報
【特許文献４】特開２０１３−１３０８２５号公報
【特許文献５】特開２０１３−１４５４２０号公報
【特許文献６】特開２０１３−１２５０３９号公報
【特許文献７】特開２０１３−２０５６５５号公報
【特許文献８】特開２００９−２７１５８４号公報
【特許文献９】特許第４９３８６７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の技術においては、情報提供者、データベースサーバ管理者およびデータベースの検索を行う利用者の間でクエリの秘匿化が十分に行えず、例えば、利用者のクエリが情報提供者に対して秘匿となっていても、データベースサーバ管理者にはデータベースに格納されているデータが秘匿とはならない場合がある。
【課題を解決するための手段】
【０００７】
本発明の一実施形態として、データベースと、受信部と、計算処理部とを有するデータベースサーバを提供する。データベースは、暗号化ベクトルデータを格納する。暗号化ベクトルデータとは、複数の要素により構成されるデータを、暗号化前における第１の演算の結果が暗号化後における第２の演算の結果を復号化して得られる結果となる第１の演算と第２の演算との準同型を保つ暗号化の処理により、前記複数の要素それぞれを暗号化して得られる。受信部は、クエリデータを有するクエリベクトルを複数のセグメントに分割し、それぞれが前記複数のセグメントのいずれかとランダムデータを含むランダムセグメントとのいずれか一以上を含み、前記クエリベクトルを復元可能な複数の難読化クエリベクトルを前記情報検索者の端末から受信する。計算処理部は、前記複数の難読化クエリベクトルそれぞれに含まれる前記複数のセグメントのいずれかのセグメントとランダムセグメントごとに、前記準同型により、前記暗号化ベクトルデータの前記複数の要素を暗号化する前の要素の部分列との計算結果のそれぞれを前記情報提供者の公開鍵により暗号化して得られるべき複数の暗号化計算結果を計算する。
【発明の効果】
【０００８】
本発明によれば、データベースサーバに格納されたデータは、情報提供者のみが復号化の処理をすることができ、また、データベースの検索を行う利用者のクエリの内容を情報提供者およびデータベースサーバ管理者が知ることを困難とすることができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の一実施形態に係るシステムの機能ブロック図
【図２】本発明の一実施形態に係るシステムの情報提供装置の機能ブロック図
【図３】本発明の一実施形態に係るシステムの情報提供装置による暗号化処理を説明するための図
【図４】本発明の一実施形態に係るシステムのデータベースサーバの機能ブロック図
【図５】本発明の一実施形態に係るシステムのデータベースサーバに格納されたベクトルデータの一例図
【図６】本発明の一実施形態に係るシステムのデータベースサーバに格納されたベクトルデータの一例図
【図７】本発明の一実施形態に係るシステムのデータベースサーバにおける計算を説明するための図
【図８】本発明の一実施形態に係るシステムのクエリ装置の機能ブロック図
【図９】（Ａ）は、クエリベクトルの一例図であり、（Ｂ）は、セグメント化されたクエリベクトルの一例図であり、（Ｃ）は、難読化クエリベクトルの一例図であり、（Ｄ）は、難読化情報の一例図である。
【図１０】本発明の一実施形態に係るシステムの復号装置の機能ブロック図
【図１１】本発明の一実施形態に係るシステムの情報提供装置の実行する処理のフローチャート
【図１２】本発明の一実施形態に係るシステムのデータベースサーバが実行する処理のフローチャート
【図１３】本発明の一実施形態に係るシステムのデータベースサーバが実行する処理のフローチャート
【図１４】本発明の一実施形態に係るシステムのクエリ装置（端末装置）が実行する処理のフローチャート
【図１５】本発明の一実施形態に係るシステムの復号装置が実行する処理のフローチャート
【図１６】本発明の一実施形態に係るシステムのデータの流れを説明するための図
【図１７】本発明の一実施形態に係るシステムのデータの流れを説明するための図
【図１８】本発明の一実施形態に係るシステムのデータの流れを説明するための図
【図１９】本発明の一実施形態に係るシステムの機能ブロック図
【図２０】本発明の一実施形態に係るシステムのデータの流れを説明するための図
【図２１】本発明の一実施形態に係るシステムのデータの流れを説明するための図
【図２２】本発明の一実施形態に係るシステムのデータベースサーバの機能ブロック図
【図２３】本発明の一実施形態に係るシステムの情報提供装置による暗号化処理を説明するための図
【発明を実施するための形態】
【００１０】
以下、本発明を実施するための形態について、図面を参照していくつかの実施形態として説明する。なお本発明は、以下に説明する実施形態に限定して、解釈されることはない。本発明は、以下に説明される実施形態を種々に変形して実施することが、可能である。
【００１１】
（実施形態１）
図１は、本発明の一実施形態に係るシステムの機能ブロック図、を示す。システム１００は、情報提供装置１０１と、データベースサーバ１０２と、クエリ装置１０３と、復号装置１０４とを備える。なお、クエリ装置１０３を、「端末装置（１０３）」と呼称する場合がある。
【００１２】
本実施形態においては、情報提供装置１０１の運営者（すなわち、情報提供者）、データベースサーバ１０２の管理者およびクエリ装置１０３の利用者は互いに異なることが通常、想定される。また、復号装置１０４の運営者は、情報提供装置１０１の運営者と同一であってもよい。
【００１３】
システム１００の動作の概要は以下の通りである。（ステップＡ）情報提供装置１０１が暗号化の処理を行った暗号化データ（例えば、複数の暗号化の処理がされた要素を含むベクトルデータ）を含むデータをデータベースサーバに格納する。（ステップＢ）クエリ装置１０３は、データベースサーバに対してクエリ（例えば、複数のクエリデータの要素を含むクエリベクトル）を送信する。この場合、クエリは平文で送られるのではなく、クエリ装置１０３において一種の暗号化の処理である難読化の処理が施され、データベースサーバ１０２の管理者および情報提供装置１０１の運営者が難読化前のクエリを復元困難な状態にしてからデータベースサーバ１０２に送信される。（ステップＣ）データベースサーバ１０２は、受信したクエリに応じて、暗号化データに対する計算を行い、その結果をクエリ装置１０３に返信する。このとき、クエリ装置１０３に返信される結果は、暗号化の処理がされている。また、データベースサーバ１０２における暗号化データに対する計算には、復号化の処理を含まないようにすることができる。（ステップＤ）クエリ装置１０３は、返信された結果の全てまたは一部を復号装置１０４に送信し、結果の全てまたは一部を復号化させる。復号装置１０４は、情報提供装置１０１がデータに対して行った暗号化の処理に対応する復号化の処理を行う。（ステップＥ）クエリ装置１０３は、復号化の処理がされた結果を受信し、難読化の処理の逆の処理を行い、計算結果を得ることができる。なお、暗号化の処理を行うことを、暗号化する（ｅｎｃｒｙｐｔ）という場合がある。同様に復号化の処理を行うことを復号化する（ｄｅｃｒｙｐｔ）という場合がある。
【００１４】
ステップＡの暗号化の処理は、データベースサーバ１０２の管理者およびクエリ装置１０３の利用者の両者がデータの復号を行うことができないようにするために行うことができる。
【００１５】
ステップＢの難読化の処理は、データベースサーバ１０２の管理者および情報提供装置１０１の運営者が、クエリの内容からクエリ装置１０３の利用者の意図を知ることができないようにするために行うことができる。なお、難読化の処理を「Ｎ−ランダム化ベクトルを生成する処理」と呼称する場合がある。ここに、「Ｎ」は、クエリをセグメントに分割数またはクエリの分割位置を表わす自然数の列であってよい。例えば、クエリの４番目までの要素のセグメントと、５番目から６番目までの要素のセグメントと、７番目以降の要素のセグメントに分割する難読化により得られるデータを、３−ランダム化ベクトルまたは（４，６）−ランダム化ベクトルという。
【００１６】
ステップＣにおける結果は、情報提供装置１０１が暗号化の処理を行ったときの暗号鍵により暗号化された状態となっており、データベースサーバ１０２の管理者およびクエリ装置１０３の利用者の両者が計算結果の復号化の処理を行うことができないようにすることができる。
【００１７】
ステップＤにおいて、復号装置１０４には、クエリの難読化により得られた計算結果が送信されるので、復号装置１０４は、復号化の処理を行っても、復号化の処理の結果から、クエリ装置１０３の利用者の意図を知ることを困難とすることができる。例えば、クエリ装置１０３の利用者が何を検索しようとしているかを知ることを困難とすることができる。
【００１８】
ステップＥにおける逆難読化の処理の結果の内容は、データベースサーバ１０２の管理者および情報提供装置１０１の運営者に知られないようにクエリ装置１０３の利用者側で行うことができる。
【００１９】
したがって、本発明の一実施形態においては、データベースサーバ１０２に格納されたデータは暗号化されているので、データベースサーバ１０２からデータが漏えいしても情報提供装置１０１の運営者以外は復号化をすることができないようにすることができる。また、クエリ装置１０３が送信するクエリは難読化されているので、データベースサーバ１０２の管理者および情報提供装置１０１の運営者は、クエリ装置１０３の利用者の意図を知ることができないようにすることができる。また、クエリに対する結果は、難読化の影響を受けているので、クエリの結果を情報提供装置１０１の運営者が知ったとしても、クエリ装置１０３の利用者の意図を知ることができないようにすることができ、また、クエリの結果は、暗号化されているので、データベースサーバ１０２の管理者が、クエリの結果を復号化できないようにすることができる。また、復号装置１０４においても、計算結果は難読化の影響を受けているので、復号化の処理を行っても復号化の処理の結果から復号装置１０４の管理者がクエリ装置１０３の利用者の意図を知ることを困難とすることができる。
【００２０】
図２は、情報提供装置１０１の機能ブロック図を示す。情報提供装置は、データ取得部２０１と、データ暗号化部２０２と、鍵情報格納部２０３と、暗号化データ送信部２０４とを有する。なお、情報提供装置１０１は、ＣＰＵ、メモリ、記憶装置、入出力装置およびそれらを接続するバスを含む計算機にプログラムを動作させることにより実現が可能である。また、情報提供装置１０１を、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）などのハードウェアの構成要素を組み合わせて実現し、プログラムを用いる必要を無くすることもできる。
【００２１】
データ取得部２０１は、データを取得する。例えば、情報提供装置１０１に備えられた光ディスクドライブやハードディスクドライブより、データを読み込み、データを取得する。あるいは、情報提供装置１０１に接続された他の機器からデータを受信し、データを取得する。取得されたデータは、情報提供装置１０１の例えばメモリや記憶装置に記憶される。
【００２２】
データ取得部２０１が取得するデータは、複数の要素により構成される。例えば化合物について、予め定められた複数の部分構造それぞれを有するか否かを表わす値の組がデータとなる。この場合、化合物が、ある１つの部分構造を有するか否かを表わす値が要素となる。例えば、その化合物がメチル基を有するか否かを表わす値が要素となる。あるいは、一般的なオブジェクト（人、有体物または無体物）が、複数の属性それぞれを有するか否かを表わす値の組がデータとなる。この場合、オブジェクトが、ある１つの属性を有するか否かを表わす値が要素となる。例えば、その人が女性であるかどうかを表わす値が要素となる。なお、化合物が部分構造を有することやオブジェクトが属性を有することを表わす値として、１という整数の値を使用し、化合物が部分構造を有しないことやオブジェクトが属性を有しないことを表わす値として、０という整数の値を使用することができる。
【００２３】
データ取得部２０１が取得するデータが複数の要素により構成されるので、データ取得部２０１を「要素取得部（２０１）」と呼称する場合がある。
【００２４】
データ暗号化部２０２は、データ取得部２０１が取得したデータの暗号化の処理を行う。データ暗号化部２０２は、鍵情報格納部２０３に格納された暗号鍵を用いて、データを構成する複数の要素それぞれを暗号化する。暗号鍵は、共通鍵暗号化方法の共通鍵、または、公開鍵暗号化方法の公開鍵や秘密鍵を用いることができる。本発明の一実施形態においては、データベースサーバ１０２においてもその暗号鍵を用いてクエリの暗号化の処理が必要となる場合に備え、情報提供装置１０１の利用者の公開鍵を用いるのが好ましい。また、２つの要素の値が同じであっても、それぞれの要素に対する暗号化の処理の結果が同一にならないのが好ましい。このため、確率暗号の処理が用いられるのが好ましい。
【００２５】
データ暗号化部２０２を「要素暗号化部（２０２）」と呼称する場合がある。
【００２６】
データ暗号化部２０２は、例えば、鍵情報格納部２０３に格納された暗号鍵を読み出し、情報提供装置１０１の例えばメモリに記憶し、また、データ取得部２０１が取得しメモリや記憶装置に記憶されたデータを読み出し、暗号化をＣＰＵに行わせるプログラムを実行することにより実現することができる。また、データ暗号化部２０２を、プログラムを用いずにハードウェアの組合せによっても実現することができる。暗号化の処理の結果は、情報提供装置１０１のメモリや記憶装置に記憶される。
【００２７】
本実施形態においては、暗号化の処理は、暗号化の処理の前の値に第１の演算を適用した結果が、暗号化の処理の結果に第２の演算を適用した結果を復号化して得られる結果となる処理であるのが好ましい。すなわち、本実施形態における暗号化の処理は、第１の演算と第２の演算との準同型（Ｓｅｍｉ−Ｈｏｍｏｍｏｒｐｈｉｓｍ）を保つことが好ましい。
【００２８】
例えば、第１の演算を「＋」を用いる和の演算とし、第２の演算を「＊」を用いる積の演算とした場合において、暗号化の処理を関数Ｅｎｃにより表わし、暗号化の処理の前の値に第１の演算を適用した結果をａ＋ｂと表わすとする。このとき、暗号化の処理の結果に第２の演算を適用した結果を復号化して得られる結果は、Ｅｎｃ−１（Ｅｎｃ（ａ）＊Ｅｎｃ（ｂ））となる。したがって、
Ｅｎｃ（ａ＋ｂ）＝Ｅｎｃ（ａ）＊Ｅｎｃ（ｂ）
が成り立つことが好ましい。
【００２９】
第１の演算と第２の演算との準同型を保つ暗号化としては、例えば、ＥｌＧａｍａｌ暗号が知られている。ＥｌＧａｍａｌ暗号においては、ある群（ｇｒｏｕｐ）Ｇの位数をｑとし、Ｇの生成元の１つをｇとした場合に、秘密鍵は、０以上ｑ−１以下の値の整数から選択された数とすることができる。例えば、秘密鍵をｘ（０≦ｘ≦ｑ−１）とする。このとき、公開鍵は、ｇｘ（ｇのｘ乗）とすることができる。なお、Ｇの生成元とは、ｇのべき乗の列ｇ０、ｇ１、ｇ２、ｇ３、…、ｇ−１、ｇ−２、ｇ−３、…を生成することにより、Ｇの全ての元を得ることができる元ｇをいう。なお、Ｇの位数ｑは無限大である場合がある。この場合には、秘密鍵は、任意の整数から選択することができる。
【００３０】
公開鍵により平文ｍを、群Ｇの元に対応付けるために、エンコードしたものをｓｍと表わすと（例えば、ｓ＝ｇとしてエンコードを行う）、暗号化の処理の結果Ｅｎｃ（ｍ）は、暗号化の処理時に０≦ｒ≦ｑ−１を任意に選択して、Ｅｎｃ（ｍ）＝（ｇｒ, ｓｍ＊（ｇｘ）ｒ）となる。ｒが個々の平文ｍに対して異なって選択されることにより、ＥｌＧａｍａｌ暗号は確率暗号となる。
【００３１】
Ｅｎｃ（ｍ）＝（ｇｒ, ｓｍ＊（ｇｘ）ｒ）を、秘密鍵ｘを用いて復号化する場合には、ｃ１＝ｇｒ、ｃ２＝ｓｍ＊（ｇｘ）ｒとすると、ｃ２＊（ｃ１ｘ）−１を計算すればよい。
【００３２】
また、Ｅｎｃ（ａ）＝（ｇｒ, ｓａ＊（ｇｘ）ｒ）とし、Ｅｎｃ（ｂ）＝（ｇｒ´, ｓｂ＊（ｇｘ）r´）として、Ｅｎｃ（ａ）＊Ｅｎｃ（ｂ）を次のように定義する。
Ｅｎｃ（ａ）＊Ｅｎｃ（ｂ）＝（ｇｒ＊ｇｒ´，ｓａ＊（ｇｘ）ｒ＊ｓｂ＊（ｇｘ）r´）
（すなわち、（ｘ，ｙ）＊（ｚ，ｗ）＝（ｘ＊ｚ，ｙ＊ｗ）と定義する）
このとき、
（ｇｒ＊ｇｒ´，ｓａ＊（ｇｘ）ｒ＊ｓｂ＊（ｇｘ）r´）＝（ｇｒ＋ｒ´，ｓａ＋ｂ＊（ｇｘ）ｒ＋ｒ´）＝Ｅｎｃ（ａ＋ｂ）
となる。したがって、Ｅｎｃ（ａ＋ｂ）＝Ｅｎｃ（ａ）＊Ｅｎｃ（ｂ）が成り立ち、ＥｌＧａｍａｌ暗号は、第１の演算「＋」と第２の演算「＊」との準同型を保つ。
【００３３】
第１の演算と第２の演算との準同型を保つ別の暗号方法としては、例えばＰａｉｌｌｉｅｒ暗号が知られている。
【００３４】
図３は、データ暗号化部２０２の暗号化の処理を説明するための図である。符号３０１は、Ｍ個の要素であるａｎ１、ａｎ２、…、ａｎＭにより構成される第ｎデータを表わすとする。データ暗号化部２０２が、このｎ番目のデータを暗号化した結果は、符号３０２により表わされ、Ｅｎｃ（ａｎ１）、Ｅｎｃ（ａｎ２）、…、Ｅｎｃ（ａｎＭ）というＭ個の暗号化された要素となる。暗号化された複数の要素により構成されるデータを、「暗号化ベクトルデータ」または単に「暗号化ベクトル」という。
【００３５】
暗号化データ送信部２０４は、データ暗号化部２０２により暗号化されたデータ（暗号化ベクトルデータ）を含むデータをデータベースサーバ１０２へ送信する。例えば、暗号化データ送信部２０４は、通信網を介してデータベースサーバ１０２と通信を行い、暗号化ベクトルデータを含むデータを送信する。あるいは、暗号化データ送信部２０４は、暗号化ベクトルデータを含むデータを記録装置に送信し、記録装置が暗号化されたデータを記録媒体に記録し、記録媒体がデータベースサーバ１０２に向けて輸送されてもよい。
【００３６】
暗号化データ送信部２０４は、情報提供装置１０１のメモリや記憶装置に記憶されたデータ暗号化部２０２による暗号化の処理の結果を読み出し、暗号化の処理の結果を入出力装置に送信し、データ暗号化部２０２により暗号化されたデータを送信する。
【００３７】
なお、暗号化データ送信部２０４を「暗号化要素送信部（２０４）」と呼称する場合がある。
【００３８】
図４は、データベースサーバ１０２の機能ブロック図を示す。データベースサーバ１０２は、データベース４０１と、暗号化データ受信部４０２と、データベース管理部４０３と、受信部４０４と、計算処理部４０５と、送信部４０６とを備える。なお、データベースサーバ１０２は、ＣＰＵ、メモリ、記憶装置、入出力装置およびそれらを接続するバスを含む計算機にプログラムを動作させることにより実現が可能である。また、データベースサーバ１０２を、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）などのハードウェアの構成要素を組み合わせて実現し、プログラムを用いる必要を無くすることもできる。
【００３９】
データベース４０１は、情報提供装置１０１から送信された暗号化ベクトルデータを含む１または複数のデータを格納する。したがって、データベース４０１は、１または複数の暗号化ベクトルデータを格納するということができる。暗号化ベクトルデータを含むデータの格納は、例えば、データベースサーバ１０２の記憶装置が行うことができる。
【００４０】
図５は、データベース４０１にそれぞれがＭ個の暗号化された要素を有するＮ個の暗号化ベクトルデータが格納された状態の一例図である。列５０１は、暗号化ベクトルデータを一意に識別するための番号が格納され、列５０２に暗号化ベクトルデータが格納されている。列５０１と列５０２とによりテーブルが形成される。
【００４１】
図６は、データベース４０１にそれぞれがＭ個の暗号化された要素を有するＮ個の暗号化ベクトルデータが格納された状態の別の一例図である。図６においては、図５に示すテーブルに、列６０１が追加されたテーブルが示されている。これにより、列６０１に格納されている例えばＥｎｃ（Ｖ３）が、Ｅｎｃ（ａ３１）、Ｅｎｃ（ａ３２）、…、Ｅｎｃ（ａ３Ｍ）という暗号化ベクトルデータに関連付けられている。これにより、データベース４０１に対するクエリの計算結果に列６０１に格納されているデータを含めることができる。すなわち、クエリが列５０２に格納された暗号化ベクトルデータをキーとする検索を行うという計算を表わしているときに、計算結果である検索結果に列６０１に格納され、暗号化ベクトルデータに関連付けられている値を含めることができる。なお、図６においては、列６０１に格納されているデータは、暗号化の処理がされたデータとなっているが、列６０１に格納されているデータは暗号化の処理がされていなくてもよい。
【００４２】
暗号化データ受信部４０２は、暗号化データ送信部２０４が送信した暗号化ベクトルデータを含むデータを受信する。例えば、暗号化データ送信部２０４が通信網を介してデータを送信する場合には、暗号化データ受信部４０２はその通信網に接続された入出力装置を介してデータを受信する。また、暗号化データ送信部２０４により、データが記録媒体に格納されている場合には、暗号化データ受信部４０２は、その記録媒体を読み取る読取装置からデータを受信する。受信されたデータは、一時的にメモリに記憶されてもよい。
【００４３】
データベース管理部４０３は、暗号化データ受信部４０２が受信したデータをデータベース４０１に格納する。例えば、一時的にメモリに記憶されているデータをＣＰＵが読み出し、記憶装置に格納する。この結果、データベース４０１には、例えば図５、図６に示されるテーブルが格納され、そのテーブルに１または複数の暗号化ベクトルデータが格納される。
【００４４】
受信部４０４は、クエリ装置１０３よりクエリを受信する。クエリは、データベース４０１に格納された暗号化ベクトルデータに対して行うべき計算を表わす。本実施形態では、クエリは、データベース４０１に格納されている暗号化ベクトルデータの要素の個数と同じ個数の値により構成されるベクトルデータであることが好ましい。もし、クエリを構成する値の個数が、データベース４０１に格納されている暗号化ベクトルデータの要素の個数と異なる場合には、クエリを複数のベクトルデータに分割したり、値のパディングを行ったりして、データベース４０１に格納されている暗号化ベクトルデータの要素の個数に合致させることが好ましい。あるいは、クエリを構成する値の個数が、データベース４０１に格納されている暗号化ベクトルデータの要素の個数と異なる場合には、エラーとしてもよい。なお、以下では、クエリが１または複数のベクトルを含む場合、個々のベクトルを「クエリベクトル」または「クエリベクトルデータ」という場合がある。
【００４５】
受信部４０４は、クエリ装置１０３が通信網を介してクエリを送信する場合には、その通信網に接続された入出力装置を介してクエリを受信する。あるいは、受信部４０４は、クエリ装置１０３によりクエリが記録された記憶媒体を読み取る読取装置からクエリを受信してもよい。受信されたクエリは、一時的にメモリに記憶されてもよい。計算処理部４０５の処理において、クエリベクトルが複数のセグメントに分割される場合には、受信部４０４は、クエリベクトルの分割の情報も受信してもよい。例えば、受信部４０４は、それぞれのセグメントが含むデータの数（または、それぞれのセグメントの長さ若しくはセグメントの区切り位置）の情報を受信してもよい。
【００４６】
計算処理部４０５は、受信部４０４が受信したクエリに応じて、データベース４０１に格納された暗号化データに対して計算を行う。データベースサーバ１０２が計算機により実現される場合には、クエリに応じて暗号化データに対して計算を行うプログラムが記憶装置からメモリに読み込まれ、そのプログラムがＣＰＵにより実行されることになる。計算結果は、データベースサーバ１０２を実現する計算機のメモリや記憶装置に格納される。
【００４７】
図７は、計算処理部４０５による計算を説明するための図である。データベース４０１には暗号化ベクトルデータが格納され、クエリも１または複数のベクトルデータ（１または複数のクエリベクトル）を含む場合には、計算処理部４０５が行う計算は、基本的には、データベース４０１に格納されている暗号化ベクトルデータそれぞれと、クエリベクトルデータそれぞれとの計算をすることになる。また、クエリのベクトルデータを複数のセグメントに分割した場合、暗号化ベクトルデータも同じく複数のセグメントに分割し、クエリデータのクエリベクトルそれぞれと、暗号化ベクトルデータの対応するセグメントとの計算をすることが可能である。この場合、「暗号化ベクトルデータも同じく複数のセグメントに分割する」とは、クエリのクエリベクトルの複数のセグメントのセグメント列中の第ｉセグメントの長さと、暗号化ベクトルデータの複数のセグメントのセグメント列中の第ｉセグメントの長さが同じになることをいう。また、「クエリベクトルデータそれぞれと、暗号化ベクトルデータの対応するセグメントとの計算をする」とは、クエリベクトルデータの複数のセグメントのセグメント列中の第ｉセグメントと、暗号化ベクトルデータの複数のセグメントのセグメント列中の第ｉセグメントとの要素の積の値を計算し、計算した値の積を計算することである。
【００４８】
図７において、クエリベクトルデータの一つが、符号７０１に示されるように、ｑ１、ｑ２、…、ｑＭとなっている場合に、データベース４０１に格納されている第ｉベクトルデータＥｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）が読み出されると、計算処理部４０５は、（ｑ１＊Ｅｎｃ（ａｉ１））＊（ｑ２＊Ｅｎｃ（ａｉ２））＊…＊（ｑＭ＊Ｅｎｃ（ａｉＭ））を計算することができる。また、計算処理部４０５は、ｑ１＊Ｅｎｃ（ａｉ１）、ｑ２＊Ｅｎｃ（ａｉ２）、…、ｑＭ＊Ｅｎｃ（ａｉＭ）のＭ個の項の中から選ばれる任意の項を用いる計算をすることができる。特に、ｑ１、ｑ２、…、ｑＭが０または１であれば、Ｅｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）の中から選ばれる項の任意の項の積を計算することができる。この計算結果は、ａｉ１、ａｉ２、…、ａｉＭの中から選ばれる項の任意の項の和に対する暗号化の処理の結果を、Ｅｎｃに対応する復号化の処理を行うことなく、計算することができる。
【００４９】
また、例えばＥｎｃ（ａ＋ｂ）＝Ｅｎｃ（ａ）＊Ｅｎｃ（ｂ）であるのでＥｎｃ（２ａ）＝Ｅｎｃ（ａ＋ａ）＝Ｅｎｃ（ａ）＊Ｅｎｃ（ａ）＝Ｅｎｃ（ａ）２などであるので、ｑ１、ｑ２、…、ｑＭが整数であれば、Ｅｎｃ（ｑ１ａｉ１＋ｑ２ａｉ２＋…＋ｑＭａｉＭ）＝Ｅｎｃ（ａｉ１）ｑ１＊Ｅｎｃ（ａｉ２）ｑ２＊…＊Ｅｎｃ（ａｉＭ）ｑＭとなる。すなわち、ｑ１、ｑ２、…、ｑＭとａｉ１、ａｉ２、…、ａｉＭとの内積（ユークリッド計量）を暗号化した値（Ｅｎｃ（ｑ１ａｉ１＋ｑ２ａｉ２＋…＋ｑＭａｉＭ））を、ａｉ１、ａｉ２、…、ａｉＭそれぞれを暗号化したＥｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）に対して演算＊を適用することにより算出することができる。
【００５０】
別言すると、ｑ１、ｑ２、…、ｑＭに基づいて、ａｉ１、ａｉ２、…、ａｉＭの各要素に対して＋の演算を行なって得られる計算結果（ｑｊａｉｊの和）を暗号化した暗号化計算結果を、暗号化ベクトルＥｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）の各データに対して、ｑ１、ｑ２、…、ｑＭに基づいて＊の演算を行なって得られる冪の値、また、複数の冪の値に対する＊による演算結果を得ることができる。暗号化ベクトルＥｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）の各データに対して、ｑ１、ｑ２、…、ｑＭに基づいて＊の演算を行なう場合、復号化を行なう必要がなくなる。
【００５１】
また、上記では、ユークリッド計量の計算の例について説明したが、ミンコフスキー計量も同様に計算することができる。
【００５２】
ここで、ａｉ１、ａｉ２、…、ａｉＭの全てが、整数０および整数１のいずれかであるとし、ｑ１、ｑ２、…、ｑＭも全てが、０および１のいずれかであるとする。
【００５３】
このとき、例えば、ｑ１、ｑ２、…、ｑＭの全てが１であれば、（ｑ１＊Ｅｎｃ（ａｉ１））＊（ｑ２＊Ｅｎｃ（ａｉ２））＊…＊（ｑＭ＊Ｅｎｃ（ａｉＭ））＝Ｅｎｃ（ａｉ１）＊Ｅｎｃ（ａｉ２）＊Ｅｎｃ（ａｉＭ）＝Ｅｎｃ（ａｉ１＋ａｉ２＋…＋ａｉＭ）となり、ａｉ１＋ａｉ２＋…＋ａｉＭは、ａｉ１、ａｉ２、…、ａｉＭの中の１の個数となるので、Ｅｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）のそれぞれの復号化の処理をしなくても、ａｉ１、ａｉ２、…、ａｉＭの中の１の個数に対して、暗号化の処理を行って得られる値を計算することができる。
【００５４】
また、ｑ１、ｑ２、…、ｑＭの全てが１でなくても、
【数１】
2016129390.tif 000003
となるので、ｑｊとａｉｊとの両方が１となる添え字ｊの個数を暗号化した値を計算することができる。なお、左辺は、ｑｊ＝１となるｊについて、Ｅｎｃ（ａｉｊ）の＊による演算結果を表わす。すなわち、ｑｊ＝１となるｊが１、３および４であれば、左辺は、Ｅｎｃ（ａｉ１）＊Ｅｎｃ（ａｉ３）＊Ｅｎｃ（ａｉ４）を表わすことになる。
【００５５】
そこで、ベクトルａｉ１、ａｉ２、…、ａｉＭをＡと記し、クエリベクトルｑ１、ｑ２、…、ｑＭをＱと記す場合、ＡとＱとの類似度を表わす指標として様々な指標が知られている。例えば、このような指標の１として、以下の式により計算されるTversky Indexが知られている。
｜Ａ∩Ｑ｜／（｜Ａ∩Ｑ｜＋α（｜Ａ｜−｜Ａ∩Ｑ｜）＋β（｜Ｑ｜−｜Ａ∩Ｑ｜））
ここに、｜Ａ∩Ｑ｜は、ｑｊとａｉｊとの両方が１となる添え字ｊの個数であり、｜Ａ｜は、ａｉ１、ａｉ２、…、ａｉＭの中の１の個数であり、｜Ｑ｜は、ｑ１、ｑ２、…、ｑＭの中の１の個数であり、αおよびβのそれぞれは、正の数である。また、αおよびβのそれぞれは、正の整数または有理数であるとすることができる。
【００５６】
θを０以上の数として、Tversky Indexがθ以上であるとする。すなわち、
｜Ａ∩Ｑ｜／（｜Ａ∩Ｑ｜＋α（｜Ａ｜−｜Ａ∩Ｑ｜）＋β（｜Ｑ｜−｜Ａ∩Ｑ｜））≧θ
の式が得られる。この式を変形すると、
｛１−θ＋θ（α＋β）｝｜Ａ∩Ｑ｜−αθ｜Ａ｜−βθ｜Ｑ｜≧０    （２）
を得ることができる。ここで、整数の演算に置き換えるために、α´、β´、θ´、θｎを、
α＝α´／θｎ、β＝β´／θｎ、θ＝θ´／θｎ
を満たす自然数であるとすると、式（２）は、以下の式（３）に変形できる。この式（３）により、Tversky Indexに対応する値を計算することができる。
γ１｜Ａ∩Ｑ｜＋γ２｜Ａ｜＋γ３｜Ｑ｜≧０    （３）
ここに
γ１＝θｎ（θｎ−θ´）＋θ´（α´＋β´）
γ２＝−α´θ´
γ３＝−β´θ´
である。したがって、式（２）が成り立てば、式（３）が成り立つこととなる。
【００５７】
ここで、｜Ａ∩Ｑ｜は、Ａの第ｉ要素とＱの第ｉ要素との両方が１となるｉの数であるので、Ｅｎｃ（｜Ａ∩Ｑ｜）は、式（１）より
【数２】
2016129390.tif 000004
により計算される。Ｅｎｃ（｜Ａ｜）は、ａｉ１＋ａｉ２＋…＋ａｉＭに暗号化の処理をしたものであるので、ａｉ１、ａｉ２、…、ａｉＭにそれぞれ暗号化の処理をして得られる値の積である
【数３】
2016129390.tif 000005
により計算される。Ｅｎｃ（｜Ｑ｜）は、ｑ１＋ｑ２＋…＋ｑＭに暗号化の処理をしたものであるので、ｑ１、ｑ２、…、ｑＭそれぞれを暗号化の処理をして得られる値の積である
【数４】
2016129390.tif 000006
により計算される。ここで、Ｅｎｃが公開鍵による暗号化の処理であれば、Ｅｎｃ（｜Ａ∩Ｑ｜）、Ｅｎｃ（｜Ａ｜）およびＥｎｃ（｜Ｑ｜）のそれぞれは復号化の処理を実行しなくても計算が可能であり、データベースサーバ１０２において計算することができる。したがって、
Ｅｎｃ（γ１｜Ａ∩Ｑ｜＋γ２｜Ａ｜＋γ３｜Ｑ｜）＝Ｅｎｃ（｜Ａ∩Ｑ｜）γ１＊Ｅｎｃ（｜Ａ｜）γ２＊Ｅｎｃ（｜Ｑ｜）γ３
により、式（３）の左辺をデータベースサーバ１０２において計算することができる。なおＥｎｃが情報提供装置１０１の運営者の秘密鍵による暗号化の処理であっても、ＱそのものまたはＱの中の１の数をデータベースサーバ１０２から情報提供装置１０１の運営者の秘密鍵を格納している装置に送信し、その装置において、Ｅｎｃ（ｑ１＋ｑ２＋…＋ｑＭ）を計算させて返信させることにより、データベースサーバ１０２は、Ｅｎｃ（｜Ｑ｜）を取得することができる。
【００５８】
なお、群Ｇは、生成元をｇとし、位数がｑであるので、整数０を群Ｇの元ｇ０（すなわち、Ｇの単位元）に対応付け、正の整数ｎをｇｎに対応付け、負の整数ｍをｇｑ＋ｍに対応付けることにより、式（３）の左辺を群Ｇの中での演算により計算することができ、式（３）が成り立つかどうかの演算も可能である。
【００５９】
以上においては、クエリベクトルｑ１、ｑ２、…、ｑＭと暗号化ベクトルデータＥｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）とを用いた計算について説明した。さらに、上述したクエリベクトルのセグメントと暗号化ベクトルデータのセグメントとを用いた計算を一般化し、クエリベクトルの部分ベクトルと暗号化ベクトルデータの部分ベクトルとを用いた計算をすることもできる。ここにベクトルｖ１、ｖ２、…、ｖＭの部分ベクトルとは、集合｛１、２、…、Ｍ｝の部分集合の要素を添え字として用いて｛ｖ１、ｖ２、…、ｖＭ｝から要素を選択してベクトルとしたものである。例えば、Ｍ≧６であるとき、｛２、４、６｝の要素を添え字として用いて｛ｖ２、ｖ４、ｖ６｝を選択して部分ベクトルとする。
【００６０】
また、集合｛１、２、…、Ｍ｝を複数の部分集合に分割し、それぞれの部分集合に対応するクエリベクトルの部分ベクトルと暗号化ベクトルデータの部分ベクトルとを用いた複数の種類の値の計算を行い、計算された複数の値の積を計算することにより、クエリベクトルと暗号化ベクトルデータの計算をすることができる。
【００６１】
例えば、クエリベクトルｑ１、ｑ２、…、ｑＭが複数のセグメントに分割されているとする。例えば、１より大きくＭ未満の数のＬ個の数の列ｕ1、ｕ2、…、ｕLであり、１＜ｕ1＜ｕ2＜…＜ｕL＜Ｍとなる列が与えられたとする。このような数の列により、クエリベクトルを複数のセグメントに分割することができる。すなわち、クエリベクトルの第１セグメントをｑ１からｑｕ1まで、クエリベクトルの第２セグメントをｑｕ1＋１からｑｕ2まで、…、クエリベクトルの第Ｌ＋１セグメントをｑｕL＋１からｑＭとすることができる。この場合、クエリベクトルのセグメントと暗号化ベクトルデータのセグメントの要素ごとの積を計算することができる。すなわち、クエリの複数のセグメントの分割に対応させて、暗号化ベクトルデータＥｎｃ（ａｉ１）、Ｅｎｃ（ａｉ２）、…、Ｅｎｃ（ａｉＭ）を、暗号化ベクトルデータの第１セグメントがＥｎｃ（ａｉ１）からＥｎｃ（ａｉｕ1）まで、第２セグメントがＥｎｃ（ａｉｕ1＋１）からＥｎｃ（ａｉｕ2）まで、…、第Ｌ＋１セグメントがＥｎｃ（ａｉｕL＋１）からＥｎｃ（ａｉＭ）まで、となるように分割する。そして、クエリベクトルの第ｉセグメントの要素と暗号化ベクトルデータの第ｉセグメントの要素（１≦ｉ≦Ｌ＋１）とのＬ＋１個の積の値を、計算処理部４０５による計算結果とすることができる。
【００６２】
計算処理部４０５は、クエリベクトルとデータベース４０１に格納されている暗号化ベクトルデータのそれぞれとの計算結果を生成することができる。計算としては、上述のように、セグメントの対応する要素の積などがある。また、複数のクエリベクトルが受信部４０４により受信された場合には、複数のクエリベクトルのそれぞれと、データベース４０１に格納されている暗号化ベクトルデータのそれぞれとの計算結果を計算する。
【００６３】
なお、複数のクエリベクトルが受信部４０４により受信される場合としては、以下に説明するように、クエリ装置１０３においてクエリの難読化の処理が行われる場合がある。すなわち、クエリベクトルを複数のセグメントに分割し、クエリベクトルと同じ長さのランダムなデータを有し、クエリと同じく複数のセグメントに分割した１または複数のランダムデータベクトルとクエリとの間で、セグメントのシャッフルが行われる場合である。この場合、クエリの第ｉセグメントは、ランダムデータベクトルの第ｉセグメントとなるようにシャッフルがされる。クエリベクトルをＮ個のセグメントに分割し、クエリベクトルと同じ長さのランダムなデータを有し、クエリと同じく複数のセグメントに分割した１または複数のランダムデータベクトルとクエリとの間で、セグメントのシャッフルが行われて生成される複数のベクトルを、Ｎ−ランダム化ベクトルという。また、Ｎは、１＜ｕ1＜ｕ2＜…＜ｕL＜Ｍとなる数列ｕ1、ｕ2、…、ｕLを表わしてもよい。このとき、上述のＮ−ランダム化ベクトルは、Ｌ＋１−ランダム化ベクトルまたは（ｕ1、ｕ2、…、ｕL）−ランダム化ベクトルと表記することができる。
【００６４】
送信部４０６は、計算処理部４０５による計算結果を、送信する。例えば、データベースサーバ１０２とクエリ装置１０３とが通信網を介して接続されていれば、送信部４０６は、その通信網を介して計算処理部４０５による計算結果をクエリ装置１０３に送信する。また、送信部４０６は、記憶媒体に計算処理部４０５による計算結果を記録する記録装置に計算処理部４０５による計算結果を送信してもよい。送信部４０６は、計算処理部４０５による計算結果をメモリや記憶装置から読み出し、入力装置に出力することにより、計算結果を送信する。
【００６５】
図８は、クエリ装置１０３の機能ブロック図を示す。クエリ装置１０３は、クエリ取得部８０１と、クエリ難読化部８０２と、クエリ送信部８０３と、計算結果受信部８０４と、計算結果送信部８０５と、復号結果受信部８０６と、逆難読化部８０７と、難読化情報格納部８０８と、出力部８０９とを備える。なお、クエリ装置１０３は、ＣＰＵ、メモリ、記憶装置、入出力装置およびそれらを接続するバスを含む計算機にプログラムを動作させることにより実現が可能である。クエリ装置１０３の具体的な形態としては、パーソナルコンピュータ、スマートフォンなどを挙げることができる。また、クエリ装置１０３を、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）などのハードウェアの構成要素を組み合わせて実現し、プログラムを用いる必要を無くすることもできる。
【００６６】
クエリ取得部８０１は、複数のデータを有するクエリを取得する。例えば、クエリ装置１０３のＧＵＩなどを介してクエリを取得する。取得されたクエリにより、クエリベクトルが得られる。すなわち、複数のデータが取得されることにより、これらのデータによりクエリベクトルが得られる。得られたクエリベクトルは、クエリ装置１０３のメモリや記憶装置に記憶される。
【００６７】
クエリ難読化部８０２は、クエリベクトルの難読化の処理を行う。クエリベクトルの難読化の処理とは、具体的には次の処理を意味することができる。
（ステップ１）クエリベクトルを複数のセグメントに分割する処理を行う。例えば上述のように、Ｍ以下の数のＬ個の数の列ｕ1、ｕ2、…、ｕLであり、１＜ｕ1＜ｕ2＜…＜ｕL＜Ｍとなる列が与えられ、クエリベクトルがＬ＋１のセグメントに分割される。
（ステップ２）複数の難読化クエリベクトルを生成する。クエリベクトルと同じ長さのランダムなデータを有し、クエリベクトルと同じく複数のセグメントに分割した１または複数のランダムデータベクトルを用意する。そして、ランダムデータベクトルとクエリベクトルとの間で、セグメントのシャッフルを行う（クエリベクトルのセグメントとランダムデータベクトルのセグメントとを交換する操作を１回以上行う）。この場合、クエリベクトルの第ｉセグメントは、ランダムデータベクトルの第ｉセグメントとなるようにシャッフルがされる。
【００６８】
上記の（ステップ１）および（ステップ２）の処理により得られる複数のベクトルを複数の「Ｌ＋１−ランダム化ベクトル」または「（ｕ1、ｕ2、…、ｕL）−ランダム化ベクトル」と呼称することが可能である。
【００６９】
クエリベクトルの難読化の処理により、複数のデータを有するクエリベクトルを複数のセグメントに分割し、複数のセグメントのいずれかとランダムデータを含むランダムセグメントとのいずれか１以上を含む複数のベクトルを得ることができる。また、この複数のベクトルから、ランダムセグメント以外を選択することにより、クエリベクトルが復元可能となる。
【００７０】
図９（Ａ）〜図９（Ｄ）は、難読化クエリ（Ｌ＋１−ランダム化ベクトル）の生成について説明するための図である。図９（Ａ）に示すように、Ｍ個の要素ｑ１、ｑ２、…、ｑＭを含むクエリ９０１が取得され、メモリや記憶装置に記憶されたとする。
【００７１】
上記のステップ１の処理に対応し、図９（Ｂ）に示すように、クエリ９０１をＬ＋１個のセグメントＢ１（９１１）、Ｂ２（９１２）、…、ＢＬ＋１（９１３）に分割する。
【００７２】
上記のステップ２の処理に対応し、最終的に得られる難読化クエリベクトルの数を例えば２とし、その２つの難読化クエリベクトルを、図９（Ｃ）のように、符号９３１と９３２とにより示すことにする。この場合、最初の段階において、例えば符号９３１をクエリベクトルとし、符号９３２をランダムデータベクトルとした場合、クエリベクトル９３１とランダムデータベクトル９３２との間でセグメントのシャッフルを行う。例えば、図９（Ｃ）においては、クエリベクトルの第１セグメントＢ１とランダムデータベクトルの第１セグメントとを交換する（図９（Ｃ）では、Ｂ２とＢＬ＋１とはランダムデータベクトル９３２のセグメントと交換されていないが、Ｂ３、Ｂ４、…、ＢLの中から選択されるセグメントをランダムデータベクトルのセグメントと交換することができる）。
【００７３】
難読化の処理により、図９（Ｃ）においては、クエリベクトルの第１セグメントＢ１（９１１）は、難読化クエリベクトル９３２の第１セグメントとして配置され、クエリベクトルの第２セグメントＢ２（９１２）は、難読化クエリベクトルの９３１の第２セグメントとして配置され、…、クエリベクトルの第Ｌ＋１セグメントは、難読化クエリベクトル９３１の第Ｌ＋１セグメントとして配置されている。そして、クエリベクトルのセグメントが配置されない難読化クエリのセグメントは、ランダムな値を有するセグメントとなる。
【００７４】
図９（Ｄ）は、クエリベクトルの各セグメントが複数の難読化クエリベクトルのいずれの難読化クエリベクトルのセグメントとして配置されたかを表わす情報の例である。すなわち、列９５１には、クエリベクトルのセグメントの番号が格納され、列９５２には、難読化クエリベクトルの番号（複数のＬ＋１−ランダム化ベクトルのいずれかの識別子）が格納される。このような情報を難読化情報または生成情報という。難読化情報には、それぞれのセグメントの長さの情報を含むこともできる。
【００７５】
クエリ難読化部８０２により、クエリベクトルの難読化の処理が行われると、難読化情報も生成され、生成された難読化情報は、難読化情報格納部８０８に格納される。例えば、メモリや記憶装置に難読化情報が記憶される。また、このとき、クエリ取得部８０１が取得したクエリと関連付けて難読化情報が記憶されてもよい。
【００７６】
クエリ送信部８０３は、クエリ難読化部８０２による難読化により得られた難読化クエリをデータベースサーバ１０２に送信する。例えば、クエリ送信部８０３は、通信網を介して、難読化クエリをデータベースサーバ１０２に送信する。あるいは、クエリ送信部８０３は、記録媒体に書き込みを行う装置に難読化クエリを送信し、難読化クエリが記録された記録媒体がデータベースサーバ１０２に発送されてもよい。なお、クエリ送信部８０３は、各セグメントの長さの情報も送信してもよい。また、例えば、Tversky Indexに関する計算がデータベースサーバ１０２において行われるのであれば、α´、β´、θ´、θｎなどがパラメータとして送信されてもよい。
【００７７】
計算結果受信部８０４は、クエリ送信部８０３による難読化クエリの送信に対応して、データベースサーバ１０２より計算結果を受信する。例えば、計算結果受信部８０４は、通信網を介して、計算結果を受信し、受信した計算結果をメモリや記憶装置に記憶する。あるいは、データベースサーバ１０２から発送された記録媒体を読み取る装置から計算結果を受信し、受信した計算結果をメモリや記憶装置に記憶する。
【００７８】
計算結果送信部８０５は、計算結果受信部８０４により受信された計算結果の一部または全てを、復号装置１０４に送信する。クエリ装置１０３においては、難読化クエリのどのセグメントがランダムデータセグメントのセグメントであるかの情報を難読化情報などとして有しているので、ランダムデータセグメントのセグメントに関する計算結果は復号装置１０４に送信する必要はない。ただし、復号装置１０４が、復号の結果から、どのような計算が行われたかを推測することを困難とするために、ランダムデータセグメントのセグメントについての計算結果を復号装置１０４に送信するのが好ましい。計算結果送信部８０５は、通信網を介して、計算結果を送信する。あるいは、記録媒体に計算結果を書き込む記録装置に計算結果を送信し、計算結果が記録された記録媒体が復号装置１０４に発送されてもよい。
【００７９】
復号結果受信部８０６は、復号装置１０４から送信される復号結果を受信する。例えば、復号結果受信部８０６は、通信網を介して復号結果を受信する。あるいは、復号結果が記録された記録媒体を読み取る装置から復号結果を受信する。受信された復号結果は、メモリや記憶装置に記憶される。
【００８０】
なお、通信網を介して、計算結果送信部８０５による計算結果の送信、および、復号結果受信部８０６による復号結果の受信を行う場合には、クエリ装置１０３と復号装置１０４とが直接通信を行うと、復号装置１０４が、クエリ装置１０３のＩＰアドレスなどを得ることができる。これにより、クエリ装置１０３がどの組織に属しているかを知ることができる。このようなことを防ぐために、クエリ装置１０３と復号装置１０４との通信は、別のサーバを介して行い、クエリ装置１０３の情報が復号装置１０４に知られないようにするのが好ましい。例えば、データベースサーバ１０２を介してクエリ装置１０３と復号装置１０４との間の通信が行われるようになっていてもよい。
【００８１】
逆難読化部８０７は、復号結果受信部８０６により受信された復号結果を、難読化情報格納部８０８に格納された難読化情報を用いて、難読化の処理の逆の処理を行う。
【００８２】
すなわち、難読化クエリベクトルのそれぞれから、各セグメントについての計算結果がデータベースサーバ１０２から受信され、復号装置１０４に送信される。復号装置１０４から受信される復号の結果から、難読化情報を参照することにより、ランダムデータベクトルのセグメントについての復号の結果を除去することができ、クエリベクトルの各セグメントについての計算結果を得ることができる。
【００８３】
例えば、クエリの全てのデータを１とするクエリベクトルを複数のセグメントＢ１、Ｂ２、…、ＢL＋１に分割したとする。これらの複数のセグメントそれぞれについての計算結果として、データベースサーバ１０２より、Ｅｎｃ（ｂ１）、Ｅｎｃ（ｂ２）、…、Ｅｎｃ（ｂＬ＋１）が得られたとすると、Ｅｎｃ（ｂ１）、Ｅｎｃ（ｂ２）、…、Ｅｎｃ（ｂＬ＋１）を復号装置１０４に送信し、復号させることにより、ｂ１、ｂ２、…、ｂＬ＋１を得ることができ、暗号化ベクトルデータの暗号化前データの各セグメントの１の数に関する情報を得ることができる。Ｅｎｃ（ｂ１）、Ｅｎｃ（ｂ２）、…、Ｅｎｃ（ｂＬ＋１）それぞれを復号装置１０４に送信するかわりにＥｎｃ（ｂ１）＊Ｅｎｃ（ｂ２）＊…＊Ｅｎｃ（ｂＬ＋１）を計算してその計算結果を復号装置１０４に送信しても、暗号化ベクトルデータの暗号化の処理前のデータの各セグメントの中の１の数に関する情報を得ることができる。
【００８４】
同様に、クエリデータと暗号化ベクトルデータの暗号化前のデータとのTversky Indexに関する情報を得ることもできる。また、上述のように、ユークリッド計量やミンコフスキー計量に関する情報を得ることもできる。
【００８５】
出力部８０９は、逆難読化部８０７の処理の結果を出力する。例えば、クエリ装置１０３のディスプレイに、逆難読化部８０７の処理の結果を、表示する。
【００８６】
図１０は、復号装置１０４の機能ブロック図を示す。復号装置は、復号鍵格納部１００１と、結果受信部１００２と、復号部１００３と、復号結果送信部１００４とを備える。なお、復号装置１０４は、ＣＰＵ、メモリ、記憶装置、入出力装置およびそれらを接続するバスを含む計算機にプログラムを動作させることにより実現が可能である。また、復号装置１０４を、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）などのハードウェアの構成要素を組み合わせて実現することによりプログラムを用いる必要を無くすこともできる。また、復号装置１０４と情報提供装置１０１とを一つの装置とすることもできる。
【００８７】
復号鍵格納部１００１は、復号鍵を記憶する。例えば、メモリや記憶装置に復号鍵が記憶される。復号鍵は、情報提供装置１０１のデータ暗号化部２０２による暗号化の処理に対応する復号化の処理を行うための鍵である。情報提供装置１０１のデータ暗号化部２０２による暗号化の処理において、公開鍵が用いられるのであれば、復号鍵は、その公開鍵に対応する秘密鍵となる。
【００８８】
結果受信部１００２は、クエリ装置１０３より、データベースサーバ１０２から送信された計算結果を、受信する。例えば、結果受信部１００２は、通信網を介して計算結果を受信し、受信した計算結果をメモリや記憶装置に記憶する。
【００８９】
復号部１００３は、復号鍵格納部１００１に格納された復号鍵を用いて、結果受信部１００２により受信された計算結果を復号化の処理を実行する。復号化の処理を実行して得られる結果である復号結果は、メモリや記憶装置に記憶される。
【００９０】
復号結果送信部１００４は、復号部１００３により復号された結果をクエリ装置に送信する。例えば、復号結果送信部１００４は、通信網を介して復号結果を送信する。
【００９１】
図１１は、情報提供装置１０１の処理のフローチャートの一例である。ステップＳ１１０１の処理として、データ取得部２０１を動作させることにより、データを取得する。ステップＳ１１０２の処理として、データ暗号化部２０２を動作させることにより、データを暗号化し暗号化ベクトルデータを生成する。ステップＳ１１０３の処理として、暗号化データ送信部２０４を動作させることにより、暗号化ベクトルデータを送信する。
【００９２】
図１２は、データベースサーバ１０２が、暗号化ベクトルデータを受信し、データベース４０１に格納するまでの処理のフローチャートである。ステップＳ１２０１の処理として、暗号化データ受信部４０２を動作させることにより、暗号化ベクトルデータを受信する。ステップＳ１２０２の処理として、データベース管理部４０３を動作させることにより、暗号化データをデータベース４０１に格納する。
【００９３】
図１３は、データベースサーバ１０２が、難読化クエリを受信してから、計算結果を送信するまでの処理のフローチャートである。ステップＳ１３０１の処理として、受信部４０４を動作させることにより、難読化クエリを受信する。ステップＳ１３０２の処理として、計算処理部４０５を動作させることにより、難読化クエリのベクトルのセグメントごとに計算を行う。ステップＳ１３０３の処理として、送信部４０６を動作させることにより、計算結果を送信する。
【００９４】
図１４は、クエリ装置１０３の処理を説明するフローチャートである。ステップＳ１４０１の処理として、クエリ取得部８０１を動作させることにより、クエリを取得する。ステップＳ１４０２の処理として、クエリ難読化部８０２を動作させることにより、難読化クエリを生成する。このとき、難読化情報が難読化情報格納部８０８に格納される。ステップＳ１４０３の処理として、クエリ送信部８０３を動作させることにより、難読化クエリを送信する。ステップＳ１４０４の処理として、計算結果受信部８０４を動作させることにより、計算結果を取得する。ステップＳ１４０５の処理として、計算結果送信部８０５を動作させることにより計算結果を送信する。ステップＳ１４０６の処理として、復号結果受信部８０６を動作させることにより、復号化の処理の結果を受信する。ステップＳ１４０７の処理として、逆難読化部８０７を動作させることにより、難読化の逆の処理を行う。ステップＳ１４０８の処理として、出力部８０９を動作させることにより、難読化の逆の処理の出力を行う。
【００９５】
図１５は、復号装置１０４の処理を説明するフローチャートである。ステップＳ１５０１の処理として、結果受信部１００２を動作させることにより、計算結果を受信する。ステップＳ１５０２の処理として、復号部１００３を動作させることにより、復号化の処理を行う。ステップＳ１５０３の処理として、復号結果送信部１００４を動作させることにより、復号化の処理の結果を送信する。
【００９６】
図１６は、本発明の一実施形態に係るシステムのデータの流れを説明するための図である。
【００９７】
（ステップ１）情報提供装置１０１からデータベースサーバ１０２へ、暗号化ベクトルデータが送信され、データベースサーバ１０２のデータベース４０１へ格納される。暗号化データの送信は、必要に応じて随時行われる。また、必要に応じて、データベース４０１に格納された暗号化データの削除、変更なども行われてもよい。
【００９８】
（ステップ２）クエリ装置１０３からデータベースサーバ１０２に難読化クエリが送信される。データベースサーバ１０２が難読化クエリを受信すると、難読化クエリのセグメントごとに計算がされる。
【００９９】
（ステップ３）データベースサーバ１０２からクエリ装置１０３に計算結果が送信される。
【０１００】
（ステップ４）クエリ装置１０３から、ステップ３で受信された計算結果が復号装置１０４に送信される。
【０１０１】
（ステップ５）復号装置１０４において復号化の処理が行われ、復号結果がクエリ装置１０３に送信される。
【０１０２】
図１７は、本発明の一実施形態における図１６とは異なるデータの流れを示す。
【０１０３】
図１７において、ステップ１からステップ２までは図１６と同じである。ステップ３以降が図１６のデータの流れと異なる。
【０１０４】
（ステップ３）データベースサーバ１０２から復号装置１０４に計算結果が送信される。
【０１０５】
（ステップ４）復号装置１０４において、計算結果の復号化の処理がされ、復号結果がクエリ装置１０３に送信される。
【０１０６】
以上のように、本実施形態として、データベースサーバにおいて、暗号化ベクトルデータを格納し、難読化クエリをクエリ装置１０３より受信し、難読化クエリのベクトルのセグメントについての計算を行い、クエリ装置１０３へ返信する。これにより、クエリ装置１０３では、データベースサーバにおける計算の目的を他者に知られずに、暗号化の処理がされた計算結果を得ることができ、復号化の処理の結果を得ることができる。
【０１０７】
なお、上記の説明において、情報提供装置１０１、データベースサーバ１０２、クエリ装置１０３および復号装置１０４それぞれの台数を１として説明した。しかし、本発明はこれに限定されることはない。情報提供装置１０１、データベースサーバ１０２、クエリ装置１０３および復号装置１０４のそれぞれの台数を任意の数とすることができる。
【０１０８】
例えば、図１８は、図１６において情報提供装置の数を複数とする場合のシステム１６００の一例を示す。すなわち、第１情報提供装置１０１−１、第２情報提供装置１０１−２、…、第ｎ情報提供装置１０１−ｎそれぞれが、情報提供装置１０１と同様に構成され、データベースサーバ１０２は、第１情報提供装置１０１−１、第２情報提供装置１０１−２、…、第ｎ情報提供装置１０１−ｎから、第１暗号化データ、第２暗号化データ、…、第ｎ暗号化データそれぞれを受信する。なお、図１８においては、第１暗号化データ、第２暗号化データ、…、第ｎ暗号化データは、第１情報提供装置１０１−１、第２情報提供装置１０１−２、…、第ｎ情報提供装置１０１−ｎからデータベースサーバ１０２が受信する暗号化ベクトルデータを示す。特に、第１暗号化データ、第２暗号化データ、…、第ｎ暗号化データのそれぞれの数は１に限定されることなく、任意の数とすることができる。
【０１０９】
図１８において、第１情報提供装置１０１−１、第２情報提供装置１０１−２、…、第ｎ情報提供装置１０１−ｎそれぞれの鍵情報格納部２０３に格納される暗号鍵は、同一とすることができる。すなわち、第１情報提供装置１０１−１、第２情報提供装置１０１−２、…、第ｎ情報提供装置１０１−ｎは、共通の公開鍵を共有することができる。したがって、第１暗号化データ、第２暗号化データ、…、第ｎ暗号化データは、同じ暗号鍵により暗号化されて得られる暗号化ベクトルデータとすることができる。
【０１１０】
また、図１８において、復号装置１０４は、第１情報提供装置１０１−１、第２情報提供装置１０１−２、…、第ｎ情報提供装置１０１−ｎそれぞれの鍵情報格納部２０３に格納される暗号鍵による暗号化の処理に対応する復号化の処理を行うための鍵を格納する。
【０１１１】
したがって、図１８において、データベースサーバ１０２は、第１情報提供装置１０１−１、第２情報提供装置１０１−２、…、第ｎ情報提供装置１０１−ｎそれぞれから同じ暗号鍵で暗号化された暗号化データを受信し、データベース４０１に格納する。また、クエリ装置１０３は、データベースサーバ１０２に対して難読化クエリを送信し、データベースサーバ１０２は、難読化クエリに対する計算結果をクエリ装置１０３に返信する。クエリ装置１０３は、計算結果を復号装置１０４へ送信し、復号装置１０４は復号結果を返信する。クエリ装置１０３は、返信された復号結果に対して逆難読化を行い、クエリに対する結果を得ることができる。
【０１１２】
このようにシステム１６００を構成することにより、複数の情報提供装置の運営者が提供するデータの処理を、データベースサーバ１０２の運営者、復号装置１０４の運営者にクエリの内容を知られずに行うことができる。また、情報提供装置の運営者が提供する個々のデータの内容をデータベースサーバ１０２の運営者およびクエリ装置１０３の利用者に知られてしまうことを困難にすることもできる。
【０１１３】
例えば、複数の情報提供装置の各運営者が物品購入機関であり、物品購入機関が提供するデータが購入を希望する物品の数を含むとする。また、クエリ装置の運営者が物品提供機関であるとする。このとき、物品提供機関は、物品購入機関それぞれが購入を希望する物品の総数を知ることが可能となる。しかし、物品購入機関それぞれが購入を希望する数は、データベースサーバ１０２の運営者および物品提供機関が知ることは困難である。
【０１１４】
以上の構成は、例えば会社が株式を発行する際に応用することができる。すなわち、各投資家は、購入を希望する株式の数を同じ暗号鍵により暗号化して、データベースサーバに送信する。データベースサーバは、例えば証券会社が運営する。このとき、株式を発行する会社は、データベースサーバに対して、投資家が購入を希望する株式の数の総数を知ることは可能であるが、個々の投資家が購入を希望する株式の数を知ることは困難となる。
【０１１５】
（実施形態２）
図１９は、図１７に示すデータの流れを実現する際のクエリ装置１０３の機能ブロック図を示す。図１９に示すように、クエリ装置１０３は、クエリ取得部８０１と、クエリ難読化部８０２と、クエリ送信部８０３と、復号結果受信部８０６と、逆難読化部８０７と、難読化情報格納部８０８と、出力部８０９とを備える。
【０１１６】
クエリ取得部８０１と、クエリ難読化部８０２と、クエリ送信部８０３と、復号結果受信部８０６と、逆難読化部８０７と、難読化情報格納部８０８と、出力部８０９とのそれぞれは、図８を参照して説明したクエリ装置１０３と同じである。
【０１１７】
図１９においては、データベースサーバ１０２の計算処理部４０５による計算結果は、データベースサーバ１０２の送信部４０６より、直接、復号装置１０４の結果受信部１００２に送信される。このため、クエリ装置１０３は、図８に示される計算結果受信部８０４と、計算結果送信部８０５を備える必要がない。
【０１１８】
図１７に示すデータの流れおよび図１９に示す構成により、クエリ装置１０３が計算結果をデータベースサーバ１０２から受信し、計算結果を復号装置１０４に送信する処理をする必要がなくなる。
【０１１９】
なお、図１９においては、復号装置１０４からクエリ装置１０３に直接、復号結果が送信されるようになっているが、データベースサーバ１０２など他のサーバを介して復号装置１０４からクエリ装置１０３に送信されるようになっていてもよい。
【０１２０】
（実施形態３）
図２０は、本発明の実施形態３に係るシステムの機能ブロック図およびデータの流れを示す。システム１９００は、第２情報提供装置１０１と、データベースサーバ１０２と、クエリ装置１０３と、第２復号装置１０４と、第１情報提供装置１９０１と、第１復号装置１９０２とを備える。
【０１２１】
図１と図２０とを較べると、図１の情報提供装置１０１と図２０の第２情報提供装置とが対応し、図１の復号装置１０４と図２０の第２復号装置１０４と対応している。また、図２０の構成は、図１の構成に第１情報提供装置１９０１と第１復号装置１９０２とが追加されている構成になっている。
【０１２２】
第１情報提供装置１９０１は、第２情報提供装置１０１と同じ構成とすることができ、データ取得部と、データ暗号化部と、鍵情報格納部と、暗号化データ送信部とを有する。この場合、第１情報提供装置１９０１の暗号化データ送信部は、第２情報提供装置１０１のデータ取得部２０１に、第１情報提供装置１９０１の運営者の暗号鍵により暗号化の処理がされたデータを送信する。第１情報提供装置１９０１における暗号化の処理も、第１の演算と第２の演算との準同型を保つことが好ましい。
【０１２３】
したがって、本実施形態では、第１情報提供装置１９０１により取得されたデータが、第１情報提供装置１９０１の運営者の暗号鍵による暗号化の処理がされ、さらに、第２情報提供装置１０１の運営者の暗号鍵による暗号化の処理がされる。結果として２重に暗号化の処理がされ、データベースサーバ１０２に格納される。
【０１２４】
また、第１復号装置１９０２は、第１情報提供装置１９０１の運営者の暗号鍵による暗号化の処理に対応した復号化の処理を行う。
【０１２５】
本実施形態におけるデータの流れを説明すると次のようになる。
（ステップ１）第１情報提供装置１９０１から第２情報提供装置１０１へ暗号化データが送信される。
【０１２６】
（ステップ２）第２情報提供装置１０１からデータベースサーバ１０２へ、２重に暗号化の処理がされたデータが送信され、データベース４０１へ格納される。
【０１２７】
（ステップ３）クエリ装置１０３からデータベースサーバ１０２に難読化クエリが送信される。データベースサーバ１０２が難読化クエリを受信すると、難読化クエリのセグメントごとに計算がされる。
【０１２８】
（ステップ４）データベースサーバ１０２からクエリ装置１０３に計算結果が送信される。
【０１２９】
（ステップ５）クエリ装置１０３から、ステップ４で受信された計算結果が第２復号装置１０４に送信される。
【０１３０】
（ステップ６）第２復号装置１０４において復号化の処理が行われ、復号化の処理の結果がクエリ装置１０３に送信される。
【０１３１】
（ステップ７）クエリ装置１０３から、ステップ６で受信された復号化の処理の結果が第１復号装置１９０２に送信される。
【０１３２】
（ステップ８）第１復号装置１９０２において復号化の処理が行われ、復号化の処理の結果がクエリ装置１０３に送信される。
【０１３３】
本実施形態においては、第１情報提供装置１９０１の運営者の暗号鍵と第２情報提供装置１０１の運営者の暗号鍵との２つの暗号鍵により、データが２重に暗号化されるので、第１情報提供装置１９０１の運営者と第２情報提供装置１０１の運営者との同意がないと、復号化の処理を行うことができない。
【０１３４】
例えば、第１情報提供装置１９０１の運営者が患者であり、第２情報提供装置１０１の運営者がその患者の担当医である場合、患者のＤＮＡデータなどを患者の暗号鍵により暗号化して第１情報提供装置１９０１から第２情報提供装置１０１に送信し、さらに担当医の暗号鍵により暗号化してデータベース４０１に格納がされ、クエリ装置１０３による検索がされる。しかし、復号化の処理がされた検索結果をクエリ装置１０３の利用者が得るには、患者と担当医との同意が必要となる。このため、プライバシーの確保がされる。例えば、患者および担当医の少なくとも一方が、情報提供に同意しなくなった場合には、少なくとも一方が、その後の復号化の処理を拒否することにより、情報開示を抑制することができる。
【０１３５】
なお、第１情報提供装置１９０１による暗号化の処理と第２情報提供装置１０１による暗号化の処理との順序を交換しても、第２復号装置１０４による復号化の処理の後に第１復号装置１９０２による復号化の処理が可能であれば、ステップ５、６とステップ７、８とを入れ替えて実行することもできる。
【０１３６】
（実施形態４）
図２１は、本発明の実施形態４に係るシステムの機能ブロック図である。システム２０００は、第１情報提供装置１０１と、第１データベースサーバ１０２と、クエリ装置１０３と、第１復号装置１０４と、第２情報提供装置１０１−２と、第２データベースサーバ１０２−２と、第２復号装置１０４−２とを備える。
【０１３７】
図２１において、第１情報提供装置１０１と、第１データベースサーバ１０２と、クエリ装置１０３と、第１復号装置１０４との構成の部分は、上記の実施形態と同様である。また、第２情報提供装置１０１−２と、第２データベースサーバ１０２−２と、クエリ装置１０３と、第２復号装置１０４−２との構成の部分も、上記の実施形態と同様である。ただし、本実施形態においては、第１情報提供装置１０１から暗号化データを第１データベースサーバ１０２に格納するときに、第２情報提供装置に、暗号化データを識別する情報（図２１では、アイテム番号）を第２情報提供装置１０１−２に送信し、第２情報提供装置１０１−２は、アイテム番号と１対１に対応する管理番号を生成する。このとき、第２情報提供装置１０１−２は、アイテム番号と１対１に対応する管理番号の生成を、第１情報提供装置１０１に対して秘密裡に行うことができる。
【０１３８】
第１情報提供装置１０１は、第１データベースサーバ１０２に格納する第１暗号化データに、アイテム番号を含め、クエリ装置１０３から第１データベースサーバに対して難読化クエリを送信することにより、計算結果として暗号化されたアイテム番号を得ることができるようにする。
【０１３９】
また、第２情報提供装置１０１−２は、第２データベースサーバ１０２−２に格納する第２暗号化データに、管理番号とアイテム番号とを含め、クエリ装置１０３から難読化したアイテム番号に関するクエリを第２データベースサーバ１０２−２に送信することにより、計算結果として暗号化された管理番号を得ることができるようにする。
【０１４０】
以上のような構成は、例えば、第１情報提供装置１０１の運営者が物品供給機関であり、供給する物品に関するデータをアイテム番号を含めて第１データベースサーバ１０２に暗号化して格納し、第２情報提供装置１０２の運営者が物品供給機関およびクエリ装置の利用者と独立した機関である場合に有効である。特に、第１情報提供装置１０１の運営者である物品供給機関が複数存在し、物品を共同の物流センターで管理する場合に有効である。
【０１４１】
この場合、物品供給機関は、アイテム番号とともに物品を第２情報提供装置１０１−２へ送付し、第２情報提供装置１０１−２は、生成した前記管理番号を付して物品を物流センターに保管させる。アイテム番号と管理番号との対応関係は、第２情報提供装置１０１−２の運営者のみが知るようにすることができる。このため、物品供給機関も物流センターも、各々の物品を開梱や開封しないと、物品がどの管理番号で管理されているのか知ることができないようにすることができる。したがって、物流センターにおける物品の秘匿性を高めることができる。
【０１４２】
クエリ装置１０３の利用者が第１データベースサーバに対して、物品に関する難読化クエリを送信し、第１復号装置１０４により復号化の結果を受け取ることにより、アイテム番号を得ることができる。しかし、物品供給機関は、どのようなクエリによりそのアイテム番号をクエリ装置１０３の利用者が得たのかを知ることができず、物品供給機関は、クエリ装置１０３の利用者の意図を知ることができない。
【０１４３】
次に、クエリ装置１０３の利用者は、アイテム番号を難読化したクエリを第２データベースサーバ１０２−２に送信し、計算結果を受信する。その後、計算結果を第２復号装置１０４−２に送信し、復号の処理の結果を得る。これにより、クエリ装置１０３の利用者は、管理番号を得ることができ、物流センターに管理番号を提示して物品を得ることができる。この場合、第２情報提供装置１０２の運営者は、クエリ装置１０３の利用者がどのようなクエリにより、管理番号を検索したのかを知ることができない。したがって、第２情報提供装置１０２の運営者も、クエリ装置１０３の利用者の意図を知ることができないこととなり、物品供給機関、第１データベースサーバ１０２の管理者、クエリ装置１０３、第２情報提供装置１０２の運営者、第２データベースサーバ１０２−２の管理者間での情報の秘匿性を維持することができる。
【０１４４】
（実施形態５）
実施形態５として、データベースサーバに格納されている暗号化ベクトルデータを更新するためのデータベースサーバおよび情報提供装置について説明する。
【０１４５】
図２２は、実施形態５に係るデータベースサーバの機能ブロック図を示す。データベースサーバ１０２は、データベース４０１と、暗号化データ受信部４０２と、データベース管理部４０３と、計算処理部４０５と、受信部４０４と、送信部４０６と、更新クエリ暗号化・復号化鍵生成部２２０１と、更新クエリ復号化鍵情報格納部２２０２と、更新クエリ暗号化鍵情報送信部２２０３と、暗号化更新クエリ受信部２２０４と、暗号化更新クエリ復号化部２２０５と、データ更新部２２０６とを有する。
【０１４６】
別言すれば、図２２に機能ブロック図を示すデータベースサーバ１０２は、実施形態１から４のいずれかの実施形態に係るデータベースサーバ１０２が、更に、更新クエリ暗号化・復号化鍵生成部２２０１と、更新クエリ復号化鍵情報格納部２２０２と、更新クエリ暗号化鍵情報送信部２２０３と、暗号化更新クエリ受信部２２０４と、暗号化更新クエリ復号化部２２０５と、データ更新部２２０６とを有するといえる。
【０１４７】
更新クエリ暗号化・復号化鍵生成部２２０１は、データベース管理部４０３が暗号化ベクトルをデータベース４０１に格納する際に、暗号化鍵を生成する。暗号化鍵による暗号化が公開鍵暗号化の処理である場合には、暗号化鍵に加え、暗号化鍵を秘密鍵とする公開鍵も生成する。生成される暗号化鍵（例えば秘密鍵および公開鍵）は、データベース４０１に格納される暗号化ベクトルごとに異なるようにすることができる。
【０１４８】
更新クエリ復号化鍵情報格納部２２０２は、データベース４０１に暗号化ベクトルが格納される際に、更新クエリ暗号化・復号化鍵生成部２２０１により生成された暗号化鍵（例えば秘密鍵）を、格納される暗号化ベクトルに対応付けて格納する。例えば、図５に示される列５０１に格納される、暗号化ベクトルを一意に識別する情報に暗号化鍵を対応付けて格納する。
【０１４９】
更新クエリ暗号化鍵情報送信部２２０３は、更新クエリ暗号化・復号化鍵生成部２２０１が生成した暗号鍵（例えば秘密鍵に対する公開鍵）を情報提供装置１０１に送信する。これにより、情報提供装置１１０１は、データベースサーバ１０２に送信した暗号化データに対応する暗号化鍵を受信して取得することができる。当該暗号鍵を「更新クエリ暗号化鍵」２２１０と呼称する。
【０１５０】
情報提供装置１０１が、暗号化ベクトルを更新したい場合には、更新を表わす更新クエリを更新クエリ暗号化鍵２２１０により暗号化する。暗号化ベクトルの一部のデータを更新したい場合には、暗号化ベクトルの識別情報および、当該識別情報により識別される暗号化ベクトルの更新するデータの範囲を含めて、更新クエリ暗号化鍵２２１０により暗号化する。このように暗号化された更新クエリを暗号化更新クエリ２２１１と呼称する。
【０１５１】
暗号化更新クエリ受信部２２０４は、暗号化更新クエリを情報提供装置１０１より受信する。
【０１５２】
暗号化更新クエリ復号化部２２０５は、暗号化更新クエリ受信部２２０４により受信された暗号化更新クエリ２２１１を、更新クエリ復号化鍵情報格納部２２０２に格納されている更新クエリ復号化鍵により復号する。この復号により、更新後の暗号化ベクトルデータ、また、必要であれば、更新する暗号化ベクトルデータの識別情報、当該識別情報により識別される暗号化ベクトルデータの更新するデータの範囲（例えば、更新する列の名前に対応するデータの範囲）をデータベースサーバ１０２内において得ることができる。
【０１５３】
データ更新部２２０６は、暗号化更新クエリ復号化部２２０５による暗号化更新クエリの復号化の結果に基づいて、データベース４０１に格納されている暗号化ベクトルデータの更新を行なう。
【０１５４】
更新は、暗号化ベクトルデータの上書きによって行なうことができる。また、暗号化ベクトルデータのデータＥｎｃ（ｍ）をＥｎｃ（ｎ）に更新する場合には、情報提供装置１０１によって、Ｅｎｃ（ｎ−ｍ）を計算し、暗号化更新クエリに含めてもよい。この場合、データベースサーバ１０２は、Ｅｎｃ（ｍ）＊Ｅｎｃ（ｎ−ｍ）を計算して得られる結果により、Ｅｎｃ（ｍ）を上書きする。準同型の性質により、Ｅｎｃ（ｍ）＊Ｅｎｃ（ｎ−ｍ）＝Ｅｎｃ（ｍ＋ｎ−ｍ）＝Ｅｎｃ（ｎ）となるので、Ｅｎｃ（ｍ）をＥｎｃ（ｎ）に更新することができる。
【０１５５】
また、Ｅｎｃ（ｍ）をＥｎｃ（０）に更新する場合には、情報提供装置は、Ｅｎｃ（−ｍ）を計算し、暗号化更新クエリに含めてもよい。
【０１５６】
図２３は、実施形態５に係る情報提供装置１０１の機能ブロック図を示す。情報提供装置１０１は、データ取得部２０１と、データ暗号化部２０２と、鍵情報格納部２０３と、暗号化データ送信部２０４と、更新データ取得部２３０３と、データ位置情報格納部２３０４と、更新データ暗号化部２３０５と、更新クエリ暗号化鍵情報受信部２３０１と、更新クエリ暗号化鍵情報格納部２３０２と、更新クエリ暗号化部２３０６と、暗号化更新クエリ送信部２３０７とを有する。
【０１５７】
別言すれば、図２３に機能ブロック図を示す情報提供装置１０１は、実施形態１から４のいずれかの実施形態に係る情報提供装置１０１が、さらに、更新データ取得部２３０３と、データ位置情報格納部２３０４と、更新データ暗号化部２３０５と、更新クエリ暗号化鍵情報受信部２３０１と、更新クエリ暗号化鍵情報格納部２３０２と、更新クエリ暗号化部２３０６と、暗号化更新クエリ送信部２３０７とを有する構成となっている。
【０１５８】
更新クエリ暗号化鍵情報受信部２３０１は、暗号化データ送信部２０４による暗号化ベクトルデータの送信に応じて、データベースサーバ１０２が生成し更新クエリ暗号化鍵情報送信部２２０３が送信する更新クエリ暗号化鍵２２１０を受信する。
【０１５９】
更新クエリ暗号化鍵情報格納部２３０２は、更新クエリ暗号化鍵情報受信部２３０１が受信する更新クエリ暗号化鍵２２１０を格納する。例えば、暗号化データ送信部２０４が暗号化ベクトルデータを送信し、データベースサーバ１０２がデータベース４０１に暗号化ベクトルデータを格納し、格納した暗号化ベクトルデータの識別情報を更新クエリ暗号化鍵２２１０とともに送信する場合には、更新クエリ暗号化鍵情報格納部２３０２は、暗号化ベクトルデータの識別情報に関連付けて更新クエリ暗号化鍵２２１０を格納する。
【０１６０】
更新データ取得部２３０３は、更新するデータを取得する。更新データ取得部２３０３は、更新するデータとともに、更新する暗号化ベクトルデータの識別情報および更新する範囲（例えば、更新する列の名前）を取得してもよい。
【０１６１】
データ位置情報格納部２３０４は、更新データ取得部２３０３が、更新する範囲を、例えば、更新する列の名前により取得した場合に、更新する列の名前を更新する範囲（例えば、暗号化ベクトルデータの要素の数による範囲）に変換するために、更新する列の名前と更新する範囲とを関連付けて記憶する。
【０１６２】
更新データ暗号化部２３０５は、更新データ取得部２３０３により取得されたデータを鍵情報格納部２０３により格納された鍵情報により暗号化する。更新データ暗号化部２３０５は、暗号化の結果と、必要であれば暗号化ベクトルデータの識別情報およびデータ位置情報格納部２３０４から得られた更新する範囲を更新クエリ暗号化部２３０６に出力する。
【０１６３】
更新クエリ暗号化部２３０６は、更新データ暗号化部２３０５による暗号化の結果を更新クエリ暗号化鍵情報格納部２３０２に格納されている更新クエリ暗号化鍵により暗号化する。このとき、更新データ暗号化部２３０５が暗号化ベクトルデータの識別情報およびデータ位置情報格納部２３０４から得られた更新する範囲を出力した場合には、出力された暗号化ベクトルデータの識別情報に関連づけて更新クエリ暗号化鍵情報格納部２３０２に格納されている更新クエリ暗号化鍵を読み出し、読み出された更新クエリ暗号化鍵を用いて暗号化し、暗号化更新クエリを生成する。暗号化更新クエリには、更新する範囲が暗号化ベクトルデータの識別情報に関連づけて更新クエリ暗号化鍵情報格納部２３０２に格納されている更新クエリ暗号化鍵により暗号化されたデータにより暗号化されて含まれていてもよい。
【０１６４】
また、更新データ暗号化部２３０５が暗号化ベクトルデータの識別情報を出力しなかった場合には、例えば、新たな暗号化ベクトルデータの追加とみなし、更新クエリ暗号化部２３０６は、鍵情報格納部２０３に格納されている暗号鍵により暗号化された以上には暗号化しなかったり、デフォルトの暗号鍵により暗号化を行なったりする。
【０１６５】
暗号化更新クエリ送信部２３０７は、更新クエリ暗号化部２３０６により暗号化された結果である暗号化更新クエリ２２１１を、データベースサーバ１０２に送信する。
【０１６６】
以上のように、本実施形態においては、情報提供装置１０１から送信された暗号化ベクトルデータのうち、任意の暗号化ベクトルおよび当該暗号化ベクトルの任意のエントリを更新することができる。特に、更新する際の更新クエリは、暗号化ベクトルデータの格納の都度生成される更新クエリ暗号化鍵により暗号化されて情報提供装置１０１からデータベースサーバ１０２に送信されるので、情報提供者およびデータベースサーバ１０２の管理者以外は復号することができず、秘匿性を高めることができる。
【０１６７】
また、暗号化ベクトルデータを、０を暗号化したデータに更新することにより、データベースサーバの計算処理部４０５の計算において０を表わすデータとして扱われ得るので、事実上削除されたのと同一の効果を得ることができる。別言すれば、０を暗号化したデータへの更新により、データを削除することが可能となる。
【符号の説明】
【０１６８】
１００  計算システム
１０１  情報提供装置（第２情報提供装置）
１０２  データベースサーバ
１０３  クエリ装置（端末装置）
１０４  復号装置（第２復号装置）
２０１  データ取得部
２０２  データ暗号化部
２０３  鍵情報格納部
２０４  暗号化データ送信部
４０１  データベース
４０２  暗号化データ受信部
４０３  データベース管理部
４０４  受信部
４０５  計算処理部
４０６  送信部
８０１  クエリ取得部
８０２  クエリ難読化部
８０３  クエリ送信部
８０４  計算結果受信部
８０５  計算結果送信部
８０６  復号結果受信部
８０７  逆難読化部
８０８  難読化情報格納部
８０９  出力部
１００１  復号鍵格納部
１００２  結果受信部
１００３  復号部
１００４  復号結果送信部
１９０１  第１情報提供装置
１９０２  第１復号装置
２２０１  更新クエリ暗号化・復号化鍵生成部
２２０２  更新クエリ復号化鍵情報格納部
２２０３  更新クエリ暗号化鍵情報送信部
２２０４  暗号化更新クエリ受信部
２２０５  暗号化更新クエリ復号化部
２２０６  データ更新部
２２１０  更新クエリ暗号化鍵
２２１１  暗号化更新クエリ
２３０１  更新クエリ暗号化鍵情報受信部
２３０２  更新クエリ暗号化鍵情報格納部
２３０３  更新データ取得部
２３０４  更新データ位置情報格納部
２３０５  更新データ暗号化部
２３０６  更新クエリ暗号化部
２３０７  暗号化更新クエリ送信部
【図１】
2016129390.tif 000007
【図２】
2016129390.tif 000008
【図３】
2016129390.tif 000009
【図４】
2016129390.tif 000010
【図５】
2016129390.tif 000011
【図６】
2016129390.tif 000012
【図７】
2016129390.tif 000013
【図８】
2016129390.tif 000014
【図９】
2016129390.tif 000015
【図１０】
2016129390.tif 000016
【図１１】
2016129390.tif 000017
【図１２】
2016129390.tif 000018
【図１３】
2016129390.tif 000019
【図１４】
2016129390.tif 000020
【図１５】
2016129390.tif 000021
【図１６】
2016129390.tif 000022
【図１７】
2016129390.tif 000023
【図１８】
2016129390.tif 000024
【図１９】
2016129390.tif 000025
【図２０】
2016129390.tif 000026
【図２１】
2016129390.tif 000027
【図２２】
2016129390.tif 000028
【図２３】
2016129390.tif 000029
【国際調査報告】
2016129390.tif 000030
2016129390.tif 000031