格⼦暗号の安全性を検証する
最短ベクトル問題に対する解読システムの開発
⽴岩 ⻫明1, 品野 勇治2, ⼭村圭⼀郎1, 吉⽥ 明広1
鍛冶 静雄1, 安⽥ 雅哉3, 藤澤 克樹1
1 九州大学

2 Zuse Institute Berlin
3 立教大学

2021/5/14
先駆的科学計算に関するフォーラム2021@オンライン1

⽬次
1. 研究背景: 最適化問題やグラフ解析, 格⼦暗号, 格⼦, 最短ベクトル問題(SVP)
2. 並列システム: 格⼦, 格⼦アルゴリズムの性質, 実装
3. 数値実験: SVP Challenge, 求解性能評価, 通信遅延評価
4. 結論
2

研究背景
数理最適化及びグラフ解析への HPC 適⽤• ⼤規模グラフ解析及び数理最適化システムの開発と評価• Graph500 ベンチマーク 通算12期 : 世界第1位(京及び富岳, 2014年〜2020年)• ⼤規模最適化問題(半正定計画問題)に対する⼤規模GPU 活⽤ (SC12, IPDPS14)• 格⼦暗号︓最短ベクトル問題 (SC20 : 本発表)

Supercomputer Fugaku
RIKEN Center for Computational Science(R-CCS)
is ranked

No.1
on the Graph500 BFS Ranking of Supercomputers with102956 GE/s on Scale 41
on the 21th Graph500 list
Congratulations from the Graph500 Executive Committee

Society 5.0 と産業アプリケーション• Society5.0 などが⽬指す超スマート社会に向けて，道路や電⼒網などのインフラを含めた都市計画への活⽤から、ヒト・モノの動きの解析まで多岐にわたる課題を解決• ⺠間企業との協業で⼤量のセンサーデータやオープンデータなどを⽤いて、サイバー空間での最適化やシミュレーションを⾏う産業アプリケーションの開発を推進
3

研究背景
量⼦計算機/アルゴリズムの台頭• Shorのアルゴリズムに代表される量⼦アルゴリズム
及び ⼤規模量⼦計算機の開発により広く普及しているRSA暗号や楕円曲線暗号の効率的な解読が危惧されている.
(国家機密であれば, 40~50年ほどの期間, 情報が守られている必要がある)

耐量⼦計算機暗号の標準化• そこで量⼦計算機でも効率的に解読できない
耐量⼦計算機暗号の選定が進められている (Post-Quantum Cryptography Standardization1)• 格⼦問題の求解困難性を拠り所にした格⼦暗号が有⼒な候補の⼀つ
その上で格⼦暗号の
1. 安全性の検証
2. 適切な公開鍵サイズの検証が急務になっている

1h"ps://csrc.nist.gov/projects/post-quantum-cryptography

4

研究背景
最短ベクトル問題(SVP)• 多くの格⼦暗号の安全性を⽀えている問題• さまざまな求解アルゴリズムが考案されているが, 決定的なものはない• さらに, ⼤規模計算機を⽤いた求解実験はなく,⼤規模並列化による求解困難性の評価が未検証であった

研究⽬標
最短ベクトル問題の⼤規模並列ソフトウェアの開発
及び, それを⽤いた最短ベクトル問題の求解困難性の検証
5

Contribution

MAP-SVP: the Massive Parallel Solver for Shortest Vector Problemの実装とその評価ü 分散で⾮同期的な SVP ソルバ
ü 安定的なMPI並列実⾏が可能(最⼤103,680 coresを⽤いた実⾏実績)
ü SVP求解ソフトのコンペティションである
SVP Challenge1にていくつかの記録を更新
ü 研究成果をまとめた論⽂はHPC分野のトップカンファレンスである SC20 に採択2

The International Conference for High Performance Computing, Networking, Storage, and Analysis

1https://www.latticechallenge.org/svp-challenge/

2Tateiwa, Nariaki, et al. "Massive parallelization for finding shortest lattice vectors based on ubiquity generator framework." 2020 SC20: International

Conference for High Performance Computing, Networking, Storage and Analysis (SC). IEEE Computer Society, 2020.

6研究内容MAP-SVP: the Massive Parallel Solver for Shortest Vector Problem
理論

格⼦アルゴリズム1.

既存のアルゴリズムの並列計算⽤拡張

2. 効率的な求解を実現するためのシステム設計

⽴教⼤学
安⽥研

ZIB研究所(ドイツ)
品野研究員

3. C++ / MPI によるソフトウェア実装

実装

⼤規模並列化技術

4. スパコンを⽤いた⼤規模実験と評価

