耐量子暗号

現在のインターネットでは,クレジットカードなどのプライバシー情報が多くやり取りされるようになっています.通信を秘匿するために, 様々な暗号が用いられています.それらの暗号は素因数分解の困難性や離散対数問題の困難性などの数学的な困難性に基づいている.
1994年, RSAと楕円曲線DH鍵共有などが量子コンピュータが完成するとこれらの安全性がなくなります.そのため, それらにも対抗できるような暗号が求められています.そのような暗号を耐量子暗号と呼びます.

同種写像暗号

Supersingular isogeny Diffie–Hellman key exchangeは, De Feo, Jao, Plutによって2011年に開発されたアルゴリズムである.

Supersingular Isogeny Diffie Helman

公開パラメータ

小さな素数$l_a, l_b$と, 小さな正の整数$f$を選ぶ.そして, $p = f * l_a^{e_a} * l_b^{e_b} - 1$が素数となるように選び公開情報とする.曲線は$E(\mathbb{F}_{p^2}) \simeq (\mathbb{Z}/(1 + p)\mathbb{Z})^2 \supseteq (\mathbb{Z}/l_a^{e_a}\mathbb{Z})^2 \oplus (\mathbb{Z}/l_b^{e_b}\mathbb{Z})^2$となるような超特異楕円曲線を選び, 位数が$l_a^{e_a}$である点$P_a, Q_a \in E[l_a^{e_a}]$, 位数が$l_b^{e_b}$である点$P_b, Q_b \in E[l_b^{e_b}]$を公開情報とする.

鍵生成

点$R_a := m_aP_a + n_aQ_a \in E[l_a^{e_a}]$が位数$l_a^{e_a}$を持つようにランダムな整数$m_a, n_a$を選び秘密情報とする.
$\langle R_a \rangle$を核とする同種写像$\phi: E \rightarrow E_a := E/\langle R_a \rangle$と$\phi(P_b), \phi(Q_b)$を計算する.これらを公開鍵とする.
同様にBobも計算する

鍵交換

$E_b$と$\phi(P_a), \phi(Q_a)$を用いて,$m_a\phi(P_a) + n_a\phi(Q_a) = \phi(m_aP_a + n_aQ_a) = \phi(R_a)$を計算し,
$\langle \phi(\langle R \rangle)\rangle$を書くとする同種写像$\phi^{'}: E_b \rightarrow E_{ab} := E_b/\langle \phi(\langle R \rangle)\rangle$を計算する.
同様にBobの計算する.

この手順を踏むことでAliceとBobが生成した鍵の$j$不変量が互いに一致する.その$j$不変量を共有鍵として用いる.

注意事項

An efficient key recovery attack on SIDHによりSIDHへの古典確率的多項式時間での鍵復元攻撃が見つかった.
SIDHベースのKEMが全て破られた.

おわりに

An efficient key recovery attack on SIDHを逆に?使ったFESTAとかいうものがあるらしいので勉強してみたい.
暗号の研究つらいけどたのしいよ

同種写像暗号 SIDH鍵共有