1. はじめに (Introduction)

多くの暗号プロトコルでは、任意の入力（たとえばパスワード）を楕円曲線上の点へと符号化する手続きが必要となります。この手続きは「楕円曲線へのハッシュ」(hashing to an elliptic curve) と呼ばれ、そのハッシュ処理は衝突耐性を備え、かつ出力される点の離散対数を漏洩しないことが求められます。楕円曲線へのハッシュを用いる暗号システムの代表例としては、パスワード認証鍵交換 (password-authenticated key exchanges) [BM92] [J96] [BMP00] [p1363.2]、IDベース暗号 (Identity-Based Encryption) [BF01]、Boneh-Lynn-Shacham 署名 [BLS01] [BLS-SIG]、検証可能ランダム関数 (Verifiable Random Functions) [MRV99] [VRF]、および忘却擬似ランダム関数 (Oblivious Pseudorandom Functions) [NR97] [OPRFs] が挙げられます。

実装者にとって不幸なことに、ある特定の楕円曲線を用いて実装される特定のプロトコルに対して、どのハッシュ関数が適切であるのかは、プロトコルの記述からは明確でないことがしばしばあります。その一方で、ハッシュ関数の選択を誤ると、セキュリティに壊滅的な結果をもたらしかねません。

本文書は、さまざまな曲線の型に対する推奨アルゴリズムの包括的な一式を提供することによって、このギャップを埋めることを目的としています。各アルゴリズムは共通のインタフェースに従います。すなわち、任意長のバイト列を入力として受け取り、楕円曲線上の点を出力として生成します。本文書では、各アルゴリズムの実装上の詳細を示し、それぞれの推奨の背後にあるセキュリティ上の根拠を説明し、明示的に扱われていない楕円曲線についての指針を与えます。また、これらのアルゴリズムが用いる内部関数の最適化された実装も提示します。

適合するハッシュ関数を手早く規定または実装したい読者は、第 8 節を参照してください。同節では推奨されるハッシュ・トゥ・カーブ・スイート (hash-to-curve suites) を列挙し、既存のスイートを実装する方法と新しいスイートを規定する方法の双方を説明しています。

本文書は、「try-and-increment」や「hunt-and-peck」と呼ばれることもある確率的棄却サンプリング法 (probabilistic rejection sampling methods) については規定しません。これは、定数時間で計算できると見込めるアルゴリズムを規定することを目標としているためです。これらの確率的棄却法の使用は推奨されません (NOT RECOMMENDED)。それらはサイドチャネル脆弱性の恒常的な原因となってきたからです。実際の問題例としては Dragonblood [VR20] を参照してください。また、棄却サンプリング法とそれが持ち込むタイミングサイドチャネルの非形式的な説明については付録 A を参照してください。

本文書は Crypto Forum Research Group (CFRG) のコンセンサスを表すものです。

1.1. 要件表記法 (Requirements Notation)

本文書におけるキーワード "MUST"、"MUST NOT"、"REQUIRED"、"SHALL"、"SHALL NOT"、"SHOULD"、"SHOULD NOT"、"RECOMMENDED"、"NOT RECOMMENDED"、"MAY"、および "OPTIONAL" は、ここに示すようにすべて大文字で現れる場合に限り、BCP 14 [RFC2119] [RFC8174] に記述されているとおりに解釈されるものとします。