Trustworthy and Efficient Protection Schemes for Digital Archiving

The amount of information produced in the last decades has grown notably. Much of this information only exists in the form of electronic documents and it has often to be stored for long periods. Therefore, digital archives are increasingly needed. However, for the documents to remain trustworthy while they are archived, they need to be protected by the archivists. Important protection goals that must be guaranteed are integrity, authenticity, non-repudiation, and proof of existence. To address these goals, several protection schemes for digital archives have been designed. These schemes are usually based on cryptographic primitives, namely digital signatures and hash functions. However, since documents can be archived for decades or even indefinitely, the used cryptographic primitives can become insecure during the archival time. This is a serious issue because it can be exploited by attackers to compromise the protection goals of the archived documents. Therefore, a requirement for long-term protection schemes is to address the aging of cryptography, i.e. replacing the used primitives properly before they become insecure. In this work we analyze and improve long-term protection schemes for digital archives. More precisely, we aim at answering three questions. (1) How do long-term protection schemes compare with respect to trustworthiness? (2) How do they differ in performance? (3) Can new schemes be designed, which generate more efficient and trustworthy evidence needed to establish the protection goals? Although several protection schemes can be found in the literature, many of them fail in addressing the aging of cryptography. Therefore, our first step is to identify which existing schemes provide long-term protection with respect to integrity, authenticity, non-repudiation, and proof of existence. Afterwards, to answer question (1) we analyze the trustworthiness of the long-term protection schemes using two approaches. In the first approach, we initially identify the required trust assumptions. Then, based on these assumptions, we compare the protection schemes. In the second approach, we turn to quantifying the trustworthiness of the evidence generated by time-stamping and notarial schemes. To this end, we use a belief trust model and design a reputation system. This leads to two further, more detailed answers to question (1). First, that trustworthiness depends on the reputation of the involved parties rather than the protection schemes themselves. Second, the trustworthiness of evidence tends to degrade in the long term. Therefore, we propose to use the reputation system to create incentives for the involved parties to build good reputation. This raises the trustworthiness of generated evidence, hence addressing question (3). Next, we address question (2) by analyzing how schemes differ in performance using an analytical evaluation and experiments. More precisely, we measure the times needed to create and verify evidence, the space required to store evidence, and the communication necessary to generate evidence. Moreover, this analysis shows that while verifying evidence most of the time is spent on checking certificate chains. The findings in the performance analysis provide us with directions for addressing question (3). We propose three new solutions that provide more efficient evidence. The first solution is a new notarial scheme that generates smaller evidence and that communicates less data than the existing notarial scheme. Novelties in our scheme include balancing the numbers of signatures that users and notaries verify, and using notaries as time-stamp authorities to provide proof of existence. The second solution is based on the time-stamping scheme Content Integrity Service (CIS) and allows for faster evidence verification. To the best of our knowledge, CIS is the only scheme designed for an archive where documents are submitted and time-stamped sequentially but share the same sequence of time-stamps. However, in this case the validities of several time-stamps in this sequence may overlap. Consequently, many of these time-stamps need not be checked when verifying the time-stamp sequence for one document. We address this issue in our new scheme by using a data structure called skip list. The result is a time-stamp sequence where users can skip the time-stamps that are not necessary to guarantee the protection goals of one document. Using an analytical evaluation and experiments, we show that our scheme is notably faster than CIS. The third solution is intended to reduce time spent on checking certificate chains when verifying evidence generated by time-stamping schemes. More precisely, we improve an existing public key infrastructure-based solution where the root certification authority generates smaller verification information for time-stamps. This verification information can be used to replace the certificate chains needed to verify time-stamps. However, this solution requires extra work from time-stamp authorities and the root certification authority, especially when the number of time-stamps grows significantly. In our solution, this issue is addressed such that this extra work is independent of the number of time-stamps. Using an analytical evaluation we demonstrate the advantage of our solution. Finally, we provide our conclusions and future work. In this thesis we design new solutions that allow for more efficient and trustworthy evidence of protection for archived documents. As future work, we suggest conducting more research in the direction of developing methods that address the decay of the trustworthiness of evidence over time