メインコンテンツまでスキップ

6. 決定的写像 (Deterministic Mappings)

本節の写像は、第 3 節の構成を用いて非一様符号化または一様符号化のいずれかを実装するのに適しています。ある種の写像は、曲線の形式やそのパラメータに制約を課します。提示される各写像について、本文書は関連する制約を列挙します。

本節の写像は互換的ではないことに注意してください。異なる写像は、同じ入力に対して評価されたとき、ほぼ確実に異なる点を出力します。

6.1. 写像関数の選択 (Choosing a Mapping Function)​

本節では、所与の楕円曲線に対して写像関数を選択するための簡潔な指針を示します。第 8 節で示されるスイートは、それぞれの曲線に対する推奨される写像であることに注意してください。

対象の楕円曲線が Montgomery 曲線（第 6.7 節）である場合、Elligator 2 法（第 6.7.1 節）が推奨されます。同様に、対象の楕円曲線がねじれ Edwards 曲線 (twisted Edwards curve)（第 6.8 節）である場合、ねじれ Edwards 版 Elligator 2 法（第 6.8.2 節）が推奨されます。

残りの場合は Weierstrass 曲線です。Simplified Shallue-van de Woestijne-Ulas (SWU) 法（第 6.6.2 節）がサポートする曲線については、その写像が推奨されるものです。そうでない場合、最良の性能を目標とするならば AB == 0 に対する Simplified SWU 法（第 6.6.3 節）が推奨され、実装の単純さを目標とするならば Shallue-van de Woestijne 法（第 6.6.1 節）が推奨されます。（この区別の理由は、AB == 0 に対する Simplified SWU 法が写像関数に加えて同種写像 (isogeny map) の実装を必要とするのに対し、Shallue-van de Woestijne 法はそれを必要としないためです。）

Shallue-van de Woestijne 法（第 6.6.1 節）は任意の曲線に対して機能し、汎用的な写像が必要とされる場合に用いることができます。ただし、この写像は上記の曲線固有の推奨よりも、ほとんど常に計算コストが高いことに注意してください。

6.2. インタフェース (Interface)​

本節のすべての写像が共有する汎用インタフェースは次のとおりです。

(x, y) = map_to_curve(u)

入力 u と出力 x, y は体 F の元です。アフィン座標 (x, y) は F 上で定義された楕円曲線上の点を指定します。ただし、点 (x, y) は一様ランダムな点ではないことに注意してください。

6.3. 記法 (Notation)​

大まかな指針として、疑似コードでは以下の慣行が用いられます。

  • 明示的に別途述べられている場合を除き、すべての算術演算は体 F 上で実行されます。

  • u: 写像関数への入力。これは hash_to_field 関数によって生成される F の元です。

  • (x, y), (s, t), (v, w): 写像が出力する点のアフィン座標。添字付きの変数（たとえば x1, y2, ...）は候補値に用いられます。

  • tv1, tv2, ...: 再利用可能な一時変数。

  • c1, c2, ...: 事前に計算できる定数値。

6.4. 結果の点の符号 (Sign of the Resulting Point)​

一般に、楕円曲線は y^2 = g(x) の形の方程式を持ちます。本節の写像は、まず g(x) が平方数となるような x を特定し、次に平方根を取って y を求めます。g(x) != 0 のとき平方根は 2 つ存在するため、これは y の符号に関する曖昧さをもたらす可能性があります。

必要な場合、本節の写像は、写像関数への入力に基づいて y 座標の符号を規定することによって、この曖昧さを解消します。このアプローチを支持する主な理由は 2 つあります。第 1 に、これは任意の体上の楕円曲線を統一的な方法で扱えること、第 2 に、実装者に平方根実装の最適化における余地を与えることです。

6.5. 例外的な場合 (Exceptional Cases)​

写像は例外的な場合、すなわち写像が未定義となる入力 u を持つことがあります。これらの場合は、とりわけ定数時間実装においては、注意深く扱われなければなりません。

本節の各写像について、例外的な場合を論じ、それらを定数時間で扱う方法を示します。0 の逆元を計算しようとすることに起因する例外的な場合を避けるため、すべての実装は乗法逆元の計算に inv0（第 4 節）を使用すべきです (SHOULD)。

6.6. Weierstrass 曲線に対する写像 (Mappings for Weierstrass Curves)​

本節の写像は、次の方程式によって定義される対象曲線 E に適用されます。

y^2 = g(x) = x^3 + A * x + B

ここで 4 * A^3 + 27 * B^2 != 0 です。

6.6.1. Shallue-van de Woestijne 法 (Shallue-van de Woestijne Method)​

Shallue と van de Woestijne [SW06] は、本質的に任意の楕円曲線に適用できる写像を記述しています。（ただし、この写像は本文書の他の写像よりも評価コストが高いことに注意してください。）

