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

超特異同種写像ディフィー・ヘルマン鍵共有 (ちょうとくいどうしゅしゃぞうディフィー・ヘルマンかぎきょうゆう、、略称: SIDH)は、暗号アルゴリズムであり、安全でない通信路を用いて二者間で共通鍵を共有するために用いられるプロトコルである。ディフィー・ヘルマン鍵共有のアナロジーであるが、に基づいており、量子コンピュータを利用した攻撃に対して耐性があるように設計されている。SIDHは、耐量子鍵交換方式の中では最も短い公開鍵長を誇っており、鍵圧縮テクニックを用いると、128ビット量子安全を達成する公開鍵は2688ビットとなる。
また、NTRUやなどの他の耐量子鍵交換方式と異なる点として、フォアワードセキュリティという性質を持つこともあげられる。この性質は、長期間使用される秘密鍵がある時点で漏洩してしまったとしても、それ以前のセッションの機密性が脅かされることがない、という性質である。
これらの性質により、現在インターネット通信において広く用いられているディフィー・ヘルマン鍵共有（DHE）や楕円曲線ディフィー・ヘルマン鍵共有（ECDHE）を置き換える耐量子プロトコルの候補である。
概要.
ある種の問題に対しては、量子コンピュータ上で動くアルゴリズムは、従来の古典コンピュータ上のアルゴリズムに比べて低い計算の複雑さを達成しうる。つまり、最も効率の良い古典アルゴリズムよりも早く問題を解くことができる場合がある。例えば、素因数分解問題を解く最も良い古典アルゴリズムである一般数体ふるい法は準指数時間であるのに対して、量子コンピュータ上で動作するショアのアルゴリズムは素因数分解を多項式時間で実行できる。これは、公開鍵暗号においては重要なことである。代表的な公開鍵暗号であるRSA暗号の安全性は素因数分解の困難性に依存している。また、ショアのアルゴリズムは、ディフィー・ヘルマン鍵交換、楕円曲線ディフィー・ヘルマン鍵交換、楕円曲線DSA、エルガマル暗号などの多くの暗号システムの安全性が依拠する離散対数問題も効率的に解くことができる。
2020年現在の量子コンピュータはまだ小規模であるが、現在進められている開発が進み大規模な量子コンピューターが実現されれば、TLS / SSLなどで利用されている現代の暗号プロトコルは破られてしまうため、量子コンピュータに対しても耐性のある暗号（耐量子暗号）の開発が促進されている。
SIDHは2011にDe Feo, Jao, Plutの三者によって開発された。
従来の楕円曲線暗号の演算を使っており、特許は申請されていない。SIDHはフォアワードセキュリティを持ち、長期間保存される秘密鍵の安全性に依存しない。フォアワードセキュリティは、暗号通信の長期間の安全性を向上させ、から通信を守り, ハートブリード攻撃のような脆弱性による影響を減少させる。
背景.
ヴァイエルシュトラス方程式formula_1で表現される楕円曲線のj-不変量(j-invaliant) は、次式で与えられる。
同型(isomorphic)の曲線は同じj-不変量を持つ。代数的に閉じている体においては、同じj-不変量を持つ二つの楕円曲線は同型である。
超特異同種ディフィー・ヘルマンプロトコル（SIDH）では、超特異楕円曲線（の同型類）と曲線間の同種写像を用いる。
2つの楕円曲線 formula_3 と formula_4 の間の同種写像 formula_5 は、群準同型性を持つのことを言う。
曲線 formula_3 の任意の巡回部分群 formula_7 に対して、formula_7 をカーネルとして持つ同種写像 formula_9 と写像先の曲線 formula_4 は、（同型である曲線を同一とみなせば）一意に定まる。
formula_3 とその巡回部分群formula_7から、formula_13 かつ formula_14 であるような formula_15 を求める方法は、Véluによって与えらえている。
SIDHのセットアップでは、formula_16 の形をした素数 formula_17 と、体 formula_18 の上で定義される超特異楕円曲線 formula_3 を用意する。
ただし、formula_20 と formula_21 は異なる（小さな）素数であり、指数 formula_22 と formula_23 は大きな自然数であり、formula_24 は小さな係数である。このような曲線 formula_3 は、二つの大きな捩れ部分群(torsion subgroups) formula_26 と formula_27 を持つ。これらの部分群はそれぞれアリスとボブに割り当てられる。（添え字 A がアリスを表し、Bはボブを表す。）
鍵共有プロトコルを実行するとき、まずアリスは自分の捩れ部分群 formula_26 の（秘密の）巡回部分群をランダムに選び、対応する（秘密の）同種写像とターゲット楕円曲線を計算する。そして、ターゲット楕円曲線と、同種写像によるボブの捩れ部分群 formula_27 の像(image)に関する情報をボブに送る。ボブも同様に、formula_27 の部分群を選んで同種写像とターゲット楕円曲線と、自分の同種写像によるアリスの捩れ部分群 formula_27 の像に関する情報をアリスに送る。
これによってアリスとボブは、 二人の秘密の巡回部分群によって決まるカーネルを持つような新しい（formula_3 の）同種写像をそれぞれ計算できるようになる。二人が計算して得る同種写像のカーネルは一致するため、その新しい楕円曲線は同型であり、共通のj-不変量を持つので、その j-不変量を共通鍵とすればよい。
この方式の安全性は、小さい方の捩れ部分群に依存しているため、formula_33 であるように選ぶ必要がある。
詳細については、De Feoによる文献に示されている。
安全性.
SIDHの安全性は、点の数が等しい二つの超特異楕円曲線の間の同種写像を見つける問題と密接に関係してる。
考案者である De Feo、Jao、Plut の３人は、SIDHへの最良の攻撃はrelated を解くことであり、従って古典計算機での計算複雑さは O(p1/4)、量子計算機では O(p1/6) であるとしている。これは、768ビットの素数 p を用いるSIDHが 128ビット安全性を持つことを意味する。
2014年の Delfs and Galbraith による研究により、古典計算機での同種写像問題の計算量は O(p1/4) であることが確認されている。
SIDHの安全性については、Biasse, Jao and Sankarによる研究や Galbraith, Petit, Shani and Ti による研究によって O(p1/4) であることが確認されている（古典計算機の場合）
超特異同種写像ディフィー・ヘルマン方式.
SIDHのいくつかのステップは複雑な同種写像の計算を含んではいるが、プロトコルの全体の流れは自体は、ディフィー・ヘルマン鍵共有方式やその楕円曲線版を知っている人にとっては分かりやすい。
セットアップ.
公開パラメータは以下を含む。
（ネットワーク上の誰でもが使えるようにしても良いし、鍵交換に先立ちアリスとボブの間で同意してもよい。）
鍵交換プロトコル.
アリスとボブが鍵交換をするとき、共通の楕円曲線 E からの同種写像をそれぞれが作る。そのために、同種写像の核空間(kernel)を定義するランダムな点（formula_46 または formula_47）を生成する。formula_46 は二点 formula_49 のランダムな線形結合であり、formula_47 は formula_51 のランダムな線形結合である。異なる点のペアを使うことで、二人が選ぶ同種写像は必ず異なり、非可換である。
formula_46（あるいは formula_47）から、アリス（あるいはボブ）はVeluの公式Velu's formulasを用いて同種写像 formula_54（あるいは formula_55）を計算する。 さらに、ボブは二つの点 formula_56 と formula_57 を、アリスは formula_58 と formula_59 を得る。
二人は、計算した二つの点を通信路を介して交換する。
次に、アリスとボブは、それぞれ受け取った二点から新たな同種写像を生成する。そのため、受け取った二点を上で用いたのと同じ係数を使って線形結合して、点 formula_60 と formula_61 を得る。ここでまた Veluの公式を使って formula_60 と formula_61 に対応する同種写像および新しい楕円曲線を計算する。
鍵交換を完了するには、アリスとボブはそれぞれ得られた楕円曲線の係数から j-不変量を計算する。通信路上でエラーが起こらない限り、二人が計算した j-不変量は等しくなる。
具体的には、プロトコルは以下のように動作する：（以下ではアリスはA、ボブはBと表記する）
1A. Aは二つのランダム整数 formula_64 を選ぶ。
2A. Aは formula_65 を計算する。
3A. Aは formula_46 を用いて同種写像 formula_67 と、formula_3 と同種な楕円曲線 formula_69 を生成する。 
4A. Aは formula_54 を点 formula_43 と formula_44 に適用して、 formula_69 上の二点 formula_74 と formula_75 を計算する。
5A. AはBに formula_76 を送る。
1B - 4B: Bは、1A～4Aを、添え字AとBとを入れ替えて実行する。
5B. BはAに formula_77 を送る。
6A. Aは formula_78 から formula_79 上の点 formula_80 を計算する。
7A. Aは formula_60 を用いて formula_79 と同種な楕円曲線 formula_83 を生成する。
8A. Aは曲線 formula_83 の j-不変量 formula_85 を計算する。
6B - 8B: Bは、6A～8Aを、添え字AとBを入れ替えて実行し、formula_86 を得る。
二つの曲線 formula_87 と formula_83 は同型であり、したがって必ず同じ j-不変量を持つため、formula_89 が成り立つ。formula_90 を何らかの関数で変換したものを共有鍵として使用する。
サンプルパラメータ.
以下に示すパラメータは、De Feoらによって例として与えられている:
法formula_91 : formula_92 とする。したがって，formula_93。
最初の楕円曲線 formula_94：formula_95。
効率.
鍵共有プロトコルにおいて、アリスとボブはそれぞれ、楕円曲線を定義するための(mod p2における)２つの係数と、曲線上の２つの点を相手に送信する。
各楕円曲線の係数は log2p2 ビットが必要で、各楕円曲線上の点は log2p2+1 ビットで表現できるため、送信量は 8log2p + 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には適用できない
<ref name="Report 2016/229"></ref>。
2014年に、ウォータールー大学の研究者がSIDHのソフトウェア実装を開発している。彼らの部分的に最適化したコードをx86-64プロセッサ上で 2.4 GHz で実行したところ、768ビットの法では、鍵交換の計算時間は 200 ミリ秒で終了した。これによって、SIDHが実用的であることが実証された。
2016年には、Microsoftの研究者がSIDHのソフトウェアを公開した。このソフトウェアは、入力によらず常に一定時間で動作し（したがってタイミングアタックに耐性がある）、これまでで最も効率の良い実装である。開発者たちは「公開鍵のサイズは564バイトであり、ほとんどの一般的な耐量子の鍵交換プロトコルよりもかなり小さい。我々のソフトウェアのサイズとスピードは、SIDHが、耐量子の鍵交換プロトコルの候補となる強い可能性を示している。我々の結果がより広い暗号解析の努力を促進させることを願っている。」と述べている。
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 は、楕円曲線の同種写像に基づく否認不可署名の構成方法を示している。