# An Efficient Approach for LBS Privacy Preservation in Mobile Social Networks
## 4 Motivation and System Model  
### Motivation  
As we all know, according to the characteristic of homomorphic encryption, if there are too many multiplications on ciphertext, the computational complexity will be high and the accuracy of the original message will be affected by the noise generated during multiplications process. Different from paper [8], which adopted multiplicative homomorphism to calculate the kinds of service category in the clustering process. In this paper, we adopt additive homomorphism to calculate the kinds of service category, the noise as well as the computational complexity can be reduced.  
In real applications, under the condition of specific time and space, users usually have common characteristics about interests or demands, so the kinds of service category that users request for LBS may be similar or even identical. For example, suppose that the site is an office building and the period is just off work time, the kinds of service category that users request are more likely as a restaurant or a supermarket rather than a post office or a bank (i.e., these departments or places are no longer within normal working hours). In addition, there is almost not only one clustering group in a region under normal circumstances. From a global perspective, the clustering process should be selective to improve the whole success rate of clustering in this region. The followings are two different scenarios that often appear.  
Scenario 1: As shown in Figure 7, assume that there are many clustering groups in region \(LA_{0}\), the \(tl_{k}\) is 6 and the \(tl_{l}\) is 4. If the clustering group \(CP_{1}\) already contains 6 users and the kinds of service category are 3, which means \(k\geq th_{k}\) but \(l<th_{l}\). When the new user \(U_{a}\) wants to participate in the clustering process of \(CP_{1}\), \(U_{a}\)'s kind of service category is the same as one of those kinds of service category in \(CP_{1}\). We can know that the participating of \(U_{a}\) cannot help \(CP_{1}\) to complete clustering, on the contrary, it just increases the load of \(CP_{1}\) and influences the success rate of other clustering  
Figure 5: \(th_{k}=5\) and \(th_{l}=3\).  
groups in region \(LA_{0}\). This scenario is what we define as a relatively dense scenario, which is more likely happen in a region with a dense population of specific time and space, rather than in an area with dense population inevitably.  
Scenario 2: As shown in Figure 8. Assume that there are two clustering groups in region \(LA_{1}\), the \(th_{k}\) is 4 and the \(th_{l}\) is 3. We also assume that the user \(U_{a}\) is the initiator of the clustering group \(CP_{1}\), which contains 3 users, and the kinds of service category are 2. The user \(U_{d}\) is the initiator of the clustering group \(CP_{2}\), which contains 2 users, and the kinds of service category are 2. If there are no other users who want to join in the two clustering groups above (i.e., \(CP_{1}\) and \(CP_{2}\)) within a certain period of time (i.e., the waiting time before the termination time), both the two clustering process cannot complete clustering, and only wait for the termination time of the two clustering groups. This scenario is what we define as a relatively sparse scenario, which is more likely happen in an area with a sparse population of specific time and space, rather than in an area with sparse population inevitably.