数理解析研究所講究録 1420 巻 2005 年 174-182

174
2

超楕円暗号の最近の話題

楕円曲線とその離散対数問題
$K$

: 有限体
の楕円曲線は、 方程式 ($K\mu_{arrow}$$4\mathrm{V}\mathrm{e}\mathrm{i}e\mathrm{r}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{s}\mathrm{s}$標準形)$E/I(\cdot\tau/^{\underline{0}}\{- a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}\dashv\vee a_{4}\cdot \mathrm{r}\vdash a_{\dot{\mathrm{r}}}.

趙 晋輝によって定義される、無限遠点 O
数曲線である。

中央大学理工学部
情報工学科
はじめに

a\rfloor.a\}\cdot a2,$$‘ \mathrm{z}4,a\epsilon\in K$をもつ非特異代楕円曲線の KK 有理点 $E^{}(.K)$ は$F_{\lrcorner}(Kj=$

1$=(0_{\mathrm{t}}1,0)${ $(x.y)$ C-$K^{\underline{9}}|y\underline’- tafxy|a_{3}y=x^{l}\dashv-\prime \mathrm{z}_{2}x^{\underline{9}}\vdash a_{4}x\dashv‘\iota_{6}$}$\cup\{O\}$と定義される。

RSA の誕生後、 十年足らずのうちに提案された楕円曲線上$E(K)$ は、 可換群をなすことが知られている。

の離散対数問題を利用した暗号系 (通称楕円暗号) は、 今や、
ポスト RSA の公開鍵暗号の標準方式となりつつある。

群の演算則 :

law

$C.1\mathrm{l}\mathrm{O}\mathrm{l}\cdot \mathrm{d}- \mathrm{t}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\iota \mathrm{l}\mathrm{t}$楕円曲線上の離散対数間題

最近、超楕円暗号をはじめ、楕円暗号の一般化の研究も盛んに行われている。

Given
find

$P,$ $Q\in E\dot{(}\mathrm{F}_{a}.$$7l\in \mathbb{Z}h.t$) $.P\in<Q>$. $F^{)}=nQ$ .

楕円曲線上の離散対数問題に基づいて、楕円 EIGamal 公開鍵
暗号、 楕円 DSA ディジタル署名などが提案されている,,

3

楕円暗号の一般化
Abel 群4上の一般的な離散対数問題$C_{t}=<g>,\forall/|\in G,$ fir}\mbox{\boldmath $\zeta$}t$G$

楕円暗号の一般化を研究する意味

1. Ilasse-W 観定理より、 種数 9 のヤコビ多様体の位数は$x\in \mathbb{Z}_{\vdash},$ti.t. $.J/^{1}=Jl$ , or$\{q-\rceil/21)^{\sim/\prime}’\leq\# J\mathrm{t}\mathrm{F}_{g})\leq(q^{1/2}+1\rangle\underline{)}_{\prime},\backslash$$x=1\mathrm{o}\mathrm{b}^{\mathrm{y}}ff\mathrm{c}/$群多様体はアフィン代数群と Abel 多様体を考えればよい。
完備な群多様休は Abel 多様体であり、 群演算は可換となる。
楕円曲線は、 種数 1 の Abel 多様体である。

$\# J\langle \mathrm{F}_{q})=\mathrm{O}(q^{g})$となるので、プロセッサの語長を種数分の 1 まで (ビット幅)小さくとることができる。
80b 汁,(1). ハードウェア実現のメリト-). ソフトウェア実現のメリト
よって、廉価なプロセッサを利用する、 コンパクト化或は処理、 伝送速度の能率を高めることが可能である。
$\mathrm{g}=2_{:}$

離散対数の発展歴史 :線形代数群を用いた離散対数問題は、
準楷数時間
例えば RSA,$\mathrm{E}.1\mathrm{G}^{1}\mathrm{a}\mathrm{m}\mathrm{a}1$

楕円曲線 (忌数 1 の: 鍵長$\dot{}\backslash \mathrm{b}\mathrm{e}^{1}.1$$1\mathrm{t}\mathrm{J}24$

ビット多様体) の離散対数問題は、完全指数時間例えば、楕円暗号: 鍵長 360 ビット$\mathrm{t}^{\eta}$

2. より豊かな曲線:
位数が
類の数は、

$\# J(\mathrm{F}_{\mathrm{p}^{m}}.1=O(N)$の種数 il のヤコビ多様体の同種) である。

$\#\{J(\mathrm{F}_{\mu^{m}})\}=O\{4g\mathit{1}\mathrm{V}^{1_{Tg}^{1}}-$

3. より. 般的な枠組みの申で楕円暗号の安全性に対する系統的な検討と理解が可能 (descent)$-\sim$超楕円曲線 (種数 2 以上の)$\mathrm{A}1$$\mathrm{e}1$多様体)$\iota^{1}..\mathrm{g}..\backslash _{l}4’ \mathrm{c}\mathrm{i}1$

種数 2-4; 完全指数時間
種数...t$\dot{\mathrm{c}}\mathrm{X}.\cdot$

例えば、超楕円暗号: 鍵長 160 ビット: 準振数時間$\mathrm{g}.=3_{\backslash }56\mathrm{b}\mathrm{i}\mathrm{t}$175
どんな Abol 多様体がよいのかつ計算の面で考えると、

5

超楕円曲線
体 $K$ 上で種数 の超楕円曲線 $H$$g$

