随着大数据时代的到来，数据已成为生产生活中网络通信的核心资源，数字签名技术是确保互联网通信数据安全的关键技术. 量子计算机的发展给传统数字签名带来了量子攻击的风险，Shor算法^[1]可以求解整数分解和离散对数问题，王亚辉等^[2]提出的相位估计量子算法能够解决RSA难题. 美国国家标准技术研究院（NIST）指出：2030年停止新增部署传统签名算法，2035年全面废止^[3]. CRYSTALS-Dilithium因无须依赖陷门且安全性高的优势被NIST正式标准化，但该方案签名阶段需要复杂的格运算，计算开销较高，难以适配资源受限、低延迟需求的场景.

针对上述效率瓶颈，Even等^[4]提出的在线/离线签名技术备受关注. 在后量子迁移方面，Yao等^[5]提出Γ_协议为实现无陷门签名的在线离线奠定基础，Zhang等^[6-7]首次提出基于qTESLA格的在线/离线签名方案，但qTESLA未通过NIST的安全评估；王后珍等^[8]基于在线/离线技术设计Olithium格签名方案，提升了在线签名效率，但离线阶段存在资源冗余和存储开销大的问题. 在资源调度优化方面，谢志强等^[9]和阿里云^[10]分别基于内存利用率和排队时间设计动态资源调度策略，通过监测负载实现了资源的高效利用. Xue等^[11]利用CPU空闲时段动态生成预计算资源，Lai等^[12]优化预计算存储格式，Liu等^[13]通过复用中间值减少存储开销，但这些方案均无法抵御量子攻击或仍存在侧信道隐患. Zhang等^[14]面向资源受限的边缘物联网提出后量子安全的边缘联邦学习框架，利用后量子标准签名算法完成身份认证，虽然满足后量子安全，但是签名算法效率低. 在格运算优化方面，Lyubashevsky等^[15]提出2n次单位根型NTT，中国科学院^[16]提出PtNTT算法，Tan等^[17]和郭俊等^[18]分别从软硬件协同和并行化角度优化NTT运算，为提升格基签名性能提供了技术基础.

针对上述问题，本文提出基于动态预计算的高效格基在线/离线签名算法DP-Olithilum，通过禁止离线资源复用来保证密码安全属性，满足资源受限、低延迟场景的需求.

格密码的设计主要基于小整数解(short integer solution，SIS) ^[19]和错误学习(learning with errors，LWE) ^[20]困难问题. 由于结构化矩阵能够减小密钥规模，且更适用于后量子密码，衍生了模格难题^[21].

定义1　格Λ. 格基矩阵$ \boldsymbol{A}\in {\bf{R}}^{n\times m} $是由$ m $个线性无关的$ n $维向量$ {\boldsymbol{a}}_{1},{\boldsymbol{a}}_{2},\cdots ,{\boldsymbol{a}}_{m}\in {\bf{R}}^{n} $（称为格基）组成的矩阵，由它生成的格$ \textit{Λ}(\boldsymbol{A}) $定义为

(1)$ \textit{Λ}(\boldsymbol{A})=\left\{\boldsymbol{y}\in {\bf{R}}^{n}\left|{\boldsymbol{y}=\boldsymbol{Ac}=\sum\limits_{i=1}^{m}{c}_{i}{\boldsymbol{a}}_{i},\boldsymbol{c}\in {\bf{Z}}^{m}}\right.\right\}. $

