# BL0K: A New Stage of Privacy-Preserving Scope for Location-Based Services
## 3 Preliminaries
### Zero-Knowledge Plan within LBS  
A data-transfer protocol between LBS user and LBS server must obey the following properties:  
1. Proof of an assertion: Provided by the protocol regarding LBS information with probability p.
2. Probability: By increasing the queries, probability q can be increased exponentially close to 1.0.
3. Leakage: No information is leaked by any query, except with negligible probability.
4. Malicious LBS server: Using probability q, it is possible to detect a malicious LBS server.  
ZKPs are a cryptographic technique that enables a prover (P) to demonstrate to a verifier (V) that [PERSON] possesses k bits of information (k arbitrary), without exposing even a single bit of this information to V. As shown in Figure 2, the initial development of ZKP relies on an interactive challenge/response protocol that could be used to demonstrate the knowledge of a single bit of information [50; 51; 52]. The ZKP technique has since been extended to completely automated (non-interactive) protocols that can handle an arbitrary bit vector of length k that is known only to the prover P. ZKPs are probabilistic protocols. In a typical implementation of a single ZKP, iteration can be used to provide 50% certainty that [PERSON] knows 1 bit of information [53]. For N iterations over a k-bit vector, the probability provided by the proof of knowledge scales as \((1-2^{-N})^{k}\). Traditionally, the verifier V is referred to as [PERSON], and the prover [PERSON] is referred to as [PERSON]. In the LBS case, the verifier is the user (receiver), and the prover is the LBS provider (sender).  
Note that while the prover P must be honest in the first case, it is not necessary for the verifier V to be honest. [PERSON] can conduct a denial-of-service attack against the prover [PERSON] by providing inaccurate reports on the outcome of a particular ZKP iteration, but [PERSON] cannot determine any component of the k-bit vector K possessed by [PERSON] with better chances. For a second case, even if a malicious prover P offers a putative vector K', a single iteration of the ZKP algorithm can be used to demonstrate that K'<i> == K<i> with random probability at best (here <i> denotes the \(i\)th bit of the vector). Thus, the malicious prover is incapable of forging information possessed by the prover P and is also incapable of forging proof of knowledge of that information. After N iterations of the ZKP algorithm, the malicious prover has only a probability of 2-Nk of providing knowledge or proof of knowledge for a k-bit vector known as the prover P [54].  
The ZKP approach has immediate relevance to the LBS privacy problem. In the LBS scenario, the user plays the role of verifier V, while the LBS server plays the role of the prover P. The user does not only submit a query Q; instead, the user submits a query Q together with an assertion A. A benign LBS will provide either a proof or refutation that the tuple (Q, A) is consistent with some probability. The user may submit additional query-assertion pairs in order to improve the likelihood that the response is accurate to the degree that satisfies the user's expectations. A malicious LBS will only be able to provide a self-consistent proof or refutation with negligible probability. The only action that a malicious LBS can take is to provide a denial of service, e.g., by dropping queries or providing nonsense responses. The likelihood that the user can detect a malicious LBS increases by at least a factor of 2 for each (Q, A) tuple [55; 56; 57].