# A Search Efficient Privacy-Preserving Location-Sharing Scheme in Mobile Online Social Networks
## 5 Search Efficient Privacy-Preserving Location-Sharing (SELS) Scheme
After getting of the query from \(SNS\), \(LS\) runs the distance comparison function \(dis((x_{ind},y_{ind}),(x_{v},y_{v}))\leq min(l,df_{v})\), where \(dis\) is a function to compute Euclidean distance and \((x_{ind},y_{ind})\) is the coordinates of \(PID_{ind}\). \((x_{v},y_{v})\) represents the corresponding coordinates of pseudo-IDs in \(\{PID_{ij}\}\), where \(1\leq v\leq(k\times m)\). Suppose that there are \(w\)\(PID\)s satisfying the  
Figure 5: Location update. distance comparison function, then \(LS\) collects these \(w\)\(PID_{s}\) to form a set \(\{PID_{f}\}\) and finds the corresponding \(str\), where \(1\leq f\leq w\) and \(\{PID_{f}\}\subseteq\{PID_{ij}\}\). Finally, \(LS\) replies a message in the form of \((\{PID_{f},SecK_{B\&L}(str_{f})\}_{f=1,\ldots,w},SecK_{B\&L}(seq))\) to \(SNS\). Upon receiving \((\{PID_{f},SecK_{B\&L}(str_{f})\}_{f=1,\ldots,w},SecK_{B\&L}(seq))\), \(SNS\) recovers the real identifiers from \(\{PID_{f}\}\) to form a result set \(\{ID_{g}\}\) (i.e., the friends' real identifiers of \(U\)) based on the \(inds\) of \(U^{\prime}\) friends. The purpose of forming \(\{ID_{g}\}\) is to filter out dummies of \(U\)'s friends. Suppose that there are \(t\) users' \(ID\)s recovered from the result set, then \(SNS\) sends a message in the form of \((\{ID_{g},SecK_{B\&L}(str_{g})\}_{g=1,\ldots,t},SecK_{B\&L}(seq))\) to \(B\). Note that if \(t~{}=~{}0\), \(SNS\) will send \(\varnothing\) to \(B\). Upon the reception of the response from \(SNS\), \(B\) first checks the sequence number \(seq\) and then decrypts \(\{SecK_{B\&L}(str_{g})\}_{g=1,\ldots,t}\) to obtain \(\{SecS_{U}(x_{g},y_{g})\}_{g=1,\ldots,t}\). Finally, \(B\) replies the result \(res\) in form of \(\{ID_{g},SecS_{U}(x_{g},y_{g})\}_{g=1,\ldots,t}\) to user \(U\). After obtaining \(res\), \(U\) uses session key \(SecS_{U}\) to decrypt the corresponding coordinates of his/her friends. Querying strangers' locations. Users also can request a location query for searching strangers' locations. The process of querying strangers' locations is similar to that of friends. Figure 7 shows the specific process of querying strangers' locations and detailed steps are as follows:  
1. \(U\) needs to submit a query in the form of \((ID_{U},s,l)\) to \(B\), where \(s\) means this query is a request for querying strangers' locations and \(l\) indicates the specified query distance such as 2 km. After receiving \(U\)'s query, \(B\) figures out the associated grids based on \(U\)'s query distance \(l\), and forms a list \(GFID_{list}\). Then, \(B\) sends the message \((ID_{U},s,l,SecK_{B\&L}(BID,seq),GFID_{list})\) to \(SNS\). Based on \(GFID_{list}\) and \(U\)'s social network graph, \(SNS\) first eliminates the users who have friendship with \(U\). Then, \(SNS\) will randomly collect a certain number of users' \(PID_{list}\) to form a set \(\{PID_{ij}\}\), where \(1\leq i\leq k\), \(1\leq j\leq rand\), and \(rand\) is a number of randomly selected users. 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\). When receiving of the query from \(SNS\), \(LS\) runs the distance comparison function \(dis((x_{ind},y_{ind}),(x_{v},y_{v}))\leq min(l,ds_{v})\). \((x_{v},y_{v})\) indicates the corresponding coordinates of pseudo-IDs in \(\{PID_{ij}\}\), where \(1\leq p\leq(k\times rand)\). Suppose that there are \(w\)\(PID\)s satisfying the distance comparison function, then \(LS\) collects these \(w\)\(PID\)s to form a set \(\{PID_{s}\}\) and finds the corresponding \((x,y)\), where \(1\leq s\leq w\) and \(\{PID_{s}\}\subseteq\{PID_{ij}\}\). Finally, \(LS\) replies a message in the form of \((\{PID_{s},SecK_{B\&L}(x_{s},y_{s})\}_{s=1,\ldots,w},SecK_{B\&L}(seq))\) to \(SNS\). Upon receiving \((\{PID_{s},SecK_{B\&L}(x_{s},y_{s})\}_{s=1,\ldots,w},SecK_{B\&L}(seq))\), \(SNS\) recovers the real identifiers from \(\{PID_{s}\}\) to form a result set \(\{ID_{g}\}\) (i.e., the users' real identifiers) based on users' \(inds\).