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

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

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

Summarize Timeline Top Qs Fact Check

ヴァイエルシュトラス方程式${\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]}。

Summarize Timeline Top Qs Fact Check

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}$。