The anonymity of a user at a client computer may be preserved when authenticating with an on-line service or content provider through the use of an anonymous and verifiable (i.e., “blind”) certificate set that is created by a certificate authority from a fixed-size set of PKI key pairs. The certificate authority randomly selects a subset of PKI key pairs to generate the blind certificate set where each certificate in the set includes a respective public key from the PKI key pair subset. The certificate authority also sends the private keys from the PKI key pair subset to the user. During authentication, the client computer is configured to randomly select a subset of one or more certificates from the set to present to the provider. The provider will encrypt content using the public keys in the subset of certificates and the client will decrypt the content with the corresponding private keys.