(57)【特許請求の範囲】
【請求項１】
クライアント・データを提供するためのクライアント・コンピュータであって、
前記クライアント・データに対応する、インデックスｉ＝１乃至ｎを有する複数ｎ個のデータ・ブロックｘｉを含むベクトル
【数１】
0006959994.tif 000138
を定め、
前記ベクトルｘ（ベクトル）に対する、非秘匿ベクトル・コミットメントである第１のコミットメントを生成し、
前記ベクトルｘ（ベクトル）に対する、秘匿ベクトル・コミットメントである第２のコミットメントを生成し、
前記第１のコミットメントに対する第３のコミットメントを生成し、
前記第２のコミットメント及び前記第３のコミットメントを鍵サーバに送り、
前記第２のコミットメント及び前記第３のコミットメントにおける前記ベクトルｘ（ベクトル）の、前記インデックスｉのサブセットについての対応する前記データ・ブロックｘｉの知識の第１の証明を前記鍵サーバに提供する、
ように構成されたクライアント・コンピュータと、
ネットワーク上で通信するための鍵サーバであって、
秘密のサーバ鍵ｋを格納し、
前記第１の証明を検証することに応答して、鍵生成プロトコルにおいて前記クライアント・コンピュータと関与する、
ように構成された鍵サーバと、
を含み、
前記クライアント・コンピュータは、関与する間、
前記第１のコミットメントのブラインド関数を前記鍵サーバに送り、前記ブラインド関数及び前記第３のコミットメントにおける前記第１のコミットメントの知識の第２の証明を前記鍵サーバに提供する、
ように構成され、
前記鍵サーバは、関与する間、
前記第２の証明を検証することに応答して、前記ブラインド関数から、前記第１のコミットメント及び前記サーバ鍵ｋの前記ブラインド関数を含むブラインド鍵Ｋ´を生成し、
前記ブラインド鍵Ｋ´を前記クライアント・コンピュータに送る、
ように構成され、
前記クライアント・コンピュータは、前記関与する間、前記ブラインド鍵Ｋ´を非ブラインド化し、前記第１のコミットメント及び前記サーバ鍵ｋの決定性関数を含むクライアント鍵Ｋを取得するように構成される、システム。
【請求項２】
前記鍵生成プロトコルの間、前記システムにおいて、さらに、
前記鍵サーバは、準同型暗号化スキームを介して暗号化スキームの公開鍵の下で前記サーバ鍵ｋを暗号化して、暗号化された鍵を生成し、前記暗号化された鍵を前記クライアント・コンピュータに送るように構成され、
前記クライアント・コンピュータは、前記暗号化スキームを介して前記公開鍵の下で前記第１のコミットメントを暗号化して暗号化されたコミットメントを生成し、ナンスを用いて前記暗号化された鍵及び前記暗号化されたコミットメントの関数をブラインド化することにより、前記第１のコミットメントの前記ブラインド関数を生成するように構成され、
前記鍵サーバは、前記暗号化スキームの復号アルゴリズムを介して、前記公開鍵に対応するプライベート鍵を用いて、前記第１のコミットメントの前記ブラインド関数を復号して、復号された値Ｖを取得し、前記復号された値Ｖから前記ブラインド鍵Ｋ´を生成するように構成され、
前記クライアント・コンピュータは、前記ナンスを用いて、前記ブラインド鍵Ｋ´を非ブラインド化することにより、前記クライアント鍵Ｋを取得するように構成される、請求項１に記載のシステム。
【請求項３】
前記鍵サーバは、前記クライアント鍵Ｋが前記第１のコミットメント及び前記サーバ鍵ｋの疑似ランダム関数を含むように、前記ブラインド鍵Ｋ´を生成するように構成される、請求項２に記載のシステム。
【請求項４】
前記システムは、さらに、
知識の前記第１の証明が、前記第３のコミットメントにおける前記第１のコミットメントの知識を証明する第１の部分証明、前記第２のコミットメント及び前記第３のコミットメントが共通の値から計算されることを証明する第２の部分証明、及び第３の部分証明を含み、
前記クライアント・コンピュータは、前記第２のコミットメント及び前記第３のコミットメントと共に、前記第１の部分証明及び前記第２の部分証明を前記鍵サーバに送るように構成され、
前記鍵サーバは、前記第１の部分証明及び前記第２の部分証明を検証することに応答して、前記インデックスｉの前記サブセットを選択し、前記サブセットを前記クライアント・コンピュータに送るように構成され、
前記クライアント・コンピュータは、前記第２のコミットメントにおける前記ベクトルｘ（ベクトル）の、前記サブセットにおける前記インデックスｉの各々に対する前記データ・ブロックｘｉの知識を証明する第３の部分証明を生成するように構成され、
前記鍵サーバは、前記第３の部分証明を検証して、知識の前記第１の証明を検証するように構成される、請求項１に記載のシステム。
【請求項５】
前記第２のコミットメントは、前記第１のコミットメントから計算され、共通の値は、前記第１のコミットメントを含む、請求項４に記載のシステム。
【請求項６】
前記システムは、１つより多くの前記クライアント・コンピュータを含み、前記１つより多くのクライアント・コンピュータの各々は、前記ネットワークを介して前記鍵サーバと通信するように適合される、請求項１に記載のシステム。
【請求項７】
前記１つより多くのクライアント・コンピュータは、その前記クライアント鍵Ｋを用いて前記クライアント・データを暗号化して暗号文を生成し、前記ネットワークにおける遠隔ストレージのために前記暗号文を送るようにさらに構成される、請求項６に記載のシステム。
【請求項８】
前記システムは、
前記１つよい多くのクライアント・コンピュータから受け取った暗号文を格納するための、前記ネットワークに接続されたストレージ・サーバをさらに含み、前記ストレージ・サーバは、前記暗号文のための重複排除プロセスを実施するように構成される、請求項７に記載のシステム。
【請求項９】
クライアント・コンピュータにより、前記クライアント・コンピュータにおけるクライアント・データに対応する、インデックスｉ＝１乃至ｎを有する複数ｎ個のデータ・ブロックｘｉを有するベクトルｘ（ベクトル）を定めることと、
前記クライアント・コンピュータにより、前記ベクトルｘ（ベクトル）に対する、非秘匿ベクトル・コミットメントである第１のコミットメントを生成することと、
前記クライアント・コンピュータにより、前記ベクトルｘ（ベクトル）に対する、秘匿ベクトル・コミットメントである第２のコミットメントを生成することと、
前記クライアント・コンピュータにより、前記第１のコミットメントに対する第３のコミットメントを生成することと、
前記クライアント・コンピュータにより、前記第２のコミットメント及び前記第３のコミットメントを鍵サーバに送ることと、
前記クライアント・コンピュータにより、前記第２のコミットメント及び前記第３のコミットメントにおける前記ベクトルｘ（ベクトル）の、前記インデックスｉのサブセットについての対応する前記データ・ブロックｘｉの知識の第１の証明を前記鍵サーバに提供することと、
前記鍵サーバにより前記第１の証明を検証することに応答して、
前記クライアント・コンピュータにより、前記第１のコミットメントのブラインド関数を前記鍵サーバに送ることにより、鍵生成プロトコルを実行し、前記ブラインド関数及び前記第３のコミットメントにおける前記第１のコミットメントの知識の第２の証明を前記鍵サーバに提供し、前記鍵サーバから、前記ブラインド関数から生成され、前記第１のコミットメント及び前記鍵サーバの秘密サーバ鍵ｋの前記ブラインド関数を含むブラインド鍵Ｋ´を受け取り、前記ブラインド鍵Ｋ´を非ブラインド化して、前記第１のコミットメント及び前記サーバ鍵ｋの決定性関数を含むクライアント鍵Ｋを取得することと、
を含む、方法。
【請求項１０】
前記鍵生成プロトコルを実行することは、
前記クライアント・コンピュータにより、前記鍵サーバから、準同型暗号化スキームを介して暗号化スキームの公開鍵の下で前記サーバ鍵を暗号化することにより生成される暗号化鍵を受け取ることと、
前記クライアント・コンピュータにより、前記暗号化スキームを介して前記公開鍵の下で前記第１のコミットメントを暗号化し、暗号化されたコミットメントを生成することと、
前記クライアント・コンピュータにより、ナンスを用いて前記暗号化された鍵及び前記暗号化されたコミットメントの関数をブラインド化することにより、前記第１のコミットメントの前記ブラインド関数を生成することと、
前記第１のコミットメントの前記ブラインド関数を復号することにより取得される復号された値Ｖから、前記鍵サーバにおいて生成された前記ブラインド鍵Ｋ´を受け取ることに応答して、前記クライアント・コンピュータにより、前記暗号化スキームの復号アルゴリズムを介して、前記公開鍵に対応するプライベート鍵を使用し、前記ナンスを用いて前記ブラインド鍵Ｋ´を非ブラインド化することと、
を含む、請求項９に記載の方法。
【請求項１１】
知識の前記第１の証明は、前記第３のコミットメントにおける前記第１のコミットメントの知識を証明する第１の部分証明、前記第２のコミットメント及び前記第３のコミットメントが共通の値から計算されることを証明する第２の部分証明、及び第３の部分証明を含み、さらに、
前記クライアント・コンピュータにより、前記第２のコミットメント及び前記第３のコミットメントと共に、前記第１の部分証明及び前記第２の部分証明を前記鍵サーバに送ることと、
前記鍵サーバにより前記第１の部分証明及び前記第２の部分証明を検証することに応答して、前記クライアント・コンピュータにより、前記鍵サーバから、前記インデックスｉの前記サブセットを受け取ることと、
前記クライアント・コンピュータにより、前記第２のコミットメントにおける前記ベクトルｘ（ベクトル）の、前記サブセットにおける前記インデックスｉの各々に対する前記データ・ブロックｘｉの知識を証明する前記第３の部分証明を生成することと、
前記クライアント・コンピュータにより、前記第３の部分証明を前記鍵サーバに送ることと、
を含む、請求項９に記載の方法。
【請求項１２】
前記クライアント・コンピュータにより、前記第１のコミットメントから前記第２のコミットメントを計算することをさらに含み、前記共通の値は、前記第１のコミットメントを含む、請求項１１に記載の方法。
【請求項１３】
前記クライアント・コンピュータにより、前記クライアント鍵Ｋを用いて前記クライアント・データを暗号化して暗号文を生成することと、
前記クライアント・コンピュータにより、前記暗号文を、ネットワークに接続され、格納された暗号文のための重複排除プロセスを実施するように適合されたストレージ・サーバに送ることと、
をさらに含む、請求項９に記載の方法。
【請求項１４】
知識の前記第１の証明は、前記第３のコミットメントにおける前記第１のコミットメントの知識を証明する第１の部分証明、前記第２のコミットメント及び前記第３のコミットメントが共通の値から計算されることを証明する第２の部分証明、及び第３の部分証明を含み、前記方法はさらに、
前記クライアント・コンピュータにより、前記第２のコミットメント及び前記第３のコミットメントと共に、前記第１の部分証明及び前記第２の部分証明を前記鍵サーバに送ることと、
前記鍵サーバにより前記第１の部分証明及び前記第２の部分証明を検証することに応答して、前記クライアント・コンピュータにより、前記鍵サーバから、前記インデックスｉの前記サブセットを受け取ることと、
前記クライアント・コンピュータにより、前記第２のコミットメントにおける前記ベクトルｘ（ベクトル）の、前記サブセットにおける前記インデックスｉの各々に対する前記データ・ブロックｘｉの知識を証明する前記第３の部分証明を生成することと、
前記クライアント・コンピュータにより、前記第３の部分証明を前記鍵サーバに送ることと、
前記クライアント・コンピュータにより、前記クライアント鍵Ｋを用いて前記クライアント・データを暗号化して暗号文を生成することと、
前記クライアント・コンピュータにより、前記暗号文を、ネットワークに接続され、格納された暗号文のための重複排除プロセスを実施するように構成されたストレージ・サーバに送ることと、
を含む、請求項１０に記載の方法。
【請求項１５】
クライアント鍵Ｋをクライアント・コンピュータに提供する方法であって、前記クライアント・コンピュータは、クライアント・データを提供し、前記クライアント・データに対応する、インデックスｉ＝１乃至ｎを有する複数ｎ個のデータ・ブロックｘｉを有するベクトルｘ（ベクトル）を定め、前記ベクトルｘ（ベクトル）に対する、非秘匿ベクトル・コミットメントである第１のコミットメントを生成するように適合され、前記方法は、ネットワークを介して前記クライアント・コンピュータと通信するように適合された鍵サーバにおいて、
秘密サーバ鍵ｋを格納することと、
前記クライアント・コンピュータから、前記ベクトルｘ（ベクトル）に対する、秘匿ベクトル・コミットメントである第２のコミットメント、及び前記第１のコミットメントに対する第３のコミットメントを受け取ることと、
前記クライアント・コンピュータから、前記第２のコミットメント及び前記第３のコミットメントにおける前記ベクトルｘ（ベクトル）の、インデックスｉのサブセットについての対応する前記データ・ブロックｘｉの知識の第１の証明を受け取ることと、
前記第１の証明を検証することと、
前記第１の証明の検証に応答して実施される鍵生成プロトコルにおいて、前記クライアント・コンピュータから、前記第１のコミットメントのブラインド関数、並びに前記ブラインド関数及び前記第３のコミットメントにおける前記第１のコミットメントの知識の第２の証明を受け取ることと、
前記第２の証明を検証し、それに応答して、前記第１のコミットメントの前記ブラインド関数から、前記第１のコミットメント及び前記サーバ鍵ｋのブラインド関数を含むブラインド鍵Ｋ´を生成し、前記クライアント・コンピュータにおける非ブラインド化のために前記ブラインド鍵Ｋ´を前記クライアント・コンピュータに送り、前記第１のコミットメント及びサーバ鍵ｋの決定性関数を含むクライアント鍵Ｋを取得することと、
を含む、方法。
【請求項１６】
前記鍵生成プロトコルにおける前記鍵サーバにおいて、
準同型暗号化スキームを介して前記スキームの公開鍵の下で前記サーバ鍵ｋを暗号化し、暗号化された鍵を生成することと、
前記暗号化された鍵を前記クライアント・コンピュータに送って、前記暗号化スキームを介して前記公開鍵の下で前記第１のコミットメントを暗号化して前記第１のコミットメントの前記ブラインド関数を生成し、暗号化されたコミットメント生成し、ナンスを用いて前記暗号化された鍵及び前記暗号化されたコミットメントの関数をブラインド化することにより、前記第１のコミットメントの前記ブラインド関数を生成することと、
前記暗号化スキームの復号アルゴリズムを介して、前記公開鍵に対応するプライベート鍵を用いて、前記第１のコミットメントの前記ブラインド関数を復号し、復号された値Ｖを取得することと、
前記ナンスを用いて前記ブラインド鍵Ｋ´を非ブラインド化することにより、前記クライアント・コンピュータが前記クライアント鍵Ｋを取得できるように、前記復号された値Ｖから前記ブラインド鍵Ｋ´を生成することと、
を含む、請求項１５に記載の方法。
【請求項１７】
前記クライアント鍵Ｋが前記第１のコミットメント及び前記サーバ鍵ｋの疑似ランダム関数を含むように、前記ブラインド鍵Ｋ´を生成することを含む、請求項１６に記載の方法。
【請求項１８】
知識の前記第１の証明は、前記第３のコミットメントにおける前記第１のコミットメントの知識を証明する第１の部分証明、前記第２のコミットメント及び前記第３のコミットメントが共通の値から計算されることを証明する第２の部分証明、及び第３の部分証明を含み、前記方法は、前記鍵サーバにおいて、
前記第２のコミットメント及び前記第３のコミットメントと共に、前記クライアント・コンピュータから、前記第１の部分証明及び前記第２の部分証明を受け取ることと、
前記第１の部分証明及び前記第２の部分証明を検証し、それに応答して、前記インデックスｉの前記サブセットを選択し、前記サブセットを前記クライアント・コンピュータに送ることと、
前記クライアント・コンピュータから、前記第２のコミットメントにおける前記ベクトルｘ（ベクトル）の、前記サブセットにおける前記インデックスｉの各々に対する前記データ・ブロックｘｉの知識を証明する前記第３の部分証明を受け取ることと、
前記第３の部分証明を検証し、知識の前記第１の証明を検証することと、
を含む、請求項１５に記載の方法。
【請求項１９】
知識の前記第１の証明は、前記第３のコミットメントにおける前記第１のコミットメントの知識を証明する第１の部分証明、前記第２のコミットメント及び前記第３のコミットメントが共通の値から計算されることを証明する第２の部分証明、及び第３の部分証明を含み、前記方法は、前記鍵サーバにおいて、
前記第２のコミットメント及び前記第３のコミットメントと共に、前記クライアント・コンピュータから、前記第１の部分証明及び前記第２の部分証明を受け取ることと、
前記第１の部分証明及び前記第２の部分証明を検証し、それに応答して、前記インデックスｉの前記サブセットを選択し、前記サブセットを前記クライアント・コンピュータに送ることと、
前記クライアント・コンピュータから、前記第２のコミットメントにおける前記ベクトルｘ（ベクトル）の、前記サブセットにおける前記インデックスｉの各々に対する前記データ・ブロックｘｉの知識を証明する前記第３の部分証明を受け取ることと、
前記第３の部分証明を検証し、知識の前記第１の証明を検証することと、
前記鍵生成プロトコルにおいて、前記クライアント鍵Ｋが前記第１のコミットメント及び前記サーバ鍵ｋの疑似ランダム関数を含むように、前記ブラインド鍵Ｋ´を生成することと、
を含む、請求項１６に記載の方法。
【請求項２０】
請求項９〜１９の何れか１項に記載の方法の各ステップをコンピュータに実行させる、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、暗号化鍵の生成に関し、より特定的には、鍵を用いるコンピュータにより保持されるデータから決定論的に導出される鍵の生成に関する。本発明の実施形態は、データ重複排除（ｄｅｄｕｐｌｉｃａｔｉｏｎ）システムに適用することができる。
【先行技術文献】
【非特許文献】
【０００２】
【非特許文献１】Ｃａｍｅｎｉｓｃｈ他、「Ｏｎ  ｔｈｅ  ｐｏｒｔａｂｉｌｉｔｙ  ｏｆ  ｇｅｎｅｒａｌｉｚｅｄ  Ｓｃｈｎｏｒｒ  ｐｒｏｏｆｓ」、ＥＵＲＯＣＲＹＰＴ  ２００９、ｖｏｌｕｍｅ５４７９  ｏｆ  ＬＮＣＳ、ページ４２５−４４２、２００９年４月
【非特許文献２】Ｃａｍｅｎｉｓｃｈ及びＳｔａｄｌｅｒ、「Ｅｆｆｉｃｉｅｎｔ  ｇｒｏｕｐ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ  ｆｏｒ  ｌａｒｇｅ  ｇｒｏｕｐｓ」（拡張アブストラクト）、ＣＲＹＰＴＯ‘９７、ｖｏｌｕｍｅ１２９４  ｏｆ  ＬＮＣＳ、ページ４１０−４２４、１９９７年８月
【非特許文献３】「Ｓｈｏｒｔ  ｓｉｇｎａｔｕｒｅｓ  ｗｉｔｈｏｕｔ  ｒａｎｄｏｍ  ｏｒａｃｌｅｓ」、ＥＵＲＯＣＲＹＰＴ  ２００４、ｖｏｌｕｍｅ  ３０２７  ｏｆ  ＬＮＣＳ、ページ５６−７３、２００４年５月
【非特許文献４】「Ａ  ｖｅｒｉｆｉａｂｌｅ  ｒａｎｄｏｍ  ｆｕｎｃｔｉｏｎ  ｗｉｔｈ  ｓｈｏｒｔ  ｐｒｏｏｆｓ  ａｎｄ  ｋｅｙｓ」、ＰＫＣ  ２００５、ｖｏｌｕｍｅ  ３３８６  ｏｆ  ＬＮＣＳ、ページ４１６−４３１、２００５年１月
【非特許文献５】Ｊａｒｅｃｋｉ及びＬｉｕ、「Ｅｆｆｉｃｉｅｎｔ  ｏｂｌｉｖｉｏｕｓ  ｐｓｅｕｄｏｒａｎｄｏｍ  ｆｕｎｃｔｉｏｎ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  ａｄａｐｔｉｖｅ  ＯＴ  ａｎｄ  ｓｅｃｕｒｅ  ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｓｅｔ  ｉｎｔｅｒｓｅｃｔｉｏｎ」、ＴＣＣ  ２００９年、ｖｏｌｕｍｅ５４４４  ｏｆ  ＬＮＣＳ、ページ５７７−５９４、２００９年３月
【非特許文献６】Ｃｈａｓｅ及びＭｅｉｋｌｅｊｏｈｎ、「Ｄｅｊａ  Ｑ：  Ｕｓｉｎｇ  ｄｕａｌ  ｓｙｓｔｅｍｓ  ｔｏ  ｒｅｖｉｓｉｔ  ｑ−ｔｙｐｅ  ａｓｓｕｍｐｔｉｏｎｓ」、ＥＵＲＯ−ＣＲＹＰＴ  ２０１４、ｖｏｌｕｍｅ  ８４４１  ｏｆ  ＬＮＣＳ、ページ６２２−６３９、２０１４年５月
【非特許文献７】Ｄｏｄｉｓ他、「Ｅｆｆｉｃｉｅｎｔ  ｃｏｎｓｔｒｕｃｔｉｏｎｓ  ｏｆ  ｃｏｍｐｏｓａｂｌｅ  ｃｏｍｍｉｔｍｅｎｔｓ  ａｎｄ  ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ  ｐｒｏｏｆｓ」、ＣＲＹＰＴＯ  ２００８、ｖｏｌｕｍｅ  ５１５７  ｏｆ  ＬＮＣＳ、ページ５１５−５３５、２００８年８月
【非特許文献８】Ｃａｍｅｎｉｓｃｈ及びＳｈｏｕｐ、「Ｐｒａｃｔｉｃａｌ  ｖｅｒｉｆｉａｂｌｅ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｄｅｃｒｙｐｔｉｏｎ  ｏｆ  ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍｓ」ＣＲＹＰＴＯ  ２００３、ｖｏｌｕｍｅ  ２７２９  ｏｆ  ＬＮＣＳ、ページ１２６−１４４、２００３年８月
【非特許文献９】Ａｌｇｅｓｈｅｉｍｅｒ他、「Ｅｆｆｉｃｉｅｎｔ  ｃｏｍｐｕｔａｔｉｏｎ  ｍｏｄｕｌｏ  ａ  ｓｈａｒｅｄ  ｓｅｃｒｅｔ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｔｈｅ  ｇｅｎｅｒａｔｉｏｎ  ｏｆ  ｓｈａｒｅｄ  ｓａｆｅ−ｐｒｉｍｅ  ｐｒｏｄｕｃｔｓ」、ＣＲＹＰＴＯ  ２００２、ｖｏｌｕｍｅ  ２４４２  ｏｆ  ＬＮＣＳ、ページ４１７−４３２、２００２年８月
【非特許文献１０】Ｂｏｎｅｈ及びＣｏｒｒｉｇａｎ−Ｇｉｂｂｓ、「Ｂｉｖａｒｉａｔｅ  ｐｏｌｙｎｏｍｉａｌｓ  ｍｏｄｕｌｏ  ｃｏｍｐｏｓｉｔｅｓ  ａｎｄ  ｔｈｅｉｒ  ａｐｐｌｉｃａｔｉｏｎｓ」、ＡＳＩＡＣＲＹＰＴ  ２０１４、Ｐａｒｔ  Ｉ、ｖｏｌｕｍｅ  ８８７３  ｏｆ  ＬＮＣＳ、ページ４２−６２、２０１４年１２月
【非特許文献１１】Ｍｅｒｋｌｅ、「Ａ  ｃｅｒｔｉｆｉｅｄ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅ」、ＣＲＹＰＴＯ’８９、ｖｏｌｕｍｅ  ４３５  ｏｆ  ＬＮＣＳ、ページ２１８−２３８、１９９０年８月
【非特許文献１２】Ｃａｔａｌａｎｏ及びＦｉｏｒｅ、「Ｖｅｃｔｏｒ  ｃｏｍｍｉｔｍｅｎｔｓ  ａｎｄ  ｔｈｅｉｒ  ａｐｐｌｉｃａｔｉｏｎｓ」、ＰＫＣ  ２０１３、ｖｏｌｕｍｅ  ７７７８  ｏｆ  ＬＮＣＳ、ページ５５−７２、２０１３年
【非特許文献１３】Ｃａｔａｌａｎｏ、「Ｖｅｃｔｏｒ  ｃｏｍｍｉｔｍｅｎｔｓ  ａｎｄ  ｔｈｅｉｒ  ａｐｐｌｉｃａｔｉｏｎｓ」、ＰＫＣ  ２０１３、ｖｏｌｕｍｅ  ７７７８  ｏｆ  ＬＮＣＳ、ページ５５−７２、２０１３年
【発明の概要】
【発明が解決しようとする課題】
【０００３】
データ重複排除のためのアプリケーションによる暗号化鍵の生成のためのシステム、方法、及びコンピュータ・プログラムを提供する。
【課題を解決するための手段】
【０００４】
本発明の少なくとも１つの実施形態によると、ネットワークを介して通信するように適合されたクライアント・コンピュータ及び鍵サーバを含むシステムが提供される。クライアント・コンピュータは、クライアント・データを提供し、クライアント・データに対応する、インデックスｉ＝１乃至ｎを有する複数ｎのデータ・ブロックｘｉを含むベクトル
【数１】
0006959994.tif 000002
を定めるように適合される。クライアント・コンピュータは、さらに、ベクトルｘ（ベクトル）に対する、非秘匿ベクトル・コミットメントである第１のコミットメントと、ｘ（ベクトル）に対する、秘匿ベクトル・コミットメントである第２のコミットメントと、第１のコミットメントに対する第３のコミットメントとを生成するように適合される。クライアント・コンピュータは、第２及び第３のコミットメントを鍵サーバに送り、第２及び第３のコミットメントにおけるベクトルｘ（ベクトル）の、インデックスｉのサブセットについての対応するデータ・ブロックｘｉの知識の第１の証明を鍵サーバに提供する。鍵サーバは、秘密サーバ鍵ｋを格納し、知識の第１の証明の検証に応答して、鍵生成プロトコルにおけるクライアント・コンピュータと関与する（engage）ように適合される。このプロトコルにおいて、クライアント・コンピュータは、第１のコミットメントのブラインド関数（blinded function）を鍵サーバに送り、このブラインド関数及び第３のコミットメントにおける、第１のコミットメントの知識の第２の証明を鍵サーバに提供する。鍵サーバは、知識の第２の証明の検証に応答して、上述のブラインド関数から、第１のコミットメント及びサーバ鍵ｋのブラインド関数を含むブラインド鍵Ｋ´を生成し、ブラインド鍵Ｋ´をクライアント・コンピュータに送るように適合される。クライアント・コンピュータは、さらに、ブラインド鍵Ｋ´を非ブラインド化し（unblind）、第１のコミットメント及びサーバ鍵ｋの決定性関数を含むクライアント鍵Ｋを取得する。
【図面の簡単な説明】
【０００５】
【図１】本発明の実施形態による、システムのブロック図である。
【図２】本発明の実施形態による、クライアント鍵を生成するための動作ステップを示すフローチャートである。
【図３】本発明の実施形態による、クライアント・データを格納するための動作ステップを示すフローチャートである。
【図４】本発明の別の実施形態による、クライアント鍵を生成するための動作ステップを示すフローチャートである。
【図５】本発明の別の実施形態による、クライアント鍵を生成するための動作ステップを示すフローチャートである。
【図６】本発明の実施形態による、図１のコンピュータ・システムの内部及び外部コンポーネントのブロック図である。
【図７】本発明の実施形態による、クラウド・コンピューティング環境のブロック図である。
【図８】本発明の実施形態による、抽象化モデル層のブロック図である。
【発明を実施するための形態】
【０００６】
コンピュータにおいて提供されるデータの決定性関数として暗号化鍵を生成することは、セキュアなデータ重複排除システムの基礎となる。データ重複排除は、ストア・システムが、ファイルなどの特定のデータ項目の１つのコピーのみを格納することを保証することにより、ストレージ要件を減らすために用いられるプロセスである。前に格納したファイルの第２のコピーの格納が要求された場合、このことは、典型的には、ファイルのハッシュを既にサーバにより格納されているファイルのハッシュと比較することによって、ストレージ・サーバにより検知される。一致が検知された場合、新しいファイルは格納されず、サーバは単に、一致している、前に格納したファイルへのポインタを格納する。
【０００７】
クライアント・コンピュータが、データを、それらの信頼ドメインの外にあるストレージ・サーバ（例えば、クラウド・ベースのストレージ・プロバイダ）に送る場合、セキュリティは、データを、格納のために送る前に暗号化することを必要とする。重複排除を可能にするために、暗号化プロセスは、決定論的とすることができ（すなわち、同じデータは同じ暗号文に暗号化される）、一致を検知することができる。さらに、同じ暗号化鍵を用いて、同じデータを暗号化できることが必要である。ストレージ・サーバが、異なるクライアント・コンピュータにより送られるデータの重複排除を実施する場合、効果的なユーザをまたがる重複排除のためには、全てのクライアント・コンピュータが同じファイルを暗号化するために同じ鍵を導出することが可能であるようにすることができる。
【０００８】
典型的には、鍵導出のためのスキームは、データ自体ではなく、クライアント・データの公開ハッシュ（public hash）のみに依存し得る。そのため、悪意のあるパーティは、ファイルのハッシュだけを知ることにより、ファイルの暗号化鍵を取得することができる。従って、こうしたスキームを配備するいずれのシステムも、現実的なセキュリティ・モデルにおいてセキュア保護されていず、ストレージ・サーバの何らかのセキュリティ侵害（compromise）のために、ファイルに対する暗号文を取得する相手方、又は悪意のあるストレージ・プロバイダ自体が、鍵を用いてそれを復号することがある。
【０００９】
図中のフローチャート及びブロック図は、本発明の種々の実施形態によるシステム、方法及びコンピュータ・プログラム製品の考え得る実装のアーキテクチャ、機能及び動作を示す。これに関して、フローチャート又はブロック図中の各ブロックは、モジュール、セグメント、又は命令の部分を表すことができ、これは、指定された論理機能を実施するための１つ又は複数の実行可能命令を含む。また、幾つかの代替的な実施において、ブロック内に示された機能は、図中に示された順序とは異なる順序で行い得る。例えば、連続して示される２つのブロックを、実際には、実質的に同時に実行することができ、又は場合により、関与する機能に応じて、ブロックを逆の順番で実行することもできる。また、ブロック図及び／又はフローチャート図の各ブロック、並びにブロック図及び／又はフローチャート図中のブロックの組み合わせは、指定された機能又は動作を実行する専用のハードウェア・ベースのシステム、又は専用のハードウェアとコンピュータ命令の組み合わせによって実施できることにも留意されたい。
【００１０】
図１は、本発明の実施形態による、システム１００のブロック図である。システム１００は、複数のクライアント・コンピュータ１０２、鍵サーバ１０３、及びストレージ・サーバ１０４を含む。クライアント・コンピュータ１０２は、ネットワーク１０５を介して鍵サーバ１０３及びストレージ・サーバ１０４と通信するように適合することができ、そこで、ネットワーク１０５は、１つ又は複数のコンポーネント・ネットワーク、及び／又はインターネットを含む相互接続ネットワークを含むことができる。システム１００の動作において、クライアント・コンピュータ１０２は、ストレージ・サーバ１０４による格納のために、ネットワーク１０５を介して、クライアント・データ（例えば、データ・ファイル）を送る。ストレージ・サーバ１０４は、クライアント・コンピュータ１０２の信頼ドメインの外にあることがあるので、ストレージ・サーバ１０４に伝送する前に、クライアント・コンピュータ１０２により、全てのファイルが暗号化される。ストレージ・サーバ１０４は、クライアント・コンピュータ１０２から受け取った暗号化されたファイルを、ストレージ・サーバ１０４に動作可能に結合されたデータベース１０６により表されるストレージ内に格納することができる。ストレージ・サーバ１０４は、データベース１０６内に格納された暗号化ファイルの重複排除を実行する。例えば、重複排除の粒度は、暗号化ファイル全体とすることができる。従って、ストレージ・サーバ１０４は、データベース１０６内のあらゆる所定の暗号化ファイルの１つのコピーを格納することができる。以下により詳細に説明されるように、ストレージ・サーバ１０４は、クライアント・コンピュータ１０２の１つから、前に格納した暗号化ファイルの第２のコピーを受け取るかどうかを検知することができる。ストレージ・サーバ１０４は、暗号化ファイルを再び格納せず、代わりに、当該クライアント・コンピュータ１０２の１つに、同一の、前に格納したファイルへのポインタを送ることができる。
【００１１】
クライアント・コンピュータ１０２の各々は、そのファイルに対する、Ｋで示されるクライアント鍵を用いて、格納のためにファイルを暗号化することができる。クライアント・コンピュータ１０２にわたるファイルの重複排除を可能にするために、同一のクライアント・ファイルは、同一の暗号文に暗号化することができ、かつ、同じ暗号化鍵を用いて暗号化することができる。従って、異なるクライアント・コンピュータ１０２が同一のファイルを暗号化する場合、クライアント・コンピュータ１０２の各々は、ファイルに対する同じクライアント鍵を使用することができる。クライアント鍵Ｋは、鍵サーバ１０３との対話を介して、クライアント・コンピュータ１０２により取得される。鍵サーバ１０３は、鍵サーバ１０３に対して秘密である暗号化鍵ｋを格納することができる。クライアント鍵Ｋを取得するために、クライアント・コンピュータ１０２は、鍵サーバ１０３と、暗号化プロトコルにおいて関与することができ、それにより、クライアント・コンピュータ１０２の１つは、サーバ鍵ｋの及び暗号化されるクライアント・ファイルの決定性関数である鍵Ｋを取得する。このプロトコルは、クライアント・コンピュータ１０２が、鍵Ｋを取得するために、クライアント・ファイルの知識を証明することを要求することができる。従って、クライアント鍵は、ファイルの短いハッシュではなく、クライアント・ファイル自体を保有するクライアント・コンピュータ１０２の１つによってしか取得することができない。鍵サーバ１０３は、クライアント・コンピュータ１０２により信頼されていないことあるので、鍵サーバ１０３が、クライアント・ファイル及び／又は結果として得られるクライアント鍵を知らずに、プロトコルを実行することができる。
【００１２】
鍵サーバ１０３は、鍵生成サービスをクライアント・コンピュータ１０２に提供するエンティティ（例えば、クラウド・サービス・プロバイダ）により動作されるコンピュータにより実装され得る。ストレージ・サーバ１０４は、同様に、ストレージ・サービス・プロバイダ（例えば、クラウド・ストレージ・プロバイダ）により動作されるコンピュータにより実装され得る。データベース１０６は、１つ又は複数のデータ・ストレージ媒体を含む任意のデータ・ストレージ装置を含むことができ、クラウド・ストレージ環境における分散型ストレージ装置により実装され得る。典型的なストレージ装置は、コンピュータの内部に（例えば、ハードディスク・ドライブ内に）あることもあり、又は外部からアクセス可能なディスク装置により（例えば、独立ディスク冗長アレイ（redundant array of independent disks）のようなディスク・ドライブ・アレイ内に）提供される、磁気若しくは光ディスクのような１つ又は複数のディスクを含むディスク・ストレージ装置を含むことができる。
【００１３】
クライアント・コンピュータ１０２は、例えば、デスクトップ・コンピュータ、ラップトップ・コンピュータ、タブレット、ノートブック、パームトップ、携帯電話、ＰＤＡ（携帯情報端末）、パーソナル音楽プレーヤ等のようなユーザ・コンピュータ、又はデータを格納するために遠隔ストレージを用いる他のいずれかのコンピュータにより実装され得る。
【００１４】
一般に、システム１００のクライアント・コンピュータ１０２、鍵サーバ１０３、ストレージ・サーバ１０４は、本明細書で説明される動作を実施するための機能を提供する１つ又は複数の実マシン及び／又は仮想マシンを含むことができる、１つ又は複数の汎用又は専用コンピュータにより実装され得る。この機能は、ハードウェア、又はソフトウェア、又はその組み合わせの形で実施される論理により提供することができる。こうした論理は、コンピューティング装置により実行される、プログラム・モジュールなどのコンピュータ・システム実行可能命令の一般的な文脈で説明することができる。一般に、プログラム・モジュールは、特定のタスクを実行する又は特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、論理、データ構造等を含むことができる。コンピューティング装置は、タスクが、通信ネットワークを通じて結び付けられた遠隔処理デバイスによって実行される分散型クラウド・コンピューティング環境において実施することができる。分散型クラウド・コンピューティング環境において、データ及びプログラム・モジュールは、メモリ・ストレージ・デバイスを含むローカル・コンピュータ・システム・ストレージ媒体及び遠隔コンピュータ・システム・ストレージ媒体の両方に配置され得る。
【００１５】
図２は、本発明の実施形態による、クライアント鍵を生成するための動作ステップを示すフローチャートである。クライアント・コンピュータ１０２が、格納のためにクライアント・ファイルＦを送ると、クライアント・コンピュータ１０２は、最初に、鍵サーバ１０３に連絡を取り、ファイルに対するクライアント鍵Ｋを取得する。ステップ３０において、クライアント・コンピュータ１０２は、そのファイルＦに対応する、インデックスｉ＝１〜ｎを有する複数ｎ個のデータ・ブロックｘｉを有するベクトルｘ（ベクトル）を定める。ステップ３０において、クライアント・コンピュータ１０２は、ファイルＦを任意の長さのｎ個のデータ・ブロックｘ１、ｘ２、・・・ｘｎに分割することができ、又は以下により詳細に説明されるように、ファイルＦを符号化し、次に、結果として得られる符号化されたファイルをｎ個のブロックｘｉに分割することができる。ステップ３１において、クライアント・コンピュータ１０２は、ベクトルｘ（ベクトル）に対する第１の暗号コミットメントを生成する。以下でより詳細に説明されるように、ｃ１で示されるこの第１のコミットメントは、非秘匿ベクトル・コミットメント（non-hiding vector commitment、ＮＨＶＣ）である。ステップ３２において、クライアント・コンピュータ１０２は、ベクトルｘ（ベクトル）に対する第２の暗号コミットメントも生成することができる。以下でより詳細に説明されるように、ｃ２で示されるこの第２のコミットメントは、秘匿ベクトル・コミットメント（hiding vector commitment、ＨＶＣ）である。さらに、ステップ３３において、クライアント・コンピュータ１０２は、第１のコミットメントｃ１に対する、ｃ３で示される第３のコミットメントを生成する。以下により詳細に説明されるように、第３のコミットメントｃ３は、「標準的な」暗号コミットメント（すなわち、暗号コミットメントの通常の秘匿性（hiding property）及び拘束性（binding property）を有する）である。ステップ３４により示されるように、クライアント・コンピュータ１０２は、第２のコミットメントｃ２及び第３のコミットメントｃ３を鍵サーバ１０３に送る。さらに、ステップ３５において、クライアント・コンピュータ１０２は、鍵サーバ１０３に対して、第２のコミットメントｃ２及び第３のコミットメントｃ３におけるベクトルｘ（ベクトル）の、インデックスｉのサブセットについての対応するデータ・ブロックｘｉの知識を、クライアント・コンピュータ１０２により証明する、Π１で示される知識の第１の暗号証明（proof of knowledge、ＰｏＫ）を提供する。この第１の証明Π１は、以下に例示されるように異なる段階で実施される。他の実施形態において、証明Π１が行われるインデックスｉのサブセットは、クライアント・コンピュータ１０２により選択することができる。１つの実施形態において、このサブセットは、セキュリティの強化のために、鍵サーバ１０３によりランダムに選択することができる。以下でより詳細に説明されるように、サブセットのサイズは、所望の通りに調整、修正、及び／又は調節することができる。
【００１６】
ステップ３６において、鍵サーバ１０３は、さらに進める前に、ｃ２及びｃ３に関して第１の証明Π１を検証する。証明が無効である場合（「いいえ」分岐、決定ブロック３７）、鍵サーバ１０３は、ステップ３８においてプロトコルをアボートし、動作は終了する。従って、鍵サーバ１０３は、検証が失敗したことを示す適切なメッセージをクライアント・コンピュータ１０２に送ることができる。Π１の成功裡の検証後（「はい」分岐、決定ブロック３７）、鍵サーバ１０３は、鍵生成プロトコルが開始されるステップ３９に進む。以下に詳細に説明されるように、このステップにおいて、鍵サーバ１０３は、クライアント・コンピュータ１０２と通信してプロトコルを開始し、鍵生成プロセスに必要なデータを送ることができる。
【００１７】
鍵生成プロセスが開始されると仮定すると、ステップ４０において、クライアント・コンピュータ１０２は、第１のコミットメントｃ１の、Ｂで示されるブラインド関数（blinded function）を生成する。ステップ４１において、クライアント・コンピュータ１０２は、鍵サーバ１０３に対して、ブラインド関数Ｂを鍵サーバ１０３に送り、ステップ４２において、クライアント・コンピュータ１０２は、Π２で示される知識の第２の暗号証明を提供する。第２の証明Π２は、ブラインド関数Ｂ及びステップ３４で送られた第３のコミットメントｃ３の両方における、第１のコミットメントｃ１の知識のクライアント・コンピュータ１０２による知識を証明する。ステップ４３において、鍵サーバ１０３は、Ｂ及びｃ３に関して第２の証明Π２を検証する。検証が失敗した場合（「いいえ」分岐、決定ブロック４４）、動作は、プロトコルがアボートされ、動作が終了するステップ３８に戻る。Π２の検証に応答して（「はい」分岐、決定ブロック４４）、動作はステップ４５に進み、そこで、鍵サーバＫは、ステップ４１で受け取ったブラインド関数Ｂからブラインド鍵Ｋ´を生成する。このブラインド鍵Ｋ´は、第１のコミットメントｃ１及びプライベート・サーバ鍵ｋのブラインド関数を含む。次に、ステップ４６において、鍵サーバ１０３は、ブラインド鍵Ｋ´をクライアント・コンピュータ１０２に送る。受信時に、クライアント・コンピュータ１０２は、ブラインド鍵Ｋ´を非ブラインド化し、最終的なクライアント鍵Ｋを取得する。
【００１８】
上記のプロトコルの動作のため、結果として得られるクライアント鍵Ｋは、第１のコミットメントｃ１及び秘密サーバ鍵ｋの決定性関数である。第１のコミットメントは、ベクトルｘ（ベクトル）に対する非秘匿ベクトル・コミットメントであるので、従って、クライアント鍵Ｋは、ベクトルｘ（ベクトル）及びサーバ鍵ｋの決定性関数である。しかしながら、ｃ１が非秘匿である間、鍵サーバ１０３は、このコミットメントのブラインド関数Ｂのみを受け取り、ｃ１自体（これは、クライアント・ファイルＦについての情報を暴露する）を知らない。従って、鍵サーバ１０３がクライアント・ファイルＦ又は最終的なクライアント鍵Ｋを知ることなく、鍵サーバ１０３を介して、クライアント鍵Ｋをオブリビアスに（obliviously）生成することができ、最終的なクライアント鍵Ｋは、クライアント・コンピュータ１０２において非ブラインド化された後にのみ取得される。さらに、クライアント・コンピュータ１０２は、その鍵の基礎となる実際のファイルＦについてのデータ・ブロックｘｉの知識を証明した後にのみ、クライアント鍵Ｋを取得することができる。コミットメント及び知識の証明の特定の組み合わせにより、データ・ブロックの知識が証明されたものと同じファイルＦに対してのみ、クライアント鍵Ｋを生成できることが保証される。特に、第２の秘匿ベクトル・コミットメントｃ２は、ファイル・ブロックを鍵サーバ１０３に暴露することなく、ファイル・ブロックｘｉの知識の証明を行うことを可能にし、第１の証明Π１は、同じベクトルｘ（ベクトル）がこのコミットメントｃ２及び第３のコミットメントｃ３の基礎となることを証明する。この第３のコミットメントｃ３は、第１のコミットメントｃ１にコミットし、次いで（関数Ｂにおいてブラインド化（blind）されたとき）、ステップ３９〜４７の鍵生成プロトコルへのクライアント入力を提供する。次に、第２の証明Π２は、第３のコミットメントｃ３が、鍵生成プロトコルにおけるブラインド関数Ｂと同じ値（ｃ１）から計算されることを証明する。従って、第３のコミットメントｃ３は、プロトコルの２つの部分（すなわち、ファイル・ブロックの知識の証明及び鍵生成）にリンクするように働き、一方、コミットメント及び証明の全体のセットは、鍵サーバ１０３により、気付かないうちにプロトコルの各部分を実行することを可能にする。
【００１９】
図３は、実施形態による、クライアント・データを格納するための動作ステップを示すフローチャートである。ステップ５０において、クライアント・コンピュータ１０２は、図２のプロセスを介して、そのファイルＦに対するクライアント鍵Ｋを取得する。ステップ５１において、クライアント・コンピュータ１０２は、対称暗号スキームを介して、クライアント鍵Ｋを用いてファイルＦを暗号化し、暗号文（すなわち、暗号化されたファイル）ＣＦを生成する。ステップ５２において、次に、クライアント・コンピュータ１０２は、ネットワーク１０５を介して、暗号文ＣＦをストレージ・サーバ１０４に送る。ステップ５３において、ストレージ・サーバ１０４は、ハッシュ関数Ｈを暗号文ＣＦに適用し、ハッシュ値Ｈ（ＣＦ）を取得する。重複排除を可能にするために、ストレージ・サーバ１０４は、データベース１０６内に格納されたあらゆる暗号化ファイルについて、そのファイルに対するハッシュ値Ｈ（ＣＦ）及びデータベース１０６内のファイルの場所を示すハッシュ・テーブルを保持する。別の実施形態において、ストレージ・サーバ１０４は、アクセス制御のために必要とされ得るあらゆる更なるデータと共に、格納されたファイルについての付加的なデータ（例えば、ファイルｉｄ、クライアントｉｄ等のようなｉｄデータ）を格納することもできる。ステップ５４において、ストレージ・サーバ１０４は、ステップ５３で取得したハッシュ値を、テーブル内の全てのハッシュ値と比較し、一致が存在するかどうかを判断する。一致が見つからない場合（「いいえ」分岐、決定ブロック５５）、ステップ５６において、ストレージ・サーバ１０４は、受け取った暗号文ＣＦをデータベース１０６に格納する。ステップ５７においてストレージ・サーバ１０４は、ハッシュ・デーブルを、新しいハッシュ値Ｈ（ＣＦ）及びＣＦについての格納場所で更新する。ステップ５８において、次に、ストレージ・サーバ１０４は、その格納されたファイルＣＦへのリンクをクライアント・コンピュータ１０２に送り、動作は完了する。決定ブロック５５に戻り、一致が見つかった場合（「はい」分岐、決定ブロック５５）、同一の暗号化されたファイルＣＦが既にデータベース１０６内に格納されている。さらに、ステップ５９において、ストレージ・サーバ１０４は、データベース１０６内の前に格納された同一のファイルのアドレスへのリンクをクライアント・コンピュータ１０２に送り、ＣＦを再び格納する必要はない。
【００２０】
クライアント・コンピュータ１０２の各々は、上記のステップ５８又は５９において提供されるリンクにアクセスすることにより、ストレージ・サーバ１０４から後に取り出されたとき、対応する暗号文の復号を可能にするように、ファイルに対するクライアント鍵Ｋを格納する。クライアント鍵Ｋは、クライアント・コンピュータ１０２に格納することができ、又は遠隔位置に（例えば、ストレージ・サーバ１０４に）暗号化された形で格納することができ、クライアント・コンピュータ１０２により必要とされたときに取り出すことができる。一般に、各クライアント鍵Ｋは、鍵サーバ１０３の鍵ｋ及びそのクライアント鍵の下で暗号化されたファイルＦの決定性関数であるので、全てのクライアント・コンピュータ１０２が、同一のファイルに対して同一のクライアント鍵を取得することができ、同一のファイルに対して、同一の暗号文ＣＦが取得され、従って、ストレージ・サーバ１０４における重複排除、及び別のクライアント・コンピュータ１０２により格納される同一のファイルを１つのクライアント・コンピュータにより復号することが可能になる。しかしながら、単に短いハッシュでなく、ファイル自体の保有を証明し、クライアント鍵を取得できるので、ストレージ・サーバ１０４は、鍵サーバ１０３と共にクライアントとして参加することにより、クライアント鍵を取得することはできない。
【００２１】
別の実施形態において、ステップ５２において、暗号化されたファイルに対するハッシュ値Ｈ（ＣＦ）を、クライアント・コンピュータ１０２で計算し、暗号文ＣＦの代わりにストレージ・サーバ１０４に送ることができる。この実施形態において、ステップ５３は省略される。一致がない場合、ステップ５５において、一致する予め格納されたファイルが識別されない場合、ステップ５６において、ストレージ・サーバ１０４は、格納のために、クライアント・コンピュータ１０２から暗号化されたファイルＣＦを要求する。従って、ここで、暗号化されたファイルＣＦをストレージ・サーバに送るステップは、ステップ５５において一致が見出されないこととは独立しており、所定のファイルＦを暗号化する最初のクライアント・コンピュータのみが、ＣＦをストレージ・サーバ１０４に送る必要があることになる。
【００２２】
図４及び図５は、本発明の別の実施による、クライアント鍵を生成するための動作ステップを示すフローチャートである。図４のステップ６０〜６３は、図２のステップ３０〜３３に対応する。ステップ６４において、クライアント・コンピュータ１０２は、ｃ１に対して、第３のコミットメントｃ３における第１のコミットメントｃ１の、クライアント・コンピュータ１０２による知識を証明する、ΠＳ１で示される第１の部分証明（sub-proof）を生成する。ステップ６５において、クライアント・コンピュータ１０２は、第２及び第３のコミットメントｃ２、ｃ３が共通の値から計算されることを証明する、ΠＳ２で示される第２の部分証明を生成する。ここでの共通の値は、以下に例示されるようにｘ（ベクトル）の関数とすることができるが、両方のコミットメントを、同じベクトルｘ（ベクトル）から導出することができる。ステップ６６において、クライアント・コンピュータ１０２は、第２及び第３のコミットメントｃ２、ｃ３と共に、第１及び第２の部分証明ΠＳ１、ΠＳ２を、鍵サーバ１０３に送る。ステップ６７において、鍵サーバ１０３は、ｃ２及びｃ３に関する部分証明ΠＳ１、ΠＳ２を検証する。検証が失敗した場合（決定ブロック６８における「いいえ」）、ステップ６９において、鍵サーバ１０３はプロトコルをアボートし、動作が終了する。ステップ７０において、検証が成功すると（決定ブロック６８における「はい」）、鍵サーバ１０３は、位置インデックスｉ＝１〜ｎのサブセットＩ＝｛ｊ１，・・・ｊｔ｝を選択し、ここで、サブセットＩにおけるインデックスの数ｔは、セキュリティ及び効率の制約に基づいて所望のとおりに選択することができる。ステップ７１において、鍵サーバ１０３は、選択されたサブセットＩをクライアント・コンピュータ１０２に送る。サブセットＩを受信すると、クライアント・コンピュータ１０２は、ΠＳ３で示される第３の部分証明を生成する。この部分証明ΠＳ３は、サブセットＩ内の位置インデックスｉの各々について、第２のコミットメントｃ２におけるベクトルｘ（ベクトル）の位置ｉにおけるデータ・ブロックｘｉの知識を証明する。ステップ７３において、クライアント・コンピュータ１０２は、第３の部分証明ΠＳ３を鍵サーバ１０３に送る。ステップ７４において、鍵サーバ１０３は、ｃ２に関して部分証明ΠＳ３を検証する。
【００２３】
従って、この実施形態において、図２における知識の第１の証明Π１は、３つの部分証明ΠＳ１〜ΠＳ３により実施され、鍵サーバ１０３による第３の部分証明ΠＳ３の検証は、証明Π１の検証を完了させる。実際上、第１の部分証明ΠＳ１は、ｃ３の内容の知識を証明し、第２の部分証明ΠＳ２は、ｃ２及びｃ３の内容をリンクし、第３の部分証明ΠＳ３は、ｃ２（及び、従って、より早期の部分証明を介するｃ３）の基礎となるベクトルｘ（ベクトル）におけるファイル・ブロックの知識を証明する。ここでの３つの部分証明は、ファイル自体についてのいずれの情報も鍵サーバ１０３に明らかにすることなく、クライアント鍵が生成されるファイルの知識の必要な証明の効率的な実施を提供する。ΠＳ３の検証が失敗した場合（決定ブロック７５における「いいえ」）、鍵サーバ１０３はアボートし、動作が終了する。検証が成功した場合（決定ブロック７５における「はい」）、鍵サーバ１０３は、図４の鍵生成プロトコルに進む。
【００２４】
図５のステップ８０において、鍵サーバ１０３は、スキームの公開鍵／プライベート鍵のペア（ｅｐｋ、ｅｓｋ）の公開鍵ｅｐｋの下で、準同型暗号化スキーム（homomorphic encryption scheme、ＨＥＳ）を介して、その秘密鍵ｋを暗号化する。一般的に、準同型暗号化スキームは、準同型特性を有し、それにより、公開鍵ｅｐｋの下でメッセージｍを暗号化する暗号文Ｃ＝ＨＥＳ．Ｅｎｃｅｐｋ（ｍ）に対する効率的な演算
【数２】
0006959994.tif 000003
が存在し、Ｃ１∈ＨＥＳ．Ｅｎｃｅｐｋ（ｍ１）及びＣ２∈ＨＥＳ．Ｅｎｃｅｐｋ（ｍ２）の場合、群の演算「・」に関して、
【数３】
0006959994.tif 000004
となる。ステップ８１において、鍵サーバ１０３は、結果として得られる暗号化された鍵［ｋ］＝ＨＥＳ．Ｅｎｃｅｐｋ（ｋ）をクライアント・コンピュータ１０２に送る。ステップ８２において、クライアント・コンピュータ１０２は、暗号化スキームＨＥＳを介して公開鍵ｅｐｋの下で第１のコミットメントｃ１を暗号化し、暗号化されたコミットメント［ｃ１］＝ＨＥＳ．Ｅｎｃｅｐｋ（ｃ１）を生成する。別の実施形態において、公開鍵ｅｐｋは、一般的に鍵サーバ１０３により発行することができ、全てのクライアント・コンピュータ１０２に利用可能である。しかしながら、好ましい実施形態におけるセキュリティの強化のために、ステップ８０において、鍵のペア（ｅｐｋ、ｅｓｋ）は、鍵サーバにより新しく生成され、ステップ８１において、公開鍵ｅｐｋは、クライアント・コンピュータ１０２に送られる。ステップ８３において、次に、クライアント・コンピュータ１０２は、ノンス（nonce）Ｎを用いて、［ｋ］及び［ｃ１］の関数をブラインド化することにより、第１のコミットメントｃ１のブラインド関数Ｂを生成する。ステップ８４において、クライアント・コンピュータ１０２は、ブラインド関数Ｂ及び図４のステップ６６において送られた第３のコミットメントｃ３の両方における第１のコミットメントｃ１の知識を証明する第２の知識の証明Π２を計算する。ステップ８５において、クライアント・コンピュータ１０２は、Ｂ及びΠ２を鍵サーバ１０３に送る。ステップ８６において、鍵サーバ１０３は、Ｂ及びｃ３に関して第２の証明Π２を検証する。決定ブロック８７において検証が失敗した場合、ステップ８８において鍵サーバ１０３はアボートし、動作は終了する。Π２の検証が成功した場合、ステップ８９において、鍵サーバ１０３は、暗号化スキームＨＥＳの復号アルゴリズムＨＥＳ．Ｄｅｃを介して、公開鍵ｅｐｋに対応するプライベート（秘密）鍵ｅｓｋを用いて、ブラインド関数Ｂを復号し、復号された値Ｖ＝ＨＥＳ．Ｄｅｃｅｓｋ（Ｂ）を取得する。ステップ９０において、鍵サーバ１０３は、復号された値Ｖからブラインド鍵Ｋ´を生成する。暗号化スキームの準同型特性のため、ステップ８３において、結果として得られるブラインド鍵Ｋ´は、ｃ１及びブラインド関数Ｂを介して導入されたサーバ鍵ｋの、（ナンスＮを用いてブラインド化された）ブラインド関数を含む。これは、ブラインド鍵Ｋ´がｃ１及びｋのブラインド化された疑似ランダム関数（ＰＲＦ）を含む例において、以下でより詳細に示される。ステップ９１において、鍵サーバ１０３は、ブラインド鍵Ｋ´をクライアント・コンピュータ１０２に送る。最終的に、ステップ９２において、クライアント・コンピュータ１０２は、ナンスＮを用いてブラインド鍵Ｋ´を非ブラインド化することにより、クライアント鍵Ｋを取得する。従って、鍵サーバが、ベクトルｘ（ベクトル）又は最終的なクライアント鍵Ｋについてのいかなる情報も知ることなく、結果として得られるクライアント鍵が、サーバ鍵ｋ及びコミットメントｃ１（及び、従って、知識が証明されたベクトルｘ（ベクトル））の決定性関数として効率的に導出される。
【００２５】
上記のスキームの例示的な実施及び予備的概念の紹介が以下に詳細に説明される。
【００２６】
証明システム（ＰｏＫ）：
ＰｏＫ｛（ｗ）：ステートメント（ｗ）｝は、ステートメント（ｗ）が真であるような証拠（witness）ｗの知識の一般的な対話式ゼロ知識証明プロトコルを示す。ＰｏＫシステムは、完全性（completeness）、ゼロ知識（zero-knowledge）及びシミュレーション健全抽出可能性（simulation-sound extractability）を実現する。ＰｏＫシステムは、２つのプロトコルＰＫ．Ｓｅｔｕｐ及びＰＫ．Ｐｒｏｖｅから構成することができる。セキュリティ・パラメータ１λの入力時、ＰＫ．Ｓｅｔｕｐ（１λ）は、（ｐａｒＰＫ）を出力する。ＰＫ．Ｐｒｏｖｅ（ｐａｒＰＫ，・）は、ステートメント（ｗ）が真であることの証明者（prover）と検証者（verifier）との間の対話型プロトコルである。証明者が保持する付加的な入力は、ステートメントに対する証拠ｗである。
【００２７】
ＰｏＫ（すなわち、一般化されたシュノア署名証明（Schnorr-signature proof）、非特許文献１を参照されたい）の具体的実現のために、非特許文献２に記載されるような、
【数４】
0006959994.tif 000005
のような、表記が用いられる。
【００２８】
コミットメント・スキーム（ＣＳ）
正当性（correctness）、秘匿性（hiding property）及び拘束性（binding property）を満たす、ペデルセン・コミットメント（Pedersen  commitment）を用いるＣＳをインスタンス化することができる。さらに、ペデルセン・コミットメントは準同型である。コミットメント・スキームは、使用される他のプリミティブと両立性のある合成位数群（composite order group）においてインスタンス化することができる。
【００２９】
ＣＳ．Ｓｅｔｕｐ（１λ）：セットアップ・アルゴリズムは、ｇｃｄ（ｐ−１，ｑ−１，７）＝１となるように、２つのλビットの安全素数ｐ，ｑを選択し、Ｎ＝ｐｑを設定し、メッセージ空間及びランダムネス空間をそれぞれ：
【数５】
0006959994.tif 000006
として設定する。次に、アルゴリズムは、ρ＝２ｋＮ＋１となるように素数ρを選び、ここでｋは、小さい素数である。
【数６】
0006959994.tif 000007
は、群
【数７】
0006959994.tif 000008
の位数Ｎの部分群（subgroup）とし、ここで、Ｇ及びＨは、
【数８】
0006959994.tif 000009
の２つの乱数生成器であり、ｌｏｇＨＧは未知である。
【数９】
0006959994.tif 000010
は、位数Ｎの
【数１０】
0006959994.tif 000011
の循環部分群であり、全ての演算は、ｍｏｄ  ρを生じる（すなわち、指数においてｍｏｄ  Ｎ簡約される）。最終的に、アルゴリズムは、公開パラメータ
【数１１】
0006959994.tif 000012
を出力する。
【００３０】
ＣＳ．Ｃｏｍｍｉｔ（ｐａｒ，ｍ，ｒ）：ｃｏｍ←ＧｍＨｒ  ｍｏｄ  ρを計算する。（ｃｏｍ，ｏｐｅｎ＝ｒ）を出力する。
【００３１】
ＣＳ．Ｖｅｒｉｆｙ（ｐａｒ，ｃｏｍ，ｍ，ｏｐｅｎ）：ｃｏｍ←ＧｍＨｏｐｅｎ  ｍｏｄ  ρの場合、１を出力する。他の場合には、０を出力する。
【００３２】
疑似ランダム関数（ＰＲＦ）：
素数位数群の代わりに合成位数群上でインスタンス化された、Ｂｏｎｅｈ−Ｂｏｙｅｎ予測不能関数（非特許文献３）に基づく、Ｄｏｄｉｓ−Ｙａｍｐｏｌｓｋｉｙ（非特許文献４）のＰＲＦスキームの変形である、非特許文献５及び非特許文献６に記載されているとおりのＰＲＦスキームを用いることができる。このＰＲＦは、部分群の秘匿にのみに基づいた任意のサイズの領域についてセキュアであることが証明されている。素数位数群によりインスタンス化されたオリジナルのＰＲＦについての証明は、セキュリティ・パラメータにおける多項式サイズである領域についてのみ考慮されている。この実施形態においては、実直だが物見高い（honest-but-curious）鍵サーバによるオフラインのブルート・フォース・アタック（総当たり攻撃、Brute Force Attack）を可能にしないように、任意のサイズの領域である。以下のＰＲＦ定義を参照されたい。
【００３３】
ＰＲＦ．Ｓｅｔｕｐ（１λ）：セキュリティ・パラメータλの入力時、セットアップ・アルゴリズムは、２つのλビットの安全素数ｐ，ｑを選択し、Ｎ＝ｐｑを設定し、次に群
【数１２】
0006959994.tif 000013
を生成し、ここで、
【数１３】
0006959994.tif 000014
は、
【数１４】
0006959994.tif 000015
の部分群である。１つの実施形態において、群
【数１５】
0006959994.tif 000016
の候補は、合成位数の双線形群の効率的なペアリング又はターゲット群のない、合成位数の楕円曲線群とすることができる。最終的に、セットアップ・アルゴリズムは、
【数１６】
0006959994.tif 000017
を選び、
【数１７】
0006959994.tif 000018
を設定し、
【数１８】
0006959994.tif 000019
を出力する。
【００３４】
ＰＲＦ．ＫｅｙＧｅｎ（１λ、ｐａｒ）：セキュリティ・パラメータ及び公開パラメータλ、ｐａｒの入力時、鍵生成アルゴリズムは、ｋ←Ｋを選び、ｋを出力する。
【００３５】
ＰＲＦ．Ｅｖａｌｕａｔｅ（ｐａｒ，ｋ，ｍ）：公開パラメータｐａｒ、鍵ｋ∈Ｋ及び入力ｍ∈Ｄの入力時、評価アルゴリズムは、以下を行う。：ｇｃｄ（（ｋ＋ｍ），Ｎ）≠１の場合、
【数１９】
0006959994.tif 000020
を出力し（ここで、
【数２０】
0006959994.tif 000021
は、エラー記号を示す）、他の場合には、
【数２１】
0006959994.tif 000022
を出力する。
【００３６】
準同型暗号スキーム（ＨＥＳ）：
Ｐｒｏｊｅｃｔｉｖｅ  Ｐａｉｌｌｉｅｒ暗号スキームは、非特許文献７及び非特許文献８において提案される。このスキームは、Ｐａｉｌｌｉｅｒ暗号の準同型特性を保持するが、公開鍵の密なセットを有する。
【００３７】
ＨＥＳ．Ｓｅｔｕｐ（１λ）：セキュリティ・パラメータλの入力時、セットアップ・アルゴリズムは、２つのλビットの安全素数ｐ，ｑを選択し、Ｎ＝ｐｑを設定する。（こうしたＮは、非特許文献９に記載されるように、分散方式で生成され得る。）次に、セットアップ・アルゴリズムは、ランダム要素
【数２２】
0006959994.tif 000023
を生成し、
【数２３】
0006959994.tif 000024
、位数Ｎの特別な要素を設定する。最終的に、アルゴリズムは、
【数２４】
0006959994.tif 000025
を出力する。
【００３８】
ＨＥＳ．ＫｅｙＧｅｎ（ｐａｒ）：公開パラメータｐａｒの入力時、鍵生成アルゴリズムは、ランダムｔ∈［Ｎ／４］を選び、ｅｐｋ←ｇｔ  ｍｏｄ  Ｎ２を計算する。最終的に、アルゴリズムは、
【数２５】
0006959994.tif 000026
を出力する。
【００３９】
ＨＥＳ．Ｅｎｃ（ｅｐｋ，ｍ）：公開鍵ｅｐｋ及びメッセージｍの入力時、暗号アルゴリズムは、ランダムｒ∈［Ｎ／４］を選び、ｕ←ｇｒ  ｍｏｄ  Ｎ２；ｖ←ｅｐｋｒｈｍ  ｍｏｄ  Ｎ２を計算する。最終的に、アルゴリズムは、暗号文
【数２６】
0006959994.tif 000027
を出力する。幾つかの実施形態において、［ｍ］は、ｍの暗号を意味するように用いられる。
【００４０】
ＨＥＳ．Ｄｅｃ（ｅｓｋ，ｃｔ）：秘密鍵ｅｓｋ及び暗号文ｃｔの入力時、暗号アルゴリズムは、ｍ´←ｖ／ｕｅｓｋ  ｍｏｄ  Ｎ２を計算する。幾つかのｎ∈［Ｎ］において、ｍ´が形式（１＋Ｎｍ  ｍｏｄ  Ｎ２）のものである場合、ｍを出力する。さもなければ、
【数２７】
0006959994.tif 000028
を出力する。
【００４１】
衝突困難ハッシュ関数（Collision Resistant Hash Function、ＣＲＨＦ）：
関数
【数２８】
0006959994.tif 000029
のファミリーは、ランダムな
【数２９】
0006959994.tif 000030
の入力時に、２つの異なる入力ｘ≠ｙで
【数３０】
0006959994.tif 000031
となるものを（セキュリティ・パラメータにおいて無視できるほどの可能性を有する場合を除き）見つける効率的なアルゴリズムない場合、衝突困難である。ＣＲＨＦは、非特許文献１０に記載されるように実施され得る。
【００４２】
マークル・ハッシュ木（Merkle Hash Tree、ＭＨＴ）：
マークル・ハッシュ木（非特許文献１１を参照されたい）は、ベクトル全体をオープンすることなく、ベクトル内の個々の値をオープンし、後で検証が可能になるように、簡潔なコミットメントをベクトルに提供する。ベクトル
【数３１】
0006959994.tif 000032
が与えられた場合、ＭＨＴは、次のようにその上に構成される：値をペアにし、次に、ＣＲＨＦを用いて各ペアをハッシュする。次に、ハッシュ値を再びペアにし、各ペアをさらにハッシュし、このプロセスは、単一のハッシュ値のみが残るまで繰り返される。これは、ベクトルのブロックに対応する葉及び最後の残りのハッシュ値に対応する根を有する二分木をもたらす。根は、ｘ（ベクトル）に対するコミットメントとして働き、後で、オープニングを根に対して検証することができるように、個々の位置をオープンすることができる。
【００４３】
ベクトル・コミットメント（ＶＣ）：
ベクトル・コミットメント（非特許文献１２を参照されたい）は、後でメッセージの１つに対するコミットメントをオープンする（すなわち、ｘｉが、実際に、ベクトルｘ（ベクトル）におけるｉ番目の値であることを証明する証拠を提供する）ことが可能となるように、メッセージのベクトルにコミットすることを可能にする。コミットメント及びオープニングのサイズは、ベクトルの長さと無関係である。この実施形態において、効率要件は、ＶＣにより修正される。例えば、ｎを、コミットされたベクトルの長さとする。従って、コミットメントのサイズは、ｎとは無関係であることが要求されるが、オープニングのサイズは、ｎを下回らなければならない、すなわち、ｏ（ｎ）である。ＶＣは、非秘匿（ＮＨＶＣ）又は秘匿（ＨＶＣ）のいずれかとすることができる。ＮＨＶＣの場合、セキュリティ要件は、拘束性である。別の言い方をすれば、この特性は、ひとたび攻撃者がＶＣを思い付くと、そのＶＣについての同じ位置に関して２つの異なる値を証明することはできないことを要求する。ＨＶＣの場合、秘匿は、付加的なセキュリティ要件である。別の言い方をすれば、この要件は、ＶＣが、コミットされたベクトルを隠すべきである（すなわち、攻撃者は、ＶＣが、ベクトル
【数３２】
0006959994.tif 000033
に対して作成されたか、又はベクトル
【数３３】
0006959994.tif 000034
に対して作成されたかを識別できてはならず、ここで、
【数３４】
0006959994.tif 000035
である）ことを規定する。標準的なコミットメントに関しては秘匿が定められる。
【００４４】
アルゴリズムへの入力の大部分は、ＨＶＣ及びＮＨＶＣにおいて共通である。ＨＶＣのために排他的に必要とされ得る入力を、以下により詳細に説明する。
【００４５】
ＶＣ．Ｓｅｔｕｐ（１λ，ｎ）：セキュリティ・パラメータ１λ及びベクトルのサイズにおける上界ｎの入力時、メッセージ空間
【数３５】
0006959994.tif 000036
の記述及びランダムネス空間
【数３６】
0006959994.tif 000037
の記述を含む、コミットメント・スキームのパラメータｐａｒを生成する。
【００４６】
【数３７】
0006959994.tif 000038
公開パラメータｐａｒ及びベクトル
【数３８】
0006959994.tif 000039
の入力時、アルゴリズムは、ｘ（ベクトル）に対するコミットメントを出力する。
【００４７】
【数３９】
0006959994.tif 000040
公開パラメータｐａｒ、位置インデックスｉ、及びベクトルｘ（ベクトル）の入力時、アルゴリズムは、ｘｉに関する証拠ｗを生成し、（ｗ，ｘｉ）を出力する。
【００４８】
ＶＣ．Ｖｅｒｉｆｙ（ｐａｒ，ｉ、ｃｏｍ、ｗ，ｘ）：公開パラメータｐａｒ、位置インデックスｉ、コミットメントｃｏｍ、及びｘに対する証拠ｗの入力時、アルゴリズムは、ｗが、位置ｉにおけるｘに関する有効な証拠である場合、１を出力し、他の場合には０を出力する。
【００４９】
以下に２つのアルゴリズム（ＶＣ．ＲａｎｄＣｏｍｍｉｔｍｅｎｔ，ＶＣ．ＲａｎｄＷｉｔｎｅｓｓ）が定められる。ＶＣ．ＲａｎｄＣｏｍｍｉｔｍｅｎｔは、ＮＨＶＣをＨＶＣに更新するのを可能にし、ＶＣ．ＲａｎｄＷｉｔｎｅｓｓは、ＮＨＶＣ証拠をＨＶＣのものに更新するのを可能にする。
【００５０】
ＶＣ．ＲａｎｄＣｏｍｍｉｔｍｅｎｔ（ｐａｒ，ｃｏｍ，ｒ）：公開パラメータｐａｒ、非秘匿コミットメントｃｏｍ及び
【数４０】
0006959994.tif 000041
の入力時、ＨＶＣ  ｃｏｍ´を出力する。
【００５１】
ＶＣ．ＲａｎｄＷｉｔｎｅｓｓ（ｐａｒ，ｃｏｍ，ｉ，ｒ，ｗ）：公開パラメータｐａｒ、ＮＨＶＣ証拠ｗ、非秘匿コミットメントｃｏｍ及び
【数４１】
0006959994.tif 000042
の入力時、ＨＶＣ証拠ｗ´を出力する。
【００５２】
プロトコル：
プロトコルは、信頼できるＣＲＳ（共通参照文字列、Common Reference String）モデルにおいて設計され、各パーティ、すなわち鍵サーバ１０３（ＫＳ）及びクライアント・コンピュータ１０２（Ｃｉ）は、信頼できるパーティからスキームの公開パラメータを受け取る。鍵サーバ１０３は、付加的に、ＰＲＦに対する鍵を選ぶ。
【００５３】
プロトコルは、２つの主なビルディング・ブロック、すなわちＶＣ及びＰＲＦを有する。この実施形態において、ＫＳがＣｉの入力ファイルに対して生成するクライアント鍵は：（１）鍵はランダムであるべきである、従って、攻撃者により推測するのが困難であるが、（２）ステートレスであるにもかかわらず、ファイルに対して一意であるべきである（すなわち、ＫＳは、同じファイルに対して同じ鍵を生成できなければならない）、及び（３）鍵は、公に（publicly）計算可能であってはならない（すなわち、秘密情報を保有するＫＳのみが、ファイルに対する鍵を計算できなくてはならない）。ここでは、これらの特性の全ては、ベクトルｘ（ベクトル）に対する簡潔な非秘匿及び拘束コミットメントに対するＰＲＦ評価をクライアント鍵に行うことにより提供される。この短いコミットメントは、ｓで示される。
【００５４】
ＫＳはＣｉの入力についての情報を知るべきではないので、ＰＲＦ評価は、オブリビアスに行うことができる。この実施形態において、ＰＲＦに関するＫＳ(ｋを保持する)とＣｉ（ｓを保持する）との間のオブリビアスなＰＲＦ評価プロトコルが上述された。さらに、プロトコルのこの部分は、上述の準同型暗号化スキームＨＥＳを利用することができる。１つの実施形態において、Ｃｉは悪意のあるものであり得る。従って、ＰＲＦの計算においてＫＳが関与する前に、Ｃｉがその入力ｓにコミットし、そのオープニングの知識（ＰｏＫ  Π２）を証明することを保証するのは有益であり得る。
【００５５】
ＶＣの特性を利用して、クライアントが、ｓのプリイメージ（preimage）の知識を効率的に証明することが可能になる。ＶＣは、Ｃｉにプリイメージの幾つかのランダム位置の知識を証明させる。この実施形態において、この特性は、Ｃｉがその入力のｔ個のランダム位置の知識を証明することをＫＳにチャレンジさせることにより利用され、ここで、ｔは、ｘ（ベクトル）の長さｎよりずっと小さいものであり得る。ｔの値の決定は、所定のプロトコルに対して受容できる健全性（soundness）エラーに依存する。
【００５６】
構成
Ｓｅｔｕｐ：セットアップ要求Ｓｅｔｕｐ及びＳｅｔｕｐの特定の呼び出しについてのセットアップｉｄ  ｓｉｄの受信時、ＫＳは以下を実行する：
１．信頼できるソースから（ｐａｒ）を受け取り、ここで、ｐａｒ＝（ｐａｒＰＲＦ，ｐａｒＶＣ，ｐａｒＣＳ，ｐａｒＰＫ，ｐａｒＨＥＳ）、すなわち、上記のＰＲＦ．Ｓｅｔｕｐ、ＣＳ．Ｓｅｔｕｐ、ＰＫ．Ｓｅｔｕｐ及びＨＥＳ．Ｓｅｔｕｐにおけるｐａｒである。（これらの選択されたスキームにおいて、これらは全て、共有パラメータを有する同じ設定で機能する。表記を簡単化するために、使用されるプリミティブが文脈から明白である場合、そのプリミティブの特定のパラメータではなく、ｐａｒが参照され得る。）
２．ｋ←ＰＲＦ．ＫｅｙＧｅｎ（１λ，ｐａｒ）を実行し、ｋを格納する。
３．（Ｓｅｔｕｐ，ｓｉｄ）を出力する。
【００５７】
Ｅｖａｌｕａｔｅ（評価する）：Ｃｉにおける
【数４２】
0006959994.tif 000043
（ここで、ｑｉｄは、Ｅｖａｌｕａｔｅの特定の呼び出しについてのクエリ識別子である）の受信時、ＣｉとＫＳとの間で以下のプロトコルが実行される。
１．信頼できるソースから、（ｐａｒ）＝（ｐａｒＰＲＦ，ｐａｒＶＣ，ｐａｒＣＳ，ｐａｒＰＫ，ｐａｒＨＥＳ）を受け取る。
２．Ｃｉは、ランダム
【数４３】
0006959994.tif 000044
を選び、
【数４４】
0006959994.tif 000045
を計算する。
付加的に、Ｃｉは、以下を行う：
（ａ）ランダム
【数４５】
0006959994.tif 000046
を選ぶ。
（ｂ）ｃｏｍ←ＣＳ．Ｃｏｍｍｉｔ（ｐａｒ，ｓ，ｒ２）を計算する。
（ｃ）次に、Ｃｉは、以下の知識の証明
【数４６】
0006959994.tif 000047
を生成する。
（ｄ）付加的に、Ｃｉは、以下の知識の証明
【数４７】
0006959994.tif 000048
を計算し、（ｓ´，ｃｏｍ，Πｓ１，Πｓ２）をＫＳに送る。
３．ＫＳは、Πｓ１及びΠｓ２を検証する。検証が成功した場合、次に、ＫＳは次のステップに進む。
４．ＫＳは、［１，ｎ］からインデックスのサブセットＩ＝｛ｊ１，．．．ｊＩ｝をランダムに選び、ＩをＣｉに送る。
５．各チャレンジ・インデックス（challenged index）ｊ∈Ｉについて、Ｃｉは、
【数４８】
0006959994.tif 000049
を計算し、以下の知識の証明
【数４９】
0006959994.tif 000050
を生成する。Πｓ３＝｛πｊ｜ｊ∈Ｉ｝とする。Ｃｉは、Πｓ３をＫＳに送り返す。
６．ＫＳは、Πｓ３を検証し、検証が成功した場合、ＫＳは、次のステップに進む。
７．ＫＳは、（ｅｐｋ，ｅｓｋ）←ＨＥＳ．ＫｅｙＧｅｎ（ｐａｒ）を選び、
［ｋ］←ＨＥＳ．Ｅｎｃ（ｅｐｋ，ｋ）を計算し、（ｅｐｋ，［ｋ］）をＣｉに送る。
８．次に、Ｃｉは、
【数５０】
0006959994.tif 000051
を選び、
【数５１】
0006959994.tif 000052
を計算し、ここで、［ｓ］←ＨＥＳ．Ｅｎｃ（ｅｐｋ，ｓ）である。
９．次に、Ｃｉは、以下の知識の証明
【数５２】
0006959994.tif 000053
を生成し、Ｃｉは、（ｃｔ，Π２）をＫＳに送る。
１０．ＫＳは、Π２を検証し、検証が成功した場合、ＫＳは続行する。
１１．ＫＳは、Ｖ←ＨＥＳ．Ｄｅｃ（ｅｓｋ、ｃｔ）を計算する。
１２．次に、ＫＳは、
【数５３】
0006959994.tif 000054
を計算し、Ｋ´をＣｉに送る。
１３．
【数５４】
0006959994.tif 000055
の場合、
【数５５】
0006959994.tif 000056
を出力する。他の場合には、
【数５６】
0006959994.tif 000057
を計算し、Ｋを出力する（ランダムネスｒ３は、この構成において選択されるような適切な値域を有する代数ＰＲＦを用いてここで打ち消される）。
【００５８】
上記の構成において、コミットメントｓ、ｓ´及びｃｏｍは、それぞれ、図４及び図５における第１、第２、及び第３のコミットメントｃ１、ｃ２及びｃ３に対応し、ランダム値ｒ３は、これらの図におけるノンスＮに対応する。第２の部分証明Πｓ２は、ｃ２及びｃ３が、ｃ１である共通の値から計算されることを証明する。ここでの準同型暗号スキームＨＥＳは加法準同型スキームであり、そのため、Ｃ１＝ＨＥＳ．Ｅｎｃｅｐｋ（ｍ１）及びＣ２＝ＨＥＳ．Ｅｎｃｅｐｋ（ｍ２）の場合、
【数５７】
0006959994.tif 000058
であり、ここで、
【数５８】
0006959994.tif 000059
は、ここでは乗算に対応する。従って、ステップ８において：
【００５９】
【数５９】
0006959994.tif 000060
であり、そのため、ステップ１１において、Ｖ＝ｒ３（ｋ＋ｓ）である。ステップ１２において、
【数６０】
0006959994.tif 000061
であり、そのため、ステップ１３において、
【数６１】
0006959994.tif 000062
であり、先に定められたＰＲＦに対応する。鍵サーバ１０３は、ベクトルｘ（ベクトル）又は最終的なクライアント鍵Ｋについて何も知らず、クライアントは、サーバ鍵ｋについての情報を入手しない。
【００６０】
パラメータｔは、効率と引き換えに通信帯域幅を与える調整パラメータである。このパラメータを所望の通りに設定し、証明者（すなわち、クライアント）がファイル全体を保有する所望の信頼度を与えることができる。健全性エラーを最小にするために、最初にクライアント・ファイルＦを消失コード化し、消失コード化されたファイルをｎ個のブロックに分割することによりベクトルｘ（ベクトル）を定める。消失コードが、ビットのαの割合まで消失を復元でき、
【数６２】
0006959994.tif 000063
が、所望の健全性限界である場合、ｔは、
【数６３】
0006959994.tif 000064
となる最小の整数として選ぶことができる。
【００６１】
上記の構成に基づいて、実施形態で用いるためのベクトル・コミットメント・スキームの２つの例は、以下の通りである。
【００６２】
マークル木（Merkle Tree）ベースのベクトル・コミットメント
このＶＣスキームは、非特許文献１０に提示されるアキュムレータ構成に基づく。１つの実施形態において、構成に基づき、同じマークル・ハッシュ木（ＭＨＴ）を用いることができるが、葉のインデックス位置を隠し、効率を向上させる必要はない。
【００６３】
ＶＣ．Ｓｅｔｕｐ（１λ，ｎ）：セキュリティ・パラメータ１λ及び上界ｎの入力時、アルゴリズムは、ＣＳ．Ｓｅｔｕｐ（１λ）を呼び出す。ＣＳ．Ｓｅｔｕｐ（１λ）は、
【数６４】
0006959994.tif 000065
を返すものとする。このアルゴリズムは、
【数６５】
0006959994.tif 000066
として定められる衝突困難ハッシュ関数
【数６６】
0006959994.tif 000067
によりタプルを追加し、それをｐａｒとして返す。
【００６４】
【数６７】
0006959994.tif 000068
公開パラメータｐａｒ及び入力
【数６８】
0006959994.tif 000069
の入力時、アルゴリズムは、
【数６９】
0006959994.tif 000070
を用いて、ｘ（ベクトル）に対してマークル・ハッシュ木を再帰的に構築する。（ｎが２の累乗ではない場合、ｎが２の完全累乗になるまで「ダミー」要素をｘ（ベクトル）に挿入する。ＭＲは、ＭＨＴの根とする。アルゴリズムは、コミットメントｃｏｍ＝ＭＲを出力する。
【００６５】
【数７０】
0006959994.tif 000071
公開パラメータｐａｒ、位置インデックスｉ、及び入力
【数７１】
0006959994.tif 000072
）
の入力時、アルゴリズムは、以下を行う。ＭＨＴにおける、値ＭＲを有する根ノードから、値ｘ［ｉ］を有する葉ノードまでの経路に沿ったノード値を、
【数７２】
0006959994.tif 000073
として示すものとする。
【数７３】
0006959994.tif 000074
であることに留意されたい。
【数７４】
0006959994.tif 000075
は、
【数７５】
0006959994.tif 000076
の兄弟経路とする（ｐ０は、兄弟を有さないことに留意されたい）。次に、アルゴリズムは、
【数７６】
0006959994.tif 000077
を計算し、証拠
【数７７】
0006959994.tif 000078
を出力する。
【００６６】
ＶＣ．Ｖｅｒｉｆｙ（ｐａｒ，ｉ，ｃｏｍ，ｗ，ｘ）：公開パラメータｐａｒ、位置インデックスｉ、コミットメントｃｏｍ＝ＭＲ、及び証拠（ｗ，ｘ）の入力時、アルゴリズムは、ｗを
【数７８】
0006959994.tif 000079
として解釈し、ｐｄ＝ｘを設定する。各々のｊ＝ｄ，．．．，１について、アルゴリズムは、左右の子をハッシュすることにより、内部ノードを再帰的に計算する。
【数７９】
0006959994.tif 000080
とする（ｐ１が左の兄弟である場合、他の場合には、
【数８０】
0006959994.tif 000081
である）。このアルゴリズムは、ＭＲ＝ｐ０であるかどうかをチェックする。アルゴリズムは、等しさが成り立つ場合、１を出力し、他の場合には、０を出力する。ＮＨＶＣ実現のために、ｗを、
【数８１】
0006959994.tif 000082
として解釈しなければならない。ステップの残りは同じままである。最後のステップにおいて、ＭＲ＝ｐ０であるかどうかをチェックする代わりに、アルゴリズムは、ＣＳ．Ｖｅｒｉｆｙ（ｐａｒ，ｃｏｍＭＲ，ＭＲ，ｏｐｅｎＭＲ）＝１であるかどうかをチェックすることになる。アルゴリズムは、等しさが成り立つ場合、１を出力し、他の場合には０を出力する。
【００６７】
ＶＣ．ＲａｎｄＣｏｍｍｉｔｍｅｎｔ（ｐａｒ，ｃｏｍ，ｒ）：公開パラメータｐａｒ、非秘匿ベクトル・コミットメントｃｏｍ＝ＭＲ、及びランダムネス
【数８２】
0006959994.tif 000083
の入力時、アルゴリズムは、ＣＳ．Ｃｏｍｍｉｔ（ｐａｒ，ＭＲ，ｒ）を呼び出す。ＣＳ．Ｃｏｍｍｉｔ（ｐａｒ，ＭＲ，ｒ）は、（ｃｏｍＭＲ，ｏｐｅｎＭＲ）を返すものとする。ｃｏｍ´＝ｃｏｍＭＲを出力する。
【００６８】
ＶＣ．ＲａｎｄＷｉｔｎｅｓｓ（ｐａｒ，ｃｏｍ，ｉ，ｒ，ｗ）：公開パラメータｐａｒ、非秘匿ベクトル・コミットメントｃｏｍ＝ＭＲ、位置ｉ、ランダムネス
【数８３】
0006959994.tif 000084
及び部分証拠ｗの入力時、アルゴリズムは、ｗを
【数８４】
0006959994.tif 000085
として解釈し、（ｃｏｍＭＲ，ｏｐｅｎＭＲ）をｗに付加し、ここで、（ｃｏｍＭＲ，ｏｐｅｎＭＲ）＝ＣＳ．Ｃｏｍｍｉｔ（ｐａｒ，ＭＲ，ｒ）であり、
【数８５】
0006959994.tif 000086
を出力する。
【００６９】
マークル木ベースのベクトル・コミットメントについての知識の証明
本実施形態において、３つの付随するＰｏＫを、効率的に実施することを必要とすることがある。全てのＰｏＫの完全な実施は、以下により詳細に説明される。ここで説明されるのは、証明であり、これは、このＶＣインスタンス化のために回避することができ、より多くの配慮を必要とする。ＶＣ．ＲａｎｄＣｏｍｍｉｔｍｅｎｔは、ＮＨＶＣ、ＭＲに対するＰｅｄｅｒｓｅｎコミットメント・スキームを計算するＣＳ．Ｃｏｍｍｉｔアルゴリズムと同じである。従って、Πｓ２は、等しさの標準的な証明にすぎないことになる。実際に、以下の最適化を行うことができ：プロトコル全体にわたってｓ´をｃｏｍとして使用し、Πｓ２をスキップする。例えば、証明πｊについては：
ＰｏＫ｛（ｗ´，ｘ）：１＝ＨＶＣ．Ｖｅｒｉｆｙ（ｐａｒ，ｊ，ｃｏｍ，ｗ´，ｘ）｝
であり、これらの関連の証明はより複雑であり、以下のステップを必要とすることを証明する。
【００７０】
１．アルゴリズムは、ｗ´を
【数８６】
0006959994.tif 000087
として解釈する。
【００７１】
２．ＭＨＴにおける、値ＭＲを有する根ノードから、値ｘｉを有する葉ノードまでの経路に沿ったノード値が、
【数８７】
0006959994.tif 000088
として示される。アルゴリズムは、
【数８８】
0006959994.tif 000089
を用いて、この経路をボトムアップ式に再帰的に回復する。各ステップにおいて、インデックス位置ｊは、左の子及び右の子を一意に決定する。
【００７２】
３．次に、アルゴリズムは、この経路におけるあらゆる値ｐｊ及びＭＨＴにおけるｐｉの左及び右の子の値にコミットする、すなわち、ｌｊを左の子とし、ｒｊを右とするとき、アルゴリズムは、
【数８９】
0006959994.tif 000090
を計算する。
【００７３】
次に、アルゴリズムは、Ｐ０が、実際、根に対するコミットメントである証明を生成する（明確にするために、ＣＳ．Ｃｏｍｍｉｔの出力におけるｏｐｅｎは無視する。）：
【数９０】
0006959994.tif 000091
【００７４】
５．次に、ｊ＝０，．．．，ｄ−１について、以下の知識の証明は、各トリプレット（Ｐｊ、Ｌｊ、Ｒｊ）が適格である（well-formed）ことを証明する。Ｌｊ（又は、Ｒｊ）は、Ｐｊ＋１として用いられることに留意されたい。
【数９１】
0006959994.tif 000092
【００７５】
この証明は、以下のサブステップを必要とする。
（ａ）この証明は、Ｐｅｄｅｒｓｅｎコミットメント・スキームの準同型特性、及び２つの値の乗算のためのＰｏＫｍｕｌｔのためのサブプロトコルを使用する。このプロトコルは、標準的な技術を用いてインスタンス化され、それは、次のようにＰｏＫｍｕｌｔにより簡潔に表される。
【数９２】
0006959994.tif 000093
（ｂ）証明者は、
【数９３】
0006959994.tif 000094
及び
【数９４】
0006959994.tif 000095
を計算する。
（ｃ）証明者は、以下のトリプレットの各々に対するＰｏＫｍｕｌｔを呼び出し、コミットメントの正当性を証明する。：
【数９５】
0006959994.tif 000096
（ｄ）検証者は、
【数９６】
0006959994.tif 000097
として
【数９７】
0006959994.tif 000098
を用いて（準同型性を用いて）、
【数９８】
0006959994.tif 000099
を計算することができる。
（ｅ）証明者は、全てのこれらのコミットメント及びＰｏＫｍｕｌｔを検証者に送る。
【００７６】
６．ｄ＝ｌｏｇ  ｎは、ＭＨＴの深さとする。完全証明は、コミットメントのセット
【数９９】
0006959994.tif 000100
、前のサブステップにおける１０ｄ補助コミットメント、及び８ｄ＋１  ＰｏＫから成る。証明の全体のサイズは、０（ｄ）＝０（ｌｏｇ  ｎ）である。ＰｏＫｊごとの１０コミットメント及び８  ＰｏＫｍｕｌｔは、表記ＰｏＫｊ内に吸収されることに留意されたい。
【００７７】
ＲＳＡベースのベクトル・コミットメント
このスキームは、（１）コミットメント・スキームが秘匿するように構成される、及び（２）値及び証拠を直接提供する代わりに、ｉ番目のインデックスを証明するＰｏＫが付加される、という２つの主な変更を伴う、非特許文献１３に提示されるＲＳＡベースの非秘匿ＶＣスキームに基づいている。
【００７８】
ＶＣ．Ｓｅｔｕｐ（１λ，ｎ）：セキュリティ・パラメータ１λ及び上界ｎの入力時、アルゴリズムは、以下を行う：
１．２つのλビットの安全素数ｐ＝２ｐ´＋１及びｑ＝２ｑ´＋１を選び、Ｎ＝ｐｑを設定する。
２．メッセージの長さ上の上界であるｌ＝ｐｏｌｙ（λ）を選ぶ。
３．φ（Ｎ）を割り切らないｎ個のｌ＋１６１８ビット素数をｅ１，．．．，ｅｎを選択する。
４．ランダムな
【数１００】
0006959994.tif 000101
を選ぶ。
５．ｊ＝１〜ｎについて、
【数１０１】
0006959994.tif 000102
を計算する。
６．
【数１０２】
0006959994.tif 000103
を設定する。
７．パラメータ
【数１０３】
0006959994.tif 000104
を出力する。
【００７９】
【数１０４】
0006959994.tif 000105
公開パラメータｐａｒ及び入力ｘ（ベクトル）＝（ｘ１，．．．，ｘｎ）の入力時、アルゴリズムは、
【数１０５】
0006959994.tif 000106
を計算し、コミットメントｃｏｍを出力する。
【００８０】
【数１０６】
0006959994.tif 000107
公開パラメータｐａｒ、位置ｉ、及びｘ（ベクトル）＝（ｘ１，．．．，ｘｎ）の入力時、アルゴリズムは、
【数１０７】
0006959994.tif 000108
を計算し、証拠（ｗ，ｘｉ）を出力する。
【００８１】
ＶＣ．Ｖｅｒｉｆｙ（ｐａｒ，ｉ，ｃｏｍ，ｗ，ｘ）：公開パラメータｐａｒ、位置ｉ、コミットメントｃｏｍ、及び証拠（ｗ，ｘ）の入力時、アルゴリズムは、
【数１０８】
0006959994.tif 000109
の場合１を出力し、他の場合には０を出力する。検証アルゴリズムは、アルゴリズムが、ｃｏｍの代わりに、ｃｏｍ´を入力として利用することを除いて、ＨＶＣ及びＮＨＶＣの両方に対して同じである。
【００８２】
ＶＣ．ＲａｎｄＣｏｍｍｉｔｍｅｎｔ（ｐａｒ，ｃｏｍ，ｒ）：公開パラメータｐａｒ、非秘匿ベクトル・コミットメントｃｏｍ及びランダムネス
【数１０９】
0006959994.tif 000110
の入力時、アルゴリズムは、
【数１１０】
0006959994.tif 000111
を計算し、ｃｏｍ´を出力する。
【００８３】
ＶＣ．ＲａｎｄＷｉｔｎｅｓｓ（ｐａｒ，ｃｏｍ，ｉ，ｒ，ｗ）：公開パラメータｐａｒ、非秘匿ベクトル・コミットメントｃｏｍ、位置ｉ、ランダムネス
【数１１１】
0006959994.tif 000112
及び部分証拠ｗの入力時、アルゴリズムは、
【数１１２】
0006959994.tif 000113
を計算し、ｗ´を出力する。
【００８４】
以下は、上記に使用されるＰｏＫプロトコルの具体的な実施を与える。ＣＲＳは、Ｃａｍｅｎｉｓｃｈ−Ｓｈｏｕｐ暗号化スキーム（先に参照した非特許文献８）のＣＰＡバージョンの公開鍵を含む。この実施形態において、ＣＲＳにおける係数Ｎが獲得され、ここで、Ｎは、分散方式で生成され得る２つの安全素数の積である。ｇ´及びｙ´は、ＣＲＳ内に含まれる
【数１１３】
0006959994.tif 000114
のランダム要素とし、ｇ＝ｇ´２Ｎ、ｙ＝ｙ´２Ｎ、及びｈ＝１＋Ｎ  ｍｏｄ  Ｎ２を設定する。最初に、上記のＶＣインスタンス化の両方に共通しているＰｏＫの実施を説明し、次に、各ＶＣに特有の実施を与える。当技術分野において周知のように、全てのＰｏＫは、所望の通り、対話型又は非対話型証明として実行することができる。
【００８５】
両方のＶＣスキームに共通のＰｏＫ：
【数１１４】
0006959994.tif 000115
これは、最初に、ｒ１及びｒ２が［Ｎ／４］からランダムに選ばれるものとして
【数１１５】
0006959994.tif 000116
を計算し、これらの値を検証者に送り、証明者により以下の証明
【数１１６】
0006959994.tif 000117
を実行することにより行われ、ここで、簡潔にするために、ｍｏｄ  ρ及びｍｏｄ  Ｎ２は省略される。
【００８６】
【数１１７】
0006959994.tif 000118
は、次のように実行される。［ｋ］＝（ｅ１，ｅ２）を示すものとする。証明者は、最初に、ｕｒが［Ｎ／４］からランダムに選ばれるものとして
【数１１８】
0006959994.tif 000119
を計算し、これらの値を検証者に送り、検証者により以下の証明プロトコル：
【数１１９】
0006959994.tif 000120
を実行する。
ここで、項
【数１２０】
0006959994.tif 000121
は、ｗ＝ｓｒ３であること、従って、
【数１２１】
0006959994.tif 000122
であることを示し、Ｂは、暗号化をランダム化するために証明者が使用した値である。
ＭＨＴ−ＶＣのためのＰｏＫ
これらの証明は、Πｓ３を証明する（上で説明したように、ここではΠｓ２を省略できる）。
【００８７】
【数１２２】
0006959994.tif 000123
は、ｒ１、ｒ２及びｒ３が［Ｎ／４］からランダムに引き出されるものとして、最初に、
【数１２３】
0006959994.tif 000124
を計算し、これらの値を検証者に送り、検証者により以下の証明プロトコル：
【数１２４】
0006959994.tif 000125
を実行することにより行われ、ここで、簡潔にするために、ｍｏｄ  ρ及びｍｏｄ  Ｎ２は省略される。
【００８８】
【数１２５】
0006959994.tif 000126
は、ｒ１、ｒ２及びｒ３が［Ｎ／４］からランダムに引き出されるものとして、最初に、
【数１２６】
0006959994.tif 000127
を計算し、これらの値を検証者に送り、次に、検証者により以下の証明プロトコル：
【数１２７】
0006959994.tif 000128
を実行することにより行われる。１つの実施形態において、これは、ｘ及びｙから計算できるので、証拠ｗを検証可能な形で暗号する必要がない場合がある。同様に、ハッシュ木の経路のより大きい証明においてこれらの証明を結合するとき、多数の暗号がドロップされることがある。
【００８９】
ＲＳＡ−ＶＣのためのＰｏＫ：
【数１２８】
0006959994.tif 000129
この記述は、ｓ´が、次にｃｏｍｓがコミットするベクトル・コミットメントのランダム化されたバージョンであることを証明する。言い換えれば、ｒ０のある値及びｃｏｍｓにおいてコミットされたｓに対して
【数１２９】
0006959994.tif 000130
が成り立つ。この記述は、以下の証明プロトコル
【数１３０】
0006959994.tif 000131
により証明することができる。ここで、ｒ´２は、ランダムネス
【数１３１】
0006959994.tif 000132
を吸収するが、ｒ´２について何も証明する必要がない場合がある。このプロトコルは、これが「ダブル離散対数（double discrete logarithm）」関係（従って、ＧＳＰＫ０１の接尾辞０１）を伴うため、バイナリ・チャレンジと共に機能する。
【００９０】
【数１３２】
0006959994.tif 000133
この証明において、ＣＲＳは、位数ｐ´ｑ´の
【数１３３】
0006959994.tif 000134
から要素ｚ１、ｚ２及びｚ３を含むことを必要とし得るので、ｗは、ｚ１に対して検証可能な形でエルガマル（ElGamal）暗号化し、ｚ２及びｚ３に対してｗについての範囲証明を行うことができる。従って、証明者は、ｕｘ及びｒが［Ｎ／４］からランダムに選ばれるものとして、最初に
【数１３４】
0006959994.tif 000135
を計算し、Ｅ１、Ｅ２、Ｅ´及びＥｘを検証者に送り、検証者により以下の証明：
【数１３５】
0006959994.tif 000136
実行する。この証明は、
【数１３６】
0006959994.tif 000137
がｘに対する証拠であり、ｘが必要とされる範囲内にあることを示す。
【００９１】
上記の実施形態は、重複排除アプリケーションに適し、かつ、鍵を生成するファイルを保有しているクライアントによってしか取得できない、クライアント鍵の、並外れてセキュアかつ効率的な生成を可能にすることが分かるであろう。しかしながら、説明される鍵生成手順は、鍵を取得するためにクライアントが知識を証明するデータから決定論的に導出される、オブリビアスな（oblivious）鍵生成を必要とするあらゆる用途に適用できることが理解されるであろう。
【００９２】
説明される例示的な実施形態に対して他の多くの変更及び修正をなすことができる。例えば、ストレージ・サーバ４によるファイル・レベルの重複排除が上述されるが、他の実施形態において、重複排除の粒度は、データ・ブロック、オブジェクト、又は他のいずれかのデータ・ユニットとすることができる。また、幾つかの実施形態において、鍵サーバ１０３はクライアントとの対話において何も知らないので、鍵サーバ１０３及びストレージ・サーバ１０４の機能を併合することが可能である。しかしながら、オフラインのブルートフォース攻撃に対して与えられる付加的な保護のために、サーバ１０３及び１０４を別個のエンティティとして実装することが好ましい。
【００９３】
特に効率的な実施を説明したが、鍵生成プロトコルにおけるオブリビアスな鍵生成及び種々の証明の構成のために、他のスキームを考えることができる。
【００９４】
一般に、フローチャートのステップは、示されるものとは異なる順序で実行することができ、必要に応じて幾つかのステップを同時に実行することができる。
【００９５】
本発明の種々の実施形態の説明は説明を目的として提示されているが、網羅的であること、又は開示された実施形態に限定することを意図したものではない。当業者には、説明される実施形態の範囲及び趣旨から逸脱することなく、多くの修正及び変形が明らかであろう。本明細書で使用される用語は、実施形態の原理、実際の用途、若しくは市場で見出される技術に優る技術的改善を最も良く説明するために、又は当業者が本明細書に開示される実施形態を理解するのを可能にするために、選択された。
【００９６】
図６は、本発明の実施形態による、図１のコンピュータ・システム５００の内部コンポーネント及び外部コンポーネントのブロック図である。図６は、１つの実装の例証のみを与えるものであり、異なる実施形態を実装できる環境に関するいずれの限定も意味しないことを認識されたい。一般に、図６に示されるコンポーネントは、マシン可読プログラム命令を実行できる任意の電子デバイスを表す。図６に示されるコンポーネントにより表すことができるコンピュータ・システム、環境、及び／又は構成の例として、これらに限定されるものではないが、パーソナル・コンピュータ・システム、サーバ・コンピュータ・システム、シン・クライアント、シック・クライアント、ラップトップ・コンピュータ・システム、タブレット・コンピュータ・システム、携帯電話（例えば、スマートフォン）、マルチプロセッサ・システム、マイクロプロセッサ・ベースのシステム、ネットワークＰＣ、ミニコンピュータ・システム、メインフレーム・コンピュータ・システム、及び上記のシステム若しくはデバイスのいずれかを含む分散型クラウド・コンピューティング環境が挙げられる。
【００９７】
コンピュータ・システム５００は、１つ又は複数のプロセッサ５０４、メモリ５０６、永続的ストレージ５０８、通信ユニット５１２、及び入力／出力（Ｉ／Ｏ）インターフェース５１４の間の通信を提供する通信ファブリック５０２を含む。通信ファブリック５０２は、プロセッサ（マイクロプロセッサ、通信及びネットワーク・プロセッサ等のような）、システム・メモリ、周辺機器、及びシステム内の他のいずれかのハードウェア・コンポーネントの間でデータ及び／又は制御情報を送るように設計された任意のアーキテクチャを有するように実装することができる。例えば、通信ファブリック５０２は、１つ又は複数のバスを有するように実装することができる。
【００９８】
メモリ５０６及び永続的ストレージ５０８は、コンピュータ可読ストレージ媒体である。この実施形態において、メモリ５０６は、ランダム・アクセス・メモリ（ＲＡＭ）５１６及びキャッシュ・メモリ５１８を含む。一般に、メモリ５０６は、任意の好適な揮発性又は不揮発性コンピュータ可読ストレージ媒体を含むことができる。ソフトウェアは、メモリ５０６の１つ又は複数のメモリを介した、それぞれのプロセッサ５０４の１つ又複数による実行及び／又はアクセスのために、永続ストレージ５０８内に格納される。
【００９９】
永続的ストレージ５０８は、例えば、複数の磁気ハードディスク・ドライブを含むことができる。代替的に又は磁気ハードディスク・ドライブに加えて、永続的ストレージ５０８は、１つ又は複数のソリッド・ステート・ハード・ドライブ、半導体ストレージ・デバイス、読み出し専用メモリ（ＲＯＭ）、消去可能プログラム可能読み出し専用メモリ（ＥＰＲＯＭ）、フラッシュメモリ、又はプログラム命令若しくはデジタル情報を格納することができる他のいずれかのコンピュータ可読ストレージ媒体を含むことができる。
【０１００】
永続的ストレージ５０８により使用される媒体は、取り外し可能とすることもできる。例えば、取り外し可能なハードドライブを、永続的ストレージ５０８のために用いることができる。他の例として、光ディスク及び磁気ディスク、サムドライブ、及び永続的ストレージ５０８の一部でもある別のコンピュータ可読ストレージ媒体に転送するためにドライブに挿入されるスマートカードが挙げられる。
【０１０１】
通信ユニット５１２は、ネットワーク（例えば、ネットワーク１０５）を介するコンピュータ・システム又はデバイスとの通信を提供する。この例示的な実施形態において、通信ユニット５１２は、ＴＣＰ／ＩＰアダプタ・カード、無線Ｗｉ−Ｆｉインターフェース・カード、又は３Ｇ若しくは４Ｇ無線インターフェース・カード、又は他の有線若しくは無線通信リンクを含む。ネットワークは、例えば、銅線、光ファイバ、無線伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、及び／又はエッジ・サーバを含むことができる。本発明の実施形態を実施するために用いられるソフトウェア及びデータは、通信ユニット５１２を通じて（例えば、インターネット、ローカル・エリア・ネットワーク、又は他の広域ネットワークを介して）ダウンロードすることができる。通信ユニット５１２から、ソフトウェア及びデータを永続的ストレージ５０８にロードすることができる。
【０１０２】
１つ又は複数のＩ／Ｏインターフェース５１４は、コンピュータ・システム５００に接続することができる他のデバイスとのデータの入力及び出力を可能にする。例えば、Ｉ／Ｏインターフェース５１４は、キーボード、コンピュータ・マウス、タッチスクリーン、仮想キーボード、タッチパッド、ポインティング・デバイス、又は他のヒューマン・インターフェース・デバイスのような１つ又は複数の外部デバイス５２０への接続を提供することができる。外部デバイス５２０はまた、例えば、サムドライブ、携帯型光ディスク又は磁気ディスク、及びメモリカードなどの携帯型コンピュータ可読ストレージ媒体を含むこともできる。Ｉ／Ｏインターフェース５１４は、ディスプレイ５２２にも接続される。
【０１０３】
ディスプレイ５２２は、データを表示するための機構をユーザに提供し、例えば、コンピュータ・モニタとすることができる。ディスプレイ５２２は、組み込み式ディスプレイとすることもでき、タブレット・コンピュータの内蔵ディスプレイのようなタッチスクリーンとして機能することができる。
【０１０４】
本発明は、システム、方法、及び／又はコンピュータ・プログラム製品とすることができる。コンピュータ・プログラム製品は、プロセッサに本発明の態様を実行させるためのコンピュータ可読プログラム命令をその上に有するコンピュータ可読ストレージ媒体（単数又は複数）を含むことができる。
【０１０５】
コンピュータ可読ストレージ媒体は、命令実行デバイスにより使用される命令を保持及び格納できる有形デバイスとすることができる。コンピュータ可読ストレージ媒体は、例えば、これらに限定されるものではないが、電子記憶装置、磁気記憶装置、光学記憶装置、電磁気記憶装置、半導体記憶装置、又は上記のいずれかの適切な組み合わせとすることができる。コンピュータ可読ストレージ媒体のより具体的な例の非網羅的なリストとして、以下のもの：すなわち、ポータブル・コンピュータ・ディスケット、ハードディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、消去可能プログラム可能読み出し専用メモリ（ＥＰＲＯＭ又はフラッシュメモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）、デジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピー・ディスク、パンチカード若しくは命令がそこに記録された溝内の隆起構造のような機械的にエンコードされたデバイス、及び上記のいずれかの適切な組み合わせが挙げられる。本明細書で使用される場合、コンピュータ可読ストレージ媒体は、電波、又は他の自由に伝搬する電磁波、導波管若しくは他の伝送媒体を通じて伝搬する電磁波（例えば、光ファイバ・ケーブルを通る光パルス）、又はワイヤを通って送られる電気信号などの、一時的信号自体として解釈されない。
【０１０６】
本明細書で説明されるコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体からそれぞれのコンピューティング／処理デバイスに、又は、例えばインターネット、ローカル・エリア・ネットワーク、広域ネットワーク、及び／又は無線ネットワークなどのネットワークを介して外部コンピュータ又は外部ストレージ・デバイスにダウンロードすることができる。ネットワークは、銅伝送ケーブル、光伝送ファイバ、無線伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、及び／又はエッジ・サーバを含むことができる。各コンピューティング／処理デバイスにおけるネットワーク・アダプタ・カード又はネットワーク・インターフェースは、ネットワークからコンピュータ可読プログラム命令を受け取り、コンピュータ可読プログラム命令を転送して、それぞれのコンピューティング／処理デバイス内のコンピュータ可読ストレージ媒体に格納する。
【０１０７】
本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セットアーキテクチャ（ＩＳＡ）命令、マシン命令、マシン依存命令、マイクロコード、ファームウェア命令、状態設定データ、又は、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語、及び、「Ｃ」プログラミング言語若しくは類似のプログラミング言語などの通常の手続き型プログラミング言語を含む１つ又は複数のプログラミング言語の任意の組み合わせで記述することができる。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で実行される場合もあり、一部がユーザのコンピュータ上で、独立型ソフトウェア・パッケージとして実行される場合もあり、一部がユーザのコンピュータ上で実行され、一部が遠隔コンピュータ上で実行される場合もあり、又は完全に遠隔コンピュータ若しくはサーバ上で実行される場合もある。最後のシナリオにおいて、遠隔コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）若しくは広域ネットワーク（ＷＡＮ）を含むいずれかのタイプのネットワークを通じてユーザのコンピュータに接続される場合もあり、又は外部コンピュータへの接続がなされる場合もある（例えば、インターネットサービスプロバイダを用いたインターネットを通じて）。幾つかの実施形態において、例えば、プログラム可能論理回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、又はプログラム可能論理アレイ（ＰＬＡ）を含む電子回路は、コンピュータ可読プログラム命令の状態情報を用いて電子回路を個人化することによりコンピュータ可読プログラム命令を実行し、本発明の態様を実施することができる。
【０１０８】
本発明の態様は、本発明の実施形態による方法、装置（システム）及びコンピュータ・プログラム製品のフローチャート図及び／又はブロック図を参照して説明される。フローチャート図及び／又はブロック図の各ブロック、並びにフローチャート図及び／又はブロック図内のブロックの組み合わせは、コンピュータ可読プログラム命令によって実装できることが理解されるであろう。
【０１０９】
これらのコンピュータ可読プログラム命令を、汎用コンピュータ、専用コンピュータ、又は他のプログラム可能データ処理装置のプロセッサに与えてマシンを製造し、それにより、コンピュータ又は他のプログラム可能データ処理装置のプロセッサによって実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロック内で指定された機能／動作を実施するための手段を作り出すようにすることができる。これらのコンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、及び／又は他のデバイスを特定の方式で機能させるように指示することができるコンピュータ可読媒体内に格納し、それにより、そのコンピュータ可読媒体内に格納された命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作の態様を実施する命令を含む製品を含むようにすることもできる。
【０１１０】
コンピュータ・プログラム命令を、コンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上にロードして、一連の動作ステップをコンピュータ、他のプログラム可能データ処理装置、又は他のデバイス上で行わせてコンピュータ実施のプロセスを生成し、それにより、コンピュータ、他のプログラム可能装置、又は他のデバイス上で実行される命令が、フローチャート及び／又はブロック図の１つ又は複数のブロックにおいて指定された機能／動作を実行するためのプロセスを提供するようにすることもできる。
【０１１１】
図面内のフローチャート及びブロック図は、本発明の種々の実施形態による、システム、方法、及びコンピュータ・プログラム製品の可能な実装の、アーキテクチャ、機能及び動作を示す。この点に関して、フローチャート内の各ブロックは、指定された論理機能を実装するための１つ又は複数の実行可能命令を含む、モジュール、セグメント、又はコードの一部を表すことができる。幾つかの代替的な実装において、ブロック内に示される機能は、図に示される順序とは異なる順序で生じることがある。例えば、連続して示される２つのブロックは、関与する機能に応じて、実際には実質的に同時に実行されることもあり、又はこれらのブロックは、ときとして逆順で実行されることもある。ブロック図及び／又はフローチャート図の各ブロック、及びブロック図及び／又はフローチャート図内のブロックの組み合わせは、指定された機能又は動作を実行する、又は専用のハードウェアとコンピュータ命令との組み合わせを実行する、専用ハードウェア・ベースのシステムによって実装できることにも留意されたい。
【０１１２】
本開示はクラウド・コンピューティングについての詳細な説明を含むが、本明細書に記載される教示の実装は、クラウド・コンピューティング環境に限定されないことを理解されたい。むしろ、本発明の実施形態は、現在周知の又は後で開発される他のいずれかのタイプのコンピューティング環境と共に実施することができる。
【０１１３】
クラウド・コンピューティングは、最小限の管理労力又はサービス・プロバイダとの対話で迅速にプロビジョニング及び解放することができる構成可能なコンピューティング・リソース（例えば、ネットワーク、ネットワーク帯域幅、サーバ、処理、メモリ、ストレージ、アプリケーション、仮想マシン、及びサービス）の共有プールへの、便利なオンデマンドのネットワーク・アクセスを可能にするためのサービス配信のモデルである。このクラウド・モデルは、少なくとも５つの特徴、少なくとも３つのサービス・モデル、及び少なくとも４つの配備モデルを含むことができる。
【０１１４】
特徴は、以下の通りである。
【０１１５】
オンデマンド・セルフサービス：クラウド・コンシューマは、必要に応じて、サーバ時間及びネットワーク・ストレージ等のコンピューティング機能を、人間がサービスのプロバイダと対話する必要なく自動的に、一方的にプロビジョニングすることができる。
【０１１６】
広範なネットワーク・アクセス：機能は、ネットワーク上で利用可能であり、異種のシン又はシック・クライアント・プラットフォーム（例えば、携帯電話、ラップトップ、及びＰＤＡ）による使用を促進する標準的な機構を通じてアクセスされる。
【０１１７】
リソースのプール化：プロバイダのコンピューティング・リソースは、マルチ・テナント・モデルを用いて、異なる物理及び仮想リソースを要求に応じて動的に割り当て及び再割り当てすることにより、複数のコンシューマにサービスを提供するためにプールされる。コンシューマは、一般に、提供されるリソースの正確な位置についての制御又は知識を持たないが、より高レベルの抽象化では位置（例えば、国、州、又はデータセンタ）を特定できる場合があるという点で、位置とは独立しているといえる。
【０１１８】
迅速な弾力性：機能は、迅速かつ弾力的に、幾つかの場合自動的に、プロビジョニングして素早くスケール・アウトし、迅速にリリースして素早くスケール・インさせることができる。コンシューマにとって、プロビジョニングに利用可能なこれらの機能は、多くの場合、無制限であり、いつでもどんな量でも購入できるように見える。
【０１１９】
サービスの測定：クラウド・システムは、サービスのタイプ（例えば、ストレージ、処理、帯域幅、及びアクティブなユーザ・アカウント）に適した何らかの抽象化レベルでの計量機能を用いることによって、リソースの使用を自動的に制御及び最適化する。リソース使用を監視し、制御し、報告し、利用されるサービスのプロバイダとコンシューマの両方に対して透明性をもたらすことができる。
【０１２０】
サービス・モデルは以下の通りである。
【０１２１】
Ｓｏｆｔｗａｒｅ  ａｓ  ａ  Ｓｅｒｖｉｃｅ（ＳａａＳ）：クラウド・インフラストラクチャ上で動作しているプロバイダのアプリケーションを使用するために、コンシューマに提供される機能である。これらのアプリケーションは、ウェブ・ブラウザ（例えば、ウェブ・ベースの電子メール）などのシン・クライアント・インターフェースを通じて、種々のクライアント・デバイスからアクセス可能である。コンシューマは、限定されたユーザ固有のアプリケーション構成設定の考え得る例外として、ネットワーク、サーバ、オペレーティング・システム、ストレージ、又は個々のアプリケーション機能をも含めて、基礎をなすクラウド・インフラストラクチャを管理又は制御しない。
【０１２２】
Ｐｌａｔｆｏｒｍ  ａｓ  ａ  Ｓｅｒｖｉｃｅ（ＰａａＳ）：プロバイダによってサポートされるプログラミング言語及びツールを用いて生成された、コンシューマが生成した又は取得したアプリケーションを、クラウド・インフラストラクチャ上に配備するために、コンシューマに提供される機能である。コンシューマは、ネットワーク、サーバ、オペレーティング・システム、又はストレージなどの基礎をなすクラウド・インフラストラクチャを管理又は制御しないが、配備されたアプリケーション、及び場合によってはアプリケーション・ホスティング環境構成に対して制御を有する。
【０１２３】
Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  ａｓ  ａ  Ｓｅｒｖｉｃｅ（ＩａａＳ）：コンシューマが、オペレーティング・システム及びアプリケーションを含み得る任意のソフトウェアを配備及び動作させることができる、処理、ストレージ、ネットワーク、及び他の基本的なコンピューティング・リソースをプロビジョニンングするために、コンシューマに提供される機能である。コンシューマは、基礎をなすクラウド・インフラストラクチャを管理又は制御しないが、オペレーティング・システム、ストレージ、配備されたアプリケーションに対する制御、及び場合によってはネットワーク・コンポーネント（例えば、ホストのファイアウォール）選択の限定された制御を有する。
【０１２４】
配備モデルは以下の通りである。
【０１２５】
プライベート・クラウド：クラウド・インフラストラクチャは、ある組織のためだけに運営される。このクラウド・インフラストラクチャは、その組織又は第三者によって管理することができ、構内又は構外に存在することができる。
【０１２６】
コミュニティ・クラウド：クラウド・インフラストラクチャは、幾つかの組織によって共有され、共通の関心事項（例えば、任務、セキュリティ要件、ポリシー、及びコンプライアンス上の考慮事項）を有する特定のコミュニティをサポートする。クラウド・インフラストラクチャは、その組織又は第三者によって管理することができ、オンプレミス又はオフプレミスに存在することができる。
【０１２７】
パブリック・クラウド：クラウド・インフラストラクチャは、一般公衆又は大規模な業界グループに利用可能であり、クラウド・サービスを販売する組織によって所有される。
【０１２８】
ハイブリッド・クラウド：クラウド・インフラストラクチャは、固有のエンティティのままであるが、データ及びアプリケーションの移行性を可能にする標準化された又は専用の技術（例えば、クラウド間の負荷分散のためのクラウド・バースティング）によって結び付けられる２つ又はそれより多いクラウド（プライベート、コミュニティ、又はパブリック）の混成物である。
【０１２９】
クラウド・コンピューティング環境は、無国籍性、低結合性、モジュール性、及びセマンティック相互運用性に焦点を置くことを指向するサービスである。クラウド・コンピューティングの中心は、相互接続されたノードのネットワークを含むインフラストラクチャである。
【０１３０】
ここで図７を参照すると、例示的なクラウド・コンピューティング環境１０が示される。示されるように、クラウド・コンピューティング環境１０は、例えば携帯情報端末（ＰＤＡ）又は携帯電話１４Ａ、デスクトップ・コンピュータ１４Ｂ、ラップトップ・コンピュータ１４Ｃ、及び／又は自動車コンピュータ・システム１４Ｎなどといった、クラウド・コンシューマによって用いられるローカル・コンピューティング・デバイスと通信することができる、１つ又は複数のクラウド・コンピューティング・ノード１０を含む。ノード１は、互いに通信することができる。これらのノードは、上述のようなプライベート・クラウド、コミュニティ・クラウド、パブリック・クラウド、若しくはハイブリッド・クラウド、又はこれらの組み合わせなど、１つ又は複数のネットワークにおいて物理的又は仮想的にグループ化することができる（図示せず）。これにより、クラウド・コンピューティング環境１０は、クラウド・コンシューマがローカル・コンピューティング・デバイス上にリソースを保持する必要のないサービスとして、インフラストラクチャ、プラットフォーム、及び／又はソフトウェアを提供することが可能になる。図７に示されるコンピューティング・デバイス１４Ａ〜Ｎのタイプは単に例示であることを意図し、コンピューティング・ノード１及びクラウド・コンピューティング環境１０は、いずれのタイプのネットワーク及び／又はネットワーク・アドレス指定可能な接続上でも（例えば、ウェブ・ブラウザを用いて）、いずれのタイプのコンピュータ化された装置とも通信できることを理解されたい。
【０１３１】
ここで図８を参照すると、クラウド・コンピューティング環境１０（図７）によって提供される機能抽象化層の組が示される。図８に示されるコンポーネント、層、及び機能は単に例示であることを意図し、本発明の実施形態はそれらに限定されないことを予め理解されたい。図示されるように、以下の層及び対応する機能が提供される。
【０１３２】
ハードウェア及びソフトウェア層６００は、ハードウェア及びソフトウェア・コンポーネントを含む。ハードウェア・コンポーネントの例として、メインフレーム６０１と；ＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ（縮小命令セット・コンピュータ））アーキテクチャ・ベースのサーバ６０２と；サーバ６０３と；ブレード・サーバ６０４と；ストレージ・デバイス６０５と；ネットワーク及びネットワーキング・コンポーネント６０６とが含まれる。幾つかの実施形態において、ソフトウェア・コンポーネントは、ネットワーク・アプリケーション・サーバ・ソフトウェア６０７及びデータベース・ソフトウェア６０８を含む。
【０１３３】
仮想化層７００は、抽象化層を提供し、この層により、仮想エンティティの以下の例、すなわち、仮想サーバ７０１、仮想ストレージ７０２、仮想プライベート・ネットワークを含む仮想ネットワーク７０３、仮想アプリケーション及びオペレーティング・システム７０４、並びに仮想クライアント７０５を提供することができる。
【０１３４】
一例においては、管理層８００は、以下で説明される機能を提供することができる。リソース・プロビジョニング８０１は、クラウド・コンピューティング環境内でタスクを実行するために利用されるコンピューティング・リソース及び他のリソースの動的な調達を提供する。計量及び価格決定８０２は、クラウド・コンピューティング環境内でリソースが利用される際のコスト追跡と、リソースの消費に対する課金又は請求とを提供する。一例においては、これらのリソースは、アプリケーション・ソフトウェア・ライセンスを含むことができる。セキュリティは、クラウド・コンシューマ及びタスクに対する識別情報の検証と、データ及び他のリソースに対する保護とを提供する。ユーザ・ポータル８０３は、コンシューマ及びシステム管理者のために、クラウド・コンピューティング環境へのアクセスを提供する。サービス・レベル管理８０４は、要求されるサービス・レベルが満たされるように、クラウド・コンピューティング・リソースの割り当て及び管理を提供する。サービス・レベル・アグリーメント（Ｓｅｒｖｉｃｅ  Ｌｅｖｅｌ  Ａｇｒｅｅｍｅｎｔ、ＳＬＡ）の計画及び履行８０５は、ＳＬＡに従って将来の要件が予測されるクラウド・コンピューティング・リソースの事前配置及び調達を提供する。
【０１３５】
ワークロード層９００は、クラウド・コンピューティング環境を利用することができる機能の例を提供する。この層から提供することができるワークロード及び機能の例には、マッピング及びナビゲーション９０１、ソフトウェア開発及びライフサイクル管理９０２、仮想教室教育配信９０３、データ分析処理９０４、トランザクション処理９０５、及びシステム９０６が含まれる。
【符号の説明】
【０１３６】
１００：システム
１０２：クライアント・コンピュータ
１０３：鍵サーバ
１０４：ストレージ・サーバ
１０５：ネットワーク
１０６：データベース
５００：コンピュータ・システム
５０２：通信ファブリック
５０４：プロセッサ
５０６：メモリ
５０８：永続的ストレージ
５１２：通信ユニット
５１４：Ｉ／Ｏインターフェース
５２０：外部デバイス
５２２：ディスプレイ
【図１】
0006959994.tif 000139
【図２】
0006959994.tif 000140
【図３】
0006959994.tif 000141
【図４】
0006959994.tif 000142
【図５】
0006959994.tif 000143
【図６】
0006959994.tif 000144
【図７】
0006959994.tif 000145
【図８】
0006959994.tif 000146