Paper 2025/1489

PQ-STAR: Post-Quantum Stateless Auditable Rekeying

Avraham Yagudaev, Ben-Gurion University of the Negev, Beer Sheva, Israel

Moti Yung, Google, USA

Abstract

Rekeying is an effective technique for protecting symmetric ciphers against side-channel and key-search attacks. Since its introduction, numerous rekeying schemes have been developed. We introduce Post-Quantum Stateless Auditable Rekeying (PQ-STAR), a novel post-quantum secure stateless rekeying scheme with audit support. PQ-STAR is presented in three variants of increasing security guarantees: (i) Plain PQ-STAR lets an authorized auditor decrypt and verify selected ciphertexts; (ii) Commitment-based PQ-STAR with the additional binding guarantee from the commitments, preventing a malicious sender from potentially claiming a random or wrong session key. (iii) Zero-knowledge PQ-STAR equips each session key with a signature-based zero-knowledge proof (ZKP), which proves that the session key was derived honestly, without ever revealing the secret preimage. We formally prove that all variants achieve key-uniqueness, index-hiding, and forward-secrecy, even if a probabilistic polynomial-time (PPT) adversary arbitrarily learns many past session keys. PQ-STAR provides a formally verified, stateless, and audit-capable rekeying primitive that can be seamlessly integrated as a post-quantum upgrade for existing symmetric-key infrastructures.

@misc{cryptoeprint:2025/1489,
      author = {Shlomi Dolev and Avraham Yagudaev and Moti Yung},
      title = {{PQ}-{STAR}: Post-Quantum Stateless Auditable Rekeying},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1489},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1489}
}