Scalable revocation scheme for anonymous credentials based on n-times unlinkable proofs

We propose the first verifier-local revocation scheme for privacy- enhancing attribute-based credentials (PABCs) that is prac- tically usable in large-scale applications, such as national eID cards, public transportation and physical access control systems. By using our revocation scheme together with ex- isting PABCs, it is possible to prove attribute ownership in constant time and verify the proof and the revocation sta- tus in the time logarithmic in the number of revoked users, independently of the number of all valid users in the sys- tem. Proofs can be effciently generated using only offline constrained devices, such as existing smart-cards. These fea- tures are achieved by using a new construction called n-times unlinkable proofs. We show the full cryptographic descrip- tion of the scheme, prove its security, discuss parameters in-uencing scalability and provide details on implementation aspects. As a side result of independent interest, we design a more effcient proof of knowledge of weak Boneh-Boyen signatures, that does not require any pairing computation on the prover side.