(57)【要約】  主題は、コンピュータ化システム上で動作する方法であって、データベース内のデータフィールドのうち少なくとも幾つかの２つの秘密シェアを生成する段階と、データベースのデータフィールドを２つのデータベースコピーにロードする段階であって、２つの秘密シェアのうち一方の秘密シェアは、一方のデータベースコピーにロードされ、２つの秘密シェアのうちもう一方の秘密シェアは、もう一方のデータベースコピーにロードされる、ロードする段階と、データベースでクエリを実行する依頼を受信する段階と、データベースコピー上で当該クエリを処理する段階であって、クエリプロセスで使用されるデータベースフィールドおよびクエリ結果は、処理の間秘密のままである、処理する段階と、秘密のクエリ結果を明らかにする段階とを備える方法を開示する。
2019500645.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ制御化されたシステム上で動作する方法であって、
データベース内のデータフィールドのうち少なくとも幾つかの２つの秘密シェアを生成する段階と、
前記データベースのデータフィールドを２つのデータベースコピーにロードする段階であって、前記２つの秘密シェアのうち一方の秘密シェアは、一方のデータベースコピーにロードされ、前記２つの秘密シェアのうちもう一方の秘密シェアは、もう一方のデータベースコピーにロードされる、ロードする段階と、
前記データベースでクエリを実行する依頼を受信する段階と、
前記データベースコピー上で前記クエリを処理する段階であって、クエリプロセスで使用される前記データフィールドおよびクエリ結果は、処理の間秘密のままである、処理する段階と、
秘密の前記クエリ結果を明らかにする段階と
を備える方法。
【請求項２】
秘密のクエリ結果を別のセキュアなパーティに送信する段階であって、前記セキュアなパーティは、前記クエリ結果を復号化する、送信する段階を更に備える、請求項１に記載の方法。
【請求項３】
秘密の前記クエリ結果を受信する前記セキュアなパーティは、ＭＰＣサーバである、請求項２に記載の方法。
【請求項４】
前記２つの秘密シェアは、ＸＯＲベースの方法を用いて秘密となる、請求項１から３の何れか一項に記載の方法。
【請求項５】
前記２つの秘密シェアは、加法的な秘密分散共有に基づく方法を用いて秘密となる、請求項１から４の何れか一項に記載の方法。
【請求項６】
前記２つの秘密シェアは、確率的検索可能暗号化に基づく方法を用いて秘密となる、請求項１から５の何れか一項に記載の方法。
【請求項７】
前記２つの秘密シェアを生成する段階は、ＭＰＣプロセスを用いて実行される、請求項１から６の何れか一項に記載の方法。
【請求項８】
前記ＭＰＣプロセスは、専用サーバにより実行される、請求項７に記載の方法。
【請求項９】
前記クエリを前記処理する段階は、秘密クエリツリーを利用する、請求項１から８の何れか一項に記載の方法。
【請求項１０】
前記クエリを前記処理する段階は、ガーブル化回路ベースのＭＰＣプロセスを含む、請求項１から９の何れか一項に記載の方法。
【請求項１１】
補助サーバが、ガーブル化回路を用いて前記クエリを処理する、請求項１０に記載の方法。
【請求項１２】
前記クエリを前記処理する段階は、セキュアなＭＰＣプロセスを使用する、請求項１０または１１に記載の方法。
【請求項１３】
前記クエリを処理する段階は、ランダムな順序で再編成される前記データベースのコピーを生成する段階を含む、請求項１から１２の何れか一項に記載の方法。
【請求項１４】
データベースの２つのコピーと、
データフィールドの一方の秘密シェアを記憶する一方のデータベースコピー、および、同じデータフィールドのもう一方の秘密シェアを記憶するもう一方のデータベースコピーと、
前記データベースコピーに対するクエリ演算を行うＭＰＣサーバであって、前記データフィールドは、クエリプロセスにおいて暗号化されたままである、ＭＰＣサーバと
を備えるコンピュータ制御化されたシステム。
【請求項１５】
前記２つのデータベースコピーは、単一のサーバに記憶される、請求項１４に記載のコンピュータ制御化されたシステム。
【請求項１６】
前記２つのデータベースコピーは、２つのサーバに記憶される、請求項１４または１５に記載のコンピュータ制御化されたシステム。
【請求項１７】
前記２つのデータベースコピーは、暗号化データフィールドを含む、請求項１４から１６の何れか一項に記載のコンピュータ制御化されたシステム。
【請求項１８】
前記２つのデータベースの前記データフィールドは、秘密シェアを用いて暗号化され、シェアが前記データベースコピー間で分散共有される、請求項１４から１７の何れか一項に記載のコンピュータ制御化されたシステム。
【請求項１９】
前記ＭＰＣサーバは、クエリ結果の前記データフィールドを復号化する、請求項１４から１８の何れか一項に記載のコンピュータ制御化されたシステム。
【請求項２０】
前記ＭＰＣサーバは、前記データフィールドを明らかにするために、前記データベースコピーを含む前記サーバを用いてマルチパーティ計算プロトコルを行う、請求項１４から１９の何れか一項に記載のコンピュータ制御化されたシステム。
【請求項２１】
ＸＯＲベースの方法を用いて前記データフィールドを暗号化する暗号化モジュールを更に備える、請求項１４から２０の何れか一項に記載のコンピュータ制御化されたシステム。
【請求項２２】
加法的な秘密分散共有方法を用いて前記データフィールドを暗号化する暗号化モジュールを更に備える、請求項１４から２１の何れか一項に記載のコンピュータ制御化されたシステム。
【請求項２３】
確率的検索可能暗号化方法を用いて前記データフィールドを暗号化する暗号化モジュールを更に備える、請求項１４から２２の何れか一項に記載のコンピュータ制御化されたシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してデータベース暗号化に関するものであり、より具体的には、暗号化データを復号化することなくそれに対するセキュアなクエリ演算を行うように設計される一式のプロトコルを提供する、データベース暗号化の方法およびシステムに関する。
【背景技術】
【０００２】
データベースおよびビジネスインテリジェンスが、ビジネス、産業および教育で広く使用されている。データリソースを通信ネットワークに接続することにより、いつでもどこからでも情報へアクセスできるようになり、被雇用者の生産性が高まる。現存するビジネス環境において、データベースに記憶される情報を管理するアプリケーションへのアクセスは、ビジネス単位、法人または企業のネットワークから可能である。場合によっては、インターネット基盤を利用することにより、リモートアクセスを介してデータベースおよび情報への接続を行うことも可能である。
【０００３】
最近のコンピュータ技術の発達に伴い、セキュリティ侵害を不当に行う手段が発達している。多くの場合は、強力な暗号化技術によってある程度保護される。それにもかかわらず、データベースへの侵害はかなり頻繁に起きる。更に、極秘データへのアクセスを試みる無権限者は、単にデータベースに記憶されている保存データへのセキュリティ侵害を行うには留まらない。場合によっては、使用中のデータを分析するために統計ツール等の洗練されたユーティリティが使用されることもある。係る使用中のデータは、データベースにアップロードされるデータ、または、ＳＱＬ演算中に露出されるデータであり得る。ＳＱＬ演算中のデータ保護は、セキュリティエンジニアおよびデータ管理者に大きな課題をもたらす。なぜなら、使用中のデータで利用される暗号化方法および復号化方法が、データベースに記憶されるデータで利用される暗号化方法および復号化方法と互換性を持っている必要があるからである。
【発明の概要】
【０００４】
本発明は、ＳＱＬベースのデータベースを暗号化することと、データを一切復号化することなく当該データベースに対するＳＱＬ演算を実行するように設計される一式の暗号化プロトコルを提供することとを行うための、コンピュータ制御化されたシステム上で実行される方法を開示する。係るＳＱＬ演算は、データベース内のデータおよび情報を検索するために使用される、クエリの予約語、予約用語、予約コマンドおよび予約条件を含むクエリに従って実行され得る。係るクエリは、場合によって、データおよび情報を検索するために使用される表、クエリツリー、コードまたはスクリプトを含んでよい。開示される方法およびそれに関連するコンピュータ制御化されたシステムは、空の場合もある２つのデータベースコピーを生成すること、次いで当該データベースコピーを２つの分離されたサーバにコピーすることにより、データベース生成から始まるデータベース暗号化を提供し得る。コンピュータ制御化されたシステムは、２つのデータベースコピーにロードされるデータを暗号化するように構成されてもよい。ここで、秘密シェアは、２つのデータベースコピー間で分割され得る。場合によっては、データベースの一方のコピーの暗号化鍵が、２つのサーバ間で分散共有されるＸＯＲであってよい。例えば、データベース内の値に対して、乱数ｘを用いたＸＯＲ演算が行われ得る。乱数「ｘ」は、一方のデータベースコピーに記憶される一方のシェアであってよく、値「ｘ」を用いたＸＯＲ演算の結果は、他方のデータベースコピーに記憶される他方のシェアであってよく、ワンタイムパッド暗号化が効果的に達成される。場合によっては、データベースコピー内のデータを暗号化するために加法的な秘密分散共有という方法が利用されてもよい。データベース内の値を暗号化するために、確率的検索可能暗号化等の追加的方法が利用され得る場合もある。
【０００５】
コンピュータ制御化されたシステムは、クエリに関与しているデータベース表とクエリコマンドタイプとから成るクエリツリーを受信するとデータベースに対するクエリ演算を実行するように構成されてもよい。コンピュータ制御化されたシステムは、セキュアなバージョンのクエリツリーを作成するように構成されてもよい。故に、クエリの表、列および条件値の名前は、セキュアなバージョンのクエリツリーで暗号化されてよい。本発明の幾つかの実施形態において、システムは、クエリ演算を受信し、かつ、セキュアなクエリツリーを生成するように設計されるＳＭＰＣ（セキュアなマルチパーティ計算）プロキシサーバを備えてよい。ひとたびセキュアなバージョンのクエリツリーが生成されると、コンピュータ制御化されたシステムは、データベースコピーをホストしているサーバへセキュアなクエリツリーを送信することにより、暗号化クエリ演算を行い得る。データベースコピーをホストしているサーバは、セキュアなクエリツリーを受信し、クエリを処理すべくセキュアなマルチパーティ計算プロトコルを行うことによりどの暗号化値がクエリ演算を満たすかを判断し、第３のサーバに最終結果を返し得る。データベースコピーをホストしているサーバは、データベースの新たな暗号化コピーをランダムな順序で生成することにより、複数のクエリに関するアクセスパターンの分析に基づいて漏洩を防ぐこともできる。
【図面の簡単な説明】
【０００６】
本明細書では、本発明の幾つかの実施形態が、添付図面を参照しながら単なる例として説明される。ここで図面を詳しく具体的に参照すると、これらの具体的事項が、本発明の実施形態を例示的に説明するために例として示されていることに留意されたい。これに関連して、図面を用いた説明からは、本発明の実施形態がいかに実施され得るかが当業者にとって明らかになる。図面は以下の通りである。
【０００７】
【図１】データベースにデータをロードするプロセスにおけるデータの暗号化方法を構成する、本発明の例示的な実施形態に係るプロセスを開示している。
【０００８】
【図２】ランダムな順序でのデータの新たな分散共有を受けてデータベースの別の暗号化コピーを生成するように設計される、本発明の例示的な実施形態に係る暗号化ミックスプロトコルを開示している。
【０００９】
【図３】データベースの値間のリンクもデータベースの構造も明かすことなく、ＳＱＬ演算をセキュアなやり方で実行することが可能となるように構成される、本発明の例示的な実施形態に係るセキュアなプロトコルを開示している。
【００１０】
【図４】ＳＭＰＣプロキシサーバにより行われる、トークン化クエリツリーを作成してそれらをＳ１、Ｓ２およびＳ３へ送信するための、本発明の例示的な実施形態に係るプロセスを開示している。
【００１１】
【図５】ＳＱＬクエリを処理するための、本発明の例示的な実施形態に係る方法を開示している。
【００１２】
【図６】２つのデータベースサーバに分割されるデータベースと、当該データベースにデータをロードするように設計されるＥＴＬサーバと、ＭＰＣ計算を高速化させるために使用される補助サーバＳ３とを備える、本発明の例示的な実施形態に係るコンピュータ制御化されたシステムを開示している。
【００１３】
【図７】基になるＳＱＬクエリフローにおいて基本的なＳＱＬ演算を処理する、本発明の例示的な実施形態に係る方法を開示している。
【００１４】
【図８】Ｓ１およびＳ２にあるＳＱＬデータベースにデータをロードして当該ＳＱＬデータベースに対するＳＱＬクエリプロセスを行う、本発明の例示的な実施形態に係る方法を開示している。
【発明を実施するための形態】
【００１５】
本発明は、ＳＱＬベースのデータベースを保護することと、当該データベースに対して実行されるクエリ演算を保護するように設計される一式の暗号化プロトコルを提供することとを行うための方法およびコンピュータ制御化されたシステムを開示する。方法は、データベースにロードされるデータを、暗号化データに対するＳＱＬ演算の実行が可能となるようなフォーマットで暗号化するように設計される暗号化プロトコルを提供する。本発明の方法は、暗号化ミックスプロトコルと称される暗号化プロトコルも開示する。当該暗号化プロトコルは、ランダムな順序で構造化される、データベースの暗号化および分散共有された新たなコピーを生成して、データベースに対する標準的なＳＱＬ演算をセキュアなやり方で行うことを可能とする。故に、暗号化データのデータ検索をランダムな順序で実行することにより、データフィールドの値が非表示となり、新たなコピーにおけるデータの元の位置が非表示となる。例えば、特定のデータベース内で２５歳を超える人の数を数えるためにＳＱＬ集約関数が実行される場合は、当該暗号化ミックスプロトコルが、ランダムな順序でのデータの新たな分散共有を受けてデータベースの暗号化コピーを生成し、ＳＱＬ集約関数を実行し、結果を出力し得る。次いで、２５歳を超える人を検索するために、同じＳＱＬ集約関数が再び使用され得る。暗号化ミックスプロトコルは、ランダムな順序でのデータの新たな分散共有を受けてデータベースの暗号化コピーを再生成してよく、これは、同じＳＱＬクエリが処理されるとはいえ、必ずしも前の検索演算と同じ順序でなくてよい。
【００１６】
本発明の幾つかの実施形態において、Ｓ１およびＳ２と称される、データベースを備える２つのサーバは、インターネット、ＬＡＮおよびＷＡＮ等といった通信ネットワークを介して通信するように構成されてよい。コンピュータ化システムは、セキュアな計算プロトコルを高速化させるために利用される第３のサーバＳ３と、クエリを受信し、クエリを暗号化し、暗号化されたクエリを、クエリを処理するためのＳ１、Ｓ２、Ｓ３へ送信し、結果を返すように設計されるＳＭＰＣ（セキュアなマルチパーティ計算）プロキシサーバとを備えてもよい。場合によっては、Ｓ３がデータベースのコピーを含んでもよい。
【００１７】
図１は、データベースにデータをロードする間にデータの暗号化方法を構成する、本発明の例示的な実施形態に係る方法を開示している。段階１０５では、Ｓ１およびＳ２が、空のデータベースのローカルコピーを２つ生成する。場合によっては、係るローカルコピーが、２つの類似データベースを生成する自動プロセスで生成されてよい。１つのローカルコピーが、サーバのうち一方、Ｓ１またはＳ２で生成されてよく、次いで、空のデータベースが他方のサーバにコピーされ得る場合もある。段階１１０では、データベースの管理者がデータベース内の秘密フィールド、すなわち秘密のままであるべきフィールドを定義し得る。データベース内の秘密フィールドは、暗号化されたままであり、フィールドの値は非表示のままである。例えば、データベース管理者は、表内のトランザクションの日付が表示されたままとなるように指定し得る。段階１１５では、データベース秘密フィールドがサーバＳ１とサーバＳ２との間で分散共有されるＸＯＲである。
例えば、値ｘは、ランダムな
【数１】
2019500645.tif 000003
を選択すること、および
【数２】
2019500645.tif 000004
と設定することにより分散共有されるＸＯＲである。
ここで、
【数３】
2019500645.tif 000005
はＸＯＲ演算を表し、｜ｘ｜は乱数Ｘ１の長さを表し、Ｘ１およびＸ２はシェアである。
【００１８】
段階１２０では、データベースの秘密数値フィールドも加法的な秘密分散共有を用いて暗号化される。場合によっては、１つまたは複数の所定のＳＱＬクエリが当該値に対して使用される可能性に従って、複数の加法的な分散共有方法が、ＳＱＬ演算中に秘密数値フィールドを暗号化するために利用されてよい。例えば、ＳＵＭ  ＳＱＬ集約関数の使用が可能なフィールドの場合は、加法的な分散共有を用いて、例えばモジュロ２１２８を用いてフィールドが分散共有されてよい。
故に、値ｖは、ランダムな
【数４】
2019500645.tif 000006
（ここで、１２８は値ｖ１の長さを表す）を選択すること、および
【数５】
2019500645.tif 000007
と設定することにより加法的に分散共有される。
このような場合は、値ｖ１および値ｖ２がＳ１およびＳ２により記憶されるシェアを表す。追加の加法的な分散共有方法が、ＳＴＤＥＶ  ＳＱＬ集約関数の使用が可能な数値フィールドに適用されてよい。秘密フィールドは、値モジュロ２１２８で二乗の加法的な分散共有を用いて分散共有されてよい。
故に、値ｖの二乗は、異なるランダムな
【数６】
2019500645.tif 000008
（ここで、１２８は値ｖ１の長さを表す）を選択すること、および
【数７】
2019500645.tif 000009
と設定することにより加法的に分散共有される。
このような場合は、値ｖ１およびｖ２がＳ１およびＳ２により記憶されるシェアである。
【００１９】
段階１２５は、ＥＱＵＡＬＳ検索関数および任意のタイプのＭＡＴＣＨ演算に使用され得る秘密フィールドで確率的検索可能暗号化を利用することにより秘密データベースのフィールドを暗号化する段階を開示している。係るＭＡＴＣＨ演算は、ＧＲＯＵＰ  ＢＹ、ＪＯＩＮ、ＳＥＴおよびＣＯＵＮＴ−ＤＩＳＴＩＮＣＴを含む多くのＳＱＬ演算で使用される。任意の確率的検索可能暗号化方法が使用されてよい。異なる演算については、異なる確率的検索可能暗号化鍵が必要である。故に、このプロセスは、３つの暗号化鍵Ｋ１、Ｋ２およびＫ３を生成してよい。
３つの暗号化鍵を生成するプロセスは、
【数８】
2019500645.tif 000010
により取得され得る擬似ランダム鍵Ｋｘを利用してよい。
関数Ｆは任意の擬似ランダム関数である。
ある例示的な方法は、
【数９】
2019500645.tif 000011
を計算することにより
【数１０】
2019500645.tif 000012
と定義する。ここで、関数
【数１１】
2019500645.tif 000013
はハッシュ関数（例えばランダムオラクルとしてモデル化される関数）であり、
【数１２】
2019500645.tif 000014
はランダム性抽出器であり、Ｇは位数ｑの楕円曲線群である。
場合によっては、値ｘを与えることにより、
【数１３】
2019500645.tif 000015
が、Ｓ１およびＳ２を用いて行われるＭＰＣプロセスにおいてＳＭＰＣプロキシサーバにより計算され得る。Ｋｘが取得されると、Ｋｘから３つの暗号化鍵が導出される。これらは以下のように計算されてよい。
・Ｋ１＝８０ビットに切り詰められたＳＨＡ２５６（１｜｜Ｋｘ）
・Ｋ２＝長さ２５６ビット（楕円曲線群の群位数ｑのサイズ）のＳＨＡ２５６（２｜｜Ｋｘ）
・Ｋ３＝ＳＨＡ２５６（３｜｜スキーマ名｜｜表名｜｜列名｜｜Ｋｘ）
【００２０】
場合によっては、このプロセスは、データベースのフィールド上で実行される分散共有方法に従って、鍵Ｋ１、Ｋ２およびＫ３を用いた確率的検索可能暗号化により当該フィールドを暗号化してよい。例えば、
・任意のタイプのＭＡＴＣＨ演算に関与し得る秘密フィールドでＫ１が使用されてよい。値Ｋ１はＳ１とＳ２との間で分散共有されるＸＯＲであり、図３で定義されるリンク可能なマッチングプロセスの場合に使用され得る。
・確率的検索可能暗号化が秘密フィールドに適用され、クエリが任意のタイプのＳＱＬ  ＭＡＴＣＨ演算を伴うときに、Ｋ２が使用されてよい。値Ｋ２は、Ｓ１とＳ２との間でモジュロｑ（ここで、ｑは使用されている楕円曲線群の位数である）で加法的に分散共有されて、図３で定義されるリンク不可能なマッチングプロセスの場合に使用され得る。
・ＥＱＵＡＬＳによる検索が可能な秘密フィールドにおける確率的検索可能暗号化の検索にＫ３が使用されてよい。フィールドは、鍵Ｋ３による任意の検索可能暗号化方法を用いて暗号化され得る。
ある例示的な方法は以下の通りである。
・ランダムな
【数１４】
2019500645.tif 000016
を選択する。
・z =
【数１５】
2019500645.tif 000017
を計算して、
【数１６】
2019500645.tif 000018
をｚの最初の６４ビットとする。
・暗号化値=
【数１７】
2019500645.tif 000019
【００２１】
本発明で開示される方法は、鍵Ｋ３を検索可能暗号化鍵として利用する検索可能暗号化プロセスも含んでよい。故に、検索可能暗号化プロセスを用いてデータベース内の値ｘに対するＥＱＵＡＬＳ等の検索演算を実行すべく、ＳＭＰＣプロキシサーバは、Ｓ１およびＳ２に個別に記憶されるデータフィールドでＭＰＣ手続きを用いてＫｘを計算し、次いでＫ３をローカルで計算し、次いでＳ１およびＳ２にＫ３を提供し得る。
鍵Ｋ３を受信すると、Ｓ１およびＳ２は、
【数１８】
2019500645.tif 000020
の最初の６４ビットが
【数１９】
2019500645.tif 000021
に等しいかどうかをペア
【数２０】
2019500645.tif 000022
ごとにテストすることにより、値をローカルで検索し得る。
図２は、ランダムな順序でのデータの新たな分散共有を受けてデータベースの暗号化コピーを生成するように設計される、本発明の例示的な実施形態に係る暗号化ミックスプロトコルを開示している。段階２０３において、Ｓ１、Ｓ２およびＳ３は、Ｋ１２がＳ１とＳ２との間で分散共有されるＡＥＳ鍵であるように、Ｋ１３がＳ１とＳ３との間で分散共有されるＡＥＳ鍵であるように、かつ、Ｋ２３がＳ２とＳ３との間で分散共有されるＡＥＳ鍵であるように分散鍵を生成する。場合によっては、分散共有されるＡＥＳ鍵が既に用意されていてよく、生成プロセスが省略されてよい。例えば、Ｓ１、Ｓ２およびＳ３は、暗号化ミックスプロトコルの前の演算からのＡＥＳ分散鍵を利用してよい。場合によっては、擬似ランダム値をセキュアに生成するための別の方法で分散鍵が使用される。
【００２２】
段階２０５では、秘密フィールド内の値のセキュアな再分散共有化を生成するために、Ｓ１、Ｓ２が分散鍵Ｋ１２を生成する。セキュアな再分散共有プロセスは、サーバの各々のペアの間で行われる。秘密フィールド内の値を再分散共有するプロセスは、分散共有される暗号化値を交換するための補助サーバとしてＳ３を利用する。場合によっては、以下に定義されるセキュアな再分散共有プロセスを行うために、Ｓ１およびＳ２が、自らの分散鍵Ｋ１２を利用することにより当該プロセスを開始してよい。
・Ｓ１とＳ２との間に値の新たなＸＯＲシェアを生成する。
・Ｓ１とＳ２との間に値の新たな加法的シェアを生成する。
・Ｓ１およびＳ２の両方により保持される値の新たなシェアを生成する。
・値の新たなシェアが生成されると、Ｓ１およびＳ２は、分散共有されるＡＥＳ鍵Ｋ１２を利用して分散値をリオーダしてよい。
【００２３】
段階２１０では、Ｓ１とＳ２との間の再分散共有プロセスから得られるリオーダされた値をＳ１がＳ３に送信することにより、Ｓ２およびＳ３がデータベースの分散共有を保持する。段階２１５では、Ｓ２およびＳ３が、鍵Ｋ２３を生成することにより、先ほど詳述されたのと同じセキュアな再分散共有プロセスを行い得る。故に、Ｓ２およびＳ３は、新たなＸＯＲシェアを生成し、新たな加法的シェアを生成し、Ｓ２およびＳ３の両方により保持される値の新たなシェアを生成し、次いで鍵Ｋ２３を利用して分散値をリオーダする。段階２２０では、Ｓ２とＳ３との間のセキュアな再分散共有プロセスから得られるリオーダされた値をＳ２がＳ１に送信することにより、Ｓ１およびＳ３がデータベースの分散共有を保持する。段階２２５では、Ｓ３とＳ１との間のセキュアな再分散共有プロセスが鍵Ｋ１３を生成しながら行われる。故に、Ｓ３およびＳ１は、新たなＸＯＲシェアを生成し、新たな加法的シェアを生成し、Ｓ３およびＳ１の両方により保持される値の新たなシェアを生成し、次いで鍵Ｋ１３を利用してシェアをリオーダする。段階２３０では、Ｓ３が、Ｓ３とＳ１との間の再分散共有プロセスから得られるリオーダされた値をＳ２に送信する。
【００２４】
段階２３５では、セキュアな再分散共有プロセスが完了し、元のデータベースとリンク可能ではない混合型の更新されたシェアをＳ１およびＳ２が保持し、新たなコピーでのトランザクションから前のコピーまたは元のコピーでトランザクションがあった場所へのリンクが残らないやり方で、分散値がランダムにリオーダされる。場合によっては、既知のアルゴリズムまたは手続きがこのタスクに利用されてよい。例えば、本発明の幾つかの実施形態では、データベース内の分散値をリオーダするために、フィッシャー・イェーツ・アルゴリズムが利用されてよい。
【００２５】
図３は、データベースの値間のリンクをＳ１、Ｓ２、Ｓ３にもＳＭＰＣプロキシサーバにも明かすことなく、ＳＱＬ  ＭＡＴＣＨ演算をセキュアなやり方で実行することが可能となるように構成される、本発明の例示的な実施形態に係るセキュアなプロトコルを開示している。段階３０５は、リンク不可能なマッチングプロセスの閾値を設定する段階を開示している。リンク不可能なマッチングプロセスは、ＳＱＬ  ＭＡＴＣＨ演算を可能にするプロセスとして定義されてよい。ここで、データベースの値間のリンクおよびデータベースの構造は、Ｓ１、Ｓ２、Ｓ３に対してもＳＭＰＣプロキシサーバに対しても非表示のままである。故に、データベース管理者は、リンク不可能なマッチングプロセスを実行するための閾値を、サーバＳ１および／またはサーバＳ２と通信するコンピュータ制御化されたデバイスに入力してよい。係る閾値は、場合によって、リンク不可能なマッチングプロセスが有効となり得る配列の最小サイズを定義する数値であってよい。例えば、ＡおよびＢが、ＳＱＬ  ＭＡＴＣＨ演算を行おうとしているデータの２つの配列であると仮定する。次いで、配列Ａおよび配列Ｂの全体的なサイズが設定閾値を下回っている場合は、リンク不可能なマッチングプロセスが行われてよい。配列Ａおよび配列Ｂの全体的なサイズが設定閾値を超えている場合は、リンク可能なマッチングプロセスが行われてよい。リンク可能なマッチングプロセスは、より効率的であるが、Ｓ３に対してのみデータの幾つかのパターンを明かす。故に、このプロセスは、マッチングされる配列が閾値を超えるときに使用される。
【００２６】
段階３１０では、ＳＭＰＣプロキシサーバが、Ｓ１およびＳ２にあるデータベースへのＳＱＬベースのクエリを受信する。当該クエリは、データベースに記憶されるデータを受信すべく、表現、コマンド、句およびクエリコマンド等を含んでよい。加えて、Ｓ３は、受信されたＳＱＬ  ＭＡＴＣＨ演算に関与しているデータの２つの配列が、リンク不可能なマッチングプロセスの閾値を満たすかどうかを確認し得る。例えば、配列Ａおよび配列Ｂから共通の値を持つ行を抽出して行のより小さな組にするＧＲＯＵＰ  ＢＹ句が特定のクエリに現れた場合は、配列Ａおよび配列Ｂの全体的なサイズが設定閾値を超えているかどうかをＳ３が確認し得る。
【００２７】
段階３１５は、受信されたＳＱＬ  ＭＡＴＣＨ演算に関与している分散値が閾値を満たすかどうか、およびリンク不可能なマッチングプロセスが行われ得るかどうかを判断する段階を開示している。分散値が閾値を下回っている場合は、段階３２０が実行され、この段階では、Ｓ１およびＳ２がリンク不可能なマッチングプロセスを実行する。リンク不可能なマッチングプロセスは、Ａ［ｉ］＝Ｂ［ｊ］となるようにｉとｊとの全てのペアを出力する、Ｓ１、Ｓ２およびＳ３間のセキュアなＭＰＣプロトコルを行うことにより実行されてよい。
【００２８】
段階３２５は、受信されたＳＱＬ  ＭＡＴＣＨ演算に関与している分散値が閾値を超えているために、リンク可能なマッチングプロセスが行われ得る場合を開示している。シェアが閾値を超えている場合に実行される段階３２５では、Ｓ１およびＳ２が、リンク可能なマッチングプロセスを実行する。リンク可能なマッチングプロセスは、以下の段階を実行してよい。１．Ｓ１およびＳ２は、配列Ａの確定的に暗号化された値Ａ［ｉ］と配列Ｂの確定的に暗号化された値Ｂ［ｊ］とのＸＯＲシェアを有する。ここで、ｉおよびｊは自然数である。２．Ｓ１およびＳ２は、シェアをＳ３に送信する。３．Ｓ３は、確定的に暗号化された値を出力する、当該シェアに対するＸＯＲ演算を実行する。４．Ｓ３は、Ａ［ｉ］＝Ｂ［ｊ］となるようにｉとｊとの特定のペアを識別する。５．Ｓ３は、マッチングした値をＳ１、Ｓ２に返す。
【００２９】
図４は、ＳＭＰＣサーバにより行われる、トークン化クエリツリーを作成してそれらをＳ１、Ｓ２およびＳ３へ送信するための、本発明の例示的な実施形態に係るプロセスを開示している。ＳＭＰＣサーバはプロキシサーバであってよい。段階４０５は、ＳＱＬクエリのためのクエリツリーを作成するＳＭＰＣプロキシサーバを開示している。係るＳＱＬクエリは、ＳＱＬデータベース内で検索するように設計され、かつ、Ｓ１およびＳ２に記憶されるＳＱＬデータベース内で検索するように構成されるＳＱＬアプリケーションを動作させるコンピュータ制御化されたデバイスにより生成され得る。例えば、特定のＳＱＬデータベース内で２０歳を超える全ての人を検索するために、コンピュータ制御化されたデバイスで動作するアプリケーションが使用され得る。このような場合は、データベースに接続されるＳＱＬアプリケーションが、ＳＱＬクエリツリーを作成してＳＭＰＣプロキシサーバに送信してよい。クエリツリーは、ＳＱＬクエリ演算およびそれに関連する表を含んでよく、これらの関係はクエリで使用される。クエリ表は、少なくとも１つのＳＱＬコマンドと、それに関連するデータベースの、当該コマンドを実行するための関係構造を成す表とを含み得る。場合によっては、データベース表の関係構造が、クエリ内でどのコマンドまたは演算子が呼び出されているのかを提示してよい。場合によっては、データベース表が表名でクエリツリーに提示されてよい。データベース表が番号でクエリツリーに提示され得る場合もある。
【００３０】
段階４１０では、ＳＭＰＣプロキシサーバが、クエリツリー内のデータベース表の表名もしくは表番号および／または列名もしくは列番号をトークンに置換する。係るトークンは、名前または番号の暗号化された形であってよい。係るトークンは、擬似ランダム関数等の確定的暗号化を平文値に適用することにより生成されてよい。場合によって、トークン化されたプロセスは、より多くの情報を追加する段階を含み得る。
【００３１】
段階４１５では、ＳＭＰＣプロキシサーバがＳ３へのトークン化クエリツリーを作成する。係るトークン化クエリツリーは、クエリツリー内の表名または配列名のうち少なくとも幾つかがトークンに置換されるクエリツリーであってよく、場合によっては、Ｓ３に送信されるトークン化クエリツリーの一部を編成する検索条件内の値が取り除かれてよい。例えば、トークン化クエリツリーが、ＷＨＥＲＥ  ａｇｅ＞２０（ここで、ａｇｅは、データベース内の年齢を含む配列名を表す）というクエリを含む場合は、Ｓ３に送信されるトークン化クエリツリーがＷＨＥＲＥ句を含むことができ、検索条件値２０が取り除かれてよい。段階４２０では、ＳＭＰＣプロキシサーバがトークン化クエリツリー内の検索条件の値の部分をランダムなシェアへと分割して、Ｓ１およびＳ２用の２つのトークン化クエリツリーを作成する。ここで、検索条件内の値は、当該２つのトークン化クエリツリー間で分散共有される。例えば、ＷＨＥＲＥ句の閾値がモジュロ２１２８で２つの加法的シェアに分割され得る。ここで、一方の加法的シェアは、Ｓ１へ渡されるトークン化クエリツリーに追加され、一方の加法的シェアは、Ｓ２へ渡されるトークン化クエリツリーに追加される。場合によっては、ＳＱＬ関数のタイプに従って、異なる分割方法が異なる条件値に利用されてよい。例えば、ＨＡＶＩＮＧ句のＳＵＭ関数およびＡＶＧ関数の閾値は、モジュロ２１２８で２つの加法的シェアとして渡されてよく、ＨＡＶＩＮＧ句のＳＴＤＥＶ関数の閾値は、モジュロ２１２８で閾値の二乗の２つの加法的シェアとして渡されてよい。場合によっては、検索条件内の値のうち幾つかがＸＯＲシェアに分割されてよい。ここで、各ＸＯＲシェアは、トークン化クエリツリーに追加されてよい。段階４２５は、ＷＨＥＲＥ  ＥＱＵＡＬＳ句を処理するために検索可能暗号化が行われ得る場合に、Ｓ１のトークン化クエリツリーおよびＳ２のトークン化クエリツリーに鍵Ｋ３を追加する段階を開示している。故に、検索可能暗号化が使用され得るそれぞれの値に対して、元の条件値の代わりに、鍵Ｋ３がＳ１のトークン化クエリツリーおよびＳ２のトークン化クエリツリーに追加および生成される。
【００３２】
段階４３０は、トークン化クエリツリーをＳ３に送信するＳＭＰＣプロキシサーバを開示しており、段階４３５は、ＳＭＰＣプロキシがＳ１用に作成されるトークン化クエリツリーをＳ１に、Ｓ２用に作成されるトークン化クエリツリーをＳ２に送信する段階を示している。
【００３３】
図５は、ＳＱＬクエリを処理する、本発明の例示的な実施形態に係る方法を開示している。段階５０５は、クエリツリーを受信するＳ１およびＳ２を開示している。場合によっては、当該クエリツリーが、先ほど定義されたような、ＳＭＰＣプロキシサーバから受信されたトークン化クエリツリーであってよい。段階５１０では、暗号化されていない属性によりデータフィールドを検索すべく、Ｓ１およびＳ２がトークン化クエリツリーを受信し、平文フィルタリングプロセスを開始する。例えば、Ｓ１およびＳ２は、データベース表内の日付を含むフィールドをフィルターで除去し得る。このような場合は、クエリがＷＨＥＲＥ  ＤＡＴＥ＞１．１．２０００を含むと、データベース内の１．１．２０００またはそれ以降の日付を含む全てのトランザクションをＳ１およびＳ２の各々が読み出す。段階５１２では、クエリの検索可能暗号化ＷＨＥＲＥ  ＥＱＵＡＬＳリーフを用いて表内の残りの行をフィルタリングするように設計される検索可能暗号化フィルタリングプロセスをＳ１およびＳ２が実行し、これらをトークン化クエリツリーに追加する。例えば、演算子ＥＱＵＡＬＳを含むＷＨＥＲＥ句が特定の表内で検索をするように現れ、かつ、先ほど開示されたように検索可能暗号化により属性が暗号化される場合は、Ｓ１およびＳ２が表内の行ごとに別々に検索可能暗号化検索プロセスを実施する。段階５１３では、ＭＰＣを用いた論理表現を含むクエリにより、Ｓ１およびＳ２がデータフィールド上での検索を行う。係る論理表現は、＞、＜および＝等であってよい。段階５１５は、図２で開示されるようにランダムな順序でのデータベースの異なる分散共有を受けてデータベースのコピーを生成すべく、Ｓ１およびＳ２が暗号化ミックスプロトコルを行い得る任意の段階を開示している。故に、ＳＱＬクエリプロセスは、Ｓ１およびＳ２により保持される新たに生成されたデータベースコピーを利用し得る。ここで、データベース表は、ＸＯＲシェアおよび／または加法的シェアを用いて暗号化されてよい。
【００３４】
段階５２０は、トークン化クエリツリーを利用することにより、段階５１５で生成されるデータベースコピーに対する残りのＳＱＬクエリ演算を実行するための、Ｓ１およびＳ２により行われるプロセスを開示している。係る残りのＳＱＬクエリ演算は、段階５１０、５１２または５１３では実施されなかったＳＱＬ演算であってよい。本発明の幾つかの実施形態において、トークン化クエリツリーは、ＰｏｓｔｇｒｅＳＱＬの表現ツリーに基づいたものであってよい。基になるクエリのＳＱＬ演算は、Ｓ１およびＳ２にある暗号化データベースに対して実行されてよい。故に、ＳＱＬ演算は、下の図８で定義されるように暗号化プロセスの仕様に従って行われてよい。
【００３５】
段階５２５は、基になるＳＱＬクエリを満たした値をＳ１およびＳ２が返す段階を示している。係る値は、ＳＱＬの元のクエリに応じて、表、配列、データおよび列等であり得る。場合によっては、Ｓ１およびＳ２がＳＭＰＣプロキシサーバに結果のＸＯＲシェアまたは加法的シェアを返してよく、ＳＭＰＣプロキシサーバが最終結果を算出してよい。
【００３６】
図６は、２つのデータベースサーバに分割されるデータベースと、当該データベースにデータをロードするように設計されるＥＴＬサーバと、ＭＰＣ計算を高速化させるために使用される補助サーバＳ３とを含む、本発明の例示的な実施形態に係るコンピュータ制御化されたシステムを開示している。図６は、Ｓ１サーバ６１５と、Ｓ２サーバ６２０と、Ｓ３サーバ６１０と、ＳＭＰＣプロキシサーバ６２５とを含むコンピュータ制御化されたシステム６０５を示している。Ｓ１サーバ６１５およびＳ２サーバ６２０は、２つのコピーに分割され得るデータベースをホストするように設計される。Ｓ１サーバ６１５は、データベースコピーのうち一方のコピーを記憶するように構成されるデータベース６１７を含み、Ｓ２サーバ６２０は、データベースコピーのうちもう一方のコピーを記憶するように構成されるデータベース６２２を含む。データベース６１７および６２２は、暗号化データベースをホストし、かつ、値の暗号化された形であり得るシェアをデータベースに記憶するように構成され得る。
例えば、値ｘがデータベース６１７および６２２に記憶される場合、値ｘは、ランダムな
【数２１】
2019500645.tif 000023
を選択すること、および
【数２２】
2019500645.tif 000024
と設定することにより分散共有されるＸＯＲであり、ここで、
【数２３】
2019500645.tif 000025
はＸＯＲ演算を表し、｜ｘ｜は値ｘの長さを表す。
故に、シェアＸ１はデータベース６１７に記憶されてよく、シェアＸ２はデータベース６２２に記憶されてよい。場合によっては、Ｓ１サーバ６１５とＳ２サーバ６２０との間の加法的シェア、および確率的検索可能暗号化が、Ｓ１サーバ６１５およびＳ２サーバ６２０で使用されてもよく、当該サーバに記憶されてもよい。コンピュータ制御化されたシステム６０５は、コンピュータ制御化されたシステム６０５により行われるセキュアな計算プロトコルを高速化させるように設計される補助サーバとして使用され得るＳ３サーバ６１０も含む。例えば、Ｓ１サーバ６１５およびＳ２サーバ６２０は、ＸＯＲシェアをＳ３サーバ６１０に送信することができる。次いで、Ｓ３サーバ６１０は、完了した暗号化値を再構成すること、および、検索可能暗号化鍵（Ｋ３）を利用して基になるクエリの検索を実行することができる。
【００３７】
図６に示されるＳＭＰＣプロキシサーバ６２５は、ＳＱＬクエリを受信し、かつ、これらをＳ１サーバ６１５、Ｓ２サーバ６２０およびＳ３サーバ６１０へ送信するように構成されてよい。ＳＭＰＣプロキシサーバ６２５は、任意の平文データを明かすことなくＳＱＬクエリを処理すべく、ＳＱＬクエリを受信し、ＳＱＬクエリを暗号化し、かつ、暗号化されたクエリをＳ１サーバ６１５、Ｓ２サーバ６２０およびＳ３サーバ６１０へ送信するように構成されてよい。ＳＭＰＣプロキシ６２５は、ＳＱＬクエリの結果を受信するように構成されてもよい。ＳＱＬクエリの結果は、ＳＭＰＣプロキシサーバ６１０のみが答えを受信できることが可能となるような方法で、ランダムなシェア内に提供されてよい。図６は、データを抽出し、変換し、データベースにロードするように設計されるＥＴＬサーバ６３０が、Ｓ１サーバ６１５およびＳ２サーバ６２０にあることも示している。場合によっては、ＥＴＬサーバが、Ｓ１サーバ６１５およびＳ２サーバ６２０にアイデンティティの証明を求めるように構成されてよい。
【００３８】
図６は、Ｓ１およびＳ２に記憶されるデータベースでクエリを実行するよう依頼し得るクライアントデバイス６３５も示している。クライアントデバイス６３５は、ＳＭＰＣプロキシサーバ６２５を介してＳ１およびＳ２に記憶されるデータベースと接続するように構成されるソフトウェアアプリケーションを動作させてよい。場合によっては、クライアントデバイス６３５がＳＱＬコマンド等のクエリコマンドをＳＭＰＣプロキシサーバ６２５に送信してよい。ＳＭＰＣプロキシサーバ６２５により実行されるクエリプロセスを開始すべく、クライアントデバイス６３５がクエリツリーをＳＭＰＣプロキシサーバに送信し得る場合もある。
【００３９】
図７は、基になるＳＱＬクエリフローにおいて基本的なＳＱＬ演算を処理する、本発明の例示的な実施形態に係る方法を開示している。段階８１０では、ＳＱＬ必須演算に従ってクエリをフィルタリングすることにより、Ｓ１およびＳ２がＳＱＬクエリ処理を開始する。場合によっては、暗号化ミックスプロトコルの完了後にこのプロセスが開始してよい。コンピュータ制御化されたシステムは、クエリツリー構造に従って、段階８１５、８２０、８２５、８３０および８３５で定義されるようにＳＱＬクエリを処理するように構成されてよい。段階８１５は、異なるタイプの値を別個の方法でフィルタリングする段階を開示している。フィルタリングは以下のように行われる。
・第１のタイプは、平文データ属性に関する条件である。このタイプのフィルタリングでは、Ｓ１およびＳ２の各々がデータフィールドをローカルで検索し得る。このフィルタリングが暗号化ミックスプロトコルの後に実施されると、平文データが暗号化ミックスプロトコルでの分散値に置換された。故に、このタイプの条件が暗号化ミックスプロトコルの後に出て来た場合は、Ｓ１およびＳ２がシェアをＳ３に送信し、Ｓ３が値を再構成し、条件を計算し、結果（この結果は、条件を満たす値の行インデックスのみを含む）を送り返す。これと同じ方法が、平文値のみが関与している全てのタイプの演算（例えば、平文値の集計、平文値間の結合等）に使用されるが、これについては以下で繰り返さない。
・第２のタイプは、検索可能暗号化が可能なデータに対するＷＨＥＲＥ  ＥＱＵＡＬＳである。このタイプの検索では、Ｓ１およびＳ２の各々が、検索可能暗号化検索プロセスを用いてローカルでフィルタリングし得る。このフィルタリングが暗号化ミックスプロトコルの後に実施されると、検索可能暗号化値（すなわち暗号文）が暗号化ミックスプロトコルでの分散値に置換された。故に、このタイプの条件が暗号化ミックスプロトコルの後に出て来た場合は、Ｓ１およびＳ２が、検索可能暗号化値のＸＯＲシェアをＳ３に送信する。次いで、Ｓ３が完全な暗号化値を再構成し、次いで、検索可能暗号化鍵（Ｋ３）を利用して基になるクエリの検索を実行する。Ｓ３は、条件を満たす値の行インデックスのみから成る結果をＳ１およびＳ２に返す。
・第３のタイプ：他の値：このタイプは、第１のタイプまたは第２のタイプのうちどちらでもなくてよい他の値を指す。このタイプでは、条件の結果を計算するために、ガーブル化回路（ｇａｒｂｌｅｄ  ｃｉｒｃｕｉｔ）のセキュアな計算または任意の他のＭＰＣがＳ１、Ｓ２と共に使用され得る。
場合によっては、ＭＰＣ計算を高速化させるためにＳ３が使用されてよく、オネストマジョリティが想定されてよい。
【００４０】
段階８２０は、基になるクエリ内のシェアに対してＭＩＮ／ＭＡＸ、ＳＵＭ、ＣＯＵＮＴ、ＳＴＤＥＶおよびＡＶＥＲＡＧＥ集約関数が使用される場合に値を計算する段階を開示している。方法は以下のように定義される。
・ＭＩＮ／ＭＡＸ：これは値のＸＯＲシェアを使用する。サーバは、リスト内の第１の値のシェアを取ることにより状態を初期化する。次いで、Ｓ１およびＳ２は、各段階で次の値のシェアと一緒に現在のＭＩＮ／ＭＡＸのシェアを取り、セキュアな計算により以下の関数を計算する。この計算は、場合によって、ガーブル化回路をＳ１、Ｓ２およびＳ３と共に利用しながら、ＭＰＣプロトコルを介して行われ得る。ａ．最小値については、ＭＰＣプロトコルが２つの値の間でより小さな値のシェアを計算し、一方のシェアをＳ１に送り返し、他方のシェアをＳ２に送り返す。ｂ．最大値については、ＭＰＣプロトコルが２つの値の間でより大きな値のシェアを計算し、一方のシェアをＳ１に送り返し、他方のシェアをＳ２に送り返す。リスト内の全ての値を処理した後、Ｓ１／Ｓ２は、ＭＩＮ／ＭＡＸ値のシェアを保持する。
・ＳＵＭ：この集約関数の場合は、Ｓ１およびＳ２が所与の加法的シェアを使用し、各サーバＳ１およびＳ２が、単にローカルでモジュロ２１２８でその分散値を合計する。
・ＣＯＵＮＴ：この集約関数の場合は、集約関数が平文で計算され得る。なぜなら、各サーバが表内に残っているトランザクションの数を数え得るからである。
・ＣＯＵＮＴ−ＤＩＳＴＩＮＣＴ：この場合の演算では、クエリが図３で開示されるセキュアなマッチングプロトコルを利用してよい。
・ＡＶＥＲＡＧＥ：この集約関数の場合は、Ｓ１およびＳ２がＳＵＭの加法的シェアを計算し、これらのシェアを平均の値のＣＯＵＮＴと共に記憶する。
・ＳＴＤＥＶ：この集約関数の場合は、Ｓ１およびＳ２が値の加法的シェアと値の二乗の加法的シェアとを使用する。この場合は、以下の式が利用され得る。
【数２４】
2019500645.tif 000026
ここで、ｎはカウント数を表す。この場合のＳＴＤＥＶでは、Ｓ１およびＳ２が値ＳＵＭおよび値ＳＵＭＳＱＵＡＲＥＳのシェアをローカルで計算し、ここで、ＳＵＭＳＱＵＡＲＥＳは、値の二乗の加法的シェアの加法的シェアをローカルで合計することにより計算され、モジュロ２１２８で平方の加法的シェアをローカルで合計することにより計算される。次いでＣＯＵＮＴ・ＳＵＭ−ＳＵＭＳＱＵＡＲＥＳのシェアをローカルで計算する。最後に、Ｓ１およびＳ２は、これらのシェアをＣＯＵＮＴと共に記憶する。
【００４１】
段階８２５は、基になるクエリでこの更なる処理が必要とされ得る場合に集約関数の条件付けを計算する段階を開示している。この段階は、場合によって、段階８２０の完了後に行われ得る。例えば、ＨＡＶＩＮＧクエリの場合は、条件文を算出するための更なる処理が必要とされる。この算出は、先ほど計算された集計の何れに関する条件であってもよい。このような場合は、Ｓ１およびＳ２が結果のＸＯＲシェアまたは加法的シェアを保持しており、比較（等値、小なり等）を実行して答えを受信するために、ガーブル化回路、または知られている任意の他のＭＰＣプロトコルを使用し得る。
【００４２】
段階８３０は、基になるクエリの一部として階数関数を計算する段階を開示している。階数関数は、以下の関数、すなわちＮＴＩＬＥ、ＰＥＲＣＥＮＴＩＬＥ、ＲＡＮＫ、ＰＥＲＣＥＮＴ＿ＲＡＮＫおよびＤＥＮＳＥ＿ＲＡＮＫと定義されてよい。階数関数の場合は、比較に基づく任意のソートアルゴリズムを用いることにより、Ｓ１およびＳ２がセキュアなソートを計算してよい。ここで、ＬＥＳＳ−ＴＨＡＮ演算は、ガーブル化回路、または、結果をＳ１およびＳ２に返す、知られている任意の他のセキュアなＭＰＣプロトコルを用いて、セキュアな計算に置換されてよい。最後に、ひとたびソートされた値が与えられると、Ｓ１およびＳ２の各々が階数関数をローカルで計算する。
【００４３】
段階８３５は、ＭＡＴＣＨ演算、ＳＯＲＴ関数およびＷＩＮＤＯＷ関数をＳＱＬクエリの一部として計算する方法を開示している。ＭＡＴＣＨ演算、演算ＧＲＯＵＰ  ＢＹ、ＪＯＩＮおよびＳＥＴについては、図３で開示されるようにＳＱＬ  ＭＡＴＣＨ演算をセキュアなやり方で実行するためのセキュアなプロトコルをＳ１およびＳ２が利用してよい。基になるクエリがＳＯＲＴを含む場合は、サーバがセキュアなソートを実行する。ここで、ＬＥＳＳ−ＴＨＡＮ演算子は、ガーブル化回路、または同業者に知られている任意の他の方法を用いて、セキュアな計算に置換される。ＷＩＮＤＯＷ関数が、基になるクエリおよび行の組で動作して、基になるクエリから行ごとに単一の値を返してよい場合には、当該関数がＳＯＲＴ演算に置換されてよい。
【００４４】
段階８４０は、ひとたびクエリプロセスが完了すると、基になるＳＱＬクエリの結果をＳ１およびＳ２によりＳＭＰＣプロキシサーバへ返す段階を開示している。場合によっては、Ｓ１およびＳ２が結果のＸＯＲシェアまたは加法的シェアを有してよく、次いで、これらのシェアが、実際の値を計算し得るＳＭＰＣプロキシサーバに送信され得る。ＡＶＥＲＡＧＥ関数の場合は、Ｓ１およびＳ２がＳＵＭのシェアを保持しており、場合によっては、ＣＯＵＮＴ値、Ｓ１およびＳ２がＳＭＰＣプロキシサーバに値を送信してよい。当該ＳＭＰＣプロキシサーバは、モジュロ２１２８でシェアを加算して実際の合計を取得することができ、平均を取得すべく当該合計をカウント数で除算する。Ｓ１およびＳ２がＳＵＭ演算子のシェアおよびＣＯＵＮＴ演算子のシェアを保持しており、Ｓ１およびＳ２がＳＭＰＣプロキシサーバにシェアを送信し得るといったような、ＳＴＤＥＶ関数等の場合もある。次いで、ＳＭＰＣプロキシサーバは、モジュロ２１２８で分子のシェアを加算し、結果を整数にわたってＣＯＵＮＴ・（ＣＯＵＮＴ−１）で除算し、次いでその平方根を結果と見なしてよい。
【００４５】
図８は、Ｓ１およびＳ２にあるＳＱＬデータベースにデータをロードし、次いでＳＱＬデータベースに対するＳＱＬクエリプロセスを行う、本発明の例示的な実施形態に係るプロセスを開示している。段階９０５では、Ｓ１およびＳ２が空のデータベースのローカルコピーを２つ生成する。段階９１０では、データベース秘密フィールドが、サーバＳ１とサーバＳ２との間で分散共有されるＸＯＲであるように構成されてよく、データベースの秘密数値フィールドが、加法的な秘密分散共有によって暗号化されるように構成されてもよい。場合によっては、ＳＱＬが当該値に対して使用される可能性に従って、複数の加法的な分散共有方法が、非表示の数値フィールドを暗号化するために利用されてよい。段階９１５は、基になるＳＱＬクエリのためのクエリツリーを作成するＳＭＰＣプロキシサーバを開示している。クエリツリーは、ＳＱＬクエリ演算およびそれに関連する表を含んでよく、これらの関係はクエリで使用される。段階９２０は、トークン化クエリツリーを作成してＳ３に送信し、次いでＳ１およびＳ２へのトークン化クエリツリーを作成する、ＳＭＰＣプロキシサーバを示している。場合によっては、Ｓ３に送信されるトークン化クエリツリーの検索条件部分にある値が取り除かれてよい。
【００４６】
段階９３０は、トークン化クエリツリーを利用して、段階９２０で生成されるデータベースコピーに対するＳＱＬクエリ演算を処理するＳ１およびＳ２を開示している。基になるＳＱＬクエリのＳＱＬ演算は、Ｓ１およびＳ２にある暗号化データベースに対して実行されてよい。故に、ＳＱＬ演算は、図８で定義されるように暗号化プロセスの仕様に従って行われてよい。段階９３５は、基になるＳＱＬクエリを満たした値をＳ１およびＳ２が返す部分を示している。係る値は、ＳＱＬの元のクエリに応じて、表、配列、データおよび列等であり得る。場合によっては、Ｓ１およびＳ２が結果のＸＯＲシェアまたは加法的シェアをＳＭＰＣプロキシサーバに返してよく、ＳＭＰＣプロキシサーバが最終結果を算出してよい。
【００４７】
例示的な実施形態を参照しながら本開示について説明してきたが、当業者であれば、本発明の範囲から逸脱することなく様々な変更が行われてよいこと、および、均等物が当該実施形態の要素に置き換えられ得ることを理解するであろう。加えて、本発明の本質的な範囲から逸脱することなく特定の状況または材料を教示に適応させるために多くの修正が行われてよい。従って、開示される主題が、想定される最良の形態として開示される、本発明を実施するための特定の実施形態に限定されることはなく、以下の特許請求の範囲によってのみ限定されるように意図されている。
【図１】
2019500645.tif 000027
【図２】
2019500645.tif 000028
【図３】
2019500645.tif 000029
【図４】
2019500645.tif 000030
【図５】
2019500645.tif 000031
【図６】
2019500645.tif 000032
【図７】
2019500645.tif 000033
【図８】
2019500645.tif 000034
【国際調査報告】
2019500645.tif 000035
2019500645.tif 000036