代数曲線は、 関数体のイデアル群によって因了群を表現することで、 欝算に有利 (Groboar 基底を用いる演算$H/K$ :$y^{\underline{?}}+h(x\}y=f(x)$$\rangle$

ここで $J(x,)$ はモニックで.

$f(.x)=\underline{9}g+1_{}c\mathrm{J}\iota^{\mathrm{l}}\mathrm{g}h\dot{(}x.\rangle\leq g$$.(\{_{P}.\mathrm{g}$とする, また, $H$ は, 特異点を持たないとする.

Superclliptic curves

標数 $\neq 2,3$ の体 $R’$ の五で、 種数 の超楕円曲線 $H$$g$$C_{nb}$

曲線

.

$H$

$Y’=F(X)\}$

ここで、 $F(X)$ は、

特に、 超楕円曲線の場合は、 二次代数体の高速算法を類似することで、 イデアル操作なしで高速演算可能。

$\underline{?}r\mathit{4}+1$

或は$\underline{\circ}g+2$

次の重根を持たない多項式とする。

種数が 以上の場合に、 H. の有理点 H(紛は群ではないが、$\underline{\eta}$

それの 次対称積から、 ヤコビ多様体という因子群を作るこ$g$とが出来る。

($\mathrm{Y}\mathrm{V}\mathrm{e}\mathrm{i}\mathrm{l}\rangle\backslash$

因子$D(H)$$=${)($\mathrm{d}\mathrm{i}\backslash \prime \mathrm{i}\mathrm{s}c$$\mathrm{t}\mathrm{l}\iota\cdot \mathrm{g}$.

$\mathrm{c}\mathrm{q}\mathcal{D}$$\sum \mathrm{o}\mathrm{z},F,$.

Ket (deg)$H$

on $H$
Z.

$\uparrow n_{l}\in$$P‘\in H(K^{\prime\prime p})$}$\sum_{\iota}n\iota_{j}F_{i}‘-\cdot\sum;^{m_{i}}$’$.=D_{\mathfrak{l}1}(H)$の関数体$K(H).=\{p/q|p,q\in K^{\hslash\prime p}[u.v_{\mathrm{J}}^{1},$ $q\neq 1l$

mod$8J^{\underline{\gamma}}+\mathrm{s}’ l1\{r\iota)-J(u)\}$$\dot{\theta}$

被約因

主因 \ell 群$D_{l}(H)= \{(f)=\sum_{P}\nu_{P}\{f)P|f\in K(H)\}\subseteq$$H\mathit{0}3\mathrm{J}_{\acute{e}1\underline{\Gamma})}‘ 1)iu1\backslash ’ i1\mathrm{J}$Do(H)$D^{0}\langle H1$$\mathrm{J}^{\acute{\wedge}}$の任意の因了は. 次のような半被約因子と線形同値である.

irty &i$D= \sum P,$ $-r\cdot\infty$$J(H)=D^{0}(H\}/D_{l}(H)${ し、と定義される ‘’$\mathrm{H}$,$P_{i}\in \mathrm{S}\backslash \iota \mathrm{p}\mathrm{p}\{D)/\{1, t,\}$は, 超楕円対合 $Prightarrow-P=\langle a.x,$ $-y-l\iota$ ) とする.となる $D$ と線形同値
により, rさらに,$\iota$超楕円曲線のヤコビ多様体上の離散対数問題
Given $P,$ $Q\in J(H)$ .

find$n\in \mathrm{Z}s.t$. $P=n.Q$ .

$\mathrm{R}^{\cdot}e.a1\tau t1111-\mathrm{r}\mathrm{i}\mathrm{o}\mathrm{t}’ \mathrm{h}$$\cdot$$\leq g$

な半被約因子が一意に存在する. これを被約因子という.

Cantor algorithm

Mumford による因子の多項式表現

ヤコビ多様体の群演算は一般的には難しい力\nwarrow 超楕円曲線の任意の半被約因子 $D$ は関数体が二次関数体であるため, 二次数体において古くからの合成と還元アルゴリズムが利用できる.
知られている$\mathrm{G}\mathrm{a}\mathrm{I}\mathrm{J}\mathrm{a}9$超楕円曲線のヤコビ多様体の演算を二次数体の類群の演算へ帰着した, 種数の多項式時間のアルゴリズムが提案されている. さらに標数 2 の場合まで拡張されている.

$(U. V)_{,} U_{\backslash }V\in \mathrm{F}_{q}[x]$となる多項式のペアで一意に表現できる$D=\mathrm{d}\mathrm{i}\vee(UV).=\mathrm{g}c\mathrm{d}(U_{\backslash }V-Y)$$V^{7}arrow+\mathrm{K}\iota V-F\equiv \mathit{0}$$\mathrm{m}\mathrm{o}\mathrm{d}$

$U,$

.

$\mathrm{d}\mathrm{c}\mathrm{g}V<\mathrm{d}\mathrm{c}\mathrm{g}U$$D= \sum$ $m(x_{\mathrm{t}},y_{i} \}\Rightarrow U\dot{(}X)=\prod‘(X-x_{\mathrm{t}})^{m}\cdot\backslash y_{j}=V(Xi_{i})$$\mathrm{C}!\mathrm{a}\iota \mathrm{l}\mathrm{t}\mathrm{o}\mathrm{r}$アルゴリズム : 計算量は$O(y\mathrm{r}^{3}\log p)$である,$\deg U\leq g\Leftrightarrow \mathrm{d}\mathrm{i}\mathrm{v}(U, V)$

is a reduced divisor

178
Cantor Algorit$b_{1}1$$D_{1}=\mathrm{c}1\mathrm{i}\mathrm{v}\langle$$a_{1},$

Harley algorithm$\mathrm{h}\mathrm{u}\mathrm{l}$と$D_{2}=\mathrm{c}1\mathrm{i}\backslash ’(a_{2},h_{-}.’\dot{)}$との和:$D=i1\mathrm{i}\mathrm{v}\dot{(}\mathit{1}1b\rangle$

を求め

るために

Strp 1 (Cfin}p(\lambda \ition)$\tau$$\mathrm{f}\mathrm{F}\mathrm{G}\mathrm{a}11\mathrm{d}:\gamma.\mathrm{H}\mathrm{a}11\mathrm{c}\}’$の半被約因子表現 {$D$$a,$ $b)$

を求$a$, : a2,)$\mathrm{o}\mathrm{i}_{\mathrm{J}1}\mathrm{t}\mathrm{s}$otl JIy-

1. 楕円曲線における chord-tangent 法を IIEC へ拡張) の場合分けにより重複処理を省く
KaraLsubt し乗算による中国人剰余定理、
3.

2, 入力

める.

(

$\mathrm{p}_{1}\mathrm{r}\mathrm{t}\mathrm{i}t\iota \mathrm{g}1$$\cdot$

まず以下の二成演篠によって,$d:=\mathrm{g}(^{\backslash }.\mathrm{d}$.

(ANTS ) Com.,
perelliptic curves over finite fields

2000$\mathrm{d}\mathrm{i}\backslash \dot{0}\mathrm{R}$$\mathrm{r}$$\mathrm{N}e\mathrm{v}\backslash ^{l}\mathrm{t}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{t}\theta.1^{\cdot}j1\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}_{\backslash }$$b_{1}+b_{2}-f\iota$)$=s_{\mathrm{J}}a_{\mathit{1}}+s_{-}’ a_{2}+s_{3}(b_{1}+b_{\grave{}}.+h)$

高速化$a=a_{1^{O’}l}/\prime\prime\underline’$

Step 2$\mathrm{d}$):$\dot{(}\mathrm{R}\epsilon \mathrm{c}\mathrm{l}\iota\iota c\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{d}\mathrm{i}\mathrm{v}(a_{:}b)$algorithni より高速
Genus 2 の HEC に特化mool a$b=\langle s_{1}a_{1}\mathrm{I}’\cdot\underline{)}+s_{2}a_{2}b_{\mathrm{t}}+s_{\delta}(b_{1}b_{2}+f))/d$$\mathrm{C}’;\mathrm{u}\mathrm{z}\mathrm{t}01^{\backslash }$が被約でない, つまり“ $\mathrm{g}(\prime A)>g$ の場合

以下の演算を cleg(a’‘)
ヘー意に還元できる.

になるまで繰り返せば被約因子$\leq \mathit{9}$$a’=(f-hl’-b^{2})/(4$$b’=-h-b\mathrm{r}\mathrm{r}\mathrm{J}()(f\mathrm{r}\iota’$

Step3 $D=(a’,b’)$ を出力する。
しかし、 構円暗号に比べて、暗号化、復号化の速度は数倍
遅い。
10

6

種数 2 の超楕円曲線の高速演算法

次に

種数 2 の超楮円曲線$ff/\mathrm{F},,$.

$\}^{\sim\underline{\mathrm{Q}}}=F(X)$$F\langle X$) $=X^{r_{)}}\llcorner+f_{1}X^{4}+\cdots$ 十$.f..\cdot\in \mathrm{F}_{q},$$D_{\}}=P_{21}+P_{22}-2\infty$$D$ の 4 点多項式。

.

と線形同値な被約因 \ell を求める.
$P_{j}\dot,=\langle \mathit{9}.\cdot\dot{\mathrm{t}}.i,$)$/\uparrow,\mathrm{j}.$$i.\mathrm{i}j\backslash =1.2$