九州⼤学
藤澤研
鍛冶研
7

最短ベクトル問題 (SVP)
格⼦(lattice)𝒏次元格⼦は, ⼀次独⽴な𝑛本のベクトル 𝐁 = 𝐛! , … , 𝐛" の整数係数による⾜し合わせで⽣成されるベクトルから構成される集合(網⽬)O$ℒ 𝐁 = $ 𝑎! 𝐛! ; 𝑎! ∈ ℤ𝐛"!"#

このとき𝐁 を 格⼦基底 と呼ぶ𝐛!
図: 2次元格⼦8

最短ベクトル問題 (SVP)
最短ベクトル問題
最短ベクトル問題は,の原点に最も近い格⼦点を求める問題
性質:• ある仮定のもとでNP-Hard• 格⼦の次元が⼤きくなるほど, 求解困難性が増⼤

最短ベクトルO

SVP

minimize 𝐯
subject to 𝐯 ∈ ℒ(𝐁) ∖ {𝟎}

𝐛"
𝐛!

$

ℒ 𝐁 = & 𝑎! 𝐛! ; 𝑎! ∈ ℤ!"#

図: 2次元格⼦と最短ベクトル9

最短ベクトル問題 (SVP)
最短ベクトル問題
最短ベクトル問題は,の原点に最も近い格⼦点を求める問題
性質:• ある仮定のもとでNP-Hard• 格⼦の次元が⼤きくなるほど, 求解困難性が増⼤

最短ベクトル?
OSVPminimize 𝐯
subject to 𝐯 ∈ ℒ(𝐁) ∖ {𝟎}

𝐛"
𝐛!

$

ℒ 𝐁 = & 𝑎! 𝐛! ; 𝑎! ∈ ℤ!"#

図: 2次元格⼦と最短ベクトル10代表的な格⼦アルゴリズム
DeepBKZ (近似的)
Oc!
c"

d!

OENUM (厳密的)

d"

d!

Od"

Sieve (確率的)
格⼦ベクトル
リスト

格⼦ベクトルサンプラー⋯

格⼦基底がなるべく直交に近くなるように⾏列の基本変形を⾏う

アルゴリズム
単体での並列化は?

• ⾼々200次元の⾏列の逐次的な⾏列変形であるため並列効果は極⼩

最短ベクトルを含む探索領域を⽊で表現し, 深さ優先探索を⾏う

サンプリングした格⼦ベクトル
同⼠の⾜し引きによりベクトルを短く変換する• 探索⽊の分割により, 並列数に対して線形の効果の並列化が可能• だが, もともと探索⽊が次元に対し指数的に極⼤なため, 探索できる範囲はそれでも極⼩• 共有メモリシステムでの並列⼿法の提案がある• が, 次元に対し指数的なサイズのベクトルの保持が必要なた
め, メモリ確保がボトルネックに11代表的な格⼦アルゴリズム
DeepBKZ (近似的)
O

c!
c"

d!

O

ENUM (厳密的)

d"

d!

Od"

Sieve (確率的)
格⼦ベクトル
リスト

格⼦ベクトル
サンプラー⋯

アルゴリズム単体の並列化だけでは,最短ベクトルを含む探索領域をサンプリングした格⼦ベクトル⽊で表現し, 深さ優先探索を⾏う
同⼠の⾜し引きにより⼤規模計算機を⼗分に活⽤できないベクトルを短く変換する

格⼦基底がなるべく直交に近くなるように⾏列の基本変形を⾏う

アルゴリズム
単体での並列化は?

