While cloud storage services offer manifold benefits such as cost-effectiveness or elasticity, there also exist various security and privacy concerns. Among such concerns, we pay our primary attention to data residency — a notion that requires outsourced data to be retrievable in its entirety from local drives of a storage server in-question. We formulate such notion under a security model called Proofs of Data Residency (PoDR). can be employed to check whether the data are replicated across different storage servers, or combined with storage server geolocation to ‘locate’ the data in the cloud. We make key observations that the data residency checking protocol should exclude all server-side computation and that each challenge should ask for no more than a single atomic fetching operation. We illustrate challenges and subtleties in protocol design by showing potential attacks to naive constructions. Next, we present a secure PoDR scheme structured as a timed challenge-response protocol. Two implementation variants of the proposed solution, namely NVeri and EVeri, describe an interesting use-case of trusted computing, in particular the use of Intel SGX, in cryptographic timed challenge-response protocols whereby having the verifier co-locating with the prover offers security enhancement. Finally, we conduct extensive experiments to exhibit potential attacks to insecure constructions and validate the performance as well as the security of our solution.

Distributed data stores have been rapidly evolving to serve the needs of large-scale applications such as online gaming and real-time targeting. In particular, distributed key-value stores have been widely adopted due to their superior performance. However, these systems do not guarantee to provide strong protection of data confidentiality, and as a result fall short of addressing serious privacy concerns raised from massive data breaches. In this paper, we introduce EncKV, an encrypted key-value store with secure rich query support. First, EncKV stores encrypted data records with multiple secondary attributes in the form of encrypted key-value pairs. Second, it leverages the latest practical primitives for searching over encrypted data, i.e., searchable symmetric encryption and order-revealing encryption, and provides encrypted indexes with guaranteed security to support exact-match and range-match queries via secondary attributes of data records. Third, it carefully integrates these indexes into a distributed index framework to facilitate secure query processing in parallel. To mitigate recent inference attacks on encrypted database systems, EncKV protects the order information during range queries, and presents an interactive batch query mechanism to further hide the associations across data values on different attributes. We implement an EncKV prototype on a Redis cluster, and conduct an extensive set of performance evaluations on the Amazon EC2 public cloud platform. Our results show that EncKV effectively preserves the efficiency and scalability of plaintext distributed key-value stores.

Current trends in technology, such as cloud computing, allow outsourcing the storage, backup, and archiving of data. This provides efficiency and flexibility, but also poses new risks for data security. It in particular became crucial to develop protection schemes that ensure security even in the long-term, i.e. beyond the lifetime of keys, certificates, and cryptographic primitives. However, all current solutions fail to provide optimal performance for different application scenarios. Thus, in this work, we present MoPS, a modular protection scheme to ensure authenticity and integrity for data stored over long periods of time. MoPS does not come with any requirements regarding the storage architecture and can therefore be used together with existing archiving or storage systems. It supports a set of techniques which can be plugged together, combined, and migrated in order to create customized solutions that fulfill the requirements of different application scenarios in the best possible way. As a proof of concept we implemented MoPS and provide performance measurements. Furthermore, our implementation provides additional features, such as guidance for non-expert users and export functionalities for external verifiers.

Deduplication is a widely used technique for reducing storage space of cloud service providers. Yet, it is unclear how to support deduplication of encrypted data securely until the study of Bellare~\etal on message-locked encryption (Eurocrypt 2013). Since then, there are many improvements such as strengthening its security, reducing client storage,~\etc While updating a (shared) file is common, there is little attention on how to efficiently update large encrypted files in a remote storage with deduplication. To modify even a single bit, existing solutions require the trivial and expensive way of downloading and decrypting the large ciphertext. We initiate the study of updatable block-level message-locked encryption. We propose a provably secure construction that is efficiently updatable with $O(\log|F|)$ computational cost, where $|F|$ is the file size. It also supports proof-of-ownership, a nice feature which protects storage providers from being abused as a free content distribution network.

The amount of digital data that requires long-term protection of integrity, authenticity, and confidentiality grows rapidly. Examples include electronic health records, genome data, and tax data. In this paper we present the secure storage system LINCOS, which provides protection of integrity, authenticity, and confidentiality in the long-term, i.e., for an indefinite time period. It is the first such system. It uses the long-term integrity scheme COPRIS, which is also presented here and is the first such scheme that does not leak any information about the protected data. COPRIS uses information-theoretic hiding commitments for confidentiality-preserving integrity and authenticity protection. LINCOS uses proactive secret sharing for confidential storage of secret data. We also present implementations of COPRIS and LINCOS. A special feature of our LINCOS implementation is the use of quantum key distribution and one-time pad encryption for information-theoretic private channels within the proactive secret sharing protocol. The technological platform for this is the Tokyo QKD Network, which is one of worlds most advanced networks of its kind. Our experimental evaluation establishes the feasibility of LINCOS and shows that in view of the expected progress in quantum communication technology, LINCOS is a promising solution for protecting very sensitive data in the cloud.