Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2026, Vol. 60 Issue (12): 2633-2641    DOI: 10.3785/j.issn.1008-973X.2026.12.009
计算机技术     
基于动态预计算的高效格基在线/离线签名算法
吴诗语1(),张文芳1,2,*()
1. 西南交通大学 信息科学与技术学院，四川 成都 610031
2. 西南交通大学 信息安全与 国家计算网格实验室，四川 成都 610031
Efficient lattice-based online/offline signature with dynamic precomputation
Shiyu WU1(),Wenfang ZHANG1,2,*()
1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China
2. Information Security and National Computing Grid Laboratory, Southwest Jiaotong University, Chengdu 610031, China
 全文: PDF(1575 KB)   HTML
摘要：

针对传统数字签名难以兼顾高效性和后量子安全的问题，提出基于动态预计算的高效无陷门格基在线/离线签名算法DP-Olithium. 通过动态生成离线预计算资源和优化矩阵向量乘法，解决现有抗量子签名离线存储开销大、验签计算成本高的问题. 将该方案的安全性归约到模格困难问题，形式化证明了该方案在量子随机谕言机模型下满足针对选择消息攻击的强存在不可伪造性. 仿真实验结果表明，与其他现有方案相比，DP-Olithium的离线存储开销最高可减少66%，在NIST-3安全级别下离线签名效率提升最明显，时间开销降低约63%，验证效率提高约68%，能够满足资源受限、低延迟场景的需求.
关键词： 后量子密码;  在线/离线签名;  基于格的密码学;  动态预计算;  数论变换    
Abstract:

An efficient trapdoor-free lattice-based online/offline signature algorithm DP-Olithium with dynamic precomputation was proposed in order to address the issue that traditional digital signatures fail to balance high efficiency and post-quantum security. The drawbacks of excessive offline storage overhead and high verification computational cost existing in current post-quantum signature schemes were resolved by dynamically generating offline precomputed resources and optimizing matrix-vector multiplications. The security of this scheme was reduced to module-lattice hard problems, and strong unforgeability against chosen-message attacks was formally proven to be achieved by the scheme in the quantum random oracle model. Simulation results show that the offline storage overhead of DP-Olithium can be reduced by up to 66% compared with other existing schemes. The most significant improvement was achieved in offline signing efficiency under the NIST-3 security level, at which the time overhead was cut by approximately 63%, and verification efficiency was boosted by around 68%. Demands from resource-constrained and low-latency application scenarios can be satisfied by the proposed algorithm.
Key words: post-quantum cryptography    online/offline signature    lattice-based cryptography    dynamic precomputation    number theoretic transform
收稿日期: 2025-12-04 出版日期: 2026-10-21
CLC:  TP 918  
基金资助: 中国铁路信息科技集团有限公司科技研究开发计划资助项目(WJZG-CKY-2024041(2024P02)).
通讯作者: 张文芳     E-mail: aa1397192336@163.com;wfzhang@swjtu.edu.cn
作者简介: 吴诗语（2000—），女，硕士生，从事后量子密码研究. orcid.org/0009-0003-3493-0724. E-mail：aa1397192336@163.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
吴诗语
张文芳

引用本文:

吴诗语,张文芳. 基于动态预计算的高效格基在线/离线签名算法[J]. 浙江大学学报(工学版), 2026, 60(12): 2633-2641.

Shiyu WU,Wenfang ZHANG. Efficient lattice-based online/offline signature with dynamic precomputation. Journal of ZheJiang University (Engineering Science), 2026, 60(12): 2633-2641.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2026.12.009    或    https://www.zjujournals.com/eng/CN/Y2026/V60/I12/2633

