CRYSTALS-Dilithium算法实现的空间优化

Spatial Optimization for CRYSTALS-Dilithium Digital Signature Scheme

摘要

量子计算机的高速发展给传统公钥密码带来了潜在的威胁，基于格的数字签名算法CRYSTALS-Dilithium，虽然实现效率较传统公钥密码要高效得多，但是需要较大的存储资源空间保存公钥、私钥以及中间变量。针对上述问题，提出了节省矩阵所需要的空间和减少临时变量的数量两种优化方法，减少签名过程中的中间变量所需空间大小。通过本文的方法，可以减少大量程序运行所需要的存储资源，以便能更好地应用于存储资源受限的物联网设备中。对于三种不同安全级别的Dilithium算法，节省空间分别为23.53%，32.00%和38.89%。

Abstract

The rapid development of quantum computers has brought potential threats to traditional encryption and signature schemes. Although the lattice⁃based digital signature algorithm Crystals Dilithium has a breakneck speed, it needs ample space to store public keys, private keys, and intermediate variables. To address this issue, the paper introduces two methods aimed at reducing the space required by the matrix and the number of temporary variables. This, in turn,minimizes the space needed for the intermediate variables in the signature process. Through the method in this paper, we can reduce the space programs required to run on space-limited IOT devices. For the three different security levels of the Dilithium algorithm, the space savings are 23.53%, 32.00%, and 38.89%, respectively.

关键词

抗量子密码 / 格密码 / 数字签名 / 物联网 / 快速数论变换

Key words

post-quantum cryptography / lattice-based cryptography / digital signature / Internet of things(IoT) / NTT(number theoretic transforms)

0　 引 言

近年来，物联网技术的发展催生了大量以物理传感器和单片机(micro control unit,MCU)为核心的应用场景，作为全球领先的半导体知识产权提供商，ARM凭借其在处理器领域优异的性能、成本和功耗优势，占据了90%以上的MCU市场份额。ARM公司既不生产芯片也不销售芯片，专业从事技术研发和授权转让，世界知名的半导体电子公司都与ARM建立了合作伙伴关系。ARM公司推出的Cortex-M系列处理器，在保证处理器的性能的前提下，最大限度地控制了硬件成本和功能损耗，以适应物联网应用的新场景。

物联网设备日渐丰富的功能也带来了更严重的隐私信息泄露问题，作为传统签名的替代，数字签名也伴随着隐私保护和网络安全的需求出现，为用户提供身份认证和数据完整性认证等。

目前量子计算理论和量子计算机正在高速发展，对传统的基于整数分解困难假设或者离散对数困难假设的公钥加密方案和签名方案（例如RSA和ECC等）造成了潜在的威胁。Shor^[1]已经证明一旦量子计算机被制造出，就可以在多项式时间内破解上述方案。

在这样的大环境下，国际上掀起了研究抗量子密码方案的热潮，其中基于格上的困难假设构造密码方案受到了广泛的关注和研究。除了目前没有多项式时间的量子求解算法之外，基于格的方案还具有诸多良好的特性，全为线性运算速度快、平均情况和最坏情况的困难性等价^[2，3]、可以用来构建全同态加密^[4~6]等。

1　 相关工作

2005年Regev在文献[3]中首次提出了错误学习问题(Learning With Errors, LWE)，并证明了该问题的安全性至少和最坏情况下的SVP问题的变体一样困难。文中还基于LWE问题构建了一个公钥加密系统，相比之前的基于格的加密系统，密文和密钥的大小被大幅度减少。此后，研究者们基于LWE问题提出了许多基于格的密码学原语，例如加密方案^[3~7]、数字签名方案^[7]、密钥交换协议^[8]、全同态加密方案^[4，6]等。值得注意的是，文献[7]是第一个可证明安全的基于格的数字签名方案，但是该方案产生的密钥尺寸过大,达到兆字节级,效率很低。

为了进一步压缩尺寸和提高效率，2010年，Lyubashevsky等在文献[9]中提出了环上的错误学习问题（Ring LWE,RLWE），RLWE是LWE问题在特定环上的版本，并将RLWE问题的困难性与理想格上最坏情况的问题建立了联系，且目前还没有算法可以有效地解决该问题^[10] 。

2012年，Lyubashevsky利用小整数解（SIS）问题、LWE问题和拒绝抽样技术(Rejected Sampling) ^[11]，构造了第一个无陷门的格基签名方案―Lyu12签名方案^[12]，该签名基于“Fiat-Shamir with Aborts”架构，公钥、私钥和签名尺寸都要优于当时的所有基于“hash-and-sign”架构的签名方案。2013年，Ducas等^[13]将文献[12]中的离散高斯分布修改为双峰高斯分布，得到BLISS签名方案，进一步优化了尺寸。几乎同时，一些关于签名压缩的技巧也被提出^[14，15]。

2015年，Langlois等^[16]提出了模上的错误学习问题（Module LWE,MLWE），该问题可以视为RLWE问题与LWE问题的折衷，比RLWE问题具有更复杂的代数结构和更强的安全性,比LWE问题有更高的性能，非常适合用来构造基于格的密码学方案。

美国国家标准技术研究所(National Institute of Standards and Technology,NIST)于2016年启动了抗量子计算密码的国际标准征集项目，并于2022年7月正式公布了首批抗量子密码算法，其中有相当一部分是基于格的方案，例如密钥封装方案CRYSTALS-Kyber^[17]以及数字签名方案CRYSTALS-Dilithium^[18]和Falcon^[19]等。中国密码学会也在2019年举办了全国密码算法设计竞赛，其中的获奖算法中大部分也是基于格困难问题构造的，如Aigis-enc(sig)^[20]。

现有的关于CRYSTALS-Dilithium签名算法的优化实现主要集中在运算速度上，例如文献[21]采用乒乓结构存储多项式系数，达到增加存取带宽的目的，并通过消除预缩放运算，达到了模乘运算减少10.5%和存储空间占用减少16.7%的效果，能够以更小的电路面积实现更高的工作频率。除此以外，一些对CRYSTALS-Kyber算法中的NTT、INTT等模块的优化工作^[22]也可以考虑迁移到CRYSTALS-Dilithium签名算法上。文献[23]介绍了目前基于格的数论变换加速方面的研究。

在利用软件与硬件结合进行实现方面，一些研究^[24~27]也已经表明大部分的仅采用能够实现NTT 变换的硬件架构，而将方案流程的其余部分交由软件负责，可以达到非常可观的性能提升。

