---
title: 重み付きポテンシャルを用いたw-PotBKZ 基底簡約の提案
tags:  #格子アルゴリズム #scis2026 #格子基底簡約  
author: [さとしん](https://convert.docswell.com/user/astonish)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/LJ1YQZXXEG.jpg?width=480
description: 基底簡約は最短ベクトル問題や最近ベクトル問題などの格子問題を解く際には必須の技術である．その基底簡約の中でも，BKZ簡約は格子暗号の安全性解析にも用いられる強い簡約アルゴリズムであるが，その停止性は保証されていない．SCIS2025ではポテンシャル量を単調減少させることで多項式回のツアーでの停止性が保証されたBKZの変種PotBKZを提案した．本稿ではを一般化した重み付きポテンシャルという量を定義した上で，PotBKZの一般化であるw-PotBKZを提案する．特定の重みによるポテンシャルと基底の品質を示す指標の1つであるGSA-slopeの和は定数となり，重みつきポテンシャルの減少によりslopeの改善が期待できる．そこで基底への挿入で重み付きポテンシャルを減少させるベクトルを探索する$\bm{w}$-PotENUMを開発する．更に，w-PotENUMを局所射影ブロック格子に対して呼び出し，重み付きポテンシャル量を単調に減少させるw-PotBKZを開発する．
published: February 14, 26
canonical: https://convert.docswell.com/s/astonish/ZN9E1P-scis2026-1B1-2
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/LJ1YQZXXEG.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/GJWGM9NK72.jpg)

研究背景
格子暗号の安全性評価と基底簡約アルゴリズム
格子暗号は耐量子計算機暗号の一つ（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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/4EZLQ93N73.jpg)

PotBKZ の課題
初期のポテンシャル減少は高速
I しかし高々 4 ∼ 5 ツアー後の BKZ の品
質には劣る
I
PotENUM の探索範囲の限界
I



課題事項

停止性を保証しつつ探索範囲を広げられ
るか？
I ポテンシャルとは別の評価軸から品質改
善できるか？
◎ 佐藤, 安田


単調減少はするが，探索範囲が狭く不
十分
I
#,;ͷϙςϯγϟϧྔ
1PU#,;ͷϙςϯγϟϧྔ

ϙςϯγϟϧྔͷର਺஋
高速だが，品質は劣る
                    
πΞʔ਺
Figure: 110 次元のポテンシャルの比較
w-PotBKZ 基底簡約の提案
2026 年 1 月 26 日（月）
3 / 21


# Page. 4

![Page Image](https://bcdn.docswell.com/page/Y76W6KX97V.jpg)

本研究の目的
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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/G75M6PXD74.jpg)

数学的準備（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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/9J29M6QMER.jpg)

数学的準備（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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/DEY4X9WPJM.jpg)

数学的準備（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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/VJNY1L9M78.jpg)

ポテンシャルと 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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/YE9P542WJ3.jpg)

ポテンシャルと GSA スロープの傾き
仮定 (GSA)
b?1 , . . . , b?n ：簡約された基底の GSO ベクトル
3 ∃
2
2
≤ q &lt; 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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/GE8DYQ5RED.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/LELM4XY27R.jpg)

PotLLL と w-PotLLL(2/2)
PotLLL 基底と w-PotLLL 基底の理論上界の比較
b?1 , . . . , b?n ：基底の GSO ベクトル
4
α := 4δ−1
（ 14 &lt; δ &lt; 1：簡約パラメタ）
1 ≤ i &lt; k ≤ n：インデックス
理論上界を初めて証明
2
:
kb?i k
2
kb?k k
αk−i+1
4(α−1)
/
&lt;
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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/4JMYKLN9JW.jpg)

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) &lt; Pot(w, B)
I
従来の ENUM[5] と w-PotENUM の比較（Di := kπi (v)k , Bi := kb?i k , Wi,j :=
2
ENUM[5]
v の条件
Dj &lt; Bj
探索方法
Dj &lt; R
挿入による効果
kb?j k を減少
◎ 佐藤, 安田
h=i wh ）
Pj
PotENUM
m
m
Y
Y
2Wm,n
vm
Diwi &lt;
Biwi
i=k
2
2
i=k
δB1 · · · Bm−1
Dj &lt; Rj2 , Rj2 =
wj+1
wm−1
Dj+1
· · · Dm−1
Pot(w, B) を減少
w-PotBKZ 基底簡約の提案
!1/W1,j
2026 年 1 月 26 日（月）
12 / 21


# Page. 13

![Page Image](https://bcdn.docswell.com/page/PJR9XKD979.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/PEXQ6L13JX.jpg)

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 &lt; δ &lt; 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 &lt; 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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/3EK91L2NED.jpg)

実験結果（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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/L73WQ34Z75.jpg)

実験結果 (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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/87DK94Q4JG.jpg)

実験結果 (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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/VJPKZMLVE8.jpg)

まとめ
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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/2EVVW9QREQ.jpg)

参考文献 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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/57GLDZW6EL.jpg)

参考文献 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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/4EQY1L32JP.jpg)

参考文献 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


