A challenge for digital archives managing long lived data, such as medical records and land registers, is to guarantee long-term authenticity, integrity, and datedness. Although some techniques have been proposed that provide these security goals, most proposals lack a corresponding performance analysis. Thus, in this paper we provide an analytical analysis of the performance of several proposals. Following, to see the impact of different approaches on the runtime, we implemented the most promising schemes and compared them with respect to their required storage space and verification time. Furthermore, the identified computational bottlenecks of the techniques are presented and corresponding improvements are indicated. Finally, we show how to select a long-term archiving scheme and the appropriate key sizes based on trust assumptions and the number of documents to be archived.