On page 3 of this U-Prove document regarding toke revocation, the author says the benefit of Accumulator-based revocation schemes is

A cryptographic accumulator allows the aggregation of a large set of elements into one constant-size value, and the ability to prove that an element has been aggregated or not in the accumulator.

... which when ported over to the x509 certificates world, means that the CRL would be of a constant size. This is important to many people who manage revocation or OCSP

Also, in the footnote

Many accumulator-based schemes rely on bilinear pairings, common in the cryptographic literature, but not yet popular in industry systems and standards.

This makes me wonder why this optimization hasn't been ported to more popular certificate formats.


  • What would be needed in order for the x509 PKI system to use an accumulator based scheme?

  • How do accumulator based schemes work? (They speak to the role of a witness and I'm not sure which entity would manage this)

  • How would the load be distributed? (Load meaning CPU or bandwidth in a high traffic area)


To put things simply, one of the goals of U-Prove is to provide some kind of anonymity (in their words, "preventing unwanted user tracking"). This makes revocation harder. In an X.509 context, where there is no user anonymity (a certificate contains the owner's name in plain words), revocation is simple: the authority who decides who is revoked and who is not simply issues signed statements about the revocation status of a given certificate. This can be an OCSP response, which talks about a single certificate, or a CRL, which lists all revoked certificate (from a given issuer or set of issuers), and thus implicitly lists all non-revoked certificates as well.

If you try to do the same thing in U-Prove, then you have invented a way to track users, and that's not good. So revocation in U-Prove must use more complex protocols, e.g. a cryptographic accumulator. Mainly, this allows each token owner to compute a verifiable proof of a token not being revoked at a given time, without opening the possibility of tracking the token owner. Revocation is still asserted by a specialized authority, so there must be some regular communication from the authority to the token owners; these are the witnesses. Each token owner must obtain a fresh witness from the authority, in order to compute the verifiable proof that the specific token is not revoked at some time.

This is not an optimization over X.509 CRL/OCSP. In an X.509 world, each certificate owner can obtain a fresh OCSP response from the CA and then show that response to third parties; this mimics the system of witness propagation but with shorter elements and less CPU cost. Moreover, in X.509, it is not necessary that the certificate owner be involved at all; each entity who wants to validate a certificate can obtain the CRL or OCSP response directly from the CA.

In other words, cryptographic accumulators don't make classic revocation more efficient. In fact, they make it less efficient. But they add a new feature, which is the possibility to maintain revocation while still pursuing a non-tracking anonymity goal. This goal makes no sense in X.509. Therefore, no cryptographic accumulators in X.509. You could try to design and implement a revocation system for X.509 which uses cryptographic accumulator, but it would provide no extra feature, and would just make the system more complex, expensive, and restricted.

(In shorter words, there is no revocation scheme for X.509 which uses cryptographic accumulators because it would be a stupid thing to do. It would be like adding an extra gasoline tank to power a horse-drawn cart: it would not help the horses go farther, even though it would have helped if the horses had not been horses, but a combustion engine.)

  • I see, a witness is a point-in-time cryptographic result, and not the math and protocol used to calculate that result. Oct 17 '13 at 14:38
  • The basis for my thinking that accumulators would be beneficial was that CRLs get very large, and I read somewhere that OCSP + Stapling was not perfect at preserving privacy and so this accumulator approach may be a good compromise Oct 17 '13 at 14:48
  • "Not perfect at preserving privacy". Indeed. But irrelevant: if you use X.509 certificates, then users can be tracked. It is just not an issue with OCSP; it is pervasive to the whole concept of X.509. Oct 17 '13 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.