Paper 2026/119

Reusable Anonymous Credentials with Flow-Mode Unlinkability

Bin Xie, Hong Kong Polytechnic University
Tianyu Zheng, Hong Kong Polytechnic University
Rui Song, Hong Kong Polytechnic University
Shang Gao, Hong Kong Polytechnic University
Bin Xiao, Hong Kong Polytechnic University
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
Creative Commons Attribution-NonCommercial-NoDerivs
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.