"動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、前記動作は、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを受信すること、および、前記暗号文Cを取得するために前記暗号化方式の前記暗号化機能に従って前記情報Bを暗号化することを含み、前記暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、前記情報B、前記暗号文C、前記少なくとも1つの公開鍵A、および前記少なくとも1つの秘密鍵Tは行列であり、前記暗号化機能は、入力として前記少なくとも1つの公開鍵Aおよび前記情報Bを受信し、前記暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である、コンピュータ読み取り可能記憶媒体。およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータである、請求項1に記載のコンピュータ読み取り可能記憶媒体。前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項1に記載のコンピュータ読み取り可能記憶媒体。p=2であり、前記情報Bが2進値の行列を備える、請求項1に記載のコンピュータ読み取り可能記憶媒体。c=cn>0、q>220p2c43n3c4log5n、およびである、請求項1に記載のコンピュータ読み取り可能記憶媒体。前記暗号化方式が、行列環上でいずれかの次数でncの加法および1つの乗法をサポートする、請求項5に記載のコンピュータ読み取り可能記憶媒体。暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを記憶するように構成された、少なくとも1つの記憶媒体と、前記暗号文Cを取得するために前記暗号化方式の前記暗号化機能に従って前記情報Bを暗号化するように構成された、少なくとも1つのプロセッサと、備える、装置であって、前記暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、前記情報B、前記暗号文C、前記少なくとも1つの公開鍵A、および前記少なくとも1つの秘密鍵Tは行列であり、前記暗号化機能は入力として前記少なくとも1つの公開鍵Aおよび前記情報Bを受信し、前記暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である、装置。およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータである、請求項7に記載の装置。前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項7に記載の装置。p=2であり、前記情報Bが2進値の行列を備える、請求項7に記載の装置。c=cn>0、q>220p2c43n3c4log5n、およびである、請求項7に記載の装置。前記暗号化方式が、行列環上でいずれかの次数でncの加法および1つの乗法をサポートする、請求項11に記載の装置。動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、前記動作は、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを受信すること、および、前記情報Bを取得するために前記暗号化方式の前記復号機能に従って前記暗号文Cを復号することを含み、前記暗号化方式は少なくとも1つの秘密鍵Tを使用し、前記情報B、前記暗号文C、および前記少なくとも1つの秘密鍵Tは行列であり、前記復号機能は入力として前記少なくとも1つの秘密鍵Tおよび前記暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って前記情報Bを出力し、この式でpは整数であり、qは奇数の素数である、コンピュータ読み取り可能記憶媒体。およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータである、請求項13に記載のコンピュータ読み取り可能記憶媒体。前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項13に記載のコンピュータ読み取り可能記憶媒体。p=2であり、前記情報Bが2進値の行列を備える、請求項13に記載のコンピュータ読み取り可能記憶媒体。c=cn>0、q>220p2c43n3c4log5n、およびである、請求項13に記載のコンピュータ読み取り可能記憶媒体。前記暗号化方式が、行列環上でいずれかの次数でncの加法および1つの乗法をサポートする、請求項17に記載のコンピュータ読み取り可能記憶媒体。復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するように構成された、少なくとも1つの記憶媒体と、前記情報Bを取得するために前記暗号化方式の前記復号機能に従って前記暗号文Cを復号するように構成された、少なくとも1つのプロセッサと、を備える、装置であって、前記暗号化方式は少なくとも1つの秘密鍵Tを使用し、前記情報B、前記暗号文C、および前記少なくとも1つの秘密鍵Tは行列であり、前記復号機能は入力として前記少なくとも1つの秘密鍵Tおよび前記暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って前記情報Bを出力し、この式でpは整数であり、qは奇数の素数である、装置。およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータである、請求項19に記載の装置。前記暗号化方式が準同形であり、双一次形式の計算をサポートする、請求項19に記載の装置。p=2であり、前記情報Bが2進値の行列を備える、請求項19に記載の装置。c=cn>0、q>220p2c43n3c4log5n、およびである、請求項19に記載の装置。前記暗号化方式が、行列環上でいずれかの次数でncの加法および1つの乗法をサポートする、請求項23に記載の装置。動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、前記動作は、暗号化機能および復号機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを受信すること、および、前記暗号文Cを取得するために前記暗号化方式の前記暗号化機能に従って前記情報Bを暗号化すること、を含み、前記暗号化方式は少なくとも1つの公開鍵Aおよび前記少なくとも1つの秘密鍵Aに対応する少なくとも1つの秘密鍵Tを使用し、前記情報B、前記暗号文C、前記少なくとも1つの公開鍵A、および前記少なくとも1つの秘密鍵Tは行列であり、およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、qは奇数の素数であり、pは整数であり、q>pであり、前記暗号化機能は入力としてAおよびBを受信し、前記暗号文Cをとして出力し、この式でSはランダム行列であって、であり、Xはエラー行列であって、であり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータであり、前記復号機能は入力としてTおよびCを受信し、B=T-1TCTtmodqTt-1modpに従って前記情報Bを出力し、前記暗号化方式は準同形であり、双一次形式の計算をサポートする、コンピュータ読み取り可能記憶媒体。この発明の目的は、暗号化および復号化のアルゴリズムに関し、より具体的には、双一次形式bilinearformのための準同形homomorphic暗号化方式を提供することにある。本発明の一例示的実施形態では、コンピュータ読み取り可能記憶媒体が、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化し、動作は、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを受信すること、および、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化することを含み、暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である。本発明の他の例示的実施形態では、装置が、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを記憶するように構成された、少なくとも1つの記憶媒体と、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化するように構成された、少なくとも1つのプロセッサとを備え、暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である。本発明の他の例示的実施形態では、コンピュータ読み取り可能記憶媒体が、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化し、動作は、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを受信すること、および、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号することを含み、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。本発明の他の例示的実施形態では、装置が、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するように構成された、少なくとも1つの記憶媒体と、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号するように構成された、少なくとも1つのプロセッサとを備え、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。本発明の他の例示的実施形態では、コンピュータ読み取り可能記憶媒体が、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化し、動作は、暗号化機能および復号機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを受信すること、および、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化することを含み、暗号化方式は少なくとも1つの公開鍵Aおよび少なくとも1つの秘密鍵Aに対応する少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、qは奇数の素数であり、pは整数であり、q>pであり、暗号化機能は入力としてAおよびBを受信し、暗号文Cをとして出力し、この式でSはランダム行列であって、であり、Xはエラー行列であって、であり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータであり、復号機能は入力としてTおよびCを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、暗号化方式は準同形であり、双一次形式の計算をサポートする。本発明の実施形態の前述および他の態様は、添付の図面に関連して以下の発明を実施するための形態を読めば、より明らかとなろう。1簡潔な概要本発明の例示的実施形態は、Boneh、Goh、およびNissimBGNの暗号化システムと同様の、双一次形式の計算たとえば、多項式的に多くの加法および1つの乗法をサポートする、単純な公開鍵暗号化方式を構築する。安全性は、最悪のケースの格子問題と同様に困難であるものとして知られている、エラーでの習得LWE:learningwitherrors問題の困難性に基づく。例示的暗号システムのいくつかの特徴は、大規模メッセージスペースのサポート、公式プライバシを達成する容易な方法、BGNよりも良好なメッセージ対暗号文拡張比、および、2つの暗号化多項式を乗算する容易な方法を含む。またこの方式は、より高いメッセージ対暗号文拡張比を犠牲にした識別ベースであり、耐リーク性とすることができる。本明細書におけるZへの任意またはすべての言及たとえば、は、すべての整数セットに対応するものと理解されたい。さらに、本明細書における、秘密、秘密鍵、またはトラップドアtrapdoorは、たとえば、公開鍵-公開鍵暗号化方式の場合におけるような秘密鍵、またはその逆に対応するものと理解されたい。本明細書で使用される用語は、本発明の様々な例示的実施形態を説明するためのものであり、本発明を制限することは意図されていない。本明細書で使用される場合、単数形a、an、およびtheは、特にコンテキストが明確に指示していない限り、複数形も同様に含むことが意図される。含むまたは含んでいるあるいはその両方の用語は、本明細書で使用される場合、述べられた特徴、整数、ステップ、動作、要素、または構成要素、あるいはそれらすべての存在を指定するが、1つまたは複数の他の特徴、整数、ステップ、動作、要素、構成要素、またはそれらのグループ、あるいはそれらすべての存在または追加を排除するものではないことを、さらに理解されよう。1.1はじめに本書では、加法的に準同形であり、加えて、1つの乗法もサポートする、例示的暗号化方式について説明する。例示的方式は、Gentry、Peikert、およびVaikuntanathanによって提案されたトラップドア関数[10]以下、GPVトラップドア関数と呼ぶに基づく。GPVトラップドア関数では、公開鍵は行列パラメータq>pおよびm>nの場合であり、対応するトラップドアはTA=0modqのような小さいエントリを伴う最大階数整数行列である。例示的暗号化システムにおける公開鍵および秘密鍵は、GPVトラップドア関数の場合とまったく同一である。正方行列は、C=ASpXBmodqを設定することによって暗号化され、上式で、Sはランダム係数行列であり、Xは、Xのエントリがqよりも大幅に小さいようなエントリを伴うノイズ行列である。暗号文行列を付加することが可能であり、単一の行列乗法C’=C1Ct2modqもサポートされる。C’はCの転置である。復号するためには以下のように設定する。B=T-1TCTtmodqTt-1modp例示的方式の安全性は、エラーでの習得LWEの困難性と等価である。この問題は、良く知られたノイズでのパリティ習得learningparitywithnoiseに関し、格子ベースの暗号化の研究では標準的になっている。この問題は、最初にRegev[14]によって提案され、Regev[14]およびPeikert[13]によって、整数格子における様々な問題の最悪のインスタンスと同じように困難であることが示された。LWE問題が関連付けられたエラー分布に関係することが、簡潔に示されている。1.2寄与おそらく、例示的方式と以前の研究との主な相違点は、基礎となる困難性仮定であろう。特に例示的方式は、単なる加法的準同形を超えたLWEに基づいて最初に報告された暗号化システムである。また、例示的方式は非常に効率的であり、の時点でm2要素の行列を暗号化することが可能であり、復号には同等の時間を要する。例示的方式とBGN暗号化システムとの1つの重要な相違点は、BGN暗号化システムが、復号時には、グループ要素gmのみを回復し、その後、メッセージmを検索する必要があるため小さいスペースからのメッセージのみを暗号化できるという点である。例示的方式では、qがpよりも十分に大きい限り、任意のpについてZp上で行列を暗号化することができる。関係する利点は、BGN暗号化システムは、Olognビットの平文をOnの暗号文ビットに拡張するが例示的方式は、大きな係数pを選択することによって、O1の暗号文拡張を有することができるようになることである。例示的方式においてメッセージスペースを画定する係数pは、暗号化側encryptorによって動的に選択可能であり、同じ公開鍵/秘密鍵のペアを使用して、多くの異なるフィールドまたは環を法とするメッセージを暗号化/復号することができることに留意されたい。例示的方式は、暗号文ブラインド化blindingすなわち、所与の暗号文が同じものを暗号化するランダムな暗号文に変換される、およびモジュールブラインド化のより強力な特性もサポートしており、行列を暗号化する暗号文が与えられ、pの何らかの除数p’が与えられた場合、p’を法とするBを暗号化するランダム暗号文を生成することができる。たとえば、元の平文行列がたとえばでnビット数を有する場合、B内のエントリの最下位ビット以外のすべてを消去するように暗号文をブラインド化することができる。標準的なブラインド化特性およびメッセージスペースの選択の柔軟性の1つの結果が、例示的システムが公式プライベートなセキュア計算のための非常に単純な手順を提供することである。すなわち、公式自体に関する所与の入力に適用した結果以外のあらゆることを秘密鍵の保持者から隠しながら、同時に、暗号文上の2DNF公式または一般的な双一次形式を計算することは非常に容易である。最後に、例示的方式は、LWEベースの暗号化システムが備えている柔軟性の多くを引き継ぐ。特に、Gentry等[10]の構築を使用して識別ベースとすることが可能であり、Dodis等[6]の最近の結果を使用して耐リーク性とすることが可能である。これらの適用例は両方共、[10]からの二重Regev暗号化システムを例示的暗号化システムの特殊なケースとして説明できる観察から得られる。適用例明らかに、例示的方式は、Boneh等[5]の論文で考察された投票およびPIRへの適用において、暫定的な代替として使用可能である。加えて例示的方式は、行列をネイティブに暗号化することから、バッチングから恩恵を受けることのできる適用例にとって、または効率的な線形代数が重要な場合に、好適である。バッチングのいくつかの例は、その係数が多項式またはそのビット表現が平文行列のエントリ内に符号化されることになる大きな整数を乗じるたとえば乗算する必要のある、適用例を含む。セクション5.3では、m×m行列の単一の乗法を使用して、2つの次数m-1多項式または2つのmビット整数を乗じることが可能なように、その結果がそれらの積以外のいずれの入力に関してもリークしないように、これらを行列内に符号化できる方法が説明されている。1.3例示的方式の概要例示的方式の構築の裏にある主な考えについて、以下で概略を説明する。例示的方式は、安全性パラメータnおよび多項式的に大きなmの場合、均一にランダムな行列が与えられると、ベクトルAsxは擬似ランダムであること均一なおよび小さいエラーベクトルの場合を示す、LWE問題決定の困難性に基づいている。LWE問題決定の困難性は、格子ベースの暗号化システムの研究において、現在も標準的な仮定であり、この問題は、Regev[14]およびPeikert[13]によって、いくつかの標準的な格子問題を最悪のケースで解決することと同様に困難であるものと示された。例示的方式の公開鍵はランダム行列であり、秘密鍵は、TA=0modqを満たす小さいエントリを伴うトラップドア行列Tである。暗号化方式に関するメッセージスペースは、行列の加法および乗法の演算によるpを法とする整数のm×m行列の環である。この方式は、pがLWE係数qよりも十分に小さい限り、任意の環Zp上で動作することができる。さらなる詳細についてはセクション3を参照されたい。行列を暗号化する場合、暗号化側は、LWEエラー分布からランダム行列および小さいエラー行列Xを選択する。その後、暗号文CはC=ASpXBとなる。暗号文が低階数行列pで割り切れる小さいノイズメッセージの形であることに留意されたい。暗号文の復号は、以下のように、暗号文に左側のトラップドア行列T低階数行列を除去するを乗じること、その後、ノイズを消去するためにpを法とするT-1を乗じることを含む。B=T-1TCmodqmodpこれは、T、X、およびBがすべて小さいことで働くため、TpXB内のすべてのエントリがq未満であり、これはmodqのみではなく整数上でTCmodqがTpXBに等しく、したがって、TBmodpに等しいことを意味する。いくつかの行列の暗号化の合計は、たとえば、内のすべてのエントリが小さいままである限り、これらの行列の合計に復号されることが容易にわかる。2つの行列の乗法の暗号化を取得するためには、以下のように設定する。これは、追加の交差項S’Atを除き、B1Bt2の暗号化と同様に見えるまた実際にはエラー行列Xは小さい。この積暗号文productciphertextを復号するためには、第1にM=TCTtmodqを設定し、結果としてASおよびS’Atの両方の項が消去され、その後B=T-1MTt-1modpとなる。これで、この方式が単一の乗法たとえば、これのみをサポートし、さらに、トラップドアTではもはや消去できない、SAS’の形の交差項が存在する理由が明らかとなる。2前置き表記法スカラーは小文字a、b、...で、ベクトルは太字の小文字で、および行列は太字の大文字で示す。ベクトルvのユークリッドノルムはで、ベクトルまたは行列内の最大エントリは、それぞれで示す。整数αを区間-q/2、q/2にマッピングする場合の演算αmodqについて考えてみる。2.1エラーでの習得LWELWE問題は、Regev[14]によってノイズでのパリティ習得の一般化として紹介された。正の整数nおよびq≧2、ベクトルおよびZq上の確率分布Xの場合、As,Xを、均一にランダムなベクトルおよびノイズ項を選択すること、およびを出力することによって取得される分布とする。定義1LWE整数q=qnおよびZq全体にわたるエラー分布の場合、エラーでの習得問題LWEn,m,q,Xは、As,Xからmの独立サンプルが与えられた場合何らかのの場合、顕著な確率でsを出力するように定義される。LWE問題の決定変形はdistLWEn,m,q,Xとして示され、As,X均一にランダムなの場合に従って選択されたmのサンプルを、全体にわたる均一な分布に従って選択されたmのサンプルから、無視できない利点で区別することである。暗号化適用例について、最も関心が高いのは決定問題distLWEである。Refev[14]は、素数係数qの場合、パラメータmにおける最高qpolyn因数までの損失で、distLWEを最悪のケースのLWEまで低減できることを示した。時には、コンパクトな行列表記法を使用して、LWE問題LWEn,m,q,Xについて説明するために便利であることがわかる場合がある。A,Asxが与えられ、この式でが均一にランダムなである場合、はLWE秘密であり、はsを発見する。同様の行列表記法が、決定バージョンdistLWEにも使用される。ガウスエラー分布最も関心が高いのは、LWEおよびdistLWE問題であり、ここではZq全体にわたるエラー分布Xがガウス分布から導出される。任意のβ>0について、実数全体にわたるガウス分布の密度関数は、Dβx=1/βexp-πx/β2によって与えられる。整数q≧2の場合、を、を引き出すこと、およびを出力することによって取得された、Zq上の分布として定義する。LWEn,m,q,βを、の省略形として書き込む。ここには、エラー分布に合わせられたガウス分布に関するいくつかの基本的事実があり、たとえば[7]を参照されたい。以下では、圧倒的な確率とは、nで無視できるほどのδの確率1-δを意味する。事実1β>0およびとし、ベクトルxをとして選択されるものとする。また、を任意ベクトルとし、とする。次に、圧倒的な確率で、とする。事実2を任意とする。分布およびの間の統計上の距離は、最大でも|y|/βqである。LWEn,m,q,βの困難性に関する証拠は、である場合、任意の所望のm=polynに対してLWEn,m,q,βを解決するために、最悪のケースでn次元格子上のある問題の近似から因数内までの量子減少を与えた、Regev[14]の結果に従うものである。本明細書で使用される場合、相対的な属性小さいは、から引き出される。一般に小さい値または整数とは、qβまでのサイズである。同様に大きい値または整数とは、qβよりはるかに大きいものである。2.2トラップドアサンプリング例示的暗号化方式の基本は、最初にAjtai[3]によって構築され、後にAlwenおよびPeikert[4]によって改良された、トラップドアサンプリングアルゴリズムである。トラップドアサンプリング手順は、ほぼ均一にランダムな行列を、と共に生成し、結果として、aTA=0modqであり、bTは可逆であり、cTのエントリは小さいたとえば、サイズOnlogqとなる。トラップドアTを使用して、Aに関連してLWE問題を解決することが可能であり、すなわち、y=Asxが与えられ、ここでxが任意の十分に短いベクトルである場合、これを使用してsを回復することができる。これは、以下のように計算することで実行され、Ty=TAsx=TAsTx=Txmodq上式で最後の等式は、Tの行が格子に属する結果として生じる。次に、Tおよびxの両方が小さいエントリを含むため、ベクトルTxの各エントリはqよりも小さく、TxmodqはTx自体である。最後に、T-1これはTが基底であり、最大階数を有するため、明確であるを乗じることでxが得られる。その後、LWE秘密sは、ガウス消去法によって回復可能である。AlwenおよびPeikert[4]の結果を以下に示す。補題1|3,4|入力1n、正整数q≧2、およびpolyn-有界正整数m≧8nlogqで、以下のような行列を出力する、効率的なアルゴリズムTrapSampleが存在する。Aは、統計的に全体にわたって均一に近い。Tの行は、格子の基底を形成する。Tおよび|T|∞のすべての行のユークリッドノルムはOnlogqによって境界が定められる。AlwenおよびPeikert[4]はO内に隠された定数がわずか20であるものと主張している。Tの行が格子全体にわたるため、detT=qnとなり、qと互いに素な任意のpについて、Tはpを法として可逆であることがわかることに留意されたい。3例示的暗号化方式nが安全性パラメータを示すものとする。システムの他のパラメータは3つの数m,p,q=polynq>pの奇数の素数であり、ガウスエラーパラメータはβ=1/polynである。これらのパラメータの具体的な例示的インスタンス化については、セクション3.2を参照されたい。これらのパラメータについて、メッセージスペースはm×m行列のセット、すなわちのセットである。公開鍵は行列であり、秘密鍵は行列であり、暗号文は行列である。例示的暗号化方式は、たとえば少なくとも以下の3つのアルゴリズムを含む。KeyGen1n:行列を、トラップドア行列と共に取得するために、補題1のトラップドアサンプリングアルゴリズムTrapSampleを実行する。公開鍵はAであり、秘密鍵はTである。:ランダム行列たとえば、均一にランダムな行列およびエラー行列を選択する。暗号文を出力する。ここで、pXは、行列Xの各エントリにpを乗じることを意味する。を設定し、を出力する。復号作業を理解するために、TA=0modq、さらにはTCTt=TpXBTtmodqを想起してみる。加えて、TpXBTtのすべてのエントリがqよりも小さい場合、整数上での等式、E=TCTtmodq=TpXBTt、したがって、T-1ETt-1=Bmodpも有する。これは、十分に小さいパラメータβを設定している限り、正しい復号を有し、結果として、高い確率でTpXBTtのすべてのエントリがq/2よりも小さくなることを意味する。注釈1復号時のTtおよびTt-1による右乗法はここでは冗長であり、代わりにのみを計算することが可能であることに留意されたい。右乗法は、以下で説明するように、積暗号文を復号する必要がある。BGN暗号化システムとは対照的に、例示的方式では、標準暗号文および積暗号文が同じスペース内にあり、どちらを復号するにも同じ復号手順を使用することができる。また、修正済みトラップドアT’=T-1modpT整数上の積を使用することによって、T-1およびTt-1による乗法の必要をなくすように最適化することができる。T’A=0modqを明確に有し、T’のエントリはT-1modp内のすべてのエントリが絶対値のポストp/2にあるためTのそれよりもそれほど大きくない。3.1準同形演算加法それぞれB1、B2に復号する2つのC1、C2が与えられた場合、いずれのエントリ内にもオーバフローがない限り、行列C=C1C2modqはB1B2modpに復号することが容易に理解されよう。具体的に言えば、C1=AS1pX1B1およびC1=AS2pX2B2を有する場合、C=C1C2=AS1S2pX1X2B1B2となり、これは、TpX1X2B1B2Tt内のすべてのエントリがq/2よりも小さい限り、B1B2として復号されることになる。正確なパラメータの例については、セクション3.2を参照されたい。乗法それぞれB1、B2を暗号化する2つのC1、C2が与えられた場合、積暗号文をC=C1Ct2modqとして計算する。C1=AS1pX1B1およびC2=AS2pX2B2を有する場合、となる。したがって、積暗号文はASpXBS’Atの形を有する。前述のように、TCTt=TpXBTtmodqであることがわかり、TpXBTtのすべてのエントリがq/2よりも小さい場合、整数上でE=TCTtmodq=TpXBTtを有し、したがって、T-1ETt-1=Bmodpとなる。以下で、これを動作可能にする例示的パラメータについて論じる。3.2パラメータの設定定理2安全性パラメータn、パラメータp、および任意のc=cn>0を固定する。q、m、βを、以下のように設定する。次に、パラメータp、n、m、q、βを伴う上記の例示的暗号化方式は、行列環上でのncの加法および1つの乗法任意の次数をサポートする。注釈3定理2では、非定常cに関するncの加法が可能であることに留意されたい。これが必要な可能性のある理由は、暗号文と大きい係数との線形組み合わせを採用するためである。具体的に言えば、暗号文行列C1、C2、...を有する場合、である限り、を準同形的に計算することができる。4拡張および適用4.1基礎となる環の動的選択パラメータが固定されると、平文に関する基礎となる環を、暗号化側によって適応的に選択できることに留意されたい。すなわち暗号化側は、同じ公開鍵Aおよび秘密鍵Tを用いて、基礎となる環を、任意のr≦pに対してZrとして選択するこれによって、暗号文をC=ASrXBとして計算することが可能であり、復号側はそれに応じて復号することが可能である。4.2公式プライバシ前述のように、この方式は、秘密鍵の保持者に対して公式プライバシを保証していない。たとえば、暗号文行列Cが与えられた場合、復号側が、この暗号文が識別の暗号化にゼロ行列の暗号化を乗じることによって取得されたケースと、ゼロ行列の2つの暗号化を乗じることによって取得されたケースとを、区別できる場合がある。この欠点は、標準的な技法によって修正可能である。第1に、定理2で指定されたようなqから、q’≧q2ωlognへ切り換えることで、係数のサイズをいくらか増加させる。次に、pを法として何らかの平文行列を暗号化する暗号文行列Cが与えられた場合、を設定することによって、これをブラインド化し、上式で、S、S’は、で均一であり、Xの各エントリは、この方式で使用されるパラメータβよりも超多項式的に大きいβ’を備えたから選択される。事実2を使用して、付加されたX内のノイズがこの暗号文の原点のすべてのトレースをかき消すことを示すことができる。すなわち、結果として生じる暗号文は、C=AS’1pX’BS’2tAtの形であり、この式で、S’1、S’2はランダムたとえば均一にランダムであり、Bは対応する平文であり、X’の分布はこの暗号文行列の出所とはほぼ無関係である。たとえ暗号化された平文行列がより大きな環Zp’内で選択された場合であっても、ブラインド化手順で使用されるパラメータpが元のp’を分割する限り、同じブラインド化技法が使用可能であることに留意されたい。4.3多項式および大きい整数の暗号化多項式または大きい数を暗号化するために、これらの多項式または数値上で演算を実行するために例示的方式によって本来サポートされている行列演算を活用させるような方法で、それらを行列として符号化する。まず多項式について考えると、2つの多項式の係数を2つの行列内に埋め込み、これらの行列の乗法によって、結果として生じる積多項式のすべての係数を生み出すような方法が良く知られている。たとえば、2つの多項式およびの場合、を使用することができる。上記の積行列は、単なる積多項式の係数ではないことを示すという点で、プライベートでないことに留意されたい。これは、行列の暗号化に、第1列および第1行、ならびにいずれの場所のランダムエントリにもゼロを追加することによって、容易に修正することができる。また、この単純な埋め込みは、暗号文拡張率Omを生じさせるm×m行列を使用して次数m-1多項式を暗号化するという点で無駄が多い。より経済的な埋め込みも可能であろう。整数乗法に移ると、2つのmビット整数を乗じる明らかな方法は、何らかのp≧22mについて、平文スペースを単にZpに設定することであるが、こうした大きい平文スペースでの作業は不都合な場合がある。したがって、小さい入力スペースで大きな整数乗法を実施するための方法を追及することが望ましい可能性がある。1つの可能性は、多項式に対して実行された技法と同じ技法を使用し、2進表現の整数を、x=2で評価された2進多項式とみなすことである。2つの整数、a、bが与えられた場合、何らかのp≧mについて、平文スペースZp上で対応する多項式の2進係数を暗号化する。積多項式の係数を読み取った後、整数上でを計算する。しかしながら、この解決策は、a、bに関する情報を、それらの整数積のみよりも多くリークすることから、プライベートではない。これをプライベートにするための1つの手法は、ランダム要素を、積行列の第1の行および列に追加し、結果として、とすることである。これによって秘密鍵保持者は、abmodpを回復することが可能となる。これを異なるpを用いて数回反復することで、中国剰余Chineseremainderingを使用してabを完全に回復することができる。4.42から2の復号例示的暗号化システムでは、2つの異なる公開鍵の下で2つの行列の暗号化を有する場合、これら2つの暗号文を乗算し、2つの平文行列の積に対応する暗号文を取得できることに留意されたい。その後、この暗号文は、2つの秘密鍵をまとめて引くことによって復号可能である。より詳細に言えば、2つの公開鍵A1、A2および対応する2つの秘密鍵T1、T2を有し、両方のペアが同じ素数qを法として定義されているものと想定してみる。また、わかりやすくするために、両方のペアが同じパラメータnおよびmを使用するものと仮定するが、この仮定は不要な場合がある。次に、2つの暗号文およびが与えられた場合、平文に対応する積暗号文を計算することができる。この平文は、T1およびT2の両方がわかっている場合、を設定することによって、回復可能である。4.5識別ベースおよび耐リーク性のBGN型暗号化次に、非限定的な例として、識別ベース暗号化および耐リーク性などのより高度な機能を得るために、単なる標準的な公開鍵暗号化を超えて、1乗法の準同形を拡張する方法が示される。これは、[10]からの異なる入力符号化を用いた2重Regev暗号化システムを、行列の特定の形についての例示的暗号化方式の特殊なケースとしてみなすことができる、単なる観察から得られ、したがって、同じ準同形演算をサポートしている。IBEランダムオラクルモデルにおけるは、Gentry等が[10]において、2重Regev鍵をマスタ鍵から導出する方法を示したことに直接付随し、耐リーク性は、Dodis等が[6]において、2重Regev暗号化システムが耐リーク性であることを証明したことに付随している。[10]からの2重Regev暗号化システムを想起してみると、公開鍵は行列であり、秘密鍵は2重内の1つのショートベクトル、すなわちショートであることから、結果としてとなる。さらに、内の最終エントリは、常に-1である。[10]に記載されたような暗号化システムでは、ビットbは、均一なベクトルおよび小さいエラーベクトルを選択し、その後、暗号文ベクトルの1つのエントリの最上位ビット内にビットbを符号化すること、すなわち、によって暗号化される。しかしながら、準同形を得るためには、を設定して、最下位ビット内の入力を符号化する。この入力符号化により、2重Regev暗号化システムを例示的暗号化システムの特殊なケースとしてみなすことが可能であり、ここで公開鍵は同じ行列Aであり、秘密鍵は最大階数行列ではない代わりに、階数-1行列である。行列T、S、X、Bは、以下のように定義される。すなわち、Tの最上行以外はすべてゼロであり、S、Xの右端列以外はすべてゼロであり、Bの右下の要素以外はすべてゼロである。意味論的安全性は、LWEに従うことが容易に示される。鍵は単なる2重Regev鍵であるため、[6]と同じ論証により、たとえ秘密鍵の部分的リークに直面しても依然としてセキュアであることを示す。また[10]では、識別ベースの設定において、この秘密鍵がランダムオラクルモデルにおけるマスタ秘密鍵からどのように計算できるかも示された。これらの選択肢では、ほとんどの暗号文行列はゼロであるため、暗号文として出力することが必要であるのはすべて、実際には1つのベクトルこれが暗黙的に、行列を符号化する。その後、準同形演算が暗黙行列に適用され、すなわち、加法は単なる要素的にqを法とする加法であり、2つのベクトルの乗法は外積演算である。暗号文行列を復号するために、秘密鍵ベクトルによって左右から乗算し、第1にqを法とする結果を、次に2を法とする結果を減じる。平文行列Bの特殊な形により、これは、左側をTで乗算し、右側をTtで乗算した後、結果の右下の要素のみを取ることと同じである。行列Tはもはや逆数を有さないが、依然として隠されたビットbを回復することができる。これは、を有することから、逆数による乗算の必要なしに、単に、を設定することで実行される。2重暗号化システムではum=-1であることを想起すると、この手順によって、実際には右側の解が与えられる。4.6単純な復号前述のように、暗号文は以下に従って復号される。B=T-1TCTtmodqTt-1modpその拡張の1つが、これに代わって単純な復号公式を使用することである。B=T-1TCmodqmodp単純な復号は、暗号文が乗法の対象でない限り、復号するために十分正確でたとえば十分に適切でなければならない。5他の例示的実施形態図1は、本発明の例示的実施形態に従った、例示的暗号化動作/機能を示す。図2は、本発明の例示的実施形態に従った、例示的復号動作/機能を示す。図3は、本発明の例示的実施形態に従った、例示的鍵生成KeyGen動作/機能を示す。図4は、本発明の例示的実施形態に従った、例示的暗号文加法動作/機能たとえば、i暗号文、nc暗号文についてを示す。図5は、本発明の例示的実施形態に従った、例示的暗号文乗法動作/機能たとえば、2つの暗号文C1およびC2についてを示す。図6は、本発明の例示的実施形態に従った、例示的単純復号動作/機能を示す。図7は、ある例示的実施形態が内部に実装可能な200を示すブロック図である。ある例示的実施形態では、システム200に従って、図1~図6に示された様々なブロックをまとめてまたは別個に実装可能である。システム200は、ある実施形態では少なくとも1つのプロセッサ204を含むことが可能な、少なくとも1つの回路202を含むことができる。システム200は、少なくとも1つのメモリ206たとえば揮発性メモリデバイスまたは少なくとも1つのストレージ208あるいはその両方を含むこともできる。ストレージ208は、不揮発性メモリデバイスたとえばEEPROM、ROM、PROM、RAM、DRAM、SRAM、フラッシュ、ファームウェア、プログラマブル論理など、磁気ディスクドライブ、光ディスクドライブ、またはテープドライブ、あるいはそれらすべてを、非限定的な例として含むことができる。ストレージ208は、内部ストレージデバイス、接続ストレージデバイス、またはネットワークアクセス可能ストレージデバイス、あるいはそれらすべてを、非限定的な例として備えることができる。システム200は、メモリ206内にロードし、プロセッサ204または回路202あるいはその両方によって実行可能な、コード212たとえばプログラムコードを含む、少なくとも1つのプログラム論理210を含むことができる。ある例示的実施形態では、コード212を含むプログラム論理210を、ストレージ208内に格納することができる。ある他の実施形態では、プログラム論理210は回路202内に実装可能である。したがって、図7は、プログラム論理210を他の要素とは別に示しているが、プログラム論理210は、メモリ206または回路202あるいはその両方内に実装可能である。システム200は、少なくとも1つの他のシステム、デバイス、または装置、あるいはそれらすべてと通信可能な、少なくとも1つの通信構成要素214を含むことができる。通信構成要素214は、情報の送受信を行うように構成されたトランシーバ、情報を送信するように構成された送信器、または情報を受信するように構成された受信器、あるいはそれらすべてを含むことができる。非限定的な例として、通信構成要素214は、モデムまたはネットワークカードを備えることができる。図7のシステム200は、非限定的な例として、デスクトップコンピュータ、ポータブルコンピュータ、またはサーバなどの、コンピュータまたはコンピュータシステム内で具体化可能である。図7に示されたシステム200の構成要素は、非限定的な例として、1つまたは複数の内部バス、接続、ワイヤ、またはプリント回路基板、あるいはそれらすべてを使用して、まとめて接続または結合することができる。本発明の例示的実施形態に従って、回路202、プロセッサ204、メモリ206、ストレージ208、プログラム論理210、または通信構成要素214、あるいはそれらすべてのうちの、1つまたは複数が、本明細書で考察される様々なアイテムたとえば、行列、変数、等式、公式、動作、動作論理、論理のうちの、1つまたは複数を格納することができることを理解されたい。非限定的な例として、上記で識別された構成要素のうちの1つまたは複数は、たとえば暗号化される、復号の結果として生じる情報B、またはたとえば復号される、暗号化の結果として生じる暗号文C、あるいはその両方の、受信または格納、あるいはその両方を実行することができる。他の非限定的な例として、上記で識別された構成要素のうちの1つまたは複数は、本明細書で説明されるような暗号化機能または復号機能あるいはその両方の、受信または格納、あるいはその両方を実行することができる。以下で、本発明の様々な非限定的な例示的実施形態について、さらに説明する。下記の例示的実施形態には、わかりやすくするために別々の番号が付けられている。この番号付けは、1つまたは複数の例示的実施形態の態様が、1つまたは複数の他の態様または例示的実施形態に関連して実施可能であるため、様々な例示的実施形態を完全に分離するものと解釈されるべきではない。1例示的一実施形態で、図8に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを受信すること301、および、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化すること302を含み、暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である。前述のコンピュータ読み取り可能記憶媒体であって、およびであり、ここでnは安全性パラメータを示し、m,q=polynであり、はエラー分布であり、βは、β=1/polynによって与えられるガウスエラーパラメータである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は準同形であり、双一次形式たとえば、多項式的に多くの加法および1つの乗法の計算をサポートする。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、p=2であり、情報Bは2進値の行列を備える。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、c=cn>0、q>220p2c43n3c4log5n、およびである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は、行列環上でいずれかの次数でncの加法および1つの乗法をサポートする。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、動作は、暗号文Cを出力することをさらに含む。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、pは、情報を含むある次数のスペースである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、pはある次数のスペース、およびである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は、秘密鍵の保持者が、復号機能の公式の知識をさらに取得することなしに暗号文を復号するよう構成されるように、公式プライベートなセキュアな計算をさらに実行可能にする。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、q>pである。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は、任意数の加法を伴う対数乗法深さの回路のための準同形暗号化方式を備え、準同形暗号化方式の安全性は、エラーでの習得問題の困難性に基づく。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、T、X、およびBのエントリが小さいため、T2XB内のエントリはqより少ない。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号文Cのサイズは平文Bのサイズのおよそたとえば実質上3倍である。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号化方式は鍵生成機能をさらに備え、鍵生成機能は、入力として1n、q、およびmを受信し、少なくとも1つの公開鍵Aおよび少なくとも1つの秘密鍵Tを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、鍵生成機能は、入力1n、正整数q≧2、およびpolynで境界が定められた正整数m≧8nlogq上で、行列およびを出力する、トラップドアサンプリングアルゴリズムを実行することによって動作する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、Aは上で統計的に均一に近く、Tの行は格子の基底を形成し、Tの行のユークリッドノルムはOnlogqによって境界が定められる。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、TA=0modqであり、Tは可逆であり、Tのエントリは小さい。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、暗号方式は復号機能をさらに備え、復号機能は、入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、である。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。2本発明の他の例示的実施形態で、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを記憶するように構成された、少なくとも1つの記憶媒体と、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化するように構成された、少なくとも1つのプロセッサとを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。3本発明の他の例示的実施形態で、図8に示されるように、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを、少なくとも1つのプロセッサによって受信すること301、および、暗号文Cを取得するために暗号化方式の暗号化機能に従って、情報Bを少なくとも1つのプロセッサによって暗号化すること302を含む、方法であって、暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である。上記いずれかのような方法であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。4本発明の他の例示的実施形態で、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを記憶するための手段と、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化するための手段とを備えた、装置であって、暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である。上記のような装置であって、記憶するための手段は少なくとも1つの記憶媒体、メモリ、またはメモリ媒体を備え、暗号化するための手段は、少なくとも1つのプロセッサ、少なくとも1つの回路、または少なくとも1つの集積回路を備える。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。5本発明の他の例示的実施形態で、暗号化機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを記憶するように構成された、記憶回路と、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化するように構成された、暗号化回路とを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数である。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。6本発明の他の例示的実施形態で、図9に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを受信すること401、および、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号すること402を含み、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記のようなコンピュータ読み取り可能記憶媒体であって、動作は、情報Bを出力することをさらに含む。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、少なくとも1つの秘密鍵Tが少なくとも1つの公開鍵Aに対応する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、少なくとも1つの秘密鍵Tは対称鍵である。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。7本発明の他の例示的実施形態では、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するように構成された、少なくとも1つの記憶媒体と、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号するように構成された、少なくとも1つのプロセッサとを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。8本発明の他の例示的実施形態で、図9に示されるように、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを受信すること401、および、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号すること402を含む、方法であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記いずれかのような方法であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。9本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するための手段と、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号するための手段とを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記のような装置であって、記憶するための手段は少なくとも1つの記憶媒体、メモリ、またはメモリ媒体を備え、復号するための手段は、少なくとも1つのプロセッサ、少なくとも1つの回路、または少なくとも1つの集積回路を備える。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。10本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するように構成された、記憶回路と、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号するように構成された、復号回路とを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。11本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを受信すること、および、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化することを含み、暗号化方式は少なくとも1つの公開鍵Aおよび少なくとも1つの秘密鍵Aに対応する少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、qは奇数の素数であり、pは整数であり、q>pであり、暗号化機能は入力としてAおよびBを受信し、暗号文Cをとして出力し、この式でSはランダム行列であって、であり、Xはエラー行列であって、であり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータであり、復号機能は入力としてTおよびCを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力し、暗号化方式は準同形であり、双一次形式の計算たとえば、多項式的に多くの加法および1つの乗法をサポートする。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータプログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。12本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って第1の暗号文C1として暗号化されることになる第1の情報B1、および暗号化方式に従って第2の情報B2として復号されることになる第2の暗号文C2のうちの、少なくとも1つを受信すること、ならびに、第1の暗号文C1を取得するために暗号化方式の暗号化機能に従って第1の情報B1を暗号化すること、および第2の情報B2を取得するために暗号化方式の復号機能に従って第2の暗号文C2を復号することのうちの、少なくとも1つを含み、暗号化方式は、少なくとも1つの公開鍵Aおよび少なくとも1つの公開鍵Aに対応する少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数であり、復号機能は、入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCTtmodqTt-1modpに従って情報Bを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータプログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。13本発明の他の例示的実施形態で、図10に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って複数の暗号文Ciとして暗号化されることになる複数の情報Biを受信すること501、それぞれの暗号文Ciを取得するために暗号化方式の暗号化機能に従って複数の情報Biのそれぞれを暗号化すること502、2次多項式をとして暗号文Ciに適用することによって結果の暗号文Cpolyを計算することであって、合計は指数iおよびjのサブセットを介する、計算すること503、ならびに、結果として生じる情報Bpolyを取得するために暗号化方式の復号機能に従って結果の暗号文Cpolyを復号すること504、を含み、暗号化方式は、少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、複数の情報Bi、暗号文Ci、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Ciをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数であり、iは整数であり、jは整数であり、復号機能は、入力として少なくとも1つの秘密鍵Tおよび結果の暗号文Cpolyを受信し、指数iおよびjのサブセットを介するに従って結果として生じる情報Bpolyを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータプログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。14本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを受信すること、および、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号することを含み、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCmodqmodpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータプログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。15本発明の他の例示的実施形態では、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するように構成された、少なくとも1つの記憶媒体と、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号するように構成された、少なくとも1つのプロセッサとを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCmodqmodpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。16本発明の他の例示的実施形態で、図9に示されるように、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを受信すること601、および、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号すること602を含む、方法であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCmodqmodpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記いずれかのような方法であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。17本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するための手段と、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号するための手段とを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCmodqmodpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記のような装置であって、記憶するための手段は少なくとも1つの記憶媒体、メモリ、またはメモリ媒体を備え、復号するための手段は、少なくとも1つのプロセッサ、少なくとも1つの回路、または少なくとも1つの集積回路を備える。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。18本発明の他の例示的実施形態で、復号機能を備える暗号化方式に従って情報Bとして復号されることになる暗号文Cを記憶するように構成された、記憶回路と、情報Bを取得するために暗号化方式の復号機能に従って暗号文Cを復号するように構成された、復号回路とを備える、装置であって、暗号化方式は少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、および少なくとも1つの秘密鍵Tは行列であり、復号機能は入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCmodqmodpに従って情報Bを出力し、この式でpは整数であり、qは奇数の素数である。上記いずれかのような装置であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。19本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って暗号文Cとして暗号化されることになる情報Bを受信すること、および、暗号文Cを取得するために暗号化方式の暗号化機能に従って情報Bを暗号化することを含み、暗号化方式は少なくとも1つの公開鍵Aおよび少なくとも1つの秘密鍵Aに対応する少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、およびであり、この式でnは安全性パラメータを示し、m,q=polynであり、qは奇数の素数であり、pは整数であり、q>pであり、暗号化機能は入力としてAおよびBを受信し、暗号文Cをとして出力し、この式でSはランダム行列であって、であり、Xはエラー行列であって、であり、この式ではエラー分布であり、βは、β=1/polynによって得られるガウスのエラーパラメータであり、復号機能は入力としてTおよびCを受信し、B=T-1TCmodqmodpに従って情報Bを出力し、暗号化方式は準同形であり、多項式的に多くの加法をサポートする。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータプログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。20本発明の他の例示的実施形態で、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って第1の暗号文C1として暗号化されることになる第1の情報B1、および暗号化方式に従って第2の情報B2として復号されることになる第2の暗号文C2のうちの、少なくとも1つを受信すること、ならびに、第1の暗号文C1を取得するために暗号化方式の暗号化機能に従って第1の情報B1を暗号化すること、および第2の情報B2を取得するために暗号化方式の復号機能に従って第2の暗号文C2を復号することのうちの、少なくとも1つを含み、暗号化方式は、少なくとも1つの公開鍵Aおよび少なくとも1つのの公開鍵Aに対応する少なくとも1つの秘密鍵Tを使用し、情報B、暗号文C、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Cをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数であり、復号機能は、入力として少なくとも1つの秘密鍵Tおよび暗号文Cを受信し、B=T-1TCmodqmodpに従って情報Bを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータプログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。21本発明の他の例示的実施形態で、図12に示されるように、動作を実行するために機械によって実行可能な命令のプログラムを有形に具体化するコンピュータ読み取り可能記憶媒体であって、動作は、暗号化機能および復号機能を備える暗号化方式に従って複数の暗号文Ciとして暗号化されることになる複数の情報Biを受信すること701、それぞれの暗号文Ciを取得するために暗号化方式の暗号化機能に従って複数の情報Biのそれぞれを暗号化すること702、合計をとして暗号文Ciに適用することによって結果の暗号文Csumを計算することであって、合計は指数iのサブセットを介する、計算すること703、ならびに、結果として生じる情報Bsumを取得するために暗号化方式の復号機能に従って結果の暗号文Csumを復号すること704、を含み、暗号化方式は、少なくとも1つの秘密鍵Tに対応する少なくとも1つの公開鍵Aを使用し、複数の情報Bi、暗号文Ci、少なくとも1つの公開鍵A、および少なくとも1つの秘密鍵Tは行列であり、暗号化機能は入力として少なくとも1つの公開鍵Aおよび情報Bを受信し、暗号文Ciをとして出力し、この式でSはランダム行列であり、Xはエラー行列であり、pは整数であり、qは奇数の素数であり、iは整数であり、jは整数であり、復号機能は、入力として少なくとも1つの秘密鍵Tおよび結果の暗号文Csumを受信し、指数iのサブセットを介するBsum=T-1TCsummodqmodp=ΣiBimodpに従って結果として生じる情報Bsumを出力する。上記いずれかのようなコンピュータ読み取り可能記憶媒体であって、本明細書で説明された本発明の例示的実施形態の1つまたは複数の追加の態様をさらに備える。方法、装置、またはコンピュータプログラムであって、前述のコンピュータ読み取り可能記憶媒体に対応する。本明細書で論じられる本発明の例示的実施形態は、動作を実行するために機械あるいはコンピュータまたはプロセッサによって実行可能な命令のプログラムたとえば、プログラム、コンピュータプログラム、プログラムコード、プログラム命令を有形に具体化するたとえば記憶する、たとえば、機械によって、コンピュータによって、プロセッサによって読み取り可能な、プログラムストレージデバイスたとえば、少なくとも1つのメモリ、少なくとも1つのコンピュータ読み取り可能記憶媒体と関連して実装可能である。動作は、本発明の例示的実施形態を使用するたとえば実施するステップ、または方法のステップを含む。さらに、図8~図12に示されたブロックは、1つまたは複数の構成要素、回路、チップ、装置、プロセッサ、コンピュータプログラム、または機能ブロック、あるいはそれらすべてによって実行される、1つまたは複数の機能または動作あるいはその両方に対応するものとみなすことができる。上記のいずれかまたはすべてあるいはその両方は、本明細書で説明された本発明の例示的実施形態に従って動作を実行可能にする、任意の実施可能なソリューションまたは配置構成内に実装可能である。加えて、図8~図12に示されたブロックの配置構成は単なる例であり、非限定的であるものとみなすべきである。図8~図12に示されたブロックは、本発明の例示的実施形態のうちの1つまたは複数を実装するように、任意のたとえば任意の好適な、実施可能な、または実現可能な、あるいはそれらすべての順序で、または同時にたとえば好適な、実施可能な、または実現可能なように、あるいはそれらすべてのように、あるいはその両方で、実行可能な、1つまたは複数の機能または動作あるいはその両方に対応可能であることを理解されたい。加えて、本発明の1つまたは複数の他の例示的実施形態を実装するように、1つまたは複数の追加の機能、動作、またはステップ、あるいはそれらすべてを、図8~図12に示されたそれらに関連して使用することができる。すなわち、図8~図12に示された本発明の例示的実施形態は、任意の組み合わせたとえば、好適な、実施可能な、または実現可能な、あるいはそれらすべての任意の組み合わせで、1つまたは複数の他の態様に関連して使用、実装、または実施可能であり、図8~図12に示されたステップ、ブロック、動作、または機能、あるいはそれらすべてにのみ限定されるものではない。図8~図12の流れ図およびブロック図は、本発明の様々な例示的実施形態に従った、システム、方法、およびコンピュータプログラム製品の、可能な例示的実装のアーキテクチャ、機能性、および動作を示すものである。この点で、流れ図またはブロック図内の各ブロックは、指定された論理機能を実装するための1つまたは複数の実行可能命令を含む、コードのモジュール、セグメント、または一部を表すことができる。いくつかの代替の実装では、ブロック内に示された機能は、図に示された順序とは異なる順序で発生可能であることにも留意されたい。たとえば、連続して示される2つのブロックは、関連する機能性に応じて、実際にはほぼ同時に実行されるか、または時には逆の順序で実行されることが可能である。ブロック図または流れ図あるいはその両方の各ブロック、および、ブロック図または流れ図あるいはその両方におけるブロックの組み合わせは、非限定的な例として、指定された機能または行為を実行する特定用途向けハードウェアベースのシステム、あるいは、特定用途向けのハードウェアおよびコンピュータ命令の組み合わせによって実装可能であることにも留意されたい。さらに、本明細書で説明されたパラメータ、動作、および機能に使用される様々な名前は、これらのパラメータ、動作、および機能が任意の好適な名前によって識別可能な場合、いかなる点においても限定されることを意図するものではない。本明細書で説明された任意およびすべての手段またはステップならびに機能要素の対応する構造、材料、行為、および等価物は、具体的に請求された場合に他の請求要素と組み合わせて機能を実行するための、任意の構造、材料、または行為を含むことが意図される。本発明の例示的実施形態の説明は、例示および説明の目的で提示されており、本発明の開示された形を網羅するかまたはこれらに限定されることは意図されていない。当業者であれば、本発明の範囲および趣旨を逸脱することなく、多くの修正および変形が明らかとなろう。例示的実施形態は、本発明の例示的実施形態の原理および実際の適用例を最も良く説明するため、ならびに、他の当業者が、企図された特定用途に好適な様々な修正を伴う様々な例示的実施形態に関して本発明を理解できるようにするために、選択および説明されたものである。当業者であれば理解されるように、本発明の例示的実施形態の態様は、非限定的な例として、システム、方法、またはコンピュータプログラム製品として具体化することが可能である。したがって、本発明の例示的実施形態の態様は、非限定的な例として、全体がハードウェア実施形態、全体がソフトウェア実施形態ファームウェア、常駐ソフトウェア、マイクロコードなどを含む、あるいは、本明細書ではすべて一般に回路、モジュール、またはシステムと呼ばれるソフトウェアとハードウェアの態様を組み合わせた実施形態の、形を取ることができる。さらに、本発明の例示的実施形態の態様は、その上にコンピュータ読み取り可能プログラムコードが具体化された、1つまたは複数のコンピュータ読み取り可能媒体内に具体化された、コンピュータプログラム製品の形を取ることができる。1つまたは複数のコンピュータ読み取り可能媒体の任意の組み合わせが使用可能である。コンピュータ読み取り可能媒体は、コンピュータ読み取り可能信号媒体またはコンピュータ読み取り可能記憶媒体とすることができる。非限定的な例として、コンピュータ読み取り可能記憶媒体は、電子、磁気、光、電磁、赤外線、または半導体のシステム、装置、またはデバイス、あるいはそれらの任意の好適な組み合わせのうちの、1つまたは複数を含むことができる。コンピュータ読み取り可能記憶媒体のさらに特定の非限定的な例は、1本または複数本のワイヤを有する電気接続、ポータブルコンピュータディスケット、ハードディスク、ランダムアクセスメモリRAM、読み取り専用メモリROM、消去可能プログラマブル読み取り専用メモリEPROMまたはフラッシュメモリ、光ファイバ、ポータブルコンパクトディスク読み取り専用メモリCD-ROM、光ストレージデバイス、磁気ストレージデバイス、または、それらの任意の好適な組み合わせを含む。本書との関連において、コンピュータ読み取り可能記憶媒体は、命令実行システム、装置、またはデバイスたとえばコンピュータまたはプロセッサによって、あるいはそれらに関連して使用するための、プログラムを含むかまたは記憶するように構成/動作可能な、任意の有形媒体とすることができる。コンピュータ読み取り可能信号媒体は、たとえばベースバンド内に、または搬送波の一部として、内部にコンピュータ読み取り可能プログラムコードが具体化された、伝搬データ信号を含むことができる。こうした伝搬信号は、電磁、光、またはそれらの任意の好適な組み合わせを含むがこれらに限定されない、任意の様々な形を取ることができる。コンピュータ読み取り可能信号媒体は、コンピュータ読み取り可能記憶媒体ではなく、命令実行システム、装置、またはデバイスによって、あるいはそれらに関連して使用するためのプログラムの通信、伝搬、または移送が可能な、任意のコンピュータ読み取り可能媒体とすることができる。コンピュータ読み取り可能媒体上に具体化されたプログラムコードは、ワイヤレス、ワイヤライン、ワイヤード、光ファイバケーブル、RF、またはそれらの任意の好適な組み合わせを含むがこれらに限定されない、任意の適切な媒体を使用して伝送することができる。本発明の例示的実施形態の態様に関する動作を実施するためのコンピュータプログラムコードは、非限定的な例として、Java、Smalltalk、またはCなどのオブジェクト指向プログラミング言語、および、Cプログラミング言語または同様のプログラミング言語などの従来の手続き型プログラミング言語を含む、1つまたは複数のプログラミング言語の任意の組み合わせで作成可能である。プログラムコードは、非限定的な例として、全体がユーザのコンピュータ上で、一部がユーザのコンピュータ上で、スタンドアロン型ソフトウェアパッケージとして、一部がユーザのコンピュータ上および一部がリモートコンピュータ上で、あるいは、全体がリモートコンピュータまたはサーバ上で、実行可能である。後者のシナリオでは、リモートコンピュータは、非限定的な例として、ローカルエリアネットワークLANまたはワイドエリアネットワークWANを含む、任意のタイプのネットワークを介して、ユーザのコンピュータに接続することができるか、あるいは、たとえば、インターネットサービスプロバイダを使用してインターネットを介して外部コンピュータに接続することができる。本明細書では、本発明の様々な例示的実施形態に従った方法、装置システム、およびコンピュータプログラム製品の、流れ図またはブロック図あるいはその両方を参照しながら、本発明の例示的実施形態の態様について説明される。流れ図またはブロック図あるいはその両方の各ブロック、および流れ図またはブロック図あるいはその両方におけるブロックの組み合わせは、非限定的な例として、コンピュータプログラム命令によって実装可能であることを理解されよう。これらのコンピュータプログラム命令は、非限定的な例として、コンピュータまたは他のプログラマブルデータ処理装置のプロセッサを介して実行する命令が、流れ図またはブロック図あるいはその両方のブロック内に指定された機能/行為を実装するための手段を作成するように、機械を生成するために汎用コンピュータ、特定用途向けコンピュータ、または他のプログラマブルデータ処理装置のプロセッサに提供可能である。コンピュータ、他のプログラマブルデータ処理装置、または他のデバイスに、特定の様式で機能するよう指示可能な、これらのコンピュータプログラム命令は、コンピュータ読み取り可能媒体内に記憶された命令が、流れ図またはブロック図あるいはその両方のブロック内に指定された機能/行為を実装する命令を含む製品を製造するように、コンピュータ読み取り可能媒体内に記憶することも可能である。コンピュータプログラム命令は、コンピュータまたは他のプログラマブル装置上で実行する命令が、流れ図またはブロック図あるいはその両方のブロック内に指定された機能/行為たとえば、本発明の例示的実施形態を実装するためのプロセスを提供するような、コンピュータ実装プロセスを生成するために、一連の動作ステップを、コンピュータ、他のプログラマブルデータ処理装置、または他のデバイス上で実行させるために、コンピュータ、他のプログラマブルデータ処理装置、または他のデバイス上にロードすることも可能である。接続された、結合された、またはそれらの変形の用語のいずれの使用も、識別された要素間での、直接または間接的な、任意のこうした接続または結合を示すものと解釈されるべきである。非限定的な例として、1つまたは複数の中間要素が結合された要素間に存在可能である。識別された要素間の接続または結合は、非限定的な例として、説明された例示的実施形態に従い、物理的、電気的、磁気的、論理的、またはそれらの任意の好適な組み合わせとすることができる。非限定的な例として、接続または結合は、1つまたは複数のプリントされた電気接続、ワイヤ、ケーブル、媒体、またはそれらの任意の好適な組み合わせを含むことができる。一般に、本発明の様々な例示的実施形態は、ソフトウェア、ハードウェア、論理、特定用途向け回路、またはそれらの任意の組み合わせなどの、異なる媒体内で実装可能である。非限定的な例として、いくつかの態様はコンピューティングデバイス上で実行可能なソフトウェア内に実装可能である一方で、他の態様はハードウェア内に実装可能である。前述の説明では、例示的かつ非限定的な例を用いて、本発明を実施するために発明者等によって現在企図されている最良の方法および装置の完全かつ有益な説明を提供してきた。しかしながら、当業者であれば、添付の図面および添付の特許請求の範囲に関連して前述の説明を読めば、これらに照らした修正および適合が明らかとなろう。しかしながら、すべてのこうした修正および同様の修正は、依然として本発明の例示的実施形態の教示の範囲内にあることになる。さらに、本発明の好ましい実施形態のいくつかの特徴は、対応する他の特徴を使用することなく、利益を得るために使用することができる。したがって前述の説明は、本発明の原理を限定するのではなく、単に例示するものとみなすことができる。"