Dynamic searchable symmetric encryption (DSSE) is a useful cryptographic tool in encrypted cloud storage. However, it has been reported that DSSE usually suffers from file-injection attacks and content leak of deleted documents. To mitigate these attacks, forward privacy and backward privacy have been proposed. Nevertheless, the existing forward backward-private DSSE schemes can only support single keyword queries. To address this problem, in this paper, we propose two DSSE schemes supporting range queries. One is forward-private and supports a large number of documents. The other can achieve backward privacy, while it can only support a limited number of documents. Finally, we also give the security proofs of the proposed DSSE schemes in the random oracle model.
However, designing a secure DSSE scheme is not an easy job. @cite_11 pointed out that only a small leakage leveraged by the adversary would be enough to compromise the privacy of clients' queries. A concrete attack named file-injection attack was proposed by @cite_13 . In this attack, the adversary can infer the concept of aclient queries by injecting a small portion of new documents into encrypted database. This attack also highlights the need for forward privacy which protects security of new added parts. Accordingly, we have backward privacy that protects security of new added parts and later deleted. These two security notions were first introduced by @cite_0 . The formal definitions of forward backward privacy for DSSE were given by Bost @cite_19 and @cite_14 , respectively. In @cite_19 , Bost also proposed a concrete forward-private DSSE scheme, it does not support physical deletion. Later on, @cite_5 proposed a forward-private DSSE scheme supporting physical deletion. Meanwhile, @cite_14 proposed a forward backward-private DSSE to reduce leakage during deletion. Unfortunately, all the existing forward backward-private DSSE schemes only support single keyword queries. Hence, forward backward-private DSSE supporting more expressive queries, such as range queries, are quite desired.
@cite_14 @cite_0 @cite_19 @cite_5 @cite_13 @cite_11
2766707306 2765463836 2539385377 2734727053
The recently proposed file-injection type attacks are highlighting the importance of forward security in dynamic searchable symmetric encryption (DSSE). Forward security enables to thwart those attacks by hiding the information about the newly added files matching a previous search query. However, there are still only a few DSSE schemes that provide forward security, and they have factors that hinder efficiency. In particular, all of these schemes do not support actual data deletion, which increments both storage space and computational complexity. In this paper, we design and implement a forward secure DSSE scheme with optimal search and update complexity, for both computation and communication point of view. As a starting point, we propose a new, simple, theoretical data structure, called dual dictionary that can take advantage of both the inverted and the forward indexes at the same time. This data structure allows to delete data explicitly and in real time, which greatly improves efficiency compared to previous works. In addition, our scheme provides forward security by encrypting the newly added data with fresh keys not related with the previous search tokens. We implemented our scheme for Enron email and Wikipedia datasets and measured its performance. The comparison with Sophos shows that our scheme is very efficient in practice, for both searches and updates in dynamic environments. Using dynamic Searchable Symmetric Encryption, a user with limited storage resources can securely outsource a database to an untrusted server, in such a way that the database can still be searched and updated efficiently. For these schemes, it would be desirable that updates do not reveal any information a priori about the modifications they carry out, and that deleted results remain inaccessible to the server a posteriori. If the first property, called forward privacy, has been the main motivation of recent works, the second one, backward privacy, has been overlooked. In this paper, we study for the first time the notion of backward privacy for searchable encryption. After giving formal definitions for different flavors of backward privacy, we present several schemes achieving both forward and backward privacy, with various efficiency trade-offs. Our constructions crucially rely on primitives such as constrained pseudo-random functions and puncturable encryption schemes. Using these advanced cryptographic primitives allows for a fine-grained control of the power of the adversary, preventing her from evaluating functions on selected inputs, or decrypting specific ciphertexts. In turn, this high degree of control allows our SSE constructions to achieve the stronger forms of privacy outlined above. As an example, we present a framework to construct forward-private schemes from range-constrained pseudo-random functions. Finally, we provide experimental results for implementations of our schemes, and study their practical efficiency. Searchable Symmetric Encryption aims at making possible searching over an encrypted database stored on an untrusted server while keeping privacy of both the queries and the data, by allowing some small controlled leakage to the server. Recent work shows that dynamic schemes -- in which the data is efficiently updatable -- leaking some information on updated keywords are subject to devastating adaptative attacks breaking the privacy of the queries. The only way to thwart this attack is to design forward private schemes whose update procedure does not leak if a newly inserted element matches previous search queries. This work proposes Sophos as a forward private SSE scheme with performance similar to existing less secure schemes, and that is conceptually simpler (and also more efficient) than previous forward private constructions. In particular, it only relies on trapdoor permutations and does not use an ORAM-like construction. We also explain why Sophos is an optimal point of the security performance tradeoff for SSE. Finally, an implementation and evaluation results demonstrate its practical efficiency. Releasing private data to the future is a challenging problem. Making private data accessible at a future point in time requires mechanisms to keep data secure and undiscovered so that protected data is not available prior to the legitimate release time and the data appears automatically at the expected release time. In this paper, we develop new mechanisms to support self-emerging data storage that securely hide keys of encrypted data in a Distributed Hash Table (DHT) network that makes the encryption keys automatically appear at the predetermined release time so that the protected encrypted private data can be decrypted at the release time. We show that a straight-forward approach of privately storing keys in a DHT is prone to a number of attacks that could either make the hidden data appear before the prescribed release time (release-ahead attack) or destroy the hidden data altogether (drop attack). We develop a suite of self-emerging key routing mechanisms for securely storing and routing encryption keys in the DHT. We show that the proposed scheme is resilient to both release-ahead attack and drop attack as well as to attacks that arise due to traditional churn issues in DHT networks. Our experimental evaluation demonstrates the performance of the proposed schemes in terms of attack resilience and churn resilience.