CRYSTALS-Dilithium（简称Dilithium）的运算速度已经极快，文献[18]指出在Dilithium-2安全级别下，1秒可以完成密钥生成、签名、验签过程2 000余次，这个速度已经远远快于传统的RSA签名方案^[28]。文献[29]对比了国密算法和传统国际算法在车载单片机中运行所需要的时间和空间大小。但是Dilithium算法运行时消耗空间较大，因此可能存在在一些物联网设备上无法运行的问题。针对这个问题，Güneysu等^[30]对文献[12,14，18]中的基于格的数字签名方案在受限的嵌入式设备上实现进行了调研，并总结回顾了这些方案在ARM Cortex-M4处理器上的实际表现，得出的结论是Dilithium为了安全性而牺牲了一些性能，相比之下BLISS在内存消耗和周期计数方面更优。Kannwischer等提出了pqm4框架^[31]，pqm4是一个基准测试框架，它目前主要针对ARM Cortex-M4系列微控制器的后量子密钥封装机制和后量子签名方案的实现。它的主要特性为可以在广泛可用的开发板上进行自动化功能测试；自动生成测试向量，并与运行主机端的参考实现输出进行比较；针对速度、堆栈使用和代码大小的自动基准测试；自动分析在SHA-2、SHA-3、AES等基本算法中花费的周期；轻松将新方案实现并集成到框架中。Kannwischer在文中分析了NIST征集的抗量子密码方案在特定场景下的表现，实验使用的是ARM Cortex-M4处理器以及STM32F4DISCOVERY单片机。

自ARM于2006年发布Cortex-M系列的第一款处理器Cortex-M3以来，Cortex-M系列推出了许多适用于不同领域的微处理器，以满足物联网发展带来的产品需求，表1列出了常见Cortex-M处理器的产品特点和应用领域。其中常用的STM32F103RD单片机以72 MHz频率运行的高性能ARM®Cortex®-M3 32位RISC为内核，它包括高速嵌入式内存（闪存高达384 KB，SRAM高达64 KB），以及连接到两条APB总线的一系列增强型I/O和外围设备。所有设备都提供三个12位ADC、四个通用16位计时器和两个PWM计时器，以及标准和高级通信接口：最多两个I2C、三个SPI、两个I2S、一个SDIO、五个USART、一个USB和一个CAN。STM32F103xC/D/E高密度性能系列在-\mathrm{40} ~+105 °C的温度范围内工作，电源电压为2.0 ~ 3.6 V。一套全面的节能模式允许设计低功耗应用程序。这些特性使STM32F103xC/D/E高密度性能线微控制器系列适用于广泛的应用，如电机驱动、应用控制、医疗和手持设备、PC和游戏外围设备、GPS平台、工业应用、PLC、逆变器、打印机、扫描仪、报警系统视频对讲机和HVAC等。

然而，在常见的STM32F103系列单片机中，STM32F103RD的Flash大小为384 KB，RAM为64 KB。经过测试，最低安全性的Dilithium算法的代码段需要52 KB，临时变量更是需要68 KB，故Dilithium算法无法在该单片机上运行。

本文针对这个问题，提出了两种方法来减少Dilithium算法运行过程中所需要的临时空间。分别通过使矩阵 A 逐项生成和减少临时变量。在通过本文提出的方法减少临时空间大小需求后，Dilithium算法可以成功在该单片机上运行。

2　 基础知识

2.1　格的定义

在被用来构造密码学方案之前，格理论就已经被用在多项式分解、整数规划^[32]、密码分析^[33]等领域，是数学与计算机科学中的一个热门研究方向。

定义1（格）：给定一组线性无关的n维向量{\mathit{a}}_{\mathrm{1}},{\mathit{a}}_{\mathrm{2}},\dots ,{\mathit{a}}_m\in {\mathbb{R}}^n，格\mathrm{ℒ}是指由这些向量的线性组合所构成的向量集合，其中线性组合的系数均在整数集合\mathbb{Z}中，即

\mathrm{ℒ}\left({\mathit{a}}_{\mathrm{1}},{\mathit{a}}_{\mathrm{2}},\dots ,{\mathit{a}}_m\right)=\left\{{\displaystyle \sum _{i=\mathrm{1}}^m}{x}_i{\mathit{a}}_i|x_i\in \mathbb{Z}\right\}

将({\mathit{a}}_{\mathrm{1}},{\mathit{a}}_{\mathrm{2}},\dots ,{\mathit{a}}_m)称为格\mathrm{ℒ}的一组基，格基可以用矩阵\mathit{A}=[{\mathit{a}}_{\mathrm{1}},{\mathit{a}}_{\mathrm{2}},\dots ,{\mathit{a}}_m]表示，因此格的定义等价于

\mathrm{ℒ}\left(\mathit{A}\right)=\mathrm{ℒ}\left({\mathit{a}}_{\mathrm{1}},{\mathit{a}}_{\mathrm{2}},\dots ,{\mathit{a}}_m\right)=\left\{\mathit{A}x|x\in {\mathbb{Z}}^m\right\}

其中，n为格的维数，m为格的秩，若m=n，则称格\mathrm{ℒ}是满秩格。除非特别说明，我们只讨论满秩格，即({\mathit{a}}_{\mathrm{1}},{\mathit{a}}_{\mathrm{2}},\dots ,{\mathit{a}}_m)是线性无关的。

2.2　格上的困难问题

基于格的密码学原语的安全性最终通常会归约到格上的计算困难问题，即找到给定格上的满足长度最小特性的向量，主要包括为最近向量问题（CVP）、最短向量问题（SVP）等，在特定的参数下，这些问题甚至是NP-hard的^[34~36]。

容易发现，如果一个问题的平均情况(Average-Case)是困难的，那么最坏情况(Worst-Case)一定是困难的。若能找到从最坏情况到平均情况的归约，就可以通过调用解决平均情况的方法来解决最坏情况，这样解决了平均情况，就能解决最坏情况，不再需要考虑弱实例的问题，这是RSA、ECC等密码系统不具备的优点。因此，密码学家们倾向于通过平均情况困难问题来构造格密码方案，主要包括小整数解问题（SIS）和错误学习问题（LWE）。

