【手続補正書】
【提出日】平成25年12月11日(2013.12.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
暗号法で使用する数学的なペアリングを決定するためのコンピュータによって実行される方法であって、
要素の第一のセットに関連する複数の反転を統合して統合された複数の反転を得るステップであって、前記要素の第一のセットは第一の曲線ポイントを含む、ステップと、
前記統合された複数の反転を使用して前記要素の第一のセットに関連する数学的なペアリングを決定するステップと、
要素の第二のセットを受領するステップと、
前記要素の第二のセットに含まれる第二の曲線ポイントが前記第一の曲線ポイントと同じ要素であることを判別するステップと、
前記要素の第二のセットに関連する数学的なペアリングを決定する際に前記統合された複数の反転の少なくとも一部を再使用するステップとを含むことを特徴とする方法。
【請求項２】
前記複数の反転を統合することが、前記複数の反転を統合して単一の反転にすることを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記要素の第一のセットに関連する数学的なペアリングまたは前記要素の第二のセットに関連する数学的なペアリングの少なくとも一方が曲線に対応する、請求項１記載の方法。
【請求項４】
前記要素の第一のセットに関連する数学的なペアリングの決定または前記要素の第二のセットに関連する数学的なペアリングの決定の少なくとも一方が、スカラの２進表現に沿ってアフィン座標内で数学的なペアリングを決定することを含む、請求項１記載の方法。
【請求項５】
前記スカラが右から左へ読み取り可能である、請求項４記載の方法。
【請求項６】
前記要素の第一のセットに関連する数学的なペアリングの決定および前記要素の第二のセットに関連する数学的なペアリングの決定を複数のプロセッサ上で並列化することを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記統合された複数の反転の出力が、前記要素の第一のセットに関連する数学的なペアリングの決定または前記要素の第二のセットに関連する数学的なペアリングの決定の少なくとも一方に際してのラインの関数の更新に関連する傾きの値を含むことを特徴とする請求項１に記載の方法。
【請求項８】
請求項１ないし７のうちいずれか一項記載の方法であって、数学的なペアリングの決定はラインの関数を評価することを含み、前記ラインの傾き値の計算が反転を使う、方法。
【請求項９】
暗号法で使用する数学的なペアリングを決定するシステムであって、
一つまたは複数のユニットと、
命令を記憶しているメモリとを有しており、前記命令は前記一つまたは複数の処理ユニットの少なくとも一部に：
要素の第一のセットに関連する複数の反転を統合して統合された複数の反転を得るステップであって、前記要素の第一のセットは第一の曲線ポイントを含む、ステップと、
前記統合された複数の反転を使用して前記要素の第一のセットに関連する数学的なペアリングを決定するステップと、
要素の第二のセットを受領するステップと、
前記要素の第二のセットに含まれる第二の曲線ポイントが前記第一の曲線ポイントと同じ要素であることを判別するステップと、
前記要素の第二のセットに関連する数学的なペアリングを決定する際に前記統合された複数の反転の少なくとも一部を再使用するステップとを含む方法を実行させるものである、システム。
【請求項１０】
前記複数の反転を統合することが、前記複数の反転を統合して単一の反転にすることを含むことを特徴とする請求項９に記載のシステム。
【請求項１１】
前記要素の第一のセットに関連する数学的なペアリングまたは前記要素の第二のセットに関連する数学的なペアリングの少なくとも一方が曲線に対応する、請求項９記載のシステム。
【請求項１２】
前記要素の第一のセットに関連する数学的なペアリングの決定または前記要素の第二のセットに関連する数学的なペアリングの決定の少なくとも一方が、スカラの２進表現に沿ってアフィン座標内で数学的なペアリングを決定することを含む、請求項９記載のシステム。
【請求項１３】
前記スカラが右から左へ読み取り可能である、請求項１２記載のシステム。
【請求項１４】
前記方法が、前記要素の第一のセットに関連する数学的なペアリングの決定および前記要素の第二のセットに関連する数学的なペアリングの決定を複数のプロセッサ上で並列化することを含むことを特徴とする請求項９に記載のシステム。
【請求項１５】
前記統合された複数の反転の出力が、前記要素の第一のセットに関連する数学的なペアリングの決定または前記要素の第二のセットに関連する数学的なペアリングの決定の少なくとも一方に際してのラインの関数の更新に関連する傾きの値を含むことを特徴とする請求項９に記載の方法。
【請求項１６】
命令を記憶しているコンピュータ可読媒体であって、前記命令は一つまたは複数の処理ユニットに：
要素の第一のセットに関連する複数の反転を統合して統合された複数の反転を得るステップであって、前記要素の第一のセットは第一の曲線ポイントを含む、ステップと、
前記統合された複数の反転を使用して前記要素の第一のセットに関連する数学的なペアリングを決定するステップと、
要素の第二のセットを受領するステップと、
前記要素の第二のセットに含まれる第二の曲線ポイントが前記第一の曲線ポイントと同じ要素であることを判別するステップと、
前記要素の第二のセットに関連する数学的なペアリングを決定する際に前記統合された複数の反転の少なくとも一部を再使用するステップとを含む方法を実行させるものである、コンピュータ可読媒体。
【請求項１７】
前記複数の反転を統合することが、前記複数の反転を統合して単一の反転にすることを含むことを特徴とする請求項１６に記載のコンピュータ可読媒体。
【請求項１８】
前記要素の第一のセットに関連する数学的なペアリングまたは前記要素の第二のセットに関連する数学的なペアリングの少なくとも一方が曲線に対応する、請求項１６記載のコンピュータ可読媒体。
【請求項１９】
前記要素の第一のセットに関連する数学的なペアリングの決定または前記要素の第二のセットに関連する数学的なペアリングの決定の少なくとも一方が、スカラの２進表現に沿ってアフィン座標内で数学的なペアリングを決定することを含む、請求項１６記載のコンピュータ可読媒体。
【請求項２０】
前記スカラが右から左へ読み取り可能である、請求項１９記載のコンピュータ可読媒体。
【請求項２１】
前記統合された複数の反転の出力が、前記要素の第一のセットに関連する数学的なペアリングの決定または前記要素の第二のセットに関連する数学的なペアリングの決定の少なくとも一方に際してのラインの関数の更新に関連する傾きの値を含むことを特徴とする請求項１６に記載のコンピュータ可読媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
一実施形態では、曲線についての有限体において、乗算と反転（たとえば、乗法的逆元すなわち逆数を識別すること）の両方が、ペアリング演算について実行される。反転の実行は、通常、乗算よりも計算コストが高い。たとえば、計算における反転と乗算の比は、しばしば８０対１となることがあるが、それというのも、曲線のポイントで使用される座標系は、普通、アフィンから射影に変更されて、多くの反転を低減させるからである。反転の決定の実例として、ゼロでない実数ｘの乗法的逆元を見積もるために、数ｙを繰り返し２ｙ−ｘｙ2で置換することができる。この例では、ｙへの変更が閾値内にあるとき、ｙは、ｘの乗法的逆元の近似値である。この例は、単に説明するためのものであり、複素数など特に他のタイプの数について、反転を決定するための他の技法があることは理解されよう。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３２
【補正方法】変更
【補正の内容】
【００３２】
たとえば、例示的な方法３００では、アフィン座標系で動作している間、反転を組み合せ、それらを同時に決定することにより、多数の反転を大幅に減らすことができる。一実施形態では、ペアリング計算においてアフィン座標系を使用するとき、それぞれの倍加（たとえば乗算）および追加の動作は、有限体の反転を使用して、後続の動作において評価されるラインの傾斜値を計算する。この実施形態では、たとえば、「モンゴメリー・トリック」を使用して、単一の反転および３（ｌ−１）回の乗算でｌ回の有限体反転を置換することにより、反転を統合することができる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
さらに他の実施形態では、本明細書において提示した技法のうちの１つまたは複数を実施するように構成されたプロセッサ実行可能な命令を含む、コンピュータ読取り可能な媒体を必要とする。このようにして考案することのできる例示的なコンピュータ読取り可能な媒体が図９に示してあるが、実装形態９００は、コンピュータ読取り可能な媒体９１６（たとえば、ＣＤ−Ｒ、ＤＶＤ−Ｒ、またはハード・ディスク・ドライブのプラッタ）を含み、これらの媒体上に、コンピュータ読取り可能なデータ９１４が符号化される。次に、コンピュータ読取り可能なデータ９１４は、本明細書において説明する原理のうちの１つまたは複数に従って動作するように構成された、１組のコンピュータ命令９１２を含む。こうした一実施形態９１０では、プロセッサ実行可能な命令９１２は、たとえば、図３の例示的な方法３００などの方法を実行するように構成してもよい。こうした他の一実施形態では、プロセッサ実行可能な命令９１２は、たとえば、図６の例示的なシステム６００などのシステムを実装するように構成してもよい。本明細書に提示した技法に従って動作するように構成された、こうした多くのコンピュータ読取り可能な媒体が、当業者によって考案することができる。