With the explosion of information in daily life, determining the trustworthiness of data has become inevitable. As data from different sources can be used in critical applications such as health-care and military for decision making, data provenance plays an important role to gauge the trustworthiness of data. Although, lots of research has been conducted out on provenance generation, provenance management/storage and provenance dissemination in various fields of computing such as: databases, scientific workflows, file systems, distributed cloud computing, and wireless sensor networks. However, security of data provenance has gained limited attention from research community. Since provenance generates a Directed Acyclic Graph (DAG) and chain structure, traditional security solutions are not directly applicable. In this paper, a novel aggregated signature based chaining scheme is presented. The proposed scheme ensures confidentiality, integrity, non-repudiation and availability in a distributed environment to achieve secure provenance. Differentfrom existing work, we assume a stronger attacker model inwhich more than two consecutive colluding users can launchattacks on provenance chain. Security analysis shows that ourscheme can detect such attacks. We have evaluated our proposed scheme empirically and analytically to validate its effectiveness. Our results show that our scheme outperforms existing schemes in term of computation and security.