# BL0K: A New Stage of Privacy-Preserving Scope for Location-Based Services
## 3 Preliminaries
### ZKP Standard  
Consider the case where there are two parties, V and P. V possesses some plaintext and P has access to an encrypted version of this plaintext. P wishes to prove that it can decrypt its encrypted version using a zero-knowledge approach. Specifically, it wishes to prove that it can decrypt the encrypted version without leaking any secret information between V and P, in either direction. ZKP must have three characteristics: completeness, soundness, and zero knowledge. These are formally defined as follows [38; 59]:  
For completeness, if the notification is genuine, the honest user (verifier) will be persuaded by the honest LBS (prover) using the following equation:  
Figure 5: BL0K architecture in LBS. \[Y_{Z}^{2}\prod_{e_{j}=1}V_{j}\ (mod\ n)=\left(r\prod_{e_{j}=1}S_{j}\ \right)^{2} \times V_{j}\ (mod\ n) \tag{1}\]  
\[=r\prod_{e_{j}=1}(S_{j}^{2}\ \times V_{j}\ )\ (mod\ n) \tag{2}\]  
\[=r^{2}\ mod\ n \tag{3}\]  
\[=X_{z} \tag{4}\]  
Soundness: If the notification is false, the dishonest prover cannot convince the honest verifier that it is true, except with negligible probability. For Zero-Knowledge ZKP, if the notification is true, no cheating verifier learns anything other than the statement is true. In this case, [PERSON] is making the statement \"I can decrypt, or I have access to a device or third party that can decrypt.\" We add a fourth requirement to the system: that it must be independent of the type of encryption/decryption being used. In particular, it must work for both symmetric and asymmetric crypto, without any change in the ZKP. In this paper, we refer to the plaintext held by [PERSON] as s. We use s to emphasize the fact that the plaintext must be protected. Not even one single bit of s can be transmitted to [PERSON]. The corresponding encrypted text that [PERSON] possesses or has access to we refer to as c. Her key material we refer to as K. Part of K may be publically known (e.g., the public part of an asymmetric key), but in general we assume that K must be protected so that not even a single bit of K can be transmitted to [PERSON]. We make one assumption regarding the cryptographic intractability of certain operations. The assumption is that the \"sqrt mod n\" problem is cryptographically intractable. Let p and q be primes such that p \(\equiv\) 3 mod 4 and q \(\equiv\) 3 mod 4. In this case, it is not acceptable for either p or q to be approximately prime (this term is defined below). We compute n = pq. The problem of the \"sqrt mod n\" determines, for a given y and n, whether there is an x such that x\({}^{2}\equiv\) y mod n. The problem is constructive: if x exists, then the algorithm must produce it. There is no known polynomial time algorithm that can solve this problem. In this formulation, the key material is p and q and the plaintext is x. It can be proven that the intractability of this problem is equivalent to the intractability of factorization. Given plaintext s, we require an invertible function g such that g(s) is a unique integer at least 256 bits in length. Function g must be polynomial time computable, the inverse g\({}^{-1}\) must also be polynomial time computable, and it must comply with the following: g\({}^{-1}\)(g(x)) = x and g(g\({}^{-1}\)(y)) = y for all plaintexts x and for all encoded integers y. This requirement is easy to meet. Length-encoded values with padding, as defined by RFC1321 for example, can be used. It is not intended that g or its inverse contain any key material. It is an advantage for both V and P that the complete algorithms for g and g\({}^{-1}\) are made publicly available. Standard encoding methods consider time as linear. For the rest of this document, we refer to s and g(s) interchangeably. There are many different forms of the ZKP algorithm, ranging from the very simple Ali Baba protocol [50] as well as many more complicated algorithms with specific properties. We use a version of the Gaillou-Quisquater (GQ) zero knowledge algorithm [60] with an auxiliary secret.