超特異同種写像ディフィー・ヘルマン

超特異同種写像ディフィー・ヘルマン鍵共有 (SIDH, Supersingular isogeny Diffie–Hellman key exchange)は、耐量子（英語: post-quantum cryptography）暗号アルゴリズムであり、安全でない通信路を用いて二者間で共通鍵を共有するために用いられるプロトコルである。ディフィー・ヘルマン鍵共有のアナロジーであるが、超特異同種写像グラフに基づいており、量子コンピュータを利用した攻撃に対して耐性があるように設計されている。SIDHは、耐量子鍵交換方式の中では最も短い公開鍵長を誇っており、鍵圧縮テクニックを用いると、128ビット量子安全を達成する公開鍵は2688ビットとなる。 また、NTRUやRing-LWEなどの他の耐量子鍵交換方式と異なる点として、フォアワードセキュリティという性質を持つこともあげられる。この性質は、長期間使用される秘密鍵がある時点で漏洩してしまったとしても、それ以前のセッションの機密性が脅かされることがない、という性質である。 これらの性質により、現在インターネット通信において広く用いられているディフィー・ヘルマン鍵共有(DHE) や楕円曲線ディフィー・ヘルマン鍵共有(ECDHE)を置き換える耐量子プロトコルの候補である。

概要

ある種の問題に対しては、量子コンピュータ上で動くアルゴリズムは、従来の古典コンピュータ上のアルゴリズムに比べて低い計算の複雑さを達成しうる。つまり、最も効率の良い古典アルゴリズムよりも早く問題を解くことができる場合がある。例えば、素因数分解問題を解く最も良い古典アルゴリズムである一般数体ふるい法は準指数時間であるのに対して、量子コンピュータ上で動作するショアのアルゴリズムは素因数分解を多項式時間で実行できる。これは、公開鍵暗号においては重要なことである。代表的な公開鍵暗号であるRSA暗号の安全性は素因数分解の困難性に依存している。また、ショアのアルゴリズムは、ディフィー・ヘルマン鍵交換、楕円曲線ディフィー・ヘルマン鍵交換、楕円曲線DSA、エルガマル暗号などの多くの暗号システムの安全性が依拠する離散対数問題も効率的に解くことができる。 2020年現在の量子コンピュータはまだ小規模であるが、現在進められている開発が進み大規模な量子コンピューターが実現されれば、TLS / SSLなどで利用されている現代の暗号プロトコルは破られてしまうため、量子コンピュータに対しても耐性のある暗号（耐量子暗号）の開発が促進されている。

SIDHは2011にDe Feo, Jao, Plutの三者によって開発された。 従来の楕円曲線暗号の演算を使っており、特許は申請されていない。SIDHはフォアワードセキュリティを持ち、長期間保存される秘密鍵の安全性に依存しない。フォアワードセキュリティは、暗号通信の長期間の安全性を向上させ、集団監視攻撃から通信を守り, ハートブリード攻撃のような脆弱性による影響を減少させる。

背景

ヴァイエルシュトラス方程式$y^{2}=x^{3}+ax+b$で表現される楕円曲線のj-不変量(j-invaliant) は、次式で与えられる。

$j(E)=1728{\frac {4a^{3}}{4a^{3}+27b^{2}}}$.

同型(isomorphic)の曲線は同じj-不変量を持つ。代数的に閉じている体においては、同じj-不変量を持つ二つの楕円曲線は同型である。

超特異同種ディフィー・ヘルマンプロトコル（SIDH）では、超特異楕円曲線（の同型類）と曲線間の同種写像を用いる。 2つの楕円曲線 $E$ と $E'$ の間の同種写像 $\phi :E\to E'$ は、群準同型性を持つ有理写像のことを言う。 曲線 $E$ の任意の巡回部分群 $G$ に対して、$G$ をカーネルとして持つ同種写像 $\phi$ と写像先の曲線 $E'$ は、（同型である曲線を同一とみなせば）一意に定まる。 $E$ とその巡回部分群$G$から、$\phi :E\to E'$ かつ $Ker(\phi )=G$ であるような $\phi ,E'$ を求める方法は、Véluによって与えらえている。

SIDHのセットアップでは、$p=w_{A}^{e_{A}}\cdot w_{B}^{e_{B}}\cdot f\mp 1$ の形をした素数 $p$ と、体 $\mathbb {F} _{p^{2}}$ の上で定義される超特異楕円曲線 $E$ を用意する。 ただし、$w_{A}$ と $w_{B}$ は異なる（小さな）素数であり、指数 $e_{A}$ と $e_{B}$ は大きな自然数であり、$f$ は小さな係数である。このような曲線 $E$ は、二つの大きな捩れ部分群(torsion subgroups) $E[w_{A}^{e_{A}}]$ と $E[w_{B}^{e_{B}}]$ を持つ。これらの部分群はそれぞれアリスとボブに割り当てられる。（添え字 A がアリスを表し、Bはボブを表す。 鍵共有プロトコルを実行するとき、まずアリスは自分の捩れ部分群 $E[w_{A}^{e_{A}}]$ の（秘密の）巡回部分群をランダムに選び、対応する（秘密の）同種写像とターゲット楕円曲線を計算する。そして、ターゲット楕円曲線と、同種写像によるボブの捩れ部分群 $E[w_{B}^{e_{B}}]$ の像(image)に関する情報をボブに送る。ボブも同様に、$E[w_{B}^{e_{B}}]$ の部分群を選んで同種写像とターゲット楕円曲線と、自分の同種写像によるアリスの捩れ部分群 $E[w_{B}^{e_{B}}]$ の像に関する情報をアリスに送る。 これによってアリスとボブは、 二人の秘密の巡回部分群によって決まるカーネルを持つような新しい（$E$ の）同種写像をそれぞれ計算できるようになる。二人が計算して得る同種写像のカーネルは一致するため、その新しい楕円曲線は同型であり、共通のj-不変量を持つので、その j-不変量を共通鍵とすればよい。

