基于LWE问题的采样算法及应用研究

摘要

随着量子计算研究的不断发展，量子计算机的出现将不再是空谈，因此研究出能够抵御量子攻击的新型密码体制成为了研究热点。而格上的很多问题被证明是困难的，是通过量子计算在多项式时间内也无法求解的，因而很多密码体制的设计都是基于格上的困难问题。带错误学习问题(Learning with error，LWE)是格上的困难问题之一，通过LWE问题构造的密码体制在安全性上可以得到保证。而对LWE问题的采样效率关系到对应的密码体制的应用效率，基于这一问题，本文对LWE问题的采样算法进行了研究。在LWE问题中，对错误因子的采样占用了绝大部分的时间，并且使用的采样算法灵活多变，是研究LWE问题采样的主要内容。对LWE问题中错误因子的采样是从离散高斯分布上采样获得的，因此对离散高斯分布上的采样算法研究成为了本文的研究重点。
　　本文以设计出高效的新型LWE问题采样算法为目标，首先对现有的LWE问题采样算法进行了研究，通过对算法的实现发现了现有算法中综合性能最好的离散金字塔(Ziggurat)高斯采样算法，因此对该算法进行了深入研究。基于将格上的采样转化为整数域上的采样这一思路，本文提出了一种新的LWE问题采样算法，在该采样算法中，对整数域上的离散高斯分布采样过程进行了优化，并与现有最优算法离散金字塔采样算法进行了效率比对，发现本文提出的优化改进算法比离散金字塔采样算法的采样速度快了2倍。
　　A-LWE（Augmented Learning with Errors）问题作为LWE问题的扩展问题，增加了信息嵌入的功能，因此基于A-LWE问题的安全加密方案相较已有基于LWE问题的安全加密方案更有研究价值。本文将新的LWE问题采样算法应用在了基于A-LWE问题的安全加密方案中，通过实验表明，在安全加密方案中，使用新的LWE问题采样算法比使用已有的采样算法，在实现速度上提升了10％-20％。

目录

声明

致谢

摘要

序言

1．1 研究背景及意义

1．2 研究现状及发展趋势

1．3 主要研究内容和工作

1．4 本文的内容安排

2 基本概念

2．1 数学符号说明

2．2 格的基本概念

2．3 LWE问题

2．4 高斯分布

2．4．1 离散高斯分布

2．4．2 格上的离散高斯分布

2．5 基本的高斯采样算法

2．5．1 CDF取反采样算法

2．5．2 转换采样算法

2．5．3 拒绝采样算法

2．5．4 递归算法

2．6 Ziggurat采样算法

2．7 统计距离

2．8 计算离散高斯分布

2．9 A-LWE问题

2．9．1 消息嵌入

2．9．2 A-LWE问题内容

2．9．3 一般的基于A-LWE问题的加密方案

2．10 CCA安全

2．11 本章小结

3 现有LWE问题的采样算法研究

3．1 LWE采样算法

3．1．1 rejSam拒绝采样算法

3．1．2 invCDF取反采样算法

3．1．3 离散Ziggurat采样算法

3．1．4 Knuth-Yao算法

3．1．5 二分采样算法

3．1．6 D采样算法

3．2 LWE采样算法性能比对

3．3 现在LWE采样算法性能分析

3．4 本章小结

4 一种新的LWE问题的采样算法

4．1 新的采样算法内容

4．1．1 格上的离散高斯分布采样算法

4．1．2 采样算法证明

4．2 采样算法分析

4．3 改进的格上离散高斯分布采样算法

4．4 实验内容及结果

4．4．1 实验参数选择

4．4．2 实验环境

4．4．3 实验结果

4．5 新的LWE采样算法性能分析

4．6 本章小结

5 新的LWE采样算法应用在基于A-LWE问题的加密方案

5．1．1 CCA1安全加密方案

5．1．2 加密方案中的高数据负载加密

5．1．3 LWE采样算法应用在CCA安全加密方案

5．2 应用在非对称认证加密方案

5．2．1 非对称认证加密方案

5．2．2 LWE采样算法应用在非对称认证加密

5．3 应用在优化对称加密方案

5．3．1 优化对称加密方案

5．3．2 LWE采样算法应用在优化对称加密方案

5．4 本章小结

6．1 本文工作总结

6．2 未来工作展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集