# A Search Efficient Privacy-Preserving Location-Sharing Scheme in Mobile Online Social Networks
## 5 Search Efficient Privacy-Preserving Location-Sharing (SELS) Scheme  
To preserve users' privacy and improve the efficiency of location-sharing systems, the proposed scheme utilizes the grid structure and anonymous technologies. The details of each step are given below. Initialization. \(SNS\) assigns a unique identifier \(ID\) to each user and builds social network graphs \(G=(V,E)\) for users. Then, \(SNS\) creates a mapping relationship set \(\{ID,PID_{list}=(PID_{1},PID_{2},\dots,PID_{k}),ind\}\) for each user. \(PID_{list}\) is a pseudo-ID set generated by the pseudo-random function [24]. \(ind\) is an index to indicate the real pseudo-ID in \(PID_{list}\), where \(1\leq ind\leq k\) and \(k\) is the number of pseudo-IDs. Finally, \(SNS\) shares the mapping relationship with \(B\). In addition, \(B\) builds a grid structure for the entire query area of the location-sharing system and creates a mapping relationship between \(GID=\{GID_{1},GID_{2},\dots,GID_{n}\}\) and \(GFID=\{GFID_{1},GFID_{2},\dots,GFID_{n}\}\), where \(GID\) is the identifier set of grid cells and \(GFID\) is the fake-IDset generated by the cryptographic hash function SHA-1. Note that one grid cell identifier in \(GID\) corresponds to one fake-ID in \(GFID\). Afterwards, \(B\) shares the mapping relationship with \(SNS\). Registration. Firstly, user \(U\) sends a registration request in the form of \((ID,df,ds,ts,Sig(ID,ts))\) to \(SNS\), where \(ts\) is a time-stamp used to prevent replay attacks, \(df\) and \(ds\) represent \(U\)'s distance threshold in friends' and strangers' location query respectively, and \(Sig(ID,ts)\) is a signature generated with \(U\)'s private key over the time-stamp \(ts\). After receiving the registration request of \(U\), \(SNS\) uses \(U\)'s public key to verify the correctness of the signature. If the decrypted \(ID\) is the same as \(U\)'s identifier assigned by \(SNS\) in advance, \(SNS\) will send a message \(OK\) to \(U\). Secondly, \(SNS\) will send a notification in the form of \((ID,df,ds,reg)\) to \(B\), where \(reg\) is a notice which means this \(ID\) is a registered one. After receiving the notification, \(B\) replies a message \({}^{\prime}OK^{\prime}\) to \(SNS\) and stores the corresponding information in the database. Figure 3 shows the message transmission about the registration. Update. The update process includes mapping relationship update and location update. Figure 4 shows the process of mapping relationship update. The detailed steps are as follows:  
1. \(B\) generates a new mapping relationship \(\{GFID=GFID_{1},GFID_{2},\ldots,GFID_{n}\}\) between grid cells' identifiers and their fake-IDs. Then, the new fake-ID set (i.e., \(\{GFID=GFID_{1},GFID_{2},\ldots,GFID_{n}\}\)) is encrypted with the secret key \(SecK_{B4S}\) and sent to \(SNS\). 2. \(SNS\) uses the random number generator [25] to generate a new \(ind\). Then, the new \(ind\) and identifier \(ID\) of each user are encrypted with the secret key \(SecK_{B4S}\) and sent to \(B\). 3. To prevent the users who are no longer friends from getting messages, \(SNS\) updates the session key \(SecS_{U}\) for each user based on social network graphs. Figure 5 shows the process of location update. The detailed steps are as follows:  
1. When user \(U\) updates his/her location, \(U\) needs to submit a message in the form of \((ID_{U},(x,y),Sess_{U}(x,y),A/F)\) to \(B\). \((x,y)\) is the \(U\)'s current location and \(Sess_{U}(x,y)\) is the encrypted location information with \(Sess_{U}\). \(A/F\) is the grid cell access control policy, which means the current grid cell is accessible/inaccessible (i.e., \(U\) allows or forbids the current grid cell where \(U\) locates can be searched by the location-sharing requests of his/her friends). When getting the message, \(B\) will record the access control policy in the form of \((ID_{U},GID,A/F)\) in the database.