以下に示すパラメータ化は Weierstrass 曲線に対するものであり、その導出は [W19] に詳述されています。このパラメータ化は、付録 D で与えられる有理写像を介して、Montgomery 曲線（第 6.7 節）およびねじれ Edwards 曲線（第 6.8 節）に対しても機能します。すなわち、まず同値な Weierstrass 曲線への Shallue-van de Woestijne 写像を評価し、次に対応する有理写像を用いてその点を対象の Montgomery 曲線またはねじれ Edwards 曲線へ写します。

前提条件 (Preconditions): Weierstrass 曲線 y^2 = x^3 + A * x + B。

定数 (Constants):

  • A および B, Weierstrass 曲線のパラメータ。

  • Z, 以下の基準を満たす F の非ゼロ元。付録 H.1 では、推奨される (RECOMMENDED) Z を出力する Sage スクリプト [SAGE] を示します。

    1. F において g(Z) != 0。
    2. F において -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0。
    3. F において -(3 * Z^2 + 4 * A) / (4 * g(Z)) が平方数である。
    4. g(Z) と g(-Z / 2) のうち少なくとも一方が F において平方数である。

y の符号: 多くの u の値について、入力 u と -u は同じ x 座標を与えます。したがって sgn0(y) == sgn0(u) と定めます。

