6. 決定論的マッピング

この節のマッピングは、第3節の構成を使用した非一様または一様エンコーディングの実装に適しています。一部のマッピングは、曲線の形式またはそのパラメータを制限します。提示される各マッピングについて、この文書では関連する制限をリストします。

この節のマッピングは互換性がないことに注意してください。異なるマッピングは、同じ入力に対して評価された場合、ほぼ確実に異なる点を出力します。

6.1. マッピング関数の選択

この節では、特定の楕円曲線に対してマッピング関数を選択するためのガイドラインを簡潔に紹介します。第8節で示されるスイートは、それぞれの曲線に対して推奨されるマッピングであることに注意してください。

ターゲットとなる楕円曲線が Montgomery 曲線（第6.7節）である場合、Elligator 2 法（第6.7.1節）が推奨されます。同様に、ターゲットとなる楕円曲線が Twisted Edwards 曲線（第6.8節）である場合、Twisted Edwards Elligator 2 法（第6.8.2節）が推奨されます。

それ以外のケースは Weierstrass 曲線です。簡略化 Shallue-van de Woestijne-Ulas (SWU) 法（第6.6.2節）がサポートする曲線については、そのマッピングが推奨されます。そうでない場合、最高のパフォーマンスを求めるなら AB == 0 の場合の簡略化 SWU 法（第6.6.3節）が、実装の単純さを求めるなら Shallue-van de Woestijne 法（第6.6.1節）が推奨されます。（この違いの理由は、AB == 0 の場合の簡略化 SWU 法がマッピング関数に加えて同源写像（isogeny map）の実装を必要とするのに対し、Shallue-van de Woestijne 法はそれを必要としないためです。）

Shallue-van de Woestijne 法（第6.6.1節）はあらゆる曲線に適用可能であり、汎用的なマッピングが必要な場合に使用できます。ただし、このマッピングの計算コストは、上記の曲線固有の推奨事項よりもほぼ常に高いことに注意してください。

6.2. インターフェース

この節のすべてのマッピングで共有される共通のインターフェースは以下のとおりです。

(x, y) = map_to_curve(u)

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

6.3. 表記

大まかなガイドとして、疑似コードでは以下の規則が使用されます。

• 特に断りのない限り、すべての算術演算は有限体 F 上で実行されます。

• u：マッピング関数への入力。これは hash_to_field 関数によって生成された F の要素です。

• (x, y), (s, t), (v, w)：マッピングによって出力される点のアフィン座標。インデックス付きの変数（例：x1, y2, ...）は候補値に使用されます。

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

• c1, c2, ...：事前計算可能な定数値。

6.4. 結果の点の符号

一般に、楕円曲線は y^2 = g(x) 形式の方程式を持ちます。この節のマッピングでは、まず g(x) が平方（square）となる x を見つけ、次に平方根をとって y を求めます。g(x) != 0 の場合には2つの平方根が存在するため、y の符号に曖昧さが生じる可能性があります。

必要に応じて、この節のマッピングではマッピング関数の入力に基づいて y 座標の符号を指定することで、この曖昧さを解決します。このアプローチを支持する主な理由は2つあります。第一に、これにより、あらゆる体上の楕円曲線を統一的な方法でカバーできること。第二に、平方根の実装を最適化するための余地を実装者に与えることです。

6.5. 例外的なケース

マッピングには、マッピングが定義されない入力 u という「例外的なケース」が存在する場合があります。これらのケース、特に定数時間の実装については、注意深く処理しなければなりません。

この節の各マッピングについて、例外的なケースを検討し、それらを定数時間でどのように処理するかを説明します。すべての実装において、0 の逆元を計算しようとすることによる例外を避けるため、乗法逆元の計算には inv0（第4節）を使用すべきであることに注意してください。

6.6. Weierstrass 曲線のマッピング

この節のマッピングは、以下の方程式で定義されるターゲット曲線 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 [SW06] は、ほぼすべての楕円曲線に適用可能なマッピングを説明しています。（ただし、このマッピングの評価コストは、この文書の他のマッピングよりも高いことに注意してください。）

以下に示すパラメータ化は Weierstrass 曲線用です。その導出の詳細は [W19] に記載されています。このパラメータ化は、付録 D に示される有理写像（rational map）を介して、Montgomery 曲線（第6.7節）および Twisted Edwards 曲線（第6.8節）にも適用可能です。まず Shallue-van de Woestijne マッピングを同等の Weierstrass 曲線に対して評価し、次に対応する有理写像を使用してその点をターゲットの Montgomery または Twisted Edwards 曲線に変換します。

