PROPYLA: Privacy Preserving Long-Term Secure Storage

An increasing amount of information today is generated, exchanged, and stored electronically. This includes sensitive information such as health records or governmental documents whose integrity and confidentiality must be protected over decades or even centuries. Commonly used cryptographic schemes, however, are not designed to provide protection over such long time periods. They are vulnerable to computational attacks that will potentially become possible using advanced computational technology (e.g., quantum computers). Recently, Braun et al. (AsiaCCS 2017) proposed the first storage architecture that uses information-theoretically secure and renewable cryptography to achieve long-term confidentiality and integrity protection. However, they only consider a simplified storage setting where unstructured data is stored and protected, which means that subsets of the data cannot be retrieved individually. Here, we consider a more realistic setting where structured data is stored, and selected parts of the data can be retrieved individually. In this setting, however, a storage provider may not only be able to deduce sensitive information about its customers by analyzing the stored data content, but also by analyzing which data items are accessed at which times. We propose the first long-term secure storage architecture that prevents this by providing integrity, confidentiality, and access pattern hiding. To achieve this, we combine several long-term protection techniques with an information-theoretically secure oblivious random access machine. In a performance analysis of our construction we show that storing and protecting data over a timespan of 100 years is practical.