(57)【要約】      （修正有）【課題】非トラステッド・コンピュータにおいて擬装計算単位の実行、および他の計算単位の実行を開始して、非トラステッド・パーティによる計算の再構成を阻止する装置、プログラム、および方法を提供すること。【解決手段】特定の計算が複数の計算単位に区切られ１０２、本来の計算とは直接関係のない１つまたは複数の擬装計算単位が生成され１０４、１つまたは複数のリソース・プロバイダに提供されて１０６、区切られた計算の計算単位とともに実行される。【選択図】図４
2005209202.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの非トラステッド・コンピュータにおいて計算の実行を開始する方法であって、
前記計算を、前記計算の結果を生成するために結合可能な複数の計算単位に区分するステップと、
少なくとも１つの擬装計算単位を生成するステップと、
非トラステッド・パーティによる前記計算の再構成を阻止するために前記非トラステッド・コンピュータにおいて前記少なくとも１つの擬装計算単位と、前記複数の計算単位のうちの少なくとも１つとの実行を開始するステップと
を含む方法。
【請求項２】
前記擬装計算単位が第２の計算を区分するステップから生成された計算単位を含む請求項１に記載の方法。
【請求項３】
前記実行を開始するステップが前記複数の計算単位からの計算単位の間に前記少なくとも１つの擬装計算単位をインターリーブするステップを含む請求項２に記載の方法。
【請求項４】
前記区分するステップが前記第２の計算を区分するのに使用されるものとは異なるアルゴリズムを使用する請求項２に記載の方法。
【請求項５】
前記擬装計算単位がダミーの計算単位を含む請求項１に記載の方法。
【請求項６】
前記擬装計算単位が前記計算の第２の区分から生成された計算単位を含む請求項１に記載の方法。
【請求項７】
第２のコンピュータにおいて前記複数の計算単位のうちの少なくとも１つの実行を開始するステップをさらに含む請求項１に記載の方法。
【請求項８】
前記非トラステッド・コンピュータにおいて前記複数の計算単位のすべての実行を開始するステップをさらに含む請求項１に記載の方法。
【請求項９】
前記区分するステップが中国剰余定理（ＣＲＴ）を使用して区分するステップを含む請求項１に記載の方法。
【請求項１０】
前記計算が複数の引数を含み、前記区分するステップが
互いに素の複数のモジュロを選択するステップと、
前記互いに素の複数のモジュロのうちの１つを使用して前記複数の引数のそれぞれに対してモジュロ演算を行うことによって各計算単位を生成するステップと
を含む請求項９に記載の方法。
【請求項１１】
前記互いに素の複数のモジュロを選択するステップが互いに素のモジュロのスーパーセットから各モジュロを選択するステップを含み、
前記方法がさらに
前記互いに素のモジュロのスーパーセットから選択された異なる組のモジュロを使用して複数の計算を複数の計算単位に区分するステップと、
前記非トラステッド・コンピュータにおいて複数の計算からの計算単位の実行を開始するステップと
を含む請求項１０に記載の方法。
【請求項１２】
前記複数の計算単位のそれぞれの実行中に生成された結果データを受信するステップと、
前記結果データから前記計算の結果を生成するステップと
をさらに含む請求項１に記載の方法。
【請求項１３】
前記非トラステッド・コンピュータがグリッド・コンピューティング・ネットワークに結合される請求項１に記載の方法。
【請求項１４】
前記区分するステップが前記グリッド・コンピューティング・ネットワークに結合されているクライアント・コンピュータによって実行される請求項１３に記載の方法。
【請求項１５】
前記区分するステップが前記グリッド・コンピューティング・ネットワークに結合されているブローカ・コンピュータによって実行され、前記方法がクライアント・コンピュータから前記計算を受信するステップをさらに含む請求項１３に記載の方法。
【請求項１６】
前記区分するステップ、前記生成するステップ、および前記開始するステップが前記非トラステッド・コンピュータに結合されている少なくとも１つのコンピュータによって実行され、前記方法が前記擬装計算単位、および前記複数の計算単位のうちの前記少なくとも１つを前記非トラステッド・コンピュータに伝えるステップをさらに含む請求項１に記載の方法。
【請求項１７】
少なくとも１つのプロセッサと、
請求項１〜１６のいずれかに記載の方法を前記プロセッサに実行させるためのプログラムを記憶した記憶装置と
を含む装置。
【請求項１８】
請求項１〜１６のいずれかに記載の方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータおよびコンピュータ・ソフトウェアに関し、より詳細には、非トラステッド分散コンピューティング環境で実行される計算の保護に関する。
【背景技術】
【０００２】
コンピュータ産業は、次第に計算のユーティリティ・モデルに依存し始めている。組織が一般に個々のコンピューティング・ニーズを満たすのに必要な必須のすべてのハードウェアおよびソフトウェアのコンピュータ・リソースを購入し維持する従来のコンピューティング・パラダイムとは異なり、計算のユーティリティ・モデルは、どちらかというと複数のすべての組織の集合的なコンピューティング・ニーズを満たすために、複数の組織によって有効に共有することができるユーティリティまたはサービスの観点からコンピュータ・リソースを捉える。
【０００３】
こうした計算ユーティリティ環境の１つは、グリッド・コンピューティングと呼ばれている。そこでは場合によると異機種で地理的に離れたコンピュータ・システムの集まりがともに分散方式で接続されており、それぞれのリソースを共有し、単一の大きく強力な仮想コンピュータ・システムの外観を呈している。グリッド・コンピューティング環境を使用すると、プロセッサ、アプリケーション、ストレージ、メモリ、プリンタ、ネットワーク接続、他の周辺装置など、様々なハードウェアおよびソフトウェアのリソースを共有することができる。計算グリッドでは、基礎となるリソースの利用を最大化するような方法で様々なリソースに作業を渡すために特殊ソフトウェアが使用されている状態で、複数のコンピュータのハードウェアまたはソフトウェアあるいはその両方のリソースが抽出される。
【０００４】
多くのコンピュータは、多くの場合、あまり十分に活用されていないことがほとんどであることを考えれば、グリッド・コンピューティングは、多くの場合、システムの使用効率の点では、従来のコンピューティング環境より有効である。従来のコンピューティング環境を使用する組織は一般に、最高の需要がどのぐらい頻繁に生じるかに関わらず、各コンピューティング・システムに対するこうした組織の最大または最高の需要を満たすのに十分な計算能力を維持することが求められる。一方、グリッド・コンピューティングを使用すると、複数の組織の計算能力（さらには同じ組織によって所有される複数のサイトまたはシステムの計算能力）を有効に共有することができ、したがって作業をグリッド内の異なるリソースに分散することができ、全体的なシステム稼働率の最大化につながる。多くの場合、グリッドで維持される集合的な計算能力は、そうでなければグリッドの各消費者の個々の計算需要を満たすために必要となる計算能力より小さくなり得る。
【０００５】
多くの場合、グリッド・コンピューティングは、多くの複雑なコンピューティング・アプリケーションには望ましい高並列処理の可能性も提供する。さらにグリッド・コンピューティングは、多くの場合、フェイルオーバー、ロード・バランシング、グリッドの信頼性および可用性を向上させる他の高可用性機能、およびセキュリティ、管理などの他の高レベルの機能を提供する。
【０００６】
一部の計算ユーティリティ環境は、単一の組織内で維持することはできるが、多くの場合、計算ユーティリティ環境は、複数の組織で使用されており、または公に維持され、またはサポートされ、あるいはその両方が行われることさえある。例えば、グリッド・サービスおよびＷｅｂサービスは、複数の組織から計算リソースを抽出し、グリッドのクライアントまたは消費者（さらにはグリッド内のどのコンピューティング・リソースもホストしていないものさえも）が、代わりに１つまたは複数のリソース・プロバイダに計算または他のタスクを行わせることができるようにするために使用することができる。さらに、グリッドのクライアントがトランザクション・ベースまたはサブスクリプション・ベースでリソースの使用代金を支払えるようにするために費用構造を開発することもできる。
【０００７】
一例として、グリッド・コンピューティングを使用して、従来数百万ドルのスーパーコンピュータで実行されている多くのタイプの計算を実行することができる。かなり安く、パフォーマンスのより低い何百または何千ものコンピュータをグリッドにおいて相互接続し、次いで複雑な計算を、複数のコンピュータによって並列処理される計算単位に区分することによって、グリッドは、多くのスーパーコンピュータと同じパフォーマンスを、しかしかなり低コストで提供することができる。多くの組織は、複雑な計算を扱うのに十分な社内の計算能力を購入し、維持する必要性を避けるために、トランザクション・ベースまたはサブスクリプション・ベースでグリッドの使用代金を大いに喜んで支払う。
【０００８】
しかし、グリッド・コンピューティングおよび他の形式の分散型の計算ユーティリティ環境の１つの欠点は、グリッドの多組織構造によって起こるセキュリティ問題である。
【０００９】
多くの分散型の計算ユーティリティ環境では、例えば、多数の組織がコンピューティング・リソースをその環境のインフラストラクチャに提供することが予想される。場合によっては、これらの組織は、互いに競争相手である場合さえある。したがってこうした環境で作業を実行させたいクライアントは、そのデータの機密性を完全には制御できない可能性がある。
【００１０】
データの基礎となる処理が計算ユーティリティ環境の特定のコンピュータ上で実行されるとき、暗号化通信を使用してコンピュータ間の通信を保護することはできるが、そのコンピュータは一般に、計算を実行する前にデータを解読することができなければならない。言い換えると、暗号化は通常、クライアントとリソースとの間の送信中はデータを保護するが、データがそのリソースによっていったん受信され、処理されると保護されない。
【００１１】
その結果、計算ユーティリティ環境においてクライアントの代わりに行われる計算は、少なくとも一部、競争相手または他の非トラステッド・パーティによってホストされるリソースを計算することによって行われる可能性がある。したがって詮索好きな、または悪意のある非トラステッド・パーティがコンピューティング・リソースをホストしながら、計算または計算に関連付けられた通信あるいはその両方を傍受し、それによってクライアントの機密データが損なわれ得るというリスクが作られるというかなりのリスクが存在する。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、当分野では、計算ユーティリティまたは他の非トラステッド分散コンピューティング環境において実行される計算を保護する必要がある。
【課題を解決するための手段】
【００１３】
本発明は、非トラステッド・コンピュータにおいて他の計算単位の実行とともに擬装計算単位の実行を開始して非トラステッド・パーティによる計算の再構成を阻止する装置、プログラム、および方法を提供することによって従来技術に関連付けられているこれらおよび他の問題に取り組む。具体的には、特定の計算が複数の計算単位に区分され、この計算とは直接関係のない１つまたは複数の擬装計算単位が生成され、１つまたは複数のリソース・プロバイダに提供されて、区分された計算の計算単位とともに実行される。対象の計算を区分する結果として生成される１つまたは複数の計算単位とともに擬装計算単位が存在していると、非トラステッド・コンピュータに提供される計算単位から、計算またはその全体的な結果を検出して再構成することがかなり複雑になると考えられる。
【００１４】
本発明による様々な実施形態は、異なるいくつかのやり方で擬装計算単位を実装することができる。例えば、擬装計算単位は、結果データの生成には使用されないダミーの計算単位として実装することができる。別の例として、擬装計算単位は、別の区分された計算からの計算単位として実装することができる。複数の別個のコンピュータにおける所与の区分からの他の計算単位の任意選択の実行とさらに組み合わせると、非トラステッド・パーティの計算を再構成する能力は大幅に低減する。しかし、上述した具体例は、本質的には単に例にすぎず、本発明は、こうした特定の例に限定されないことを理解されたい。
【００１５】
本発明を特徴付けるこれらおよび他の利点および特徴は、本明細書に添付し、さらにその一部を形成している特許請求の範囲に記載されている。しかし、本発明、およびその使用によって得られる利点および目的をよりよく理解するために、本発明の実施形態の例を記述している図面および添付の記述を参照されたい。
【発明を実施するための最良の形態】
【００１６】
以下に記載する実施形態は、擬装計算単位を使用して、少なくとも一部が非トラステッド・コンピュータによって実行される区分された計算の再構成を阻止する。非トラステッド・コンピュータは、例えば、計算グリッドなどの計算ユーティリティ環境に結合することができ、それによって、クライアントの代わりに計算を行うために計算リソースを使用できるようにするためにグリッド・サービス、Ｗｅｂサービス、および他の分散コンピューティング機能が使用される。この点について、コンピュータとの通信にアクセスできるパーティが機密の計算やデータ・トラフィックを「傍受」、その他監視できないことが計算のクライアントまたは所有者に保証されない限り、そのようなコンピュータは非トラステッドである。
【００１７】
本発明によれば、計算が複数の計算単位に区分または分割され、次いで複数の計算単位は、任意の非トラステッド計算プロバイダが計算単位を有効に再結合して元の計算を再構成することができないように、１つまたは複数の計算プロバイダに分配される。次いで結果が再結合されて、一般に許可されていないパーティによる傍受のおそれのない環境で最終結果が生成される。
【００１８】
計算の再構成または再結合を阻止するために、擬装計算単位が、区分された計算からの計算単位とともに、非トラステッド・コンピュータに分配される。ここで、擬装計算単位は、非トラステッド・コンピュータに渡された複数の計算単位のうち、どの計算単位が同じ区分された計算に属するかを非トラステッド・コンピュータが決定できないようにする、あるいはそのような決定を困難にする計算単位である。例えば、擬装計算単位は、結果データの生成には使用されないが、非トラステッド・コンピュータにとっては計算の要素に見えるダミーの計算単位として実装することができる。別の例として、擬装計算単位は、同じ計算の複製でもよい別の区分された計算からの計算単位として実装することができ、したがって計算単位の帰属関係の確認が困難または不可能になるように、複数の計算からの単位が非トラステッド・コンピュータに渡される。計算単位の一部を、特定の非トラステッド・パーティとは関係がなく、それとは通信しない他のパーティの制御下にある他のコンピュータに分配することによって追加の保護を提供することができることも理解されたい。擬装計算単位の他の実装は、本開示の利益を得る当業者には明らかである。
【００１９】
次に図面を参照すると、図１は、本発明による計算ユーティリティ環境１０の例を示している。環境１０は、例えば、複数のクライアント１４を複数のコンピューティング・リソース１６に結合するために使用される計算グリッド１２を使用して実装される。
【００２０】
計算グリッド１２は、当業者にはよく知られているように、リソース１６への共用アクセスを提供するのに適した任意の数のコンピュータ、周辺装置、記憶装置、ネットワーク接続、その他の構成要素を使用して実装することができる。グリッド１２、クライアント１４、およびリソース１６の構成要素は、任意の数のサイトに配置することができ、また任意の数の組織または個人の制御下またはドメイン下に置くことができることを理解されたい。さらに、こうした構成要素は、本質的に同種であっても異種であってもよい。
【００２１】
次に図２は、計算ユーティリティ環境１０のための高度に抽象化されたアーキテクチャ２０の例を示している。例えばアーキテクチャ２０は、グリッド・プロトコルによって共用アクセスが行われるリソースの論理表現を提供するファブリック層２２を含む。例示の実施形態では、ファブリック構成要素は、主にリソース固有のローカル・オペレーションを実行する。また、アーキテクチャ２０は、グリッド・トランザクション用、および特にファブリック層構成要素間の通信および認証プロトコルを定義する接続層２４も含む。通信プロトコルは、トランスポート、ルーティング、ネーミングなど、様々な通信関連のサービスを含み得る。認証プロトコルは、例えばユーザおよびリソースの識別を確認するためのセキュリティ機構を提供するために使用することができる。
【００２２】
また、アーキテクチャ２０は、例えば個々のリソースに対する共用操作の安全な交渉、開始、監視、制御、会計、支払いのサポートを介した、リソースへの共用アクセスのためのプロトコルを提供するリソース層２６も含む。さらに、共同層２８を使用して、数ある中でも例えばディレクトリ・サービス、共同割り振り／スケジューリング／ブローカリング・サービス、監視／診断サービス、データ複製サービス、プログラミング・システム／仕事量管理システム／共同作業フレームワークのソフトウェア発見サービス、コミュニティ認証サービス、コミュニティ会計／支払いサービス、および共同作業サービスなど、リソースの集まりへのアクセスを調整する。層２４、２６、２８は、一般にグリッド対応アプリケーション３０によってアクセス可能である。
【００２３】
アーキテクチャ２０の各層で異なるサービスを実施できることを理解されたい。さらに、アーキテクチャ２０は、本質的に例にすぎず、他のグリッドまたは計算ユーティリティ・アーキテクチャを代替で使用してもよい。したがって本発明は、本明細書に示した特定の計算ユーティリティ環境に限定されるものではない。
【００２４】
次に図３は、本発明による擬装分散計算を実行するのに適した装置４０のハードウェアおよびソフトウェアの環境例を示している。特に、装置４０は、図１の計算ユーティリティ環境に存在するブローカ・コンピュータとして実装される。しかし本発明の目的上、装置４０は、実際には、クライアント・コンピュータ、サーバ・コンピュータ、ポータブル・コンピュータ、ハンドヘルド・コンピュータ、内蔵コントローラなど、任意のタイプのコンピュータ、コンピュータ・システム、または他のプログラム可能電子装置を表し得る。さらに装置４０は、例えばクラスタ、計算グリッド、または他の分散コンピューティング・システムなどにおいて複数のネットワーク式コンピュータを使用して実装することができる。装置４０は、以下「コンピュータ」と呼ぶが、「装置」という用語は本発明による他の適したプログラム可能電子装置も含み得ることを理解されたい。
【００２５】
コンピュータ４０は一般に、コンピュータ４０の主記憶を構成するランダム・アクセス・メモリ（ＲＡＭ）装置、および例えばキャッシュ・メモリ、不揮発性メモリまたはバックアップ・メモリ（プログラム可能メモリまたはフラッシュ・メモリ）、読み取り専用メモリなど、任意の補足レベルのメモリを表すメモリ４４に結合されている１つまたは複数のプロセッサを含む中央処理装置（ＣＰＵ）４２を含む。さらにメモリ４４は、物理的にコンピュータ４０内のどこかに配置されているメモリ、例えばＣＰＵ４２のプロセッサ内の任意のキャッシュ・メモリ、および仮想メモリとして使用される任意の記憶域、例えば大容量記憶装置またはコンピュータ４０に結合されている他のコンピュータ上に格納されるようなものを含むと考えることができる。
【００２６】
不揮発性ストレージでは、コンピュータ４０は一般に、数ある中でもフレキシブル・ディスク・ドライブその他の取り外し可能ディスク・ドライブ、ハード・ディスク・ドライブ、直接アクセス記憶装置（ＤＡＳＤ）、光ディスク・ドライブ（ＣＤドライブ、ＤＶＤドライブなど）またはテープ・ドライブあるいはそのすべてなど、１つまたは複数の大容量記憶装置４６を含む。さらに、コンピュータ４０は、例えば１つまたは複数のクライアントまたは管理コンピュータ５２、１つまたは複数の計算所有者５４、および１つまたは複数の計算プロバイダ５６など、他のコンピュータおよび電子装置との情報の通信を可能にするために、１つまたは複数のネットワーク５０（例えばＬＡＮ、ＷＡＮ、無線ネットワーク、インターネットなど）とのインターフェース４８を含むこともできる。他の実装では、計算グリッドは、コンピュータ４０内に単独で存在していてもよく、その場合、計算所有者および計算プロバイダはユーザ・インターフェース５８を介してグリッドと通信することができる。
【００２７】
コンピュータ４０は一般に、外部との情報通信のための１つまたは複数の入出力インターフェースを有する。ユーザまたはオペレータとのインターフェースとして、コンピュータ４０は一般に、１つまたは複数のユーザ入力装置（例えばキーボード、マウス、トラックボール、ジョイスティック、タッチバッド、マイクロフォンなど）、およびディスプレイ（例えばＣＲＴモニタ、ＬＣＤディスプレイ・パネル、スピーカなど）を組み込むユーザ・インターフェース５８を含む。ユーザ・インターフェース５８以外からのユーザ入力は、例えばネットワーク５０およびネットワーク・インターフェース４８を介してコンピュータ４０に結合されているクライアント・コンピュータ５２などの別のコンピュータまたは端末を介して受信することができる。コンピュータ４０は一般に、当業者にはよく知られているように、ＣＰＵ４２と構成要素４４、４６、４８、５８のそれぞれとの間にアナログまたはデジタルの適当なインターフェース（図示せず）を含んでいる。
【００２８】
コンピュータ４０は、オペレーティング・システム６０の制御下で動作し、コンピュータ・ソフトウェアの様々なアプリケーション、コンポーネント、プログラム、オブジェクト、モジュールなどを実行する。例えば、グリッド・ミドルウェア・コンポーネント６２は、計算グリッド１２の一部を実装するために常駐させてもよく、コンピュータ４０に存在する１つまたは複数のグリッド対応アプリケーション６４からアクセス可能である。さらに、追加のアプリケーション、コンポーネント、プログラム、オブジェクト、モジュールなども、例えば分散またはクライアント−サーバ・コンピューティング環境においてネットワークを介してコンピュータ４０に結合されている別のコンピュータの１つまたは複数のプロセッサ上で実行することができ、それによってコンピュータ・プログラムの機能を遂行するのに必要な処理を、ネットワークを介して複数のコンピュータに割り振ることができる。
【００２９】
一般に、本発明を実施するために実行されるルーチンは、オペレーティング・システムの一部として実装されていようと、特定のアプリケーション、コンポーネント、プログラム、オブジェクト、モジュール、または一連の命令、あるいはそのサブセットとして実装されていようと、本明細書では「コンピュータ・プログラム・コード」または単に「プログラム・コード」と呼ぶ。プログラム・コードは一般に、様々なときにコンピュータ内の様々なメモリに存在しており、コンピュータ内の１つまたは複数のプロセッサによって読み取られ、実行されると、そのコンピュータに、本発明の様々な態様を具現化するステップまたは要素の実行に必要なステップを実行させる１つまたは複数の命令を含む。さらに、本明細書では十分に機能するコンピュータおよびコンピュータ・システムを例にとって本発明を説明しているが、本発明の様々な実施形態は、様々な形のプログラムとして分配することができ、本発明は、実際に分配を行うために使用されるコンピュータ可読信号担持媒体の特定のタイプに関わらず、等しく適用されることを当業者であれば理解されよう。コンピュータ可読信号担持媒体の例には、それだけには限定されないが、揮発性および不揮発性のメモリ装置、フレキシブル・ディスクその他の取り外し可能ディスク、ハード・ディスク・ドライブ、磁気テープ、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）などの書き込み可能タイプの媒体、デジタルおよびアナログの通信リンクなどの伝送タイプの媒体などがある。
【００３０】
本発明の様々な実施形態は、１つまたは複数のコンピュータに実装されるサービスとして実施することができ、当該サービスにアクセスできるクライアントに使用可能にされることも理解されたい。こうしたサービスは、例えば、計算ユーティリティ、グリッド・サービス、Ｗｅｂサービスなどを介して提供することができる。
【００３１】
さらに、以下に記載する様々なプログラム・コードは、本発明の特定の実施形態でその中に実装されるアプリケーションに基づいて識別することができる。しかし、以下のどんな特定のプログラムの名称も単に便宜上使用されているだけであり、したがって本発明は、こうした名称によって識別される、またはこうした名称に含意される任意の特定のアプリケーションにおいてのみ使用されるものと限定されるべきではないことを理解されたい。さらに、コンピュータ・プログラムをルーチン、プロシージャ、メソッド、モジュール、オブジェクトなどに構成する様々な手法、および（オペレーティング・システム、ライブラリ、ＡＰＩ、アプリケーション、アプレットなど）一般のコンピュータ内に存在する様々なソフトウェア層の間にプログラム機能を割り振る様々な手法を考慮すれば、本発明は、本明細書に記載したプログラム機能の特定の構成および割り振りに限定されるものではないことも明かである。
【００３２】
図１、図２、図３に示した実施形態の例は、本発明を限定するためのものではないことを当業者であれば理解されよう。実際に、他の代替のハードウェアまたはソフトウェアの環境を、本発明の範囲から逸脱することなく使用できることを当業者であれば理解されよう。さらに、本発明は、計算ユーティリティ環境、グリッド環境、分散コンピューティング環境、クライアント−サーバ環境、ピア・ツー・ピア環境、または当分野で知られている他のマルチコンピュータ環境のいずれで実施されていようと、計算が１つまたは複数の非トラステッド・コンピュータ上で実行される他の環境で使用できることを当業者であれば理解されよう。
【００３３】
次に図４を参照すると、クライアントまたは所有者の要求に応答して計算グリッド１２内の例えば１つまたは複数のブローカ・コンピュータによって実行される計算処理ルーチン１００の例をより詳しく示している。一般に、クライアントまたは所有者の要求が特定の計算を指定し、ルーチン１００は、計算を複数の計算単位に区分するブロック１０２から処理を開始する。
【００３４】
他の実施形態では、計算を区分する他のやり方を使用することはできるが、ブロック１０２で使用することができる１つの区分方法では、計算の引数に中国剰余定理（ＣＲＴ）を使用する。ＣＲＴにおいて、計算の引数として、最大数Ｍ未満の２つの整数ＪおよびＫを使用すると、次のようにモジュロｍ１、ｍ２、およびｍ３（この場合ｍ１、ｍ２、およびｍ３は、２つずつが互いに素であり、ｍ１＊ｍ２＊ｍ３＝Ｍである）を選択することができる。
ｊ１＝Ｊ（ｍｏｄ  ｍ１）      ｋ１＝Ｋ（ｍｏｄ  ｍ１）
ｊ２＝Ｊ（ｍｏｄ  ｍ２）      ｋ２＝Ｋ（ｍｏｄ  ｍ２）
ｊ３＝Ｊ（ｍｏｄ  ｍ３）      ｋ３＝Ｋ（ｍｏｄ  ｍ３）
ＣＲＴでは、次のようになる。
ｊ１＋ｋ１＝Ｊ＋Ｋ（ｍｏｄ  ｍ１）ｊ１＊ｋ１＝Ｊ＊Ｋ（ｍｏｄ  ｍ１）
ｊ２＋ｋ２＝Ｊ＋Ｋ（ｍｏｄ  ｍ２）ｊ２＊ｋ２＝Ｊ＊Ｋ（ｍｏｄ  ｍ２）
ｊ３＋ｋ３＝Ｊ＋Ｋ（ｍｏｄ  ｍ３）ｊ３＊ｋ３＝Ｊ＊Ｋ（ｍｏｄ  ｍ３）
減算および除算も同じように実行することができる。さらに、ｊ１、ｊ２、およびｊ３を再結合してＪを、またｋ１、ｋ２、およびｋ３を再結合してＫを得ることができる。
【００３５】
したがって、計算において任意の整数の最大数より大きい値Ｍが与えられている場合、ｍ１、ｍ２、およびｍ３を選択し、計算の引数に対してモジュロ演算を行うことによって整数を含む計算を複数の計算単位に分割して、それぞれ異なるｍｉを使用する３つの個別の計算単位を生成することができる。
【００３６】
例示の実施形態では、ｍｉ（ｍ１、ｍ２、ｍ３）の大きさは一般に、概ねＭの立方根でなければならない。計算は、概ねＭのＮ乗根である（および互いに素である）ｍｉを選択することによってＮ個の計算単位に分割することができることも理解されたい。さらに、実施形態によっては、ｍｉごとに素数のみを選択することが望ましい場合がある。
【００３７】
したがって、ブロック１０２で計算が区分されると、制御はブロック１０４に渡されて、少なくとも１つの擬装計算単位が生成され、次いで制御はブロック１０６に渡されて、（擬装計算単位を含む）計算単位が１つまたは複数の計算プロバイダに転送されて、計算プロバイダのコンピューティング・リソースにおいてこうした計算単位の実行が有効に開始される。次いでブロック１０８では、計算プロバイダによって生成された計算結果を集め、ブロック１１０では、ＣＲＴを使用して結果を再結合して全体的な結果を生成する。次いでブロック１１２では、計算結果がクライアントに戻され、ルーチン１００が完了する。
【００３８】
他の実施形態では、図４に概説した様々なステップを異なるエンティティで実行することができる。例えば、実施形態によっては、トラステッド・ブローカ・コンピュータまたは計算グリッド内の他のエンティティが計算単位を計算プロバイダに渡し、計算プロバイダから結果を受け取るためだけに使用されるようにして、クライアントまたは所有者が、計算単位への計算の区分、および結果の再結合の一方または両方を行うようにしてもよい。さらに別の実施形態では、クライアントまたは所有者が、図４に概説したすべてのステップを行うようにしてもよい。他の代替は、本開示の利益を得る当業者には明らかである。
【００３９】
計算を計算単位に区分し、擬装計算単位を生成して、非トラステッド・パーティによる計算の再構成を阻止する様々な実施形態を思い描くことができる。例えば、上述したように、擬装計算単位は、他の任意の計算単位の外観を有し、しかしその結果はいったん戻されると決して使用されないダミーの計算単位として実装することができる。こうしたダミーの計算単位は、無作為に生成するか、または他のプログラマティックな方法で生成することができる。計算ごとにコストがかかる実施形態では、ダミーの計算単位の使用は、計算所有者のコストを増大させるかもしれないが、こうした単位の存在は、悪意のあるパーティが考える必要がある可能な再構成数を大幅に増加させ得る。
【００４０】
別の例として、例えば、計算を区分し、結果を結合するパーティのみに知られている一意の無相関のＩＤを各計算単位に与えることによって、個々の計算単位における計算単位と完全な計算との間の特定の関連付けを示す識別子なしに、大量（Ｆ個）の完全な計算のための計算単位を概ね同時に実行依頼することができる。さらに、計算単位の順序が特定の計算との関連付けを示さないように、各非トラステッド・コンピュータに渡される計算単位をインターリーブすることが好ましい。この点で、各計算の計算単位は、他の計算とともに実行依頼されると、当該他の計算の擬装計算単位として働く。
【００４１】
ＣＲＴでは、例えば計算単位＜Ｆ１，ｍ１＞、＜Ｆ２，ｍ２＞、および＜Ｆ３，ｍ３＞の結合は、結果が実際には無意味である場合でさえも、外見上有効な結果を与える。というのは、計算単位は、完全に個別の３つの完全な計算（Ｆ１、Ｆ２、およびＦ３）から来るからである。
【００４２】
別の例として、例えばＣＲＴを使用して計算を区分するときに異なる計算に異なるｍｉを選択することによって、個々の計算を区分するのに異なるやり方またはアルゴリズムを選択することが望ましい。実施形態によっては、例えば、非トラステッド・パーティが、計算を傍受することによって計算単位ごとにどのｍｉが使用されるかを決定することが可能である。そうすることによって、非トラステッド・パーティは、複数の計算単位を同じｍｉを有するバケットにソートすることができるかもしれない。ＣＲＴでは、１つのバケットからの計算単位は、同じバケットからの計算単位と再結合することができない。というのは、ＣＲＴでのｍｉは、互いに素でなければならないからである。したがって、Ｆ個の計算がそれぞれ同じｍｉを使用して３つの計算単位に区分された場合、非トラステッド・パーティは、計算単位を３つのバケットにソートし、次いで単位を再結合できるＦ３通りの方法を分析することができることになる。一般に、Ｆ個の計算がそれぞれＰ個の計算単位に区分された場合、こうした計算単位を再結合するにはＦＰ通りの方法が考えられる。
【００４３】
この潜在的な攻撃の形に対処するために、例えば好適なｍｉのスーパーセットからｍｉを選択することによって、完全な計算ごとに異なる組のｍｉを選択することができる。例えば、多くの実施形態では、各計算を３つの単位に分割するので十分である。しかし、３つのｍｉを選択する代わりに、３つを上回るｍｉ、例えば概ねＭの立方根である１０個のｍｉを選択することによってさらにセキュリティが向上する。多くの場合、選択された３つのｍｉの積がＣＲＴにおいてＭに関する上記の制約を満たす限り、計算に選択された任意の３つのｍｉの積が正確にＭであるかどうかは無関係である。したがって、計算ごとに、使用可能な１０個のうちの異なる３つのｍｉを使用して計算を区分することができる。こうした実施形態では、非トラステッド・パーティがＦ個の計算について考える必要がある可能な有効な組み合わせの数はかなり多くなり、すなわち１０Ｃ３Ｆ３となる。一般にＰ個の計算単位がＦ個の各計算に使用され、Ｐ個のモジュロがＴＰ個のモジュロのスーパーセットから選択されて、Ｐ個の計算単位を生成する場合、結果として得られる計算単位を再結合するのにＴＰＣＰＦＰ通りの方法があるからである。
【００４４】
さらに別の例として、所与の計算を複数のやり方で区分し、複数の区分の計算単位をまとめて実行依頼すると、１つの区分からの計算単位は、他の各区分からの計算単位に対する擬装計算単位として働く。
【００４５】
本発明による上述したいくつかの擬装技術を使用する擬装分散コンピューティングの具体的な１つの実施形態を、図５に示す計算処理ルーチン１２０によってより詳しく示している。ルーチン１２０はブロック１２２で開始し、モジュロのスーパーセットから得た異なるモジュロを使用して、ＣＲＴでＦ個の計算を計算単位に区分する。さらにブロック１２２では、計算単位ごとに無相関の識別子を割り当てて、計算単位と特定の計算との間の関連の導出を阻止する。
【００４６】
次に、ブロック１２４では、１つまたは複数の計算プロバイダに転送される計算単位を配列し直し、それによって異なる計算からの計算単位をいっしょにインターリーブする。
【００４７】
次にブロック１２６では、複数の計算からの計算単位を１つまたは複数の計算プロバイダに転送して、計算プロバイダのコンピューティング・リソースにおいてこうした計算単位の実行を有効に開始する。次いでブロック１２８では、計算プロバイダによって生成された計算結果を集め、ブロック１３０では、ＣＲＴを使用して結果を再結合して全体的な結果を生成する。次いでブロック１３２では、計算結果をクライアントに戻し、ルーチン１２０が完了する。
【００４８】
本発明の意図および範囲から逸脱することなく、本明細書に記載した実施形態に様々な追加の変更を加えることができる。本発明の本質は、添付した特許請求の範囲に記載されている通りである。
【図面の簡単な説明】
【００４９】
【図１】本発明による擬装分散コンピューティングを実施するのに適した計算ユーティリティ環境を示すブロック図である。
【図２】図１の計算ユーティリティ環境の実施形態の例におけるソフトウェア層を示すブロック図である。
【図３】図１の計算ユーティリティ環境のハードウェアおよびソフトウェアの実施形態の例を示すブロック図である。
【図４】図３で参照したブローカ・コンピュータによって実行され、本発明による擬装分散コンピューティングを実施する計算処理ルーチンの例を示すフロー図である。
【図５】図３で参照したブローカ・コンピュータによって実行され、本発明による擬装分散コンピューティングを実施する計算処理ルーチンの別の例を示すフロー図である。
【図１】
2005209202.tif 000003
【図２】
2005209202.tif 000004
【図３】
2005209202.tif 000005
【図４】
2005209202.tif 000006
【図５】
2005209202.tif 000007