文章基本信息

标题：Finding a Very Short Lattice Vector in the Extended Search Space
本地全文：下载
作者：Masaharu Fukase ; Kazunori Yamaguchi
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2012
卷号：7
期号：3
页码：1062-1072
DOI：10.11185/imt.7.1062
出版社：Information and Media Technologies Editorial Board
摘要：The problem of finding a lattice vector approximating a shortest nonzero lattice vector (approximate SVP) is a serious problem that concerns lattices. Finding a lattice vector of the secret key of some lattice-based cryptosystems is equivalent to solving some hard approximate SVP. We call such vectors very short vectors (VSVs). Lattice basis reduction is the main tool for finding VSVs. However, the main lattice basis reduction algorithms cannot find VSVs in lattices in dimensions ∼200 or above. Exhaustive search can be considered to be a key technique toward eliminating the limitations with current lattice basis reduction algorithms. However, known methods of carrying out exhaustive searches can only work in relatively low-dimensional lattices. We defined the extended search space (ESS) and experimentally confirmed that exhaustive searches in ESS make it possible to find VSVs in lattices in dimensions ∼200 or above with the parameters computed from known VSVs. This paper presents an extension of our earlier work. We demonstrate the practical effectiveness of our technique by presenting a method of choosing the parameters without known VSVs. We also demonstrate the effectiveness of distributed searches.
关键词：lattice;approximate SVP;exhaustive search;enumeration