| 高木 剛 |
| 題名: 並列ガウス篩アルゴリズム：128次元イデアル格子の最短ベクトル問題の求解 |
| アブストラクト:
次世代公開鍵暗号として注目を集めている格子暗号では、暗号化した
状態にて論理演算が可能となるなどプライバシー保護を考慮した秘匿
通信が実現できる。格子暗号の安全性は、最短ベクトル問題(SVP)の
困難性に基づいている。本講演では、最新のSVPの大規模解読実験デー
タも含め、格子暗号の安全性評価方法に関する簡単なサーベイを行う。
特に、2010年にMicciancio等によって提案されたSVPの高速求解法で
あるガウス篩アルゴリズムの並列化を考察する。複数の初期ベクトル
を同時に計算可能なガウス縮約リストを用いて、数千個のスレッドに
よる並列化が実現できるアルゴリズムを提案する。その結果、ダルム
シュタット工科大が主催するのイデアル格子チャレンジの最高記録と
なる128次元のイデアル格子上の最短ベクトル問題を、約3万CPU時間
で解くことに成功した。
キーワード：最短ベクトル問題、格子暗号、イデアル格子、ガウス篩、並列計算 |
| Tsuyoshi Takagi |
| Title: Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice |
| Abstract: Lattice-based cryptography allows us to compute logic operations
in the encrypted data, and it provides us many privacy-preserving
cryptographic protocols. The security of lattice-based cryptography
is based on the hardness of solving the shortest vector problem (SVP)
in lattices. In this talk, we give a short survey of the security
analysis of lattice-based cryptography including recent records of
solving SVP via large-scaled experiments. In particular, we deal
with the parallelization of the Gauss Sieve algorithm proposed by
Micciancio and Voulgar in 2001. We propose a practical parallelized
Gauss Sieve algorithm for large dimensions with a small communication
overhead. We succeeded in solving the SVP Challenge from TU Darmstadt
over a 128-dimensional ideal lattice generated by the cyclotomic
polynomial x^128+1 using about 30,000 CPU hours.
Keywords: shortest vector problem, lattice-based cryptography, ideal lattice, Gauss Sieve algorithm, parallel algorithm |