わる 6 点によって定まる.

$D_{3}=D_{!}+D_{\sim^{\gamma}}$$P_{\mathrm{J}1}+P_{\dot{\mathrm{t}}^{\underline{9}}}+P_{21}+P_{2_{\vee}^{r,}}+P_{\mathrm{J}\mathrm{J}}+P_{72}-6\infty=(?’-V)$つまり.

$l_{-\lrcorner}^{f}$$D_{\acute{\mathrm{A}}}+D_{\wedge}\downarrow\rangle$となる。 ここで、$U_{2}(X)=1X-x..71\grave{)}(X-x_{22}.)$ ,:} $=1$ という典型的な場合を考える。

$D_{3}$

或いは、 $D_{3}:=-((V-Y\rangle-D)$は被約因子である.
$[I_{3}=(F\cdot’- V^{?}’)/U$

まず直接短し算すると、 半被出面 .
$g’$$D=P|)+P_{12}+P_{-1})+P_{\sim^{l}arrow},$ $-4\infty=(U,$V_{3}\equiv-V$

V)$が得られて、 U=U, 砺となる。
また、剰余定理により、,とすると、 $F\equiv V^{2}$ madが求まる.

$1=f\iota_{1}U_{1}+f\iota_{1,\lrcorner}.U$$V$$V=h_{2}.U_{2}V7+l_{l|}$$+D’=11$$[r_{\mathrm{J}(Xj=}\dot{\mathrm{t}}X-x_{1}’)\wedge(X-x_{1_{\vee}^{)}}.\cdot)\backslash$$D\mathrm{g}:=-\mathrm{t}P_{S1}’+P_{32}-2\infty)$$\mathrm{g}.\mathrm{c}^{\backslash }c\mathrm{I}(U_{\grave{\mathrm{A}}},$

を内挿する $V(X)$ は 3 次関数 $(V-Y)$ が定義する主因子は、 曲線 $(V-Y)$ と $H$ と交$f_{0\text{、}}$$\mathrm{d}\mathrm{i}\mathrm{f}\mathrm{f}\mathrm{l}^{1}(F’)\neq 0$の足し算$D_{1}=\langle U_{\mathrm{i}},$ $V_{1}\}_{:}D_{-}.’=(U_{\underline{J}}., \mathrm{V}2)$$D_{1}=P_{11}+P_{1}\underline{\cdot\cdot,}-2\infty$.

$D$$\backslash$こt 予$\acute{2}$)$\mathrm{n}$

$U$

と中国

$\mathrm{o}\mathrm{d}U_{\mathrm{I}}U_{2}$11.

$1^{\underline{1}}$lnoct$\mathrm{I}r_{3}$177
標数 2 の場合への拡張

Li .
$\Re$

ハードウエア実装

高速乗算器を持たない安価な CPU
安全な曲線を高速に構成可能
霞 1:] による内舞とその主因$\mathrm{Y}^{\cdot}-4^{\cdot}(\mathrm{X}\backslash$$\mathrm{J}’$.

一般標数のの場合への拡張$\mathrm{S}\mathrm{f}\mathrm{f}\backslash f$

Harley アルゴリズ\Delta の研究に必要不岨欠
数式処理システ\Delta 上等への実装を考慮

14

li$

$\# F_{J}(\mathrm{F}_{\eta L^{\mathfrak{l}}}.)$

乗算$\# J\langle \mathrm{F}_{9\mathrm{J}J})\approx q_{lJ}^{2}\Rightarrow \mathrm{f}\mathit{4}H\approx\sqrt{t\mathit{1}b}$

駕伽

種数 3 の超楕円曲線の高速算法

7

楕円曲線暗号との比較

種数 3 の超楕円曲線の高速算法. $c_{l}=.p’|$: 素数$\neq\underline{9}_{\backslash }\overline{(}$$p$$(c\mathrm{l}\mathrm{a}\backslash \cdot \mathrm{s}\mathrm{i}\mathrm{c}\mathrm{a}\mathit{1})$

コスト:

.

$M\approx 2(\log q)^{\underline{\gamma}}$l\mbox{\boldmath $\nu$}Ifj\approx 4 蜘$C/\mathrm{F}_{\iota_{\mathit{1}}}$: $Y^{arrow)}.=F(X)$$F(X)=\prime \mathrm{Y}^{\prime 7}+f\overline{.}\backslash ^{f\mathrm{Y}^{6}+\acute{\int}(X^{\{}+\cdots+f_{0}\in}$$\mathrm{d}\mathrm{i}_{\mathrm{b}\mathrm{C}}.\langle\Gamma^{t})\neq(\}$比較対象 IEEE
加算:$\mathrm{P}1363$

方式
倍算: $10M$$\{\mathrm{J},\tau \mathrm{c}\mathrm{o}\mathrm{l})\mathrm{i}\mathrm{a}\mathrm{n}\mathrm{P}\mathrm{r}\mathrm{o}.\dot{|}\mathrm{t}^{2},\mathrm{c}\mathrm{r}\mathrm{i}\iota\cdot\epsilon\rangle$$16M_{\backslash }2$のとき、超楕円曲線のほうが楕円曲線より高速 i
超楕円曲線:
楕円曲線 :$Gene^{\iota}\mathrm{r}\mathrm{i}c.\cdot$case$D_{1}=P_{11}+P_{1_{\vee}}\cdot\cdot+P_{1’S}-3\infty$$I_{Jl}<14M\mathrm{K}i$$D_{2}=P_{21}+P_{\underline{)}}.2+P_{!\}2}-\backslash J?\infty$’改,$U_{1}(X^{\cdot})=(X-x_{11})(X-x_{12}.)(X-x_{13})_{:}$,$\mathrm{H}_{\acute{\tau}}\mathrm{u}\cdot 1\mathrm{e}\backslash$$U_{2}(X)=(X-x_{2\mathrm{I}})(_{\grave{J}}’-x_{22})(X-x_{3\cdot \mathrm{f}}.)$$\mathrm{P}1363$$\# J_{C}(\mathrm{F}_{4H})\approx\# E(\mathrm{F}_{q\rho}.)\approx 2^{18\mathrm{b}}$

16

16

,

照 ]
$X$

178
種数 3 超楕円曲線の暗号応用での利点

種数 3 の Hmrley$.\mathrm{t}11\Pi 1$$\mathrm{a}\mathrm{l}\mathrm{g}.()\iota^{-}$」の概略

1. 園子の分類
位数$\mathrm{P}\mathrm{i}^{r}A\mathrm{P}\approx$

種数

定義体

$\mathrm{x}$$\mathrm{s}\mathrm{i}^{r}/.\mathrm{e}$($\mathrm{H}.\mathrm{a}\mathrm{a}.\mathrm{i}\mathrm{e}- 4\mathrm{V}\acute{\mathrm{e}}\mathrm{i}\mathrm{l}$range)

2$\mathrm{i}\mathrm{t}$..

$641_{3}\mathrm{i}\mathrm{t}\mathrm{C}_{-\prime}\Gamma \mathrm{U}$$\mathrm{C}_{\mathrm{o}11}^{\mathrm{t}},‘ 1.\mathrm{z}$Karatsuba 乗算$\mathrm{b}.1\circ \mathrm{r}1\mathrm{r},\mathrm{g}\mathrm{o}\mathrm{I}11(^{\backslash }1\}’$

