楕円ペアリング
現在,暗号で利用されているペアリングは楕円曲線上で定義される関数であり,楕円曲線上の 2点をを入力とし,ある有限体の元を出力とする関数である.代表的な楕円ペアリングに以下のものがある.
Weil ペアリング
有限体 $\mathbb{F}_q$ 上の楕円曲線 $E$ 上の点で,$m$ 倍すると無限遠点 ${\cal O}$ になる点を $m$ ねじれ点 ($m$-torsion point) と呼び,その集合を $E[m]$ で表す.$m$ が $q$ と互いに素であるとき,$E[m]$ の要素の数は $m^2$ になる.
\[ E[m] = \{P \in E(\mathbb{F}_q)\ |\ m P = {\cal O}\} \]
Weil ペアリング $e_m$ は,$\mu_m$ を $\mathbb{F}_q$ における $1$ の $m$ 乗根の群として
\[ e_m = \left\{
\begin{array}{lcl}
E[m] \times E[m] & \longrightarrow & \mu_m \\
(P,\ Q) & \longmapsto & \{f_p(Q + S)\cdot f_q(T)\}/\{f_p(S)\cdot f_q(P+T)\} \\
\end{array}\right.
\]
で定義される.
ここで,$f_p$,$f_q$ は,楕円曲線上の点 $P$,$Q$ から構成される $E$ 上の有理関数で,$f_p(R)$ は $f_p$ に $E$ 上の点 $R$ を代入したものを意味する.また,$S$,$T$ は
$E$ 上のランダムな点であるが,$e_m (P, Q)$ は $S$,$T$ の選び方にはよらない.
$1$ の $m$ 乗根の群 $\mu_m$ は,$\mathbb{F}_q$ のある拡大体 $\mathbb{F}_{q^k}$ に含まれる. このような $k$ で最小のものを $E$ の埋め込み次数と呼ぶ.埋め込み次数
$k$ は $q^k\equiv1 \pmod{m}$ を満たす最小の $k$ である.
Weil ペアリングは,楕円曲線 $E$ 上の点の加法群から有限体 $\mathbb{F}_q$ 上の乗法群への双線形写像であり,以下の関係が成立つ.
- $e_m(P,P)=1, \quad \forall P \in E[m]$
- $e_m(P,Q)=e_m(Q,P)^{-1}, \quad \forall P,Q \in E[m]$
- $e_m(P+Q,R)=e_m(P,R)\cdot e_m(Q,R),$
$e_m(P,Q+R)=e_m(P,Q)\cdot e_m(P,R),\quad \forall P,Q,R \in E[m]$
- $e_m(P,Q)=1,\quad \forall Q \in E[m]$ $\longrightarrow$ $P={\cal O}$
- $e_m(kP,Q) = e_m(P,kQ) = e_m(P,Q)^k$
Tate ペアリング
- Tate ペアリングとは
$E$ を有限体 $\mathbb{F}_p$ 上の楕円曲線,$E(\mathbb{F}_{p^k})$ を $E$ の $\mathbb{F}_{p^k}$ 有理点の成す群とする.
このとき,以下で定義される写像を Tate ペアリング ($\tau_q$) と呼ぶ.
\[ E[q] \times E(\mathbb{F}_{p^k})/q E(\mathbb{F}_{p^k}) \rightarrow {\mathbb{F}_{p^k}}^*/({\mathbb{F}_{p^k}}^*)^q \]
\[ (P,\ Q) \longmapsto f_p(Q + S)/f_p(S) \]
ここで,$S$ は $E$ 上のランダムな点である.
上記において,$qE(\mathbb{F}_{p^k})$ は,$E(\mathbb{F}_{p^k})$ の点を $q$ 倍した点からなる集合であり,$E(\mathbb{F}_{p^k})$ の部分集合となる.これより,商群 $E(\mathbb{F}_{p^k})/qE(\mathbb{F}_{p^k})$ を考えることができる.
すなわち,$P,Q \in E(\mathbb{F}_{p^k})$ に対して,$P - Q = qR\ (R \in E(\mathbb{F}_{p^k}))$ と書けるとき,$P$ と $Q$ は $E(\mathbb{F}_{p^k})/qE(\mathbb{F}_{p^k})$ で等しいとみなす.
また,$({\mathbb{F}_{p^k}}^*)^q$ は
\[ ({\mathbb{F}_{p^k}}^*)^q = \{ a \in {\mathbb{F}_{p^k}}^*\ |\ \exists b \in {\mathbb{F}_{p^k}}^*, a=b^q\} \]
であり,${\mathbb{F}_{p^k}}^*$ の部分群である.
Tate ペアリングの値は,剰余数全体の集合 ${\mathbb{F}_{p^k}}^*/({\mathbb{F}_{p^k}}^*)^q$ に属しており,一意には定まらない.すなわち,2つの元 $a, b \in {\mathbb{F}_{p^k}}^*$ が 元 $c \in \mathbb{F}_{p^k}$ を用いて $a=bc^q$ と表現可能なとき,$a$,$b$ は合同になる.
ペアリングを利用する方式では,${\mathbb{F}_{p^k}}^*$ における一意に定まる値が必要なため,$c^q$ を消去する必要がある.
$a^{p^k-1}=1, a \in \mathbb{F}_{p^k}$ の性質を利用して Tate ペアリングの値にべき乗 $(p^k-1)/q$ を行うことにより一意な値を得ることが可能である. すなわち,
$f_p(Q + S)/f_p(S)$を$(p^k -1)/q$ 乗することにより一意な値にした
\[ \tau_q(P,\ Q) = \left(\frac{f_p(Q + S)}{f_p(S)}\right)^{(p^k-1)/q} \]
を用いる.
なお,$P$ が素体有理点,$k \gt 1$,$(p^k - 1)/q$ が ($p - 1$) で割り切れる場合には,上式は
\[ \tau_q(P,\ Q)=f_p(Q)^{(p^k -1)/q} \]
というように $S$ を省略した形で求めることができる.
Tate ペアリングでは $f_p$ のみを計算すればよく,Weilペアリングのように $f_p$,$f_q$ をを求める必要はないため計算量が削減できる.
Tate ペアリングでは以下の関係が成立つ.
- $\tau_q(P,\ Q)^q = 1$
- $\tau_q(P,\ Q + R) = \tau_q(P,\ Q) \cdot \tau_m(P,\ R)$
- $\tau_q(P + Q,\ R) = \tau_q(P,\ R) \cdot \tau_m(Q,\ R)$
- $\tau_q(P,\ k Q) = (k P,\ Q) = \tau_q(P,\ Q)^k$
- $\tau_q(P,Q)=1,\quad \forall Q \in E[q]$ $\longrightarrow$ $P={\cal O}$
$\tau_q(P,Q)=1,\quad \forall P \in E[q]$ $\longrightarrow$ $\bar{Q}={\cal \bar{O}}$
なお,$\tau_q(P,P)$ は Weilペアリングと異なり一般的には $1$ ではない.
- Tate ペアリングの計算
Tate ペアリングは,以下の Miller's Algorithm を用いて計算することができる.
Miller's Algorithm
入力: $P \in E(\mathbb{F}_q)[m]$,$Q \in E(\mathbb{F}_{q^k})[m]$
$\quad (m = (m_{n-1},\cdots,m_0),m_i=\{0,1\}, m_{n-1}=1)$
出力: $\tau_m(P, Q) \in {\mathbb{F}_{q^k}}^*$
- Choose a suitable point $S \in E(\mathbb{F}_{q^k})$
- $Q' \leftarrow Q + S$
- $T \leftarrow P$
- $f \leftarrow 1$
- For $i \leftarrow n - 1$ downto 0 do
- Calculate lines $l$, $v$ for $[2]T$
- $T \leftarrow [2]T$
- $f \leftarrow f^2\cdot (l(Q')v(S))/(v(Q')l(S))$
- If $m_i = 1$ then
- Calculate $l$,$v$ for $T + Q$
- $T \leftarrow T + P$
- $f \leftarrow f\cdot (l(Q')v(S))/(v(Q')l(S))$
- Return $f^{(q^k - 1)/m}$
(備考)
$l$ は加算の入力の2点を通る直線または2倍算の入力の接線,$v$ は出力の点から $x$ 座標に下ろした垂線とする.また,$l()$,$v()$ は直線に点を代入した値とする.
楕円曲線を $y^2=x^3+ax+b$ とし,点 $P_1=(x_1,y_1)$ とするとき,点 $P_1$ における接線の式 $l$ は,$l=2y_1(y-y_1)-(3x_1^2+a)(x-x_1)$
となる.また,$P_3=(x_3,y_3)$ とするとき,$P_3$ における垂直線の式 $v$ は,$v=x-x_3$ である.$P_3=\mathcal{O}$ ならば,$v = 1$ とする.
- Projection map
$\mathbb{F}_{p^m}$ の ODタイプの曲線に対しては,拡大体上の楕円点から基礎体上の楕円点への変換であるプロジェクションが必要になる場合がある(同じ拡大体上の楕円点でペアリングを構成する場合).
プロジェクションは
\[{\psi} : P {\rightarrow} \psi(P)=\sum_{i=0}^{m-1}\phi^i(P) \]
で与えられる.ここで $\phi$ は Frobenius写像,$m$ は拡大体の拡大次数である.
\[ \tilde{\tau}_q(P,\ Q) = \tau_q(\psi(P),\ Q)\]
Bilinear ペアリング
- Distortion map
SSタイプの楕円曲線 $E$ については,distortion mapと呼ばれる $E$ 上の自己同型写像 $\phi : E \rightarrow E$ が存在し,$E(\mathbb{F}_p)$ の点を
$E(\mathbb{F}_{p^k})$ の点へ写像する.すなわち,
\[ \phi : E(\mathbb{F}_p) \rightarrow E(\mathbb{F}_{p^k}) \]
\[ \phi(P+Q) = \phi(P)+\phi(Q) \qquad \mbox{for all}\ P,\; Q \in E(\mathbb{F}_p) \]
である.
- Bilinear ペアリング
Distortion map と Tate ペアリングを組み合わせて新たな Bilinear ペアリング $\tilde{e}_q$ が下記のように定義される.
\begin{eqnarray*}
E(\mathbb{F}_p)[q] \times E(\mathbb{F}_p)[q] & \rightarrow & \mathbb{F}_{p^k} \\
(P,\ Q) & \rightarrow & \tilde{e}_q(P,\ Q)= \tau_q(P,\ \phi (Q))
\end{eqnarray*}
$\tilde{e}_q$ は non-degenerated であり,Tate ペアリングと同様に以下の関係が成り立つ.
\[ \tilde{e}_q(P,\ Q)^q = 1 \]
\[ \tilde{e}_q(P,\ Q + R) = \tilde{e}_q(P,\ Q) \cdot \tilde{e}_q(P,\ R) \]
\[ \tilde{e}_q(P + Q,\ R) = \tilde{e}_q(P,\ R) \cdot \tilde{e}_q(Q,\ R) \]
\[ \tilde{e}_q(P,\ m Q) = \tilde{e}_q(m P,\ Q) = \tilde{e}_q(P,\ Q)^m \]
Bilinear ペアリング $\tilde{e}_q(P, \ Q)$ は,$Q$ も $\mathbb{F}_p$ 有理点として取れるため扱いやすい.このため,SSタイプの楕円曲線の場合は,Tate ペアリングの代わりに Bilinear ペアリング $\tilde{e}_q$ が使われる.