The ability to record and keep account of the usage of cloud resources in a credible and verifiable way is a precursor to widespread cloud deployment and availability because usage information is potentially sensitive and must be verifiably accurate. In an attempt to provide a mutually verifiable resource usage and billing mechanism, we found that the frequent asymmetric key operations of a digital signature lead to excessive computations and a bottleneck of billing transactions. As a remedy for these limitations, we propose a mutually verifiable billing system called THEMIS. The system, which introduces the concept of a cloud notary authority for the supervision of billing, makes billing more objective and acceptable to users and cloud service providers. THEMIS generates mutually verifiable binding information that can be used to resolve future disputes between a user and a cloud service provider. Because THEMIS does not require any asymmetric key operations of users and providers, it provides a level of security that is identical to that of a signature and it minimizes the latency of billing transactions. A secure and nonobstructive billing system called THEMIS as a remedy for these limitations. The system uses a novel concept of a cloud notary authority for the supervision of billing. The cloud notary authority generates mutually verifiable binding information that can be used to resolve future disputes between a user and a cloud service provider in a computationally efficient way.