Scientific and Educational Reports of the Facultyof Science and Technology, Kochi University
Vol. 6 (2023), No. 1

同種写像を用いたディフィヘルマン鍵交換とID ベース暗号の実装
Implementations of Diﬃe-Hellman Key Exchange and ID-Based Encryption
by Using Isogenies
境野 圭 ∗ ,塩田研一 †Kei Sakaino∗

Ken-ichi Shiota†

要旨
現在の情報通信は RSA 暗号や楕円曲線暗号等の公開鍵暗号に支えられている。しかし，量子計算機が実用化に至ればこれらの安全性が脅かされることから，耐量子計算機暗号がいくつか提案されている。本研究では，その中でも楕円曲線間の同種写像を用いた暗号方式であるディフィヘルマン鍵交換（SIDH）と ID ベース暗号（SIIBE）の実装を行い，実用上問題ない処理時間で動作することを確認した。論文では，同種写像を高速に計算する
手法と，その最適なパラメータを解析した結果を述べた後，SIDH 鍵交換と SIIBE の実行
時間計測結果について報告する。

同種写像

1

Fq を標数が 5 以上の位数 q の有限体，E : y 2 = x3 + ax + b /Fq を Fq 上の楕円曲線，
O をその無限遠点とし，楕円曲線 E/Fq 上の Fq -有理点の集合を E(Fq ) と表す。また，自然数 m に対して，E の m-等分点の成す部分群を E[m] と表す。定義体の標数 p について，E[p] = { O } であるような楕円曲線を超特異楕円曲線という。

E ′ : Y 2 = X 3 + a′ X + b′ をもう一つの Fq 上の楕円曲線とし，O′ をその無限遠点とする。有理写像 ϕ : E → E ′ /Fq が ϕ(O) = O′ を満たすとき，ϕ を同種写像という。同種写
像は自動的に加法準同型になり，その核 Ker(ϕ) = { P ∈ E | ϕ(P ) = O′ } は E の部分群となる。
逆に，E の有限部分群 C に対して剰余群 E/C も楕円曲線の構造を持ち，自然な準同型

ϕ : E −→ E/C∗

高知大学大学院総合人間自然科学研究科理工学専攻情報科学コース
Information Science Course, Gaduate School of Science and Technology, Kochi University†
高知大学理工学部情報科学科
Department of Information Science, Faculty of Science and Technology, Kochi University

1

は C を核とする同種写像になる。ϕ 及び E ′ = E/C の定義式を求めるには 次の Vélu の公式 [4] を用いる。

1.1

Vélu の公式

楕円曲線 E : y 2 = x3 + ax + b と，その有限部分群 C が与えられているとする。

E ′ = E/C : Y 2 = X 3 + a′ X + b′ と同種写像
E′

∈

∈

−→

ϕ: E

(x, y) 7−→ (X, Y )は次の式で得られる。

Q = (xQ , yQ ) ̸= O ∈ C に対しygQ:= −2yQx
gQ:= 3x2Q + a,

とおいて

tQ :=


x
 gQ

if Q ∈ E[2]

 2g xotherwise

Q

,

