(57)【特許請求の範囲】
【請求項１】
プロセッサと、
プロセッサによりアクセス可能で、複数のデータベースレコードを含むメモリと
を備えるデータベースサーバ（２００）であって、
プロセッサが、
少なくとも擬似ランダムにデータベースレコードの順序を並べ替え、それによって並べ替えられたデータベース（Ｒ［πｉ］）を生成し（Ｓ１０）、
並べ替えられた各データベースレコードに対応する少なくとも擬似ランダムな暗号化キーを生成し、それによって暗号化キー配列（ｋｒ［πｉ］）を生成し（Ｓ１５）、
並べ替えられたデータベースレコードのそれぞれを、対応する暗号化キー配列の暗号化キーを使用して暗号化し、それによって暗号化されたデータベース配列（Ｅ［πｉ］）を生成し（Ｓ２０）、
暗号化キー配列の暗号化キーのそれぞれを暗号化することによって、暗号化された暗号化キー配列（ｋｒ，ＨＥ［πｉ］）を生成（Ｓ２５）し、
暗号化されたデータベース配列（Ｅ［πｉ］）および暗号化された暗号化キー配列（ｋｒ，ＨＥ［πｉ］）をインデックスサーバに送り（Ｓ３０）、
インデックスサーバから受信された、暗号化された暗号化キー配列から導出されるマスキングされた暗号化キー配列（ｋｍ，ＨＥ［πｉ］）を復号して格納し（Ｓ４５）、
公開−秘密キーペアを使用して、クライアントサーバ（４００）から受信された、暗号化されたマスキング済みキー（ｋｍ，ＨＥ［ｎ］）を復号し、復号結果のマスキングされたキー（ｋｍ［ｎ］）をクライアントサーバに送る（Ｓ３５）
ように構成される、
データベースサーバ。
【請求項２】
プロセッサ、インデックスサーバおよびクライアントサーバの間のネットワーク上に通信を提供するように構成されるネットワークインタフェースをさらに備える、請求項１に記載のサーバ。
【請求項３】
プロセッサが、公開−秘密のキーペアを生成し（Ｓ０５）、かつ、暗号化キー配列の擬似ランダムな暗号化キーのそれぞれを公開−秘密キーペアを使って準同型暗号化する（Ｓ２５）ようにさらに構成される、請求項１に記載のサーバ。
【請求項４】
プロセッサと、
プロセッサによりアクセス可能で、プロセッサにより実行可能なプログラム命令を含むメモリと
を備えるデータインデックスサーバ（３００）であって、
プログラム命令が、
暗号化された暗号化キーのキー配列を受信し（Ｓ３０）、
それぞれがキー配列の要素に対応する、少なくとも擬似ランダムなマスクを含むマスク配列を生成し（ＩＳ１５）、
キー配列の各暗号化キーについて、その暗号化キーと対応するマスクとの合計を計算し（ＩＳ２０）、
各合計を暗号化し、それによって、暗号化されたマスキング済みキーの配列を生成し（ＩＳ２０）、
暗号化された合計の順序を少なくとも擬似ランダムに並べ替えて、マスキングされた暗号化済みキーの並べ替えられた配列を生成し、マスキングされた暗号化済みキーの並べ替えられた配列をデータベースサーバに送る（ＩＳ２５）ためのプログラム命令である、
データベースインデックスサーバ。
【請求項５】
合計が準同型暗号化される、請求項４に記載のインデックスサーバ。
【請求項６】
プロセッサが、データベースサーバ（２００）からデータレコードの配列を受信し（Ｓ３０）、クライアントサーバ（４００）からレコード番号を受信し（Ｃ０５）、応答として、レコード番号に対応するデータレコードおよびマスクをクライアントサーバに返送する（ＩＳ３０）ようにさらに構成される、請求項４に記載のインデックスサーバ。
【請求項７】
プロセッサが、マスキングされた暗号化済みキーの並べ替えられた配列の対応する要素にアクセスするために、並べ替えられたデータベースインデックスをデータベースサーバに送る（ＩＳ３５）ようにさらに構成される、請求項６に記載のインデックスサーバ。
【請求項８】
データレコードの配列のレコードのそれぞれが暗号化されている、請求項６に記載のインデックスサーバ。
【請求項９】
データベースサーバ（２００）を操作する方法であって、
サーバによって記憶されているデータベースレコードの順序を少なくとも擬似ランダムに並べ替えることによって、並べ替えられたデータベース（Ｒ［πｉ］）を生成する（Ｓ１０）ステップと、
並べ替えられた各データベースレコードに対応する少なくとも擬似ランダムな暗号化キーを生成し、それによって暗号化キー配列（ｋｒ［πｉ］）を生成する（Ｓ１５）ステップと、
暗号化キー配列の対応する暗号化キーを使用して、並べ替えられたデータベースレコードのそれぞれを暗号化し、それによって暗号化されたデータベース配列（Ｅ［πｉ］）を生成する（Ｓ２０）ステップと、
暗号化キー配列の暗号化キーをそれぞれ暗号化し、それによって、暗号化された暗号化キー配列（ｋｒ，  ＨＥ［πｉ］）を生成する（Ｓ２５）ステップと、
暗号化されたデータベース配列および暗号化された暗号化キー配列をインデックスサーバに送る（Ｓ３０）ステップと、
インデックスサーバから受信されたマスキングされた暗号化キー配列を暗号化して記憶するステップであって、マスキングされた暗号化キー配列が暗号化された暗号化キー配列から導出される、暗号化して記憶する（Ｓ４５）ステップと、
公開−秘密キーペアを使用して、クライアントサーバ（４００）から受信されたマスキングされたキーを復号し、復号結果のマスキングされたキーをクライアントサーバに送る（Ｓ３５）ステップと、
指定された暗号化されたマスキング済み暗号化キーをクライアントサーバから受信したことに応答して、マスキングされた暗号化キー配列の、指定された暗号化されたマスキング済み暗号化キーを復号するステップと
を含む方法。
【請求項１０】
公開−秘密キーペアを生成する（Ｓ０５）ステップと、公開−秘密キーペアを使用して擬似ランダム暗号化キーのそれぞれを準同型暗号化する（Ｓ２５）ステップとをさらに含む、請求項９に記載の方法。
【請求項１１】
データベースインテックスサーバ（３００）を操作する方法であって、
暗号化キーの配列を受信する（Ｓ３０）ステップと、
複数の少なくとも擬似ランダムなマスクを含むマスク配列を生成するステップであって、少なくとも擬似ランダムなマスクのそれぞれが、キー配列の要素に対応する、マスク配列を生成する（ＩＳ１５）ステップと、
各暗号化キーとそのキーに対応する少なくとも擬似ランダムなマスクとの合計を計算して暗号化する（ＩＳ２０）ステップと、
各合計を暗号化し、それによって、暗号化されたマスキング済みキーの配列を生成する（ＩＳ２０）ステップと、
暗号化された合計の順序を少なくとも擬似ランダムに並べ替えて（ＩＳ２５）マスキングされた暗号化済みキーの並べ替えられた配列を生成し、マスキングされた暗号化済みキーの並べ替えられた配列をデータベースサーバに送るステップとを含む方法。
【請求項１２】
合計が準同型に暗号化される、請求項１１に記載の方法。
【請求項１３】
データベースサーバ（２００）からデータレコードの配列を受信する（Ｓ３０）ステップと、クライアントサーバ（４００）からレコード番号を受信する（Ｃ０５）ステップと、それに応答して、レコード番号に対応するデータレコードおよびマスクをクライアントサーバに返送する（ＩＳ３０）ステップをさらに含む、請求項１１に記載の方法。
【請求項１４】
マスキングされた暗号化済みキーの並べ替えられた配列の対応する要素にアクセスするために、並べ替えられたデータベースインデックスをサーバに送る（ＩＳ３５）ステップをさらに含む、請求項１１に記載の方法。
【請求項１５】
データレコードの配列のレコードのそれぞれが暗号化されている、請求項１３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
連邦政府資金による研究開発の記載
本発明は、情報先端研究プロジェクト活動（ＩＡＲＰＡ）により与えられた契約番号Ｄ１１ＰＣ２０１９４の下で連邦政府の支援を受けて行われた。連邦政府は本発明に一定の権利を有する。
【０００２】
本開示は一般に、情報の安全な格納および取り出しの分野に関する。
【背景技術】
【０００３】
クライアントがデータベースからデータを取り出すとき、取り出したデータおよびクエリ自体が、例えばデータベースサーバおよび、何らかの補助サービスが存在する場合はその補助サービスなどの中間エンティティから見えない（つまり、隠される）ことが望ましいことがある。サーバからデータを隠すために、様々な方法が考案されてきたが、例えば、かなりの計算オーバヘッドの影響を被る。さらに、現在の解決策では、クライアントクエリを検閲から適切に保護することができず、それによって、クライアントに提供される情報を決定する機会を悪意のエンティティに与える可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
したがって、上記の欠陥に対処する、改良された安全な、データベースからのデータ取り出しのために解決策が必要とされる。
【課題を解決するための手段】
【０００５】
一実施形態では、本開示はデータベースサーバを提供する。サーバはプロセッサおよびメモリを備える。メモリはプロセッサによりアクセス可能で、複数のデータベースレコードを含む。プロセッサは、例えば、補助の非協働サーバなどのインデックスサーバとネットワーク上で通信するように構成される。プロセッサは、少なくとも疑似ランダムにデータベースレコードの順序を並べ替え、それによって並べ替えられたデータベースを生成する。プロセッサは、並べ替えられた各データベースレコードに対応する少なくとも疑似ランダムな暗号化キーを生成し、それによって暗号化キー配列を生成してもよい。並べ替えたデータベースレコードのそれぞれは、対応する暗号化キーで暗号化されてもよい。プロセッサは、並べ替えられたデータベースレコードおよび少なくとも疑似ランダムな暗号化キーをメモリに記憶するように構成される。
【０００６】
データベースサーバの任意の実施形態で、プロセッサは、公開−秘密のキーペアを生成し、疑似ランダムな暗号化キーのそれぞれを、キーペア、例えば公開キーを使用して準同型暗号化するようにさらに構成されてもよい。任意の実施形態で、プロセッサは、暗号化キーの配列を受信し、復号し、復号された暗号化キーを記憶するようにさらに構成されてもよく、受信される暗号キーはマスキングされていてもよい。任意の実施形態で、プロセッサは、インデックスサーバから受信した暗号化キーを復号し、復号結果のキーを、例えばクライアントへ送信するように構成されてもよい。任意の実施形態で、プロセッサは、並べ替えられたデータベースおよび暗号化されたキー配列を補助の非協働サーバに送信するように構成されてもよい。
【０００７】
別の実施形態では、本開示はデータベースインデックスサーバを提供する。インデックスサーバは、プロセッサおよび、プロセッサによりアクセス可能なメモリを備える。メモリは、プロセッサ、クライアントおよびインデックスサーバの間のネットワーク上に通信を提供するために、プロセッサにより実行可能なプログラム命令を含む。プロセッサは、暗号化キーの配列を受信するように構成され、この暗号化キーは暗号化されていてもよい。プロセッサは、配列内の各キーに対応する少なくとも疑似ランダムなマスクを生成してもよい。プロセッサは、各暗号化キーと、そのキーに対応するマスクの合計を計算して暗号化してもよい。
【０００８】
インデックスサーバの任意の実施形態で、プロセッサは、暗号化された合計の順序を少なくとも疑似ランダムに並べ替えて、並べ替えられたマスキング済みキーの配列を生成するようにさらに構成されてもよい。いくつかの実施形態では、合計は準同型暗号化される。任意の実施形態で、プロセッサは、データベースサーバからデータレコードの配列を受信するようにさらに構成されてもよい。そのような実施形態では、プロセッサは、クライアントからレコード番号を受信し、そのレコード番号に対応するデータレコードおよびマスクをクライアントに返すようにさらに構成されてもよい。インデックスサーバの任意の実施形態で、データレコードの配列の各レコードは暗号化されてもよい。
【０００９】
別の実施形態は、データベースクライアントを提供する。クライアントは、プロセッサおよびメモリを備える。メモリはプロセッサによりアクセス可能であり、インデックスサーバからデータベースレコード、マスクおよび対応するキーを受信するために、プロセッサにより実行可能なプログラム命令を含む。プロセッサは、キーとマスクの合計を計算して暗号化し、暗号化した合計をデータベースサーバに送信するように構成される。
【００１０】
データベースクライアントの任意の実施形態で、キーはマスキングされたキーでもよく、プロセッサは、そのマスキングされたキーに対応する復号されたキーをサーバから受信するようにさらに構成されてもよい。そのような任意の実施形態で、プロセッサは、受信された復号済みキーからマスクを減算するようにさらに構成されてもよい。そのような任意の実施形態で、プロセッサは、復号されたキーを使用して受信されたデータベースレコードを復号するようにさらに構成されてもよい。
【００１１】
別の実施形態は、データベースサーバを動作させる方法を提供する。この方法は、サーバによって記憶されるデータベースレコードの順序を少なくとも疑似ランダムに並べ替えるステップを含む。並べ替えられた各データベースレコードに対応する、少なくとも疑似ランダムな暗号化キーが生成される。並べ替えられたデータベースレコードのそれぞれは、対応する暗号化キーで暗号化される。
【００１２】
別の実施形態は、データベースインデックスサーバを動作させる方法を提供する。この方法は、暗号化キーの配列を受信するステップを含み、この暗号化キーは暗号化されていてもよい。配列内の各キーに対応する、少なくとも疑似ランダムなマスクが生成される。各暗号化キーと、そのキーに対応するマスクについて、暗号化された合計が計算される。
【００１３】
さらに別の実施形態は、データベースクライアントを動作させる方法を提供する。この方法は、あるレコード番号に対応するデータベースレコード、マスクおよびキーについてインデックスサーバにクエリを行うステップを含む。キーとマスクの合計が計算されて暗号化される。暗号化された合計は、データベースサーバに提供される。
【００１４】
本発明のさらなる態様が、下記の詳細な説明、図および特許請求の範囲に部分的に明記され、また、部分的に、詳細な説明から導かれるか、または本発明の実施により学習され得る。上記の一般的な説明および下記の詳細な説明はどちらも例であり、説明のみを目的とし、本発明を開示される内容に制限するものではないことが理解されよう。
【図面の簡単な説明】
【００１５】
【図１】通信ネットワークを介して結合されている、通信サーバ（Ｓ）、インデックスサーバ（ＩＳ）およびクライアント（Ｃ）を備えるデータベースシステムを示す図である。
【図２】例えば図１に示されるようなサーバの機能ブロックを示す図である。
【図３】例えば図１に示されるようなインデックスサーバの機能ブロックを示す図である。
【図４】例えば図１に示されるようなクライアントの機能ブロックを示す図である。
【図５】図１のサーバおよびインデックスサーバの一実施形態の動作、例えば、クエリに応答して安全にクライアントにデータを提供するように、図１のサーバおよびインデックスサーバを設定する動作を示す図である。
【図６】図１のサーバ、インデックスサーバおよびクライアントの第１の実施形態の動作、例えば、クライアントに安全にデータを提供する動作を示す図である。
【図７】図１のサーバ、インデックスサーバおよびクライアントの第１の実施形態の動作、例えば、クライアントに安全にデータを提供する動作を示す図である。
【図８】図１のサーバおよびインデックスサーバの別の実施形態の動作、例えば、図１のサーバおよびインデックスサーバを設定する動作を示す図である。
【図９】図１のサーバ、インデックスサーバおよびクライアントの第２の実施形態の動作、例えば、クライアントに安全にデータを提供する動作を示す図である。
【図１０】図１のサーバ、インデックスサーバおよびクライアントの第２の実施形態の動作、例えば、クライアントに安全にデータを提供する動作を示す図である。
【発明を実施するための形態】
【００１６】
本開示は、例えばサーバによるデータベースレコードの安全な取り出しを目的とする。従来の安全なデータベースシステムのいくつかでは、データベースサーバが２つの非協働エンティティ、サーバＳおよびインデックスサーバＩＳとして実装される。そのようなシステムでは、サーバがデータベースの所有者である。インデックスサーバは、例えば補助的な非協働サーバと見なされてもよい。設定段階で、サーバはデータベースの各行を暗号化して、暗号化結果をインデックスサーバに送信する。クライアントＣが、インデックスサーバが保持する暗号化されたデータベースのクエリを行うと、インデックスサーバは応答して正しい（暗号化された）行を返し、クライアントに復号キーを送信するようサーバに要請する。しかし、クライアントに送信されたキーをサーバが知っているので、このクライアントクエリは、厳密には秘密ではなく、悪意のエンティティにクエリデータを傍受する機会を与える可能性がある。
【００１７】
そのような従来のシステムの安全性を向上させるための試みには、高価な、または法外価格でさえあり得る計算資源が必要である。例えば、ある解決策の提案では、サイズｎ２の準同型暗号化の行列を使用し、ここでｎはデータベースレコードの数である。そのような実施形態では、インデックスサーバはｎ個のレコードのそれぞれを新しいキーで再暗号化するので、ｎ２回の暗号化操作が必要になる。少なくない数のデータベースレコードでは、このような解決策では、データベースシステムの実際的な計算限界を超えることがある。よって、代替の解決策が必要である。
【００１８】
発明者は、安全なデータベースシステムでのクエリの安全性は、例えば、本明細書に記載する実施形態で開示されるように設定段階で復号キーの割り当ておよび操作を行うことによって向上させ得ることを発見した。簡潔に要約すると、一実施形態で、サーバが非協働インデックスサーバに、並べ替えられた暗号化済みデータベースおよび、対応する暗号化／復号キーの配列を提供するが、これに限定されない。本明細書で、非協働サーバとは、暗号化されたデータベースを記憶および検索する補助サーバとして定義される。クライアントが、インデックスサーバにデータベースレコードのクエリを行う。インデックスサーバは、要求されたレコードを暗号化された形式で、対応する復号キーおよび対応するマスク値と共にクライアントに返す。クライアントは次に、キーにマスク値を加算し、合計を暗号化してサーバに送信する。サーバは次に、マスキングされた暗号化されていないキーを返し、クライアントはそのキーで、先にインデックスサーバから受信した暗号化レコードを復号する。クライアントのみが、要求されたデータベースレコードの値を決定するために十分な情報をもっている。インデックスサーバが所有しているのは、暗号化されたデータベースの並べ替えられたコピーなので、クエリはインデックスサーバから隠される。よって、インデックスサーバは、並べ替えられていないデータベースのどのレコードが返されたのかを知らない。サーバが返すキーはマスキングされているので、サーバもまた、並べ替えられていないデータベースのどのレコードが返されたのかを知らない。よって、サーバはマスキングされたキーと、サーバがデータベースの決定の行を暗号化するために使用したキーを関連付けることはできない。これによって、安全なデータベースシステムは、レコードの安全な取り出しを提供し得る。さらに、記載の実施形態は、ｎに比例する時間でデータベースクエリにサービスを提供する。したがって、１Ｅ８個のレコードを含むデータベースでは、本発明の実施形態では、現在の例で、ｎ２／ｎすなわち１Ｅ８の効率向上が得られる。
【００１９】
図１は、例えば安全なデータの記憶および取り出しのために動作することができる、非制限的な一実施形態によるシステム１００を示す。システム１００はシステム１１０を備え、システム１１０は同様にサーバ（Ｓ）２００およびインデックスサーバ（ＩＳ）３００を備える。クライアント（Ｃ）４００はシステム１１０と通信して、データベース項目を取り出してもよい。クライアント４００、サーバ２００およびインデックスサーバ３００間の通信は、ネットワーク１２０を介してもよい。ネットワーク１２０は、例えばインターネットなど、有線、無線または光接続のいずれの組み合わせでもよい。サーバ２００およびインデックスサーバ３００は物理的に併置されていてもよいし、互いに離れていてもよい。いくつかの実施形態では、サーバ２００、インデックスサーバ３００およびクライアント４００は、インターネットを介して通信する。
【００２０】
図２は、サーバ２００の例示的な一実施形態を示す。サーバ２００は、プロセッサ（ＣＰＵ）２１０、メモリ２２０およびネットワークインタフェース２３０を備える。メモリ２２０は、本明細書に記載する機能をサポートするために、ＲＡＭ、ＲＯＭおよびディスク記憶装置のいずれの組み合わせを含んでもよい。メモリ２２０は、プロセッサ２１０によってアクセスおよび実行が可能な命令を含んでもよい。メモリ２２０はまた、例えば、クライアント４００への要求時に提供されてもよいデータ項目の配列などのデータベースレコードを含んでもよい。メモリ２２０は、データベース機能をサポートするために、例えば１００ＧＢまたはそれ以上のＲＡＭを含んでもよい。ネットワークインタフェース２３０は、インデックスサーバ３００およびクライアント４００と通信するための機能性を備えてもよい。例えば、ネットワークインタフェース２３０は、ＴＣＰ／ＩＰまたは類似の規格によってネットワーク１２０を介して通信するように構成されてもよい。
【００２１】
図３は、インデックスサーバ３００の例示的な一実施形態を示す。インデックスサーバ３００は、サーバ２００について説明したものと類似する機能ブロックを備えてもよい。例えば、インデックスサーバ３００は、プロセッサ３１０、メモリ３２０およびネットワークインタフェース３３０を備えてもよい。メモリ３２０は、プロセッサ３１０によってアクセスおよび実行が可能な命令、ならびに、下記に説明する様々なデータ構造およびクライアント４００からのデータアクセス要求を収容するためのメモリ空間を含む。
【００２２】
図４は、クライアント４００の一実施形態を示す。クライアント４００もまた、例えば、プロセッサ４１０、メモリ４２０およびネットワークインタフェース４３０などの、サーバ２００およびインデックスサーバ３００のものと類似した機能ブロックを含んでもよい。メモリ２２０は、プロセッサ４００によってアクセスおよび実行が可能な命令を含んでもよい。クライアント４００は、例えば、パーソナルコンピュータ、移動体通信コンピューティング装置（例えばｉＰＡＤ（Ｒ））、スマートフォン、ワークステーションまたはメインフレームコンピュータシステムなどであってもよい。
【００２３】
図５は、クライアント４００に安全なデータ取り出しを提供するための、サーバ２００およびインデックスサーバ３００の初期化の第１の実施態様を示す。データベース初期化の方法５００がステップＳ０５で開始し、このステップではサーバ２００が公開−秘密キーペアｋｐｐを生成し、公開キーをクライアント４００に送信する。サーバ２００は既にレコードＲ［ｉ］＝Ｒ［１］，Ｒ［２］，Ｒ［３］，…のデータベースを含んでいると仮定される。ステップＳ１０で、サーバ２００は少なくとも疑似ランダムにデータベースレコードの順序を並べ替えて、並べ替えられたデータベースＲ［πｉ］を生成する。換言すれば、データベース配列のレコードＲ［ｉ］は新しいデータベース配列にマッピングされ、そこでは、レコードインデックスｉは、少なくとも疑似ランダムに｛ｉ｝の組から選択される並べ替えられたインデックスπｉに置き換えられる。本明細書で、「少なくとも疑似ランダムに」という用語は、「ランダムな」値を生成する計算的な方法は本質的に何らかの決定のレベルを含むが、ランダムに生成された値と事実上識別不可能であり得るという了解を反映する。以下、計算および数字の組が制限なく「ランダムである」として記載されることがあるが、これらの計算または組は疑似ランダムにすぎないこともあるのを認めてのことである。
【００２４】
ステップＳ１５で、サーバ２００はランダムなキー配列ｋｒ［πｉ］を生成する。この配列は、並べ替えられたデータベースＲ［πｉ］の各レコードに関連するランダムなキー値ｋｒを含む。ステップＳ２０で、サーバ２００は、Ｒ［πｉ］の各値をそれぞれの関連するキー値ｋｒ［πｉ］を使用して暗号化することにより、暗号化されたデータベース配列Ｅ［πｉ］を生成する。ステップＳ２５で、サーバ２００は、キーペアｋｐｐの公開キーを使用してｋｒ［πｉ］の各メンバを暗号化して、暗号化されたキー配列を生成する。好ましい実施形態では、暗号化は準同型である。準同型暗号化（ＨＥ）の一例に、Ｐａｉｌｌｉｅｒ暗号がある。下記に、様々な実施形態でのＨＥの利用について記載する。本実施形態を反映するために、暗号化されたキー配列は、ｋｒ，ＨＥ［πｉ］と呼ばれるが、これに制限されない。ステップＳ３０で、サーバ２００は暗号化されたデータベース配列Ｅ［πｉ］および暗号化されたキー配列ｋｒ，ＨＥ［πｉ］をインデックスサーバ３００に送信する。ステップＩＳ０５で、インデックスサーバ３００は、Ｅ［πｉ］およびｋｒ，ＨＥ［πｉ］を記憶する。
【００２５】
ステップＩＳ０５が終了すると、システム１００の設定段階は終了する。Ｅ［πｉ］を生成するために使用される、記載の動作に起因して、サーバ２００は、Ｅ［πｉ］配列の内容を決定するための十分な情報をもたない。より具体的には、サーバ２００によって記憶されるＲ［ｉ］データベース配列は、インデックスサーバ３００によって記憶されるＥ［πｉ］配列とは異なってインデックス付けされ、これらの配列間の関係は、サーバ２００とインデックスサーバ３００のそれぞれから隠されるようになる。しかし、下記に記載するように、クライアント４００は、自身のみが知る情報を使用してデータベースレコードの値を決定できるので、従来の安全なデータベースシステムに比べて、システム１００にはより優れた安全性が提供される。
【００２６】
図６および図７を参照しながら、クライアント４００によるシステム１００からのデータの安全な取り出しの第１の実施形態について説明する。図６は、クライアント４００とサーバ２００の間の情報交換および、クライアント４００とインデックスサーバ３００の間の情報交換の上位レベルでの説明である。図７は方法７００を表し、本実施形態で、データベースクエリに応答してサーバ２００、インデックスサーバ３００およびクライアント４００によって実行される動作のより詳細な説明である。
【００２７】
図７を参照すると、ステップＣ０５で、クライアント４００は特定のレコードｎについてインデックスサーバ３００にクエリを送信する。このステップは、図６では、クライアント４００からインデックスサーバ３００への第１の通信に対応する。クエリに応答して、ステップＩＳ１０（図７）で、インデックスサーバはＥ［ｎ］およびｋｒ，ＨＥ［ｎ］をクライアント４００に送信する。このステップは、図６では、インデックスサーバ３００からクライアント４００への第２の通信に対応する。
【００２８】
続いて図７を参照すると、ステップＣ１０で、クライアント４００は、並べ替えられたデータベースの各項目についてランダムなマスク値を生成する。ステップＣ１５で、クライアント４００は、サーバ２００にキーｋｒ［ｎ］を復号するよう求める要求を作成する。しかし、サーバ２００がキー値を決定することを防ぐために、クライアント４００は最初に、ステップＣ１０で生成された対応するマスク値を加算することによってキーの値をマスキングする。これが可能な理由は、ステップＳ１０（図５）でのキー値の準同型暗号化である。よって、第１のサブステップＣ２０で、クライアント４００は、先にサーバ２００から受信した公開キーを使用して、ｋｒ，ＨＥ［ｎ］とｍａｓｋ［ｎ］の合計の準同型暗号化を実行する。当業者には理解されるように、準同型暗号化の性質から、暗号化されたｋｒ，ＨＥ［ｎ］値にｍａｓｋ［ｎ］などのオフセットを加算し、加算結果を暗号化して、後に、例えば下記のステップＣ３０で暗号化された合計を最初に復号することなく、ｍａｓｋ［ｎ］を減算することによってｋｒ［ｎ］値を復元することが可能である。サブステップＣ２５で、クライアント４００は、ｋｍ，ＨＥ［ｎ］をサーバ２００に送信する。このステップは、図６では、クライアント４００からサーバ２００への第３の通信に対応する。
【００２９】
ｋｍ，ＨＥ［ｎ］値の送信は、サーバ２００にｋｒ，ＨＥ［ｎ］を復号してマスクされたキーｋｍ［ｎ］を生成させるよう要求を開始する働きをする。ステップＳ３５（図７）で、サーバ２００は、例えばｋｐｐの秘密キーなどのｋｐｐを使用して、ｋｍ，ＨＥ［ｎ］を復号し、ｋｍ［ｎ］を復元する。この値は、この時点ではマスクされているので、サーバ２００は対応するｋｒ［ｎ］の値についての知識をもたない。ステップＳ４０で、サーバ２００はクライアント２００にｋｍ［ｎ］を送信する。このステップは、図６では、サーバ２００からクライアント４００への第４の通信として示される。
【００３０】
ステップＣ３０（図７）で、クライアント４００はｋｍ［ｎ］からｍａｓｋ［ｎ］を減算し、それによってｋｒ［ｎ］を復元する。ステップＣ３５で、クライアント４００はｋｒ［ｎ］を使用してＥ［ｎ］を復号して、Ｒ［ｎ］を得る。
【００３１】
前述の実施形態では、クライアント４００のみが暗号化されたデータＥ［ｎ］およびｍａｓｋ［ｎ］値を所有するので、クライアントのみが、Ｅ［ｎ］を復号するために必要な値ｋｒ［ｎ］を復元することができる。さらに、Ｒ［ｉ］配列からＲ［πｉ］配列への並べ替えにより、クライアント４００が復元しようとしているデータベースレコードをサーバ２００が決定できないことが確実になる。このようにして、クライアント４００は、例えば、サーバ２００またはインデックスサーバ３００がクライアント４００によって受信されたデータを決定することができないように、安全に、Ｒ［ｎ］の値を復元することができる。
【００３２】
図８−図１０は、システム１００の動作の第２の実施形態を示す。図８は、図５に示されるデータベース設定方法５００の実施形態の代替実施形態を説明する方法８００を示す。図９および図１０は、それぞれ、方法１０００の詳細な上位レベルでの説明を示す。この実施形態では、方法７００でクライアント４００によって行われた準同型動作を行うのは、インデックスサーバ３００である。そのような動作によって、クライアント４００がサーバ２００およびインデックスサーバ３００とオンライン状態であるために必要とする時間が短縮され得るが、追加のオフライン処理に負担がかかることもある。
【００３３】
図８を参照すると、ステップＳ０５−Ｓ３０およびＩＳ０５は、図５について前述したとおりである。方法８００では、ステップＩＳ０５の前にステップＩＳ１５があり、このステップで、インデックスサーバ３００は、例えば、ステップＣ１０（図７）について前述したように、各データベースレコードに対応するランダムなマスク値ｍａｓｋ［πｉ］を生成する。ステップＩＳ０５で、インデックスサーバ３００は、前述したように、配列Ｅ［πｉ］およびｋｒ，ＨＥ［πｉ］を記憶する。ステップＩＳ２０で、インデックスサーバ３００は、各データベースレコードについて、ｋｒ，ＨＥ［πｉ］（例えばｋｐｐの公開キーを使用）とｍａｓｋ［πｉ］の合計の準同型暗号化を、ｋｐｐの公開キーを使用して計算し、この合計はｋｍ，ＨＥ［πｉ］と呼ばれる。ステップＩＳ２５で、インデックスサーバ３００は、ｋｍ，ＨＥ［πｉ］の順序をランダムに並べ替え、並べ替えられた値の配列をサーバ２００に送信する。ステップＳ４５で、サーバ２００は並べ替えられたマスク配列を、ｋｐｐの秘密キーを使用して復号し、結果の値を記憶する。
【００３４】
図１０を参照すると、方法１０００は前述したステップＣ０５を含み、このステップで、クライアント４００はインデックスサーバ３００に暗号化されたレコードｎをクエリする。このクエリは、図９では、クライアント４００からインデックスサーバ３００への第１の通信として示される。インデックスサーバ３００は、ステップＩＳ３０で、クライアント４００にＥ［ｎ］およびｍａｓｋ［ｎ］を送信する。このステップは、図９では、クライアント４００とインデックスサーバ３００との間の第２の通信に対応する。ステップＩＳ３５で、インデックスサーバ３００は、並べ替えられたインデックスπｉをサーバ２００に送信する。このステップは、図９では、インデックスサーバ３００からサーバ２００への第３の通信に対応する。ステップＳ５０で、サーバ２００は、並べ替えられたインデックスを、並べ替えられたマスク配列の対応する値と関連付け、ステップＳ５５で、対応する値ｋｍ［πｉ］をクライアント４００に送信する。この送信は、図９では、サーバ２００からクライアント４００への第４の通信として示される。前述したように、ステップＣ３０で、クライアント４００はｋｍ［ｎ］からｍａｓｋ［ｎ］を減算することによってｋｒ［ｎ］を復元し、ステップＣ３５で、クライアント４００はｋｒ［ｎ］を使用してＥ［ｎ］を復号し、Ｒ［ｎ］を得る。
【００３５】
記載の実施形態で、サーバ２００、インデックスサーバ３００およびクライアント４００の動作は、記載の順序に限定されないことに留意されたい。他の実施形態では、記載の動作のステップは別の順序でもよく、もしくは結合または分離されてもよい。いくつかの実施形態では、本開示の範囲を逸脱することなく、図示されたステップのいくつかは削除されてもよく、他のステップが追加されてもよい。
【００３６】
本発明の複数の実施形態が添付の図面に示され、前述の、発明を実施するための形態に記載されているが、本発明は開示された実施形態に限定されず、下記の特許請求の範囲によって明記され定められる本発明から逸脱することなく、多数の再構成、修正および置換が可能であることを理解されたい。
【図１】
0005997851.tif 000002
【図２】
0005997851.tif 000003
【図３】
0005997851.tif 000004
【図４】
0005997851.tif 000005
【図５】
0005997851.tif 000006
【図６】
0005997851.tif 000007
【図７】
0005997851.tif 000008
【図８】
0005997851.tif 000009
【図９】
0005997851.tif 000010
【図１０】
0005997851.tif 000011