## 3 Materials and Methods
### Privacy Preservation Analysis
For the sake of completeness, the main steps of these protocols, along with the privacy preservation properties they offer, are presented. The mobile user, U performs the following protocol in order to retrieve a set of pseudonyms with the identity provider (IP):  
Initially, user U chooses random values \(r_{(1,1)},r_{(1,2)},\ldots,r_{(1,m)},e\in Z_{q}\) where \(e\) is known only to user U, then computes the quantity \(t_{1}=g_{1}^{r_{(1,1)}}g_{2}^{r_{(1,2)}}\ldots g_{m}^{r_{(1,m)}}g_{m+1}^{e}\in Z _{q}\) and finally sends it to IP \((g_{1},g_{2},\ldots,g_{m+1}\in G_{q})\). Secondly, IP recovers the quantity \(t_{1}\), collects random quantities \(r_{(2,1)},r_{(2,2)},\ldots,r_{(2,m)}\) and computes the product \(t=t_{1}\cdot t_{2}\), where \(t_{2}=g_{1}^{r_{(2,1)}}g_{2}^{r_{(2,2)}}\ldots g_{m}^{r_{(2,m)}}\). Thirdly, user U creates the \(r_{i}\)'s according to the equation \(r_{i}=r(1,i)+r(2,i)\) for \(i=1,2,\ldots,m\) and computes the quantity \(t=g_{1}^{r_{1}}g_{2}^{r_{2}}\ldots g_{m}^{r_{m}}\). Hence, the corresponding user creates \(m\) pseudonyms \((P_{i},sign(P_{i}))\) and values \(s_{i}\in Z_{q}\), such that \(P_{i}=(tf_{0})^{s_{i}}\) for \(i=1,2,\ldots,m\). A mobile user U registers a pseudonym \((P_{i},sign(P_{i}))\) with a service provider \(SP_{i}\) presenting the pseudonyms \((P_{i},sign(P_{i}))\) and uncovering the value \(r_{i}\) encoded in \(P_{i}\). The user with the service provider \(SP_{i}\) performs the following proof of knowledge, provided that \(P_{i}\
eq 1\), so as the tuple \((P_{i},sign(P_{i}))\) will be a valid one. \[PK(\delta_{1},\delta_{2},\ldots,\delta_{i-1},\delta_{i+1},\ldots,\delta_{m}, \epsilon,\varsigma):(\delta_{1},\delta_{2},\ldots,\delta_{i-1},r,\delta_{i+1}, \ldots,\delta_{m},\epsilon,\varsigma)=rep_{(g_{1},\ldots,g_{m},g_{m+1},P_{i}) }f_{0}^{-1} \tag{3}\]  
Then, the service provider \(SP_{i}\) stores the tuple \((P_{i},r_{i})\) and associates it with either a new or an existing user account. Through this protocol, it is demonstrated that the user owns the pseudonyms and proves that the disclosed value \(r_{i}\) is actually the value encoded in \(P_{i}\). The privacy preservation lies in the following facts:  
1. The service provider cannot find out any additional information about the quantities encoded in \(P_{i}\), except for the disclosed value \(r_{i}\). 2. The random set \((r_{1},r_{2},\ldots,r_{m},e)\) is created so that nobody (user, identity provider) can control its end value. 3. The \(e\) is randomly selected from the user so that it can remain unknown to the IP. The user also computes a secret key \((r_{1}s_{i},r_{2}s_{i},\ldots,r_{m},e_{i})\), one for each pseudonym \((P_{i},sign(P_{i}))\); this proves that the user is aware of it without unveiling it. 4. The assumption of the Discrete Logarithm in a group \(G_{q}\) of prime order \(q\) along with the values \(r_{i}\in Z_{q}=\{1,2,\ldots,q\}\) (\(i=\{1,2,\ldots,m\}\)) ensures that any malicious user \(MU\), irrespective of the level of knowledge they possess about the Original and Transformed Database, even if they engage a pseudonym recovery protocol to the IP and obtain a valid pseudonym \((P,sign(P))\), has negligible probability that it is the value encoded in the public key \(P\). Suppose there is a mobile user who has initiated a discrete number of \(k\)-NN queries with different pseudonyms for each one. The unlinkability that the aforementioned protocols provide relates with the service provider's incapability to connect to the IP with the different pseudonyms to that mobile user and validate that they belong to the same user. Thus, the privacy preservation of that user identity is achieved.