A Random Sampling Algorithm for SVP Challenge Based on y-Sparse Representations of Short Lattice Vectors

Author

Dan Ding ; Guizhen Zhu

Author_Institution

Dept. of Comput. Sci., Tsinghua Univ., Beijing, China

fYear

2014

fDate

15-16 Nov. 2014

Firstpage

425

Lastpage

429

Abstract

In this paper, we propose a novel random sampling algorithm for the shortest vector problem (SVP) based on the y-sparse representations of the short lattice vectors. The experimental results show that the random sampling algorithm outperforms the other two SVP algorithms under the benchmarks of SVP challenge[1]. Therefore, the random sampling algorithm is an efficient SVP solver for the shortest vector problem.

Keywords

cryptography; random processes; sampling methods; vectors; SVP algorithms; SVP solver; lattice-based cryptography; random sampling algorithm; short lattice vectors; shortest vector problem; y-sparse representations; Algorithms; Complexity theory; Cryptography; Lattices; Polynomials; Vectors; Lattice-Based Cryptography; Random Sampling; Shortest Vector Problem (SVP); y-Sparse Representation;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Intelligence and Security (CIS), 2014 Tenth International Conference on

Conference_Location

Kunming

Print_ISBN

978-1-4799-7433-7

Type

conf

DOI

10.1109/CIS.2014.31

Filename

7016931

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=234912