この方式の安全性は、小さい方の捩れ部分群に依存しているため、$w_{A}^{e_{A}}\approx w_{B}^{e_{B}}$ であるように選ぶ必要がある。 詳細については、De Feoによる文献に示されている。

安全性

SIDHの安全性は、点の数が等しい二つの超特異楕円曲線の間の同種写像を見つける問題と密接に関係してる。 考案者である De Feo、Jao、Plut の３人は、SIDHへの最良の攻撃はrelated claw finding problemを解くことであり、従って古典計算機での計算複雑さは O(p^1/4)、量子計算機では O(p^1/6) であるとしている。これは、768ビットの素数 p を用いるSIDHが 128ビット安全性を持つことを意味する。 2014年の Delfs and Galbraith による研究により、古典計算機での同種写像問題の計算量は O(p^1/4) であることが確認されている。 SIDHの安全性については、Biasse, Jao and Sankarによる研究や Galbraith, Petit, Shani and Ti による研究によって O(p^1/4) であることが確認されている（古典計算機の場合）。

超特異同種写像ディフィー・ヘルマン方式

SIDHのいくつかのステップは複雑な同種写像の計算を含んではいるが、プロトコルの全体の流れは自体は、ディフィー・ヘルマン鍵共有方式やその楕円曲線版を知っている人にとっては分かりやすい。

セットアップ

公開パラメータは以下を含む。 （ネットワーク上の誰でもが使えるようにしても良いし、鍵交換に先立ちアリスとボブの間で同意してもよい。）

1. $p=w_{A}^{e_{A}}\cdot w_{B}^{e_{B}}\cdot f\pm 1$ の形をした素数 $p$。
2. $\mathbb {F} _{p^{2}}$ 上の超特異楕円曲線 $E$。
3. 楕円曲線 $E$ の上にある４つの点 $P_{A},Q_{A},P_{B},Q_{B}$。
4. $P_{A}$ と $Q_{A}$ の位数 $(w_{A})^{e_{A}}$、$P_{B}$ と $Q_{B}$ の位数 $(w_{B})^{e_{B}}$。

鍵交換プロトコル

アリスとボブが鍵交換をするとき、共通の楕円曲線 E からの同種写像をそれぞれが作る。そのために、同種写像の核空間(kernel)を定義するランダムな点（$R_{A}$ または $R_{B}$）を生成する。$R_{A}$ は二点 $P_{A},Q_{A}$ のランダムな線形結合であり、$R_{B}$ は $P_{B},Q_{B}$ のランダムな線形結合である。異なる点のペアを使うことで、二人が選ぶ同種写像は必ず異なり、非可換である。

$R_{A}$（あるいは $R_{B}$）から、アリス（あるいはボブ）はVeluの公式Velu's formulasを用いて同種写像 $\phi _{A}$（あるいは $\phi _{B}$）を計算する。 さらに、ボブは二つの点 $\phi _{B}(P_{A})$ と $\phi _{B}(Q_{A})$ を、アリスは $\phi _{A}(P_{B})$ と $\phi _{A}(Q_{B})$ を得る。 二人は、計算した二つの点を通信路を介して交換する。

次に、アリスとボブは、それぞれ受け取った二点から新たな同種写像を生成する。そのため、受け取った二点を上で用いたのと同じ係数を使って線形結合して、点 $S_{BA}$ と $S_{AB}$ を得る。ここでまた Veluの公式を使って $S_{BA}$ と $S_{AB}$ に対応する同種写像および新しい楕円曲線を計算する。

鍵交換を完了するには、アリスとボブはそれぞれ得られた楕円曲線の係数から j-不変量を計算する。通信路上でエラーが起こらない限り、二人が計算した j-不変量は等しくなる。

具体的には、プロトコルは以下のように動作する：（以下ではアリスはA、ボブはBと表記する）

1A. Aは二つのランダム整数 $m_{A},n_{A}(<(w_{A})^{e_{A}})$ を選ぶ。

2A. Aは $R_{A}:=m_{A}\cdot (P_{A})+n_{A}\cdot (Q_{A})$ を計算する。

