2. 背景

2.1. 楕円曲線

以下は、重要なパラメータとその楕円曲線へのハッシュとの関係に重点を置いた、楕円曲線の簡潔な定義です。楕円曲線の詳細については、[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の要素です。さらに、すべての楕円曲線群には、群演算の単位元として機能する特別な要素である無限遠点（単位点）があります。特定の曲線（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上の点の数。	n = h * r。ここで、hとrは以下で定義される。
G	E上の点の素数位数部分群。	Gはバイト文字列がエンコードされる宛先群。
r	Gの位数。	rはnの素因数（通常は最大の因数）。
h	余因子、h >= 1。	hはn = h * rを満たす整数。

表 1: 記号とその定義の要約

2.2. 用語

この節では、文書全体で使用される重要な用語を定義します。

2.2.1. マッピング（Mappings）

マッピングは、有限体Fの要素から、F上で定義された楕円曲線E上の点への決定論的な関数です。

一般に、考えられるすべての入力に対してマッピングが生成できるすべての点の集合は、楕円曲線上の点のサブセットにすぎない場合があります（すなわち、マッピングは全射ではない可能性があります）。さらに、マッピングは、2つ以上の異なる入力に対して同じ点を出力する場合があります（すなわち、マッピングは単射ではない可能性があります）。例えば、n個の点を持つ楕円曲線へのFからのマッピングを考えます。Fの要素数がnと等しくない場合、マッピングは決定論的であると定義されているため、このマッピングは全単射（単射かつ全射）にはなり得ません。

マッピングは可逆（invertible）である場合もあります。これは、マッピングによって出力された任意の点Pに対して、マッピングをxに適用するとPが出力されるようなF内のxを出力する効率的なアルゴリズムが存在することを意味します。第6節で示すマッピングの一部は可逆ですが、この文書では反転アルゴリズムについては説明しません。

2.2.2. エンコーディング（Encodings）

エンコーディングはマッピングと密接に関連しています。マッピングと同様に、エンコーディングは楕円曲線上の点を出力する関数です。しかし、マッピングとは対照的に、エンコーディングへの入力は任意の長さのバイト文字列です。

この文書では、ハッシュ関数Hfと決定論的マッピングを合成することにより、決定論的エンコーディングを構築します。特に、Hfは任意の文字列を入力として受け取り、Fの要素を出力します。決定論的マッピングはその要素を入力として受け取り、F上で定義された楕円曲線E上の点を出力します。Hfは任意の長さのバイト文字列を入力として受け取るため、単射にはなり得ません。入力の集合は出力の集合よりも大きいため、同じ出力を与える異なる入力が存在する必要があります（すなわち、衝突が存在する必要があります）。したがって、Hfから構築されたエンコーディングも単射ではありません。

マッピングと同様に、エンコーディングは可逆である場合があります。これは、エンコーディングによって出力された任意の点Pに対して、エンコーディングをsに適用するとPが出力されるような文字列sを出力する効率的なアルゴリズムが存在することを意味します。しかし、この文書で指定されているすべてのエンコーディングで使用されるHfのインスタンス（第5節）は可逆ではありません。したがって、それらのエンコーディングも可逆ではありません。

楕円曲線へのハッシュのいくつかのアプリケーションでは、エンコーディングがサイドチャネルを通じて情報を漏らさないことが重要です。[VR20]は、このタイプの漏洩がセキュリティの脆弱性につながる一例です。詳細については、第10.3節を参照してください。

2.2.3. ランダムオラクルエンコーディング（Random Oracle Encodings）

ランダムオラクルエンコーディングは強力な特性を満たします。適切な仮定の下で、それがランダムオラクル[MRH04]と識別不能であることを証明できます。

第3節で説明する2つの構成は、この文書のガイドラインに従ってインスタンス化された場合、ランダムオラクル[MRH04]と識別不能です。構成は出力分布が異なります。一方は曲線上の一様ランダムな点を与え、もう一方は非一様分布からサンプリングされた点を与えます。

一様な出力分布を持つランダムオラクルエンコーディングは、ランダムオラクルモデルで安全性が証明されている多くの暗号プロトコルでの使用に適しています。詳細については、第10.1節を参照してください。

2.2.4. シリアライゼーション（Serialization）

エンコーディングに関連する手順は、楕円曲線の点をビット文字列に変換することです。これはシリアライゼーションと呼ばれ、通常、点のコンパクトな保存や送信に使用されます。逆の操作であるデシリアライゼーションは、ビット文字列を楕円曲線の点に変換します。例えば、[SEC1]と[p1363a]は、シリアライゼーションとデシリアライゼーションの標準的な方法を示しています。

デシリアライゼーションがエンコーディングと異なる点は、特定の文字列（すなわち、シリアライゼーション手順によって出力されたもの）のみがデシリアライズできることです。対照的に、この文書は、任意の文字列から楕円曲線の点へのエンコーディングを扱います。この文書では、シリアライゼーションやデシリアライゼーションについては扱いません。

2.2.5. ドメイン分離（Domain Separation）

ランダムオラクルモデルで安全性が証明されている暗号プロトコルは、多くの場合、ランダムオラクルがそのプロトコルに関連するクエリ（敵対者によるクエリを含む）にのみ回答するという仮定の下で分析されます[BR93]。実際には、2つのプロトコルがランダムオラクルをインスタンス化するために同じ関数を使用する場合、この仮定は成り立ちません。具体的には、ランダムオラクルROにクエリを行うプロトコルP1とP2を考えます。P1とP2の両方が同じ値xに対してROにクエリを行う場合、一方または両方のプロトコルのセキュリティ分析が無効になる可能性があります。

この問題に対処する一般的な方法はドメイン分離と呼ばれます。これにより、単一のランダムオラクルが複数の独立したオラクルをシミュレートできるようになります。これは、各シミュレートされたオラクルが、他のすべてのシミュレートされたオラクルが見るものとは異なるクエリを見るようにすることで実行されます。例えば、単一のオラクルROが与えられた場合に2つのオラクルRO1とRO2をシミュレートするには、次のように定義します。

RO1(x) := RO("RO1" || x)
RO2(x) := RO("RO2" || x)

ここで、|| は連結演算子です。この例では、"RO1"と"RO2"はドメイン分離タグ（DST）と呼ばれます。これらは、RO1およびRO2へのクエリがROへの同一のクエリを引き起こさないことを保証します。つまり、RO1とRO2を独立したオラクルとして扱うことが安全であることを意味します。

一般に、ドメイン分離には、シミュレートされる各オラクルに対して異なる単射エンコーディングを定義する必要があります。上記の例では、"RO1"と"RO2"は同じ長さであるため、プレフィックスとして使用される場合にこの要件を満たします。この文書で指定されているアルゴリズムは、単射性を保証するために異なるアプローチをとります。詳細については、第5.3節および第10.7節を参照してください。