重み付きポテンシャルを用いたw-PotBKZ 基底簡約の提案

重み付きポテンシャルを用いた w-PotBKZ 基底簡約の提案 Proposal of w-PotBKZ Basis Reduction Using Weighted Potential ◎ 佐藤 新 1 1 安田 雅哉 1 立教大学大学院理学研究科 2026 年 1 月 26 日（月） ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 1 / 21

• #p21

研究背景 格子暗号の安全性評価と基底簡約アルゴリズム 格子暗号は耐量子計算機暗号の一つ（ML-KEM, ML-DSA, FN-DSA） I I 安全性は SVP や CVP などの格子問題の求解困難性に基づく 格子暗号の安全性評価には，格子問題の求解困難性評価が必要 基底簡約は格子問題の求解に必須の技術 I I LLL [7] 格子次元に関して多項式時間計算量 BKZ [8] やその改良 ブロックサイズに関して指数時間計算量 F F I BKZ は強力な基底簡約で，安全性解析の標準ツール（停止性は保証されてない） 実用上，実行時間や繰り返し（ツアー）回数に上限を設けて強制停止 (fplll[2] 内の BKZ オプションとして max_time や max_loops がある) PotBKZ[10] SCIS2025 で提案 ポテンシャル Pot (B) を単調減少 =⇒ 停止性を理論的に保証（多項式回のツアーで停止） n Q i 2 Q F Pot (B) := b?j ：格子基底 {b1 , . . . , bn } の品質を表す指標の 1 つ F i=1 j=1 ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 2 / 21

• #p20
• #p19
• #p21
• #p1

PotBKZ の課題 初期のポテンシャル減少は高速 I しかし高々 4 ∼ 5 ツアー後の BKZ の品 質には劣る I PotENUM の探索範囲の限界 I    課題事項  停止性を保証しつつ探索範囲を広げられ るか？ I ポテンシャルとは別の評価軸から品質改 善できるか？ ◎ 佐藤, 安田   単調減少はするが，探索範囲が狭く不 十分 I #,;ͷϙςϯγϟϧྔ 1PU#,;ͷϙςϯγϟϧྔ  ϙςϯγϟϧྔͷର਺஋ 高速だが，品質は劣る                      πΞʔ਺ Figure: 110 次元のポテンシャルの比較 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 3 / 21

• #p1

本研究の目的 2 0.0 GSA-slope GSA-slope 0.5 0 1.0 2 log bb1i 2 2 log bb1i 2 2 4 1.5 2.0 2.5 6 3.0 8 3.5 0 10 20 30 40 index 50 60 70 80 0 10 20 30 40 index 50 60 70 80 Figure: GSA スロープの比較：簡約前（左）と簡約後（右） 1 目的：BKZ[8] 並みの品質と理論的保証 I I 2 停止性の保証: 理論的な停止性を担保 高品質基底: BKZ[8] に匹敵する GSA スロープを実現 提案：w-PotBKZ (PotBKZ[10] の一般化) I I ポテンシャルを重みにより一般化 原理： 「重み付きポテンシャル +GSA スロープ = 一定」を利用 ポテンシャル減少操作により，スロープを 0 (平坦) に近づける 3 検証：理論と実験による比較 I I 理論: w-PotLLL と PotLLL の上界比較 実験: 対 BKZ 比較（ツアー数，出力品質） ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 4 / 21

• #p20
• #p21
• #p1

数学的準備（1/3） 格子の基礎 定義 (格子の GSO ベクトルと体積) 一次独立な b1 , . . . , bn の整数係数の一次結合全体 Pn L = L(b1 , . . . , bn ) := { i=1 ai bi | a1 , . . . , an ∈ Z} を格子，{b1 , . . . , bn } を基底，n を次元と呼ぶ． b?1 := b1 , b?i := bi − Pi−1 ? j=1 µi,j bj , µi,j := hbi , b?j i/kb?j k2 で定義される b?1 , . . . , b?n を GSO ベクトル，µ = (µi,j ) を GSO 係数行列と呼ぶ． 格子 L の体積を vol(L) = Qn ? i=1 kbi k と表し，これは基底にとり方によらない ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 5 / 21

• #p1

