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

付録

付録 A. 関連研究​

任意のビット値を楕円曲線の点にマッピングする問題は、実用的および理論的な研究の主題となってきました。この節では、この文書における推奨事項の背景と研究結果について簡潔に紹介します。この節は情報提供のみを目的としています。

文字列 msg を n 個の点を持つ楕円曲線 E 上の点にマッピングするための素朴ですが、通常は安全ではない方法は、まず楕円曲線群を生成する点 P と、ビット文字列から n 未満の整数へのハッシュ関数 Hn を固定し、次に Hn(msg) * P を計算することです（* はスカラー倍を表します）。この方法が安全でない理由は、結果として得られる点が P に対して既知の離散対数関係を持つためです。したがって、プロトコルでこの方法が明示的に指定されていない限り、使用してはなりません（MUST NOT）。さもなければ、致命的なセキュリティ上の欠陥を招くリスクがあります。

Boneh ら [BLS01] は、MapToGroup と呼ぶエンコード方法を説明しました。その仕組みは大まかには次のとおりです。まず、入力文字列を使用して疑似乱数生成器を初期化し、その生成器を使用して有限体 F 内の値 x を生成します。x が楕円曲線上の点の x 座標である場合、その点を出力します。そうでない場合は、F 内で新しい値 x を生成して再試行します。F 内のランダムな値 x が曲線上の点に対応する確率は約 1/2 であるため、期待される試行回数はわずか 2 回です。しかし、この「試行・増加（try-and-increment）」アルゴリズムとして知られる方法は、実行時間が入力文字列に依存します。そのため、Dragonblood 攻撃 [VR20] で示されているように、タイミングサイドチャネルに敏感なプロトコルで使用するのは安全ではありません。

Schinzel と Skałba [SS04] は、限定されたクラスの曲線と極少数の点に適用可能な、楕円曲線の点を決定論的に構築する方法を紹介しました。Skałba [S05] は、この構築をより多くの曲線とより多くの点に一般化しました。Shallue と van de Woestijne [SW06] は、Skałba の構築をさらに一般化・簡略化し、ほぼすべての曲線において一定比率の点へとマッピングする具体的な有効なマッピングを生成しました。Fouque と Tibouchi [FT12] は、Barreto-Naehrig ペアリングフレンドリー曲線 [BN05] に対してこのマッピングのパラメータ化を示しました。

Ulas [U07] は Shallue-van de Woestijne マッピングの簡略化版を説明し、Brier ら [BCIMRT10] はさらに簡略化した「簡略化 SWU」マッピングを示しました。この簡略化マッピングは当初、標数 p = 3 (mod 4) の体にのみ適用可能でしたが、Wahby と Boneh [WB19] はこれを任意の標数の体に一般化し、さらなる最適化を行いました。

Boneh と Franklin は、標数 p = 2 (mod 3) の体上の特定の超特異曲線（supersingular curve）への決定論的アルゴリズムを示しました [BF01]。Icart は、標数 p = 2 (mod 3) の体上のあらゆる曲線への別の決定論的アルゴリズムを示しました [Icart09]。この研究に続いて、[FSV09]、[FT10]、[KLR10]、[F11]、[CK11] など、いくつかの拡張と一般化が行われました。

Farashahi [F11] の研究に続いて、Fouque ら [FJT13] は、標数 p = 3 (mod 4) の体上の、点数が 4 で割り切れる曲線へのマッピングを説明しました。Bernstein ら [BHKL13] は、このマッピングを最適化し、「Elligator 2」と呼ぶ関連マッピングを説明しました。これは、位数 2 の点を持つ奇標数の体上のあらゆる曲線に適用可能です。これには、CFRG 推奨曲線である Curve25519 および Curve448 も含まれます [RFC7748]。Bernstein ら [BLMP19] は、Elligator 2 マッピングを標数 p = 3 (mod 4) の体上の一連の超特異曲線に拡張しました。

上記のすべての決定論的マッピング関数に関する重要な注意点は、それらがいずれも曲線全体にマッピングするのではなく、点の一部にのみマッピングするという点です。これは、それらを曲線上の点を出力するランダムオラクルの構築に直接使用できないことを意味します。

Brier ら [BCIMRT10] は、この問題に対して2つの解決策を示しました。第1の解決策（Brier らは Icart の方法に適用可能であることを証明しました）は、f(H0(msg)) + f(H1(msg)) を計算するものです。ここで H0 と H1 はビット文字列から F への2つの異なるハッシュ関数であり、f は F から楕円曲線 E へのマッピングです。第2の解決策は、ほぼすべての決定論的マッピングに適用可能ですがよりコストがかかり、f(H0(msg)) + H2(msg) * P を計算します。ここで P は楕円曲線群の生成元、H2 はビット文字列から位数 r の整数へのハッシュ、r は楕円曲線群の位数です。

Farashahi ら [FFSTV13] は第1の方法の分析を改善し、それがほぼすべての決定論的マッピングに適用可能であることを示しました。Tibouchi と Kim [TK17] はさらに分析を洗練させ、追加の最適化について説明しました。

