Realization and optimization of a LWE sampling algorithm
WANG Kexiang
LI Lin
PENG Shuanghe
Abstract：The crypto system constructed with Learning With Errors (LWE) can resist quantum attacks,and its application efficiency is closely related to the sampling process of LWE problem.In the LWE problem sampling,the error factor sampling which accounted for most of the sampling process.This paper studies the sampling algorithm of the error factor in the LWE problem,and applies the Gaussian distribution (Ziggurat) sampling algorithm to an effective sampling algorithm of the LWE problem.Based on the idea of high sampling efficiency on the sampling domain in the continuous domain,this paper deals with the LWE problem sampling algorithm on the discrete domain.The sampling process is optimized,and a method of rounding the sampling results in the continuous domain is proposed and applied to the LWE problem sampling algorithm.We have compared the two LWE sampling algorithms before and after optimization.The experimental results show that the improved algorithm increases the sampling speed by 38％ ～ 200％ in the condition of not using a lot of memory and ensuring the safety of sampling.
Keywords：latticelearning with errorsGaussian distributionerror factorsampling
Publication Date：2017-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：5( 32-36 )