As organizations become increasingly reliant on cloud computing for servicing their data storage requirements, the need to govern access control at finer granularities becomes particularly important. This challenge is increased by the lack of policy supporting data migration across geographic boundaries and through organizations with divergent regulatory policies. In this paper, we present an architecture for secure and distributed management of provenance, enabling its use in security-critical applications. Provenance, a metadata history detailing the derivation of an object, contains information that allows for expressive, policy-independent access control decisions. We consider how to manage and validate the metadata of a provenance-aware cloud system, and introduce protocols that allow for secure transfer of provenance metadata between end hosts and cloud authorities. Using these protocols, we develop a provenance-based access control mechanism for Cumulus cloud storage, capable of processing thousands of operations per second on a single deployment. Through the introduction of replicated components, we achieve overhead costs of just 14%, demonstrating that provenance-based access control is a practical and scalable solution for the cloud.