3A. Aは $R_{A}$ を用いて同種写像 $\phi _{A}:E\rightarrow E_{A}$ と、$E$ と同種な楕円曲線 $E_{A}$ を生成する。

4A. Aは $\phi _{A}$ を点 $P_{B}$ と $Q_{B}$ に適用して、 $E_{A}$ 上の二点 $\phi _{A}(P_{B})$ と $\phi _{A}(Q_{B})$ を計算する。

5A. AはBに $E_{A},\phi _{A}(P_{B}),\phi _{A}(Q_{B})$ を送る。

1B - 4B: Bは、1A～4Aを、添え字AとBとを入れ替えて実行する。

5B. BはAに $E_{B},\phi _{B}(P_{A}),\phi _{B}(Q_{A})$ を送る。

6A. Aは $m_{A},n_{A},\phi _{B}(P_{A}),\phi _{B}(Q_{A})$ から $E_{B}$ 上の点 $S_{BA}:=m_{A}(\phi _{B}(P_{A}))+n_{A}(\phi _{B}(Q_{A}))$ を計算する。

7A. Aは $S_{BA}$ を用いて $E_{B}$ と同種な楕円曲線 $E_{BA}$ を生成する。

8A. Aは曲線 $E_{BA}$ の j-不変量 $K_{A}:=j(E_{BA})$ を計算する。

6B - 8B: Bは、6A～8Aを、添え字AとBを入れ替えて実行し、$K_{B}:=j(E_{AB})$ を得る。

二つの曲線 $E_{AB}$ と $E_{BA}$ は同型であり、したがって必ず同じ j-不変量を持つため、$K:=K_{A}=K_{B}$ が成り立つ。$K$ を何らかの関数で変換したものを共有鍵として使用する。

サンプルパラメータ

以下に示すパラメータは、De Feoらによって例として与えられている:

法$p$ : $w_{A}=2,w_{B}=3,e_{A}=63,e_{B}=41,f=11$ とする。したがって，$p=(2^{63}3^{41}11)-1$。

最初の楕円曲線 $E_{0}$：$y^{2}=x^{3}+x$。

効率

鍵共有プロトコルにおいて、アリスとボブはそれぞれ、楕円曲線を定義するための(mod p²における)２つの係数と、曲線上の２つの点を相手に送信する。 各楕円曲線の係数は log₂p² ビットが必要で、各楕円曲線上の点は log₂p²+1 ビットで表現できるため、送信量は 8log₂p + 2 ビットとなる。 768ビットの p（128ビット安全）を用いた場合には、これは 6146ビットである。 しかし、鍵圧縮のテクニックを用いれば，半分以下の 2640ビット（330バイト）まで短くできることが、Costello, Jao, Longa, Naehrig, Renes and Urbanikの最新の研究によって示されている。 鍵圧縮を用いれば、SIDHが必要とする帯域は、従来の 3072-bit RSA署名やDiffie-Hellman鍵共有プロトコルと同程度である。このため、ビットコインやTorのようにデータ容量が限定される場合にも応用できる。

Torのデータセルは 512バイト以下でなければならないが、SIDHに必要な330バイトの情報を運ぶことができる。これに対し、NTRUEncryptは、128ビット安全を達成するためには 約600バイトの情報を交換する必要があり、セルのサイズを増やさない限り、Torには適用できない。

2014年に、ウォータールー大学の研究者がSIDHのソフトウェア実装を開発している。彼らの部分的に最適化したコードをx86-64プロセッサ上で 2.4 GHz で実行したところ、768ビットの法では、鍵交換の計算時間は 200 ミリ秒で終了した。これによって、SIDHが実用的であることが実証された。

2016年には、Microsoftの研究者がSIDHのソフトウェアを公開した。このソフトウェアは、入力によらず常に一定時間で動作し（したがってタイミングアタックに耐性がある）、これまでで最も効率の良い実装である。開発者たちは「公開鍵のサイズは564バイトであり、ほとんどの一般的な耐量子の鍵交換プロトコルよりもかなり小さい。我々のソフトウェアのサイズとスピードは、SIDHが、耐量子の鍵交換プロトコルの候補となる強い可能性を示している。我々の結果がより広い暗号解析の努力を促進させることを願っている。」と述べている。 Their software is posted on here.

2016年、Florida Atlantic Universityの研究者は、SIDHの効率的な ARM 実装を開発し、アフィン座標と射影座標の比較を与えた。 また2017年には、最初のSIDHのFPGA実装が開発されている。

類似した方式、署名への拡張

楕円曲線の同種写像に基づくディフィー・ヘルマン鍵共有方式は、2006年に Rostovtsev と Stolbunov によって初めて提案されている。彼らの方式は、上述のSIDHとは異なり通常の（超特異ではない）楕円曲線を用いており、準指数時間の量子攻撃が発見された。

2014年、Chinese State Key Lab for Integrated Service Networks と Xidian University の研究者は、SIDHの安全性を検証者指定型ディジタル署名方式へと拡張した。 2014年10月、University of Waterloo のJao and Soukharev は、楕円曲線の同種写像に基づく否認不可署名の構成方法を示している。