how to design a distributed client certificate verification service

With Eccentric Authentication, the goal is to make sure that each
client certificate has a globally unique, human memorable name. In
other words: there are no two certificates (with different public
keys) bearing the same CN.

With unique CN’s, people can trust that each signed message must have
been signed by the holder of the corresponding private key. This ties
human memorable names to public keys. When we make it globally unique,
we have squared Zooko’s Triangle.

To make sure that each CN is unique, we create a Client Certificate
Validation Service.

The main tasks of the Client Certificate Verification Service are:

  1. Validate that each client certificate has a unique CN;
  2. Raise an alarm when a violation is detected.

CN’s are a tuple of (nickname, sitename), for example:
user@domain. Each site signs the client certificates for its
clients. Client certificates contain no identifying data other than
the nick name and the user’s public key. This makes client
certificates pseudonyms for their owners. People have at least one,
perhaps more different pseudonyms for each site they’ve signed up for.

To make sure that only the site itself can sign certificates for that
domain, each site runs its own RootCA. That CA is specified in
DANE/DNSSEC, making the domain name point to a globally unique Root CA
public key. (Site identity).

The risk is that a site signs multiple certificates bearing the same
CN. This would enable the site to perform a MitM-attack on its users.

To counter that treat, people submit their client certificates to the
verification service. The service makes it detectable when there is
a violation. That’s sufficient for our purposes.

More requirements:

  • The CCVS must not refuse to add any valid certificate to its list;

This requirement is to ensure that when a duplicate certificate for a
CN is detected by someone, it will be added to the CCVS, so others can
learn about this incident.

  • The CCVS must not be able to withhold a certificate when queried for a CN.

The CCVS must answer truthfully. It may not be able to withhold
certificates that match a given CN. It must report them all. If not,
it could collude with the site’s CA to attempt a MitM attack.

The challenge

The challenge is to find protocol that fits these requirements. Bonus
points if it is scalable, distributable .