Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2026, Vol. 60 Issue (12): 2633-2641    DOI: 10.3785/j.issn.1008-973X.2026.12.009
    
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
Download: HTML     PDF(1575KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 04 December 2025      Published: 21 October 2026
CLC:  TP 918  
Fund:  中国铁路信息科技集团有限公司科技研究开发计划资助项目(WJZG-CKY-2024041(2024P02)).
Corresponding Authors: Wenfang ZHANG     E-mail: aa1397192336@163.com;wfzhang@swjtu.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Shiyu WU
Wenfang ZHANG
Cite this article:

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

URL:

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


基于动态预计算的高效格基在线/离线签名算法

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


关键词： 后量子密码,  在线/离线签名,  基于格的密码学,  动态预计算,  数论变换 
输入：随机种子$\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
Tab.1 Success probability of signing with different numbers of intermediate value groups N
安全等级G
P = 88%P = 96%P = 98%P = 99%
NIST-28121517
NIST-310151722
NIST-57111416
Tab.2 Upper bound of retry count for single signing
安全等级Spk/BSsk/BSσ/BSφ/B
NIST-21312252824205408
NIST-31952400032934595
NIST-525924864459510400
Tab.3 Size of key, signature and intermediate value
方案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
Tab.4 Signature-stage storage overhead for different schemes
Fig.1 Signature storage overhead for different security levels
安全等级(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
Tab.5 Storage overhead for different security levels
方案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}} $
Tab.6 Comparison of computational overhead of matrix-vector multip lication in verification phase
NIST安全等级方案$ {T}_{\text{keygen}} $TofflineTonlineTverify
2Dilithium90026592
Olithium89216212991
本方案9080513332
3Dilithium1750448151
Olithium1753163217152
本方案176146722650
5Dilithium2350501242
Olithium2364608242245
本方案234179525677
Tab.7 Comparison of computational overhead at each phase among different schemes μs
Fig.2 Computational overhead for different security levels
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
Tab.8 Comparison of time overhead of each operation in verification phase
[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!