平成28年3月 先端暗号フロンティアセミナー アブストラクト

高木 剛
題名:格子基底縮約アルゴリズムBKZの改良について
アブストラクト: ポスト量子暗号として注目を集めている格子暗号は、 格子上で最短ベクトルを求める問題(SVP)の困難性を 安全性の根拠としている。SVPを効率的に解く計算法 として、格子基底縮約法(LLL,BKZ),列挙法(Extreme pruning),篩法(Gauss sieve)などが知られている。 本講演では、BKZアルゴリズムを高速化する手法を 解説した後に、ドイツ・ダルムシュタット工科大学 が主催するSVP Challengeの解読世界記録を紹介する。 SVP Challengeの解読データにより、攻撃者の計算 限界を評価することができ、格子暗号で用いる安全 なパラメータを選択することが可能となる。
キーワード: 格子暗号、格子基底縮約アルゴリズム、BKZアルゴリズム、ダルムシュタット格子解読問題

The 7th Meeting for Cryptology Frontier Group Abstract

Tsuyoshi Takagi
Title: Improvement on BKZ Lattice Reduction Algorithm
Abstract: The security of lattice-based cryptography is based on the hardness of finding a short vector in the underlying lattice. Currently the most efficient algorithms for solving this problem in random lattices of large dimensions are perhaps the BKZ algorithm and its modifications. In this talk, we investigate a variant of BKZ algorithm, called progressive BKZ, which performs the BKZ reduction starting from the small block size and switches to larger ones so that the total cost used for the local enumeration algorithm is minimized. We discuss how to accelerate the speed of the progressive BKZ algorithm for optimizing the parameters: the block size, the search radius and probability of the local enumeration algorithm, and the successive sizes of Gram-Schmidt orthogonal basis known as geometric series assumption. Using our improved progressive BKZ we have solved the ideal lattice challenge from Darmstadt in 2^20.7 and 2^24.0 seconds on a standard PC for 600 and 650 dimensions, respectively.
Keywords: Lattice-based cryptography, Lattice reduction algorithm, BKZ algorithm, Darmstadt lattice challenge

[Back ]