定义2（错误学习问题, LWE）^[3]：对于均匀随机产生的秘密向量\mathit{s}\leftarrow {\mathbb{Z}}_q^n，定义LWE分布\left(\mathit{a},〈\mathit{a},\mathit{s}〉+\mathit{e}\right)\in {\mathbb{Z}}_q^n\times {\mathbb{Z}}_q，其中\mathit{a}\leftarrow {\mathbb{Z}}_q^n均匀随机产生，错误\mathit{e}\leftarrow {\chi }_{\alpha }\in {\mathit{\mathbb{Z}}}_q由离散高斯分布{\chi }_{\alpha }产生。Search-LWE问题要求通过m个LWE分布的样本\left({\mathit{a}}_i,〈{\mathit{a}}_i,\mathit{s}〉+{\mathit{e}}_{\mathit{i}}\right)求解秘密向量\mathit{s}；Decision-LWE问题要求区分LWE分布和在{\mathbb{Z}}_q^n\times {\mathbb{Z}}_q上均匀随机抽样得到的样本。

LWE问题也可以写成矩阵形式，如下：

\left(\begin{array}{l}〈{\mathit{a}}_{\mathrm{1}},\mathit{s}〉+{\mathit{e}}_{\mathrm{1}}\\ 〈{\mathit{a}}_{\mathrm{2}},\mathit{s}〉+{\mathit{e}}_{\mathrm{2}}\\ ⋮\\ 〈{\mathit{a}}_m,\mathit{s}〉+{\mathit{e}}_m\end{array}\right)=\left(\begin{array}{l}{\mathit{a}}_{\mathrm{1}}^T\\ {\mathit{a}}_{\mathrm{2}}^T\\ ⋮\\ {\mathit{a}}_m^T\end{array}\right)\mathit{s}+\left(\begin{array}{l}{\mathit{e}}_{\mathrm{1}}\\ {\mathit{e}}_{\mathrm{2}}\\ ⋮\\ {\mathit{e}}_m\end{array}\right)={\mathit{A}}^{\mathrm{T}}\mathit{s}+\mathit{e}

即通过({\mathit{A}}^{\mathrm{T}},{\mathit{A}}^{\mathrm{T}}\mathit{s}+\mathit{e})恢复秘密向量\mathit{s}\leftarrow {\mathbb{Z}}_q^n，其中矩阵\mathit{A}=\left[{\mathit{a}}_{\mathrm{1}},\cdots ,{\mathit{a}}_m\right]\in {\mathbb{Z}}_q^{n\times m}的每一列都对应一个LWE分布样本的a_i\in {\mathbb{Z}}_q^n，\mathit{e}={\left[e_{\mathrm{1}},\cdots ,e_m\right]}^{\mathrm{T}}\leftarrow {\chi }_{\alpha }^m\in {\mathbb{Z}}_q^m是错误向量。

LWE问题来源于对于一般的矩阵乘法{\mathit{A}}^{\mathrm{T}}\mathit{s}=\mathit{b}，可以通过高斯消元法求得方程的解，即秘密向量\mathit{s}。在添加一定的噪声\mathit{e}后，即方程{\mathit{A}}^{\mathrm{T}}\mathit{s}+\mathit{e}=\mathit{b}，此时不能再用高斯消元法来获取方程的解。

为了减小密钥长度和提高效率，RLWE问题和MLWE问题被相继提出^[9，16]，下面给出介绍：

设f\left(x\right)=x^n+\mathrm{1}为不可约多项式，R=\mathbb{Z}\left[x\right]/(f\left(x\right))，R_q=R/qR={\mathbb{Z}}_q\left[x\right]/(f\left(x\right))，其中参数q\ge \mathrm{2}和n\ge \mathrm{1}均为正整数，n一般选取2的幂次。

定义3（环上错误学习问题, RLWE）：对于均匀随机产生的秘密向量\mathit{s}\leftarrow R_q，定义RLWE分布\left(\mathit{a},〈\mathit{a},\mathit{s}〉+\mathit{e}\right)\in R_q\times R_q，其中\mathit{a}\leftarrow R_q均匀随机产生，错误\mathit{e}\leftarrow {\chi }_{\alpha }\in R_q由离散高斯分布{\chi }_{\alpha }产生。Search-RLWE问题要求通过m个RLWE分布的样本\left({\mathit{a}}_{\mathit{i}},〈{\mathit{a}}_{\mathit{i}},\mathit{s}〉+{\mathit{e}}_{\mathit{i}}\right)求解秘密向量\mathit{s}；Decision-RLWE问题要求区分RLWE分布和在R_q\times R_q上均匀随机抽样得到的样本。

定义4（模上错误学习问题, MLWE）：对于均匀随机产生的秘密向量\mathit{s}\leftarrow R_q^v，定义MLWE分布\left(\mathit{a},〈\mathit{a},\mathit{s}〉+\mathit{e}\right)\in R_q^v\times R_q，其中\mathit{a}\leftarrow R_q^v均匀随机产生，错误\mathit{e}\leftarrow {\chi }_{\alpha }\in R_q由离散高斯分布{\chi }_{\alpha }产生。Search-MLWE问题要求通过m个MLWE分布的样本\left({\mathit{a}}_{\mathit{i}},〈{\mathit{a}}_{\mathit{i}},\mathit{s}〉+{\mathit{e}}_{\mathit{i}}\right)求解秘密向量\mathit{s}；Decision-MLWE问题要求区分MLWE分布和在R_q^v\times R_q上均匀随机抽样得到的样本。

MLWE问题也可以写成矩阵形式，如下：

\left(\begin{array}{l}〈{\mathit{a}}_{\mathrm{1}},\mathit{s}〉+{\mathit{e}}_{\mathrm{1}}\\ 〈{\mathit{a}}_{\mathrm{2}},\mathit{s}〉+{\mathit{e}}_{\mathrm{2}}\\ ⋮\\ 〈{\mathit{a}}_m,\mathit{s}〉+{\mathit{e}}_m\end{array}\right)=\left(\begin{array}{l}{\mathit{a}}_{\mathrm{1}}^T\\ {\mathit{a}}_{\mathrm{2}}^T\\ ⋮\\ {\mathit{a}}_m^T\end{array}\right)\mathit{s}+\left(\begin{array}{l}{\mathit{e}}_{\mathrm{1}}\\ {\mathit{e}}_{\mathrm{2}}\\ ⋮\\ {\mathit{e}}_m\end{array}\right)={\mathit{A}}^{\mathrm{T}}\mathit{s}+\mathit{e}

即通过({\mathit{A}}^{\mathrm{T}},{\mathit{A}}^{\mathrm{T}}\mathit{s}+\mathit{e})恢复秘密向量\mathit{s}\leftarrow R_q^v，其中矩阵\mathit{A}=\left[{\mathit{a}}_{\mathrm{1}},\cdots ,{\mathit{a}}_m\right]\in {\mathbb{R}}_q^{v\times m}的每一列都对应一个MLWE分布样本的{\mathit{a}}_i\in {\mathbb{R}}_q^v，\mathit{e}={\left[e_{\mathrm{1}},\cdots ,e_m\right]}^{\mathrm{T}}\leftarrow {\chi }_{\alpha }^m\in{\mathbb{R}}_q^m是错误向量。

