## 4 Concisely Indexed Multi-Keyword Rank Search
### Encrypted Search on the Cloud  
To do encrypted search on the cloud, the condensed index is incorporated to the encryption scheme proposed in [10]. For completeness, the scheme is briefly described as follows. The data owner would generate the secret key set \(SK=\left\{\mathbf{s},M_{1},M_{2}\right\}\), where \(\mathbf{s}\) is a \(r\)-bit binary vector with 0 and 1 generated randomly, and \(M_{1}\) and \(M_{2}\) are \(r\times r\) invertible matrices. Let \(\mathbf{h}\) be a condensed document index generated as in Equation (17). To generate the encrypted document indexes, the condensed index \(\mathbf{h}\) is first split by \(\mathbf{s}\) to \(\mathbf{h}^{\prime\prime}\) and \(\mathbf{h}^{\prime\prime}\) as follows:  
\[\left\{ \begin{array}{ll}\text{if }s_{k}=1,&\mathbf{h}_{k}^{\prime}=\mathbf{h} _{k}^{\prime\prime}=\mathbf{h}_{k}\\ \text{Otherwise, }&\mathbf{h}_{k}^{\prime}+\mathbf{h}_{k}^{\prime\prime}=\mathbf{h} _{k}\end{array} \right.,\forall 1\leq k\leq r, \tag{19}\]where \(s_{k}\), \(\mathbf{h}_{k}\), \(\mathbf{h}^{\prime}_{k}\), and \(\mathbf{h}^{\prime\prime}_{k}\) are the \(k\)th element of \(\mathbf{s}\), \(\mathbf{h}\), \(\mathbf{h}^{\prime}\), and \(\mathbf{h}^{\prime\prime}\), respectively. Essentially, if \(\mathbf{s}_{k}\) is 1, \(\mathbf{h}^{\prime}_{k}\) and \(\mathbf{h}^{\prime\prime}_{k}\) are equal to \(\mathbf{h}_{k}\); otherwise, \(\mathbf{h}^{\prime}_{k}\) and \(\mathbf{h}^{\prime\prime}_{k}\) are randomly set such that \(\mathbf{h}^{\prime}_{k}+\mathbf{h}^{\prime\prime}_{k}=\mathbf{h}_{k}\). The encrypted document index is then given by  
\[\mathbf{\hat{h}}=\left\{M^{T}_{1}\mathbf{h}^{\prime},M^{T}_{2}\mathbf{h}^{ \prime\prime}\right\}. \tag{20}\]  
The documents are also encrypted by a certain symmetric encryption scheme. The data owner stores the encrypted documents and the associated encrypted document indexes on the cloud server. When a data user proposes a search, the user sends the keywords to the data owner. The data owner will generate the condensed query vector and encrypt it to build the trapdoor. Suppose that the condensed query vector \(\mathbf{g}\) is generated as in Equation (18). Similarly, \(\mathbf{g}\) is split into two vectors \(\mathbf{g}^{\prime}\) and \(\mathbf{g}^{\prime\prime}\) as follows. \[\left\{ \begin{array}{rl}\text{if }s_{k}=1,&\mathbf{g}^{\prime}_{k}+\mathbf{g}^{ \prime\prime}_{k}=\mathbf{g}_{k}\\ \text{Otherwise,}&\mathbf{g}^{\prime}_{k}=\mathbf{g}^{\prime\prime}_{k}= \mathbf{g}_{k}\end{array} \right.,\forall 1\leq k\leq r. \tag{21}\]  
where \(s_{k}\), \(\mathbf{g}_{k}\), \(\mathbf{g}^{\prime}_{k}\), and \(\mathbf{g}^{\prime\prime}_{k}\) are the \(k\)th element of \(\mathbf{s}\), \(\mathbf{g}\), \(\mathbf{g}^{\prime}\), and \(\mathbf{g}^{\prime\prime}\), respectively. The trapdoor is generated by  
\[\mathbf{\hat{g}}=\left\{M^{-1}_{1}\mathbf{g}^{\prime},M^{-1}_{2}\mathbf{g}^{ \prime\prime}\right\}. \tag{22}\]  
The trapdoor is then given to the data user and transmitted to the cloud server. Note that, to further obfuscate the query, a vector with small random numbers can be added to the trapdoor for every query, so the cloud server will receive different trapdoor, even for the same query keywords as in [10]. After the data user sends the trapdoor to the cloud server to request a search, the cloud server performs the following computation to calculate the relevance score of the query and the documents. \[RScore = \mathbf{\hat{h}}_{j}\cdot\mathbf{\hat{g}} \tag{23}\] \[= \left\{M^{-1}_{1}\mathbf{h}^{\prime}_{j},M^{T}_{2}\mathbf{h}^{ \prime\prime}_{j}\right\}.\left\{M^{-1}_{1}\mathbf{g}^{\prime},M^{-1}_{2} \mathbf{g}^{\prime\prime}\right\}\] \[= \mathbf{h}^{\prime}_{j}\cdot\mathbf{g}^{\prime}+\mathbf{h}^{ \prime\prime}_{j}\cdot\mathbf{g}^{\prime\prime}\] (24) \[= \mathbf{h}_{j}\cdot\mathbf{g}\hskip 56.905512 pt,\forall 1\leq j\leq n\]  
The \(RScore\) is an approximation of the relevance computed by Equation (2). However, in general, the higher the \(RScore\), the better the corresponding document fits the user's request.