基于NTRU格的快速傅里叶正交化及模糊提取器研究

# 基于NTRU格的快速傅里叶正交化及模糊提取器研究 ## 1. 基于NTRU格的快速傅里叶正交化在FALCON中的应用 ### 1.1 实验背景与设置 在实验中，我们将相关技术应用于FALCON，这是NIST第三轮决赛入围的基于格的数字签名算法。NIST第一轮版本的FALCON在分圆域 \(Q[x]/(x^n - x^{n/2} + 1)\)（\(n = 768\)）上实现，但因技术难度过高在第二轮被移除。我们的实验基于第三轮的实现，仅考虑分圆域 \(Q[x]/(x^n + 1)\)，其中 \(n = 512\) 或 \(1024\)。 在FALCON的第三轮NIST包中，我们选择 `/falcon-round3/Extra/c` 文件夹中的代码进行实验，这样便于测试修改后实现的正确性和性能。新的实现已在两种不同架构（Intel i7 - 4790 CPU和ARM Cortex M4）上成功测试，因此基准测试结果分为两部分。 ### 1.2 Intel i7 - 4790 实验结果 我们在Ubuntu 18.04系统上，使用单个Intel Core i7 - 4790 CPU核心（3.60 GHz）和4 GB RAM进行实验。基准测试不考虑AVX2加速，所有浮点运算使用C double类型。代码使用clang 6.0.0和默认优化标志 `-O3` 进行编译。 #### 1.2.1 LDL树生成时间 FALCON的LDL树生成主要包括三个步骤： 1. 将NTRU基 \(B_{f,g}\) 转换为其FFT表示 \(FFT(B_{f,g})\)。 2. 计算 \(FFT(G_{f,g}) = FFT(B_{f,g}) × FFT(B_{f,g}^*)\)。 3. 使用 \(FFT(G_{f,g})\) 构建LDL树。 实验结果如下表所示： | \(n\) | FALCON生成时间（\(B_{f,g}\)，\(\mu s\)） | 我们的工作生成时间（\(B_{f,g}\)，\(\mu s\)） | FALCON生成时间（\(FFT(G_{f,g})\)，\(\mu s\)） | 我们的工作生成时间（\(FFT(G_{f,g})\)，\(\mu s\)） | | ---- | ---- | ---- | ---- | ---- | | 512 | 35.28 | 25.38 | 20.12 | 10.28 | | 1024 | 76.02 | 54.81 | 43.40 | 22.53 | 在不计算 \(\frac{1}{ff^* + gg^*}\) 的LDL树时，使用 \(B_{f,g}\) 生成LDL树的时间约减少28%，使用 \(FFT(G_{f,g})\) 生成LDL树的时间约减少48%。 #### 1.2.2 LDL树存储内存 FALCON中 \(Q[x]/(x^n + 1)\) 上的LDL树需要 \(64n(\log n + 1)\) 位内存来存储。在不保留 \(\frac{1}{ff^* + gg^*}\) 的LDL树时，NTRU格的LDL树仅需要 \(32n(\log n + 2)\) 位内存，对于 \(n = 512\) 或 \(1024\)，节省了约45%的内存。具体内存使用情况如下表： | \(n\) | FALCON内存（KB） | 我们的工作内存（KB） | | ---- | ---- | ---- | | 512 | 40 | 22 | | 1024 | 88 | 48 | #### 1.2.3 快速傅里叶采样性能 不存储 \(\frac{1}{ff^* + gg^*}\) 的LDL树对NTRU格上的快速傅里叶采样性能几乎没有影响。在FALCON的实现中，LDL树叶节点的值是整数上高斯分布标准差 \(\sigma_d\) 的倒数，而不是快速傅里叶正交化算法得到的对角元素 \(d\)。设 \(\sigma\) 是NTRU格上高斯分布的标准差，有 \(\sigma_d = \sigma / \sqrt{d}\)，设 \(q\) 是FALCON的模数。\(ff^* + gg^*\) 的LDL树叶节点存储的值是 \(1 / \sigma_d = \sqrt{d} / \sigma\)，而 \(\frac{1}{ff^* + gg^*}\) 的LDL树所需的值是 \(q / (\sigma \sqrt{d})\)。 在预计算 \(1 / \sigma^2\) 时，对于数域 \(Q[x]/(x^n + 1)\)，我们的技术在签名过程中引入了额外的 \(n\) 次浮点乘法和 \(n\) 次浮点除法。但从下表可以看出，这些浮点运算对签名生成效率影响很小。然而，动态构建LDL树会使签名生成时间增加70% - 80%。 | 度数 | 无LDL树签名生成时间（\(\mu s\)） | 有LDL树签名生成时间（\(\mu s\)） | 我们的工作签名生成时间（\(\mu s\)） | | ---- | ---- | ---- | ---- | | 512 | 318.43 | 183.30 | 184.38 | | 1024 | 649.21 | 363.68 | 365.17 | ### 1.3 ARM Cortex M4 实验结果 对于内存受限的设备，在不牺牲签名效率的前提下减少RAM使用更为重要。我们使用STM32F4开发板对实现进行基准测试，该开发板与pqm4项目和Pornin使用的相同，提供