PROPYLA: Privacy Preserving Long-Term Secure Storage

The amount of electronically stored information increases rapidly. Sensitive information requires integrity and confidentiality protection, sometimes for decades or even centuries (e.g., health records or governmental documents). Commonly used cryptographic schemes, however, are not designed to provide protection over such long time periods. Their security usually relies on the hardness of a specific computational problem and security cannot be maintained against unforeseeable developments in computational technology (e.g., quantum computers breaking RSA-based systems). Recently, Braun et al.\ (\mboxAsiaCCS'17 ) proposed the first storage architecture that supports integrity protection renewal while guaranteeing information theoretic confidentiality. However, their solution only considers the storage of unstructured data and does not allow for reading or writing subparts of the data. Our contribution is the first long-term secure storage architecture that supports storage of structured databases and provides long-term integrity, confidentiality, and access pattern hiding security. To achieve this, we combine several cryptographic components (i.e., secret sharing, renewable timestamps, and renewable commitments) with an information-theoretically secure \mboxORAM such that the described security properties are achieved. We also prove our construction secure and show that it only introduces a small overhead compared to standard secret sharing and ORAM based storage solutions.