Preserving Module Privacy in Workflow Provenance
The authors study the problem of providing workflow data provenance without revealing the functionality of any module. The authors develop a model that formalizes the notion of privacy of modules embedded in a workflow structure as a natural extension of privacy of standalone modules. The model shows that by hiding a small amount of carefully chosen data, one can ensure privacy of all modules over an unbounded number of executions. The problem of identifying the smallest possible amount of such data is NP-hard, and in the full generality of the model it is in fact even hard to get a good approximation.