Efficient Implementation of a Post-Quantum Anonymous Credential Protocol

Authentication on the Internet usually has the drawback of leaking the identity of the users, or at least allowing to trace them from a server to another. Anonymous credentials overcome this issue, by allowing users to reveal the attributes necessary for the authentication, without revealing any other information (in particular not their identity). In this article, we provide a generic framework to construct anonymous credential schemes and use it to give a concrete construction of post-quantum (lattice-based) anonymous credential protocol. Our protocol thus allows for long-term security even when one considers the emergence of quantum computers able to break widely used traditional computational assumptions, such as RSA, the discrete logarithm or Diffie-Hellman. We also give a concrete implementation of our protocol, which is only one order of magnitude slower and bandwidth consuming than previous anonymous credentials that are not post-quantum.