特别地，对于v=k+l维秘密向量\mathit{s}，取矩阵{\mathit{A}}^{\mathit{\text{'}}}=[\mathit{A},{\mathit{I}}_{\mathit{k}}]，其中\mathit{A}\leftarrow {\mathit{R}}_q^{k\times l}均匀随机选取，{\mathit{I}}_{\mathit{k}}表示k阶单位矩阵，此时得到的{\mathit{A}}^{\mathit{\text{'}}}\mathit{s}=\left[\mathit{A},{\mathit{I}}_{\mathit{k}}\right]\left[\begin{array}{c}{\mathit{s}}_{\mathrm{1}}\\ {\mathit{s}}_{\mathrm{2}}\end{array}\right]=\mathit{A}{\mathit{s}}_{\mathrm{1}}+{\mathit{s}}_{\mathrm{2}}称为Hermite正规形式，泄露的关于\mathit{s}的信息最少，适合用作加密或签名系统中的公钥^[37]，Dilithium公钥就是出于该考虑进行的选取。

2.3　CRYSTALS-Dilithium算法

2020年7月，NIST的抗量子密码算法征集完成了第三轮筛选并确定了7个最终方案，其中包含了CRYSTALS-Dilithium、Falcon、Rainbow三个数字签名方案，前两个是基于格困难问题的方案，最后一个是基于多变量困难问题的方案。

根据研究者们向NIST的提交的材料以及评审结果显示，Falcon在公钥、签名尺寸和性能上略胜一筹，但是其签名算法内部逻辑较为复杂，实现难度较高；Rainbow算法虽然具有很小的签名尺寸，但是其公钥过大，即便在压缩状态下也相当于Dilithium和Falcon的数十倍。相对而言，CRYSTALS-Dilithium在安全性和性能上均没有明显的缺点，因而正式成为抗量子数字签名最终国际标准之一。

Dilithium算法的设计用到了“Fiat-Shamir with Aborts”范式^[17，18]，并使用了一些压缩技巧^[20，21]，主要具备以下几个优点：

1) 容易安全地实现：此前的基于格的数字签名方案^[18，19]需要从离散高斯分布中选取秘密值，效率较低，同时容易遭到侧信道攻击，导致实现的不安全^[38，39]。与它们不同，Dilithium签名算法只需要进行均匀采样。除了采样之外，其余的运算操作例如多项式乘法和采样也都可以在恒定时间内完成。

2) 参数的选取较为保守，同时公钥和签名的尺寸是已有的基于格的方案中最小的。

3) 不同级别的安全性之间容易切换：只需在环上进行更多/更少的操作，或者修改XOF(建议使用SHAKE-128或SHAKE-256)就可以切换到不同级别的安全性。换句话说，一旦获得某个安全级别的更优化的实现，就很容易获得其他安全级别的更优化的实现。

Dilithium签名算法主要包括密钥生成、签名生成以及签名验证三个过程，本文主要关注和优化签名生成过程，以及其中的临时变量所需要的空间。

在介绍Dilithium签名生成过程之前，我们先介绍算法中需要用到的提取R_q中元素的每一个系数的高位比特(HighBits)和低位比特(LowBits)的算法^[24]，称为\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}{\mathrm{e}}_q(\bullet )。该算法的目标是给定任意的元素r\in {\mathbb{Z}}_q和一个小的元素z\in {\mathbb{Z}}_q，能在不保存z的情况下恢复r+z的高位整数。

算法1即为该算法。\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}{\mathrm{e}}_q(r,\alpha )算法输入数字r和\alpha，分解得到r=r_{\mathrm{H}}\bullet \alpha +r_{\mathrm{L}}，其中且{‖r_{\mathrm{L}}‖}_{\mathrm{\infty }}\le \alpha /\mathrm{2}。当\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}{\mathrm{e}}_q(\bullet )算法作用到多项式（例如环R_q中的元素）或由多项式组成的向量或矩阵时，对应操作被分别独立地作用到多项式的每个系数。

Dilithium算法的密钥生成算法主要分为以下几个步骤：

Step 1 首先利用SHAKE-256算法和种子产生k\times l维的矩阵\mathit{A}，\mathit{A}中的每一个元素都是在环R_q={\mathbb{Z}}_q\left[x\right]/(X^n+\mathrm{1})上的多项式，其中q={\mathrm{2}}^{\mathrm{23}}-{\mathrm{2}}^{\mathrm{13}}+\mathrm{1}，n=\mathrm{256}。

Step 2 利用SHAKE-256算法和种子分别产生l维向量{\mathit{s}}_{\mathrm{1}}和k维向量{\mathit{s}}_{\mathrm{2}}，其中向量{\mathit{s}}_{\mathrm{1}}和{\mathit{s}}_{\mathrm{2}}中的每一个元素都是-\eta到\eta中的随机数。

Step 3 计算向量\mathit{t}=\mathit{A}{\mathit{s}}_{\mathrm{1}}+{\mathit{s}}_{\mathrm{2}}。

Step 4 公钥p_k=(\mathit{A},\mathit{t})，私钥s_k=(\mathit{A},\mathit{t},{\mathit{s}}_{\mathrm{1}},{\mathit{s}}_{\mathrm{2}})。

Dilithium算法的签名生成算法主要分为以下几个步骤：

Step 1 生成系数小于{\gamma }_{\mathrm{1}}的多项式\mathit{y}的屏蔽向量(masking vector)，参数{\gamma }_{\mathrm{1}}需要设置在一定范围内使得最终签名不会泄露密钥(即签名算法是零知识的)，且使得签名不容易被伪造。

Step 2 计算\mathit{A}\mathit{y}，并使用\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}{\mathrm{e}}_q(\bullet )算法得到\mathit{w}的高位比特{\mathit{w}}_{\mathrm{1}}和低位比特{\mathit{w}}_{\mathrm{2}}，分解时使用的\alpha =\mathrm{2}{\gamma }_{\mathrm{2}}。

Step 3 使用哈希函数H_{\mathrm{0}}计算挑战值c\in C，c是R_q中的多项式，系数c_{\mathrm{0}},c_{\mathrm{1}},\cdots ,c_{\mathrm{255}}\in \{\pm \mathrm{1,0}\}，其中\pm \mathrm{1}的个数为\tau。选择这种分布的原因是c具有小的范数，并且来自（拥有足够大的）熵\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\left(\genfrac{}{}{0pt}{}{\mathrm{256}}{\tau }\right)+\tau 的挑战值空间。

