International Association
for Cryptologic Research

It is known that one can generically construct a very flexible post-quantum anonymous credential scheme, supporting the showing of arbitrary predicates on its attributes using general-purpose zero-knowledge proofs secure against quantum adversaries [Fischlin, CRYPTO 2006]. Traditionally, such a generic instantiation is thought to come with impractical sizes and performance but recent advances in succinct proofs warrant a reconsideration. We show that with careful choices and optimizations, such a scheme can perform surprisingly well. In fact, it can even perform competitively against state-of-the-art post-quantum blind signatures, for the simpler problem of post-quantum unlinkable tokens, required for a post-quantum version of \emph{privacy pass}. To wit, a post-quantum privacy pass constructed in this way using zkDilithium, our proposal for a STARK-friendly variation on Dilithium2, allows for a trade-off between token size (76--172 kB) and generation time (0.25--4.5s) with a target proof security level of 115 bits. Verification of these tokens can be done in ~30ms. We argue that these tokens are reasonably practical, adding less than a second upload time over traditional tokens, supported by a measurement study. We also discuss how our construction enables an improved version of rate-limited privacy pass that does not require an attester and hides usage patterns of clients.