数学的準備（2/3） 重み付きポテンシャルと GSA スロープの傾き 定義 (重み付きポテンシャル，GSA スロープの傾き) {b1 , . . . , bn }：基底，Bi := kb?i k ，w := (wi )1≤i≤n 2 ポテンシャルと重み付きポテンシャル Pot (B) := Qn Qi i=1 j=1 Bj Qn Qi Pot (w, B) := i=1 j=1 Bjwi GSA スロープの傾きと重み付き GSA スロープの傾き Q n Q i Bi sl(B) := n(n23−1) log i=1 j=1 B j  w i Q Q n i Bi sl(w, B) := n(n23−1) log i=1 j=1 B j ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 6 / 21

• #p1

数学的準備（3/3） 基底簡約の概要 基底簡約：長く平行に近い基底を短く直交に近い基底に変換する操作 格子の基底は無数に存在 良い基底の方が SVP や CVP などの格子問題が求解しやすい I 代表的なアルゴリズム：LLL[7]，BKZ[8] I 目的の 1 つに GSA スロープの傾きの絶対値を小さくすること [3, pp.9] I I   87349 0 0 0  83474 1 0 0     98247464 0 1 0  847984 0 0 1  基底簡約 悪い基底 基底のノルムが長くほぼ平行 sl ≈ −6.8266 ◎ 佐藤, 安田 −8  −7   −2 8 8 −9 −3 6  −1 3 14 4   −11 16  12 17 良い基底 基底のノルムが短くほぼ直交 sl ≈ 0.358622 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 7 / 21

• #p20
• #p19
• #p1

ポテンシャルと GSA スロープの傾き 命題 B ：n 次元格子の基底 w = (wi )1≤i≤n ：重み   n X log Pot(w, B) n+1 iwi log Bi + sl(w, B) = 2 3 2 i=1 [3, section 2.3] の式 (1) log Pot (B) +   n+1 sl(B) = (n + 1) log vol(L) 3 の一般化になっている wi = 1i とすると右辺が定数になる I 以降，重みとして wi = 1i を選択 ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 8 / 21

• #p19
• #p1

ポテンシャルと GSA スロープの傾き 仮定 (GSA) b?1 , . . . , b?n ：簡約された基底の GSO ベクトル 3 ∃ 2 2 ≤ q < 1 s.t. 1 ≤ ∀ i ≤ n, kb?i k ≈ q i−1 kb?1 k 4 GSA の下で GSA スロープの傾きと重み付きポテンシャルの和は一定：      1 n (2) log Pot ,B + sl(B) ≈ 2 log vol(L) i i 2 I 重み付きポテンシャルを下げると GSA スロープの傾きが改善 F 後述するが，重み付きポテンシャルの減少により，理論的に基底をより短くできる ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 9 / 21

• #p1

PotLLL と w-PotLLL(1/2) PotLLL の一般化として w-PotLLL を開発 基底に対する deep-insetion という操作 σk,` ({b1 , . . . , bn }) = {. . . , bk−1 , b` , bk , . . . , b`−1 , b`+1 . . .} w-PotLLL アルゴリズム ← 今回開発 PotLLL アルゴリズム [4] 次の条件を満たす基底を見つける 次の条件を満たす基底を見つける 1 2 |µi,j | ≤ 1/2 δPot(B) ≤ Pot(σk,` (B)) 1 2 条件 2 を満たさない基底を deep-insertion で入れ替え I I Pot(B) を下げる deep-insertion のみ ポテンシャルが単調減少 =⇒ GSA スロープの傾きが改善する (式 (1)) ◎ 佐藤, 安田 |µi,j | ≤ 1/2 δ wk−1 Pot(w, B) ≤ Pot(w, σk,` (B)) 条件 2 を満たさない基底を deep-insertion で入れ替え I I Pot(w, B) を下げる deep-insertion のみ 重み付きポテンシャルが単調減少 =⇒ GSA スロープの傾きが改善する (式 (2)) w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 10 / 21

• #p19
• #p10
• #p8
• #p9
• #p1

