A Characterization of the problem of secure provenance management

Data (or information) provenance has many important applications. However, prior work on data provenance management almost exclusively focused on the collection, representation, query, and storage of provenance data. In contrast, the security aspect of provenance management has not been understood nor adequately addressed. A natural question then is: What would a secure provenance management system - perhaps as an analogy to secure database management systems - look like? In this paper, we explore the problem space of secure provenance management systems with an emphasis on the security requirements for such systems, and characterize desired solutions for tackling the problem. We believe that this paper makes a significant step towards a comprehensive solution to the problem of secure provenance management.