Time-Based Re-randomization for Zero-Knowledge Proofs: Enhancing Privacy Through Temporal Unlinkability

Abstract

Zero-knowledge proofs provide cryptographic guarantees of statement validity without revealing underlying secrets. However, static proofs enable linking attacks where adversaries track the same proof across multiple uses, compromising user privacy. We introduce Time-Based Re-randomization (TBR), a novel protocol that automatically transforms zero-knowledge proofs at fixed time intervals while preserving their validity. Our construction leverages cryptographic randomization combined with deterministic time-slot generation to create temporally unlinkable proofs without user interaction. We provide formal security proofs demonstrating that TBR maintains zero-knowledge and soundness properties while preventing proof-linking attacks. Performance analysis shows TBR incurs only 8-12ms overhead compared to 450-600ms for generating fresh proofs, making it practical for privacy-preserving applications including anonymous authentication, timelimited credentials, and blockchain systems.