A customer can demonstrate control over an element, such as a domain, by receiving a certificate from a certificate authority. After receiving a request for a certificate for a certain domain name, the certificate authority uses a public key cryptography protocol to generate a request for information regarding the domain name. The request for information is submitted to a domain service which hosts that domain name, and the domain service will provide a response to the certificate authority which includes a public key and data for the domain name, with the data encrypted under an associated private key for the domain name. The certificate authority will issue a certificate specifying the domain name and utilizing the received public key, and the certificate is unable to be validated without access to the associated private key.