Paper 2016/950
Orthogonalized Lattice Enumeration for Solving SVP
Zhongxiang Zheng, Xiaoyun Wang, Guangwu Xu, and Yang Yu
Abstract
In 2014, the orthogonalized integer representation was proposed independently by Ding et al. using genetic algorithm and Fukase et al. using sampling technique to solve SVP. Their results are promising. In this paper, we consider sparse orthogonalized integer representations for shortest vectors and propose a new enumeration method, called orthognalized enumeration, by integrating such a representation. Furthermore, we present a mixed BKZ method, called MBKZ, by alternately applying orthognalized enumeration and other existing enumeration methods. Compared to the existing ones, our methods have greater efficiency and achieve exponential speedups both in theory and in practice for solving SVP. Implementations of our algorithms have been tested to be effective in solving challenging lattice problems. We also develop some new technique to reduce enumeration space which has been demonstrated to be efficient experimentally, though a quantitative analysis about its success probability is not available.
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint. MINOR revision.
- Keywords
- Lattice-basedSVPsparse representationsenumerationBKZ
- Contact author(s)
- zhengzx13 @ mails tsinghua edu cn
- History
- 2017-02-20: revised
- 2016-10-01: received
- See all versions
- Short URL
- https://ia.cr/2016/950
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/950,
author = {Zhongxiang Zheng and Xiaoyun Wang and Guangwu Xu and Yang Yu},
title = {Orthogonalized Lattice Enumeration for Solving {SVP}},
howpublished = {Cryptology {ePrint} Archive, Paper 2016/950},
year = {2016},
url = {https://eprint.iacr.org/2016/950}
}
