Gaussian sampling of lattices for cryptographic applications

Gaussian sampling is the major class of algorithms for solving the close vector problem (CVP) of lattices. In this paper we present a novel Gaussian sampling algorithm, which has the same cryptographic applications with original Gaussian sampling algorithms. Our novel Gaussian sampling algorithm has smaller deviations, meaning smaller space sizes of lattice based public-key ciphers. The shape of our novel algorithm is almost repeated implementations of original algorithm, with random repeating times. Major result is that the deviation can be reduced to 0.64 ～ 0.75 of that of original Gaussian sampling algorithm without clearly increasing the average time cost.