y 2
)
uQ := (gQとする。また，S := (C − {O})/ { ±1 } とし，

t :=

∑

tQ ,

u :=

∑

(uQ + xQ tQ )

Q∈S

Q∈S

a′ := a − 5t,b′ := b − 7u

とおいてとする。X, Y は次の式で得られる。
)∑ ( tQuQ
X =x++,
x − xQ (x − xQ )2
Q∈S
)
(
x gy
∑
tQ (y − yQ ) − gQ
2uQ y
Q
+
.
Y =y−
(x − xQ )3(x − xQ )2
Q∈S

1.2

ℓe -同種写像計算

Vélu の公式は核の位数オーダーの計算回数を必要とするが，暗号の設計では核の位数が数百ビットである必要があり，効率が悪い。そこで，同種写像を暗号に利用するためには，位数が小さい素数 ℓ のべき乗 ℓe であるような点 P0 の生成する巡回部分群 ⟨ P0 ⟩ を核として設定し，次のように e 回のステップに分けて同種写像を計算する [2, §4.2.2] 。

2

E1

ϕ1

-

ϕ2

E2

E0 /⟨ℓe−1 P0 ⟩E1 /⟨ℓe−2 P1 ⟩P0 : ℓe -等分点 - ϕ0 (P0 ) = P1

- ϕ1 (P1 ) = P2
- ϕ1 (R1 ) = R2

- ϕ0 (R0 ) = R1

R0

-

···

ϕe−1

-

Ee
=

-

=

ϕ0

=

E = E0Ee−1 /⟨Pe−1 ⟩ ≃ E0 /⟨P0 ⟩-···- ϕe−1 (Pe−1 ) = Pe-···

- ϕe−1 (Re−1 ) = ϕ(R0 )6ϕ
図 1: ℓe - 同種写像計算

このように，楕円曲線上の ℓ 倍算と，核の位数が ℓ の場合の Vélu の公式を複数回組み合わせることにより，核の位数が数百ビットであるときも同種写像計算が計算可能になる。

2同種写像暗号

2.1

SIDH 鍵交換

同種写像を用いたディフィヘルマン鍵交換を SIDH ( Supersingular Isogeny Diﬃe-Hellman ) と呼ぶ [2, §3]。
Alice と Bob が鍵交換したいとする。事前準備として，小さな素数 ℓA , ℓB と，小さなeAeB

整数 f > 0 を選び，素数 p = f × ℓA × ℓB − 1 を作成し公開する。曲線はeA

eB

E(Fp2 ) ≃ (Z/(1 + p)Z)2 ⊇ (Z/ℓA Z)2 ⊕ (Z/ℓB Z)2
eA

eA

eB

となる超特異楕円曲線 E/Fp2 を選び，位数が ℓA である点 PA , QA ∈ E[ℓA ]，位数が ℓBeBである点 PB , QB ∈ E[ℓB ] を公開する。Alice と Bob はそれぞれ次の計算を行う。

Alice
eA

eA

• 点 RA := mA PA + nA QA ∈ E[ℓA ] が位数 ℓA をもつようにランダムな整数
eA

mA , nA ( 0 < mA , nA < ℓA ) を選び，RA と mA , nA を秘匿する。
• ⟨RA ⟩ を核とする同種写像
φ

E −→ EA := E/⟨RA ⟩と φ(PB ), φ(QB ) を計算し，EA , φ(PB ), φ(QB ) を公開する。

Bob
eB

eB

• 点 RB := mB PB + nB QB ∈ E[ℓB ] が位数 ℓB をもつようにランダムな整数
eB

mB , nB ( 0 < mB , nB < ℓB ) を選び，RB と mB , nB を秘匿する。
• ⟨RB ⟩ を核とする同種写像ψE −→ EB := E/⟨RB ⟩と ψ(PA ), ψ(QA ) を計算し，EB , ψ(PA ), ψ(QA ) を公開する。

3

AliceEB と ψ(PA ), ψ(QA ) を用いて
mA ψ(PA ) + nA ψ(QA ) = ψ(mA PA + nA QA ) = ψ(RA )を計算し，⟨ψ(RA )⟩ を核とする同種写像
φ′

EB −→ EAB := EB /⟨ψ(RA )⟩を計算する。

Bob
EA と φ(PB ), φ(QB ) を用いて
mB φ(PB ) + nB φ(QB ) = φ(mB PB + nB QB ) = φ(RB )を計算し，⟨φ(RB )⟩ を核とする同種写像
ψ′

EA −→ EBA := EA /⟨φ(RB )⟩を計算する。
このとき EAB と EBA は同型となるので，その j-不変量を共通鍵とする。その理由は次の通りである。

EAB = EB /⟨ψ(RA )⟩≃ E/⟨RA , RB ⟩≃ EA /⟨φ(RB )⟩= EBA
SIDH 鍵交換の流れを図 2 に示す。
EA

*

H
′

6 HH φ
H

HH


φ

E


HH

HH
H

EB
EA
ψ(PA ) φ(PB )ψ(QA ) φ(QB )

ψ HHH
j

j
H

EAB ≃ EBA



*


? ψ ′EB

図 2: SIDH 鍵交換の流れ
eA

eB

注意 2.1.1. Alice か Bob のどちらかの強度が弱まらないように，ℓA と ℓB のビット数は同程度に設定する必要がある。また，f は p が 素数になるよう設定するが，強度のためには小さい整数であることが望ましい。

4

2.2

SIIBE

ID ベース暗号を，同種写像とペアリングを用いて実現することが可能である。これをSIIBE ( Supersingular Isogeny Identity-Based Encryption ) と呼ぶ [3]。
事前準備
鍵生成局が小さな素数 ℓ と，整数 f > 0 を選び，

• 素数 p = f × ℓe − 1• 位数が 1 + p = f × ℓe である超特異楕円曲線 E0 /Fp• 核の位数が ℓe である同種写像 ϕ : E0 → E1を決める。このとき m = 1 + p, q = p2 として E0 [m] = E0 (Fq ), E1 [m] = E1 (Fq ) が成り立つ。E0 , E1 は公開し，ϕ はマスタ秘密鍵として保持する。さらに×• ペアリング e0 : E0 [m] × E0 [m] → F×q , e1 : E1 [m] × E1 [m] → Fq

• Fq を ID 空間とするハッシュ関数 H : Fq → E0 [m]• gˆ0 ∈ E0 [m] , gˆ1 := ϕ(gˆ0 ) ∈ E1 [m]を決めて公開する。
秘密鍵の生成鍵生成局が各ユーザ X の IDX ∈ Fq から暗号化鍵 h0X = H(IDX ) ∈ E0 [m] を作り，

h1X = ϕ(h0X ) を X へ復号鍵として渡す。
暗号化
ユーザ A に対して平文 M を暗号化するには乱数 ζ ∈ Z/mZ を選んで c := ζ gˆ1 ,ez := (e0 (h0A , ζ gˆ0 ))ℓ , cT := M z を計算しEnc(M ) := (c, cT )を暗号文とする。
復号
ユーザ A は暗号文 C := (c, cT ) を受け取り

Dec(c, cT ) := cT (e1 (h1A , c))−1を計算する。
正しく復号できる理由は次の通りである。

Dec(Enc(M )) = Dec((c, cT ))= cT (e1 (h1A , c))−1= M z(e1 (h1A , ζ gˆ1 ))−1
= M z(e1 (ϕ(h0A ), ϕ(ζ gˆ0 )))−1= M z((e0 (h0A , ζ gˆ0 ))ℓ )−1 = M z z −1 = M.
e5

ここで同種写像とペアリングの適応性 ( compatibility )e1 (ϕ(P ), ϕ(Q)) = e0 (P, Q)deg(ϕ)
を用いた [1, §3]。
注意 2.2.1. z は 1 の f 乗根であるので，全探索による攻撃を避けるためには f を大きく設定しなければならない。

3ℓe -同種写像計算の計算量削減
1.2 節で述べた ℓe -同種写像計算中の計算回数を削減させることで高速に同種写像を計算する手法を述べる。
まず，最も素朴に計算する方法の例を示す。e = 11，核を P0 ∈ E0 [ℓ11 ] としたとき，

ϕ(R0 ) を最も素朴に求める例は図 3 である。

ℓP0 ℓ2 Pℓ10 P· ·q · -q -q -q -q -q -q -q 0
q-q
-q 0 . . . E0
J ϕ0
^q
-q
-q
-q
-q
-q
-q
-q
-q
-q ℓ9 P . . . E1 = E0 /⟨ℓ10 P0 ⟩R1 , P1 J
1
J ϕ1
^q
-q
-q
-q
-q
-q
-q
-q
-q ℓ8 P
R2 , P2 J. . . E2 = E1 /⟨ℓ9 P1 ⟩
2
J
J
..
^q
-q
-q
-q
-q
-q
-q
-q
.
J
J
^q
-q
-q
-q
-q
-q
-q
J
J
^q
-q
-q
-q
-q
-q
J
J
^q
-q
-q
-q
-q
J
J
^q
-q
-q
-q
J
J
^q
-q
-q
J
J
^q
-q
J ϕ9
^q
R10 , P10 J. . . E10 = E9 /⟨ℓP9 ⟩···R0 , P0

図 3: ℓ11 -同種写像の例
図 3 の有向グラフは，ℓ 倍算を緑の枝，同種写像計算を赤の枝で示し，ℓe -同種写像を計算するのに必要な計算を示している。計算手順は次のとおりである。楕円曲線 Ei 上の有理点 Pi を順次 ℓ 倍計算することで，ℓe−i−1 Pi を求める。赤の枝はそれを核として，ϕi (Ri )と ϕi (Pi ) を Vélu の公式で計算する。これらは Ei+1 上の点である。i を 0 から e − 1 までインクリメントすることにより，目的となる楕円曲線 Ee 上の点 ϕe−1 (Re−1 ) = ϕ(R0 )を得ることができる。ℓ 倍算と同種写像の計算回数の合計は O(e2 ) である。本手法は最も素朴な手法であるため simple method と呼ぶことにする。

6

この計算量は，次に示す有向グラフとすることにより O(e log e) まで削減することができる。この有向グラフを optimal tree と呼び，このときの手法を optimal method と呼ぶことにする。

e = 16 のときに optimal tree を生成する手法を図 4 から図 7 に示す。
p

p

p

p -p
^p
p J
p p p p p p p p p p p p p p
p p p p p p p p p p p p p
p p p p p p p p p p p p
p p p p p p p p p p p
p p p p p p p p p p
p p p p p p p p p
p p p p p p p p
p p p p p p p
p p p p p p
p p p p p
p p p p
p p p
p p
p
p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

図 4: Optimal tree の生成 1
p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

p

図 5: Optimal tree の生成 2

図 7: Optimal tree の生成 4

p

p

p

図 6: Optimal tree の生成 3ppp -p -p -p^p p J^p
p J^p -p
p p p p p p p p p p p p J^p
p p p p p p p p p p p p J
p p p p p p p p p p p p
p p p p p p p p p p p
p p p p p p p p p p
p p p p p p p p p
p p p p p p p p
p p p p p p p
p p p p p p
p p p p p
p p p p
p p p
p p
p
p

p -p -p -p -p -p -p -p -p -p -p -p -p -p -p -p
J^p p p p p p p p J^p p p p J^p p J^p
J^p p p p p p p p J^p p p p J^p -p
J^p p p p p p p p J^p p p p J^pJ^p p p p p p p p J^p -p -p -p
J^p p p p p p p p J^p p J^p
J^p p p p p p p p J^p -p
J^p p p p p p p p J^pJ^p -p -p -p -p -p -p -p
J^p p p p J^p p J^p
J^p p p p J^p -p
J^p p p p J^pJ^p -p -p -p
J^p p J
^p
J
^p -p
J
^p

p

p

p

p -p -p -p -p -p -p -p^p p p p J^p p J^p
p J^p p p p J^p -p
p p p p p p p p J^p p p p J^p
p p p p p p p p J^p -p -p -p
p p p p p p p p J^p p J^p
p p p p p p p p J^p -p
p p p p p p p p J^p
p p p p p p p p J
p p p p p p p p
p p p p p p p
p p p p p p
p p p p p
p p p p
p p p
p p
p
p

p

p

p

p

まず，初期設定として図 4 のように枝が 2 本の木を用意する。そして，図 4 と同じ木を2 つ用意し，それらの根に繋がるように 4 本の枝を繋ぎ，図 5 を得る。次に，図 5 と同じ
木を 2 つ用意し，それらの根に繋がるように 8 本の枝を繋ぎ，図 6 を得る。最後は，図 6と同じ木を 2 つ用意し，それらの根に繋がるように 16 本の枝を繋ぎ，図 7 を得る。この
図 7 が optimal tree である。

Optimal tree の枝の合計本数は，e = 2n のとき 2n × n = e × log e となる。従って，本手法を用いた場合の計算回数のオーダーは O(e log e) である。

e が e = 2n と表せないときは，左右のバランスを崩すことにより optimal tree を作成することが可能である。e = 20, 29 のときの例を図 8，9 に示す。

7

q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q
J^q q q q q q q q q q q q J^q q q q J^q q J^q
J^q q q q q q q q q q q q J^q q q q J^q -q
J^q q q q q q q q q q q q J^q q q q J^qJ^q q q q q q q q q q q q J^q -q -q -q
J^q q q q q q q q q q q q J^q q J^q
J^q q q q q q q q q q q q J^q -q
J^q q q q q q q q q q q q J^qJ^q -q -q -q -q -q -q -q -q -q -q -q
J^q q q q q q q q J^q q J^q
J^q q q q q q q q J^q -q
J^q q q q q q q q J^qJ^q -q -q -q -q -q -q -q
J^q q q q J^q q J^q
J^q q q q J^q -q
J^q q q q J^qJ^q -q -q -q
J^q q J
^q
J
^q -q
J
^q

図 8: Optimal tree e = 20 のときの例

q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q
J^q q q q q q q q q q q q q q q q J^q q q q q q q q J^q q q J^q
J^q q q q q q q q q q q q q q q q J^q q q q q q q q J^q -q -q
J
^q q q q q q q q q q q q q q q q J^q q q q q q q q J^q -q
J^q q q q q q q q q q q q q q q q J^q q q q q q q q J^qJ^q q q q q q q q q q q q q q q q J^q -q -q -q -q -q -q -q
J^q q q q q q q q q q q q q q q q J^q q q q J^q q J^q
J^q q q q q q q q q q q q q q q q J^q q q q J^q -q
J^q q q q q q q q q q q q q q q q J^q q q q J^qJ^q q q q q q q q q q q q q q q q J^q -q -q -q
J^q q q q q q q q q q q q q q q q J^q q J^q
J^q q q q q q q q q q q q q q q q J^q -q
J^q q q q q q q q q q q q q q q q J^qJ^q -q -q -q -q -q -q -q -q -q -q -q -q -q -q -q
J^q q q q q q q q J^q q q q J^q q J^q
J^q q q q q q q q J^q q q q J^q -q
J^q q q q q q q q J^q q q q J^qJ^q q q q q q q q J^q -q -q -q
J^q q q q q q q q J^q q J^q
J^q q q q q q q q J^q -q
J^q q q q q q q q J^qJ^q -q -q -q -q -q -q -q
J^q q q q J^q q J^q
J^q q q q J^q -q
J^q q q q J^qJ^q -q -q -q
J^q q J
^q
J
^q -q
J
^q

図 9: Optimal tree e = 29 のときの例

8また，ℓ 倍算，同種写像計算の計算時間は少なからず計算機に依存する。実用の際は，扱う計算機において計算時間の比率を計測し，最短の計算時間で実行できるように枝の本数を設定する [2, §4.2] 。本研究では，比率を 1 : 1 として実験した。実装は，まず optimal

tree を作成し，その木の通りに同種写像計算と楕円曲線上の加算を繰り返す。
一般に ℓ 倍算と同種写像計算の計算時間比を α : β とするとき，optimal tree を生成するアルゴリズムは次の通りである。optimal tree は e − 1 次行列 Se = (sij ) として表し，
その (i, j)-成分は Ei 上の点 ℓj Pi に対する作業を次のように表すこととする：• sij = 0 : 計算無し
• sij = 1 : ℓ 倍算 ℓ(ℓj Pi ) を計算• sij = 2 : Vélu の公式 ϕi (ℓj Pi ) = ℓj Pi+1 を計算• sij = 3 : ℓ 倍算の結果を受けて ℓ 倍算と Vélu の公式を計算• sij = 4 : Vélu の公式の結果を受けて ℓ 倍算と Vélu の公式を計算
アルゴリズム 1 Optimal tree creation
Input: e, ℓ 倍算の重み α, 同種写像計算の重み β
Output: optimal tree Se
cost1 ← 0, cost2 ← α + βS2 ← (4)for n = 3 to e do
costk + costn−k + (n − k) × α + k × β を最小とする k ( 1 ≤ k ≤ n − 1 ) を検索
costn ← costk + costn−k + (n − k) × α + k × β
k0 ← (k, k)1 ← n − k0(n)Sn = sij ← n − 1 次ゼロ行列(n)for j = 0 to k1 − 1 do s0j ← 1(n)for i = 0 to k0 − 1 do si0 ← 2
Sk0 を k1 列右シフトして Sn に上書き
Sk1 を k0 行下シフトして Sn に上書き(n)s0k1 ← 3(n)

if k1 > 1 then sk0 0 ← 4(n)s00 ← 4end forreturn Se

9ℓe -同種写像計算の実装実験

4

本研究での実験環境は次の通りである。実装には Java の BigInteger クラスを用いた。
表 1: 実験環境

OS
CPU
メモリ
システムの種類
言語
コンパイラ

4.1

Windows 10 Pro バージョン 22H2
R CoreTM i9-11900K @ 3.50GHz 3.50GHz
11th Gen Intel⃝
32.0GB (31.9GB 使用可能)
64 ビットオペレーティングシステム, x64 ベースプロセッサ
Java 19.0.1
javac 19.0.1

Optimal method の実装

Optimal method を実装し，パラメータを取り換えて実行時間を計測する。実験条件は次の通りである。p = f × ℓe − 1 としたときの ℓe のビット数を固定し，素数 ℓ は 2, 3, 5,

7, 11, 13 で比較する。また， f は ℓe のビット数と同じになるように設定する。入力する
超特異楕円曲線 E0 ，核 P0 ∈ E[ℓe ]，点 R0 は同じものを使用する。100 回実行した平均時間を実験結果とする。

Optimal method に対する simple method の実行時間の比率を測定した結果を表 2 に示す。

表 2: Optimal method に対する simple method の実行時間の比率
素数ℓℓe のビット数
128 256 512 1024

2
3
5
7
11
13

6.0
6.3
4.3
3.2
2.5
2.5

10.3
10.9
7.3
5.6
4.1
3.7

18.0
19.2
12.8
9.6
7.0
6.4

32.3
34.4
22.7
17.0
12.2
11.1

表 2 より，ℓe のビット数を大きくするほど simple method に比べ速度の向上が大きくな
る結果となった。e が大きいほど O(e2 ) と O(e log e) の差が大きくなることが影響すると考えられる。また，ℓ を大きくすると，simple method に比べ速度の向上割合が小さくなることが判明した。ℓ を大きくすると削減できる枝の本数が減少することに加え，一つ当たりの ℓ 倍算と同種写像の計算コストが増加することが原因であると考えられる。

10

次に，表 3 にそれぞれの ℓe のビット数に対して パラメータ毎に 1 回の同種写像計算にかかる計算時間を示す。
表 3: Optimal method の計算時間 [秒]素数ℓℓe のビット数
128 256 512 1024

2
3
5
7
11
13

0.02
0.02
0.02
0.02
0.03
0.03

0.12
0.10
0.10
0.11
0.13
0.14

0.66
0.59
0.60
0.67
0.77
0.79

4.51
3.96
4.09
4.54
5.18
5.36

Optimal method は ℓ = 2 を除いて ℓ が小さいほど高速に動作することが判明した。

4.2ℓ = 2, 3 の場合に特化した Vélu の公式

高島 [5, p.12] では ℓ = 2 の場合に特化した Vélu の公式が示されている。本研究では，ℓ = 3 の場合にもそれに特化した Vélu の公式を用いることにより高速化を図った。
ℓ = 2 のとき楕円曲線 E : y 2 = x3 + ax + b 上の 2-等分点 Q = (xQ , 0) に対し，同種写像

ϕ : E −→ E ′ ,E ′ = E/⟨Q⟩ : Y 2 = X 3 + a′ X + b′は次式で与えられる。

tQ := 3x2Q + aとして，

a′ := a − 5tQ , b′ := b − 7xQ tQ ,
{
}
tQ
tQ
, Y =y 1−.
X =x+
x − xQ(x − xQ )2ℓ = 3 のとき
核が 3-等分点のときも次のように Vélu の公式を簡潔に記述できる。
楕円曲線 E : y 2 = x3 + ax + b 上の 3-等分点 Q = (xQ , yQ ) に対し，同種写像

ϕ : E −→ E ′ ,E ′ = E/⟨Q⟩ : Y 2 = X 3 + a′ X + b′11は次式で与えられる。
x
gQ:= 3x2Q + a,xtQ := 2gQ
= 2(3x2Q + a),ygQ:= −2yQ ,y 2
uQ := (gQ
) = 4(yQ )2として，

a′ := a − 5tQ , b′ := b − 7(uQ + xQ tQ ),
{
}
tQ
uQ
tQ
2uQ
X =x+
+
, Y =y 1−−.
x − xQ (x − xQ )2(x − xQ )2 (x − xQ )3

上記の ℓ = 2, 3 のときに特化した Vélu の公式に加え，2 倍算，3 倍算も最適化し optimal

method に組み込む。本手法を optimal method with simple formulas と呼ぶことにする。
Optimal method with simple formulas に対する optimal method の実行時間の比率を表4 に示す。参考として，optimal method with simple formulas に対する simple method の
実行時間の比率を表 5 に示す。

表 4: Optimal method with simple formulas に対する optimal method の実行時間の
比率
素数
ℓ

2
3

表 5: Optimal method with simple formulas に対する simple method の実行時間の比率ℓe のビット数
128 256 512 1024
1.4
1.4

1.5
1.4

1.5
1.4

素数
ℓ

1.5
1.4

2
3

ℓe のビット数
128 256 512 1024
8.6
9.0

15.0
15.3

26.5
27.0

48.0
48.4

Vélu の公式と楕円曲線上の加算を最適化させることにより，optimal method よりさらに 1.4 倍〜1.5 倍高速化した。次に，表 6 に，それぞれの ℓe のビット数に対して 1 回の同種写像計算にかかる計算時間を示す。

表 6: Optimal method with simple formulas の実行時間

ℓe の
ビット数
128
256
512
1024

実行時間 [秒]ℓ=2 ℓ=3

0.016
0.079
0.451
3.034

12

0.014
0.071
0.417
2.616

表 3 と 表 6 を比較した結果，optimal method with simple formulas は，どの ℓ についての optimal method の実行時間よりも短い時間で動作することを確認した。例えば

SIDH 鍵交換では，小さな素数 ℓ を 2 つ用意する必要があるが，これらは 2 と 3 が適切であることが明らかになった。

SIDH 鍵交換, SIIBE の実装と実行速度

5SIDH 鍵交換と SIIBE を実装し，実用的な鍵サイズでの実行時間を測定する。同種写像
計算は，本研究で最も高速に動作した手法である optimal method with simple formulasを使用する。

SIDH 鍵交換の実装と実験

5.1

本節では 2.1 節で述べた SIDH を実装し，実行時間を測定する。実験条件は次の通りで
eA

eBある。p = f × ℓA × ℓB − 1 に対して，ℓA = 2, ℓB = 3 とする。p は 128 ビット，256
ビット，512 ビット，1024 ビットでそれぞれ実験する。f は小さいビット数が望ましいたeAめ，ランダムに 20 ビット以下の正の整数を選び，残りの p のビット数を ℓA のビット数
eBと ℓB のビット数が同程度になるように eA と eB を選択する。曲線は CM 法を用いて超特異楕円曲線を生成する。以上の条件の下，100 回 SIDH を実行した平均実行時間は次のようになった。
表 7: SIDH の平均実行時間

p のビット数
128
256
512
1024

平均実行時間 [秒]

0.04
0.21
1.10
7.97

p のビット数を 512 としたとしても，平均 1.1 秒で動作することを確認できた。

5.2

SIDH 鍵交換の数値例

p のビット数が 254 ビットのときの例を示す。記号は節 2.1 に準じている。

13

p
E : y2= 821567 × 2118 × 374 − 1 (2118 のビット数 : 119，374 のビット数 : 118)
= 55354804868874296338872938406488614177080837520664041078134855038103623565311= x3 + 40417794031241549707748494709499623049932040094453109358638148123059788634987 x+ 45396797643785798584789975941829286758981639236523419931803717094741066945095(mod 55354804868874296338872938406488614177080837520664041078134855038103623565311)

PA= ( 26102265900913132216324954701666615341828028826375526228233080646634393197343+ 9167607572850195059253511101098133216855482734008259561385765165909321552516 i,
4768392627377563845615167599389891827945948239929122584412452832051576614285+ 39583001829215754248811452187334769916944203611643454264261224649704078386749 i )QA= ( 16419309770954556293126497788576157050064038769134975924381700696754829741385+ 2257599459949817366931538247858370290499941855026445157834569200795559491964 i,
4889390439105394286448508405985795353256460773409859191412620347745691507586+ 28625051516602030813594217943750193656409030131993570320006564372947737595941 i )PB= ( 6101996650329658109164087344807084868443744807345698640234847414501293213252+ 46991952733872132041913727733854989220878280421923551061526907057859451374442 i,
8620939699035219500401568444989403697027763789713483074185214435592931383603+ 7787974427179894404910964341717767594785112484405121276378215640617270363645 i )QB= ( 24101128355261807044712405767527199357425902865986973450467502226805766884768+ 49165029885587917017542338015217591855693354201064484145172188061353199582513 i,
2398644570720472640848995819987446544619030980755670778545089672827536588344+ 3154982418123800687719829693931971314123249375464057098362215912839641381391 i )mA= 262151770619228789254827514573750011

nA
RA= 318584208557734815676494971505242631= ( 53782868188384247654743708822445587164946676759377500736402535113619117773936+ 31704242681374499664775643152283108860078619526920402922266435709666778532294 i,
41168751817644237151697513287953031686349884858796618423458388111096810056270+ 51986863178962236537624390502832048946085803427391647593144777801203705754732 i )mB= 135273219196619178737655514334762883

nB= 162451797652781039421985432829957056

RB= ( 21631292719515335583655509038921161920274371981333374384015976459639655943229+ 36642880056717294225714605777870396070268220187561760807501486127748745021695 i,
19599098566888746669505932500239841044752723388450140932596459162144142167373+ 38047301902161696783172199552400250507381553142095232069780204615407420987455 i )φ(PB ) =( 36870835972505809056661128198724688404972144151309736682072564787786079672265+ 5133111506557340047320668722938590701542181858612545925464304902072596102028 i,
14113914106205049002557042656637100127393754113809433279694884745214534024260+ 19550056221053948106817889373171760056678025692416547525116422050206616688092 i )14

φ(QB )=

( 40592907683503498764373872213522905597150559210216476801571776320753788442941+ 7047218703418579282872219467936607710426575990613466566399816052515381294819 i,
52661468236299943707287675911527352777103605116571848578348769374356853725866+ 2924385988811294479294487982712932076626172693463006451606583321067895732563 i )φ(RB )=( 4583842687453210967452382218279080056630996201697516670814592740618784034506+ 24261627028588264530153070110552217281513641019668758192645010218161473893414 i,
51152516853552948670684943306065662602836923670833175900135844559821911757480+ 16028025106245030273625386884240447321221556831340718440951900601568135857733 i )ψ(PA )=( 18598622957114423613740643243211374611714708243699175603764600052151610517604+ 5216252986117292526705673760987735422565098154810329886473615131484698148778 i,
12204310840849679800625218584703971502588134846434935911504771828290390784697+ 32415996152346820693499667628662725078606919314336355178358056887956823342922 i )ψ(QA )=( 16117267126103977372280707286700167939038449789904734023300589789437458857936+ 54796499594041661161768753657424543353457797897212131119924160709347061190926 i,
52934864064149747305620788491757569465962497816586590991164056573806890935863+ 23007740916631564614461562531541715380594734056782316270783751639295779429361 i )ψ(RA )=( 35688676386474294728901474226313212693282111487053787052869408713368999077440+ 47050263870802569447924320187363838045036209128188656361918364398428973565787 i,
9733590384717002172074659327205417727344548092939906957349238280450616986540+ 44029580856469323018108782424089083958831939640919541927074703633185490666325 i )EA : y2= x3 + ( 40956092948066896294601569038326615429063353911588206327444902209924897089689+37745300089799895778757951587409536564582742629084498131215296726083469521638 i ) x+ ( 47019671881634836830398161999211231232260598404423287578936615333866741584235+48101641600168017371449202685812730246307498303895997927412224043724491961123 i )(mod 55354804868874296338872938406488614177080837520664041078134855038103623565311)

EB : y2= x3 + ( 1269498639358534657003348473046988850578233730534071519210942915204861358513+46676449947968833225759527065876335196278785430518088155656823738555163144860 i ) x+ ( 44425348601543330008771249458213341537320189924390382337180853062162175617511+10050929913356925611700313776328360323523865745975986215699990493411176104448 i )(mod 55354804868874296338872938406488614177080837520664041078134855038103623565311)

EAB

=

EBA :

2

=

x3 + ( 51429330059312707161400727104341372075771243839592853034837092403072307485177

y+7925523642178061515219142047829063333674871961497938647637379992937762774294 i ) x+ ( 20409855163874460579201762601880666583370641764814866964227773355788696406639+13459123622548355331233323819687342054665284573185622044949952908402353873395 i )(mod 55354804868874296338872938406488614177080837520664041078134855038103623565311)
j(EAB )=

j(EBA )=

22731710315759414739049418555877888561670888007059347290802869343905819904391+17625469119007401672699099803018842173287111511830149207824686724277932102327 i

ただし i =√

−1 ∈ Fp2 とする。

15

5.3

SIIBE の実装と実験

本節では 2.2 節で述べた SIIBE を実装し，実行時間を測定する。実験条件は次の通りである。p = f × ℓe − 1 に対して，ℓ = 2 とする。p は 128 ビット，256 ビット，512 ビット，
1024 ビットでそれぞれ実験する。注意 2.2.1 より，f は大きくする必要があるため，f のビット数は 2e のビット数と同程度になるよう設計する。曲線は CM 法を用いて超特異楕円曲線を生成し，ペアリングは Weil ペアリングを用いる。なお Weil ペアリング計算アル
ゴリズムも Java で実装した。以上の条件の下，100 回 SIIBE を実行した平均実行時間は次のようになった。
表 8: SIIBE の平均実行時間

p のビット数
128
256
512
1024

平均実行時間 [秒]

0.02
0.10
0.46
2.46

p のビット数を 512 としたとしても，平均 0.46 秒で動作することを確認できた。アルゴ
リズム中にペアリング計算を含むが，ℓe -同種写像計算の回数が少ない分，SIDH 鍵交換よりは短い実行時間で動作した。

5.4

SIIBE の数値例

p のビット数が 257 ビットのときの例を示す。記号は節 2.2 に準じている。なお本実験
では，m-等分点に値をとるハッシュ関数は簡易的なものを用いた。
p
E0 : y2=389914925368855257150786563197020999657 × 2128 − 1=

132681173702315141865438014550186471435326052993279445372984380168176079470591=

x3 + 23768282817421533350044451586087825948731877973852780463641192819242426934638 x+ 15845521878281022233362967724058550632487918649235186975760795212828284623092

ϕの核 P

=

(mod 132681173702315141865438014550186471435326052993279445372984380168176079470591)( 81370727764711652912568091494244918775521733188745718659708080599275566126062+ 112534723667661811105846136186774083467077282535008085692031074764958349863944 i,
49553030590094737682537350837927493634360832959191377217365039460118726974935+ 70389499044337049845688120501007985593343159095606597984589527912548070956957 i )E1 : y2=x3 + ( 88584009117305586086058882985827780040062253268660311292944211991843660284796+28502558832025109448464856585960442956088907003995086644063190989425492868334 i ) x+ ( 47591816879788159289844701761563967006171704703542295545994480410002089988535+121450383030063813945874331613376613134504297445409991093329764593538823000022 i )(mod 132681173702315141865438014550186471435326052993279445372984380168176079470591)

16

gˆ0

=

( 51247311715671372201081561044214226861498294252965592383493407772231955808543+ 111285987005568582060001807560211775197234993185432047653324220309758994882443 i,
14488001326424757036604273219444877282605344124174241768005679742848425351162+ 73244330747803764811275854290098977337476707432944933406481561737388132164792 i )gˆ1=( 99693601447418388035053214616419490027015231670259893188061924699151334358402+ 102688379322842421812176756134643591984595501776299595735316242773429849898092 i,
70066883673639595025889560837973261339963560179900161980900654779453322198224+ 67129541715786341992072497408813598344549120764773630456294974059560686421646 i )IDX= ksakaino@is.kochi − u.ac.jp

h0X

=

h1X

=

( 20678506974986819748901564238839171084474281415541795035215740224107296864171 ,107361932079546562168871441856986314269996232216665442041003621720056693359798 )( 127405673988859476167363252496912399243314052154228291093834421350101852638372+ 39403103345798159454185531845516659154476942836047315947645311375760500042234 i,
47304090301473113664492826818864578709433626968185239187685884241583566381295+ 17660592112153324926162768376332901492168483746295328888621948687248211798978 i )M=34096057100933967347878698843465580915564799680760691986248126232050335246463+ 76282367112771029249718966038757600572408978578053931405971465663533852549869 i

c =( 59125352684484104737052185531933643615610466706824217453460817025567948285264+ 67558933277096854268849520923472614347660232542632025179059725772179854828603 i,
114200752739050057226406851008209549719202307919032729344232753930422464558861+ 11277016952228983295279172909770829278330305786858273145959701030209764731399 i )cT=

Enc(M )
Dec(c, cT )109180213589888456130184305856114284493637118884906839563930956678541605376362+ 63737405569186021927306831909183274474929742892219727367638335942595644807318 i= (c, cT )=34096057100933967347878698843465580915564799680760691986248126232050335246463+ 76282367112771029249718966038757600572408978578053931405971465663533852549869 i=

M

ただし i =

6√

−1 ∈ Fp2 とする。

まとめ

耐量子計算機暗号に用いる同種写像計算を実装し，動作速度の検証に加え，SIDH 鍵交
換と SIIBE の実装を行った。同種写像計算は素朴な手法では計算回数の合計は O(e2 ) であるが，最適な計算手順を踏むことで O(e log e) まで削減することができる。本手法を実装することで，例えば ℓe のビット数が 256 のとき，素朴な手法に比べ 3.7 倍〜10.9 倍高速化した。また，同種写像計算ではパラメータとして小さな素数 ℓ が必要であるが，特に ℓ = 2, 3 のときは Vélu の公式中の計算を簡略化することが可能である。楕円曲線上の2 倍算，3 倍算も簡略化した関数を用いることで，更に 1.4 倍〜1.5 倍の高速化を実現できた。以上の結果より，ℓe -同種写像に用いる小さな素数 ℓ は 2, 3 が適切であった。SIDH とSIIBE は，素数 p のビット数が 256 のとき，SIDH は平均 0.21 秒，SIIBE は平均 0.10 秒で17動作した。また，p のビット数を 512 としても，SIDH は平均 1.10 秒，SIIBE は平均 0.46秒で動作した。充分高速に動作し，実用上問題ない処理時間であることを確認できた。

参考文献[1] Andreas Enge, Bilinear pairings on elliptic curves , HAL Id: hal-00767404 (2014).
[2] Luca De Feo, David Jao and Jérôme Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol. 8 (2014), 209-247.
[3] Takeshi Koshiba and Katsuyuki Takashima, New Assumptions on Isogenous Pairing
Groups with Applications to Attribute-Based Encryption. ICISC 2018, LNCS 11396(2019), 3-19.
[4] Jacques Velu, Isogénies entre courbes elliptiques, C.R. Acad. Sc. Paris, Séries A.
273 (1971), 238-241. ( https://aghitza.org/publications/translation-velu/ に Alex
Ghitza による英訳がある )[5] 高島克幸, 同種写像グラフの数理と耐量子計算機暗号への応用, 早稲田整数論セミナー,
2022 年 4 月 22 日.

18