定义2　模的小整数解(module-SIS, MSIS). 已知矩阵$ \boldsymbol{A}\in {\bf{R}}_{}^{k\times l} $，寻找非零向量$ \boldsymbol{z}\in {{\boldsymbol{R}}}_{q}^{l} $(其中${\boldsymbol{R}} _q^l$为l维R_q环，R_q为Z_q[x]/(xⁿ+1)的多项式环，Z_q[x]=${\displaystyle \sum}_{i=0}^{n-1}w_ix^{n-1} $，w_i为整数），使得$ \boldsymbol{A}\boldsymbol{z}={\boldsymbol{0}}\left(\text{mod }q\right) $，且$ \| \boldsymbol{z}{\| }_{\infty } \leqslant B $.

定义3　模的错误学习(module-LWE, MLWE). 已知矩阵$ \boldsymbol{A}\in {{\boldsymbol{R}}}_{q}^{k\times l} $和$ \boldsymbol{b}\in {{\boldsymbol{R}}}_{q}^{k} $，寻找秘密向量$ \boldsymbol{s}\in {{\boldsymbol{R}}}_{q}^{l} $和噪声向量$ \boldsymbol{e}\in {{\boldsymbol{R}}}_{q}^{k} $，使得$ \boldsymbol{A}\boldsymbol{s}+\boldsymbol{e} \equiv \boldsymbol{b}\left(\text{mod }q\right) $，且$ ||\boldsymbol{e}{||}_{\infty } \leqslant B $.

在线/离线签名一般由4个算法构成.

1）$ \text{KeyGen(}{{\boldsymbol{1}}}^{\lambda })\to \bf{(sk, pk)} $：密钥生成算法输入安全参数$ \lambda $，输出签名私钥sk和验证公钥pk.

2）$ \text{Signoff} ({\bf{sk}})\to{{\textit{φ}}} $：离线签名算法在未收到消息时预计算并生成中间值${{\textit{φ}}} $.

3）$ \text{Signon} ({\bf{sk}},\; M, {{\textit{φ}}} )\to{\boldsymbol{\sigma}} $：在线签名算法在收到消息M后，利用中间值计算最终签名${\boldsymbol{\sigma}} $.

4）$ \text{Verify}({\bf{pk}},\;M ,\;{\boldsymbol{\sigma}} )\to \text{{0,1}} $：该算法输入公钥和消息签名对，若签名有效，则输出1；否则输出0.

为了评估方案的安全性，基于选择消息攻击强存在不可伪造模型^[22]（strong existential unforgeability under chosen-message attack, SUF-CMA）进行安全分析.

定义4　SUF-CMA敌手优势可以表示为

(2)$\begin{split} &{\mathrm{Adv}}^{\text{SUF-CMA}}= \\& \quad P \left(\text{Verify}({\bf{pk}},\;{M},\;{{\boldsymbol{\sigma}} })=1\left|({\bf{pk}},{\bf{sk}})\leftarrow {\mathrm{KeyGen}}(\lambda ),\right.\right.\\&\quad \left.({M},{{\boldsymbol{\sigma}} })\leftarrow {\cal{A}}^{{{O}_{{\mathrm{s}}}}}\text{(pk),}\;({M},{{\boldsymbol{\sigma}} }) \notin {L}_{\text{query}}\right).\end{split}$

式中：O_s为签名谕言机，L_query为对应的Hash列表. 敌手利用$ {({\bf{pk}},{\bf{sk}})生成(}{M},{{\boldsymbol{\sigma}} }) $. 若$ \text{Verify}({\bf{pk}},\;{M},\;{{\boldsymbol{\sigma}} })=1 $且$ ({M},{{\boldsymbol{\sigma}} })\notin {L}_{\text{query}} $，则敌手获胜. 若该优势可忽略，则说明签名方案安全.

无陷门格基签名方案依赖拒绝采样技术. 签名时计算挑战值与响应值，若响应值范数超出阈值则重启，直至合法. 重启涉及复杂的矩阵向量乘法，会显著增加在线时延与计算开销. 通过将此类运算移至离线阶段，并预生成足够的中间值，可以避免重启，从而提升实时效率. 同时，拒绝采样所需中间值组数具有动态不确定性，单次即能满足或须多次重试的情况均可能发生. 针对拒绝采样所需中间值数量的不确定性，本方案DP-Olithium利用在线/离线技术，确保即使拒绝采样失败，也无须重启整个过程，仅须读取下一组中间值重新判定，从而降低签名重启频率. 设计动态预计算策略，实现在线签名阶段中间值的动态增加，确保预计算资源池充足且无冗余，从而减轻预计算负担，降低存储开销. 为了防止私钥信息泄露，方案禁止中间值复用.

验证端利用$ {\boldsymbol{w}}_{1}' $完成签名验证，该过程的核心运算是$ \boldsymbol{A}\boldsymbol{z}-c{\boldsymbol{t}}_{1}{2}^{d} $，NTT变换是实现高效矩阵向量乘法的基础. 标准NTT采用AOS布局，以多项式向量为存储单元，对多项式向量逐个执行NTT变换. 该串行模式须重复加载旋转因子常数表，多次执行完整的蝶形运算，计算效率较低. 本方案DP-Olithium采用并行处理一次性完成8路运算，矩阵A为公开参数，无须动态更新；转换至NTT域后，一次性预缓存至内存即可复用. 综合上述优化，本方案仅须加载一次旋转因子常数表，理论上可以将计算效率提高8倍，有效降低验证阶段的时间开销.

密钥生成算法利用随机种子ρ和扩展函数生成$ k\times l $的矩阵$ \boldsymbol{A} $和私钥向量$ ({\boldsymbol{s}}_{1},{\boldsymbol{s}}_{2}) $，$ \boldsymbol{A} $和$ ({\boldsymbol{s}}_{1},{\boldsymbol{s}}_{2}) $的元素都是$ {{R}}_{q}$环上的多项式. 计算公钥$ \boldsymbol{t}=\boldsymbol{A}{\boldsymbol{s}}_{1}+{\boldsymbol{s}}_{2} $，利用二次幂分解函数$ {\text{Power2Round}}_{{q}} $分解出高位$ {\boldsymbol{t}}_{1}\text{和低位}{\boldsymbol{t}}_{0} $，最终输出公私钥对.

算法1　密钥生成算法

其中，H为哈希函数，ExpandA为矩阵生成函数，ExpandS为向量扩展函数，利用种子均匀随机选取私钥向量.

离线阶段所有计算仅依赖私钥和随机种子，可以提前完成计算量大的矩阵乘法运算$ \boldsymbol{w}{\;=\;}\boldsymbol{Ay} $. 为了降低存储开销并避免因预计算值耗尽而导致签名重启，本方案对离线阶段设计了动态预计算机制，利用阈值触发，并采用固定增量策略生成$ \Delta {\rm{EE}} $组中间值，同时同步更新中间值资源的总量$ {\mathrm{avail}} $.

算法2　动态预计算资源管理函数$ \text{EnsureEE} $

其中，ExpandMask为向量扩展函数，利用种子均匀随机选取掩码向量；Decompose_q为高低位比特分解函数.

算法3　离线签名算法

在线签名阶段利用消息计算$ \boldsymbol{z}=\boldsymbol{y}+c{\boldsymbol{s}}_{1} $，完成拒绝采样的范数校验，生成提示位和签名$ \sigma =(c,\boldsymbol{z},\boldsymbol{h}) $. 整个过程中，用$ \text{used} $记录拒绝采样过程消耗的中间值个数，并实时监测资源池样本数$ \text{avail} $. 当$ \text{used}> \text{avail}-2 $时，判定中间值余量是否低于阈值1，若低于阈值，说明触发$ \text{EnsureEE} $生成$ \Delta {\mathrm{EE}} $组中间值. 由于中间值包含私钥信息，为了保证密码的安全性，禁止中间值复用；每组中间值被使用后，立即通过随机数据覆盖并执行消除操作，以防止因复用而导致侧信道信息累积.

算法4　在线签名算法$ \text{} $

其中，MakeHint_q为提示位生成函数，SampleInBall为球形采样函数.

验证的计算核心是$ {\boldsymbol{w}}^{\text{'}}=\boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1} $，先查验是否已缓存矩阵$ \boldsymbol{A} $，若未缓存，则利用种子$ \rho $生成，否则直接使用缓存的矩阵完成矩阵向量乘法. 然后计算消息哈希值，并利用球内采样算法获取挑战值，根据提示向量计算恢复$ \boldsymbol{w} $的高阶比特$ {\boldsymbol{w}}^{\text{'}} $，通过第8行的条件来验证签名的合法性. 上述函数的具体实现参考文献[23].

算法5　签名验证算法

其中，UseHint_q为提示位使用函数.

$ {\boldsymbol{A}}\boldsymbol{z}-{2}^{d} c{\boldsymbol{t}}_{1}$的计算采用并行化批NTT变换算法，该算法通过调整数据布局和循环结构实现Cooley-Tukey蝶形运算的并行操作. 输入多项式向量及公开旋转因子表，输出NTT变换后的多项式向量. 3层嵌套循环完成内部并行运算：最外层循环用于初始化蝶形层级参数，中层循环负责确定层级数据的起始索引，最内层实现8个并行蝶形运算. Bitrev函数完成比特逆序重排，MontgomeryReduce执行模约减运算，具体实现见文献[23].

算法6　并行化批NTT算法

其中，layer为蝶形运算层级，len为蝶形运算步长.

方案通过以下3个条件验证签名的合法性：1）$ {\left|\left|\boldsymbol{z}\right|\right|}_{\infty }{<{\gamma }}_{1}-{\beta } $；2）$ \tilde{\boldsymbol{c}}{=H(}\boldsymbol{\mu }||\boldsymbol{w}_{1}^{\text{'}}) \oplus \tilde{\boldsymbol{k}} $；3）$ {\left|\left|\boldsymbol{h}\right|\right|}_{1} \leqslant \boldsymbol{\omega } $.

条件1）和3）在签名过程中已通过拒绝采样得到满足，因此只须保证条件2）正确，即证明$ \boldsymbol{w}_{1}^{\text{'}}={\boldsymbol{w}}_{1} $.

引理1^[23]　假设r和$ \boldsymbol{z} $是$ {{R}}_{{q}} $上的多项式向量，$ \boldsymbol{h} $和$ {\boldsymbol{h}}^{{'}} $是生成的提示向量，若满足$ {\left|\left|\boldsymbol{z}\right|\right|}_{\infty }<\textit{α}/2 $且$ {q}>2\textit{α} $，则有$ {\text{UseHint}}_{{q}}\text{(MakeHin}{\text{t}}_{{q}}(\boldsymbol{z},\boldsymbol{r},\textit{α),}\boldsymbol{r},\textit{α)=}{\text{HighBits}}_{{q}}(\boldsymbol{z}+\boldsymbol{r},\textit{α)} $.

引理2^[23]　假设r和$ {\boldsymbol{s}} $是$ {{R}}_{{q}} $上的多项式向量，若满足$ {\left|\left|\boldsymbol{s}\right|\right|}_{\infty }<{\beta } $且$ \text{LowBit}{\text{s}}_{{q}}(\boldsymbol{r}\textit{,α)<α}/2-{\beta } $，则有$ {\text{HighBits}}_{{q}}(\boldsymbol{r},\textit{α})={\text{HighBits}}_{{q}}(\boldsymbol{r}+\boldsymbol{s},\textit{α} )$.

对于算法4签名验证第7行的核心运算$ {{\boldsymbol{w}}}_{1}^{\text{'}}={\text{UseHint}}_{{q}}({{\boldsymbol{h}}},{{\boldsymbol{A}}}{{\boldsymbol{z}}}-{2}^{{d}}{c}{{{\boldsymbol{t}}}}_{1},2{{\gamma }}_{2}) $，结合关系式$ {{\boldsymbol{w}}}={{{{\boldsymbol{A}}}{{\boldsymbol{y}}} }}$，$ {{\boldsymbol{z}}}={{\boldsymbol{y}}}+{c}{{{\boldsymbol{s}}}}_{1} $，$ {{\boldsymbol{t}}}={{\boldsymbol{A}}}{{{\boldsymbol{s}}}}_{1}+{{{\boldsymbol{s}}}}_{2}={{{\boldsymbol{t}}}}_{0}+{2}^{{d}}{{{\boldsymbol{t}}}}_{1} $，可得

(3)$\begin{split} \boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1}=&\boldsymbol{A}\boldsymbol{z}-c(\boldsymbol{t}-{\boldsymbol{t}}_{0})=\boldsymbol{A}\boldsymbol{y}-c{\boldsymbol{s}}_{2}+c{\boldsymbol{t}}_{0}=\\&\boldsymbol{w}-c{\boldsymbol{s}}_{2}+c{\boldsymbol{t}}_{0} .\end{split}$

由引理1可知，当$ {\left|\left|c{\boldsymbol{t}}_{0}\right|\right|}_{\infty } \leqslant {\gamma }_{2} $时，有$ {\text{UseHint}}_{q}(\boldsymbol{h}, \boldsymbol{w}-c{\boldsymbol{s}}_{2}+c{\boldsymbol{t}}_{0}, 2{\gamma }_{2})={\text{HighBits}}_{{q}}(\boldsymbol{w}-c{\boldsymbol{s}}_{2}, 2{\gamma }_{2}) $，其中 $ \boldsymbol{h}= \text{MakeHin}{\text{t}}_{q}(\boldsymbol{r}+c{\boldsymbol{t}}_{0},{\boldsymbol{w}}_{1},{\gamma }_{2}) $. 验证方可以计算

(4)$\begin{split} \boldsymbol{w}_{1}^{\text{'}}=\;&{\text{UseHint}}_{q}(\boldsymbol{h},\boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1},2{\gamma }_{2}) =\\ &{\text{UseHint}}_{q}(\boldsymbol{h},\boldsymbol{w}-c{\boldsymbol{s}}_{2}+c{\boldsymbol{t}}_{0}, 2{\gamma }_{2}) =\\ &{\text{HighBits}}_{\text{q}}(\boldsymbol{w}-c{\boldsymbol{s}}_{2},~2{\gamma }_{2}) .\end{split}$

根据引理2可知，因为方案设计中满足$ {\left|\left|c{\boldsymbol{s}}_{2}\right|\right|}_{\infty } \leqslant \beta $且$ \text{LowBit}{\text{s}}_{q}(\boldsymbol{w}-c{\boldsymbol{s}}_{2}, 2{\gamma }_{2})<{\gamma }_{2}-\beta $，可得

(5)$ {\text{HighBits}}_{\text{q}}(\boldsymbol{w}-c{\boldsymbol{s}}_{2},~2{\gamma }_{2})={\text{HighBits}}_{\text{q}}(\boldsymbol{w},2{\gamma }_{2})={\boldsymbol{w}}_{1}. $

综上所述，根据式(3)~(5)可知，验证算法中输出的$ \boldsymbol{w}_{1}^{\text{'}} $与签名者在离线签名算法中得到的$ {\boldsymbol{w}}_{1} $相同，故该方案的正确性得证.

本方案沿用Fiat-Shamir with Aborts (FSwA)签名框架，并与Dilithium的安全参数保持一致.

引理3^[24]　假设$ {\mathcal{A}}$是针对Fiat-Shamir with Aborts签名方案的EF-CMA选择消息攻击敌手，则存在EF-NMA无消息攻击敌手$ {\mathcal{B}}， $满足：$ \text{Adv}^{\text{EF-CMA}}(\mathcal{A}) \leqslant \text{Adv}^{\text{EF-NM}}(\mathcal{B}) $.

引理4^[24]　若签名在EF-CMA与EF-NMA下均具备不可伪造性，则签名满足SUF-CMA.

定理1　对于每一个攻破NMA安全性的敌手$ {\mathcal{A}} $，可以构造MLWE敌手$ \cal{B} $和MSIS敌手$ \mathcal{C} $，满足：$ {\text{Adv}}^{\text{EF-CMA}}(\mathcal{A}) \leqslant {\text{Adv}}^{\text{MLWE}}(\mathcal{B})+{\text{Adv}}^{\text{MSIS}}(\mathcal{C}) $.

证明：针对敌手$ \cal{B} $，在密钥生成算法中均匀随机采样公钥中的向量$ {\boldsymbol{t}}^{\text{'}} $，用以替代原始公钥生成方式$ \boldsymbol{t}=\boldsymbol{A}{\boldsymbol{s}}_{1}+{\boldsymbol{s}}_{2} $. 根据LWE困难问题假设，公钥$ (\boldsymbol{A},{\boldsymbol{t}}^{\text{'}}) $和$ (\boldsymbol{A},\boldsymbol{t}) $是计算不可区分的，因此可以将该方案的安全性归约到LWE问题.

针对敌手$ \mathcal{C} $，构造归约算法C，使得每当敌手$ (\boldsymbol{A},{\boldsymbol{t}}^{\text{'}}) $成功伪造一个签名消息对$ \left\{M,(\mathit{c},\boldsymbol{z},\boldsymbol{h})\right\} $且该签名通过验证$ \mathit{c}={H}(\mathit{\mu }||{\boldsymbol{w}}_{1},M) $时，就能输出一个有效的SIS问题解$ {\boldsymbol{r}}^{\text{'}} $. 该算法的具体步骤如下.

1）给定一个SIS实例矩阵$ {\boldsymbol{A}}^{\mathit{'}} $，其维度为$ \mathit{k}\times l+1 $.

2）拆分$ {\boldsymbol{A}}^{\mathit{'}} $的最后一列并取负值，得到$ {\boldsymbol{A}}^{\mathit{'}}=(\boldsymbol{A},\boldsymbol{t}) $. 该矩阵满足均匀随机采样，将其作为公钥发送给敌手$ \mathcal{C} $.

3）随机谕言机$ {{H}}^{\text{'}}({\boldsymbol{w}}_{1},M{)=G(}{\text{shift}}_{\mathit{\alpha }}({\boldsymbol{w}}_{1}),M)， $完成哈希查询.

4）输出解$ {\boldsymbol{r}}^{} $.

根据哈希函数结构与输出的独立性，对于固定的${M} $，该问题仍然困难. 短向量$ {\boldsymbol{r}}^{\text{'}}=(({\boldsymbol{u}}_{1}-{\boldsymbol{u}}_{2})\mid \boldsymbol{z}\mid c) $即为算法C的解，其中$ {\boldsymbol{u}}_{1}=\boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1}-{\text{shift}}_{\alpha }\left({\boldsymbol{w}}_{1}\right) $，$ {\boldsymbol{u}}_{2}=c(\boldsymbol{t}-{2}^{d}{\boldsymbol{t}}_{1}) $，此时有

(6)$ \begin{split} {{H}}^{\text{'}}({\boldsymbol{w}}_{1},M) =&{{H}}^{\text{'}}\left({\text{UseHint}}_{\text{q}}(\boldsymbol{h},\boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1},2{\gamma }_{2}),M\right)=\\ &{G({\boldsymbol{A}}}\boldsymbol{z}-c\boldsymbol{t}+({\boldsymbol{u}}_{1}-{\boldsymbol{u}}_{2}),M)=\\ & {G([}{{{\boldsymbol{I}}}}_{k}|\boldsymbol{A}|-\boldsymbol{t}]\cdot {\boldsymbol{r}}^{\text{'}},M) =\\ &{G([}{{{\boldsymbol{I}}}}_{k}|{\boldsymbol{A}}^{\text{'}}]\cdot {\boldsymbol{r}}^{\text{'}},M).\end{split} $

求解$ {\boldsymbol{r}}^{} $的值可以规约为求解$ [{\boldsymbol{I}}_{k}|{\boldsymbol{A}}^{\text{'}}]\cdot {\boldsymbol{r}}^{\text{'}}=0 $中的短向量，即SIS困难问题.

综上所述，通过将敌手$ \text{B} $和$ \mathcal{C} $规约为格困难问题，再结合引理3和引理4，可以证明该方案在EF-CMA与EF-NMA下均具有不可伪造性，从而在量子随机谕言机模型下满足SUF-CMA安全性.

侧信道攻击是指攻击者不依赖密码算法本身的数学缺陷，通过利用物理设备在运行中泄露的、与敏感数据相关的侧信道信息，获取敏感信息. 下面对本方案的侧信道安全性进行分析.

1）本方案的动态预计算机制中，资源池和增量均为固定值，消除了因资源池容量调整和中间值生成幅度随机变化而导致的侧信道信息泄露；禁止中间值复用的策略进一步防止了侧信道信息累积.

2）并行化批NTT是对NTT内部运算的并行化，不改变内部运算的运算模式，即无条件运算模式，因此不会带来额外的侧信道安全问题.

3）针对矩阵预缓存命中差异可能导致的时序攻击，采用固定延迟补偿策略：无论缓存是否命中，均在关键运算节点插入标准化的空操作序列，确保运算耗时保持恒定，从而保证时序侧信道安全.

为了进行系统性性能分析，定义失败率、重试次数和单次签名成功概率. 失败率指中间值未通过拒绝采样而导致签名重启的概率；重试次数指为满足拒绝采样的范数条件所消耗的中间值组数；单次签名成功概率指仅用一组中间值成功签名的概率. 在本方案中，在线签名阶段拒绝采样的阈值为$ {\left|\left|\boldsymbol{z}\right|\right|}_{\infty }{<\mathit{\gamma }}_{1}-\mathit{\beta } $和$ {\left|\left|{{\boldsymbol{r}}}_{0}\right|\right|}_{\infty }< {\gamma }_{2}-\beta $. 由$ {\left|\left|\boldsymbol{z}\right|\right|}_{\infty }={{\left|\left|\boldsymbol{y}+\text{c}{\boldsymbol{s}}_{1}\right|\right|}_{\infty }}< {\gamma }_{1}- \beta $可知，$ \boldsymbol{y}+\text{c}{\boldsymbol{s}}_{1} $的区间大小为$ 2({\gamma }_{1}{-\beta )-1} $，$ \boldsymbol{y} $的区间大小为$ 2{\gamma }_{1}-1 $，因此$ {\left|\left|\boldsymbol{z}\right|\right|}_{\infty }{<\gamma }_{1}-\beta $成立概率为

(7)$ {{P}}_{{{\left|\left|\boldsymbol{z}\right|\right|}_{\infty }}}={\left(\frac{2\left({\gamma }_{1}-\beta \right)-1}{2{\gamma }_{1}-1}\right)}^{256l}={\left(1-\frac{\beta }{{\gamma }_{1}-0.5}\right)}^{256l}. $

由$ {\left|\left|{\boldsymbol{r}}_{0}\right|\right|}_{\infty }={\left|\left|\text{LowBit}{\text{s}}_{q}(\boldsymbol{w}-c{\boldsymbol{s}}_{2}, 2{\gamma }_{2})\right|\right|}_{\infty }<{\gamma }_{2}-\beta $可知，$ {\boldsymbol{r}}_{0} $的区间大小为$ 2({\gamma }_{2}-\beta )-1 $，又因为$ \text{LowBit}{\text{s}}_{q} $的区间大小为$ 2{\gamma }_{2} $，$ {\left|\left|{\boldsymbol{r}}_{0}\right|\right|}_{\infty }<{\gamma }_{2}-\beta \text{成立的} $概率为

(8)$ {{P}}_{{{\left|\left|{\boldsymbol{r}}_{0}\right|\right|}_{\infty }}}={\left(\frac{2({\gamma }_{2}-\beta )-1}{2{\gamma }_{2}}\right)}^{256k}. $

当$ {\gamma }_{1}\gg 1/2 $且$ \beta \gg 1/2 $时，代入式$ (7)、(8) $，可得通过拒绝采样的概率为

(9)$ {P}={{P}}_{{{\left|\left|\boldsymbol{z}\right|\right|}_{\infty }}}\cdot {{P}}_{{{\left|\left|{\boldsymbol{r}}_{0}\right|\right|}_{\infty }}}={{\mathrm{exp}}}\;{[{-256 \beta }\left(\text{l}/{\gamma }_{1}{+\;k}/{\gamma }_{2}\right)]}. $

根据文献[23]代入具体的参数值，不同中间值组数$ N $对签名成功概率P的影响如表1所示.

从表1可知，单次签名失败率在NIST-2/3/5等级下分别为76.50%、80.34%和74.04%，当预计算生成5组中间值时，各安全等级下签名成功概率均大于1/2. 基于每组中间值的拒绝采样成功相互独立的假设，根据下式计算重试次数上界：

(10)$ 1-{\left(1-{P}_{N=1}\right)}^{G} \geqslant P .$

式中：$ {P}_{N=1} $为单组中间值未通过拒绝采样的概率，$G $为重试次数上界. 不同置信度下的重试次数上界G对比如表2所示.

当置信度为99%时，重试次数上界表示若要求签名成功率为99%，则拒绝采样所需的中间值组数分别为17、22和16. 以NIST-3为例，当重试上界设置为10组时，签名成功概率大幅提升；设置为15组时，签名成功概率可达96%，此时采用固定增量为5组中间值所获得的效益最为明显.

公钥$ {{\bf{pk}}=(}\rho ,{\boldsymbol{t}}_{1}) $的大小为$ 32+320k $字节，其中包含256位随机种子$ \rho $以及$ k $维向量$ \boldsymbol{t} $的幂分解高位向量$ {\boldsymbol{t}}_{1} $；私钥$ {{\bf{sk}}=(}K,\rho ,{\mathrm{tr}},{\boldsymbol{s}}_{1},{\boldsymbol{s}}_{2},{\boldsymbol{t}}_{0}) $的大小为$ 96+ 32(k+l) \left\lceil \log_2 (2\eta +1)\right\rceil+416k $字节，其中包含$ \rho 、{\mathrm{tr}}、K $（各占256位），满足特定分布的$ l $维向量$ {\boldsymbol{s}}_{1} $和$ k $维$ {\boldsymbol{s}}_{2} $以及幂分解低位向量$ {\boldsymbol{t}}_{0} $；签名$ {\boldsymbol{\sigma}} =(\tilde{c},\boldsymbol{z},\boldsymbol{h}) $的大小为$ 32+ 32l \left(1+\log_2 (2{\gamma }_{1})\right)+\omega +k $字节，其中包含256位$ c $、$ l $维向量$ \boldsymbol{z} $和提示生成值$ \boldsymbol{h} $. 中间值$ {{\textit{φ}}} = (\tilde{c},\boldsymbol{y},{\boldsymbol{w}}_{0},{\boldsymbol{w}}_{1}) $，其中$ \tilde{c} $占用32字节；向量$ \boldsymbol{y} $的系数范围为$ \left({-\gamma }_{1},{\gamma }_{1}\right) $，在NIST-2时$ {\gamma }_{1}={2}^{17} $，$ \boldsymbol{y} $占用576$ l $字节，NIST-3和NIST-5时$ \boldsymbol{y} $占用640$ l $字节；向量$ {\boldsymbol{w}}_{0} $在NIST-2时占用576$ k $字节，NIST-3和NIST-5时占用608$ k $字节；$ {\boldsymbol{w}}_{1} $的系数小于$ q-1/2{\gamma }_{2} $，NIST-2时$ {\boldsymbol{w}}_{1} $占用192$ k $字节，在NIST-3和NIST-5时$ {\boldsymbol{w}}_{0} $占用128$ k $字节. 不同安全等级下密钥、签名和中间值的尺寸如表3所示. 其中，S_pk为公钥的尺寸，S_sk为私钥的尺寸，S_σ为签名的尺寸，S_φ为每组中间值的尺寸.

随着中间值组数N的增加，本方案与其他方案在签名阶段的存储开销S对比如表4所示. 考虑到本方案每次增加5组预计算中间值的策略，不同方案签名阶段存储开销随N的变化情况如图1所示.

分析图1可知，与Dilithium签名方案相比，本方案在签名阶段的存储开销有所增加，但能避免签名重启带来的计算开销；与Olithium签名方案相比，在单次签名成功的前提下，本方案的离线存储开销最高可以减少66%，签名阶段总开销最高可以减少52%. 上述存储开销的优化，使本方案更适用于设备资源受限的场景.

验证端采用预缓存机制存储矩阵的NTT域变换结果. 由于该矩阵为公开参数且无须动态更新，仅须预缓存转换为NTT域的矩阵，以便验证签名多次复用. 缓存项即为矩阵所有多项式的系数，内存开销可以表示为(klL)×$\left\lceil {{\text{log}}}_2 q\right\rceil $，对应的空间复杂度为O(klL)，其中k为格基矩阵的行数，l为格基矩阵的列数，L为单个多项式的系数长度，q为格基模数，$\left\lceil {{\text{log}}}_2 q\right\rceil $为系数位宽. 根据Dilithium标准要求，L=256，q=8380417；在NIST-2时(k, l) = (4, 4)，NIST-3时(k, l) = (6, 5)，NIST-5时(k, l) = (8, 7). 不同安全等级下的存储开销如表5所示. 其中，S′为验证阶段的存储开销.

从表5可知，存储上界约为40.25 kB，低于端侧设备的常规可用内存，可以满足资源受限场景的部署需求. 即便同时采用3种安全等级，本文方案的总存储开销上界增加约73.25 kB，仍处于可接受范围内，且不会影响验证效率.

$ \boldsymbol{w}_{1}^{\text{'}}={\text{UseHin}t}_{q}(\boldsymbol{h},\boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1},2{\gamma }_{2}) $是验证的核心运算，计算开销主要来源于包含NTT变换的矩阵向量乘法$ \boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1} $，该运算也是验证阶段的主要效率瓶颈. 该运算涉及NTT域矩阵$ \boldsymbol{A} $的生成，$ \boldsymbol{z}、c、{\boldsymbol{t}}_{1} $的NTT变换以及模乘、模加等操作；此外，整个验证过程还包含哈希、解包、上传等轻量操作. $ 令{T}_{\text{add}} $表示矩阵向量乘法中的模加操作开销，$ {T}_{\text{mul}} $表示矩阵向量乘法中的模乘操作开销，$ {T}_{\text{zeta}} $表示旋转因子表的加载操作开销. 不同方案在验证阶段矩阵向量乘法的计算开销T对比如表6所示.

在Dilithium和Olithium中，验证阶段对每个多项式独立进行NTT变换，且都需要重复加载旋转因子常数表，因此$ l $维多项式向量的NTT计算开销为$ 1\;024l\left({T}_{\text{add}}+2{T}_{\text{mul}}\right)+l\cdot {T}_{\text{zeta}} $. NIST-2时，$ l=4 $，计算开销为$ 4\;096{T}_{\text{add}}+8\;192{T}_{\text{mul}}+4{T}_{\text{zeta}} $；NIST - 3时，$ l=5 $，开销为$ 5\;120{T}_{\text{add}}+10\;240{T}_{\text{mul}}+5{T}_{\text{zeta}} $；NIST - 5时，$ l=7 $，开销为$ 7\;168{T}_{\text{add}}+14\;336{T}_{\text{mul}}+7{T}_{\text{zeta}} $. DP-Olithium采取并行化批NTT变换，计算开销不受向量维度的影响，理想情况下的计算开销为$ 1\;024{T}_{\text{add}}+2\;048{T}_{\text{mul}}+ {T}_{\text{zeta}} $. 该方案利用并行化批NTT变换，将矩阵向量乘法的复杂度从传统的$ O(lN\log N) $降低至$ O(N\log N) $，通过8路蝶形运算并行，在理想条件下可以将矩阵向量乘法加速8倍.

使用C语言实现本方案DP-Olithium，并与Dilithium和Olithium方案进行对比. 测试平台配置如下：AMD Ryzen 5 4600H with Radeon Graphics，内存为32 GB，操作系统为Kali Linux-6.12.25-amd64. 在NIST不同安全等级下完成实验仿真，消息随机生成，各方案分别执行10万次签名操作并取平均值，不同安全等级下各方案各阶段的时间开销如表7和图2所示. 其中，$ {T}_{\text{keygen}} $、$ {T}_{\text{offline}} $、$ {T}_{\text{online}} $、$ {T}_{\text{verify}} $分别为密钥生成、离线签名、在线签名和签名验证的时间开销. 将验证阶段拆分为4种操作：生成矩阵A、NTT和逆NTT、模乘模加运算、其他轻量运算. 各操作的时间开销分别用T_A、T_NTT、T_mod、T_other表示，具体数值如表8所示.

分析图2可知，3种方案在密钥生成阶段的耗时基本一致，这与理论分析相符——该阶段的计算开销仅由格基密码的核心算法复杂度决定，不受预计算及验证优化策略的影响. 在离线签名阶段，Olithium为避免在线阻塞须预生成大量中间值，在NIST-5下离线耗时高达4608 μs. 本方案通过动态预计算机制，仅在拒绝采样次数超出阈值时动态生成5组中间值，在NIST-5下离线耗时为1795 μs，较Olithium减少61%；在NIST-2和NIST-3下分别为805、1467 μs，分别降低了63%和53.6%. 由此可见，该方案在有效减少存储冗余的同时显著提升了离线计算效率. 在在线签名阶段，本方案与Olithium耗时相近，两者均显著低于Dilithium，这表明动态预计算机制在降低离线开销的同时能够保证在线签名效率.

结合表6和表7分析签名验证阶段可知，预缓存NTT域矩阵A显著降低了生成矩阵A的时间开销，在NIST-2、NIST-3、NIST-5下分别加速3.46倍、3.38倍和3.44倍. 并行化批NTT采用8路并行蝶形运算，使得模加与模乘运算在3种安全等级下的加速效果均接近8倍. NTT相关操作总耗时在NIST-2、NIST-3、NIST-5下分别加速6.82倍、6.55倍和6.40倍，未达到理论峰值，这可能与数据读取延迟有关. 本方案验证阶段耗时在NIST-2下为32 μs，较传统方法降低65%，在NIST-3下降低67%，在NIST-5下降低68%. 综合对比可知，本方案较好地平衡了存储与计算开销，既避免了Dilithium因重启签名而带来的额外计算开销，又避免了Olithium中间值冗余造成的存储浪费. 随着安全等级的提高和向量维数的增加，本方案在验证阶段的效率提升效果更显著，因此更适用于资源受限、低延迟场景.

基于后量子Dilithium算法的格结构，提出面向资源受限、低延迟场景的动态预计算在线/离线签名方案DP-Olithium. 该方案利用在线/离线技术，有效提高了签名和验证效率，降低了离线预计算的存储和计算开销. 此外，该方案通过约束中间值复用保障了侧信道安全，适用于低延迟、资源受限场景. 后续工作将探索结合量子密钥分发技术，研究该方案在物联网环境中的具体实现方式，以及该方案与传统密码体制融合的实际部署性能.