一种基于LWE采样算法的实现与优化
王柯翔
黎琳
彭双和
1.北京交通大学计算机与信息技术学院,北京,1000442.北京交通大学计算机与信息技术学院,北京,1000443.北京交通大学计算机与信息技术学院,北京,100044
摘要：基于带错误学习问题(Learning With Errors,LWE)构造的密码体制能够抵御量子攻击,它的应用效率与LWE问题的采样过程密切相关.而在LWE问题采样中,对其中的错误因子(Error Factor)采样占采样过程绝大部分时间,本文对LWE问题中的错误因子的采样算法进行研究,将在高斯分布上效率较高的金字塔(Ziggurat)采样算法,应用到了一种高效的LWE问题采样算法中.基于在连续域上的采样比离散域上采样效率高的思路,对LWE问题采样算法在离散域上采样的过程进行了优化,提出了一种将连续域上的采样结果进行取整的方法,.对优化前后的两种LWE问题的采样算法进行了对比实验,结果表明:改进后的算法在不占用大量内存并且保证安全性的情况下,将采样速度提高了38％～200％.
关键词：格带错误学习问题高斯分布错误因子采样
分类号：TP309(计算技术、计算机技术)
资助基金：国家自然科学基金青年基金项目(61402035)中央高校基础科研业务费专项资金(2014JBM033)National Natural Science Foundation of China(61402035)Fundamental Research Funds for the Central Universities(2014JBM033)
论文发表日期：2017-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：5( 32-36 )
英文信息