逆元計算

3. Reduction (種数 2 と違って、 2 回必要)

.

因了の分類
による場合分け・共通試着による場合分け
種数 3 では場合分けが約 70 通り必要
加算
1(genez ic case),, Matsuo, C.
Kui .
Pelrl Wollinger-Guajardo Paax (2003),
ii $(2004j$ ,Gonda. Matsuo, Aoki,$o\mathrm{k}^{-}\mathrm{i}$$\alpha\triangleleft \mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$1$・多項式の Nesvton 反復 (倍算)$\Rightarrow 1601\iota i\mathrm{t}$種数 3 の超楕円曲線上の Harlcy algorithm 及びその改良) )$\tau \mathrm{r}$・多項式の中国人剰余定理 (加算)Theriault \iota こよる Gaud}.\gamma 攻撃の改良を考慮しても楕円曲線暗号と同等の安全性上で多倍長演算を必要としないので, 高速な婁装が期待される。
定義体心.,. $‘.\geq 56$ }, .

$C‘$ )$\mathrm{T}\mathrm{s}.\iota’ \mathrm{j}\mathrm{i}_{1}\langle 21\mathrm{I}\mathrm{t}1^{t}\underline{)}\rangle$$\mathrm{C}^{\mathrm{t}r}.\mathrm{T}_{8\mathrm{U}}\mathrm{j}$$\mathrm{r}\mathrm{l}\iota\backslash \mathrm{g}PI$$\epsilon \mathrm{l}\mathrm{e}\mathrm{g}U|=\deg U_{2}=31\mathrm{C}\mathrm{S}(\rangle U\rceil .

Harlcv algorithrn
2. それ以外の場合$\neq 0$\# 2)$$=\pm$: 確率 $O(1/q)$ なので無視できる$\Rightarrow \mathrm{C}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{o}\mathrm{l}\cdot‘.\iota \mathrm{l}\mathrm{g}.\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{t}_{1\mathrm{l}}\mathrm{n}$

2 倍算

1.

and les [l, ,algolithm$\mathrm{d}e\mathrm{g}I^{\gamma_{1}}=3$$\Rightarrow \mathrm{H}4\mathrm{r}\iota_{\mathrm{e}\}^{r}}$$\langle$$1_{\}}^{j}$)$\neq 0$($\mathrm{m}\mathrm{o}6\mathrm{t}$frequent case)

2. それ以外の場合
algol ir.ltlYl: 確率 $O(3/q)$ なので無視できる$\overline{\sim}\mathrm{C}n\tau 1\mathrm{t}\mathrm{o}1^{\cdot}$$\cdot$17$\mathrm{J}\mathrm{b}^{\mathrm{t}}$

改良の方針

1.

$\mathrm{T}_{\mathrm{o}\circ \mathrm{l}}\mathrm{n}$$\mathrm{V}i1^{\cdot}\mathrm{t}\backslash t\mathrm{a}1$

I’ol‘\acute no 而 ml

... 十
... 十
... 十

乗算の利用

2. Virtual polynon]i 田 multil)lication の利用
$b$

$a,$

$A$

$\int\sqrt\int$$I$: 定義体上の元: $a+b,$: },a2 の計算時間: $1/a$ の計算時間$-a_{:}a-b,\underline{.}\mathrm{z}_{a,a}./2$

tioll の利用$\mathrm{r}11\mathrm{m}’[\mathrm{t}\mathrm{i}\iota^{\mathrm{z}1\mathrm{i}\mathrm{t}\mathrm{d}}’\cdot$の計算時間$\mathrm{a}f$を多項式乗算$s_{1}$

ご$+\cdots$$s_{0}z_{3}+\cdots$$(\theta 1X+\epsilon 0)\{,$” $4^{A}\mathrm{Y}+\underline{r}$$\delta$.

(sl+So\sim (z4+z の一を利用して 41),f から $3M$ に削減

Toon 漂算

種数 3 の丁子群演算の高速化$\lambda\hslash$$\circ^{\ulcorner}\Lambda \mathrm{f}arrow \mathrm{C}^{\backslash }1\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{c}\mathrm{a}1$

乗算:6M: $R=r2X’+r\uparrow X+r0\cdot S=s_{1}X+\hslash_{\mathit{0}}$

出力:
1

乗算

$T=t_{3arrow}Y^{3}+t\underline{\cdot\prime}X^{2}+t_{1}X+\dagger,\mathit{0}=RS$$u_{1}’=\langle r_{2}+r_{1}+r_{0})(s_{!}+s_{0})$$2\prime l\mathit{1}’q=(_{T\underline{\rangle}}-r_{\rceil}+t\dot{\mathrm{n}})\mathrm{t}-s_{1}+s_{()})$$3t_{0}=r_{0}s_{0}$4$t_{3}=r_{2}s_{1}$$.r.\ell_{1}=\{_{\sim}-9t_{1}+w_{1}-u\mathit{1}q\}/2$

6$t\mathrm{g}=\langle-^{\mathrm{q}}\wedge t_{0}+w’+w_{2})/2$

19) と見倣し,Karatsr\iota ba 乗算$s_{0}z_{3}$Tbom 乗算の利用

.

.

,

$\epsilon_{\mathrm{i}^{\sim}\prime\rfloor}$

Toom 乗算 : 高次多項式の効率的な乗算法
低次多項式においても特定の次数ならば効率的に計算角能$:4Marrow \mathrm{I}\backslash \mathrm{a}’$ $\mathrm{r}\mathrm{a}\mathrm{t}^{\mathrm{q}}..,\mathrm{u}\mathrm{b}_{4}^{r}$.

$s_{1}z_{\ddot{\alpha}}+s_{0}z_{4}+\cdots$$\underline{.1}0$$s_{1}z_{\mathrm{I}},-s_{0\sim 3}\wedge$

179
Weil

8

実装納果

