Provenance information is information about the history of described objects. Provenance Storage System is a Python implementation of a system for storing and managing provenance documents according to the Common Provenance Model. The goal of this thesis is to rewrite the system's functionality into Java. The system will 1) enable common CRUD operations for provenance documents, 2) maintain non-repudiation evidence for stored provenance documents, and 3) enable authenticity verification of stored provenance documents. Retrieval and authenticity verification will be implemented at three levels of granularity: provenance document, domain-specific part of a provenance graph, and traversal information. The implementation shall be implemented in a modular way, so that it is easily extensible.