前提条件：Weierstrass 曲線 y^2 = x^3 + A * x + B。

定数：

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

• Z：F 内のゼロでない要素で、以下の基準を満たすもの。付録 H.1 に、推奨される 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) と設定します。

例外：u の例外的なケースは (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0 のときに発生します。上記で示された Z の制限により、この積を反転するために inv0 を使用する実装は例外なしで動作することが保証されます。

操作：

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 でなければならない
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. (x, y) を返す

付録 F.1 に、このマッピングの直線実装の例を示します。

6.6.2. 簡略化 Shallue-van de Woestijne-Ulas 法

関数 map_to_curve_simple_swu(u) は、Brier ら [BCIMRT10] が「簡略化 SWU」マッピングと呼んだ、Shallue-van de Woestijne-Ulas マッピング [U07] の簡略化版を実装したものです。Wahby と Boneh [WB19] は、このマッピングを一般化し、最適化しました。

前提条件：Weierstrass 曲線 y^2 = x^3 + A * x + B。ただし、A != 0 かつ B != 0。

定数：

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

• Z：有限体 F の要素で、以下の基準を満たすもの。付録 H.2 に、推奨される Z を出力する Sage スクリプト [SAGE] を示します。基準は以下のとおりです。

  1. Z が F において非平方である。

  2. F において Z != -1 である。

  3. 多項式 g(x) - Z が F 上で既約である。

  4. F において g(B / (Z * A)) が平方である。

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

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

操作：

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. (x, y) を返す

付録 F.2 に、このマッピングの汎用的かつ最適化された直線実装を示します。このマッピングの最適化に関する詳細は、[WB19] の第4節または [hash2curve-repo] のサンプルコードを参照してください。

6.6.3. AB == 0 の場合の簡略化 SWU

Wahby と Boneh [WB19] は、第6.6.2節のマッピングではサポートされていない A == 0 または B == 0 の Weierstrass 曲線に対して、簡略化 SWU マッピングを適応させる方法を示しました。（y^2 = x^3 は楕円曲線ではないため、A == B == 0 のケースは除外されます。）

この方法は、secp256k1 [SEC2] や、Barreto-Lynn-Scott ファミリー [BLS03]、Barreto-Naehrig ファミリー [BN05] などのペアリングフレンドリーな曲線に適用可能です。

この方法では、以下の方程式で与えられる、E と同源であり A' != 0 かつ B' != 0 を満たす別の楕円曲線 E' を見つける必要があります。

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

（[SAGE] を使用して E' を見つける一つの方法については、[WB19] の付録 A を参照してください。）この同源性は、有理関数のペアで与えられる写像 iso_map(x', y') を定義します。iso_map は E' 上の点を入力として受け取り、E 上の点を出力として生成します。

E' と iso_map が決定されると、このマッピングは次のように動作します。入力 u に対して、まず簡略化 SWU マッピングを適用して E' 上の点を取得し、次にその点に同源写像を適用して E 上の点を取得します。

iso_map は群準同型（group homomorphism）である、すなわち点加算と iso_map は可換であることに注意してください。したがって、第3節で説明した hash_to_curve 構成でこのマッピングを使用する場合、まず u0 と u1 を E' にマッピングし、E' 上で結果の点を加算してから、その合計に iso_map を適用することで、小さな最適化が可能です。これにより、iso_map の評価を一度だけに抑えつつ、同じ結果が得られます。

前提条件：A' != 0 かつ B' != 0 を持ち、ターゲット曲線 E と同源である楕円曲線 E'。および E' から E への同源写像 iso_map。

補助関数：

• map_to_curve_simple_swu：E' への第6.6.2節のマッピング

• iso_map：E' から E への同源写像

y の符号：このマッピングでは、符号は map_to_curve_simple_swu によって決定されます。さらなる符号調整は不要です。

例外：map_to_curve_simple_swu は自身の例外的なケースを処理します。iso_map の例外的なケースは、いずれかの有理関数の分母が 0 になる入力です。そのようなケースでは E の無限遠点（単位点）を返さなければなりません。

操作：

1. (x', y') = map_to_curve_simple_swu(u)    # (x', y') は E' 上の点
2.   (x, y) = iso_map(x', y')               # (x, y) は E 上の点
3. (x, y) を返す

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

6.7. Montgomery 曲線のマッピング

この節で定義されるマッピングは、以下の方程式で定義されるターゲット曲線 M に適用されます。

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

6.7.1. Elligator 2 法

Bernstein, Hamburg, Krasnova, Lange らは、2次（位数2）の点を持つあらゆる曲線に適用可能なマッピング [BHKL13] を示し、これを Elligator 2 と呼びました。

前提条件：Montgomery 曲線 K * t^2 = s^3 + J * s^2 + s。ただし、J != 0、K != 0 であり、(J^2 - 4) / K^2 は F においてゼロでなく、かつ非平方であること。

定数：

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

• Z：F 内の非平方要素。付録 H.3 に推奨される Z を出力する Sage スクリプト [SAGE] を示します。

t の符号：このマッピングは [BHKL13] の規定に従って t の符号を固定します。追加の調整は不要です。

例外：例外的なケースは Z * u^2 == -1、すなわち 1 + Z * u^2 == 0 のときです。実装ではこのケースを検出し、x1 = -(J / K) と設定しなければなりません。これは q = 3 (mod 4) の場合にのみ発生する可能性があることに注意してください。

操作：

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. (s, t) を返す

付録 F.3 に、このマッピングの直線実装の例を示します。付録 G.2 に、特定の曲線カテゴリーと基礎体に合わせた最適化された直線手順を示します。

6.8. Twisted Edwards 曲線のマッピング

Twisted Edwards 曲線（Edwards 曲線を包含する曲線の一種）は、以下の方程式で与えられます。

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

ここで、a != 0、d != 0、かつ a != d です [BBJLP08]。

これらの曲線は Montgomery 曲線（第6.7節）と密接に関連しています。すべての Twisted Edwards 曲線は Montgomery 曲線と双有理同値（birationally equivalent）です（[BBJLP08]、定理 3.2）。この同値性により、Twisted Edwards 曲線へのハッシュを効率的に計算する方法が得られます。まず、同等の Montgomery 曲線にハッシュし、次に有理写像（rational map）を使用して結果を Twisted Edwards 曲線上の点に変換します。したがって、この Twisted Edwards 曲線へのハッシュ方法では、対応する Montgomery 曲線と有理写像を特定する必要があります。それらを特定する方法について以下に説明します。

6.8.1. Montgomery 曲線から Twisted Edwards 曲線への有理写像

特定の Twisted Edwards 曲線へハッシュする場合、Montgomery 曲線と有理写像を選択する方法は2つあります。選択された Montgomery 曲線と有理写像は、特定の Twisted Edwards 曲線の hash-to-curve スイートの一部として指定されなければなりません（第8節を参照）。

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

   一部のケース（例：edwards25519 [RFC7748]）では、Twisted Edwards 曲線から対応する Montgomery 曲線への有理写像の符号が明示的に示されていません。そのような場合、Twisted Edwards 曲線の基点に有理写像を適用した際に、正しい符号を持つ Montgomery 曲線の基点が生成されるように、符号を固定しなければなりません（edwards25519 については [RFC7748] および [Err4730] を参照）。

   新しい Twisted Edwards 曲線を定義する場合、Montgomery 同等物と有理写像も指定すべきであり、有理写像の符号を明示的に記載すべきです（SHOULD）。

2. 標準化された Montgomery 形式や有理写像が存在しない Twisted Edwards 曲線へハッシュする場合、付録 D に記されるマッピングを使用すべきです（SHOULD）。

6.8.2. Elligator 2 法

前提条件：第6.8.1節の要件を満たす Twisted Edwards 曲線 E、および同等の Montgomery 曲線 M。

補助関数：

• 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 によって決定されます。さらなる符号調整は不要です。

例外：Elligator 2 マッピングの例外は第6.7.1節に、有理写像の例外は第6.8.1節に記載されているとおりです。他に起こり得る例外はありません。

以下の手順で Twisted Edwards 曲線に対する Elligator 2 マッピングを実装します。（ターゲットとなる Twisted Edwards 曲線上の点であるため、出力点は (v, w) と表記されることに注意してください。）

map_to_curve_elligator2_edwards(u)

Input: u, an element of F.
Output: (v, w), a point on E.

1. (s, t) = map_to_curve_elligator2(u)      # (s, t) は M 上の点
2. (v, w) = rational_map(s, t)              # (v, w) は E 上の点
3. (v, w) を返す