楕円ペアリング

現在,暗号で利用されているペアリングは楕円曲線上で定義される関数であり,楕円曲線上の 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$ 上の乗法群への双線形写像であり,以下の関係が成立つ.

  1. $e_m(P,P)=1, \quad \forall P \in E[m]$
  2. $e_m(P,Q)=e_m(Q,P)^{-1}, \quad \forall P,Q \in E[m]$
  3. $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]$
  4. $e_m(P,Q)=1,\quad \forall Q \in E[m]$ $\longrightarrow$ $P={\cal O}$
  5. $e_m(kP,Q) = e_m(P,kQ) = e_m(P,Q)^k$

Tate ペアリング

Bilinear ペアリング

inserted by FC2 system