# A Search Efficient Privacy-Preserving Location-Sharing Scheme in Mobile Online Social Networks
## 5 Search Efficient Privacy-Preserving Location-Sharing (SELS) Scheme
Note that \(A\) is the default state and \(F\) means only the current grid cell can not be searched by the location-sharing request of his/her friends (i.e., the current grid cell is a sensitive area that \(U\) does not want his/her friends to know). However, if \(U\) is no longer in this grid cell, \(U\) can be searched by the location-sharing requests of his/her friends. 2. If \(A\) is included in \(U\)'s submitted message, \(B\) will send a message in the form of \(SecK_{B4S}(ID_{U},GFID)\) to \(SNS\), where \(GFID\) is the fake-ID of the grid cell where \(B\) locates. Figure 4: Mapping relationship update. Figure 3: Registration. For example, if \(U\) offers update information through base station \(B_{a}\) which locates in \(GFID_{a}\), then \(B_{a}\) will send \(SecK_{B\&S}(ID_{U},GFID_{a})\) to \(SNS\). After receiving the update information, \(SNS\) will reply a message \(OK\) to \(B\) which then forwards \(OK\) to \(U\). If \(U\)'s submitted message includes \(F\), \(B\) will do nothing. 3. \(B\) sends a message in the form of \(((PID_{1},x_{1},y_{1},str_{1},df_{1},ds_{1}),\ldots,(PID_{k},x_{k},y_{k},str_{ k},df_{k},ds_{k}))\) to \(LS\), where \(PID\) is the pseudo-ID set of \(U\) and \(str\) is a random string to imitate the encrypted location. Herein, suppose that \(ind~{}=~{}1\) in the last mapping relationship update, then \((PID_{1},x_{1},y_{1},SecK_{U}(x_{1},y_{1}),df_{1},ds_{1})\) represents the real information of \(U\), and \(((PID_{2},x_{2},y_{2},str_{2},df_{2},ds_{2}),\ldots,(PID_{k},x_{k},y_{k},str_{ k},df_{k},ds_{k}))\) indicates the dummies of \(U\). Then \(LS\) stores the information in its database and sends a response in the form of \({}^{\prime}OK^{\prime}\) to \(B\) which then forwards \({}^{\prime}OK^{\prime}\) to \(U\). Querying friends' locations. Users can request a location query for searching friends' locations. If user \(U\) wants to request a location sharing with nearby friends, \(U\) needs to submit a request for querying friends' locations through a nearby base station. Note that the base station and the user are assumed to be in the same grid cell. Figure 6 shows the specific process of querying friends' locations. The detailed steps are as follows:  
1. \(U\) needs to submit a query in the form of \((ID_{U},f,l)\) to \(B\), where \(f\) means this query is a request for querying friends' locations and \(l\) indicates the specified query distance such as 2 km. 2. When receiving \(U\)'s query, \(B\) first figures out the associated grids of \(U\) (see Section 3.2) based on \(U\)'s query distance \(l\), and form a list \(GFID_{list}\) which contains the fake-ID set of the associated grids. The purpose of finding out the list \(GFID_{list}\) is to help \(SNS\) filter out \(U\)'s friends that are not in the associated grids. Then, \(B\) encrypts its identifier \(BID\) and \(seq\) with \(SecK_{B\&L}\) to form \(SecK_{B\&L}\) (\(BID,seq\)), where \(seq\) is a sequence number to resist the replay attack. Finally, \(B\) sends the message \((ID_{U},f,l,SecK_{B\&L}(BID,seq),GFID_{list})\) to \(SNS\). 3. According to \(U\)'s social network graph and users' location update information, \(SNS\) finds out the \(U\)'s friends who are in \(GFID_{list}\) (i.e., seeking out \(U\)'s friends whose locations are in \(GFID_{list}\)). Suppose that there are \(m\) users meeting the above condition, where \(m\leq n\) and \(n\) is the total number of \(U\)'s friends. Then \(SNS\) will collect these users' \(PID_{list}\) to form a set \(\{PID_{ij}\}\), where \(1\leq i\leq k\) and \(1\leq j\leq m\). The purpose of forming \(\{PID_{ij}\}\) is to perturb the identity information of \(U\)'s friends. Finally, \(SNS\) sends a query in the form of \((PID_{ind},l,\{PID_{ij}\},SecK_{B\&L}(BID,seq))\) to \(LS\), where \(PID_{ind}\) represents the real pseudo-ID of \(U\). 4.