PotLLL と w-PotLLL(2/2) PotLLL 基底と w-PotLLL 基底の理論上界の比較 b?1 , . . . , b?n ：基底の GSO ベクトル 4 α := 4δ−1 （ 14 < δ < 1：簡約パラメタ） 1 ≤ i < k ≤ n：インデックス 理論上界を初めて証明 2 : kb?i k 2 kb?k k αk−i+1 4(α−1) / < PotLLL 2 w-PotLLL : kb?i k 2 kb?k k / α k−i− k (k−1)(k−2)(log(k−1)−log(i−1)) 4(α−1) w-PotLLL 基底の方が PotLLL 基底よりも短い I GSA スロープの傾きがより改善されると期待 ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 11 / 21

• #p1

w-PotENUM
PotENUM の一般化

Pot(w, B) を減少させる格子ベクトル v =

i=j vi bi (vm 6= 0) の数え上げ

Pm

PotENUM[10] の一般化
I C = {. . . , b
j−1 , v, bj , . . .}：j 番目に v を挿入
I Pot(w, C) < Pot(w, B)
I

従来の ENUM[5] と w-PotENUM の比較（Di := kπi (v)k , Bi := kb?i k , Wi,j :=
2

ENUM[5]
v の条件

Dj < Bj

探索方法

Dj < R

挿入による効果

kb?j k を減少

◎ 佐藤, 安田

h=i wh ）

Pj

PotENUM
m
m
Y
Y
2Wm,n
vm
Diwi <
Biwi
i=k

2

2

i=k

δB1 · · · Bm−1
Dj < Rj2 , Rj2 =
wj+1
wm−1
Dj+1
· · · Dm−1
Pot(w, B) を減少

w-PotBKZ 基底簡約の提案

!1/W1,j

2026 年 1 月 26 日（月）

12 / 21

• #p21
• #p20
• #p1

w-PotBKZ（1/2）：BKZ との構成の差異 今回開発 w-PotBKZ BKZ[8] LLL[7] ENUM[5] w-PotLLL 今回開発 w-PotENUM 今回開発 PotBKZ では BKZ の LLL を PotLLL に，ENUM を PotENUM に置き換え PotLLL と PotENUM はどちらもポテンシャルを単調減少 I PotENUM が呼ばれる回数（ツアー回数）は格子次元に関して多項式的 ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 13 / 21

• #p20
• #p1

w-PotBKZ（2/2）：アルゴリズムの概要
BKZ[8]: LLL[7] と ENUM[8] の組み合わせ
w-PotBKZ: w-PotLLL と w-PotENUM の組み合わせ（1, 5, 11 行目）
Algorithm w-PotBKZ(w, β, δ): w-PotBKZ アルゴリズム
Require: n 次元格子の基底 {b1 , . . . , bn }，ブロックサイズ 2 ≤ β ≤ n，簡約パラメタ 14 < δ < 1，重み w = (wi )1≤i≤n
Ensure: 簡約基底 {b1 , . . . , bn }
1: {b1 , . . . , bn } ← w-PotLLL({b1 , . . . , bn }, w, δ)/* BKZ[8] では LLL[7] を利用*/
2: z ← 0; j ← 0
3: while z < n − 1 do
4:
j ← (j mod n − 1) + 1; k ← min(j + β − 1, d)
5:
v ← w-PotENUM (πj (bj ), . . . , πj (bk ))/* BKZ では ENUM[5] で最短ベクトルを探索*/
6:
if no solution then
7:
z ←z+1
8:
else
9:
z←0
10:
{b1 , . . . , bn } ← MLLL({. . . , bj−1 , v, bj , . . .}, δ)/* MLLL[8] で一次独立性を取り除く*/
11:
{b1 , . . . , bn } ← w-PotLLL({b1 , . . . , bn }, w, δ)

◎ 佐藤, 安田

w-PotBKZ 基底簡約の提案

2026 年 1 月 26 日（月）

14 / 21

• #p20
• #p1

実験結果（1/3） ：実装方法と実験方法 実装方法 実装は総て C++言語で NTL ライブラリ [9] と Eigen ライブラリ [6] を使用 g++でコンパイル I コンパイルオプションは-O3 -flto -march=native -funroll-loops -ffast-math I 基底は long 型，GSO 情報は long double 型を使用 I I 実験方法 I I SVP-challenge[1] のシード 0～9 で実行 ツアー回数，ENUM のノード数，GSA スロープの傾きの平均をとる ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 15 / 21

