The Web public key infrastructure is essential to providing secure communication on the Internet today, and in turn certificate authorities play a crucial role in this ecosystem by issuing certificates. These authorities may misissue certificates or suffer misuse attacks, however, which has given rise to the Certificate Transparency (CT) project. The goal of CT is to store all issued certificates in publicly auditable logs, which can then be checked for the presence of potentially misissued certificates. Thus, the requirement that a given certificate is indeed in one (or several) of these logs lies at the core of CT. In the current deployment of CT, however, most individual clients do not check that the certificates they see are in the log, as requesting a proof of inclusion directly from the log reveals the certificate and thus creates the clear potential for a violation of that client's privacy.
In this paper, we explore the techniques that have been proposed for privacy-preserving auditing of certificate inclusion, focusing on their effectiveness, efficiency, and suitability in a near-term deployment. In doing so, we also explore the parallels with related problems involving browser clients, such as Safe Browsing and certificate revocation checks. Guided by a set of constraints that we develop, we ultimately observe several key limitations in many proposals, ranging from their privacy provisions to the fact that they focus on the interaction between a client and a log but leave open the question of how a client could privately report any certificates that are missing.