## 2 Related Work  
The issue for searching over encrypted data to protect users' privacy and data security has been studied for the recent cloud computing environment [1; 2; 3; 4; 5; 6; 7]. The goal is to prevent the untrust cloud server to know details about the data and users' query during the search. The early work in [1] suggested that the encrypted search on the untrusted server should fulfill four features--query isolation, controlled searching, hidden query, and provably secure. Query isolation indicates that the untrusted server cannot learn anything about the data content more than the search results. Controlled searching prevents the untrusted server from searching the data without the data owner's authorization. Hidden query means that the user can ask the untrusted server to perform the search without revealing the search keyword to the server. Certainly, the scheme should be provable for secure. Conventional techniques to perform secure search over encrypted data include SearchableSymmetric Encryption (SSE) [2; 7; 8] and public key-based cryptography [4; 9]. Symmetric encryption is a cryptography scheme, in which the same key is used to encrypt the plaintext and decrypt the ciphertext. Searchable symmetric encryption allows the data to be stored in the third party storage, while still maintaining the capability to search for the encrypted data. For the public key-based cryptography scheme, the data content and index keywords are encrypted separately. A secret key is sent to the third party server by the data owner, and the third party server can use the key to identify whether a particular keyword is in the index, without learning anything else about the data content [4]. [PERSON] et al. use bloom filter to construct the secure index for documents [2]. Bloom filter requires a relatively small space to store the keyword set and calculates via hash coding. Nevertheless, it also reduces the correctness of the results, since the error rate inherited the hash coding. [PERSON] et al. further define the searchable encryption mechanism and proposed an index based scheme with the inverted list to link the same keywords in different files [7]. In [6], [PERSON] et al. proposes a ranked keyword search scheme for encrypted cloud data. The returned documents are in the order of certain score function, for instance, the frequency of the keyword in the associated documents. However, these studies only support single keyword encryption search. While single keyword search is sufficient for certain applications, multiple keyword search is more appropriate for most of the practical usage. In [10], a scheme for multi-keyword ranked search over encrypted data is presented. The scheme adopts the similarity measure based on coordinate matching, i.e., as many matches as possible, to characterize the relevance of the documents to the query. The paper also improves the proposed scheme to fulfill various privacy requirements, such as adding a small random perturbation in the query to further obfuscate the search each time. The perturbation trades off the search precision to privacy requirements. In [11], a tree-based search scheme is developed to increase the search efficiency. The above work adopts a vector based document indexes and uses inner product to measure the similarity. However, they may use a long index for a document, and reduce the space and time efficiency of the scheme. Multi-keyword boolean search has also been studied to enrich query predicates for encryption search. Two major types of boolean keyword search are commonly studied in the literature, namely conjunctive keyword search [3; 5; 9] and disjunctive keyword search [12; 13]. For conjunctive keyword search, the returned documents have to completely match all the query keywords. In contrast, for disjunctive keyword search, the documents that satisfy a subset of the query conditions can be used as the answer. Predicate search schemes are also developed to resolve both conjunctive and disjunctive keyword search [14; 15].