定義体 : 素体$\mathrm{F}_{p},p=2^{\delta 1}-1$,
Alpha
Compiler . Compaq $C++$ xvith inkne asymbki
を利瑠.algorithm および整数倍旧 :win(lo}\ rrlcthod (window!80 倍算:乱数 signed(’PU

Gehard$\mathrm{d}\mathrm{e}\mathrm{s}\mathrm{c}.\mathrm{e},\mathrm{n}\mathrm{t}$攻撃と安全性解析
to disguis$\mathrm{F}1^{\cdot}\mathrm{C}\}’\backslash \mathrm{t}\mathrm{H}\circ w$$e_{-}11\mathrm{i}\mathrm{p}t\mathrm{i}\mathrm{t}^{\backslash }-$”ECC1998$\mathrm{E}\backslash \prime 68\mathrm{C}\sim \mathrm{B}1.25c_{\mathrm{r}}\mathrm{H}/$$\mathrm{N}\mathrm{T}\mathrm{L}/\mathrm{G}\mathrm{M}\mathrm{P}$$\mathrm{c}|\downarrow \mathrm{f}\mathrm{l}\mathrm{J}\mathrm{l}\mathrm{t}\mathrm{o}\mathrm{l}$$K/k_{:}[K : L.]=\tau\iota$

-Y/K:

.

$\cdot$$1601_{\mathrm{J}}\mathrm{i}\mathrm{t}$$n1\mathrm{i}\mathrm{c}1\mathrm{i}_{1\mathrm{l}}\mathrm{g}$.

$\mathrm{c}^{1}.\mathrm{g}.K=1\mathrm{B}^{\backslash },,,1/\mathrm{A}$.

$=\mathrm{F}‘$’$\mathrm{A}\mathrm{V}^{\cdot}$$\exists \mathrm{t}\Psi_{hik}.$

$/k$

:n-D

.

$\mathrm{A}\mathrm{t}_{\backslash }^{-}$$\mathrm{s}.\mathrm{t}$.

$W_{I_{\acute{\mathrm{t}}}/\succ}.(k)=X(I\mathrm{f})$$\ovalbox{\tt\small REJECT} 5)$$\exists\omega$:$\forall Y/h’:.r\{\mathrm{V}\forall c$.

$/\downarrow \mathrm{v}_{r}$$\mathfrak{l}V/Karrow"’$$\mathrm{F}\mathrm{r}($$\mathrm{J}\mathrm{l}\mathrm{l}()\mathrm{r}\mathrm{l}\supset t\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{l}\mathrm{I}\mathrm{J}$$\forall Y/K$.

:

morpllislll: $Y/Karrow\lambda’/K$ :$\acute{\nearrow}\overline{\mathrm{a}}:$$\exists!\iota$:$\mathrm{I}\prime V;,\cdot/\mathrm{A}./Karrow X/K$

$Y/Karrow W_{I\backslash ^{J}/k}./K$-Y/K

m rphism:$\cdot$.

$X/k$ $\Rightarrow W\kappa/\mathrm{A}(X)=X\mathrm{x}$$\mathrm{i}\mathrm{n}\mathrm{e}(\mathrm{l}\mathrm{u}\mathrm{c}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}/k.$) の楕成法Covering attack(Diem. Sholten 2003)$(\mathrm{e}!.\mathrm{g}.)$

.

$K/k$

$\mathrm{P}^{1\mathrm{i}\mathrm{n}1\mathrm{e}}$の Affinc coordinates ( $X_{1,\ldots:}X_{1},1$ から G\kappa 不変な関数:$\prod$$W_{I\backslash /k}\{\mathrm{A}^{n})\mathrm{x}K\simeq$A$\mathrm{z}\mathrm{z}$$K/k$. Calois, $G(K/k)=<\sigma>,$ orcl(\sigma )=l$\mathrm{A}^{\prime 1}$$c=\omega \mathrm{o}l$$\dim A=[Kk]-\dim X$.21$W_{\backslash /\mathrm{A}},.\{\lambda’$.

:] . が注目した構造

A$\mathrm{s}^{\neg}.\mathrm{t}$$\mathrm{o}$covering$c:C/Karrow H/K$$(\sigma(X_{1}), \ldots, \sigma\{X_{t\backslash }\})$$c/K\underline{c.}H/K$

一般的な多様体 : 定義方程式から

Generic points of$(P,\sigma P, ..

$W_{J_{1}/\mathrm{A}}\langle X$\sigma^{l-1}P)$

.

):
$P$

. a

$f\mathrm{i}./k$. point of$\mathrm{g}(\mathrm{Z}\mathrm{l}\{\mathrm{i}\mathrm{r}\mathrm{i}\mathrm{c}$.

$.\backslash ’\downarrow\wedge’\mathrm{Y}^{\cdot}\circ c/$の基底変換で求める。

.

$C/k$

$c/^{0_{(C}}./K)\underline{\mathrm{c}^{l}}Cl^{0}(H/K\rangle$.

$X\mathrm{x}K$$\wedge:/)\mathrm{o}r/$$\backslash ^{r}\downarrow$

A はトレースゼロの部分多様体として定義される。

$Cl^{0}(C/k\}$

attack が成り . つ条作 :$’\acute{j}.$$\mathrm{C}^{\mathrm{t}_{\{1}}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}$$A= \{(P’.\sigma P’, -\sigma^{\prime-1}P’)|\sum\sigma^{i}P’=0$

例-. $K$ , 辷有限体、 $[K : k]=l$ :prime, $X=E-$. 楕円曲線

1$\mathrm{E}\mathrm{x}\mathrm{p}1\mathrm{i}_{1}\mathrm{i}\mathrm{t}C/K$

2. pullback$c^{*}$

Wcil rvstriction (GHS)

cunozrn ( IS)$\mathrm{G}\mathrm{I}$$A\langle k)\supset\{P\in E(K)|Trr\acute{\iota}/\mathrm{t}(P) =0\}$3.

?? (評価)4. $g(C,)$ は大きすぎない.4 上の演算は、 $X$ の演算から得られる。
のとき、 $E$ の情報のみ与えて、実

特に $X=E$ :elliptic
際に を使って暗号を定義する。 (disguise)(tl \kappa pdoor$c\mathrm{u}\mathrm{r}1’\mathrm{e}$?(条件). 嫁 rivia}$1i\mathrm{L}^{\backslash }1^{\cdot}No\prime’$$\cdot$$A$$\rangle$

この仕組みと構成は、 結局攻撃法として生かされている。
$\underline{\prime \mathrm{J}}4$$.-\cdot\prime 3$

180
Tim tableの hxnctorial property よりこれを 」
YVeil
nlOelel として使ってよい。実際に、適当な ])intersec$\mathfrak{B}1:$$\iota\cdot \mathrm{c}.\backslash \mathrm{s}.\mathrm{t}\mathrm{l}\cdot \mathrm{i}\mathrm{c}\cdot \mathrm{t}\mathrm{i}\mathrm{o}\mathrm{r}\mathrm{l}$$\mathrm{e}$$\mathrm{c}\mathrm{r}\mathrm{a}1$$\mathrm{g}.\mathrm{t}^{\mathrm{J}}\mathrm{r}$$1\iota \mathrm{y}$t.iOll (GHS$\mathrm{c}\mathrm{u}\mathrm{t}\grave{|}$$\mathrm{e}\mathrm{r}\mathrm{p}\mathrm{l}\mathrm{a}\mathfrak{n}\mathrm{e}$によって曲線を得る。

標数 2 の合成数次数の拡大下上の楕円曲線へ適用 (GHS2000)
擦数 3 の場合の楕円曲線への拡張 有田 2000)
標数 2 の超楕円曲線へ拡張 (Galbraith, 2000)
実験的に GIIS の得られた関数体の種数を評価
さらに GHS の攻撃実例, Stein))
奇標数の )$\langle$

条件 2 : 関数体のを利用する。

$\mathrm{c}\mathrm{o}\iota \mathrm{l}\mathrm{o}\mathrm{r}\mathrm{n}\mathrm{l}$$\{\mathrm{b}\cdot 1\epsilon \mathrm{n}\mathrm{e}\mathrm{z}\iota^{1}\mathrm{s},\mathrm{Q}\iota\iota)$

条件 3 : 要検討 :(素体や、 素数次拡大体なら、 安全)$(\mathrm{J}\mathrm{a}\mathrm{c}o\mathrm{t})\mathrm{s}.\mathrm{o}\mathrm{n}_{}\mathrm{h}f\mathrm{e}\tau 1\prime\prime\Leftrightarrow.\cdot.$$\mathrm{h}3^{\cdot}1$

