Query: Searchable Encryption

title: Lattice Based Public Key Searchable Encryption from Experimental Perspectives
abstract: Public key Encryption with Keyword Search (PEKS) aims in mitigating the impacts of data privacy versus utilization dilemma by allowing any user in the system to send encrypted files to the server to be searched by a receiver. The receiver can retrieve the encrypted files containing specific keywords by providing the corresponding trapdoors of these keywords to the server. Despite their merits, the existing PEKS schemes introduce a high end to end delay that may hinder their adoption in practice. Moreover, they do not scale well for large security parameters and provide no post quantum security promises. In this paper, we propose two novel lattice based PEKS schemes that offer a high computational efficiency along with better security assurances than that of the existing alternatives. Specifically, our NTRU PEKS scheme achieves 18 times lower end to end delay than the most efficient pairing based alternatives. Our LWE PEKS offers provable security in the standard model with a reduction to the worst case lattice problems. We fully implemented our NTRU PEKS scheme and benchmarked its performance as deployed on Amazon Web Services cloud infrastructures.

title: Dynamic Multi Phrase Ranked Search over Encrypted Data with Symmetric Searchable Encryption
abstract: As cloud computing becomes prevalent, more and more data owners are likely to outsource their data to a cloud server. However, to ensure privacy, the data should be encrypted before outsourcing. Symmetric searchable encryption allows users to retrieve keyword over encrypted data without decrypting the data. Many existing schemes that are based on symmetric searchable encryption only support single keyword search, conjunctive keywords search, multiple keywords search, or single phrase search. However, some schemes, i.e. static schemes, only search one phrase in a query request. In this paper, we propose a multi phrase ranked search over encrypted cloud data, which also supports dynamic update operations, such as adding or deleting files. We used an inverted index to record the locations of keywords and to judge whether the phrase appears. This index can search for keywords efficiently. In order to rank the results and protect the privacy of relevance score, the relevance score evaluation model is used in searching process on client side. Also, the special construction of the index makes the scheme dynamic. The data owner can update the cloud data at very little cost. Security analyses and extensive experiments were conducted to demonstrate the safety and efficiency of the proposed scheme.

title: Flexible Wildcard Searchable Encryption System
abstract: Searchable encryption is an important technique for public cloud storage service to provide user data confidentiality protection and at the same time allow users performing keyword search over their encrypted data. Previous schemes only deal with exact or fuzzy keyword search to correct some spelling errors. In this paper, we propose a new wildcard searchable encryption system to support wildcard keyword queries which has several highly desirable features. First, our system allows multiple keywords search in which any queried keyword may contain zero, one or two wildcards, and a wildcard may appear in any position of a keyword and represent any number of symbols. Second, it supports simultaneous search on multiple data owner's data using only one trapdoor. Third, it provides flexible user authorization and revocation to effectively manage search and decryption privileges. Fourth, it is constructed based on homomorphic encryption rather than Bloom filter and hence completely eliminates the false probability caused by Bloom filter. Finally, it achieves a high level of privacy protection since matching results are unknown to the cloud server in the test phase. The proposed system is thoroughly analyzed and is proved secure. Extensive experimental results indicate that our system is efficient compared with other existing wildcard searchable encryption schemes in the public key setting.

title: Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency
abstract: Recently, several practical attacks raised serious concerns over the security of searchable encryption. The attacks have brought emphasis on forward privacy, which is the key concept behind solutions to the adaptive leakage exploiting attacks, and will very likely to become a must have property of all new searchable encryption schemes. For a long time, forward privacy implies inefficiency and thus most existing searchable encryption schemes do not support it. Very recently, Bost (CCS 2016) showed that forward privacy can be obtained without inducing a large communication overhead. However, Bost's scheme is constructed with a relatively inefficient public key cryptographic primitive, and has poor I/O performance. Both of the deficiencies significantly hinder the practical efficiency of the scheme, and prevent it from scaling to large data settings. To address the problems, we first present FAST, which achieves forward privacy and the same communication efficiency as Bost's scheme, but uses only symmetric cryptographic primitives. We then present FASTIO, which retains all good properties of FAST, and further improves I/O efficiency. We implemented the two schemes and compared their performance with Bost's scheme. The experiment results show that both our schemes are highly efficient.

title: Achieving Secure and Efficient Dynamic Searchable Symmetric Encryption over Medical Cloud Data
abstract: In medical cloud computing, a patient can remotely outsource her medical data to the cloud server. In this case, only authorized doctors are allowed to access the data since the medical data is highly sensitive. Before outsourcing, the data is commonly encrypted, where the corresponding secret key is sent to authorized doctors. However, performing searches on encrypted medical data is difficult without decryption. In this paper, we propose two Secure and Efficient Dynamic Searchable Symmetric Encryption (SEDSSE) schemes over medical cloud data. First, we utilize the secure k Nearest Neighbor (kNN) and Attribute Based Encryption (ABE) techniques to construct a dynamic searchable symmetric encryption scheme, which can achieve forward privacy and backward privacy simultaneously. These tow security properties are vital and very challenging in the area of dynamic searchable symmetric encryption. Then, we propose an enhanced scheme to solve the key sharing problem which widely exists in the kNN based searchable encryption scheme. Compared with existing proposals, our schemes are better in terms of storage, search and updating complexity. Extensive experiments demonstrate the efficiency of our schemes on storage overhead, index building, trapdoor generating and query.

