Cloud platforms can leverage Trusted Platform Modules to help provide assurance to clients that cloud-based web services are trustworthy and behave as expected. We discuss a variety of approaches to providing this assurance, and we implement one approach based on the concept of a trustworthy certificate authority. TaoCA, our prototype implementation, links cryptographic attestations from a cloud platform, including a Trusted Platform Module, with existing TLS-based authentication mechanisms. TaoCA is designed to enable certificate authorities, browser vendors, system administrators, and end users to define and enforce a range of trust policies for web services. Evaluation of the prototype implementation demonstrates the feasibility of the design, illustrates performance tradeoffs, and serves as an end-to-end, proof-of-concept evaluation of underlying trustworthy computing abstractions. The proposed approach can be deployed incrementally and provides new benefits while retaining compatibility with the existing public key infrastructure used for TLS.