# Lightweight and Privacy-Preserving Multi-Keyword Search over Outsourced Data
## 1 Introduction
### Related Works  
The first single keyword searchable encryption scheme over outsourced encrypted data was proposed by [PERSON] et al. [16] in the symmetric key setting. Subsequently, many schemes supporting single keyword searching [17; 18; 19; 20] were designed. [PERSON] et al. [21] proposed a scheme supporting single-keyword boolean search over large outsourced dataset. However, the single keyword search mechanism cannot provide accurate search results. Since the cloud server usually stores massive amounts of data, there would be many pieces of matched data satisfying the search condition of a single keyword, and most of the search results may have no relation with the expected data. To support more sophisticated outsourcing search methods, many multi-keyword search schemes have been proposed [12; 22; 23; 24]. Such multi-keyword search mechanism has many advantages over the single keyword search. With the multi-keyword search method, users are able to implement more complicated search conditions on outsourced data, in such a way that the accuracy of search results could be greatly improved. Furthermore, the efficiency can be enhanced, since the users do not need to carry out multiple rounds of single keyword search to achieve the same effect of multi-keyword search. Thus, the multi-keyword search schemes can allow the cloud server to return the most relevant data, which are more practical than the single keyword search mechanism in supporting real-world applications. For example, the works [25; 26] support multi-keyword search with fully homomorphic encryption, refs. [22; 23; 27] conjunctive keyword search, ref. [24] multi-keyword fuzzy search, and [12] ranked multi-keyword search. In the public-key setting, the first searchable encryption scheme was proposed by [PERSON] et al. [13], where anyone can outsource encrypted data to the cloud server, but only the user holding the private key can issue search queries. [PERSON] et al. [28] constructed a searchable public-key ciphertexts scheme with hidden structures to achieve fast search. [PERSON] et al. [29] presented a public-key encryption scheme with keyword search from obfuscation, where the cloud server is given an obfuscated simple decrypt-then-compare circuit with the secret key to perform keyword search. [PERSON] et al. [30] designed a public-key multi-keyword searchable encryption scheme with a hidden structures model, which also supports boolean search over encrypted e-mails. [PERSON] et al. [31] proposed a tree-based public-key multi-dimensional range searchable encryption scheme from the predicate encryption method and leakage function. For [PERSON] and [PERSON]'s certificateless lightweight keyword searchable encryption scheme [32], it was proved to secure against inside keyword guessing attacks in Industrial Internet of Things setting. To enrich the functionality of searching over remote data, various practical schemes have been designed. [PERSON] and [PERSON] [33] proposed a fuzzy search scheme over encrypted data using bloom filter. [PERSON] et al. [34] noticed that [PERSON] and [PERSON]'s proposal [33] cannot resist the sparse non-negative matrix factorization based attacks and further presented a multi-keyword fuzzy search scheme using random redundancy method. [PERSON] et al. [11] designed a semantic-aware search scheme, where both the index and search trapdoor contain two vectors. [PERSON], [PERSON] and [PERSON] [35] proposed a multi-keyword ranked searchable encryption scheme in multi-user setting, which does not require the keyword set to be predefined and supports keywords in arbitrary language and flexible search authorization. [PERSON] et al. [36] constructed a multi-keyword search scheme in wireless body area networks, which also supports access control on electronic health records. [PERSON] et al. [37] designed a privacy-preservation phrase with multi-keyword ranked searching scheme, which employs optimized filtering and binary tree index structure to improve the search efficiency. [PERSON] et al.