# A Security-Enhanced Query Result Verification Scheme for Outsourced Data in Location-Based Services
## 4 Proposed Scheme
### Data Outsourcing Process
#### 4.2.2 Design of Description File Verification Objects  
For each set of description files containing the keyword \(w_{i}\) (i.e., \(c(ds)_{w_{i}}\)), the LBSP prepares a counting Bloom filter \(VO_{w_{i}}\) with \(m\) counters, where the initial value of each counter is 0. Then, for each encrypted description file \(c\in c(ds)_{w_{i}}\), the LBSP uses the pseudo-random function (i.e., \(prf_{k}\)) to obtain the secret value \(prf_{k}(c)\) and utilizes the set \(H\) composed of \(l\) hash functions to hash \(prf_{k}(c)\), obtaining the set of hashed values \(\{h_{1}(prf_{k}(c))\in[0,m-1],\ldots,h_{l}(prf_{k}(c))\in[0,m-1]\}\). Finally, the LBSP enabling these hashed values can be represented in the counting Bloom filter, adding the corresponding counter \(vo_{w_{i}}[h_{j}(prf_{k}(c))]\) by 1, where \(1\leq j\leq l\), \(1\leq i\leq\theta\), and \(\theta\) indicate the total number of keywords. **Problem statement**: If the verification object \(VO_{w_{i}}\) is directly outsourced to the third party (i.e., the cloud side or the fog side), the number of description files represented in \(VO_{w_{i}}\) can be easily figured out by calculating \(\frac{\sum_{j=0}^{m-1}vo_{w_{i}}[j]}{l}\), where \(l\) is the number of hash functions. Therefore, the scheme in [9] proposed a novel structure for the verification object to fix the above issue by adding a padding region, shown in Figure 3. In the structure, the number of counters is extended to \(n\). The counters from 0 to \(m-1\) are inserted corresponding to description files of \(c(ds)_{w_{i}}\) by using \(prf_{k}\) and \(H\), and the counters from \(m\) to \(n\) are inserted corresponding to \(l\times|c(ds)_{w_{i}}|_{max}-\sum_{j=0}^{m-1}vo_{w_{i}}[j]\) random strings \(\{R_{1},R_{2},...\}\) by using a pad function \(P\) with the range \([m,n-1]\), where \(|c(ds)_{w\in W}|_{max}\) is the maximum number of description files containing the same keyword. The computed result \(P(R)=m+prf_{k}(R)\)\(mod\)\((n-m)\), \(R\in\{0,1\}^{*}\) is not 0, the corresponding counter \(vo_{w_{i}}[p(R)]\) is added by 1. Although the padding region can efficiently prevent the third party from calculating how many description files are contained in \(c(ds)_{w_{i}}\), the structure of the verification object is not perfect since this construction will leak some important information. For example, since each \(VO_{w_{i}}\) satisfies \(\sum_{j=0}^{n-1}vo_{w_{i}}[j]=l\times|c(ds)_{w\in W}|_{max}\). Then, the structure of the verification object \(VO_{max}\) is an exceptional layout since all of the values of counters in the padding region are 0, where \(VO_{max}\) represents the verification object of \(\{c(ds)_{w\in W}\}_{max}\). In other words, the value in the last \(m\) to \(n\) counters are all 0, as shown in Figure 4. Due to the layout shown in Figure 4, the third party can easily lock the verification object \(VO_{max}\) and further figure out the corresponding encrypted query. Consequently, the layout will support the third party to infer the meaning of the encrypted query index by investigating the data number of the POI type related to keyword \(w\). **Improved construction process of verification objects**: The main idea of our improved method is to set the sum of genuine description files and dummy description files of each keyword \(w\in W\) to be a fixed value \(S=|c(ds)_{w\in W}|_{max}+r\), where \(|c(ds)_{w\in W}|_{max}\) is the maximum number of genuine description files and \(r\) is a random value. \(|c(ds)_{w\in W}|_{max}-|c(ds)_{w}|+r\) indicates the number of dummy description files. Suppose that \(|c(ds)_{w\in W}|\) denotes the number of genuine description files for each keyword \(w\in W\), then the total number of description files that need to be represented (i.e., the number that needs to be inserted into the structure of the verification object) can be set as \(Sum=l\times(|c(ds)_{w\in W}|_{max}+r)\).