Step 4 计算潜在的签名\mathit{z}≔\mathit{y}+c{\mathit{s}}_{\mathrm{1}}，由于直接输出可能会导致密钥的泄露，因此使用拒绝采样^[17]，参数\beta被设置为c{\mathit{s}}_{\mathrm{1}}的最大可能系数。如果\mathit{z}的任何一项系数大于{\gamma }_{\mathrm{1}}-\beta，那么拒绝并重新开始签名过程。同样，如果\mathit{A}\mathit{z}-c\mathit{t}的任何低位比特的系数大于{\gamma }_{\mathrm{2}}-\beta，则需要重新开始计算签名。

算法2即为Dilithium算法的签名算法。

在具体的实现中，Dilithium算法签名过程中使用的随机数是作为消息和小密钥的确定性函数生成的(使用 SHAKE-256)。由于签名过程可能需要重复几次，直到生成一个签名，因此添加了一个计数器，以使SHAKE-256输出在同一消息的每次签名尝试中有所不同。

由于每个消息(可能很长)可能需要多次迭代才能签名，使用抗碰撞哈希函数计算消息的初始摘要，并在整个签名过程中使用该摘要来代替消息。不同安全等级的Dilithium算法参数选择如表2所示，下文以Dilithium-i表示不同安全级别的Dilithium算法，其中i=2,3,5。

3　 算法的空间优化实现

3.1　NTT算法的空间优化实现

由于Dilithium算法需要大量计算向量的乘积，而向量乘积中高次多项式乘法又是算法中最耗时的部分，所以我们需要一种快速算法计算高次多项式乘积。

快速数论变换^[40]（number theoretic transform，NTT）算法是计算高次多项式乘法的一种常用方法，该方法能使高次多项式乘法的时间复杂度从{\rm O}(n^{\mathrm{2}})降低到{\rm O}\left(n\mathrm{l}\mathrm{o}\mathrm{g}n\right)。快速数论变换是在快速傅里叶变换（fast Fourier transform，FFT）的基础上改进而来的。由于快速傅里叶变换的计算使用了复平面上的单位根，计算时会有大量的复数运算、正弦函数、余弦函数以及浮点数的计算，在多项式阶数较高时运算量过大，且浮点数运算会损失精度。

快速数论变换是快速傅里叶变换在有限域上的扩展，由于复平面上的单位根和有限域上的本原根具有相同的性质，故将快速傅里叶变换中所使用的复平面上单位根替换成有限域上的本原根即为快速数论变换。快速数论变换中的运算均为在有限域中的整数运算，减少了运算的复杂度，且避免了浮点数运算的精度损失。

定义5（基于循环卷积的 NTT，CC-based NTT）：n个点基于循环卷积的NTT有两个参数：多项式长度或者点的个数n，以及模数q，其中n为2的整数次幂，q为满足q\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}n的素数，这意味着{\mathbb{Z}}_q上的n阶本原根{\omega }_n存在，令\omega为n阶本原根，即满足{\omega }^n\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}q。

向量\mathit{a}表示多项式的系数向量，即：

\mathit{a}=\left(a_{\mathrm{1}},a_{\mathrm{2}},a_{\mathrm{3}},\dots ,a_n\right)\in {\mathbb{Z}}_q^n

正向NTT变换\widehat{\mathit{a}}=\mathrm{N}\mathrm{T}\mathrm{T}(\mathit{a})定义如下：

{\widehat{a}}_j={\displaystyle \sum _{i=\mathrm{0}}^{n-\mathrm{1}}} a_i{\omega }_n^{ij}\mathrm{m}\mathrm{o}\mathrm{d}q,j=\mathrm{0,1},\dots ,n-\mathrm{1}

逆向NTT变换\mathit{a}=\mathrm{I}\mathrm{N}\mathrm{T}\mathrm{T}(\widehat{\mathit{a}})定义如下：

a_i=n^{-\mathrm{1}}{\displaystyle \sum _{j=\mathrm{0}}^{n-\mathrm{1}}} {\widehat{a}}_j{\omega }_n^{-ij}\mathrm{m}\mathrm{o}\mathrm{d}q,i=\mathrm{0,1},\dots ,n-\mathrm{1}

此时可以通过将NTT公式中的{\omega }_n^{ij}变更为{\omega }_n^{-ij}，并乘以比例因子n^{-\mathrm{1}}，使得NTT和INTT共享同一个运算公式，且\mathit{a}=\mathrm{I}\mathrm{N}\mathrm{T}\mathrm{T}(\mathrm{N}\mathrm{T}\mathrm{T}(\mathit{a}))。

故计算多项式\mathit{a}和多项式\mathit{b}的卷积\mathit{c}时就可以使用下式：

\mathit{c}=\mathrm{I}\mathrm{N}\mathrm{T}\mathrm{T}\left(\mathrm{N}\mathrm{T}\mathrm{T}\left(\mathit{a}\right)\circ \mathrm{N}\mathrm{T}\mathrm{T}\left(\mathit{b}\right)\right)

定义6（基于负折叠卷积的NTT，NTT-Negative Wrapped Convolution）：在基于循环卷积的 NTT基础上，如果模数q满足q\equiv \mathrm{1}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{2}n，意味着{\mathbb{Z}}_q上的\mathrm{2}n阶本原根{\psi }_{\mathrm{2}n}存在。此时{\omega }_n={\psi }_{\mathrm{2}n}^{\mathrm{2}}\mathrm{m}\mathrm{o}\mathrm{d}q，且记\mathit{\psi }=\left(\mathrm{1},{\psi }_{\mathrm{2}n},{\psi }_{\mathrm{2}n}^{\mathrm{2}},\dots ,{\psi }_{\mathrm{2}n}^{n-\mathrm{1}}\right)

{\mathit{\psi }}^{-\mathrm{1}}=(\mathrm{1},{\psi }_{\mathrm{2}n}^{-\mathrm{1}},{\psi }_{\mathrm{2}n}^{-\mathrm{2}},\dots ,{\psi }_{\mathrm{2}n}^{-(n-\mathrm{1})})

