超特異同種写像ディフィー・ヘルマン
二人は、計算した二つの点を通信路を介して交換する。
次に、アリスとボブは、それぞれ受け取った二点から新たな同種写像を生成する。そのため、受け取った二点を上で用いたのと同じ係数を使って線形結合して、点 S B A {\displaystyle S_{BA}} と S A B {\displaystyle S_{AB}} を得る。ここでまた Veluの公式を使って S B A {\displaystyle S_{BA}} と S A B {\displaystyle S_{AB}} に対応する同種写像および新しい楕円曲線を計算する。
鍵交換を完了するには、アリスとボブはそれぞれ得られた楕円曲線の係数から j-不変量を計算する。通信路上でエラーが起こらない限り、二人が計算した j-不変量は等しくなる。
具体的には、プロトコルは以下のように動作する:(以下ではアリスはA、ボブはBと表記する)
1A. Aは二つのランダム整数 m A , n A ( < ( w A ) e A ) {\displaystyle m_{A},n_{A}(<(w_{A})^{e_{A}})} を選ぶ。
2A. Aは R A := m A ⋅ ( P A ) + n A ⋅ ( Q A ) {\displaystyle R_{A}:=m_{A}\cdot (P_{A})+n_{A}\cdot (Q_{A})} を計算する。
3A.
ヴァイエルシュトラス方程式 y 2 = x 3 + a x + b {\displaystyle y^{2}=x^{3}+ax+b} で表現される楕円曲線のj-不変量(j-invaliant) は、次式で与えられる。
j ( E ) = 1728 4 a 3 4 a 3 + 27 b 2 {\displaystyle j(E)=1728{\frac {4a^{3}}{4a^{3}+27b^{2}}}} .
同型(isomorphic)の曲線は同じj-不変量を持つ。代数的に閉じている体においては、同じj-不変量を持つ二つの楕円曲線は同型である。
超特異同種ディフィー・ヘルマンプロトコル(SIDH)では、超特異楕円曲線(の同型類)と曲線間の同種写像を用いる。 2つの楕円曲線 E {\displaystyle E} と E ′ {\displaystyle E'} の間の同種写像 φ : E → E ′ {\displaystyle \phi :E\to E'} は、群準同型性を持つ有理写像(英語版)のことを言う。 曲線 E {\displaystyle E} の任意の巡回部分群 G {\displaystyle G} に対して、 G {\displaystyle G} をカーネルとして持つ同種写像 φ {\displaystyle \phi } と写像先の曲線 E ′ {\displaystyle E'} は、(同型である曲線を同一とみなせば)一意に定まる。
Aは R A {\displaystyle R_{A}} を用いて同種写像 φ A : E → E A {\displaystyle \phi _{A}:E\rightarrow E_{A}} と、 E {\displaystyle E} と同種な楕円曲線 E A {\displaystyle E_{A}} を生成する。
4A. Aは φ A {\displaystyle \phi _{A}} を点 P B {\displaystyle P_{B}} と Q B {\displaystyle Q_{B}} に適用して、 E A {\displaystyle E_{A}} 上の二点 φ A ( P B ) {\displaystyle \phi _{A}(P_{B})} と φ A ( Q B ) {\displaystyle \phi _{A}(Q_{B})} を計算する。
5A. AはBに E A , φ A ( P B ) , φ A ( Q B ) {\displaystyle E_{A},\phi _{A}(P_{B}),\phi _{A}(Q_{B})} を送る。
1B - 4B: Bは、1A~4Aを、添え字AとBとを入れ替えて実行する。
5B. BはAに E B , φ B ( P A ) , φ B ( Q A ) {\displaystyle E_{B},\phi _{B}(P_{A}),\phi _{B}(Q_{A})} を送る。
6A.
E {\displaystyle E} とその巡回部分群 G {\displaystyle G} から、 φ : E → E ′ {\displaystyle \phi :E\to E'} かつ K e r ( φ ) = G {\displaystyle Ker(\phi )=G} であるような φ , E ′ {\displaystyle \phi ,E'} を求める方法は、Véluによって与えらえている。
SIDHのセットアップでは、 p = w A e A ⋅ w B e B ⋅ f ∓ 1 {\displaystyle p=w_{A}^{e_{A}}\cdot w_{B}^{e_{B}}\cdot f\mp 1} の形をした素数 p {\displaystyle p} と、体 F p 2 {\displaystyle \mathbb {F} _{p^{2}}} の上で定義される超特異楕円曲線 E {\displaystyle E} を用意する。 ただし、 w A {\displaystyle w_{A}} と w B {\displaystyle w_{B}} は異なる(小さな)素数であり、指数 e A {\displaystyle e_{A}} と e B {\displaystyle e_{B}} は大きな自然数であり、 f {\displaystyle f} は小さな係数である。このような曲線 E {\displaystyle E} は、二つの大きな捩れ部分群(torsion subgroups) E [ w A e A ] {\displaystyle E[w_{A}^{e_{A}}]} と E [ w B e B ] {\displaystyle E[w_{B}^{e_{B}}]} を持つ。これらの部分群はそれぞれアリスとボブに割り当てられる。