北京交通大学学报2017，Vol.41Issue(5)：32-36,5.DOI:10.11860/j.issn.1673-0291.2017.05.005
一种基于LWE采样算法的实现与优化
Realization and optimization of a LWE sampling algorithm
摘要
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.关键词
格/带错误学习问题/高斯分布/错误因子/采样Key words
lattice/learning with errors/Gaussian distribution/error factor/sampling分类
信息技术与安全科学引用本文复制引用
王柯翔,黎琳,彭双和..一种基于LWE采样算法的实现与优化[J].北京交通大学学报,2017,41(5):32-36,5.基金项目
国家自然科学基金青年基金项目(61402035) （61402035）
中央高校基础科研业务费专项资金(2014JBM033)National Natural Science Foundation of China(61402035) （2014JBM033）
Fundamental Research Funds for the Central Universities(2014JBM033) （2014JBM033）
