Establishing the Theoretical Bounds in the Relationship Between Locality, Storage, Read Efficiency, and Storage Notion in a Dynamic Searchable Symmetric Encryption - Research Significance

Establishing the Theoretical Bounds in the Relationship Between Locality, Storage, Read Efficiency, and Storage Notion in a Dynamic Searchable Symmetric Encryption

Research Significance

Searchable encryption secures the privacy of one’s search over encrypted data.  One of its popular application models allows a data owner to store encrypted data to a server which can effectively perform keyword-based search over encrypted data according to a query trapdoor submitted by a data user.  The owner’s data and the user’s queries are kept secret in the server. Recently, many searchable encryptions have been proposed to achieve better security and performance, provide secure data updatable feature, and search results verifiable capability. However, most of the existing works endow the data user unlimited search capacities and do not consider a data user’s search permissions. In practical applications, granting search privileges for data users is a very important measure to enforce data access control.

Major concern over the security of searchable encryption schemes has become an important issue for discussion. There have been attacks (Zhang, et al., 2016) that have been devised that would allow an untrusted server to recover the keywords in the client’s search tokens, and in consequence, to learn a significant amount of information about the outsourced These attacks are normally performed by utilizing information leaked in the searching and updating phase, and they are pervasive because the information leakage exists inevitably in any searchable encryption scheme. A simple yet effective adaptive attack that can fully reveal the client’s queries by injecting only a small number - usually less than 100 files - to the encrypted data store has been performed raising more concerns in terms of the safety of the customers’ data (Zhang, et al.2016). The result has been devastating since the attack not only enabled the server to learn partial information about the encrypted data, the recovered keywords have also helped the server in other statistical attacks. The essential idea of the attacks is that the server first crafts a set of files, with each containing certain keywords, then sends the files to the client and tricks the client into encrypting them. After the client has encrypted and uploaded the injected files, the server can use the tokens previously submitted by the clients to search on the injected files. By knowing which keywords are in each injected file and observing which files matches the token, the server can deduce easily which keyword is encrypted in the token (Song, et al., 2017).

Dynamic searchable symmetric encryption (DSSE) is a useful cryptographic tool in the encrypted cloud storage. It provides data dynamics that allows the client to update data over the time without losing data confidentiality and searchability. Due to this property, DSSE is highly demanded in encrypted cloud. However, many existing DSSE schemes (Cash, et al., 2014) suffer from the file-injection attacks (Zhang, et al., 2016), where the adversary can compromise the privacy of a client query by injecting a small portion of new documents to the encrypted database. To resist this attack, Zhang et al. [22] highlighted the need of forward security that was informally

Searchable encryption facilitates cloud server to search over encrypted data without decrypting the data. Single keyword based searchable encryption enables a user to access only a subset of documents, which contains the keyword of the user's interest. Verifiable Searchable Symmetric Encryption, as an important cloud security technique, allows users to retrieve the encrypted data from the cloud through keywords and verify the validity of the returned results. Dynamic update for cloud data is one of the most common and fundamental requirements for data owners in such schemes. To the best of our knowledge, the existing verifiable SSE schemes supporting data dynamic update are all based on asymmetric-key cryptography verification, which involves time-consuming operations. The overhead of verification may become a significant burden due to the sheer amount of cloud data. Therefore, how to achieve keyword search over dynamic encrypted cloud data with efficient verification is a critical unsolved problem. To address this problem, we explore achieving keyword search over dynamic encrypted cloud data with symmetric-key based verification and propose a practical scheme in this paper. In order to support the efficient verification of dynamic data, we design a novel Accumulative Authentication Tag (AAT) based on the symmetric-key cryptography to generate an authentication tag for each keyword. Benefiting from the accumulation property of our designed AAT, the authentication tag can be conveniently updated when dynamic operations on cloud data occur. In order to achieve efficient data update, we design a new secure index composed by a search table ST based on the orthogonal list and a verification list VL containing AATs. Owing to the connectivity and the flexibility of ST, the update efficiency can be significantly improved. The security analysis and the performance evaluation results show that the proposed scheme is secure and efficient (Ge, et al., 2019).