Paper 2026/119
Reusable Anonymous Credentials with Flow-Mode Unlinkability
Abstract
Anonymous credentials let a holder prove certified attributes and verifier predicates without revealing the credential or linking sessions. SNARK-based credentials support expressive predicates and deployed signatures such as ECDSA and BLS, but remain stateless: each presentation re-proves the credential relation and predicates from scratch. Reusable presentations amortize this cost, but create a leakage channel outside standard unlinkability: a verifier may detect that two tokens came from the same evolving reuse chain. We introduce reusable anonymous credentials, where a holder maintains a compact private state and derives fresh presentation tokens by rerandomization or incremental predicate update. Our security model introduces flow-mode unlinkability, which requires tokens from the same reuse chain to be indistinguishable from independently generated tokens under the same public schedule. This captures colluding verifiers who pool transcripts across repeated presentations. SHIFT realizes this model with two components. Superhalo is a function-hiding non-uniform incrementally verifiable computation (IVC) from Halo-style KZG accumulation. Standard multi-function IVC reveals the active function because only one accumulator slot changes; Superhalo instead updates all slots with dummy work and hides the update trace. SHIFT also uses proof composition for signature possession: a $\Sigma$-protocol proves expensive BLS pairing checks outside the recursive circuit, while the IVC binds the proof to the credential digest, predicates, and session context. Our Rust implementation evaluates BLS credentials and an ECDSA variant on commodity hardware. Rerandomization takes about $0.65$ s independent of attribute length and predicate size, proof size is below $2$ KB, and verification is below $50$ ms. Incremental predicate update reduces prover time by up to $3.5\times$ compared with the proof-of-possession baseline of Woo~et al (S&P~2025) in the evaluated setting.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Anonymous credentialRecursive SNARKsZero-KnowledgeAuthenticationWeb3
- Contact author(s)
-
bindyy xie @ connect polyu hk
tian-yu zheng @ connect polyu hk
csrsong @ comp polyu edu hk
shanggao @ polyu edu hk
b xiao @ polyu edu hk - History
- 2026-11-16: revised
- 2026-01-25: received
- See all versions
- Short URL
- https://ia.cr/2026/119
- License
-
CC BY-NC-ND
BibTeX
@misc{cryptoeprint:2026/119,
author = {Bin Xie and Tianyu Zheng and Rui Song and Shang Gao and Bin Xiao},
title = {Reusable Anonymous Credentials with Flow-Mode Unlinkability},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/119},
year = {2026},
url = {https://eprint.iacr.org/2026/119}
}