条件 4 : 具体的に評価が必要$\mathrm{e}\mathrm{r}\mathrm{e}11\mathrm{i}\mathrm{I}$$1\mathrm{i}\mathrm{c}-(\mathrm{D}\mathrm{i}\mathrm{C}^{\backslash }\mathrm{I}1‘\rangle$

特殊な Kuznmar extension
特殊な-Schreier extension (Theriault)
curves へ拡張 {l$rss)
一般的なcyclic Galois 拡大と superelliptic curves(飯島, 志村, , 辻井)
偶数次、 4 次拡大体への攻撃 (有田、 長尾有田 b 松賂志村)$(\mathrm{T}]_{1\mathrm{e}1}\cdot \mathrm{i}\mathrm{a}\mathrm{u}1\mathrm{t},)$$\mathrm{A}_{1}\cdot \mathrm{t}\mathrm{i}\mathrm{n}$$g(G)\geq ng(H)$$\mathrm{A}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{n}- \mathrm{S}\mathrm{c}\mathrm{h}\mathrm{r}\epsilon.\mathrm{i}\mathrm{c}.\mathrm{r}$楕円・超楕円暗号に対する攻撃法’ Squared-roota$\mathrm{c}$(BSGS Pollard’s$1\mathrm{a}111\mathrm{b}\mathrm{d}\mathrm{a}_{\tau}1^{\cdot}\mathrm{h}\mathrm{o}ae$-\rightarrow 般有限アーベル群 $G$ に適用可能

..
.

)

$O(\sqrt{\#\mathrm{G}}$$c_{P}=O(g(K(C)\mathrm{I}^{-})q^{\mathrm{A}^{f_{1\succ)}}}.\langle\log q’‘)^{2})\mathrm{C}_{1}n$ADH attack : 種数の準指数時間攻撃. variaza : 指数時閥ではあるが、 高速$\mathrm{G}_{\dot{\epsilon}111}^{\mathrm{I}}\mathrm{d}_{1}\gamma.\mathrm{s}$$c_{G}.\cdot=o(g\{F\}^{\hslash}q^{\vee}’(\log q).)+g(F\}^{2}(g(F)!)q(\log q)^{2})$’I’heriault ’s$\mathrm{S}^{\mathrm{t}}(1^{11\mathrm{d}1l}...\iota.\mathrm{o}\mathrm{o}\mathrm{t}$$\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{v}(^{1}\mathrm{X}11\mathrm{P}11\mathrm{t}$attack より早くなる種数の範囲:$5\leq g\leq 9$.16$\underline{.\rangle}6$

GHS Weil attack$K=\mathrm{F}_{q^{i\iota}}$,んsuch case.

$Jn$$=\mathrm{F}_{q:}‘ \mathit{4}=2^{l}$$\Gamma^{\mathit{4}}=(F’)^{a}$$E/K$ ::

$fi\tau c^{J}d$$Y^{f}.+X1’=\lambda^{-3}+\alpha X+/\mathit{3}$$g(F1=2_{\backslash }^{m-\prime}$$o\uparrow \mathrm{J}\rho\gamma$$\sigma_{|,|}^{\mathrm{I}}|\backslash _{\backslash }$$F$’field ofor

hyperelliptit$\sigma$$2^{\prime\prime-)}’-1$

the exaff constant fieid A$\mathrm{F}_{q^{n}}(Ej$$Cl^{0}.* \cdot\int^{F’)}\backslash _{\backslash }(.\backslash$$\backslash$$\backslash \backslash _{\backslash }$$\mathrm{A}’.\downarrow\backslash .\cdot,.\backslash FF^{\neg\prime}\overline{\backslash \mathrm{o}\mathrm{C}}\backslash _{\backslash }^{c_{\dot{\mathrm{F}}_{q^{\hslash}}\{E)}^{\mathrm{Y}}}$,$cl^{()}(F)\overline{4\backslash ’\circ}c^{Cl^{0}(\mathrm{F}_{q^{n}}(F_{\lrcorner}\rangle)},\cdot$$\mathrm{h}\mathrm{F}_{q’’}|_{\backslash }^{\backslash }\langle x)$

攻撃が成り立つためには、$\mathrm{F}_{\triangleleft}(x)\mathrm{F}_{\prime^{\eta}},\backslash ‘|\sigma_{K/\mathrm{A}}\backslash _{\mathrm{F}_{q}}$$N=N_{F’/F_{\dot{\prime}}^{1}}.C=C,on_{k^{l^{(\prime}}}\cdot/’\backslash (h)$$N_{F’j\Gamma}\mathrm{c}CJtrn_{F^{:}/R\{r_{\acute{\prime}})}\cdot Cl^{0}(K\downarrow.E)).arrow Cl^{\theta}(F’)arrow ConF’\prime J\mathrm{f}(L1r\mathrm{b},’/tCl^{0}(F)$.

$G(K/k)\ni\sigma_{h/k}$$F’:= \prod\sigma^{t}$($\sim$$\sigma\in G(K(x)/k(x))$

conjugate closure of$\mathrm{F}_{q^{n}}(E\rangle)$$\mathrm{F}_{\Gamma}‘\langle E$)

は、 離散対数を定義する巡回群を保存する必要がある。
つまり、 自明な$\mathrm{K}C.1^{\cdot}71^{s}‘ 1$を持つべき。

Artin-Schreier 拡大
1.

GHS$\tau\iota:od\prime l$$\mathrm{T}^{\mathrm{i}}\{$

定理 1, 条件

L. $???=n$ ,$m:=[F’ : K\langle x)]$$\mathrm{k}.\mathrm{e}1^{\cdot}Con_{F’j\mathit{4}\mathrm{i}^{-}\{E)}=${dts of }$($$\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{s}2$$\prime pr_{\Gamma\acute{\mathrm{t}}/\mathrm{p}_{2}}(\alpha)=0$の$-\cdot-$

っでもを満たせば、$\Rightarrow\exists\sigma\in G(F’/k.)$’, or’t $\sigma=n$$2^{-}$$2\theta$

powers}181
Menezes, Qu は、 $F$ の種数を実験的に計算、、攻撃は無理$q=\mathit{2},n:\mathrm{p}\mathrm{l}\cdot \mathrm{i}\mathrm{n}\mathrm{l}\mathrm{e}7t\in\{160_{:} 600\}$

Diem 奇標数の超楕円曲線 (Knmml 拡大)
Theorem, $H’$ : a hvperelliptic K-curve$F’$ : theofof $F’/L(x)$If $F’/K$ . regular, $\exists!F/k(x)$ . regular$K/k\cdot[K : k.]=\mathrm{o}\mathrm{c}1\mathrm{d}$$\mathit{7}\lambda=7,31_{:}12_{\mathfrak{l}}’,g[F$) $=7l$ となる楕円曲線がある。

$I\zeta\langle H’)/K(x)$$\mathrm{G}_{i}d\mathrm{o}\mathrm{i}\mathrm{s}\{1_{0911\mathrm{I}}.\epsilon$$5\mathrm{u}\mathrm{b}\mathrm{e}\mathrm{x}\mathrm{t}$しかし、 ff 丁$\mathrm{R}\mathrm{F}\mathrm{C}$$\mathrm{F}$. 24121998 では、, を推奨$\mathrm{F}_{2}’.- \mathrm{F}_{\underline{1}}$}$KF=F’$ .

$\mu\uparrow$$\acute{n},.\mathrm{t}\epsilon \mathrm{r}$.

$\hat{\sigma}_{\overline{K/}k1^{\backslash }}I^{1}\grave{K}1H’)F’$

Jacobson, Menezes, Sraein:$2^{\mathrm{J}5\theta}$

descent個の同型類のなかで .33 個へ攻撃 11J 能。
$\mathrm{F}_{2-}\uparrow\epsilon \mathrm{r}_{1}^{i}\ \mathrm{F}_{\hslash},\text{へ}$$-\mathrm{Q}$$\backslash \backslash _{\backslash _{\backslash }}\backslash _{\mathrm{A}’(x)}\backslash |\backslash \backslash$C4a 市\sim 箱 th により、 同じ isogeny$\mathrm{c}.\mathit{1}\mathrm{a}.\mathrm{s}\backslash \cdot$にある曲線へ攻撃範囲を

A

広げる。

$\{x)K\backslash |\backslash _{\backslash \mathrm{A}}.\sigma_{\mathit{4}\zeta\prime}\mathrm{g}$If$F’/K.\mathrm{n}\mathrm{t}$$\exists|F/\eta$($x\grave{)}$)$\mathrm{n}\mathrm{r}‘\backslash \mathrm{g}\prime 1\mathrm{L}.\iota$}$\exists^{\underline{\mathrm{t}}}\eta/k,$.