定义\overline{\mathit{a}}=\mathit{\psi }\circ \mathit{a}，即\overline{a_i}={\psi }_{\mathrm{2}n}^i{a}_i，则\mathit{a}={\mathit{\psi }}^{-\mathrm{1}}\circ \overline{\mathit{a}}，即a_i={\psi }_{\mathrm{2}n}^{-i}\overline{a_i}。此时，n个点的负折叠卷积NTT就被表示为\mathit{\psi }（{\mathit{\psi }}^{-\mathrm{1}}）的普通NTT（INTT）形式，并且用\mathrm{N}\mathrm{T}{\mathrm{T}}^{\mathit{\psi }}（\mathrm{N}\mathrm{T}{\mathrm{T}}^{{\mathit{\psi }}^{-\mathrm{1}}}）表示，此时有如下公式：

\widehat{\mathit{a}}=\mathrm{N}\mathrm{T}{\mathrm{T}}^{\mathit{\psi }}\left(\mathit{a}\right)=\mathrm{N}\mathrm{T}\mathrm{T}(\mathit{\psi }\circ \mathit{a})

\mathit{a}=\mathrm{I}\mathrm{N}\mathrm{T}{\mathrm{T}}^{{\mathit{\psi }}^{-\mathrm{1}}}\left(\widehat{\mathit{a}}\right)={\mathit{\psi }}^{-\mathrm{1}}\circ \mathrm{I}\mathrm{N}\mathrm{T}\mathrm{T}(\widehat{\mathit{a}})

更具体地说，正向NTT转换\widehat{\mathit{a}}=\mathrm{N}\mathrm{T}{\mathrm{T}}^{\mathit{\psi }}\left(\mathit{a}\right)可以写成如下形式：

{\widehat{a}}_j={\displaystyle \sum _{i=\mathrm{0}}^{n-\mathrm{1}}} a_i{\psi }_{\mathrm{2}n}^i{\omega }_n^{ij}\mathrm{m}\mathrm{o}\mathrm{d}q,j=\mathrm{0,1},\dots ,n-\mathrm{1}

此时，逆向NTT转换\mathit{a}=\mathrm{N}\mathrm{T}{\mathrm{T}}^{{\mathit{\psi }}^{-\mathrm{1}}}\left(\widehat{\mathit{a}}\right)可以写成如下形式：

a_i=n^{-\mathrm{1}}{\psi }_{\mathrm{2}n}^{-i}{\displaystyle \sum _{j=\mathrm{0}}^{n-\mathrm{1}}} {\widehat{a}}_j{\omega }_n^{-ij}\mathrm{m}\mathrm{o}\mathrm{d}q,i=\mathrm{0,1},\dots ,n-\mathrm{1}

故计算多项式\mathit{a}和多项式\mathit{b}的卷积\mathit{c}时可以使用下式：

\mathit{c}=\mathrm{I}\mathrm{N}\mathrm{T}{\mathrm{T}}^{{\mathit{\psi }}^{-\mathrm{1}}}(\mathrm{N}\mathrm{T}{\mathrm{T}}^{\mathit{\psi }}\left(\mathit{a}\right)\circ \mathrm{N}\mathrm{T}{\mathrm{T}}^{\mathit{\psi }}\left(\mathit{b}\right))

Dilithium算法使用的是基于负折叠卷积的NTT算法，负折叠卷积可以避免填充多项式系数，加快多项式乘法速度。此外，Dilithium算法将NTT算法和INTT算法的系数直接存储在一个数组中，而并非等到使用时再开始计算系数，这样提高了多项式乘法的效率，但会占用大量存储空间。我们不提前存储NTT以及INTT的系数，待到使用时再计算生成，这样就可以节省大量存储空间。

3.2　CRYSTALS-Dilithium算法的空间优化实现

本文使用了两种方法来减少签名过程中所使用到的中间变量的空间大小。

第一种方法是减少矩阵\mathit{A}所需空间大小。以Dilithium-2安全性为例，由于矩阵\mathit{A}在32位机器中所需要的空间为\mathrm{4}\times \mathrm{4}\times \mathrm{256}\times \mathrm{32}(\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s})=\mathrm{16}\mathrm{K}\mathrm{B}，很难作为密钥进行传输。

Dilithium算法通过种子以及SHAKE-256算法扩展生成矩阵\mathit{A}，这样通过传输种子即可获得完整的矩阵。但在签名过程中，通过种子生成矩阵仍需要\mathrm{16}\mathrm{K}\mathrm{B}的空间保存矩阵，在很多的物联网设备中可能并没有足够的空间保存该矩阵。

为了减少保存矩阵所需要的空间，可以在\mathrm{4}\times \mathrm{4}矩阵生成的过程中，每生成矩阵中的一项时，直接与\mathit{y}中对应项进行相乘，并将结果保留在{\mathit{w}}_{\mathrm{1}}对应项中。这样就不用等完全生成矩阵\mathit{A}后，再进行运算，从而达到节省空间的目的。

第二种方法通过减少临时变量的数量，从而达到节省空间的目的。

签名过程需要\mathit{z}≔\mathit{y}+c{\mathit{s}}_{\mathrm{1}}判断签名是否有效。此时可以通过\mathit{y}=\mathit{y}+c{\mathit{s}}_{\mathrm{1}}进行判断，而不要重新声明一个新的变量，从而减少中间变量\mathit{z}的空间。改进后的算法如算法3所示。

3.3　实验结果分析

实验平台为Intel平台，芯片型号为i5-11500，实验环境为Ubuntu，内存RAM大小为16 GB。

实验对Dilithium算法在linux平台下运行过程进行了比较，主要包括改进前后所需空间的大小。代码段通常保存在Flash中，函数中的临时变量为栈中的数据，通常保存在RAM中。结果如表3所示。

以Dilithium-2安全性为例，由表3可知，代码段大小为52 KB，临时变量大小为68 KB，改进后临时变量大小为52 KB，节省的空间为16 KB，节省了23.53%的空间。在Dilithium-3和Dilithium-5安全等级下更是节省了32.00%和38.89%的空间。

传统的签名方案RSA算法签名速度已经足够快，但Dilithium签名算法的速度更快，在高安全等级下尤为明显。RSA算法和Dilithium算法的签名速度如表4所示。

由表4可知，Dilithium算法经过avx2指令集加速以及AES加速矩阵生成，速度已经比传统的签名算法快。而传统的1 024 bit的RSA算法（RSA-1024）由于其安全性问题已不再推荐，商密测评标准中更加推荐RSA-2048算法。此时RSA-2048签名速度就比Dilithium慢许多。

RSA-1024和RSA-2048的公私钥长度分别为128字节和256字节。但是Dilithium-2安全性下公钥长度为1 312字节，私钥长度为2 528字节，由此可见Dilithium签名算法所需要的空间极大。由于去除了NTT算法的预处理过程，且改变了Dilithium算法中矩阵\mathit{A}生成的顺序，这使得签名的速度变慢，但实际上速度仍比传统的RSA签名算法快，且节省了大量的空间，使其能在空间受限的物联网设备中使用，因此本文的改进是有意义的。改进前后的速度对比如表4所示。

