格子暗号の安全性は最短べクトル問題(SVP)の困難性に基づいている.2010年にMicciancio等によって高速なSVPの求解アルゴリズムであるGaussSieveアルゴリズムが提案され，2011年にMilde等によってGaussSieveァルゴリズムの実装の並列化手法が提案された.しかし，Milde等の実装手法では並列度を上げるにつれ処理するべクトルの数が増大してしまい，効率的ではなかった.そこで本稿では，処理するベクトルの数が増大せず，高い並列度においても効率的な並列GaussSieveアルゴリズムを提案する.また，提案アルゴリズムをCPU, GPU上で実装し評価を行い，8コアのCPU, 2台のGPUを用いて従来のアルゴリズムの約60倍の高速化を達成した.%Security of lattice-based cryptosystems is based on the hardness of the Shortest Vector Problem (SVP) in lattices. Micciancio et al. proposed a GaussSieve algorithm for solving the SVP in 2010. In 2011, Milde et al. proposed a parallel implementation method for the GaussSieve algorithm. The algorithm is not effective for large numbers of threads, since the number of vectors in order to find a shortest vector is increased according to the increase of the threads. In this paper, we propose a more efficient and practical parallelized GaussSieve algorithm. Our algorithm requires few additional vectors for the parallelization. We implement the parallelized GaussSieve algorithm on a PC that has a 8-core CPU and 2 GPUs. Our experimental results demonstrate that the algorithm achieves a processing speed, which is 50 times faster than that of the original GaussSieve implementation.
展开▼