输入：随机种子$\zeta \in\{{0,1}{\}}^{256}$，矩阵$ \boldsymbol{A} $、$ \mu $
输出：公钥$ {\bf{pk}}=(\rho ,{\boldsymbol{t}}_{1}) $，私钥$ {\bf{sk}}=(K,\rho ,{\mathrm{tr}},{\boldsymbol{s}}_{1},{\boldsymbol{s}}_{2},{\boldsymbol{t}}_{0}) $
1. $(K,\rho,\rho') \in \{0,1\}^{256} \times \{0,1\}^{256} \times \{0,1\}^{512} = {H}(\zeta ) $;
2.$ \boldsymbol{A}:=\text{ExpandA(}\rho ) $;
3. $ ({\boldsymbol{s}}_{1},{\boldsymbol{s}}_{2})\in S_{\eta }^{l}\times S_{\eta }^{k}:=\text{ExpandS(}{\rho }^{\text{'}}) $;
4. $ \boldsymbol{t}=\boldsymbol{A}{\boldsymbol{s}}_{1}+{\boldsymbol{s}}_{2} $;
5. $ \left({\boldsymbol{t}}_{1},{\boldsymbol{t}}_{0}\right)={\text{Power2Round}}_{q}\left(\boldsymbol{t},d\right) $;
6. ${\mathrm{tr}} \in {\{ 0,1\} ^{256}} = {{H}}(\rho ||{{\boldsymbol{t}}_1});$
7. RETURN ${({\bf{pk}},{\bf{sk}})} $
  
输入：种子$ {\rho }^{\text{'}} $，矩阵$ \boldsymbol{A} $，$ \mu $
输出：预计算值令牌池$ {{\textit{φ}}} $
1.$ {\mathrm{new}}\leftarrow ~{\mathrm{avali}}+\Delta {\mathrm{EE}} $;
2. FOR $ t={\mathrm{avail}} $ TO $ {\mathrm{new}}-1 $ IN PARALLEL
3. 　$ \boldsymbol{y}\in S_{{\gamma }_{1}}^{l}:=\text{ExpandMask(}{\rho }^{\text{'}},\kappa ++) $;
4. 　$ \boldsymbol{w}=\boldsymbol{A}\boldsymbol{y} $;
5. 　$ ({\boldsymbol{w}}_{1},{\boldsymbol{w}}_{0}\text{):=Decompos}{\text{e}}_{\boldsymbol{q}}(\boldsymbol{w}, 2{\textit{γ}}_{2}) $;
6. 　$\tilde c \in {\{ 0,1\} ^{256}}: = H(\mu ||{{\boldsymbol{w}}_1})$;
7. 　$ {{\bf\textit{φ}}}:=(\tilde{c},\boldsymbol{y},{\boldsymbol{w}}_{1},{\boldsymbol{w}}_{0}) $;
8. END FOR
9.$ {\mathrm{avali}}\leftarrow ~{\mathrm{new}} $;
10.RETURN
  
输入：私钥 $ {\bf{sk}}=(K,\rho ,{\mathrm{tr}},{\boldsymbol{s}}_{1},{\boldsymbol{s}}_{2},{\boldsymbol{t}}_{0}) $
输出：预计算值令牌池$ {{\textit{φ}}} $
1. $ {\boldsymbol{A}} \leftarrow {\mathrm{ExpandA}}(\rho ) $;
2.$\mu \in \{0,1\}^{512} \leftarrow {{H}}({\mathrm{tr}}); $
3.$\rho ' \in {\{ 0,1\} ^{512}}: = {{H}}(\mu ||K)$;
4.$ {{\textit{φ}}} \leftarrow \text{EnsureEE(}{\mathrm{EE}}\_ {\mathrm{INIT}},{\rho }^{\text{'}},\boldsymbol{A},~\mu ) $;
5. RETURN $ {{\textit{φ}}} $
  
输入：$ {\bf{sk}},{{\textit{φ}}},\;M\text{, used} $
输出：签名$ {\boldsymbol{\sigma}} =(c,z,h) $
1.$ \tilde k \in {\{ 0,1\} ^{256}}: = {{H}}(M)$;
2. WHILE $ (\boldsymbol{z},\boldsymbol{h}):= \bot $ DO
3. 　$ \tilde{c}:=\tilde{k} \oplus \tilde{c} $ ;
4. 　IF $ \text{used}>{\mathrm{avail}} $
5. 　　$ \text{EnsureEE(}{\rho }^{\text{'}},\;\boldsymbol{A},\; \mu ) $;
6. 　$ c\in {B}_{\tau }\text{:=SampleInBall(}\tilde{c}) $;
7. 　$ \boldsymbol{z}=\boldsymbol{y}+c{\boldsymbol{s}}_{1} $;
8. 　$ \text{used++} $;
10. 　$ {\boldsymbol{r}}_{0}:={\boldsymbol{w}}_{0}-c{\boldsymbol{s}}_{2} $;
11. 　IF $ {\left|\left|\boldsymbol{z}\right|\right|}_{\infty } \geqslant {\gamma }_{1}-\beta $ OR $ {\left|\left|{\boldsymbol{r}}_{0}\right|\right|}_{\infty } \geqslant {\gamma }_{2}-\beta $
12. 　　$ (\boldsymbol{z},\boldsymbol{h}):= \bot $;
13. 　ELSE
14. 　　$ \boldsymbol{h}\text{:=MakeHin}{\text{t}}_{q}(\boldsymbol{r}+c{\boldsymbol{t}}_{0},{\boldsymbol{w}}_{1},{\gamma }_{2}) $;
15. 　　IF $ {\left|\left|c{\boldsymbol{t}}_{0}\right|\right|}_{\infty } \geqslant {\gamma }_{2} $ OR $ {\left|\left|\boldsymbol{h}\right|\right|}_{1} \geqslant \omega $
16. 　　　$ (\boldsymbol{z},\boldsymbol{h}):= \bot $;
17. END WHILE
18. RETURN $ \sigma =(c,\boldsymbol{z},\boldsymbol{h}) $
  
输入：$ {\bf{pk}},{\boldsymbol{\sigma}} ,M $
输出：验证成功输出1，否则输出0
1. IF $ \boldsymbol{A}=\bot $
2. 　$ \mathbf{Antt} \leftarrow \text{ExpandA (}\rho ) $;
3. 　$ \boldsymbol{A} \leftarrow \mathbf{Antt} $;
4. $ \mu \in {\{ 0,1\} ^{512}} \leftarrow {{H}}({{H}}(\rho ||{{\boldsymbol{t}}_1}))$;
5. $\tilde k \in {\{ 0,1\} ^{256}}: = {{{{H}}}}(M) $;
6. $ c \leftarrow \text{SampleInBall (}\tilde{c} $);
7. $ {\boldsymbol{w}}_{1}'={\text{UseHint}}_{q}(\boldsymbol{h},\boldsymbol{A}\boldsymbol{z}-{2}^{d}c{\boldsymbol{t}}_{1}, 2{\gamma }_{2}) $;
8. $ \text{IF}{\left|\left|\boldsymbol{z}\right|\right|}_{\infty }{<\gamma }_{1}-\beta $ AND $ \tilde{c}{=H(}\mu ||\boldsymbol{w}_{1}^{\text{'}}) \oplus \tilde{k} $
AND $ \left|\left|\boldsymbol{h}\right|\right| \leqslant \omega $
9. 　RETURN 1
10. ELSE
11. 　RETURN 0
  
输入：多项式向量$ \boldsymbol{z} $, 旋转因子表$ {\mathrm{zeta}} $
输出：多项式向量$ \boldsymbol{z} $
1. $ \boldsymbol{z} \leftarrow \text{Bitrev}\left(\boldsymbol{z}\right) $;
2. FOR $ {\mathrm{layer}}= 0 $ TO $ 7 $ DO
3. 　$ {\mathrm{len}} \leftarrow {2}^{{\mathrm{layer}}} $;
4. 　FOR $ {\mathrm{start}}= 0 $ TO $ N-1 $ STEP $ 2{\mathrm{len}} $ DO
5. 　　FOR $ i= 0 $ TO $ {\mathrm{len}}-1 $ STEP 8 DO
6. 　　　　$ \left(\boldsymbol{a},\boldsymbol{b}\right) \leftarrow \boldsymbol{z} $;
7. 　　　　$ \boldsymbol{b} \leftarrow \boldsymbol{b}\times \boldsymbol{z} $;
8. 　　　　$ \boldsymbol{t} \leftarrow \boldsymbol{b}+\boldsymbol{a} $;
9. 　　　　$ \boldsymbol{a} \leftarrow \boldsymbol{a}-\boldsymbol{b} $;
10.　　　　$ \left(\boldsymbol{a},\boldsymbol{t}\right) \leftarrow \text{MontgomeryReduce}\left(\boldsymbol{a},\boldsymbol{t}\right) $;
11.　　　　$ \boldsymbol{z} \leftarrow \left(\boldsymbol{a},\boldsymbol{b}\right) $;
12. 　　　END FOR
13. 　　END FOR
14. END FOR
15. RETURN $ \boldsymbol{z} $
  
安全等级P/%
N = 1N = 2N = 3N = 4N = 5N = 6N = 10N = 15
NIST-223.5041.4855.2365.7573.8079.9693.1498.20
NIST-319.6335.4148.0958.2866.4773.0588.7696.23
NIST-525.9645.1859.8169.9577.7583.5295.0598.81
表 1  不同中间值组数N下的签名成功概率
安全等级G
P = 88%P = 96%P = 98%P = 99%
NIST-28121517
NIST-310151722
NIST-57111416
表 2  单次签名的重试次数上界
安全等级Spk/BSsk/BSσ/BSφ/B
NIST-21312252824205408
NIST-31952400032934595
NIST-525924864459510400
表 3  密钥、签名和中间值的尺寸
方案S/kB
NIST-2NIST-3NIST-5
Dilithium签名5280123
Olithium，离线126178242
Olithium，在线26.744.574.8
本方案，离线$ 5.3N+20 $$ 7.5N+28 $$ 10.2N+38 $
本方案，在线26.744.574.8
表 4  不同方案的签名阶段存储开销
图 1  不同安全等级下的签名阶段存储开销
安全等级(k, l)L$\left\lceil {{\text{log}}}_2 q\right\rceil $S′/kB
NIST-2(4, 4)2562311.2
NIST-3(6, 5)2562321.5
NIST-5(8, 7)2562340.25
表 5  不同安全等级下的存储开销
方案T
NIST-2NIST-3NIST-5
Dilithium$ 4\;906\left({T}_{\text{add}}+2{T}_{\text{mul}}\right)+4{T}_{\text{zeta}} $$ 5\;120\left({T}_{\text{add}}+2{T}_{\text{mul}}\right)+5{T}_{\text{zeta}} $$ 7\;168\left({T}_{\text{add}}+2{T}_{\text{mul}}\right)+7{T}_{\text{zeta}} $
Olithium$ 4\;906\left({T}_{\text{add}}+2{T}_{\text{mul}}\right)+4{T}_{\text{zeta}} $$ 5\;120\left({T}_{\text{add}}+2{T}_{\text{mul}}\right)+5{T}_{\text{zeta}} $$ 7\;168\left({T}_{\text{add}}+2{T}_{\text{mul}}\right)+7{T}_{\text{zeta}} $
本方案$ 1\;024{T}_{\text{add}}+2\;048{T}_{\text{mul}}+{T}_{\text{zeta}} $$ 1\;024{T}_{\text{add}}+2\;048{T}_{\text{mul}}+{T}_{\text{zeta}} $$ 1\;024{T}_{\text{add}}+2\;048{T}_{\text{mul}}+{T}_{\text{zeta}} $
表 6  验证阶段矩阵向量乘法的计算开销对比
NIST安全等级方案$ {T}_{\text{keygen}} $TofflineTonlineTverify
2Dilithium90026592
Olithium89216212991
本方案9080513332
3Dilithium1750448151
Olithium1753163217152
本方案176146722650
5Dilithium2350501242
Olithium2364608242245
本方案234179525677
表 7  不同方案各阶段的计算开销对比
图 2  不同安全等级下的计算开销
NIST安全等级TA/μsTNTT /μsTmod /μsTother /μs
2Dilithium30.2035.6410.2015.34
Olithium30.4135.5310.4015.59
本方案8.725.211.3115.47
3Dilithium63.1050.5418.3121.44
Olithium62.6350.6318.6221.61
本方案18.537.732.3821.57
5Dilithium108.0379.8426.5228.95
Olithium106.9680.0326.7228.95
本方案32.5912.503.4328.57
表 8  验证阶段各操作的时间开销对比
1 Shor P W Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41 (2): 303- 332
doi: 10.1137/S0036144598347011
2 王亚辉, 张焕国, 吴万青, 等 基于相位估计和方程求解破解RSA的量子算法[J]. 计算机学报, 2017, 40 (12): 2688- 2699
Wang Yahui, Zhang Huanguo, Wu Wanqing, et al Quantum algorithms for breaking RSA based on phase estimation and equation solving[J]. Chinese Journal of Computers, 2017, 40 (12): 2688- 2699
3 NIST. IR 8547. Transition to post-quantum cryptography standards [EB/OL]. (2024-11-12)[2025-10-11]. https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8547.ipd.pdf.
4 Even S, Goldreich O, Micali S On-line/off-line digital signatures[J]. Journal of Cryptology, 1996, 9 (1): 35- 67
doi: 10.1007/BF02254791
5 Yao C C, Zhao Y Online/Offline signatures for low-power devices[J]. IEEE Transactions on Information Forensics and Security, 2013, 8 (2): 283- 294
doi: 10.1109/TIFS.2012.2232653
6 Zhang P Y, Jiang H, Zheng Z, et al A new and efficient lattice-based online/offline signature from perspective of abort[J]. The Computer Journal, 2022, 65 (9): 2400- 2410
doi: 10.1093/comjnl/bxab074
7 Zhang P Y, Yang H N, Zhu L, et al A new lattice-based online/offline signatures framework for low-power devices[J]. Theoretical Computer Science, 2023, 962: 113942
doi: 10.1016/j.tcs.2023.113942
8 王后珍, 段小超, 文嘉明, 等 Olithium: 基于格的无陷门在线/离线签名方案[J]. 计算机学报, 2025, 48 (4): 877- 892
Wang Houzhen, Duan Xiaochao, Wen Jiaming, et al Olithium: a lattice-based online/offline signature scheme without trapdoors[J]. Chinese Journal of Computers, 2025, 48 (4): 877- 892
doi: 10.11897/SP.J.1016.2025.00877
9 谢志强, 邵侠 一种考虑资源状态动态反馈的云计算调度算法[J]. 北京理工大学学报, 2019, 39 (6): 624- 631
Xie Zhiqiang, Shao Xia A scheduling algorithm for the cloud computing system with the dynamical feedback of server state[J]. Transactions of Beijing Institute of Technology, 2019, 39 (6): 624- 631
doi: 10.15918/j.tbit1001-0645.2019.06.012
10 阿里云. Spark作业配置动态资源分配[EB/OL]. (2025-02-25)[2025-10-11]. https://help.aliyun.com/zh/ack/ack-managed-and-ack-dedicated/use-cases/configure-dynamic-resource-allocation-for-spark-jobsobs.
11 Xue H, Au M H, Xie X, et al. Efficient online-friendly two-party ECDSA signature [C]//Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. Seoul: ACM, 2021: 558–573.
12 Lai J, Huang X, He D, et al Provably secure online/offline identity-based signature scheme based on SM9[J]. The Computer Journal, 2022, 65 (7): 1692- 1701
doi: 10.1093/comjnl/bxab009
13 Liu J K, Baek J, ZHOU J, et al Efficient online/offline identity-based signature for wireless sensor network[J]. International Journal of Information Security, 2010, 9 (4): 287- 296
doi: 10.1007/s10207-010-0109-y
14 Zhang W, Wei J, Khan M K PQC-enhanced privacy-preserving federated learning for edge-based IoT ecosystems[J]. IEEE Transactions on Consumer Electronics, 2025, 71 (4): 11171- 11182
doi: 10.1109/TCE.2025.3601395
15 Lyubashevsky V, Micciancio D, Peikert C, et al. SWIFFT: a modest proposal for FFT hashing [C]//Fast Software Encryption. Berlin: Springer, 2008: 54–72.
16 Zhou S, Xue H, Zhang D, et al. Preprocess-then-NTT technique and its applications to kyber and NewHope [M]//Information security and cryptology. Cham: Springer, 2019: 117–137.
17 Tan W, Lao Y, Parhi K K. Area-efficient matrix-vector polynomial multiplication architecture for ML-KEM using interleaving and folding transformation [C]//Proceedings of the IEEE International Symposium on Circuits and Systems. Singapore: IEEE, 2024: 1–5.
18 郭俊, 刘鹏, 杨昕遥, 等 大点数FFT在“申威26010”上的并行优化[J]. 浙江大学学报(工学版), 2024, 58 (1): 78- 86
Guo Jun, Liu Peng, Yang Xinyao, et al Parallel optimization of large-point FFT on Sunway 26010[J]. Journal of Zhejiang University (Engineering Science), 2024, 58 (1): 78- 86
doi: 10.3785/j.issn.1008-973X.2024.01.009
19 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.
20 Regev O. On lattices, learning with errors, random linear codes, and cryptography [C]//Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. Baltimore: ACM, 2005: 84–93.
21 Langlois A, Stehle 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
22 Bagherzandi A, Cheon J H, Jarecki S. Multi signatures secure under the discrete logarithm assumption and a generalized forking lemma [C]//Proceedings of the 15th ACM Conference on Computer and Communications Security. Alexandria: ACM, 2008: 449–458.
23 Ducas L, Lepoint T, Lyubashevsky V, et al. CRYSTALS-Dilithium: digital signatures from module lattices [EB/OL]. (2017-06-20)[2025-10-11]. https://eprint.iacr.org/2017/633.
No related articles found!