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

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

概要

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

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

背景

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

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

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

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

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

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

安全性

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

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

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

セットアップ

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

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

鍵交換プロトコル

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

サンプルパラメータ

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

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

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

効率

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

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

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

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

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

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

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

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

出典

1. Costello, Craig; Jao, David; Longa, Patrick; Naehrig, Michael; Renes, Joost; Urbanik, David (2016-10-04). Efficient compression of SIDH public keys. https://eprint.iacr.org/2016/963. 
2. Utsler, Jim (2013年). “Quantum Computing Might Be Closer Than Previously Thought”. IBM. 27 May 2013閲覧。
3. ^ De Feo, Luca. “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies”. PQCrypto 2011. Springer. 4 May 2014閲覧。
4. Higgins, Parker. “Long Term Privacy with Forward Secrecy”. Electronic Frontier Foundation. 4 May 2014閲覧。
5. Zhu, Yan. “Why the Web Needs Perfect Forward Secrecy More Than Ever”. Electronic Frontier Foundation. 4 May 2014閲覧。
6. J., Vélu (1971). “Isogénies entre courbes elliptiques”. C.R. Acad. Sc. Paris, Série A., 273: 238–241. 
7. De Feo, Luca (2017). "Mathematics of Isogeny Based Cryptography". arXiv:1711.04062 [cs.CR]。
8. Delfs, Christina; Galbraith (29 October 2013). "Computing isogenies between supersingular elliptic curves over F_p". arXiv:1310.7789 [math.NT]。
9. biasse. “A quantum algorithm for computing isogenies between supersingular elliptic curves”. CACR. 11 December 2016閲覧。
10. Galbraith. “ON THE SECURITY OF SUPERSINGULAR ISOGENY CRYPTOSYSTEMS”. IACR. 5 Jan 2020閲覧。
11. Costello, Craig. “Efficient Compression of SIDH public keys”. 8 October 2016閲覧。
12. “Key Compression for Isogeny-Based Cryptosystems”. eprint.iacr.org. 2016年3月2日閲覧。
13. Fishbein, Dieter (30 April 2014). “Machine-Level Software Optimization of Cryptographic Protocols”. University of Waterloo Library - Electronic Theses. University of Waterloo. 21 June 2014閲覧。
14. Costello, Craig; Longa, Patrick; Naehrig, Michael (2016-01-01). Efficient algorithms for supersingular isogeny Diffie-Hellman. https://eprint.iacr.org/2016/413. 
15. Koziel, Brian; Jalali, Amir; Azarderakhsh, Reza; Kermani, Mehran; Jao, David (2016-11-03). NEON-SIDH: Efficient Implementation of Supersingular Isogeny Diffie-Hellman Key Exchange Protocol on ARM. https://eprint.iacr.org/2016/669. 
16. Jalali, A.; Azarderakhsh, R.; Kermani, M. Mozaffari; Jao, D. (2017). “Supersingular Isogeny Diffie-Hellman Key Exchange on 64-bit ARM”. IEEE Transactions on Dependable and Secure Computing PP (99): 1. doi:10.1109/TDSC.2017.2723891. ISSN 1545-5971. https://ieeexplore.ieee.org/abstract/document/7970184/. 
17. Koziel, Brian; Kermani, Mehran; Azarderakhsh, Reza (2016-11-07). Fast Hardware Architectures for Supersingular Isogeny Diffie-Hellman Key Exchange on FPGA. http://eprint.iacr.org/2016/1044. 
18. Rostovtsev, Alexander (2006年). “PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES”. Springer. 29 May 2006時点のオリジナルよりアーカイブ。10 May 2014閲覧。
19. Childs, Andrew M; Jao, Soukharev (2014). “Constructing elliptic curve isogenies in quantum subexponential time”. Journal of Mathematical Cryptology 8: 1–29. arXiv:1012.4019. doi:10.1515/jmc-2012-0016. 
20. Sun, Xi; Tian (2 March 2014). “Toward quantum-resistant strong designated verifier signature”. International Journal of Grid and Utility Computing 5 (2): 80. doi:10.1504/IJGUC.2014.060187. http://dl.acm.org/citation.cfm?id=2608696 21 June 2014閲覧。. 
21. Jao, David; Soukharev, Vladimir (3 October 2014). “Isogeny-based quantum-resistant undeniable signatures”. Post-Quantum Cryptography. Lecture Notes in Computer Science. 8772. pp. 160–179. doi:10.1007/978-3-319-11659-4_10. ISBN 978-3-319-11658-7. http://cacr.uwaterloo.ca/techreports/2014/cacr2014-15.pdf 28 April 2016閲覧。