本文针对ARM Cortex-M4处理器的开发板，在使用pqm4框架下测试了Dilithium-2算法运行密钥生成、签名以及验证三个模块所需要的时间和空间，结果如表5所示。

由表5可知，经过优化后Dilithium-2算法运行时总共所需要的空间减少了37.2%。这是由于pqm4测试框架不包括存储密钥和消息所需的堆栈空间，因为它们是在实现代码之外分配的，这使得实验节省的空间更大。我们之前的实验在除去存储密钥和消息所需的堆栈空间后，与pqm4框架吻合。

测试pqm4框架下Dilithium算法运行所需要的时间如表5所示。由表5可见，只有签名阶段速度变慢，密钥生成阶段和验证阶段速度基本不变，因此本文方案对于空间上的优化是很有必要的。

4　 结 语

基于格的密码算法正在快速发展，尽管其运算速度很快，但是密钥尺寸和密文尺寸过大仍然是目前的主要问题。这使得基于一些格的密码系统无法在低功耗、低存储的物联网设备中使用。

本文针对NIST首批抗量子标准算法中的CRYSTALS-Dilithium数字签名算法，提出了两种方法减少签名生成过程中所需要的临时变量的空间大小，但仍然需要较大的空间，并不适用于性能较低的物联网设备。

从目前来看，基于MLWE困难问题的格密码仍然需要较大空间。未来可能需要提出其他的消耗更小空间的方案来适配物联网设备。

参考文献

[1] SHOR P W. Algorithms for quantum computation： Discrete logarithms and factoring［C］//Proceedings 35th Annual Symposium on Foundations of Computer Science. New York： IEEE Press， 2002： 124-134. DOI： 10.1109/SFCS.1994.365700 .

[2] AJTAI M. Generating hard instances of lattice problems （extended abstract）［C］//Proceedings of the 28th Annual ACM Symposium on Theory of Computing. New York： ACM， 1996： 99-108. DOI： 10.1145/237814.237838 .

[3] REGEV O. On lattices， learning with errors， random linear codes， and cryptography［C］//Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York： ACM， 2005： 84-93. DOI： 10.1145/1060590.1060603 .

[4] GENTRY C. Fully homomorphic encryption using ideal lattices［C］//Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York： ACM， 2009： 169-178. DOI： 10.1145/1536414.1536440 .

[5] BRAKERSKI Z， VAIKUNTANATHAN V. Efficient fully homomorphic encryption from （standard） LWE［J］. SIAM Journal on Computing， 2014， 43（2）： 831-871. DOI: 10.1137/120868669 .

[6] GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： Conceptually-simpler， asymptotically-faster， attribute-based［C］//Annual Cryptology Conference. Berlin： Springer， 2013： 75-92.DOI： 10.1007/978-3-642-40041-4_5 .

[7] GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions［C］//Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. New York： ACM， 2008： 197-206. DOI： 10.1145/1374376.1374407 .

[8] ALKIM E， DUCAS L， PÖPPELMANN T， et al. Post-quantum key exchange—A New Hope［DB/OL］.［2022-09-12］.

[9] LYUBASHEVSKY V， PEIKERT C， REGEV O. On ideal lattices and learning with errors over rings［C］//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg： Springer， 2010： 1-23. DOI： 10.1007/978-3-642-13190-5_1 .

[10] RENTERÍA-MEJÍA C P， VELASCO-MEDINA J. High-throughput ring-LWE cryptoprocessors［J］. IEEE Transactions on Very Large Scale Integration （VLSI） Systems， 2017， 25（8）： 2332-2345. DOI： 10.1109/TVLSI.2017.2697841 .

[11] LYUBASHEVSKY V. Fiat-shamir with aborts： Applications to lattice and factoring-based signatures［C］//International Conference on the Theory and Application of Cryptology and Information Security. Berlin： Springer， 2009： 598-616. DOI： 10.1007/978-3-642-10366-7_35 .

[12] LYUBASHEVSKY V. Lattice signatures without trapdoors［C］//Advances in Cryptology ― EUROCRYPT 2012. Berlin： Springer， 2012： 738-755. DOI： 10.1007/978-3-642-29011-4_43 .

[13] DUCAS L， DURMUS A， LEPOINT T， et al. Lattice signatures and bimodal Gaussians［C］//Annual Cryptology Conference. Berlin： Springer， 2013： 40-56. DOI： 10.1007/978-3-642-40041-4_3 .

[14] GÜNEYSU T， LYUBASHEVSKY V， PÖPPELMANN T. Practical lattice-based cryptography： A signature scheme for embedded systems［C］//International Workshop on Cryptographic Hardware and Embedded Systems. Berlin： Springer， 2012： 530-547. DOI： 10.1007/978-3-642-33027-8_31 .

[15] BAI S， GALBRAITH S D. An improved compression technique for signatures based on learning with errors［C］//Cryptographers’ Track at the RSA Conference. Cham： Springer， 2014： 28-47. DOI： 10.1007/978-3-319-04852-9_2 .

[16] LANGLOIS A， STEHLÉ D. Worst-case to average-case reductions for module lattices［J］. Designs， Codes and Cryptography， 2015， 75（3）： 565-599. DOI： 10.1007/s10623-014-9938-4 .

[17] BOS J， DUCAS L， KILTZ E， et al. CRYSTALS - Kyber： A CCA-secure module-lattice-based KEM［C］//2018 IEEE European Symposium on Security and Privacy （EuroS&P）. New York： IEEE Press， 2018： 353-367. DOI： 10.1109/EuroSP.2018.00032 .

[18] DUCAS L， KILTZ E， LEPOINT T， et al. CRYSTALS-Dilithium： A lattice-based digital signature scheme［J］. IACR Transactions on Cryptographic Hardware and Embedded Systems， 2018： 238-268. DOI： 10.46586/tches.v2018.i1.238-268 .

[19] FOUQUE P A， HOFFSTEIN J， KIRCHNER P， et al. Fast-fourier lattice-based compact signatures over NTRU［EB/OL］.［2022-09-30］.

[20] ZHANG J， YU Y， FAN S Q， et al. Tweaking the asymmetry of asymmetric-key cryptography on lattices： KEMs and signatures of smaller sizes［C］//IACR International Conference on Public-Key Cryptography. Cham： Springer， 2020： 37-65.10.1007/978-3-030-45388-6_2. DOI: 10.1007/978-3-030-45388-6_2 .