ビット文字列を楕円曲線の点にマッピングする問題の補完として、Bernstein ら [BHKL13] は楕円曲線の点を一様ランダムなビット文字列にマッピングする問題を研究し、Montgomery 曲線および Twisted Edwards 曲線を含む一連の曲線に対して解決策を示しました。Tibouchi [T14] および Aranha ら [AFQTZ14] はこれらの結果を一般化しました。この文書では、この補完的な問題については扱いません。

付録 B. ristretto255 へのハッシュ​

ristretto255 [ristretto255-decaf448] は、curve25519 [RFC7748] に基づく素数位数群を提供します。この節では、一様な出力分布（第2.2.3節）を持ち、hash_to_curve 関数（第3節）と同じセキュリティ属性とインターフェースを持つ、その群へのランダムオラクルエンコーディングを実装する hash_to_ristretto255 について説明します。

ristretto255 API は、一方向マッピングを定義しています（[ristretto255-decaf448]、第4.3.4節）。この節では、そのマッピングを ristretto255_map と呼びます。

hash_to_ristretto255 関数は、第5.3節の要件に従った expand_message 関数を使用してインスタンス化されなければなりません。さらに、第3.1節で説明されている方法で構築されたドメイン分離タグを使用しなければならず、hash_to_ristretto255 を使用するプロトコルの実装に際しては、第10.7節で示されるドメイン分離に関するすべての推奨事項が適用されます。

hash_to_ristretto255(msg)

Parameters:
- DST: ドメイン分離タグ（上記の議論を参照）
- expand_message: バイト文字列とドメイン分離タグを一様ランダムなバイト文字列に拡張する関数（上記の議論を参照）
- ristretto255_map: ristretto255 API から提供される一方向マッピング

Input: msg, 任意の長さのバイト文字列
Output: P, ristretto255 群の要素

手順:
1. uniform_bytes = expand_message(msg, DST, 64)
2. P = ristretto255_map(uniform_bytes)
3. P を返す

hash_to_ristretto255 は hash-to-curve スイートではないため、スイート ID を持ちません。同様の識別子が必要な場合は、第8.10節のガイドラインに従って、以下のパラメータを使用して構築しなければなりません。

  • CURVE_ID: "ristretto255"

  • HASH_ID: 第8.10節の記載どおり

  • MAP_ID: "R255MAP"

  • ENC_VAR: "RO"

例えば、expand_message が SHA-512 を使用した expand_message_xmd である場合、必要な識別子は次のようになります。

ristretto255_XMD:SHA-512_R255MAP_RO_

付録 C. decaf448 へのハッシュ​

ristretto255 と同様に、decaf448 [ristretto255-decaf448] は、curve448 [RFC7748] に基づく素数位数群を提供します。この節では、一様な出力分布（第2.2.3節）を持ち、hash_to_curve 関数（第3節）と同じセキュリティ属性とインターフェースを持つ、その群へのランダムオラクルエンコーディングを実装する hash_to_decaf448 について説明します。

decaf448 API は、一方向マッピングを定義しています（[ristretto255-decaf448]、第5.3.4節）。この節では、そのマッピングを decaf448_map と呼びます。

hash_to_decaf448 関数は、第5.3節の要件に従った expand_message 関数を使用してインスタンス化されなければなりません。さらに、第3.1節で説明されている方法で構築されたドメイン分離タグを使用しなければならず、hash_to_decaf448 を使用するプロトコルの実装に際しては、第10.7節で示されるドメイン分離に関するすべての推奨事項が適用されます。

hash_to_decaf448(msg)

Parameters:
- DST: ドメイン分離タグ（上記の議論を参照）
- expand_message: バイト文字列とドメイン分離タグを一様ランダムなバイト文字列に拡張する関数（上記の議論を参照）
- decaf448_map: decaf448 API から提供される一方向マッピング

Input: msg, 任意の長さのバイト文字列
Output: P, decaf448 群の要素

手順:
1. uniform_bytes = expand_message(msg, DST, 112)
2. P = decaf448_map(uniform_bytes)
3. P を返す

hash_to_decaf448 は hash-to-curve スイートではないため、スイート ID を持ちません。同様の識別子が必要な場合は、第8.10節のガイドラインに従って、以下のパラメータを使用して構築しなければなりません。

  • CURVE_ID: "decaf448"

  • HASH_ID: 第8.10節の記載どおり

  • MAP_ID: "D448MAP"

  • ENC_VAR: "RO"

例えば、expand_message が SHAKE256 を使用した expand_message_xof である場合、必要な識別子は次のようになります。

decaf448_XOF:SHAKE256_D448MAP_RO_

付録 D. 有理写像​

この節では、Twisted Edwards 曲線や Montgomery 曲線へハッシュする際に使用できる有理写像を示します。

