Lattice-Based Rate-Limited Tokens (Anonymous Credentials) in the Random Oracle Model

Abstract: An anonymous credential allows a user to prove that she is authorized to access a resource in a privacy-preserving way. A rate-limited token is an anonymous credential that can only be used a limited number of times in any particular context; this means that even though we do not know which users are gaining access to a resource, there is a limit to how many resources one user may consume. Such tokens are becoming an increasingly attractive way to balance privacy with authorized access. Camenisch, Lysyanskaya, and Hohenberger (Eurocrypt 2005) proposed a communication-optimal framework for instantiating rate-limited tokens, relying on digital signatures, pseudorandom functions (PRFs), and non-interactive zero-knowledge proofs (NIZKs). However, obtaining an efficient post-quantum secure instantiation has been an open problem. One of the major issues leading to this failure has been the lack of efficient post-quantum PRFs that can be efficiently composed with a NIZK. In this talk, I will revisit the Camenisch, Lysyanskaya, and Hohenberger framework and show how, in the random oracle model, a weak PRF, where adversaries are limited to evaluating the PRF on random inputs, suffices. Then I will show how, using a candidate weak PRF based on the Learning With Errors assumption, we can obtain a post-quantum secure instantiation of rate-limited credentials that offers promising token sizes (899 KB for a rate limit of 256 vs 3 MB for prior constructions).

Joint work: Victor Youdom Kemmoe, Anna Lysyanskaya, Ngoc Khanh Nguyen.

Suggested readings

• Lattice-Based Rate-Limited Tokens in the Random Oracle Model (ia.cr/2026/1649)