# BL0K: A New Stage of Privacy-Preserving Scope for Location-Based Services
## 3 Preliminaries
### ZKP Standard
During the initialization phase, V is provided with s and P is provided with c (presumably from its database). 1. [PERSON] STEP: [PERSON] generates primes p and q, such that p \(\equiv\) 3 mod 4 and q \(\equiv\) 3 mod 4. She computes n = pq and sends n to [PERSON]. The values p and q are the \"auxiliary secret\" referred to above. 2. [PERSON] STEP: [PERSON] chooses a random integer x and computes w = (xs)\({}^{4}\) mod n. He then sends w to [PERSON]. Note that because of the intractability assumption, it is not possible to recover a single bit of (xs)\({}^{2}\) or (xs) from w. Good practice suggests that [PERSON] uses a new value of x for each ZKP interaction (LBX transaction). 3. PEGGY STEP: [PERSON] can now compute the principal square root y\({}_{1}\) of w mod p and the principal square root y\({}_{2}\) of w mod q. Using [PERSON]'s Little Theorem [61], these values are:\[y_{1}=w^{(p+1)/2}\] (5) \[y_{2}=w^{(q+1)/2}\] (6) [PERSON] then uses the Chinese Remainder Theorem [62] to construct a value \(y\) such that \(y\equiv y_{1}\mod p\) and \(y\equiv y_{2}\mod q\). It follows that \((xs)^{2}\equiv y\mod n\). [PERSON] now needs to find m--the multiplicative inverse of \(s^{2}\mod n\). [PERSON]'s algorithm tells us that m exists and is computable in linear time if and only if \(gcd(s^{2},n)=1\). This will be true, except with negligible probability. [PERSON] then computes m and observes that m\((xs)^{2}\equiv x^{2}\equiv my\mod n\). [PERSON] sends \(my\) to [PERSON]. 4. VICTOR STEP: [PERSON] computes \(x^{2}\mod n\) and observes that this is equal to the value just received from [PERSON], namely \(my\). First, consider that this is a probabilistic algorithm. The likelihood of success is \(1-2^{-b}\) where \(b=\log 2(n)\). This may increase arbitrarily using larger values of \(p\) and \(q\). Secondly, in Step 3, [PERSON] did not need \(s^{2}\); she only needed \(m\), the multiplicative inverse of \(s^{2}\mod n\). By the first assumption, it is computationally intractable to recover any part of \(s\) from m. (his is why a fourth power was used rather than a second power. The value m can be safely be stored in a database referring to the quantity \(c\), or some abstract token that refers to \(c\). If the encryption was performed on a device, then it could be arranged that the encryption mechanism returns m and a token that points to \(c\). Finally, we must discuss the issue of Fermat Liars and \"approximately prime\" values. [PERSON]'s Little Theorem states that if \(p\) is prime, then \(a^{p-1}\equiv 1\mod p\) for all such that \(1\leq a<p\). If n is composite, then \(a^{n-1}\equiv 1\mod n\), where n is referred to as a Fermat Liar or an approximately prime integer. For example, \(n=221\) is a Fermat Liar for \(a=38\). This is why the auxiliary secrets \(p\) and \(q\) must be prime, and not approximately prime. Any primary algorithm that runs on \(p\) and \(q\) must ensure that they are truly prime. Since \(p\) and \(q\) are computed offline, this does not affect the runtime performance of the system. Note that the ZKP standard describes an abstract transfer protocol for learning information about a quantity (an LBS data item) without actually transferring the information itself. Like the OT protocol, cryptographic primitives are combined to yield a transfer protocol that is immune to information leakage, except with negligible probability. The system architecture is outlined in Table 1.  
The notations are outlined in Table 2. \begin{table}
\begin{tabular}{c c} \hline
**Symbol** & **Description** \\ \hline Verifier & Mobile device user \\ Prover & Location-based servers \\ SNS & The social network server \\ CT & Wi-Fi tower \\ BF & Bloom filter \\ ZKP & Zero Knowledge Proof \\ \hline \end{tabular}
\end{table} 
Table 1: System architecture.