英语原文共 6 页
Ring-LWE加密的高效软件实现
Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede KU Leuven, Department of Electrical Engineering - ESAT/COSIC and iMinds, Belgium
firstname.lastname@esat.kuleuven.be
摘要
而今，随着量子计算机成为现实，公钥加密，如RSA和ECC已经变得不再安全。本文介绍了基于Ring-LWE难题的后量子公钥加密方案的高效软件实现的最新进展。本项目使用32位的ARM Cortex-M4F微处理器作为目标平台，实现了包括快速离散高斯抽样和高效多项式乘法的优化技术。本实现方案比所有已知的Ring-LWE公钥加密方案的软件实现至少高效七倍以上。而且，进一步地证明了，本方案至少比基于ECC的公钥加密方案高一个数量级。对于中期安全性，要求每次加密121166个周期，每次解密43324个周期。而对于长期安全性，要求每次加密2619939个周期，每次解密96 520个周期。高斯抽样是在平均每个样本28.5个周期的情况下进行的。
关键词：误差环学习(ring-LWE)，软件实现、后量子安全、公钥加密、离散高斯抽样、数论变换
- 引言
本项目目前的公钥密码方案是基于数论问题，例如因子分解或离散对数来提供数字签名、密钥交换和机密性。在密钥足够大的情况下，这些公钥密码系统在当今的计算机、超级计算机和特殊硬件集群中实际上是不可攻破的。1994年Peter Shor提出了整数因子分解的量子算法[1]。改进的Shor算法可以解决椭圆曲线上的离散对数问题(ECDLP)。但是肖尔的算法不能在经典计算机上使用，只能在功能强大的量子计算机上执行，在多项式时间内解决因式分解或离散对数问题。在这十年中，学界为了开发强大的量子计算机不断进行重大的研究。因此，当量子计算机成为现实时，必须使用高效的量子安全公钥算法。
带误差学习问题及其有效环变量与格上已知的最坏情况问题有关，因此被认为在后量子世界是安全的。本文描述了一种基于Ring-LWE难题[2]的加密方案的高效软件实现。Ring-LWE加密方案计算量大，采用多项式算法和离散高斯采样作为基元函数。大型多项式的加减运算很容易实现，而高效的设计决策是实现多项式乘法的关键。同样的，一个有效的离散高斯采样器可以提高加密的性能。
近年来，有几个基于Ring-LWE难题的实际运用被公布。第一个实现[3]包括一个基于硬件的体系结构和一个高级软件实现。它使用了一个基于数论变换(NTT)的多项式乘法器和一个拒绝采样器。而且在[4]、[5]、[6]、[7]、[8]中更高效的硬件实现减少了对面积和时间的要求。虽然存在基于Ring-LWE加密方案的几个高级软件实现[3]、[9]，但是在资源受限的微控制器[10]、[11]、[12]上却很少有有效的软件实现。人们的日常生活被这些设备所充满，它们的相互联系变得越来越多，尤其是通过互联网。这引起了人们对安全问题关注，因为这些设备处理敏感信息，有时对人类生命的安全至关重要。
本项目的成果:本文介绍了ARM Cortex-M4F单片机上的Ring-LWE加密方案的实现，设计目标包括高速和低内存消耗。本项目的成果如下:
1)快速离散高斯采样:本项目使用Knuth－Yao采样算法实现了一个快速离散高斯采样器，研究了基于单片机结构的加速技术来改进采样器。该平台内置的真随机数生成器(TRNG)用于生成随机数。在高斯分布中最常用的区域使用查找表来加速采样算法，这允许本方案以平均每个样本28.5个周期进行抽样。
2)高效多项式乘法:本方案使用负包装的NTT和[7]的计算优化来实现多项式乘法。该体系结构的大字长用于在每个处理器字中存储多个乘法系数，并且基本的负包装迭代NTT算法的展开系数为2。这减少了50%的内存访问和循环开销，证明了一个256个元素的多项式乘法可以在108147个循环中完成。
论文组织如下。首先，提供一个数学背景来帮助读者理解这篇论文。接下来，讨论实现细节，分析了标准算法的瓶颈，并针对目标平台提出了解决方案。然后，提出了本项目的结果，最后得出结论。
- 数学背景
在这一节中，本项目提供了可能对读者有帮助的一个简短的数学概述和相关的参考资料。
- Ring-LWE 加密体系
在Ring-LWE问题中 [13]，两个多项式和被均匀地从一个多项式环中选取，是一个次的不可约多项式。从误差分布中采样次误差多项式。误差分布通常是一个离散高斯分布标准差。Ring-LWE分布，覆盖由元组(a、t)在中移动。即使给定了，的样本对的多项式个数，也是很难找到的。这个问题被称为搜索Ring-LWE问题。在[2]中提出了一种基于环路问题的加密方案。在本文中，使用了一种高效的加密方案[7] 最小化复杂的NTT操作的数量。本文用表示NTT的多项式。
- 密钥产生:两个多项式和从使用离散高斯采样器采样。执行以下计算。
私钥为和公钥为
- 加密:输入消息是一个多项式编码中移动。错误多项式通过使用离散高斯采样器生成。下面的计算执行计算密文离散高斯抽样。
- 解密:通过执行逆NTT计算。使用解码器从中恢复原始消息。
本项目使用来自于[3]的参数设置，即和其分别是中期和长期安全。
- 离散高斯分布
Ring-LWE密码系统在密钥生成和加密过程中需要离散高斯分布的样本来构造错误多项式。离散高斯分布的采样方法有很多种，其中最著名的技术是拒绝抽样、反转抽样和随机位模型。采样算法效率(时间和空间)取决于分布的标准差，在[14]中可以找到对采样算法的详细比较分析。本项目使用Knuth-Yao算法[15]对离散高斯分布进行采样。Knuth-Yao算法基于随机比特模型，平均使用接近最优的随机比特数。该算法需要存储样本点的概率。Ring-LWE加密方案中较小的标准差意味着微控制器对内存的需求较小，很容易满足。
尾部和精度边界:离散高斯函数的尾部是无限长的，概率值具有无限大的精度。因此想要实际的实现，就需要一个尾部和精度约束的位安全性。通过使用足够大的精度和尾部边界[14],[6]保持最大统计距离真正的分布。
- 多项式乘法
对于大型多项式乘法，由于其复杂度为，快速傅里叶变换(FFT)被认为是最快的算法。在本文中，本项目使用了数论变换(NTT)，它对应于FFT，其中单位的原根来自一个有限环(因此系数是整数)而不是复数。为了有效实现,执行多项式算术和,和一个素数，这样。这样的参数选择使得的多项式乘法中使用点NTT而不是点NTT。然而，这增加了与负包装卷积相关的额外的缩放开销。这种技术被称为负卷积。在NTT计算过程中，本项目使用了来自[7]的优化。
在本文中，通过使用[7]中的步骤来实现一种快速加密方案。加密操作采样三个误差多项式，计算三个正向NTT，两个系数明确的多项式乘法和三个多项式加法。解密计算一个系数的多项式乘法、一个多项式加法和一个逆NTT。有关详细信息，请参阅[7]。
- 实现
本节将描述基于ARM平台的Ring-LWE实现。在介绍了目标器件之后，描述了从高斯分布中有效采样的技术，高效的多项式乘法，最后是随机数生成。
- 目标设备
本设计是在ARM Cortex-M4F上实现的，ARM Cortex-M4F是一款非常流行并且功能强大的嵌入式平台。它为32位，有13个通用寄存器，指令集支持执行单周期32位乘法，16位SIMD算法，以及一个取决于输入参数的需要2-12个周期的除法指令。本项目使用了STMicroelectronics的STM32F407芯片，其中包括ARM Cortex-M4F，最大时钟速度为168 MHz, 192kb的SRAM，以及基于硬件的TRNG。
- 高斯采样
离散高斯采样器由于其高效的实现对环路密码系统的性能影响很大，所以值得特别关注。在实现中，每个加密操作都需要3n个采样。
1) Knuth-Yao 算法: 该算法[15]在二叉树离散分布生成树(discrete distribution generate, DDG)上随机游走。DDG树与样本点的概率有关。概率的二进制展开用矩阵形式，二进制元素表示，称为概率矩阵。的每一行都对应于从高斯分布中抽取一个离散位置的随机数的概率。的每个元素表示二叉树中的一个节点，每个非零元素对应一个终端节点。的每一列对应于DDG树中的一个级别。
算法 1 显示了算法的步骤。DDG树是动态构建的，不需要存储整个树。在抽样操作期间，从DDG树的根开始执行随机游走。每一次随机游走都会消耗一个随机位元来从树的一层移动到下一层。距离计数器表示访问节点右侧的中间节点数。访问每个非零节点都将距离计数器减1。当距离计数器最终降至0以下时，就找到了终端节点，概率矩阵的当前行数表示样本。由于概率矩阵只包含高斯分布的正半部分，因此用随机比特来决定样本的符号。本方案计划执行所有操作模,负数通过得到。有关详细信息，请参阅[6]，[14]。
算法1 Knuth-Yao 抽样算法
|
Algorithm 1 Knuth-Yao 抽样算法 |
|
Input：概率矩阵，随机数，模量 |
|
Output：抽样值s |
|
1：for do |
|
2： |
|
3： |
|
4： for do |
|
5： |
|
6： if = -1 then |
|
7： if then |
|
8： return |
|
9： else |
|
10： return row |
|
11：return 0 |
算法1中的位扫描操作代价高昂:在内部循环中，从中提取列的每一位，从d中减去，然后检查d的符号。循环开销存在于每个内部循环迭代中:需要更新行索引，并根据其下界进行检查，还需要从每个列中读取多个字。因此，内部循环的每个迭代至少需要8个循环:更新和检查d和行索引的循环开销的边界。虽然这看起来是一个很小的数字，但是在本项目的的设计中，当考虑到由5995位组成时，它就变得非常重要了。本文接下来讨论了Knuth-Yao算法软件实现的几种优化技术。这些技术主要着重于减少扫描位的数量。
2)将概率矩阵以列的形式存储:Alg. 1要求中连续访问同一列中不同行的元素。为了保持低内存访问数，以列形式存储。和s = 11.31两个系数的存储需要55行和109列提供精度。由于每个列只包含55位，因此当一个列存储在两个32位的字中时，会浪费9位。下面的优化假设矩阵以列形式存储。
3)减少存储的元素数量:从算法 1可以看出，处理0没有效果，因为距离d没有改变。因此，只需要处理和存储包含非零元素的矩阵区域。连续两列之间的汉明权值最多增加1;从而使得概率矩阵左下角存在大量的0，如图1所示。
图1概率矩阵的部分图。
注：本设计避免存储零个字(用蓝色框表示)，因为它们不需要处理。
存储每一列需要多个处理器字(section III-B2)，为了避免对零字进行无效的位扫描操作，本项目只存储概率矩阵中的非零字，因为零字不需要处理。对于，这种技术允许本项目将存储的字数量从218个减少到180个。
4)跳过不必要的位扫描:当距离d小于概率矩阵相关列的汉明权值时，终端节点位于特定的层。[6]中的作者建议将每一列的汉明权重存储在内存中。汉明权值用于避免对距离d不为负数的任何列执行位扫描，从而避免在其中找不到终端节点的列。这种方法需要存储汉明权值，以及外部循环中的逻辑来检查是否会在当前级别中发现终端节点。
本项目提出另一种解决方案，以避免对概率矩阵的所有非零
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