• #p21
• #p20
• #p19
• #p1

実験結果 (2/3) 100 次元の ENUM のノード数と GSA スロープの傾きの変化 0.085 BKZ PotBKZ w-PotBKZ slope 0.075 0.070 0.065 0.060 ENUM PotENUM w-PotENUM 106 Number of nodes for ENUM 0.080 105 104 103 102 101 0.055 100 0 3 6 9 Tours 12 15 18 1 10 20 30 40 50 60 70 80 90 99 GSA スロープの傾きの比較（右図） PotBKZ は 1 ツアー目で一気に GSA スロープの傾きが減少し，その後はほとんど変化することなく 5 ∼ 6 ツアー程度で 停止する w-PotBKZ は PotBKZ と比較すると緩やかなものの，PotBKZ よりも改善（まだ不十分） ノード数の比較（左図） PotENUM と比較すると w-PotENUM のノード数は多いものの，ENUM と比較すると少なく抑えられる ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 16 / 21

• #p15
• #p1

実験結果 (3/3) 実験結果 Intel Core i7-1355U @ 1.70 GHz 上で実験 ブロックサイズは β = 40 を選択 I PotBKZ は約 2 回程度のツアー回数で停止 I 自己双対型 PotBKZ も約 5 回程度のツアー回数で停止 I I F I PotBKZ よりも低い GSA スロープの傾きとポテンシャル量の対数値の比をとる 一方, BKZ[8] と比較すると高く，十分に下げられていない 格子 階数 #Tours 100 110 120 130 ≥ 20 ≥ 20 ≥ 20 ≥ 20 ◎ 佐藤, 安田 BKZ[8] PotBKZ[10] w-PotBKZ ENUM PotENUM w-PotENUM −sl(B) #Tours −sl(B) #Tours −sl(B) のノード数 のノード数 のノード数 1398330.8 0.05224 2.643 11371.5 0.06173 7.134 75764.1 0.06012 1888054.7 0.05229 2.698 11699.5 0.06186 7.983 74371.1 0.06046 1844612.2 0.05239 3.388 12641.3 0.06187 9.023 67156.3 0.06083 2030502.9 0.05255 3.408 12853.3 0.06172 9.321 65933.1 0.06089 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 17 / 21

• #p20
• #p21
• #p1

まとめ w-PotBKZ の開発と実験 SCIS2025 で提案の PotBKZ[10] の一般化 重み付きポテンシャルの減少により，GSA スロープの傾きが改善 I PotBKZ よりも短い基底を出力することが期待 I 100 次元格子での実験結果 I I GSA スロープの傾きは PotBKZ が 0.06173 に対し w-PotBKZ は 0.06012 に改善 ノード数は 11372 から 75764 に広がる =⇒ 探索範囲が広がる ? ENUM[5] の 1398331 と比べると少なくより高速 今回の実験結果から得られた知見 I BKZ ほど GSA スロープの傾きを改善できない 自己双対型の w-PotBKZ の開発をしたい 理論的により短い基底を出力できる w の取り方を研究したい F 単調減少するだけでなく，適切に増加させることによる効果なども研究したい F F ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 18 / 21

• #p21
• #p20
• #p1

参考文献 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] Léo Ducas, Ludo N. Pulles, and Marc Stevens. Towards a modern LLL implementation. Cryptology ePrint Archive, Paper 2025/774, 2025. [4] 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. ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 19 / 21

• https://www.latticechallenge.org/svp-challenge/
• https://github.com/fplll/fpylll
• #p1

参考文献 II [5] 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. [6] Gaël Guennebaud, Benoît Jacob, et al. Eigen v3. http://eigen.tuxfamily.org, 2010. [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] Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 66:181–199, 1994. ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 20 / 21

• http://eigen.tuxfamily.org
• #p1

参考文献 III [9] Victor Shoup. NTL: A Library for doing Number Theory. http://www.shoup.net/ntl/. [10] 佐藤新 and 安田雅哉. 自己双対型 PotBKZ 基底簡約の提案と BKZ との比較, 2025. ◎ 佐藤, 安田 w-PotBKZ 基底簡約の提案 2026 年 1 月 26 日（月） 21 / 21

• http://www.shoup.net/ntl/.
• #p1