On Privacy-Preserving Revocation

[alecolo129]

I'd like to open a discussion on unlinkable revocation methods.

BBS signatures, one of the formats considered for the Swiss e-ID, support zero-knowledge proofs that provide unlinkable presentations of the holder's attributes. The importance of unlinkability was highlighted in a feedback to the EU Digital Identity's ARF signed by some of the most prominent cryptographers working on the field.

However, traditional revocation methods expose unique identifiers (e.g., revocation list indices), enabling verifiers to track multiple uses of the same credential, which undermines the privacy properties offered by BBS signatures.

In contrast, cryptographic accumulators preserve unlinkability across multiple presentations by enabling zero-knowledge non-revocation proofs. They also allow direct revocation without relying on expiration dates or frequent credential re-issuance. The downside, however, is the perceived computational burden on the user-side for keeping their credentials updated with the accumulator.

At the Cyber Defence Campus, we explored ways to speed up these updates. Our simulations, show that after 1 month of inactivity, an update takes less than 0.4 seconds on a laptop—assuming 10M users and high revocation rates.
While further improvements are possible, this already indicates that unlinkable accumulator-based revocation is not just feasible, but practical for national ID systems like the Swiss e-ID.

More details on the project can be found in this master's thesis, while the code used for benchmarks is available in a public GitHub repository.