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 practically usable in large-scale applications, such as national eID cards, public transportation and physical access control systems. By using our revocation scheme together with existing PABCs, it is possible to prove attribute ownership in constant time and verify the proof and the revocation status in the time logarithmic in the number of revoked users, independently of the number of all valid users in the system. Proofs can be efficiently generated using only offline constrained devices, such as existing smart-cards. These features are achieved by using a new construction called \$n\$-times unlinkable proofs. We show the full cryptographic description of the scheme, prove its security, discuss parameters influencing scalability and provide details on implementation aspects. As a side result of independent interest, we design a more efficient proof of knowledge of weak Boneh-Boyen signatures, that does not require any pairing computation on the prover side.