$[\eta\cdot k.]=2\mathrm{H}\mathrm{t}F’/7|\mathrm{A}_{\sim}’$. regular sub ext of)$F^{:}i\mathit{1}|(x)\mathrm{s}\mathrm{c}\Gamma^{t}/7$$\mathrm{l}\rho \mathrm{g}_{11}1\mathrm{a}$$\mathrm{r}\iota^{\backslash }\mathrm{g}\iota \mathrm{d}r\mathrm{v}$

)

,

.

$\eta \mathrm{A}^{r}F=KF=F^{J}$.

$0$\cdot$$.l^{(}\mathrm{J}$$N\mathrm{o}C$$\eta F’$

$z$

i.e .

$|\overline{\sigma_{J}\nwarrow}/k\backslash \backslash _{\wedge}$$\mathrm{A}_{\mathrm{A}(H’)/\{f}^{\Gamma}.’$By Hasse-Weil$\overline{\sigma_{\mathrm{A}/k1\gg}}F’F\eta \mathrm{A}’(H’)F\grave{K}(B’)\backslash \grave{r}(K’(x)\nearrow’\backslash \swarrow[searrow]_{\backslash }’,’\backslash$:factors thrrughnont.rivial.

$\mathrm{C}1^{0}(K(H^{)}))arrow \mathrm{C}1^{0}(h\mathit{1})$$1\mathrm{c}G1^{\cdot}\langle N\circ C\rangle\mathrm{F}\mathrm{h}_{\text{、}}$$\uparrow\supset \mathrm{o}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}$.

lccl (NoC} : 廿 ivi$\cdot$$\approx$

中間体が存在しない$\backslash \backslash \backslash \backslash ,\backslash _{\backslash }/|^{\backslash _{\backslash }}\backslash _{\backslash }^{K(x)\eta\langle x\mathrm{I}\eta_{\int}K}\backslash /|\succ^{\prime’\backslash \mathrm{g}/}\backslash \bigwedge_{\backslash ^{\mathrm{t}}}|l\backslash \backslash \backslash$$F’$$|\backslash _{\backslash }\backslash$$h’$$k\langle x)$$\eta$$\Gamma_{0}^{r’}$.

$K(FI’)$$\backslash \backslash _{\backslash ^{\sigma_{1\mathrm{c}/l1}}\backslash }/.2$$|\backslash |$$\backslash \sim\backslash$$t$以上の結論は、$F3MK‘(x.)\backslash \backslash \backslash _{\backslash \backslash }|^{\backslash }\backslash _{\backslash }\backslash _{\backslash }\mathrm{g}(\mathit{9}i)K\backslash$Artin-Schrcier 拡大、 (GHS を含む)
巡回 Giois 拡大体
へ拡張できる。

$\backslash _{\backslash \backslash _{\backslash }|^{\backslash }\backslash |}\backslash f_{i}(x)t^{I}\backslash \backslash \backslash$$\backslash _{\backslash \backslash }|$攻撃の条件 (Artin-Schreier, 巡回拡大でも成り立つ)$\oint_{i}$Proposition:$k\subset\exists\mu\subsetarrow K\mathrm{s}.\mathrm{t}$$\Rightarrow\exists M/\mu$.

$K(fI^{J})//\iota(x,)$: regfflar:Galois$\backslash KM=K\langle$ $H’$

.

31

}

$.\backslash ’.t$.
.

$3^{1}.$,

182
Diem : 種数 $g(F)$ の上 F\rightarrow 界を計算{$.\mathrm{h}_{\mathrm{d}I}.K/k=\mathrm{o}\mathrm{d}\mathrm{c}\mathrm{L}$[If :$\mathrm{A}.\mathrm{J}=7L=\prod p^{n_{1^{J}}}$. curve, $g(H)=g$

Artin-Schreier 拡大に対する解析 (Hess)
:odd

$H/K$

$g(F)\leq 2^{n-1}$

.

$k$

{( 十

$1\rangle n-1$$g$

$K(H)\cdot=E(\wp^{-1}\langle f))$) $+1$$\subset E/\lrcorner\subsetarrow K\Rightarrow \mathrm{k}\mathrm{c}\mathrm{i}rN\mathrm{o}C=${clt8 of order 2power8} and$\forall f\in E$$\geq 2^{\dot{\phi}2(n)}-2(n-4’)+1$

whexe$\forall?\tau\in \mathrm{N}$.

$\phi_{2}\langle n,$)$K=\mathrm{F}_{l},\Uparrow,k=\mathrm{F}_{q},$$q=p^{-}$$7l$$:=f\mathrm{F}\underline{\cdot,}[\xi_{1},]$,. Artin-Schreiet extension$\Delta_{f}.=\{d^{p}-d+\sum_{i=0}^{\prime)-1}\lambda_{i}\sigma^{j}\{f)|d\in E^{l}, \lambda, \in \mathrm{F}_{J},\}$となる最小次数の: prime定理 2. .
$\deg(m_{f})\geq 2$

楕円曲線に対する攻撃

E( . 戸$r$

素数拡大次数の場合.

$\cup K\subset\wp(E)$$\Delta,$$\sum\lambda_{i}\sigma^{j}\dot{\{}f$

: 多項式
$p$

$\epsilon$$F’=E(\wp^{-}{}^{\mathrm{t}}(\Delta_{f}))$,F2]$=d^{p}-d_{\tau}m\exists d\in E$.

$?nf \langle t)-\cdot=\sum’\backslash jt^{1}m\in \mathrm{F}_{p}[t]s.t$$g(F) \geq 2^{\mathrm{I}_{g+}^{\Sigma_{\underline{p,\prime}1h^{\neq}}}\frac{\mathrm{u}\prime J^{1}\prime}{\sim}l-2}(_{p.n_{P}\neq\{\}}\sum.;" \mathrm{z}_{p}-1)+1$$g(F\rangle$. $y^{p}-y=f(x)$ .

$E.=K(x)’.\wp(x)=x^{\mathcal{P}}-\tau$$H:\mathrm{h}\mathrm{y}:)\iota\backslash \mathrm{r}\mathrm{e}!1\mathrm{l}\mathrm{i}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{c}$,)$\{1)\mathrm{n}\mathrm{i}\mathrm{q}\iota\iota \mathrm{c}^{\mathrm{J}})_{\mathrm{t})}$$[F’ E]=l^{J^{4\mathrm{g}\{m\}}}‘/$,) の種数は 2 以紅$(f_{:}\sigma(f))$$g(fI)p^{\mathrm{d}\mathrm{g}(’ n_{f}\}}‘ \underline{)}+1\leq‘ d(\Gamma’\}\leq ng\{H)\frac{p^{\mathrm{d}r\mathrm{g}(\prime n_{f)}}-1}{p-1}$; 安全$n\geq 11\Rightarrow\# c_{J}l^{\mathit{0}}(F)\sim q^{g(\prime\dot{\prime})}=2^{\acute{0}01\dot{1}0}$$n=5.ng\backslash \{F$

