# An Efficient Approach for LBS Privacy Preservation in Mobile Social Networks
## 5 Algorithm Design
### Request Aggregation Protocol  
Generally speaking, assume that a user \(U_{1}\) is not in a clustering group of other users and wants to launch a request to the LBSP in his region. \(U_{1}\) should unite with other \(k-1\) users to form a clustering group. Algorithm 1 describes the pseudo code of the request aggregation protocol. The detailed explanation is as follows. User \(U_{1}\) firstly broadcasts the request aggregating message and sets the termination time T, and T starts counting down. If there are some users who want to join in the clustering process of \(U_{1}\), these users should return their pseudo-IDs to \(U_{1}\). Then \(U_{1}\) will count the number \(k\) of users who have responded. If the number (include \(U_{1}\) himself) \(k\geq 2\), \(U_{1}\) takes himself as the representative of the clustering group, which is symbolized by \(PID_{1}^{R}\), he names the clustering group as \(PID_{1}^{CP1}\). When the number of sums \(SL_{i}\) is obtained by one clustering group (i.e., this sum is obtained only from \(PID_{1}^{CP1}\)), the number of groups \(NCG_{PID_{1}^{R}}=1\). After the setting above, \(PID_{1}^{R}\) firstly uses his public key \(pk_{1}\) to encrypt his kind of service category \(L_{1}^{1}\). Then \(PID_{1}^{R}\) gives his \(pk_{1}\) and \(pk_{1}(L_{i}^{1})\) to members of this clustering group. Finally, the members use \(pk_{1}\) to encrypt their kinds of service category and return the result \(pk_{1}(SL_{i})=pk_{1}(L_{i}^{1})+pk_{1}(L_{i}^{2})+...+pk_{1}(L_{i}^{k})=pk_{1} (L_{i}^{1}+L_{i}^{2}+...+L_{i}^{k})\) to \(U_{1}\), where \(SL_{i}=\sum_{n=1}^{k}L_{i}^{n}\), \(1\leq i\leq th_{l}\). \(PID_{1}^{R}\) names this result of the clustering group as \(pk_{1}(SL_{i})^{CP1}\), which is the encrypted sum of kinds of service category in \(PID_{1}^{CP1}\). \(PID_{1}^{R}\) firstly uses his private key \(sk_{1}\) to decrypt \(pk_{1}(SL_{i})\) and gets \(SL_{i}\). Then \(PID_{1}^{R}\) uses variety judgment protocol to calculate the kinds of service category \(l\) in \(PID_{1}^{CP1}\). Note that here the kinds of service category \(l\geq 2\). Otherwise, \(U_{1}\) would know other users' kinds of service category in the current clustering group. There will be four cases as follows, and here assume that \(T>0\). Case 1: \(k\geq th_{k}\) and \(l\geq th_{l}\). \(U_{1}\) firstly notifies the members in \(PID_{1}^{CP1}\) to prepare their inputs based on their kinds of service category. Then he repackages their packets and gets an aggregated package, which is symbolized by \(Ag\). As the respective, \(U_{1}\) sends \(Ag\) to the LBSP. Case 2: \(k<th_{k}\) and \(l\geq th_{l}\). As explained in Section 3.4, k-anonymity is easier to be satisfied than l-diversity. So waiting for new users to join is a better choice for \(PID_{1}^{CP1}\). Under this situation, \(U_{1}\) does not need to judge new users' kinds of service category, and just wait for new users' joining to meet the condition \(th_{k}\). Case 3: \(k\geq th_{k}\) and \(l<th_{l}\). We know this case is the same as scenario 1, the filtering aggregation protocol will be carried out. The reasons why we choose it will be explained when we describe it. Case 4: \(k<th_{k}\) and \(l<th_{l}\). We know this case is the same as scenario 2, the representative aggregation protocol will be carried out. The reasons why we choose it will be also explained when we describe it. Figure 10: The scheme of service category table based algorithm (SCTB).