title: Secure Channel Free Certificate Based Searchable Encryption Withstanding Outside and Inside Keyword Guessing Attacks
abstract: Searchable public key encryption (SPKE) is a useful public key cryptographic primitive that allows a user to perform keyword searches over publicly encrypted messages on an untrusted storage server while guaranteeing the privacy of the original messages as well as the search keywords. However, most of the previously proposed SPKE frameworks suffer from the security vulnerability caused by the keyword guessing attack and some other weaknesses. Inspired by the ideas of certificate based cryptography and signcryption, we present a new SPKE framework called certificate based searchable encryption. The new framework not only provides resistance to the existing known types of keyword guessing attacks, but also enjoys some appealing merits, such as implicit authentication, no key escrow and no secure channel. Under this new framework, we devise a concrete searchable certificate based encryption scheme. In the random oracle model, it is proven to meet the keyword ciphertext indistinguishability, the keyword ciphertext unforgeability and the keyword trapdoor indistinguishability under the adaptive chosen keyword attack. The comparisons indicate that it is secure and practicable.

title: Blockchain based searchable encryption for electronic health record sharing
abstract: Data leakage in electronic health records (EHRs) could result in the compromise of patient privacy (e.g. medical conditions) Generally most data in EHRs remain unchanged once they are uploaded to the system; thus, blockchain can be potentially used to facilitate the sharing of such data. Different participating medical organizations and individuals (e.g. medical practitioners, hospitals, medical labs and insurance companies) can then access EHRs stored on the blockchain with a higher level of confidence. In this paper, a blockchain based searchable encryption scheme for EHRs is proposed. The index for EHRs is constructed through complex logic expressions and stored in the blockchain, so that a data user can utilize the expressions to search the index. As only the index is migrated to the blockchain to facilitate propagation, the data owners have full control over who can see their EHRs data. The use of blockchain technology ensures the integrity, anti tampering, and traceability of EHRs' index. Finally, the performance of the proposed scheme is evaluated from two aspects, namely in terms of the overhead for extracting the document IDs from EHRs and the overhead associated with conducting transactions on smart contract in Ethereum.

title: An efficient KP design framework of attribute based searchable encryption for user level revocation in cloud
abstract: Attribute based searchable encryption (ABSE) is the combination of attribute based encryption (ABE) and searchable encryption with the inherent benefits of fine grained access control and expressive searching capabilities in multiuser setting. In this paper, we have used the key policy (KP) design framework of ABE and named the scheme KP ABSE. The proposed KP ABSE scheme efficiently supports user revocation where the computationally intensive tasks are delegated to the cloud server. Furthermore, the proposed scheme generates constant size user secret keys and trapdoors and has constant number of pairing operations, which in other schemes typically varies with the number of attributes associated with them. Thus, the proposed scheme reduces computational and storage costs and supports fast searching. Finally, the proposed scheme can be proven secure under a decision linear assumption in a selective security model.

title: Multi User Verifiable Searchable Symmetric Encryption for Cloud Storage
abstract: In a cloud data storage system, symmetric key encryption is usually used to encrypt files due to its high efficiency. In order allow the untrusted/semi trusted cloud storage server to perform searching over encrypted data while maintaining data confidentiality, searchable symmetric encryption (SSE) has been proposed. In a typical SSE scheme, a users stores encrypted files on a cloud storage server and later can retrieve the encrypted files containing specific keywords. The basic security requirement of SSE is that the cloud server learns no information about the files or the keywords during the searching process. Some SSE schemes also offer additional functionalities such as detecting cheating behavior of a malicious server (i.e. verifiability) and allowing update (e.g. modifying, deleting and adding) of documents on the server. However, the previous (verifiable) SSE schemes were designed for single users, which means the searching can only be done by the data owner, whereas in reality people often use cloud storage to share files with other users. In this paper we present a multi user verifiable searchable symmetric encryption (MVSSE) scheme that achieves all the desirable features of a verifiable SSE and allows multiple users to perform searching. We then define an ideal functionality for MVSSE under the Universally Composable (UC security framework and prove that our ideal functionality implies the security requirements of a secure MVSSE, and our multi user verifiable SSE scheme is UC secure. We also implement our scheme to verify its high performance based on some real dataset.

title: Passive Attacks Against Searchable Encryption
abstract: Searchable encryption (SE) provides a privacy preserving mechanism for data users to search over encrypted data stored on a remote server. Researchers have designed a number of SE schemes with high efficiency yet allowing some degree of leakage profile to the remote server. The leakage, however, should be further measured to allow us to understand what types of attacks an SE scheme would encounter. This paper considers passive attacks that make inferences based on prior knowledge and observations on queries issued by users. This is in contrast to previously studied active attacks that adaptively inject files and queries. We consider several assumptions on the types or prior knowledge the attacker possessed and propose a few passive attacks. In particular, under the "full fledged" assumption, the keyword recovery rate of our attack is optimal in the sense that it is equal to the theoretical upper bound. We further present several enhanced attacks under other weaker assumptions on various levels of the prior knowledge that the attacker can obtain, in which the keyword recovery rates are optimal or nearly optimal (i.e. approaching the theoretical upper bound) In addition, we provide extensive experiments to show the "power" of our passive attacks. This paper highlights the importance of minimizing the prior knowledge of a server and the leakage of search queries. It also shows that simply distorting the frequency of the keyword to hold against our passive attacks may not scale well.