跳到主要内容

6. 确定性映射 (Deterministic Mappings)

本节中的映射适合使用第 3 节中的构造实现非均匀或均匀编码。某些映射限制曲线的形式或其参数。对于所提出的每个映射，本文档列出了相关限制。

请注意，本节中的映射不可互换：在相同输入上评估时，不同的映射几乎肯定会输出不同的点。

6.1. 选择映射函数 (Choosing a Mapping Function)​

本节简要介绍为给定椭圆曲线选择映射函数的指南。请注意，第 8 节中给出的套件是相应曲线的推荐映射。

如果目标椭圆曲线是 Montgomery 曲线（第 6.7 节），推荐使用 Elligator 2 方法（第 6.7.1 节）。类似地，如果目标椭圆曲线是扭曲 Edwards 曲线（第 6.8 节），推荐使用扭曲 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 节）。

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 时存在两个平方根，这可能导致 y 的符号存在歧义。

必要时，本节中的映射通过根据映射函数的输入指定 y 坐标的符号来解决此歧义。支持此方法的两个主要原因：首先，这以统一的方式覆盖任何域上的椭圆曲线，其次，它为实现者提供了优化平方根实现的余地。

6.5. 异常情况 (Exceptional Cases)​

映射可能具有异常情况，即映射未定义的输入 u。必须仔细处理这些情况，特别是对于常数时间实现。

对于本节中的每个映射，我们讨论异常情况并展示如何以常数时间处理它们。请注意，所有实现都应该 (SHOULD) 使用 inv0（第 4 节）来计算乘法逆元，以避免因尝试计算 0 的逆元而导致的异常情况。

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 [SW06] 描述了适用于几乎任何椭圆曲线的映射。（但是，请注意，此映射的评估成本高于本文档中的其他映射。）

此方法适用于 Weierstrass 曲线，也可以通过附录 D 中给出的有理映射用于 Montgomery 曲线和扭曲 Edwards 曲线。

6.6.2. 简化 Shallue-van de Woestijne-Ulas 方法​

函数 map_to_curve_simple_swu(u) 实现了 Brier 等人 [BCIMRT10] 描述的 Shallue-van de Woestijne-Ulas 映射 [U07] 的简化，他们称之为"简化 SWU"映射。Wahby 和 Boneh [WB19] 泛化并优化了此映射。

前提条件： Weierstrass 曲线 y^2 = x^3 + A * x + B，其中 A != 0 且 B != 0。

6.6.3. AB == 0 的简化 SWU​

Wahby 和 Boneh [WB19] 展示了如何将简化 SWU 映射适配到具有 A == 0 或 B == 0 的 Weierstrass 曲线，第 6.6.2 节的映射不支持这些曲线。

此方法适用于 secp256k1 [SEC2] 等曲线以及 Barreto-Lynn-Scott 系列 [BLS03]、Barreto-Naehrig 系列 [BN05] 和其他系列中的配对友好曲线。

6.7. Montgomery 曲线的映射 (Mappings for Montgomery Curves)​

本节定义的映射适用于由以下方程定义的目标曲线 M：

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

6.7.1. Elligator 2 方法​

Bernstein 等人 [BHKL13] 给出了一个映射，称为 Elligator 2，适用于任何具有 2 阶点的奇特征域上的 Montgomery 曲线。

前提条件： 具有以下附加要求的 Montgomery 曲线：

  • J != 0
  • K != 0
  • 曲线具有 2 阶点

6.8. 扭曲 Edwards 曲线的映射 (Mappings for Twisted Edwards Curves)​

本节定义的映射适用于由以下方程定义的目标曲线：

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

6.8.1. 从 Montgomery 到扭曲 Edwards 曲线的有理映射​

对于某些曲线，Montgomery 形式和扭曲 Edwards 形式通过有理映射相关。这允许通过首先映射到等效的 Montgomery 曲线，然后应用有理映射来映射到扭曲 Edwards 曲线。

6.8.2. Elligator 2 方法（扭曲 Edwards）​

本节给出了扭曲 Edwards 曲线的 Elligator 2 方法。这是将第 6.7.1 节的方法与第 6.8.1 节的有理映射组合的结果。

注意：完整的算法实现和参数详见各子节。本文档提供了优化的直线实现和安全考虑。

最后于 更新