Twisted Edwards 曲線が与えられた場合、付録 D.1 では、対応する Montgomery 曲線を引き出す方法と、その曲線から Twisted Edwards 曲線へマッピングする方法を示します。第6.8節で説明されている Twisted Edwards 曲線へのハッシュを行う際に、このマッピングを使用できます。

Montgomery 曲線が与えられた場合、付録 D.2 では、対応する Weierstrass 曲線を引き出す方法と、その曲線から Montgomery 曲線へマッピングする方法を示します。このマッピングを使用することで、次のように Shallue-van de Woestijne 法（第6.6.1節）または簡略化 SWU 法（第6.6.2節）を Montgomery 曲線または Twisted Edwards 曲線に適用できます。

  • Montgomery 曲線の場合：まず Weierstrass 曲線へマッピングし、次にその写像を通じて Montgomery 座標に変換します。

  • Twisted Edwards 曲線の場合：Weierstrass から Montgomery への写像と、Montgomery から Twisted Edwards への写像（付録 D.1）を組み合わせることで、Weierstrass 曲線およびターゲットの Twisted Edwards 曲線への写像を得ます。この Weierstrass 曲線へマッピングし、次にその写像を通じて Edwards 座標に変換します。

D.1. Montgomery 曲線から Twisted Edwards 曲線への汎用マッピング​

この節では、Twisted Edwards 曲線と Montgomery 曲線との間の汎用的な双有理写像（birational map）を示します。

この節のマッピングは、[BBJLP08] の定理 3.2 で示されているマッピングの簡略化版です。具体的には、この節のマッピングは、Twisted Edwards 曲線の素数位数部分群へのハッシュに適した方法で例外的なケースを簡略化して処理します。

Twisted Edwards 曲線 a * v^2 + w^2 = 1 + d * v^2 * w^2

は、Montgomery 曲線 K * t^2 = s^3 + J * s^2 + s

と双有理同値です。これは、第6.7.1節の Elligator 2 マッピングに必要な形式を持っています。Montgomery 曲線の係数は次のとおりです。

  • J = 2 * (a + d) / (a - d)

  • K = 4 / (a - d)

上記の Montgomery 曲線上の点 (s, t) から Twisted Edwards 曲線上の点 (v, w) への有理写像は、次のように与えられます。

  • v = s / t

  • w = (s - 1) / (s + 1)

t == 0 または s == -1 のとき、すなわち上記のいずれかの有理関数の分母が 0 になるとき、この写像は未定義です。実装では例外的なケースを検出し、すべての Twisted Edwards 曲線上の単位点である値 (v, w) = (0, 1) を返さなければなりません。

上記の有理写像の以下の直線実装では、例外的なケースが処理されています。

monty_to_edw_generic(s, t)

Input: (s, t), 曲線 K * t^2 = s^3 + J * s^2 + s 上の点
Output: (v, w), 同等の twisted Edwards 曲線上の点

1. tv1 = s + 1
2. tv2 = tv1 * t        # (s + 1) * t
3. tv2 = inv0(tv2)      # 1 / ((s + 1) * t)
4.   v = tv2 * tv1      # 1 / t
5.   v = v * s          # s / t
6.   w = tv2 * t        # 1 / (s + 1)
7. tv1 = s - 1
8.   w = w * tv1        # (s - 1) / (s + 1)
9.   e = tv2 == 0
10.  w = CMOV(w, 1, e)  # 例外的なケースを処理
11. (v, w) を返す

完全性のために、逆の関係も示します（Twisted Edwards 曲線へハッシュする際には、このマッピングは不要です）。上記の Montgomery 曲線に対応する Twisted Edwards 曲線の係数は次のとおりです。

  • a = (J + 2) / K

  • d = (J - 2) / K

Twisted Edwards 曲線上の点 (v, w) から Montgomery 曲線上の点 (s, t) への有理写像は、次のように与えられます。

  • s = (1 + w) / (1 - w)

  • t = (1 + w) / (v * (1 - w))

v == 0 または w == 1 のとき、写像は未定義です。Montgomery 曲線の素数位数部分群へのマッピングを目的とする場合、例外的なケースでは Montgomery 曲線上の単位点を返せば十分です。

D.2. Weierstrass 曲線から Montgomery 曲線へのマッピング​

Montgomery 曲線上の点 (s, t) K * t^2 = s^3 + J * s^2 + s

から、同等の Weierstrass 曲線上の点 (x, y) y^2 = x^3 + A * x + B

への有理写像は、次のように与えられます。

  • A = (3 - J^2) / (3 * K^2)

  • B = (2 * J^3 - 9 * J) / (27 * K^3)

  • x = (3 * s + J) / (3 * K)

  • y = t / K

点 (x, y) から点 (s, t) への逆写像は、次のように与えられます。

  • s = (3 * K * x - J) / 3

  • t = y * K

このマッピングは、Montgomery 曲線に対して Shallue-van de Woestijne 法（第6.6.1節）または簡略化 SWU 法（第6.6.2節）を適用するために使用できます。

に最終更新