2. 背景 (Background)
2.1. 楕円曲線 (Elliptic Curves)
以下では楕円曲線について簡潔に定義し、重要なパラメータと、それらが曲線へのハッシュとどのように関係するかに重点を置いて説明します。楕円曲線に関するさらなる参考文献としては、[CFADLNV05] または [W08] を参照してください。
F を素数標数 p > 3 の有限体 GF(q) とします。（本文書では標数 2 または 3 の体上の楕円曲線は扱いません。）多くの場合、F は素体であり、したがって q = p となります。そうでない場合、F は拡大体であり、整数 m > 1 に対して q = p^m となります。本文書では拡大体の元を、原始元基底または多項式基底で、すなわち次数の昇順に並べた m 個の GF(p) の元からなるベクトルとして記述します。このベクトルの成分は 1 から始まる昇順で添字付けされます。すなわち x = (x_1, x_2, ..., x_m) です。たとえば q = p^2 で原始元基底が (1, I) である場合、x = (a, b) は元 a + b * I に対応し、x_1 = a かつ x_2 = b となります。（基底の選び方はすべて同型であることに注意してください。ただし、ある選び方は、より効率的な実装をもたらす場合があります。本文書は基底の選択について特定の仮定を置きません。）
楕円曲線 E は、2 変数の方程式と有限体 F によって規定されます。楕円曲線の方程式は、Weierstrass 形式、Montgomery 形式、Edwards 形式を含む（ただしこれらに限られない）いくつかの標準形のいずれかを取ります。
曲線 E は位数 n の代数的群を誘導します。これは、その群が n 個の相異なる元を持つことを意味します。（本文書では楕円曲線の群演算に加法的記法を用います。）楕円曲線群の元は、曲線の方程式を満たすアフィン座標 (x, y) を持つ点であり、ここで x と y は F の元です。加えて、すべての楕円曲線群は特別な元である単位元点 (identity point) を持ち、これは群演算に対する単位元として働きます。ある種の曲線（Weierstrass 曲線や Montgomery 曲線を含む）では、単位元点は (x, y) 座標の組として表現できません。
セキュリティ上の理由から、楕円曲線の暗号応用では一般に素数位数の（部分）群を用いることが要求されます。G を、そのような素数位数 r の曲線の部分群とし、n = h * r とします。この式において h は余因子 (cofactor) と呼ばれる整数です。曲線 E 上の任意の点を入力として受け取り、E の部分群 G 内の点を出力として生成するアルゴリズムは、「余因子を除去する」(clear the cofactor) と言われます。そのようなアルゴリズムについては第 7 節で論じます。
ある種のハッシュ・トゥ・カーブ・アルゴリズムは、曲線の方程式の形式、体の標数、あるいは曲線のパラメータに制約を課します。提示される各アルゴリズムについて、本文書は関連する制約を列挙します。
下の表は、曲線へのハッシュに関連する諸量をまとめたものです。
| 記号 | 意味 | 関連性 |
|---|---|---|
| F,q,p | 標数 p かつ #F = q = p^m である有限体 F。 | 素体の場合は q = p、そうでない場合は q = p^m かつ m>1。 |
| E | 楕円曲線。 | E は方程式と体 F によって規定される。 |
| n | 楕円曲線 E 上の点の個数。 | 下記で定義される h と r に対して n = h * r。 |
| G | E 上の点がなす素数位数の部分群。 | G はバイト列の符号化先となる群である。 |
| r | G の位数。 | r は n の素因数（通常はその最大の因数）である。 |
| h | 余因子、h >= 1。 | h は n = h * r を満たす整数である。 |
表 1: 記号とその定義の一覧
2.2. 用語 (Terminology)
本節では、本文書全体を通じて用いられる重要な用語を定義します。
2.2.1. 写像 (Mappings)
写像 (mapping) とは、体 F の元から、F 上で定義された楕円曲線 E 上の点への決定的な関数のことです。
一般に、ある写像が取りうるすべての入力にわたって生成できる点の全体は、楕円曲線上の点の部分集合にすぎない場合があります（すなわち、写像は全射でないことがあります）。加えて、写像は 2 つ以上の相異なる入力に対して同じ点を出力することがあります（すなわち、写像は単射でないことがあります）。たとえば、n 個の点を持つ楕円曲線への F からの写像を考えてみましょう。F の元の個数が n と等しくない場合、写像は決定的であると定義されているため、この写像は全単射（すなわち単射かつ全射）にはなりえません。
写像はまた可逆 (invertible) である場合があります。これは、写像が出力する任意の点 P に対して、x に写像を適用すると P が出力されるような F の元 x を出力する効率的なアルゴリズムが存在することを意味します。第 6 節で示す写像のいくつかは可逆ですが、本文書では逆写像のアルゴリズムについては論じません。
2.2.2. 符号化 (Encodings)
符号化 (encoding) は写像と密接に関連しています。写像と同様に、符号化は楕円曲線上の点を出力する関数です。しかし写像とは対照的に、符号化への入力は任意長のバイト列です。
本文書では、ハッシュ関数 Hf と決定的な写像とを合成することによって決定的な符号化を構成します。とりわけ、Hf は任意の文字列を入力として受け取り、F の元を出力します。決定的な写像はその元を入力として受け取り、F 上で定義された楕円曲線 E 上の点を出力します。Hf は任意長のバイト列を入力として受け取るため、単射にはなりえません。入力の集合は出力の集合よりも大きいので、同じ出力を与える相異なる入力が必ず存在するはずです（すなわち、衝突が必ず存在します）。したがって、Hf から構成される任意の符号化もまた単射ではありません。
写像と同様に、符号化も可逆である場合があります。これは、符号化が出力する任意の点 P に対して、s に符号化を適用すると P が出力されるような文字列 s を出力する効率的なアルゴリズムが存在することを意味します。しかしながら、本文書で規定されるすべての符号化が用いる Hf の実体化（第 5 節）は可逆ではありません。したがって、それらの符号化もまた可逆ではありません。
楕円曲線へのハッシュのいくつかの応用では、符号化がサイドチャネルを通じて情報を漏洩しないことが重要です。[VR20] は、この種の漏洩がセキュリティ脆弱性につながった一例です。さらなる議論については第 10.3 節を参照してください。
2.2.3. ランダムオラクル符号化 (Random Oracle Encodings)
ランダムオラクル符号化 (random-oracle encoding) は強い性質を満たします。すなわち、適切な仮定の下で、ランダムオラクル [MRH04] から識別不可能 (indifferentiable) であることが証明できます。
第 3 節で述べる 2 つの構成は、いずれも本文書の指針に従って実体化された場合、ランダムオラクル [MRH04] から識別不可能です。これら 2 つの構成は出力分布において異なります。一方は曲線上の一様ランダムな点を与え、他方は非一様な分布からサンプリングされた点を与えます。
一様な出力分布を持つランダムオラクル符号化は、ランダムオラクルモデルで安全性が証明された多くの暗号プロトコルでの使用に適しています。さらなる議論については第 10.1 節を参照してください。
2.2.4. シリアライズ (Serialization)
符号化に関連する手続きとして、楕円曲線上の点をビット列に変換するものがあります。これはシリアライズ (serialization) と呼ばれ、典型的には点をコンパクトに保存または伝送するために用いられます。その逆演算であるデシリアライズ (deserialization) は、ビット列を楕円曲線上の点に変換します。たとえば [SEC1] や [p1363a] は、シリアライズとデシリアライズの標準的な方法を与えています。
デシリアライズが符号化と異なるのは、特定の文字列（すなわち、シリアライズ手続きによって出力されたもの）だけがデシリアライズ可能である、という点です。これに対して本文書が関心を持つのは、任意の文字列から楕円曲線上の点への符号化です。本文書はシリアライズおよびデシリアライズを扱いません。
2.2.5. ドメイン分離 (Domain Separation)
ランダムオラクルモデルで安全性が証明された暗号プロトコルは、しばしば、ランダムオラクルがそのプロトコルに関連するクエリ（攻撃者によるクエリを含む）にのみ応答するという仮定の下で解析されます [BR93]。実際には、2 つのプロトコルが同じ関数を用いてランダムオラクルを実体化する場合、この仮定は成り立ちません。具体的に、ランダムオラクル RO にクエリを行うプロトコル P1 と P2 を考えてみましょう。P1 と P2 がともに同じ値 x について RO にクエリを行うと、いずれか一方または双方のプロトコルの安全性解析が無効になる可能性があります。
この問題に対処する一般的な方法はドメイン分離 (domain separation) と呼ばれ、単一のランダムオラクルで複数の独立したオラクルをシミュレートできるようにするものです。これは、シミュレートされる各オラクルが、他のすべてのシミュレートされるオラクルが見るクエリとは相異なるクエリを見るように保証することで実現されます。たとえば、単一のオラクル RO が与えられたときに 2 つのオラクル RO1 と RO2 をシミュレートするには、次のように定義することが考えられます。
RO1(x) := RO("RO1" || x)
RO2(x) := RO("RO2" || x)
ここで || は連結演算子です。この例において、"RO1" と "RO2" はドメイン分離タグ (domain separation tags, DSTs) と呼ばれます。これらは、RO1 と RO2 へのクエリが RO への同一のクエリを生じさせないことを保証し、したがって RO1 と RO2 を独立したオラクルとして扱っても安全であることを意味します。
一般に、ドメイン分離では、シミュレートされる各オラクルについて相異なる単射的な符号化を定義することが要求されます。上の例では、"RO1" と "RO2" は同じ長さであり、したがってプレフィックスとして用いられる場合にこの要件を満たします。本文書で規定されるアルゴリズムは、単射性を保証するために異なるアプローチを採ります。詳細は第 5.3 節および第 10.7 節を参照してください。