# PPDC: A Privacy-Preserving Distinct Counting Scheme for Mobile Sensing
## 3 Privacy-Preserving Distinct Counting Computation
### Privacy-Preserving Distinct Counting Scheme  
In Section 3.2, we calculated the number of distinct counting through PPDC. The specific operation towards users' data is prepared for the homomorphic encryption to protect users' privacy. In this subsection, we highlight the modules of encryption and decryption(i.e., calculation based on ciphertexts) in PPDC that allow the aggregator to solve the distinct counting problem and to avoid acquiring each user's data privacy at the same time. In our assumption, there is a trusted authority as a third party who helps users and the aggregator to establish a key system each time. 1. _Setup._ The protection mechanism of PPDC is based on the bitwise XOR homomorphic encryption introduced in Section 2.2. The trusted authority has \(m_{1},...,m_{n}\in\{0,1\}^{\gamma}\) privately and he computes \(M_{a}^{i}=m_{i}\) and \(M_{b}^{i}=m_{(i\ mod\ n)+1}\) for each user \(i(i=1,...,n)\). Then the two seeds are sent to the corresponding user. The user \(i\) does a bitwise XOR operation on the seeds as well as a nonce number \(t\) according to Equation (1) to acquire his own key \(k_{i}\). Notice that the nonce number \(t\) used for calculating \(k\) is different in each transmission. 2. _Encrypt._ The data encryption is operated on the user's side. The user \(i\) regards the coding string \(T(r_{i_{j}})\) for \(j\)th bit of his data representation \(\Lambda_{i}\) as the plaintext and encryptes it with the bitwise XOR homomorphic encryption algorithm to get the ciphertext \[\overline{T(r_{i_{j}})}=T(r_{i_{j}})\oplus k_{i},(j=1,...,w)\] (13) where the user \(i\)'s key \(k_{i}\) is generated as introduced above. Then the ciphertext \(\overline{T(r_{i_{j}})}\) is sent to the aggregator as user \(i\)'s sensing data. 3. _Aggregate._ On the side of the aggregator, he collects all the \(n\) users' data about the \(j\)th-LSB and then does the bitwise XOR computations. Denote by \(\overline{G(j)}\) the bit string result. According to Equation (4), it can be drawn that \[\overline{G(j)}=\overline{T(r_{1_{j}})}\oplus...\oplus\overline{T(r_{n_{j}})}\] (14) It is easy to see that if the \(j\)th-LSBs of the \(n\) users are all 0, then the bitwise XOR of the corresponding strings \(\overline{G(j)}\) is always a \(q\)-bit string of 0s. If there is any user whose data \(\Lambda\) is 1 on the \(j\)th-bit, the bitwise XOR of all reports' corresponding strings is not a \(q\)-bit string of 0s with a probability of \(1-1/2^{q}\). However this situation has little influence on the accuracy of PPDC which will be proved in Section 3.4. 4. _Judge._ Just like the rule mentioned above, we define the rule as follows: \[s_{j}=\left\{ \begin{array}{ll}0,&if\ \overline{G(j)}=0^{q}\\ 1,&if\ \overline{G(j)}\
eq 0^{q}\end{array} \right.\] (15) where \(s_{j}\) is the \(j\)th-LSB in the bit field \(S\). In Figure 3, a detailed example of aggregation in the FM sketch using above described transformation and corresponding bitwise XOR computations is shown. And the formal description of our entire scheme is shown in Algorithm 1. **Remark 3**. : _The operation of homomorphic encryption causes no damage on the accuracy of PPDC. According to the property of the bitwise XOR homomorphic encryption, there is \(\overline{G(j)}=\overline{T(r_{1_{j}})}\oplus...\oplus\overline{T(r_{n_{j}}) }=T(r_{1_{j}})\oplus...\oplus T(r_{n_{j}})=G(j)\). Thus, we can say that Equation (15) is equal to Equation (12), which means that the calculated aggregation result is not influenced by the encryption and decryption operations for user's privacy protection. Then the final result of distinct counting problem is calculated by Step 4 in Section 3.2._  
**Remark 4**. : _The correctness and security of PPDC are credible. According to Equation (10), we have_  
\[s_{j}=r_{i_{1}}\vee...\lor r_{i_{w}} \tag{16}\]  
In PPDC, Equation (15) is equal to Equation (16) with a probability of \(1-1/2^{q}\), which means that the operations in PPDC have nearly no effect on the final result when the parameter \(q\) is appropriate. We will prove it in Theorem 1.