最近、よく見かけるRistrettoについて調べてみた↓
Ristrettoが解決すること
Ristrettoは、楕円曲線の内、曲線上の有効な点の総数（位数）が素数ではない楕円曲線から、位数が素数となる群を構築する抽象化レイヤーを提供するための手法。
位数が素数だと何が嬉しいのか？
- 楕円曲線暗号の安全性は、楕円曲線上の離散対数問題（ECDLP）の困難さに基づいており、この難易度は曲線の計算に使用する群の位数が素数である場合に最大になる。
- 単位元を除く群内のすべての点が生成元になり得る。
- 群の演算（点の加算や、スカラー乗算）が比較的単純になる。
- 安全な楕円曲線のパラメーターを選択するのが比較的単純になる。
- 部分群（サブグループ）が存在しないので、t小さな部分群を利用した攻撃を回避できる。
最後の部分群を利用した攻撃について、暗号通貨で有名なのはMoneroに存在した脆弱性（実際に悪用されてはいない）↓
techmedia-think.hatenablog.com
といったことから、素数位数を持つ楕円曲線が多くの暗号プロトコルなどで推奨されている。Bitcoinで使用されている楕円曲線secp256k1も、位数は素数。
素数位数でない曲線
一方で最近の楕円曲線の実装では、位数が素数ではないことが多い（MoneroのCurve25519もそう）。なぜ位数が素数ではない曲線を使うのか？というと、演算がとても高速に行えるから。
これらの楕円曲線の位数Nは、素数位数の部分群の位数をとした場合、
となる。hは余因子（cofactor）と呼ばれる値で、部分群と曲線全体の群の比率を表す値。
が巨大な素数であるのに対して、hは通常1とか4とか8とか小さな値になる。secp256k1など素数位数の曲線の場合、h = 1となる（つまり曲線の群＝部分群）。
このような曲線上で暗号学的な演算を行う場合、それらの演算は基本的に素数位数の部分群において行われる必要がある。通常、群内の点に対する演算（スカラー乗算や、点の加算など）は、その結果得られる点も同じ群内に留まる（つまり群の演算は閉じている）。ただ、外部から不正な入力が与えられるような場合（例えば他のユーザーの公開鍵とか署名など）、与えられた点が期待する部分群内に属さない点であることがあり得る。
たとえば、↑のMoneroの件では、素数位数の部分群に属さない点をキーイメージとして提供することで不正を行う。この件ではキーイメージが素数位数の部分群内の点か検証する追加チェックを導入して対応しているけど、どのプロトコルでも単に位数lの乗算チェックを適用すればいい（適用できる）とは限らず、複雑なプロトコルの場合に元の安全性の証明が適用されなくなってしまう可能性もある。
上位プロトコルにおいて、このような脆弱性が発生しないように適切に余因子を処理していくのは、難易度の高いものになる。そこで、高速な演算の恩恵を受けつつ、余因子による煩雑さを考慮しなくても済むようにしようというのがRistrettoの目的。
Ristretto
RistrettoはMike HamburgのDecafという提案がベースになっている。Decafは、余因子 = 4のエドワーズ曲線とモンゴメリ曲線について、曲線上の点を特定の方法でエンコード/デコードすることで余因子の影響を受けない安全な素数位数の部分群を提供する。そしてDecafをベースとして余因子が8の曲線（Curve25519とか）をサポートしたのがRistretto。
Ristrettoが提供する機能は↓
- 元の曲線の点を含む素数位数群の提供：
これは、元の楕円曲線上の点に対して同じ暗号学的情報を持つ点を等価性クラスとして分類し、各等価性クラス内の1つの点を代表点として選択し、その代表点を使って素数位数の群を形成する。構成される素数位数群の位数は、元の曲線の素数位数の部分群の位数と一致する。 - 点の等価性チェック：
Ristrettoでは点の情報は内部的に元の曲線の点を使用している。この等価性チェックでは、内部表現の異なる2つの点の等価性をチェックする（内部表現が違っても同じ等価性クラスに分類されていれば等価とみなされる）。 - エンコード関数：
内部表現が等価な点についてはすべて同じビット列としてエンコードするエンコード関数 - デコード関数：
有効な点の正規のエンコードのみが受け入れられるよう、検証処理が組み込まれたデコード関数 - Hash to Point演算に適したビット文字列からRistrettoの点へのマッピング
点の演算に関しては、内部表現を利用して高速な既存の曲線の計算をそのまま利用する。
既存の曲線の実装に対して、新しい型と上記関数を追加する薄い抽象化レイヤーによって必要な抽象化を利用者に提供している。
↑の関数の具体的な群の演算については、RFC9496に記載されているristretto255（Curve25519）とdecaf448（edwards448）の疑似コードが参考になる↓
RFC 9496: The ristretto255 and decaf448 Groups
また、エンコード/デコードについては、最初のサイトにそれぞれアフィン座標で行う方法と拡張座標で行う方法の説明がある↓
- Ristretto in Affine Coordinates - The Ristretto Group
- Ristretto in Extended Coordinates - The Ristretto Group
（RFC9496の説明もこっち。アフィン座標で計算するより高速なので）
等価性の検証方法は↓
Hash to Pointの演算は、それぞれアフィン座標と拡張座標用に↓
- Elligator in Affine Coordinates - The Ristretto Group
- Elligator in Extended Coordinates - The Ristretto Group
この曲線上の点へのハッシュは、以前書いたHash to Curveなんかでも使用されているElligator 2を使ってまず要素をヤコビ四次曲線*1にマッピングして、同種写像を使ってエドワーズ/モンゴメリ曲線の点にマッピングするらしい。だから同種写像を用いた変換の説明がサイトの最初にあったのか。
間にこの曲線を挟むのは、直接マッピングするより特定の攻撃ベクトル（サイドチャネル攻撃や、点の判別攻撃、特定の数学的構造を利用した攻撃など）に対する耐性が上がりより安全性が高まるためとか。また、同種写像による変換も計算効率が良いので、コストも高くないそうな。
*1:方程式y2 = x4 + ax2 + bで定義される曲線。
