平成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 ]