基于模容错学习问题的加密算法研究

论文摘要

量子计算机发展迅速,如果量子比特位数足够多,量子Shor算法能在多项式时间内破解整数分解与离散对数问题,所有基于两类问题的传统密码体制将不安全。当前已知最好的量子算法破解格上困难问题需要花费指数时间,格密码有望应对量子计算机与量子算法的攻击,因此格密码成为了当前信息安全界的研究热点。基于MLWE的密钥交换算法Kyber是当前最新的格加密算法之一,加密效率远高于基于LWE问题与RLWE问题构建的加密算法。但由于该算法主要应用于密钥封装少数场景,所以存在明文空间小,密文膨胀率较大的缺点。论文第一部分工作针对Kyber算法存在的问题进行了改进:在Kyber加密算法中引入新的加密参数dp,以扩大明文空间,降低密文膨胀率。在改进过程中主要解决了以下三个关键问题:1.通过严格的理论推导与实现分析了dp对加密算法正确性的影响。2.通过优化加密参数降低了密文膨胀率。3.通过基于浮点运算的复数域上的快速傅里叶变换进行多项式乘法,避免了在增大后的有限域上进行大整数多项式乘法,保证了改进后算法的计算效率,并对浮点运算产生的误差进行了分析。并且用C++实现了改进后的算法,与Kyber的实验数据进行对比,密文膨胀率由1:25左右降低到了1:4.25左右。同态内积在安全多方几何计算、隐私数据挖掘、外包计算、可排序的密文检索等场景有广泛的应用。但现有的计算同态内积的方案大多是基于RLWE的全同态加密方案,普遍存在效率不高的问题。针对上述问题,论文的第二部分工作是基于改进后的算法构造了一种基于MLWE的同态内积方案,在此过程中主要解决了以下三个关键问题:1.给出了密文空间上的张量积运算?,该密文空间上的运算对应明文空间上的整数向量内积运算。2.由于引入了张量运算,同态内积方案的加密噪声相比第一部分工作提出的改进算法发生了改变,重新对方案的正确性与安全性进行了分析。3.给出了两种优化的加密参数,对应计算两种不同大小的整数向量同态内积的应用场景。通过C++与大整数计算库NTL实现了本文的方案,对比其他同态加密方案,该方案能够高效地计算整数向量的同态内积。

论文目录

• 摘要
• abstract
• 第1章 引言
•   1.1 研究背景与意义
•   1.2 研究现状
•     1.2.1 格密码的研究现状
•     1.2.2 同态内积的研究现状
•   1.3 论文内容及组织结构
•     1.3.1 论文内容和创新点
•     1.3.2 论文组织结构
• 第2章 相关理论概述
•   2.1 基础符号说明
•   2.2 格与格上困难问题
•     2.2.1 格的基本概念
•     2.2.2 格上困难问题
•   2.3 格上容错学习问题概述
•     2.3.1 LWE（Learning with errors）问题
•     2.3.2 RLWE（Ring Learning with errors）问题
•     2.3.3 MLWE（Module Learning with errors）问题
•     2.3.4 BKZ攻击
•   2.4 同态加密概述
•   2.5 快速傅里叶变换（Fast Fourier Transform）
•   2.6 独立同分布的中心极限定理
•   2.7 本章小结
• 第3章 基于MLWE的低膨胀率加密算法
•   3.1 预备知识
•     3.1.1 中心二项分布
•     3.1.2 压缩技术（Compress）与解压缩技术（Decompress）
•   3.2 Kyber算法的改进
•     3.2.1 Kyber密钥封装算法
•     3.2.2 对Kyber算法的改进
•     3.2.3 新参数dp对噪声的影响
• q上多项式乘法'>    3.2.4 R_q上多项式乘法
•     3.2.5 密文膨胀率与dp的关系
•     3.2.6 参数优化与正确性证明
•     3.2.7 安全性证明
•   3.3 基于浮点运算的多项式乘法
•     3.3.1 多项式乘法的实现
•     3.3.2 算法的计算复杂度
•     3.3.3 浮点计算的误差
•   3.4 算法实例
•   3.5 实验结果
•   3.6 本章小结
• 第4章 一种基于MLWE的同态内积方案
•   4.1 同态内积方案
•   4.2 通过多项式乘法计算向量内积
•   4.3 通过密文空间张量运算计算同态内积
•   4.4 方案正确性与优化参数
•   4.5 方案安全性
•   4.6 方案计算复杂度
•   4.7 基于MLWE的同态内积方案实例
•   4.8 实验结果
•   4.9 方案适用场景
•   4.10 本章小结
• 第5章 结论与展望
•   5.1 结论
•   5.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间从事的科研工作及取得的成果

文章来源

类型: 硕士论文

作者: 柯程松

导师: 冯勇

关键词: 后量子加密算法,格密码,同态内积

来源: 重庆邮电大学

年度: 2019

分类: 基础科学,信息科技

专业: 物理学,电信技术

单位: 重庆邮电大学

分类号: O413;TN918.4

DOI: 10.27675/d.cnki.gcydx.2019.000767

总页数: 80

文件大小: 2491K

下载量: 59