# PPDC: A Privacy-Preserving Distinct Counting Scheme for Mobile Sensing
## 3 Privacy-Preserving Distinct Counting Computation
### Scheme Analysis  
We present analysis of PPDC in terms of correctness and security. **Theorem 1** (Correctness). : _The probability that the result of Equation (15) equals to that of Equation (16) is greater or equal to \(1-1/2^{q}\). The correctness of PPDC is greater or equal to \(1-(w/2^{q})^{d}\)._  
Proof. : According to the definition in Section 3.3, it is obvious that the sketch constructed by Equation (10) is the correct result of our problem. Equation (16) is one of Equation (10)'s mutually independent \(w\) parts to determine the \(j\)th-LSB bit. While in PPDC, Equation (15) represents the result. Actually, Equation (15) is equal to Equation (16) with a probability of \(1-1/2^{q}\) on the calculation. On the basis of a regular bitwise OR, only when all the numbers on that bit are 0, the result bit is 0, which is \(0\lor...\lor 0=0\). Otherwise, that bit should be 1. If our scheme is 100 percent accurate, when \(s_{j}=0\), it means \(G(j)\) should be 0\({}^{q}\) where all users' \(r_{i_{j}}\) should be 0. However there is a special case that a user \(y\) whose \(r_{y_{j}}\) is 1 while \(y\)'s encrypted bit string equals the bitwise XOR of all other users' encrypted strings. Since the encoding function in our scheme is random and the encoding string has \(2^{q}\) different choices, the probability for the result of our scheme being not accurate is \(1/2^{q}\). Therefore, we have:  
\[P(\text{the jth bit is accurate}) =P(\text{all users'}\text{ jth bits are }0)\times 1+P(\text{any user's jth bit is }0)\times(1-1/2^{q})\] \[\geqslant 1-1/2^{q}\]  
Because Equation (15) has to be independently calculated for \(w\) times to achieve the goal of Equation (10) and there are \(d\) FM sketches used, it is obvious that the correctness of PPDC is greater or equal to \(1-(w/2^{q})^{d}\). As in most cases, a malicious aggregator can only have the knowledge of ciphertext in privacy-preserving mobile sensing schemes. This belongs to the ciphertext-only attacks, which correspond to an attacker of minimal capability. However, we still analyze the security of PPDC under a more stronger model, known as the plaintext model, which assumes that the attackers may obtain a certain number of plaintext-ciphertext pairs through extra channels. The security of the proposed PPDC is summarized in the following theorem. **Theorem 2** (Security). : _For the homomorphic operations in PPDC, there is no probabilistic polynomial time (P.P.T.) adversary that can break the data confidentiality of user's data under the known plaintext model._  
Proof. : In PPDC, for the aggregator, we prove that there is no extra knowledge revealed to him in PPDC. We consider the situation that the aggregator could acquire most information. To calculate out the final result, all the \(w\) bits in \(S\) should be confirmed, which means that there must be \(w\) times communication between each user and the aggregator and each time the aggregator could get \(n\) cipertexts from all users. Let \(I=(I_{1},...,I_{w})\) denote the aggregator's information received from all users for \(w\) times, where \(I_{j}=(\overline{T(r_{1_{j}})},...,\overline{T(r_{n_{j}})})\)\((j=1,...,n)\) is the ciphertexts of \(q\)-bit bit strings from all users to decide the \(j\)th bit in \(S\). The aggregator calculates \(G(j)\) according to Equation (14) and then determines \(s(j)\) in \(S\) by Equation (15). If the result is \(s_{j}=1\), then \(G(j)\
eq 0^{q}\), which can help the aggregator speculate that in \(I_{j}\) there is at least one bit string \(\overline{T}\) from some user which is not \(0^{q}\). The aggregator wants to speculate \(T\) from \(\overline{T}\). Since the aggregator has no corresponding key, the probability that he guesses the correct plaintext is \(1/2^{q}\). Under known plaintext model, the aggregator could get \(a\) plaintext-ciphertext pairs to calculate \(a\) keys. Then, the probability of knowing a certain user's original data rises to \(1/A_{n}^{a}\).