Thinking inside the BLAC box

Abstract

We present BLACRONYM, a suite of new communication- and computation-efficient protocols for anonymous blacklisting without trusted third parties. Our protocols improve on Tsang et al.'s Blacklistable Anonymous Credentials (BLAC) system and its variants by incorporating novel batch zero-knowledge proof and verification techniques. BLACRONYM provides comparable functionality and security guarantees to those of BLAC and its derivatives, but it is substantially faster and consumes much less bandwidth. At the heart of BLACRONYM is the first batch zero-knowledge protocol in the literature for proofs of partial knowledge over non-monotone access structures; we suspect that our new techniques will find applications in speeding up other cryptographic constructions that require proofs of similar statements.