An Overview on Lattice-Based Zero-Knowledge Proofs

doi:10.3969/j.issn.1671-1122.2025.05.001

Abstract

Abstract:

With the rapid development of quantum computing and increasing attentions on privacy protection, post-quantum zero-knowledge proofs have received a permanent interest. This paper primarily focused on the study for lattice-based zero-knowledge proofs. First, a brief overview on current zero-knowledge proofs from lattces was given. Subsequently, we classified these mainstream protocols into three types according to the underlying key techniques they use, followed by deep analysis for their design principle and performance. Finally, we gave a short discussion about the potential reseach line in the future.

Key words: lattice cryptography, zero-knowledge proof, commitment, stern-like framework, rejection sampling

CLC Number:

TP309

PAN Jing, LI Boxun, WAN Beilin, ZHONG Yantao. An Overview on Lattice-Based Zero-Knowledge Proofs[J]. Netinfo Security, 2025, 25(5): 679-688.

Figures/Tables 6

References 39

[1]	GOLDWASSER S, MICALI S, RACKOFF C. The Knowledge Complexity of Interactive Proof-Systems(Extended Abstract)[C]// ACM. 17th Annual ACM Symposium on Theory of Computing-STOC 1985. New York:ACM, 1985: 297-304.
[2]	GOLDREICH O, MICALI S, WIQDERSON A. How to Prove all NP Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design[C]// Springer. The 6th Annual International Cryptology Conference-CRYPTO1986. Heidelberg: Springer, 1986: 171-185.
[3]	GROTH J, OSTROVSKY T, SAHAI A. Non-Interactive Zaps and New Techniques for NIZK[C]// Springer. 26th Annual International Cryptology Conference-CRYPTO 2006. Heidelberg: Springer, 2006: 97-111.
[4]	JENS Groth. On the Size of Pairing-Based Non-Interactive Arguments[C]// Springer. 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques-EUROCRYPT 2016. Heidelberg: Springer, 2016: 305-326.
[5]	GOLDREICH O, GOLDWASSER S. On the Limits of Non-Approximability of Lattice Problems[C]// ACM. 13th Annual ACM Symposium on the Theory of Computing-STOC 1998. New York:ACM, 1998: 1-9.
[6]	MICCIANCIO D, VADHAN S P. Statistical Zero-Knowledge Proofs with Efficient Provers: Lattice Problems and More[C]// Springer. 23th Annual International Cryptology Conference-CRYPTO 200. Heidelberg:Springer, 2003: 282-298.
[7]	PEIKERT C, VAIKUNTANATHAN V. Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems[C]// Springer. 28th Annual International Cryptology Conference-CRYPTO 2008. Heidelberg: Springer, 2008: 536-557.
[8]	KAWACHI A, TANAKA K, XAGAWA K. Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems[C]// Springer. 24th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT 2008. Heidelberg: Springer, 2018: 372-389.
[9]	LING San, NGUYEN K, STEHLÉ D, et al. Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications[C]// Springer. 16th International Conference on Theory and Practice of Public Key Cryptography-PKC 2013. Heidelberg: Springer, 2013: 107-124.
[10]	ZHANG Yupeng, GENKIN D, KATZ J, et al. vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases[C]// IEEE. 38th IEEE Symposium on Security and Privacy-SP 2017. New York: IEEE, 2017: 863-880.
[11]	YANG Rupeng, AU M H, ZHANG Zhenfei, et al. Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications[C]// Springer. 39th Annual International Cryptology Conference-CRYPTO 2019. Heidelberg: Springer, 2019: 147-175.
[12]	LIBERT B, LING San, MOUHARTEM F, et al. Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions[C]// Springer. 22th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT 2016. Heidelberg: Springer, 2016: 373-403.
[13]	LING San, NGUYEN K, WANG Huaxiong, et al. Lattice-Based Group Signatures: Achieving Full Dynamicity with Ease[C]// Springer. 15th International Conference on Applied Cryptography and Network Security-ACNS 2017. Heidelberg: Springer, 2017: 293-312.
[14]	LIBERT B, LING San, MOUHARTEM F, et al. Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption[C]// Springer. 22th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT 2016. Heidelberg: Springer, 2016: 101-131.
[15]	LYUBASHEVSKY V. Fiat-Shamir with Aborts: Applications to Lattice and Factoring Based Signatures[C]// Springer. 15th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT 2009. Heidelberg: Springer, 2009: 598-616.
[16]	LYUBASHEVSKY V. Lattice Signatures without Trapdoors[C]// Springer. The 31th Annual International Conference on the Theory and Applications of Cryptographic Techniques-EUROCRYPT 2012. Heidelberg: Springer, 2012: 738-755.
[17]	BENHAMOUDA F, CAMENISCH J, KRENN S, et al. Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures[C]// Springer. The 20th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT 2014. Heidelberg: Springer, 2014: 551-572.
[18]	BAUM C, DAMGÅRD I, LYUBASHEVSKY V, et al. More Efficient Commitments from Structured Lattice Assumptions[C]// Springer. The 11th International Conference on Security and Cryptography for Networks-SCN 2018. Heidelberg: Springer, 2018: 368-385.
[19]	ESGIN M F, STEINFELD R, LIU J K, et al. Lattice-Based Zero-Knowledge Proofs: New Techniques for Shorter and Faster Constructions and Applications[C]// Springer. 39th Annual International Cryptology Conference-CRYPTO 2019. Heidelberg: Springer, 2019: 115-146.
[20]	BOOTLE J, LYUBASHEVSKY V, SEILER G. Algebraic Techniques for Short(er) Exact Lattice-Based Zero-Knowledge Proofs[C]// Springer. The 39th Annual International Cryptology Conference-CRYPTO 2019. Heidelberg: Springer, 2019: 176-202.
[21]	ATTEMA T, LYUBASHEVSKY V, SEILER G. Practical Product Proofs for Lattice Commitments[C]// Springer. The 40th Annual International Cryptology Conference CRYPTO 2020. Heidelberg: Springer, 2020: 470-499.
[22]	ESGIN M F, NGUYEN N K, SEILER G. Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings[C]// Springer. The 26th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT 2020. Heidelberg: Springer, 2020: 259-288.
[23]	LYUBASHEVSKY V, NGUYEN N K, SEILER G. Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments[C]// Springer. The 24th International Conference on Theory and Practice of Public Key Cryptography-PKC 2021. Heidelberg: Springer, 2021: 215-241.
[24]	KIM D, LEE D, SEO J, et al. Toward Practical Lattice-Based Proof of Knowledge from Hint-MLWE[C]// Springer. The 43th Annual International Cryptology Conference CRYPTO-2023. Heidelberg: Springer, 2023: 549-580.
[25]	ESGIN M F, STEINFELD R, LIU Dongxi, et al. Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs[C]// Springer. The 43th Annual International Cryptology Conference-CRYPTO 2023. Heidelberg: Springer, 2023: 484-517.
[26]	GOLDREICH O. Zero-Knowledge Twenty Years after Its Invention[EB/OL]. (2020-05-11)[2024-11-20]. https://dblp.org/rec/journals/iacr/Goldreich02a.html.
[27]	LI Feng, MCMILLIN B M. A Survey on Zero-Knowledge Proofs[J]. Advances in Computers, 2014(94): 25-69.
[28]	LI Weihan, ZHANG Zongyang, ZHOU Zibo, et al. An Overview on Succinct Non-Interactive Zero-Knowledge Proofs[J]. Journal of Cryptologic Research, 2022, 9(3): 379-447.
[29]	ZHANG Zongyang, ZHOU Zibo, DENG Yi. A Survey on Recursive and Composite Techniques of Zero-Knowledge Proofs[J]. Chinese Journal of Computers, 2024, 47(10): 2466-2490.
[30]	BAUM C, DITTMER S, SCHOLL P, et al. Sok: Vector OLE-Based Zero-Knowledge Protocols[J]. Designs, Codes and Cryptography, 2023(91): 3527-3561.
[31]	SUN Xiaoqiang, YU F R, ZHANG Peng, et al. A Survey on Zero-Knowledge Proof in Blockchain[J]. IEEE Network, 2021(35): 198-205.
[32]	BLUM M, FELDMAN P, MICALI S. Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract)[C]// ACM. The 20th Annual ACM Symposium on Theory of Computing-STOC 1988. New York: ACM, 1988: 103-112.
[33]	FIAT A, SHAMIR A. How to Prove Yourself: Practical Solutions to Identification and Signature Problems[C]// Springer. The 6th Annual International Cryptology Conference CRYPTO 1986. Heidelberg:Springer, 1986: 186-194.
[34]	FEIGE U, FIAT A, SHAMIR A. Zero-Knowledge Proofs of Identity[C]// ACM. The 19th Annual ACM Symposium on Theory of Computing-STOC 1987. New York:ACM, 1987: 210-217.
[35]	BEN-SASSON E, CHIESA A, GARMAN C, et al. Zerocash: Decentralized Anonymous Payments from Bitcoin[C]// IEEE. The 35th IEEE Symposium on Security and Privacy-SP 2014. New York: IEEE, 2014: 459-474.
[36]	GUILLOU L C, QUISQUATER J. A “Paradoxical” Indentity-Based Signature Scheme Resulting from Zero-Knowledge[C]// Springer. The 8th Annual International Cryptology Conference-CRYPTO 1988. Heidelberg:Springer, 1988: 216-231.
[37]	STERN J. A New Paradigm for Public Key Identification[J]. IEEE Transactions on Information Theory, 1996, 42(6): 1757-1768.
[38]	LIBERT B, LING S, NGUYEN K, et al. Lattice-Based Zero-Knowledge Arguments for Integer Relations[C]// Springer. The 38th Annual International Cryptology Conference-CRYPTO 2018. Heidelberg: Springer, 2018: 700-732.
[39]	LYUBASHEVSKY V, NGUYEN N K, PLANÇON M. Lattice-Based Zero-Knowledge Proofs and Applications:Shorter, Simpler, and More General[C]// Springer. The 42th Annual International Cryptology Conference-CRYPTO 2022. Heidelberg: Springer, 2022: 71-101.

符号	说明
$q$	素数
${{Z}_{q}}=Z/qZ$	模$q$整数环
${{R}_{q}}={{Z}_{q}}/({{X}^{d}}+1)$	多项式环，其中$d$是一个2的方幂
$\mathbf{a}$	表示向量（若无特殊说明，如$\mathbf{a}\in R_{q}^{n}$，默认表示$Z_{q}^{n}$中的向量）
$\mathbf{A}$	表示矩阵，默认属于$Z_{q}^{n\times m}$
${{l}_{\infty }}={{\max }_{i}}\|{{a}_{i}}\|$	所有向量元素绝对值的最大值
${{S}_{u}}$	${{l}_{\infty }}\le u$的元素构成的有限集合
$x$?$U(X)$	从有限集合$X$中均匀随机抽样$~x$