自己双対型 PotBKZ 基底簡約の提案と BKZ との比較
>100 Views
February 14, 26
スライド概要
基底簡約は最短ベクトル問題や最近ベクトル問題などの格子問題を解く際には必須の技術である．その基底簡約の中でも，BKZ簡約は格子ベースの暗号の安全性解析にも用いられる強い簡約アルゴリズムであるが，その停止性は保証されていない．本稿では，停止性を保証する新しいBKZの変種を提案する．基底のポテンシャルと呼ばれる量に着目し，そのアルゴリズムをPotBKZと命名する．特に基底に挿入することでポテンシャル量を減少させるベクトルを数え上げるPotENUMや，双対型のアルゴリズムである双対型PotENUMを開発する．PotBKZの中では厳密SVPアルゴリズムの代替としてPotENUMを全ての局所射影ブロック格子に対して呼び出し，基底のポテンシャル量を単調に減少させる．また，その双対型である双対型PotBKZの中でも，双対基底を求めることなく全ての局所射影ブロック格子に対して双対型PotENUMを呼び出し，基底のポテンシャル量を単調に減少させる．自己双対型PotBKZでは，ツアー毎にPotBKZと双対型PotBKZを交互に呼び出すことで，ポテンシャル量を単調に減少させ，有限回のツアーで停止させる．
立教大学大学院で，格子基底簡約アルゴリズムに関する研究をしています． 趣味でゲーム開発も行ってます． C++ | Go | Python | SageMath | Asir | Bash NTL | Eigen | DXライブラリ Visual Studio
関連スライド
各ページのテキスト
自己双対型 PotBKZ 基底簡約の提案と BKZ との比較 ◎ 佐藤 新 1 安田 雅哉 1 1 立教大学 2025 年 1 月 29 日（水） ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 1 / 20
研究背景 格子暗号の安全性評価と基底簡約アルゴリズム 格子暗号は耐量子計算機暗号の一つ（ML-KEM, ML-DSA, Falcon） ▶ ▶ 安全性は SVP や CVP などの格子問題の求解困難性に基づく 格子暗号の安全性評価には，格子問題の求解困難性評価が必要 基底簡約は格子問題の求解に必須の技術 ▶ ▶ LLL [7] ⇝ 格子次元に関して多項式時間計算量 BKZ [9] やその改良 ⇝ ブロックサイズに関して指数時間計算量 BKZ は強力な基底簡約アルゴリズムで，安全性解析における標準ツール LLL と異なり，BKZ の停止性は理論的には保証されてない ⋆ 実用上，実行時間や繰り返し（ツアー）回数に上限を設けて強制停止 (fplll[2] 内の BKZ オプションとして max_time や max_loops がある) ⋆ ⋆ ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 2 / 20
本研究の目的 停止性を保証する BKZ の変種の提案と BKZ との実験比較 1 停止性を保証する BKZ[9] の変種 PotBKZ を提案 ▶ 基底に対して定まるポテンシャル量を利用 ⋆ ▶ 2 ポテンシャル量は LLL[7] の多項式時間での停止性を保証する量 PotBKZ ではポテンシャル量を単調減少させる基底操作のみを行う =⇒ 多項式回のツアー回数で停止することが保証できる PotBKZ の様々な変種を開発＋実験比較 ▶ ▶ 双対型や自己双対型の PotBKZ まで開発 BKZ と実験比較：BKZ とのツアー回数，出力基底の品質を比較 ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 3 / 20
数学的準備：格子の基礎 定義 1 (格子の GSO ベクトルと体積) 一次独立な b1 , . . . , bn の整数係数の一次結合全体 P L = L(b1 , . . . , bn ) := { ni=1 ai bi | a1 , . . . , an ∈ Z} を格子，{b1 , . . . , bn } を基底，n を次元と呼ぶ． b⋆1 := b1 , b⋆i := bi − Pi−1 ⋆ ⋆ ⋆ 2 j=1 µi,j bj , µi,j := ⟨bi , bj ⟩/∥bj ∥ で定義される b⋆1 , . . . , b⋆n を GSO ベクトル，µ = (µi,j ) を GSO 係数行列と呼ぶ． 格子 L の体積を vol(L) = Qn と表し，これは基底にとり方によらない ◎ 佐藤, 安田 ⋆ i=1 ∥bi ∥ 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 4 / 20
数学的準備：基底簡約の概要 基底簡約：長く平行に近い基底を短く直交に近い基底に変換する操作 格子の基底は無数に存在 良い基底の方が SVP や CVP などの格子問題が求解しやすい ▶ 代表的なアルゴリズム：LLL[7]，BKZ[9] ▶ ▶ 87349 83474 98247464 847984 0 1 0 0 0 0 1 0 0 0 0 1 悪い基底 基底のノルムが長くほぼ平行 基底簡約 −8 8 −1 3 −7 −9 14 4 −2 −3 −11 16 8 6 12 17 良い基底 基底のノルムが短くほぼ直交 ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 5 / 20
ポテンシャル量と LLL アルゴリズム
基底 {b1 , . . . , bn } のポテンシャル量
Pot({b1 , . . . , bn }) :=
LLL アルゴリズム [7]
次の条件を満たす基底を見つける
1
2
|µi,j | ≤ 1/2
2
δ · b⋆k−1 ≤ ∥πk−1 (bk )∥2
特に，条件 2 を満たさない
(bk , bk+1 ) を交換（Step 7）
▶
ポテンシャルが δ 倍ずつ減少
=⇒ 多項式時間で停止
Qn
⋆ 2(n−k+1)
>0
k=1 ∥bk ∥
Algorithm LLL 基底簡約アルゴリズム [7]
Require: 格子 L の基底 {b1 , . . . , bn }
定数 1/4 < δ < 1
Ensure: δ に関して LLL 簡約された基底
1: k ← 2
2: while k ≤ n do
3:
基底をサイズ簡約 [6]
4:
if 条件 2 を満たす then
5:
k ←k+1
6:
else
7:
swap(bk , bk+1 )
8:
k ← max{k − 1, 2}
◎ 佐藤, 安田
自己双対型 PotBKZ の提案と BKZ との比較
2025 年 1 月 29 日（水）
6 / 20
DeepLLL アルゴリズムと PotLLL アルゴリズム 基底に対する deep-inserion という操作 σk,ℓ ({b1 , . . . , bn }) = {. . . , bk−1 , bℓ , bk , . . . , bℓ−1 , bℓ+1 . . .} DeepLLL アルゴリズム [9] PotLLL アルゴリズム [3] 次の条件を満たす基底を見つける 次の条件を満たす基底を見つける 1 2 |µi,j | ≤ 1/2 δ · ∥b⋆i ∥2 ≤ ∥πi (bk )∥2 1 条件 2 を満たさない基底を deep-insertion で入れ替え ▶ ポテンシャルは増えたり減ったり =⇒ 指数時間 2 |µi,j | ≤ 1/2 δ · Pot(B) ≤ Pot(σk,ℓ (B)) 条件 2 を満たさない基底を deep-insertion で入れ替え ▶ ▶ Pot(B) を下げる deep-insertion のみ ポテンシャルが単調減少 =⇒ 多項式時間で停止 ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 7 / 20
PotENUM：PotLLL の一般化
Pot(B) を減少させる格子ベクトル v =
i=j vi bi (vm = 1) の数え上げ
Pm
C = {. . . , bj−1 , v, bj , . . . , b|
m , . . .}：j 番目に v を挿入+bm を除去
▶ Pot(C) < Pot(B)
（cf., PotLLL[3] では deep-insertion σj,m で得られる基底に限定）
▶
従来の ENUM[4] と PotENUM の比較（Di := ∥πi (v)∥, Bi := ∥b⋆i ∥）
ENUM[4]
v の条件
探索方法
挿入による効果
Dj < B j
Djj
PotENUM
m−1
Y
2
Di < δ
Bi
m−1
Y
i=j+1
Dj < R
2
∥b⋆j ∥ を減少
i=1
δB1 · · · Bm−1
Dj < Rj2 , Rj2 =
Dk+1 · · · Dm−1
Pot(B) を減少
◎ 佐藤, 安田
1/j
自己双対型 PotBKZ の提案と BKZ との比較
2025 年 1 月 29 日（水）
8 / 20
PotBKZ（1/2）：BKZ との構成の差異 BKZ[9] LLL[7] ENUM[4] 今回開発 PotBKZ PotLLL[3] PotENUM 今回開発 PotBKZ では BKZ の LLL を PotLLL に，ENUM を PotENUM に置き換え PotLLL と PotENUM はどちらもポテンシャルを単調減少 ▶ PotENUM が呼ばれる回数（ツアー回数）は格子次元に関して多項式的 ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 9 / 20
PotBKZ（2/2）：アルゴリズムの概要
Algorithm PotBKZ 基底簡約アルゴリズム
Require: n 次元格子の基底 {b1 , . . . , bn }，簡約変数 1/4 < δ < 1
Ensure: 簡約された基底 {b1 , . . . , bn }
1: {b1 , . . . , bn } ← PotLLL({b1 , . . . , bn }, δ) /* BKZ[9] では LLL[7] を利用*/
2: z ← 0
3: while z < n − 1 do
4:
j ← (j mod n − 1) + 1; k ← min(j + β − 1, n)
5:
v ← PotENUM(πj (bj ), . . . , πj (bk )) /* BKZ では ENUM[4] で最短ベクトルを探索*/
6:
if no solution then
7:
z ←z+1
8:
else
9:
{b1 , . . . , bn } ← MLLL({. . . , bj , v, bj+1 , . . .}, δ) /* MLLL[9] で一次独立性を除く*/
10:
{b1 , . . . , bn } ← PotLLL({b1 , . . . , bn }, δ)
11:
z←0
◎ 佐藤, 安田
自己双対型 PotBKZ の提案と BKZ との比較
2025 年 1 月 29 日（水）
10 / 20
自己双対型 PotBKZ：自己双対型 BKZ との構成の差異 今回開発 自己双対型 PotBKZ 自己双対型 BKZ[8] BKZ[9] 双対型 BKZ[8] 双対型 PotBKZ 今回開発 PotBKZ 自己双対型 PotBKZ は PotBKZ とその双対型を交互に呼び出す 双対型 PotBKZ を開発 双対基底を求めるには逆行列計算が必要 双対型 PotENUM⇝双対基底への挿入でポテンシャルが減少するベクトルの数え上げ ▶ 逆行列計算が不要 ▶ ▶ ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 11 / 20
実験結果（1/3） ：実装方法と実験方法 実装方法 実装は総て C++言語で NTL ライブラリ [10] と Eigen ライブラリ [5] を使用 g++でコンパイル ▶ コンパイルオプションは-O3 -mtune=native -march=native -mfpmath=both ▶ 基底は long 型，GSO 情報は long double 型を使用 ▶ ▶ 実験方法 ▶ ▶ SVP-challenge[1] のシード 0〜9 で実行 ツアー回数，ポテンシャル量の対数値，GSA スロープの傾きの平均をとる ⋆ GSA スロープの傾きは良い基底を判断する指標の一つ（小さい方が良い） ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 12 / 20
実験結果 (2/3)：100 次元のポテンシャル量の変化 #,;ͷϙςϯγϟϧྔ 1PU#,;ͷϙςϯγϟϧྔ ࣗݾରܕ1PU#,;ͷϙςϯγϟϧྔ ϙςϯγϟϧྔͷର πΞʔ PotBKZ は 1 ツアー目で一気にポテンシャルが低くなり，その後 2 ツアーで停止 自己双対型 PotBKZ も同様の挙動を取り 4 ツアーで停止 ▶ PotBKZ より小さいポテンシャル量をとる 一方，BKZ[9] は緩やかに減少し，その後 7 ツアー目頃から停滞を続ける ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 13 / 20
実験結果 (3/3)： 実験結果 Intel Core i7-1355U @ 1.70 GHz 上で実験 ブロックサイズは β = 40 を選択 ▶ PotBKZ は約 2 回程度のツアー回数で停止 ▶ 自己双対型 PotBKZ も約 5 回程度のツアー回数で停止 ▶ ▶ ⋆ ▶ 格子 階数 100 110 120 PotBKZ よりも低い GSA スロープの傾きとポテンシャル量の対数値の比をとる 一方, BKZ[9] と比較すると高く，十分に下げられていない ツアー 回数 ≥ 20 ≥ 20 ≥ 20 BKZ[9] log Pot の比 0.9668 0.9658 0.9616 −ρ 0.0553 0.0561 0.0558 ツアー 回数 1.9 1.9 1.7 PotBKZ log Pot −ρ の比 0.9735 0.0615 0.9722 0.0617 0.9685 0.0612 自己双対型 PotBKZ ツアー log Pot −ρ 回数 の比 4.8 0.9714 0.0595 5.2 0.9697 0.0594 5.9 0.9665 0.0597 ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 14 / 20
まとめ PotBKZ と自己双対型 PotBKZ の開発と実験 ポテンシャルの単調減少により停止性の保証された BKZ[9] の変種 基底への挿入でポテンシャルが減少するベクトルを数え上げる PotENUM を開発 ▶ その双対版，自己双対版を開発 ▶ 120 次元格子での実験結果 ▶ ▶ ⇝ PotBKZ は 2 ツアー程度，自己双対型 PotBKZ は 5 ツアー程度で停止 ⇝ 一方 BKZ は 20 ツアー以上を要する 今回の実験結果から得られた知見 ▶ PotBKZ や自己双対型 PotBKZ は BKZ ほどポテンシャルを下げれない ⋆ ⋆ より大きなブロックサイズを試せばBKZ 程度の品質が出せると期待 より大きなブロックサイズの利用のため，枝切りや篩の適用をしたい ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 15 / 20
PotBKZ とその変種の公開ソースコード 本研究の成果となるソースコードを GitHub にて公開 https://github.com/satoshin-des/self-dual-PotBKZ ファイル構成 ┣━━ src ┃ ┃ ┃ ┗━━各種ソース（SelfDualPotBKZ.h，PotBKZ.h など） ┣━━ svp_challenge_list ┃ ┃ ┃ ┗━━テストケースとして svp challenge[1] の基底（LLL 済） ┣━━ libSDPotBKZ.so ┃ ⇝C++ファイルをコンパイルした共有ライブラリ ┗━━ excample.py ⇝libSDPotBKZ.so を python で動かすテストコード ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 16 / 20
参考文献 I [1] TU Darmstadt. SVP challenge. Available at https://www.latticechallenge.org/svp-challenge/. [2] The FPLLL development team. fpylll, a Python wrapper for the fplll lattice reduction library, Version: 0.6.1. Available at https://github.com/fplll/fpylll, 2023. [3] Felix Fontein, Michael Schneider, and Urs Wagner. PotLLL: A polynomial time version of LLL with deep insertions. Designs, Codes and Cryptography, 73:355–368, 2014. ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 17 / 20
参考文献 II [4] Nicolas Gama, Phong Q Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Advances in Cryptology–EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 257–278. Springer, 2010. [5] Gaël Guennebaud, Benoît Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010. [6] C. Hermite. Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objects de la théorie des nombres. Journal für die reine und angewandte Mathematik, 40:261–277, 1850. ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 18 / 20
参考文献 III [7] Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. [8] Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction. In Advances in Cryptology–EUROCRYPT 2016, volume 9665 of Lecture Notes in Computer Science, pages 820–849. Springer, 2016. [9] Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 66:181–199, 1994. ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 19 / 20
参考文献 IV [10] Victor Shoup. NTL: A Library for doing Number Theory. http://www.shoup.net/ntl/. ◎ 佐藤, 安田 自己双対型 PotBKZ の提案と BKZ との比較 2025 年 1 月 29 日（水） 20 / 20