• ⾼々200次元の⾏列の逐次的な⾏列変形であるため並列効果は極⼩• 探索⽊の分割により, 並列数に対して線形の効果の並列化が可能• だが, もともと探索⽊が次元に対し指数的に極⼤なため, 探索できる範囲はそれでも極⼩• 共有メモリシステムでの並列⼿法の提案がある• が, 次元に対し指数的なサイズのベクトルの保持が必要なた
め, メモリ確保がボトルネックに12格⼦の性質
格⼦基底のランダマイズℒ 𝐁 = ℒ 𝐔𝐁 ∀𝐔: ユニモジュラ⾏列(ℒ 𝐁 ≔ ∑$!"# 𝑎! 𝐛! ; 𝑎! ∈ ℤ )ランダマイズ

Oc"b"
d!

アル
ゴリズ
ムのの出
分⼒布解
最適解の推定値

/b!

c!

O

(

ユニモジュラ⾏列を基底に作⽤させても⽣成される格⼦は不変→ 無限個の異なる問題表現が可能• ⼊⼒基底が変わることで, アルゴリズムの挙動も変化• 例えば, 128個のランダム基底に対してDeepBKZを実⾏した場合アルゴリズムが⾒つけた最短ベクトルの⻑さにも下図のような, ばらつきが⾒られた

Od")

基底の次元

13

格⼦の性質格⼦アルゴリズムの副産物
格⼦アルゴリズムは, 最短ベクトルの探索の過程において• 最短ではないが⼗分短いベクトルなどの副産物が得られるが,それらをDeepBKZやENUMアルゴリズムに対し効果的に活⽤したSVP求解ソルバはなかった→ 活⽤するとどうなる?

発
⾒した
ベク
トルの個数

ベクトルノルム
図: DeepBKZアルゴリズムが実⾏中に発⾒する格⼦ベクトルの分布図

15

並列システム• ランダマイズによる, 別表現の問題の分配• 並列で競争的な実⾏• ⾮同期での格⼦ベクトルの共有によるアルゴリズムの加速求解プロセス A

ベクトルの共有

求解プロセス Bc"

ランダマイズ + 問題分配制御プロセス

格⼦ベクトルプールb!

Ob"

求解アルゴリズム

Oc!

探索空間の削減Od!

d"

求解アルゴリズム

求解プロセス COe!

e"

探索空間の削減

探索空間の削減
求解アルゴリズム16

並列システム
短いベクトル共有によるアルゴリズムの効率化
DeepBKZ (近似的)ENUM (厳密的)アルゴリズム内の⼀部サブルーチンを“外部から短いベクトルを取得する”ことでより, 基底ベクトルの直交化を促進できる→ アルゴリズムの強⼒化
OO!!

現在⾒つかっている最短ベクトルノルムを⽤いることで探索空間をより⼩さくできる→ 探索時間の削減

!"

!!

𝐚!"

OO!!

!"
vector 𝐚!!

!"

図: ENUMにおける探索領域削減のイメージ(探索領域を擬似的に円で表現)

17

実装
Ubiquity Generator (UG) Framework• 分枝限定B&Bソルバ(SCIP, CPLEX, Xpress, …)を外側から並列化する汎⽤分散並列ソフトウェア• 制御プロセス(LC)と複数のSolverから構成される• LCはSolverに渡す問題の分配と動的管理を⾏い,Solverは与えられた問題に対し基本的に独⽴に動作
hBps://ug.zib.de

UG framework
LoadCoordinator(LC)Loads are coordinated by a special process or thread

Base solver : Initiator
I/O , presolve(any) Base solver(any) Base solver
Using API to control
solving algorithms

Using API to control
solving algorithms

Using MPI or C++11
for communications

Using MPI or C++11
for communications

Using MPI or C++11
for communications

Using API to control
solving algorithms(any) Base solver

18

実装
UGを継承して SVP⽤の求解ソフトウェアを開発• UGの通信機能に加え, ベクトル共有の通信関数を追加
1. 管理プロセス(LC)はSolverにランダマイズ問題を分配(MPI)
2. Solverは問題を受け取りDeepBKZとENUMを実⾏
3. Solverは定期的にLCに短いベクトルの送受信を⾏う(MPI)

MAP-SVP
LoadCoordinator(LC)Loads are coordinatedby a special process or thread

SVP solver

Pool ofshort lattice vectors

SVP solver

Base solver : Initiator
I/O , presolve

SVP solver

Using API to control
solving algorithms

Using API to control
solving algorithms

Using API to control
solving algorithms

Using MPI or C++11
for communications

Using MPI or C++11
for communications

Using MPI or C++11for communications

19

The Darmstadt SVP Challenge
SVP求解ソフトウェアのコンペティション
𝜶-approximate SVP+inding𝐯 ∈ ℒ 𝐁 ∖ {𝟎}subject to 𝐯 ≤ 𝛼 𝜆# ℒ 𝐁
格⼦ℒ(𝐁)における最短ベクトルノルム
SVP Challengeでは• 𝜶 = 1.05
• 𝜆# ℒ 𝐁 : = GH
(最短ベクトルノルムの推定値)が使⽤される
次元ごとに記録が管理され
1. 上記の条件を満たし
2. 既存記録よりも短いベクトルであればサイトに登録される• 現在の最⾼記録は180次元の記録 (2021年2⽉8⽇).
ただ, 𝐯 ⁄ GH は1.04であり,最短ベクトルの発⾒には⾄っていない
20

計算機

以降の実験は下記の設定で⾏っている.
• MPIプロセスのみを使⽤.
• 1コアに1プロセスを割り当てる(ハイパースレッディング機能は使⽤しない).
• LC と Solver は1つのプロセスに割り当てる
21

SVP Challengeでの記録更新
複数の次元で記録を更新* † ベクトル取得のために,複数の計算機で複数回MAP-SVPを実⾏した. この表には,その中の最⼤のプロセス数とwall timeの合計値の概算を記載している.
† これらの解は新記録ではないが, 既存記録と同じ,もしくはそれに⼗分に近いものであるため記載した.

checkpoint and Restart

DeepBKZ
基底を保存

ENUM
探索ノードの保存

22

SVP Challengeでの記録更新
130次元の求解報告
130次元の現在記録はノルム2870, 近似係数 0.99413

23

数値実験
並列数の増加による性能向上••

Root Hermite Factor はDeepBKZなどの簡約アルゴリズムの質を測る資料!/"𝐛𝛾 !⁄" ≔vol 𝐿 !⁄"ここで 𝐛 は簡約アルゴリズムが出⼒する
最短ベクトル𝜸𝟏⁄𝒏 が⼩さいほど, より短いベクトルが発⾒できている
100,032プロセスでの⼤規模であっても性能向上(スケーラビリティ)は保たれている

1.01105RRt +HrmLtH )aFtRr•dLmHnVLRn 120# RI prRFHVV# RI prRFHVV# RI prRFHVV# RI prRFHVV# RI prRFHVV

1.01051 (Fal B + Fal C)
16 (Fal B + Fal C)
64 (Fal B + Fal C)
128 (Fal B + Fal C)
100,032 (+L51 ,9)

1.01001.00951.00901.0085
01000

2000

3000

4000

5000

6000

TLmH [V]図: 120次元のSVPに関する平均Root Hermite Factorの推移

24

数値実験
並列数の増加による推定計算時間の減少•ENUMアルゴリズムの探索⽊のサイズの推定式からENUMの探索時間を推定•

並列数が増加するほど,より強く探索空間を削減される•

実際に並列数が増加するほど,探索時間が減少していることを確認

図: 0.99の確率で最短ベクトルが求められる推定時間(ENUMアルゴリズムの探索時間から推定)
25

数値実験
コミュニケーションの⼩遅延
7Lme [s]startLC•••100
10−110−2

send / receivevectors

1632

wait idle 0me

100次元のSVPを1時間実⾏した場合の通信遅延の調査
プロセス数が増加するほどLCの負荷(メッセージの総送受信)も増加するが,⾮同期で通信するため, 局所的な集中は少ない
実際, 通信の遅延は1時間の実⾏時間に⽐べてはるかに少ない

486484104124

144

180 1024 2048
I72 I72

waLt LdOe tLme oI each soOver

10−17Lme [s]start idle 0me

10110−310−510−7108

1632

486484104

124

144

180 1024 2048
I72 I72

7otaO number oI communLcatLons between LC and 6oOvers

106
Count

Solverstart

distributes
instance

start LdOe tLme oI each soOver

102104
send102

receLve

1632486484

104

124

144

1umber oI Srocesses

180 1024 2048
I72 I7226

Conclusion• UGフレームワークをベースに新しいSVPソルバである初の⾮同期協調分散型システムMAP-SVPを開発した.
• 数値実験により MAP-SVPを⽤いて SVP Challenge において最⾼ 127 次元の記録の更新に成功した.
これは現状厳密解法アルゴリズムによるソルバで達成された最⼤次元の記録である.
• また, 130次元の求解において, 103,680 processでの並列実⾏に成功した

Future Work
• 本稿での研究成果を踏まえて，UG⾃体を分枝限定法以外のソルバも扱えるように汎⽤化し，MAP-SVPをスクラッチから再設計する• Solverが実⾏するアルゴリズムを柔軟に変えられるように変更→ HeterogeneousなSolverへ• 将来的に本稿のアルゴリズムを含むより強⼒なSolverのコードを公開する予定

27

学会, 研究会発表
国際学会• Tateiwa, N., Shinano, Y., Nakamura, S.,Yoshida, A., Kaji, S., Yasuda, M., & Fujisawa, K.
(2020, November). Massive parallelization forfinding shortest lattice vectors based onubiquity generator framework. In SC20:International Conference for High Performance
Computing, Networking, Storage andAnalysis (pp. 1-15). IEEE.

国内研究会• ⽴岩⻫明, 品野勇治, 吉⽥明広, 鍛冶静雄, 安⽥雅哉,& 藤澤克樹. (2020). 最短格⼦ベクトル問題求解における Ubiquity Generator Framework を⽤いた
⼤規模 MPI 並列化. 研究報告ハイパフォーマンス
コンピューティング (HPC), 2020(1), 1-10.

28