Cryptology ePrint Archive: Report 2016/950

Orthogonalized Lattice Enumeration for Solving SVP

Zhongxiang Zheng and Xiaoyun Wang and 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.

Category / Keywords: Lattice-based, SVP, sparse representations, enumeration, BKZ

Date: received 30 Sep 2016, last revised 19 Feb 2017

Contact author: zhengzx13 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20170220:010641 (All versions of this report)

Short URL: ia.cr/2016/950

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]