例外 (Exceptions): u に対する例外的な場合は (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0 のときに生じます。上で与えられた Z への制約は、この積の逆元を求めるのに inv0 を用いる実装が例外を生じないことを保証します。

演算 (Operations):

1. tv1 = u^2 * g(Z)
2. tv2 = 1 + tv1
3. tv1 = 1 - tv1
4. tv3 = inv0(tv1 * tv2)
5. tv4 = sqrt(-g(Z) * (3 * Z^2 + 4 * A))    # 事前計算可能
6. sgn0(tv4) == 1 ならば tv4 = -tv4 とする  # sgn0(tv4) は 0 でなければならない (MUST)
7. tv5 = u * tv1 * tv3 * tv4
8. tv6 = -4 * g(Z) / (3 * Z^2 + 4 * A)      # 事前計算可能
9.  x1 = -Z / 2 - tv5
10. x2 = -Z / 2 + tv5
11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. is_square(g(x1)) ならば x = x1, y = sqrt(g(x1)) とする
13. そうでなく is_square(g(x2)) ならば x = x2, y = sqrt(g(x2)) とする
14. それ以外は x = x3, y = sqrt(g(x3)) とする
15. sgn0(u) != sgn0(y) ならば y = -y とする
16. return (x, y)

付録 F.1 では、この写像の直線的な実装例を示します。

6.6.2. Simplified Shallue-van de Woestijne-Ulas 法 (Simplified Shallue-van de Woestijne-Ulas Method)​

関数 map_to_curve_simple_swu(u) は、Brier ら [BCIMRT10] が記述した Shallue-van de Woestijne-Ulas 写像 [U07] の簡略化を実装するもので、彼らはこれを「simplified SWU」写像と呼んでいます。Wahby と Boneh [WB19] はこの写像を一般化し最適化しています。

前提条件 (Preconditions): A != 0 かつ B != 0 である Weierstrass 曲線 y^2 = x^3 + A * x + B。

定数 (Constants):

  • A および B, Weierstrass 曲線のパラメータ。

  • Z, 以下の基準を満たす F の元。付録 H.2 では、推奨される (RECOMMENDED) Z を出力する Sage スクリプト [SAGE] を示します。基準は次のとおりです。

    1. Z は F において非平方数である、
    2. F において Z != -1 である、
    3. 多項式 g(x) - Z が F 上で既約である、および
    4. g(B / (Z * A)) が F において平方数である。

y の符号: 入力 u と -u は同じ x 座標を与えます。したがって sgn0(y) == sgn0(u) と定めます。

例外 (Exceptions): 例外的な場合は Z^2 * u^4 + Z * u^2 == 0 となるような u の値です。これには u == 0 が含まれ、また Z に依存する他の値が含まれることもあります。実装はこの場合を検出して x1 = B / (Z * A) と設定しなければなりません。これは上で与えられた Z に関する条件により g(x1) が平方数であることを保証します。

演算 (Operations):

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2.  x1 = (-B / A) * (1 + tv1)
3.  tv1 == 0 ならば x1 = B / (Z * A) とする
4. gx1 = x1^3 + A * x1 + B
5.  x2 = Z * u^2 * x1
6. gx2 = x2^3 + A * x2 + B
7.  is_square(gx1) ならば x = x1, y = sqrt(gx1) とする
8.  それ以外は x = x2, y = sqrt(gx2) とする
9.  sgn0(u) != sgn0(y) ならば y = -y とする
10. return (x, y)

付録 F.2 では、この写像の一般的かつ最適化された直線的な実装を示します。この写像の最適化についてのさらなる情報は、[WB19] の第 4 節、または [hash2curve-repo] にあるサンプルコードを参照してください。

6.6.3. AB == 0 に対する Simplified SWU (Simplified SWU for AB == 0)​

Wahby と Boneh [WB19] は、第 6.6.2 節の写像がサポートしない A == 0 または B == 0 である Weierstrass 曲線に対して、Simplified SWU 写像をどのように適応させるかを示しています。（A == B == 0 の場合は、y^2 = x^3 が楕円曲線ではないため除外されます。）

この手法は secp256k1 [SEC2] のような曲線、および Barreto-Lynn-Scott 族 [BLS03]、Barreto-Naehrig 族 [BN05]、その他の族に属するペアリングフレンドリー曲線に適用されます。

この手法は、次の方程式によって与えられる別の楕円曲線 E' を見つけることを必要とします。

y'^2 = g'(x') = x'^3 + A' * x' + B'

この E' は E と同種 (isogenous) であり、かつ A' != 0 および B' != 0 を満たします。（[SAGE] を用いて E' を見つける一つの方法については [WB19] の付録 A を参照してください。）この同種写像は、有理関数の対によって与えられる写像 iso_map(x', y') を定義します。iso_map は E' 上の点を入力として受け取り、E 上の点を出力として生成します。

E' と iso_map が特定されると、この写像は次のように機能します。入力 u に対して、まず Simplified SWU 写像を適用して E' 上の点を得て、次にその点に同種写像を適用して E 上の点を得ます。

iso_map は群準同型であり、これは点の加算が iso_map と可換であることを意味することに注意してください。したがって、第 3 節で論じた hash_to_curve 構成においてこの写像を用いる場合、まず u0 と u1 を E' へ写し、E' 上で得られた点を加算し、その和に iso_map を適用することによって、小さな最適化を実現できます。これは同じ結果を与えつつ、iso_map の評価を 1 回だけしか必要としません。

前提条件 (Preconditions): A' != 0 かつ B' != 0 であり、対象曲線 E と同種である楕円曲線 E'、および E' から E への同種写像 iso_map。

補助関数 (Helper functions):

  • map_to_curve_simple_swu は E' への第 6.6.2 節の写像

  • iso_map は E' から E への同種写像

y の符号: この写像では、符号は map_to_curve_simple_swu によって決定されます。それ以上の符号調整は不要です。

例外 (Exceptions): map_to_curve_simple_swu は自身の例外的な場合を処理します。iso_map の例外的な場合は、いずれかの有理関数の分母が 0 に評価される原因となる入力です。そのような場合は E 上の単位元点を返さなければなりません (MUST)。

演算 (Operations):

1. (x', y') = map_to_curve_simple_swu(u)    # (x', y') は E' 上にある
2.   (x, y) = iso_map(x', y')               # (x, y) は E 上にある
3. return (x, y)

同種写像の実装の詳細については [hash2curve-repo] または [WB19] の第 4.3 節を参照してください。

6.7. Montgomery 曲線に対する写像 (Mappings for Montgomery Curves)​

本節で定義される写像は、次の方程式によって定義される対象曲線 M に適用されます。

K * t^2 = s^3 + J * s^2 + s

6.7.1. Elligator 2 法 (Elligator 2 Method)​

Bernstein、Hamburg、Krasnova、および Lange は、位数 2 の点を持つ任意の曲線に適用できる写像を与えており [BHKL13]、彼らはこれを Elligator 2 と呼んでいます。

前提条件 (Preconditions): J != 0、K != 0 であり、かつ (J^2 - 4) / K^2 が F において非ゼロかつ非平方数である Montgomery 曲線 K * t^2 = s^3 + J * s^2 + s。

定数 (Constants):

  • J および K, 楕円曲線のパラメータ。

  • Z, F の非平方元。付録 H.3 では、推奨される (RECOMMENDED) Z を出力する Sage スクリプト [SAGE] を示します。

t の符号: この写像は [BHKL13] で規定されているとおりに t の符号を定めます。追加の調整は不要です。

例外 (Exceptions): 例外的な場合は Z * u^2 == -1、すなわち 1 + Z * u^2 == 0 です。実装はこの場合を検出して x1 = -(J / K) と設定しなければなりません。これは q = 3 (mod 4) の場合にのみ起こりうることに注意してください。

演算 (Operations):

1.  x1 = -(J / K) * inv0(1 + Z * u^2)
2.  x1 == 0 ならば x1 = -(J / K) とする
3. gx1 = x1^3 + (J / K) * x1^2 + x1 / K^2
4.  x2 = -x1 - (J / K)
5. gx2 = x2^3 + (J / K) * x2^2 + x2 / K^2
6.  is_square(gx1) ならば x = x1, y = sqrt(gx1) （sgn0(y) == 1 となるように）とする。
7.  それ以外は x = x2, y = sqrt(gx2) （sgn0(y) == 0 となるように）とする。
8.   s = x * K
9.   t = y * K
10. return (s, t)

付録 F.3 では、この写像の直線的な実装例を示します。付録 G.2 では、特定の種類の曲線および基礎体に適用される最適化された直線的手続きを示します。

6.8. ねじれ Edwards 曲線に対する写像 (Mappings for Twisted Edwards Curves)​

ねじれ Edwards 曲線（Edwards 曲線を含む曲線の一群）は、次の方程式によって与えられます。

a * v^2 + w^2 = 1 + d * v^2 * w^2

ここで a != 0、d != 0、および a != d です [BBJLP08]。

これらの曲線は Montgomery 曲線（第 6.7 節）と密接に関連しています。すべてのねじれ Edwards 曲線は、ある Montgomery 曲線と双有理同値です（[BBJLP08]、定理 3.2）。この同値性は、ねじれ Edwards 曲線へハッシュする効率的な方法をもたらします。すなわち、まず同値な Montgomery 曲線へハッシュし、次に有理写像を介してその結果をねじれ Edwards 曲線上の点へ変換します。したがって、ねじれ Edwards 曲線へハッシュするこの方法は、対応する Montgomery 曲線と有理写像を特定することを必要とします。そのような曲線と写像を特定する方法を、直下で説明します。

6.8.1. Montgomery 曲線からねじれ Edwards 曲線への有理写像 (Rational Maps from Montgomery to Twisted Edwards Curves)​

所与のねじれ Edwards 曲線へハッシュする際に使用する Montgomery 曲線と有理写像を選択する方法は 2 つあります。選択された Montgomery 曲線と有理写像は、所与のねじれ Edwards 曲線に対するハッシュ・トゥ・カーブ・スイートの一部として規定されなければなりません (MUST)。第 8 節を参照してください。

  1. 対応する Montgomery 形式および有理写像もまた標準化されている、標準化されたねじれ Edwards 曲線へハッシュする場合、既存のソフトウェアとの互換性を保証するため、標準の Montgomery 形式と有理写像を使用すべきです (SHOULD)。

    ある種の場合、たとえば edwards25519 [RFC7748] では、ねじれ Edwards 曲線から対応する Montgomery 曲線への有理写像の符号が明示的に与えられていません。この場合、ねじれ Edwards 曲線のベースポイントに有理写像を適用したときに、Montgomery 曲線のベースポイントが正しい符号で得られるように、符号を定めなければなりません (MUST)。（edwards25519 については、[RFC7748] および [Err4730] を参照してください。）

    新しいねじれ Edwards 曲線を定義する際には、Montgomery 同値形式と有理写像も併せて規定すべきであり (SHOULD)、また有理写像の符号は明示的に述べられるべきです (SHOULD)。

  2. 標準化された Montgomery 形式または有理写像を持たないねじれ Edwards 曲線へハッシュする場合、付録 D で与えられる写像を使用すべきです (SHOULD)。

6.8.2. Elligator 2 法 (Elligator 2 Method)​

前提条件 (Preconditions): ねじれ Edwards 曲線 E、および第 6.8.1 節の要件を満たす同値な Montgomery 曲線 M。

補助関数 (Helper functions):

  • map_to_curve_elligator2 は曲線 M への第 6.7.1 節の写像。

  • rational_map は M 上の点 (s, t) を受け取り、E 上の点 (v, w) を返す関数。この有理写像は第 6.8.1 節で定義されるとおりに選択されるべきです。

t（および v）の符号: この写像では、符号は map_to_curve_elligator2 によって決定されます。それ以上の符号調整は不要です。

例外 (Exceptions): Elligator 2 写像に対する例外は第 6.7.1 節で与えられるとおりです。有理写像に対する例外は第 6.8.1 節で与えられるとおりです。他の例外はありえません。

以下の手続きは、ねじれ Edwards 曲線に対する Elligator 2 写像を実装します。（出力される点が対象のねじれ Edwards 曲線上の点であるため、(v, w) と表記されていることに注意してください。）

map_to_curve_elligator2_edwards(u)

入力 (Input): u, F の元。
出力 (Output): (v, w), E 上の点。

1. (s, t) = map_to_curve_elligator2(u)      # (s, t) は M 上にある
2. (v, w) = rational_map(s, t)              # (v, w) は E 上にある
3. return (v, w)
に最終更新