Develop with pleasure!

福岡でCloudとかBlockchainとか。

楕円曲線上の点を出力するハッシュ関数の標準化 Hash to Curves

Cryptography

楕円曲線を使用したPedersen CommitmentやBLS署名など、誰もその離散対数を知らない点を利用する暗号プロトコルを最近よく見かける。ただ、プロトコルの説明では、そのような点の導出方法があまり詳しく書かれていなかったりすることもあり、アルゴリズムの選択を誤ると脆弱性の原因となる可能性が出てくる。

そんな点の導出方法について、さまざまな楕円曲線に対応した推奨アルゴリズムを定義しようというのが、現在IETFでドラフトが提案されている任意の入力値を楕円曲線上の点に変換するハッシュ関数↓

datatracker.ietf.org

ハッシュ関数の仕様

この仕様では、入力値（バイト列）を楕円曲線の点にエンコードするのに以下の３つの関数を定義している。※ 正式な仕様は↑参照。

hash_to_field

hash_to_field関数は、任意の入力値（バイト列）msgを有限体F上の１つ以上の要素にハッシュする関数。

  • 入力
    • 任意の入力値msg
    • 出力する要素の数count
  • 出力
    • count個の有限体Fの要素のリスト

hash_to_field関数は、まず補助関数expand_messageを呼んで、msgのハッシュ値を計算する。仕様では、SHA-2やSHA-3、BLAKE2のハッシュ関数に加えて、可変長の出力値をサポートするSHAKE128、BLAKE2Xが利用可能になっている。 続いて、生成したハッシュ値を有限体F上の要素として解釈する。※ expand_message関数は、countで指定した要素数を満たす長さのランダムデータを出力する。

具体的な疑似コードは、5.1章に記載されてる。

map_to_curve

map_to_curve関数は、有限体F上の要素から有限体F上に構成された楕円曲線E上の点を計算する写像関数。

  • 入力
    • 有限体Fの要素u
  • 出力

写像関数自体は、対象とする楕円曲線の形式（モンゴメリ曲線、ワイエルシュトラス曲線、ツイストされたエドワーズ曲線など）によって、それぞれ推奨されるロジックがある模様。具体的な仕様は、6章で定義されている。SSWU（Simplified Shallue-van de Woestijne-Ulas）方式とか*1、Elligator 2方式とか。

基本的には楕円曲線の方程式から座標を計算することになるので、y座標の候補は2つ存在することになる。この曖昧さの解消のため、関数の入力値でy座標の偶奇を指定できるようにしているっぽい。どちらかに固定すると出力される点の数が半分になるから？

clear_cofactor

clear_cofactor関数は楕円曲線E上の点を部分群G上の点に変換する関数。

※ Bitcoinの楕円曲線secp256k1やNISTの曲線P-256、P-384、P-521などcofactor = 1の曲線においては、この操作は必要ない。

2つのエンコード方式

基本的には上記の3つの関数を順に実行して、任意の入力値を楕円曲線G上の点に変換する。

  1. hash_to_field関数で有限体Fの要素を出力
  2. 1の要素をmap_to_curve関数で楕円曲線上の点に変換
  3. 2の点に対してclear_cofactor関数を実行した点が最終的に出力される点

上記のシンプルなエンコード方式をencode_to_curve関数として定義している。ただ、この関数は入力値に対して出力される点が一様にランダムではないとされていて、一様に分布する点を出力する関数としてhash_to_curve関数を定義している。この関数の処理は、

  1. hash_to_field関数で有限体Fの要素を2つ出力（count = 2を指定）
  2. 1の2つの要素をmap_to_curve関数で楕円曲線上の点に変換（Q0, Q1）
  3. 2の2つの点を加算してR = Q0 + Q1を計算
  4. 3の点Rに対してclear_cofactor関数を実行した点が最終的に出力される点P

というもので、出力する有限体の要素が2つになり、それらの点を加算しているのが違い。これが一様な分布でG上の点を出力するポイントなのか。

暗号スイート

現在定義されている暗号スイートのリストがこちら。

Bitcoinが採用しているsecp256k1以外に、NIST系の曲線やcurve25519、BLS12-381などが定義されている。これ以外の楕円曲線を利用したHash to Curveを定義する方法はこちら。

参照実装

参照実装はこちら。現状、Sage、Go、Rustで書かれたものがある。

Hash and Increment

単純な楕円曲線のハッシュ関数だとHash and Incrementという手法がある。ハッシュ値を楕円曲線上の点のx座標として対象となる点を探し、有効な点でなければ有効な点が見つかるまでハッシュ値を1ずつインクリメントしていく。

この場合、入力する値によって計算コストが変わってくるのと、定数時間処理にするのが難しいので、今回のHash to Curvesみたいな提案が出てきてるのかな。

*1:曲線の方程式のパラメーターa, bが0の場合（secp256k1やBLSなどの曲線の場合）、SSWU方式はそのまま使えないので、aとbが0ではない同種写像を持つ曲線を使ってSSWUで計算した点を、元の曲線の点に変換するSSWUAB0方式が採用されている。