Observations on Random Sampling Reduction Algorithms

Abstract:Development of efficient solvers of the (approximated) shortest vector problem over lattices is an important research area because the security of lattice-based schemes is based on the hardness of the shortest vector problem. (Random) sampling reduction is an approach to construct efficient solvers of the shortest vector problem by combining lattice basis reduction and sampling of short lattice vectors. In this talk, we show our observations on random sampling reduction algorithms, and recently proposed our probabilistic analysis framework (IACR ePrint 2018/815).

Note:This is revised version to fix several typos.To make the slide easier to read, three correlation heatmaps are uploaded separately.