ポスターファイル

格子基底縮約を用いたLWE問題の解法
工藤 桃成
九州大学大学院数理学府 博士後期課程
[email protected]
LWE 問題 [Regev09]
情報セキュリティを支える暗号技術
暗号はネットワーク上の情報漏洩を防ぐための最適な
技術で, 現在広く普及している
通信ネットワーク
・個人情報
・秘密
・人
・企業
・国家
暗号化により
安心して通信可能
𝐬, 𝐴, 𝐞 から 𝐭 を生成
するのは簡単だが,
𝐴, 𝐭 のみから 𝐬 を求
めるのは難しい
与えられた 𝐴, 𝐭 から secret vector 𝐬 を求めよ
格子基底縮約に基づく鍵復元 [LL15]
悪い人
しかし現在, 様々な暗号解読の技術が進展
頑強な暗号技術の開発が常に必須
暗号技術と数学
暗号文からメッセージが復元されないように（一方向性）,
数学問題の計算量困難性を利用
暗号文
暗号化
41115102
悪意ある復元
の阻止
𝑞 : 奇素数, 𝑛, 𝑑 ∈ ℕ,
ℤ𝑞 ≔ ℤ ∕ 𝑞ℤ,
𝐬 ∈ ℤ𝑛𝑞 : secret vector* （縦ベクトル）,
𝑑×𝑛
𝐴 = 𝑎𝑖,𝑗 ∈ ℤ𝑞 : 𝑑 × 𝑛 行列*,
𝐞 = 𝑒𝑖 ∈ ℤ𝑑 : error vector*,
𝑑
𝐭 = 𝐴𝐬 + 𝐞 ∈ ℤ𝑞 : sample vector.
* 𝐬, 𝐴 は一様分布に従い選ばれ, 𝐞 の各成分は正規分布に従い独立に選ばれる
・クラッキング
・情報漏洩
メッセージ
（格子暗号の安全性を支える数学問題の1つ）
LWE に関する近年の研究として, 鍵復元 [LL15] があり, 高確率かつ
実用的な時間（多項式時間）で解ける
〇鍵復元 [LL15] のスケッチ
𝐚𝑖 ≔ 𝑎𝑖,1 , 𝑎𝑖,2 , … , 𝑎𝑖,𝑛 （𝑖 = 1, … , 𝑑）,
仮定： 𝐚𝑖 , 𝐬 + 𝑒𝑖 mod 𝑞 = 𝐚𝑖 , 𝐬 mod 𝑞 + 𝑒𝑖 in ℤ.
𝐛1 ≔ 𝑞, 0, … , 0, 0 , 𝐛𝑑+1 ≔ 𝑎1,1 , … , 𝑎𝑑,1 ,
⋯
⋯
𝐛𝑑 ≔ 0, 0, … , 0, 𝑞 , 𝐛𝑑+𝑛 ≔ 𝑎1,𝑛 , … , 𝑎𝑑,𝑛 ,
ℒ≔
⇒ 𝐯
, 𝐯≔
𝐚1 , 𝐬 , … , 𝐚𝑑 , 𝐬
∈ ℒ.
𝐭 と最も近い格子点となる
最近ベクトル問題（Closest Vector Problem, CVP）に帰着
CVP 解法の例: [Babai86] による
・BN; Nearest Plane Algorithm （精度：高, 効率：低）,
・BR; Rounding Technique
（精度：低, 効率：高）.
悪い人
現代暗号では, 整数論・代数幾何（楕円曲線）, 格子理論,
符号理論などの数学理論が応用されている
𝑑+𝑛
𝑖=1 𝑙𝑖 𝐛𝑖 𝑙𝑖 ∈ ℤ
𝑑
は, ℝ において,
格子 ℒ
格子点 𝐯
ℒ の縮約基底
格子基底縮約
（LLL reduction [LLL82]）
CVP 求解アルゴリズム
（Nearest Plane algorithm）
内積 𝐚𝑖 , 𝐬 の値 （𝑖 = 1, … , 𝑑）から 𝐬 が復元される
実験結果と考察
[LL15]の方法に加え, BR アルゴリズムを取り入れた
**表：𝒏 = 𝟖𝟎, 𝒅 = 𝟐𝟓𝟓 における攻撃結果と攻撃に要した時間
**EV： Magma V2.21-3 [BCP97], Mac OS X 64 bit. 2.60 GHz CPU (Intel Core i5) and 16 GB memory.
格子暗号
 格子＝規則正しく整列された点の
集まり（右図の点の集合）
 格子暗号の安全性は,最短ベクト
ル問題（Shortest Vector Problem）
などの求解困難性に基づいている
 最短ベクトル問題とは, 最も短い格
子の点を探索する問題
 近年, LWE（Learning with Errors）と呼ばれる特殊な
格子を利用した格子暗号が数多く提案されている
[Babai86] L. Babai, On Lovász lattice reduction and the nearest lattice point problem,
Combinatorica 6 (1), 1-13 (1986).
[BCP97] W. Bosma, J. Cannon, and C. Playoust : The Magma algebra system. I. The user language,
Journal of Symbolic Comput. 24, pp. 235-265 (1997).
[LL15] K. Laine and L. Lauter, Key recovery for LWE in polynomial time, IACR Crypto. ePrint Archive 2015/176.
[LLL82] A.K. Lenstra, H.W. Lenstra, L. Lovász: Factoring polynomials with rational coefficients,
Mathematische Annalen 261 (4), 515-534 (1982).
[Regev09] O. Regev: On lattices, lerning with errors, random linear codes, and cryptography,
Journal. of the ACM 56 (2009).
log 2 𝑞
LLL+BN
[LL15]
LLL+BR
15
false
250s
false
4s
20
25
30
35
40
45
50
success success success success success success success
1800s 3700s 5700s 8500s 11000s 12500s 14250s
false
false
false success success success success
550s
1300s 2700s 5000s 7000s 8200s 9400s
安全
脆弱
 LLL+BN [LL15] は log 2 𝑞 ≥ 20 に対して成功（精度：高）
 LLL+BR は log 2 𝑞 ≥ 35 に対して成功（効率：高）
格子暗号を利用する上で, 避けるべきパラメータ 𝑞 が判明
今後の研究・展開
新しい攻撃手法を研究し, 頑強な格子暗号の構築に貢献
することを目指す
実用化・普及（将来）
格子暗号の安全性を
数学問題の解析・評価
※今回の研究
feedback
頑強な格子暗号
の構築
新しい解法
（攻撃）の発見
今後の研究