. F:種数 3$p$ ニとは限らない。 グレーゾン$F:]\mathrm{l}\mathrm{y}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{c}$$rn=3$

さらに、) $=5$ or 7,,$\mathit{0}\mathrm{J}$llyperellitpic

2,$F’/E$: 安全$f=\wedge:/x+a+r\beta x_{\backslash }\gamma_{:^{\mathrm{t}t_{\backslash }}\acute{i}}\mathit{3}\in K,\gamma[t\neq 0$

regular,$P^{\neg\prime}.=E(\wp^{-1}(\triangle j))$$g(F”)=2^{d_{P}}\epsilon \mathrm{t}^{\mathrm{y}7\mathrm{t}}J^{1}’-2^{\deg(m_{f}\}\prime 1q(m_{\backslash })}-2^{e1\epsilon \mathrm{g}\{m_{J}\mathfrak{i}-\mathrm{d}ae(m_{\beta})}\mathrm{P}_{\Leftrightarrow}+]$$l4$$.\cdot’..j$

SuPerellitPic curves に対する解析 (飯島, 志村, , 辻井).
$c,,/K$ :.
$\mathrm{c}$$Y’$$=j(X):=asX^{\delta}+\cdots+\prime r_{1}..\mathrm{Y}+\prime \mathrm{J}_{0}$$r|$ $(t- 1, \mathrm{g}.\mathrm{c}.\sigma 1(f\{X)_{-}f^{J}(X))=1_{:}\mathrm{g}\mathrm{r}.\cdot\sigma 1\{.r.\delta\rangle$

or

$=1$

$r$

$\mathrm{g}\mathrm{c}\mathrm{d}(n_{\backslash }r)=1_{\}r,n$$g(K(C)\rangle\underline{\backslash }4’,$

primes$\mathrm{c}\iota\iota \mathrm{r}\mathrm{v}\mathrm{c}^{1}$

or 1 if.

$\mathrm{g}.\mathrm{c}\cdot \mathrm{d}\langle r,\delta)=ro\mathrm{z}’ 1$$\subseteq\beta\muarrow\subset K\mathrm{s}.\mathrm{t}$.

$K(C)/\prime \mathit{1}(\mathrm{i}S)$\’a :$g(\Gamma^{d})\geq$

「
「
$.$

.

$\mathrm{g}’.(1(\tau\oint..r\rangle$$=1_{:}r_{1}n$,$g(C\rangle\leq 4,$

11$0^{\cdot}4^{(}\mathrm{J}$for $n\geq 17$ .

: prime nurnbers$C:\mathrm{s}.\prime 1\mathrm{P}’\tau \mathrm{c}^{\backslash }11\mathrm{i}1)\mathrm{t}\mathrm{i}\mathrm{c}^{\backslash }(.\cdot l\mathrm{J}\mathrm{r}.\mathrm{v}\iota^{\backslash }.,$

$g(F) \geq(\prod_{i=1}^{\overline{m}}\overline{r}_{\lambda})\ovalbox{\tt\small REJECT}\underline{\frac{1}{9}}\{_{l’,p}\sum_{n\neq 11}.p^{\prime t_{p}}(1-\underline{1})\uparrow.\}-1\ovalbox{\tt\small REJECT}+1$

7$\mathrm{g}_{\overline{(}}6^{\cdot}$$\mathrm{J},\mathrm{J}.!$$n:]\lrcorner \mathrm{r}i\mathrm{n})\mathrm{c}_{\backslash }^{\backslash }g(\Gamma’)\geq.21517$:Galois, $n:= \prod_{r}$13.
91$g(\Gamma^{\sim})\geq 5_{\backslash 1}^{r}\mathrm{f}\check{\circ}1^{\cdot}7’$$(7l\geq\neg l)$$\mathrm{n}o11-t_{1\backslash }.\mathrm{p}(\mathrm{i}1\epsilon.\mathrm{J}\mathrm{h}.\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{c}^{\backslash }$$q^{g(c_{\dot{\{}n}^{\sim}}\geq 2^{\iota 60}$

$1\mathrm{f}.r$$1\leq\exists\overline{n7}\leq Y\mathfrak{l}\cdot\cdot\overline{r}:13.’:\overline{r}_{i}>1$

is. aPrillle$\mathrm{n}\mathfrak{U}111\mathrm{b}\mathrm{C}^{1}1^{\cdot}$

.

.

,

9
.

今後の課題

$g(F) \geq r\lceil_{-}^{\Sigma}\mu.\ovalbox{\tt\small REJECT}’\frac{0^{\rho^{n_{p}}}}{a}\rceil|;\frac{1}{\overline{2}}\{_{\rho,\prime}\sum_{t_{\nu}\neq 0}p^{n_{p}}(1-\frac{1}{r})\}-1]+1$$\mathrm{g}\mathrm{c}.\sigma 1\{?\iota,r.\}=1$とする。

$\phi_{r}(.n):=[\mathrm{F},.[\zeta_{n}‘]$:・安全性の検討

・暗号化・復号化用の高速算法の開発]$\mathrm{F}_{r}$・安全な曲線を効率的な構成.

$g(F) \geq r^{\phi_{r}\{\prime}‘’[\frac{1}{2}\{7?(1-\frac{1}{\Gamma})\}-1]+1$35$.\mathrm{J}6$17$|\mathrm{i}200884\underline{\mathrm{C}99}|$$\Rightarrow q^{g(F^{\mathfrak{l}})}\geq 2^{^{7}360}\mathrm{e}.\backslash \cdot \mathrm{c}^{\backslash }\mathrm{c}\eta)\mathrm{b}n=13,\delta=4.\ulcorner 0.6$

witlJ

.

.

$g(F) \leq\tau’’\{\frac{n\cdot\langle\delta.+\alpha)}{\mathit{2}}(1-\frac{1}{},)\backslash -1\}+1$$1\mathrm{f}k$$\Rightarrow C\rho<Cc_{l}$$\log_{\sim}7q^{g(C)}’\}\leq \mathit{0}^{r}60$$n$$’.\mathrm{Y}:=0$$(n\geq 5)_{\mathrm{s}}$, non-hy pet elhptic,$Ct\gamma\prime 11JC\mathrm{l}\mathrm{c}\mathrm{l}\mathrm{l}\mathrm{i}\mathrm{l})\mathrm{t}\mathrm{i}\mathrm{e}$,.

$\geq \mathrm{t}r\mathrm{J}$