LBAC: Lattice-based Anonymous Credential Based on the zk-creds Paradigm

GUO Xian; GU Tengfei; JIA Wenjuan; CHENG Yudan; FANG Junli; FENG Tao

doi:10.11999/JEIT260718

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2026 >

GUO Xian, GU Tengfei, JIA Wenjuan, CHENG Yudan, FANG Junli, FENG Tao. LBAC: Lattice-based Anonymous Credential Based on the zk-creds Paradigm[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260718

Citation:

GUO Xian, GU Tengfei, JIA Wenjuan, CHENG Yudan, FANG Junli, FENG Tao. LBAC: Lattice-based Anonymous Credential Based on the zk-creds Paradigm[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260718

Citation:

PDF( 1279 KB)

LBAC: Lattice-based Anonymous Credential Based on the zk-creds Paradigm

doi: 10.11999/JEIT260718 cstr: 32379.14.JEIT260718

School of Computer Science and Artificial Intelligence, Lanzhou University of Technology, 730050, China

Funds: The National Natural Science Foundation of China (61461027), The Natural Science Foundation of Gansu Province (26JRRA528, 20JR5RA467)

Received Date: 2026-06-01
Accepted Date: 2026-09-15
Rev Recd Date: 2026-09-15

Available Online: 2026-09-22

Abstract

Abstract

Objective With the pervasive integration of digital identity authentication technologies across various sectors, the need for rigorous privacy protection and data minimization is increasingly critical. In contemporary digital ecosystems, frameworks such as eIDAS 2.0 and W3C Verifiable Credentials heavily rely on cryptographic mechanisms to facilitate selective disclosure. However, existing anonymous credential schemes encounter two fundamental challenges that severely hinder their widespread real-world adoption. First, most deployed constructions rely on classical number-theoretic assumptions—such as the discrete logarithm and integer factorization problems. These mathematical foundations are proven to be fundamentally vulnerable to Shor's quantum algorithm, rendering current identity systems defenseless against future quantum computing adversaries. Second, high-performance privacy-preserving schemes typically conform to the Signature with Efficient Protocol (SEP) paradigm. This paradigm strictly requires identity issuers to adopt specific, non-standard signature primitives, which poses a significant barrier to integration with traditional legacy identity infrastructures and incurs prohibitive economic and operational costs. While the recently proposed zk-creds paradigm addresses this compatibility issue by encapsulating standard credentials via general-purpose zero-knowledge proofs, current implementations predominantly rely on pairing-based proof systems (e.g., Groth16), completely lacking post-quantum security. Conversely, existing lattice-based attempts to achieve quantum resistance often suffer from prohibitive proof sizes and excessive communication overheads due to the inherent complexity of high-dimensional matrix operations. Therefore, bridging the gap between backward compatibility with legacy systems and the urgent need for post-quantum security remains a critical theoretical and practical challenge in the field of cryptography. Methods To comprehensively overcome these limitations, a novel and highly efficient lattice-based anonymous credential scheme, named LBAC (Lattice-Based Anonymous Credentials), is proposed under the zk-creds paradigm. Operating as a purely two-party zero-knowledge proof layer between a user and a verifier, LBAC fundamentally decouples the credential issuance process. Standard, already-issued digital credentials (e.g., JSON Web Tokens) are directly taken as private inputs, providing robust post-quantum privacy enhancement without necessitating any coordination with or modifications to existing credential issuers. To achieve this, a sophisticated hybrid proof architecture is systematically developed based on the lattice-based LaBRADOR interactive proof system. First, to render the underlying LaBRADOR protocol zero-knowledge and non-interactive, a random masking mechanism bound by Ajtai commitments is introduced. By leveraging the rejection sampling, the original witness is rigorously blinded, and the Fiat-Shamir heuristic is subsequently applied to transform the interactive protocol into a non-interactive zero-knowledge argument. Second, to address the severe performance bottleneck of LaBRADOR when handling complex arithmetic circuits associated with standard signature verification, the Sumcheck protocol is introduced as a compressor. This protocol effectively reduces the large-scale arithmetic circuit satisfiability statements into significantly smaller, low-dimensional polynomial evaluation and dot-product proof tasks. Finally, inspired by the design philosophy of the Crescent scheme, the improved LaBRADOR proof generation process is architecturally decoupled into an offline "Prepare" phase and an online "Show" phase. Intensive computations—including the Sumcheck compression and the initial D-1 rounds of recursive folding—are entirely offloaded to the Prepare phase, where an intermediate state and a specific base vector are cached locally. During the Show phase, a lightweight lattice vector re-randomization is merely executed by the prover using a fresh nonce and the cached base vector, ensuring multi-show unlinkability while guaranteeing millisecond-level responsiveness for end-users. Results and Discussions The security properties of the LBAC scheme are comprehensively analyzed and rigorously proven under the standard random oracle model, demonstrating resilience against various malicious adversarial behaviors. The computational performance and practical viability are evaluated on an Ubuntu 20.04 environment equipped with an Intel Xeon Platinum 8352V processor. Empirical results robustly validate the superiority of the proposed Prepare-Show architecture. With heavy computational tasks successfully offloaded to the Prepare phase during the user’s idle time, an extraordinary latency of only 5.27 milliseconds is achieved during the online "Show" phase. This result is significantly faster than the 122 milliseconds recorded for comparative quantum-resistant schemes (e.g., Ligero-based schemes) and is highly competitive even with classical, non-quantum-safe schemes (Fig. 4). Regarding communication overhead, for a massive circuit scale of 2²⁰ constraints, the generated proof size is strictly maintained at 50.17 KB. A substantial and decisive advantage over other quantum-resistant alternatives is demonstrated (Fig. 5). Unlike existing quantum-resistant schemes whose proof sizes expand drastically with statement complexity, LBAC leverages the recursive amortization of the modified LaBRADOR system to maintain a logarithmic proof size, thereby significantly reducing communication bandwidth. The 621-millisecond verification time is deemed practically acceptable given the significant post-quantum security enhancements and the fact that verification is typically executed on computationally powerful servers; furthermore, it is noted that this overhead can be effectively mitigated in future deployments via batch verification techniques and GPU acceleration for number-theoretic transforms (NTT). Conclusions The challenge of achieving quantum-resistant privacy protection for existing digital credentials is successfully addressed in this study. By synthesizing the zk-creds paradigm with an optimized LaBRADOR proof system and the Sumcheck protocol compressor, an optimal balance between security, system compatibility, and operational performance is achieved. An end-to-end and post-quantum secure framework is provided with millisecond-level response speeds and compact proof sizes, effectively overcoming typical lattice-based bandwidth bottlenecks for scalable online usage. Furthermore, fundamental security properties—namely correctness, presentation unforgeability, and anonymity that inherently guarantees multi-show unlinkability—are rigorously proven. Future research is directed towards exploring simulation extractability for enhanced resilience in adaptive adversarial environments, alongside hardware-based device-binding and traceability mechanisms. These mechanisms are expected to prevent unauthorized transfers and enable identity tracking and credential revocation against malicious behaviors, thereby balancing privacy protection with regulatory compliance.
- Anonymous Credentials,
- Lattice-based Cryptography,
- Quantum-resistant Security,
- Zero-knowledge Proofs,
- Privacy Preserving

FullText(HTML)

References(30)

References

[1]	CHAUM D. Security without identification: Transaction systems to make big brother obsolete[J]. Communications of the ACM, 1985, 28(10): 1030–1044. doi: 10.1145/4372.4373.
[2]	CAMENISCH J and LYSYANSKAYA A. A signature scheme with efficient protocols[C]. Proceedings of the 3rd International Conference on Security in Communication Networks, Amalfi, Italy, 2002: 268–289. doi: 10.1007/3-540-36413-7_20.
[3]	BONEH D, BOYEN X, and SHACHAM H. Short group signatures[C]. Proceedings of the 24th Annual International Cryptology Conference on Advances in Cryptology–CRYPTO 2004, Santa Barbara, USA, 2004: 41–55. doi: 10.1007/978-3-540-28628-8_3.
[4]	CAMENISCH J and VAN HERREWEGHEN E. Design and implementation of the idemix anonymous credential system[C]. Proceedings of the 9th ACM Conference on Computer and Communications Security, Washington, USA, 2002: 21–30. doi: 10.1145/586110.586114.
[5]	SONNINO A, AL-BASSAM M, BANO S, et al. Coconut: Threshold issuance selective disclosure credentials with applications to distributed ledgers[C]. Proceedings of the Network and Distributed System Security Symposium (NDSS), San Diego, USA, 2019. doi: 10.14722/ndss.2019.23272.
[6]	POINTCHEVAL D and SANDERS O. Short randomizable signatures[C]. Proceedings of the Topics in Cryptology–CT-RSA 2016, San Francisco, USA, 2016: 111–126. doi: 10.1007/978-3-319-29485-8_7.
[7]	赵陆天禹, 王化群. 基于SM2的去中心化匿名凭证方案[J]. 计算机研究与发展, 2025, 62(12): 3093–3105. doi: 10.7544/issn1000-1239.202440756. ZHAO Lutianyu and WANG Huaqun. SM2-based decentralized anonymous credential scheme[J]. Journal of Computer Research and Development, 2025, 62(12): 3093–3105. doi: 10.7544/issn1000-1239.202440756.
[8]	李威翰, 张宗洋, 周子博, 等. 简洁非交互零知识证明综述[J]. 密码学报, 2022, 9(3): 379–447. doi: 10.13868/j.cnki.jcr.000525. 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. doi: 10.13868/j.cnki.jcr.000525.
[9]	DESMOULINS N, DUMANOIS A, KANE S, et al. Making BBS anonymous credentials eIDAS 2.0 compliant[C]. Proceedings of the 10th International Conference on Security Standardisation Research, Passau, Germany, 2026: 26–45. doi: 10.1007/978-3-032-19567-8_2.
[10]	W3C. Verifiable credentials data model v2.0: W3C recommendation[EB/OL]. https://www.w3.org/TR/vc-data-model-2.0/, 2025.
[11]	ROSENBERG M, WHITE J, GARMAN C, et al. zk-creds: Flexible anonymous credentials from zkSNARKs and existing identity infrastructure[C]. Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP), San Francisco, USA, 2023: 790–808. doi: 10.1109/SP46215.2023.10179430.
[12]	PAQUIN C, POLICHARLA G V, and ZAVERUCHA G. Stronger privacy for existing credentials[C/OL]. https://rwc.iacr.org/2025/program.php, 2025.
[13]	俞惠芳, 党宁泽. 车联网环境下去中心化抗量子计算数据共享方案[J]. 电子与信息学报, 2025, 47(10): 3838–3846. doi: 10.11999/JEIT250144. YU Huifang and DANG Ningze. Decentralized anti-quantum internet of vehicles data sharing scheme[J]. Journal of Electronics & Information Technology, 2025, 47(10): 3838–3846. doi: 10.11999/JEIT250144.
[14]	赵毅强, 孔金笛, 付玉成, 等. 面向模块化格基密钥封装机制算法多项式乘法的侧信道安全防护关键技术研究[J]. 电子与信息学报, 2025, 47(9): 3126–3136. doi: 10.11999/JEIT250292. ZHAO Yiqiang, KONG Jindi, FU Yucheng, et al. Research on key technologies of side-channel security protection for polynomial multiplication in ML-KEM/Kyber algorithm[J]. Journal of Electronics & Information Technology, 2025, 47(9): 3126–3136. doi: 10.11999/JEIT250292.
[15]	刘媛, 王励成, 周永彬. TTRC-ABE: 可追踪可撤销的基于循环代数带误差学习问题的格基属性加密方案[J]. 电子与信息学报, 2025, 47(6): 1911–1926. doi: 10.11999/JEIT240997. LIU Yuan, WANG Licheng, and ZHOU Yongbin. TTRC-ABE: Traitor traceable and revocable CLWE-based ABE scheme from lattices[J]. Journal of Electronics & Information Technology, 2025, 47(6): 1911–1926. doi: 10.11999/JEIT240997.
[16]	BEULLENS W and SEILER G. LaBRADOR: Compact proofs for R1CS from module-SIS[C]. Proceedings of the 43rd Annual International Cryptology Conference on Advances in Cryptology–CRYPTO 2023, Santa Barbara, USA, 2023: 518–548. doi: 10.1007/978-3-031-38554-4_17.
[17]	LYUBASHEVSKY V, SEILER G, and STEUER P. The LaZer library: Lattice-based zero knowledge and succinct proofs for quantum-safe privacy[C]. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, Salt Lake City, USA, 2024: 3125–3137. doi: 10.1145/3658644.3690330.
[18]	NGUYEN N K and SEILER G. Greyhound: Fast polynomial commitments from lattices[C]. Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology–CRYPTO 2024, Santa Barbara, USA, 2024: 243–275. doi: 10.1007/978-3-031-68403-6_8.
[19]	HWANG I, SEO J, and SONG Y. Concretely efficient lattice-based polynomial commitment from standard assumptions[C]. Proceedings of the 44th Annual International Cryptology Conference on Advances in Cryptology–CRYPTO 2024, Santa Barbara, USA, 2024: 414–448. doi: 10.1007/978-3-031-68403-6_13.
[20]	ARGO S, GÜNEYSU T, JEUDY C, et al. Practical post-quantum signatures for privacy[C]. Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, Salt Lake City, USA, 2024: 1523–1537. doi: 10.1145/3658644.3670297.
[21]	BOOTLE J, LYUBASHEVSKY V, NGUYEN N K, et al. A framework for practical anonymous credentials from lattices[C]. Proceedings of the 43rd Annual International Cryptology Conference on Advances in Cryptology–CRYPTO 2023, Santa Barbara, USA, 2023: 384–417. doi: 10.1007/978-3-031-38545-2_13.
[22]	MASSIMO J, KAMPANAKIS P, TURNER S, et al. RFC 9881: Internet X. 509 public key infrastructure -- algorithm identifiers for the module-lattice-based digital signature algorithm (ML-DSA)[EB/OL]. https://www.rfc-editor.org/rfc/rfc9881.html, 2025.
[23]	DELIGNAT-LAVAUD A, FOURNET C, KOHLWEISS M, et al. Cinderella: Turning shabby X. 509 certificates into elegant anonymous credentials with the magic of verifiable computation[C]. Proceedings of the 2016 IEEE Symposium on Security and Privacy (SP), San Jose, USA, 2016: 235–254. doi: 10.1109/SP.2016.22.
[24]	FRIGO M and SHELAT A. Anonymous credentials from ECDSA[J]. IACR Communications in Cryptology, 2026, 3(1): 7. doi: 10.62056/a3qjmpgxq.
[25]	AMES S, HAZAY C, ISHAI Y, et al. Ligero: Lightweight sublinear arguments without a trusted setup[C]. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, USA, 2017: 2087–2104. doi: 10.1145/3133956.3134104.
[26]	TEAM P Z. Plonky2: Fast recursive arguments with PLONK and FRI[EB/OL]. https://docs.rs/crate/plonky2/latest/source/plonky2.pdf, 2022.
[27]	BEN-SASSON E, BENTOV I, HORESH Y, et al. Scalable, transparent, and post-quantum secure computational integrity[EB/OL]. https://eprint.iacr.org/2018/046, 2018.
[28]	GOLOVNEV A, LEE J, SETTY S, et al. Brakedown: Linear-time and field-agnostic SNARKs for R1CS[C]. Proceedings of the 43rd Annual International Cryptology Conference on Advances in Cryptology–CRYPTO 2023, Santa Barbara, USA, 2023: 193–226. doi: 10.1007/978-3-031-38545-2_7.
[29]	DE SANTIS A, DI CRESCENZO G, OSTROVSKY R, et al. Robust non-interactive zero knowledge[C]. Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology–CRYPTO 2001, Santa Barbara, USA, 2001: 566–598. doi: 10.1007/3-540-44647-8_33.
[30]	FRIEDRICHS K, HARDING F, LEHMANN A, et al. Device-bound anonymous credentials with(out) trusted hardware[EB/OL]. https://eprint.iacr.org/2025/1995, 2025.