Huge amounts of information today are stored digitally and a significant amount of this information (e.g., health records) must be kept unaltered and confidential over long periods of time (i.e., decades or centuries). Consequently, there is a high demand for protection schemes that can ensure integrity and confidentiality over such long time periods. The cryptographic schemes used today for protecting integrity and confidentiality (e.g., RSA signatures and AES encryption), however, are not designed to provide long-term protection as their security relies on computational assumptions (e.g., that factoring large integers is infeasible) and trust assumptions (e.g., that a secret key is not compromised) which cannot be guaranteed over such long time periods. To achieve long-term integrity protection Bayer, Haber, and Stornetta proposed a method for prolonging the validity of digital signatures by using cryptographic timestamping. The security of this method, however, is unclear as no precise security analysis has been performed. To achieve long-term confidentiality protection there exist information-theoretically secure schemes (e.g., Quantum Key Distribution, One-Time-Pad Encryption, or Secret Sharing) whose security does not depend on computational assumptions. However, so far it is unclear whether information-theoretic confidentiality protection can be combined with prolongable integrity protection.

This thesis answers both of these research questions. In the first part, we develop the first formal security models and proofs for several long-term integrity protection schemes that are derived from the ideas of Bayer, Haber, and Stornetta. We first develop a novel computational model that captures long-lived adversaries whose computational power increases over time. Then, using this model, we show that signature-based long-term integrity protection can be constructed from short-term unforgeable signature schemes and that hash-based long-term integrity protection can be constructed from short-term preimage-aware hash functions. We also propose a new cryptographic primitive called long-term commitment, which is crucial for the second part of this thesis. In the second part we then present the first storage system that combines information-theoretic confidentiality protection with prolongable integrity protection. We also propose two extensions of this system, where the first enables long-term access pattern hiding security (i.e., it remains secret which data items are accessed by the user at which times) and the second improves the efficiency when storing large complex datasets.