[21] 陈朝晖， 马原， 荆继武. 格密码关键运算模块的硬件实现优化与评估［J］. 北京大学学报（自然科学版）， 2021， 57（4）： 595-604. DOI： 10.13209/j.0479-8023.2021.054 .

[22] CHEN Z H， MA Y， JING J W. Hardware optimization and evaluation for crucial modules of lattice-based cryptography［J］. Acta Scientiarum Naturalium Universitatis Pekinensis， 2021， 57（4）： 595-604. DOI： 10.13209/j.0479-8023.2021.054（Ch ）.

[23] 李斌， 陈晓杰， 冯峰， 等. 后量子密码CRYSTALS-Kyber的FPGA多路并行优化实现［J］. 通信学报， 2022， 43（2）： 196-207. DOI： 10.11959/j.issn.1000-436x.2022026 .

[24] LI B， CHEN X J， FENG F， et al. FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber［J］. Journal on Communications， 2022， 43（2）： 196-207. DOI： 10.11959/j.issn.1000-436x.2022026（Ch ）.

[25] 吴志红， 赵建宁， 朱元， 等. 国密算法和国际密码算法在车载单片机上应用的对比研究［J］. 信息网络安全， 2019（8）： 68-75. DOI： 10.3969/j.issn.1671-1122.2019.08.010 .

[26] WU Z H， ZHAO J N， ZHU Y， et al. Comparative study on application of Chinese cryptographic algorithms and international cryptographic algorithms in vehicle microcotrollers［J］. Netinfo Security， 2019（8）： 68-75. DOI： 10.3969/j.issn.1671-1122.2019.08.010（Ch ）.

[27] DU C H， BAI G Q. Towards efficient polynomial multiplication for lattice-based cryptography［C］//2016 IEEE International Symposium on Circuits and Systems （ISCAS）. New York： IEEE Press， 2016： 1178-1181. DOI： 10.1109/ISCAS.2016.7527456 .

[28] FENG X， LI S G， XU S F. RLWE-oriented high-speed polynomial multiplier utilizing multi-lane stockham NTT algorithm［J］. IEEE Transactions on Circuits and Systems Ⅱ： Express Briefs， 2020， 67（3）： 556-559. DOI： 10.1109/TCSII.2019.2917621 .

[29] ZHOU Z， HE D B， LIU Z， et al. A software/hardware co-design of crystals-dilithium signature scheme［J］. ACM Transactions on Reconfigurable Technology and Systems， 2021，14（2）：Article No. 11. DOI： 10.1145/3447812 .

[30] 周朕， 何德彪， 罗敏， 等. 紧凑的Aigis-sig数字签名方案软硬件协同实现方法［J］. 网络与信息安全学报， 2021， 7（2）： 64-76. DOI： 10.11959/j.issn.2096-109x.2021026 .

[31] ZHOU Z， HE D B， LUO M， et al. Compact Aigis-sig digital signature scheme software and hardware co-implementation method［J］. Chinese Journal of Network and Information Security， 2021， 7（2）： 64-76. DOI： 10.11959/j.issn.2096-109x.2021026（Ch ）.

[32] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems［J］. Communications of the ACM， 1978， 21（2）： 120-126. DOI： 10.1145/359340.359342 .

[33] 陶云亭， 孔凡玉， 于佳， 等. 抗量子格密码体制的快速数论变换算法研究综述［J］. 信息网络安全， 2021， 21（9）： 46-51. DOI： 10.3969/j.issn.1671-1122.2021.09.007 .

[34] TAO Y T， KONG F Y， YU J， et al. Survey of number theoretic transform algorithms for quantum-resistant lattice-based cryptography［J］. Netinfo Security， 2021， 21（9）： 46-51. DOI： 10.3969/j.issn.1671-1122.2021.09.007（Ch ）.

[35] GÜNEYSU T， KRAUSZ M， ODER T， et al. Evaluation of lattice-based signature schemes in embedded systems［C］//2018 25th IEEE International Conference on Electronics， Circuits and Systems （ICECS）. New York： IEEE Press， 2019： 385-388. DOI： 10.1109/ICECS.2018.8617969 .

[36] KANNWISCHER M J， RIJNEVELD J， SCHWABE P， et al. pqm4： Testing and Benchmarking NIST PQC on ARM Cortex-M4［J］. IACR Cryptol EPrint Arch， 2019， 2019： 844. DOI: 10.1007/978-3-030-21568-2_14 .

[37] KANNAN R. Improved algorithms for integer programming and related lattice problems［C］//Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. New York： ACM， 1983： 193-206. DOI： 10.1145/800061.808749 .

[38] DON C. Small solutions to polynomial equations， and low exponent RSA vulnerabilities［J］. Journal of Cryptology， 1997， 10（4）： 233-260. DOI： 10.1007/s001459900030 .

[39] van EMDE BOAS P. Another NP-complete problem and the complexity of computing short vectors in a lattice［R］. Amsterdam： University of Amsterdam， 1981.

[40] AJTAI M. The shortest vector problem in L₂ is NP-hard for randomized reductions （extended abstract）［C］//Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. New York： ACM， 1998： 10-19. DOI： 10.1145/276698.276705 .

[41] HENK M. Note on shortest and nearest lattice vectors［J］. Information Processing Letters， 1997， 61（4）： 183-188. DOI： 10.1016/S0020-0190（97）00019-7 .

[42] MICCIANCIO D. Improving lattice based cryptosystems using the Hermite normal form［C］//Cryptography and Lattices（LNCS 2146）. Berlin： Springer， 2001： 126-145. DOI： 10.1007/3-540-44670-2_11 .

[43] GROOT BRUINDERINK L， HÜLSING A， LANGE T， et al. Flush， Gauss， and reload―A cache attack on the BLISS lattice-based signature scheme［C］//International Conference on Cryptographic Hardware and Embedded Systems. Berlin： Springer， 2016： 323-345. DOI： 10.1007/978-3-662-53140-2_16 .

[44] PESSL P， BRUINDERINK L G， YAROM Y. To BLISS-B or not to be： Attacking strongSwan’s implementation of post-quantum signatures［C］//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2017： 1843-1855. DOI： 10.1145/3133956.3134023 .

[45] LIANG Z C， ZHAO Y L. Number theoretic transform and its applications in lattice-based cryptosystems： A survey［EB/OL］. 2022： arXiv： 2211.13546.

基金资助

国家重点研发计划(2022YFB4500800)

中央高校基本科研业务费专项资金(2042022kf0021)

先进密码技术与系统安全四川省重点实验室开放课题(SKLACSS-202203)