Private certificates designed to counteract problems associated with certificate lending are configured such that disclosure of a secret key associated with one certificate automatically results in disclosure of a secret key associated with another certificate, while the corresponding public keys are unlinkable with one another. In an illustrative private certificate generation protocol, a user generates verification information associated with a first public key. The verification information is generated at least in part using a corresponding first secret key. The verification information is supplied to a certification authority, which generates based at least in part on the first public key and the verification information a second public key having a corresponding second secret key, and generates a certificate based at least in part on the second public key. The private certificate generation protocol may be asymmetric or symmetric.