# PPDC: A Privacy-Preserving Distinct Counting Scheme for Mobile Sensing
## 3 Privacy-Preserving Distinct Counting Computation
### Main Idea  
From Section 2.3, it is obvious that while dealing with the distinct counting problem, FM sketch cannot provide the protection of users' privacy during the transmission and calculation process. Therefore, we provide a method that expands each bit of the string to make the sketch suitable for the encryption operation, where the string is the calculating result of each user's dataset. As mentioned above, there are \(n\) users in total. In the FM sketch, the bit field \(S=s_{1},s_{2},...,s_{w}\) of length \(w\) is initialized to zero at all positions. In the meanwhile, each user's sensing data is a dataset with various forms of elements, ranging in size from small to large. Assume that user \(i(i=1,...,n)\) has \(L_{i}\) elements in his sensing dataset. Let the set \(\{x_{l}^{(i)}\}\) denote the original sensing dataset of user \(i\), where \(l=1,...,L_{i}\). While putting user \(i\)'s sensing data \(\{x_{l}^{(i)}\}\) into the FM sketch, PPDC determines the bit field \(S\) bit by bit, from the Most Significant Bit (MSB) to the Least Significant Bit (LSB). The MSB refers to the last bit of \(S\), and the LSB is the first bit relatively. _Step 1_: This step is taken by users. For a user \(i(i=1,...,n)\), every element \(x_{l}^{(i)}(l=1,...,L_{i})\) in his original dataset \(\{x_{l}^{(i)}\}\) is hashed by a hash function \(h\) with a \(w\)-bit string output. Let \(\Lambda_{l}^{(i)}=(r_{l}^{(i)})_{1},...,(r_{l}^{(i)})_{w}\) denote this bit string output of length \(w\), where \((r_{l}^{(i)})_{j}\) is the \(j\)th bit in the string and the probability is \(P((r_{l}^{(i)})_{j}=1)=2^{-j}\). That is to say, \(\Lambda_{l}^{(i)}=h(x_{l}^{(i)})\). Then a bitwise OR operation is taken to get  
\[\Lambda_{i}=\Lambda_{1}^{(i)}\vee...\vee\Lambda_{L_{i}}^{(i)} \tag{9}\]  
The string \(\Lambda_{i}=r_{i_{1}},...,r_{iw}\) represents all elements in user \(i\)'s original dataset. According to the knowledge mentioned in Section 3.3, Equation (10) should be correct. \[S=\Lambda_{1}\vee...\vee\Lambda_{n} \tag{10}\]However, \(S\) should not be calculated out straightforward. Because according to Equation (9), if the aggregator could receive \(\Lambda_{i}\) directly, \(\Lambda_{i}\) would reveal the original data of user \(i\), especially when the size of his dataset is small. Therefore, a series of operations should be carried on the \(\Lambda_{i}\). **Step 2**: This step is also done on the user's side. The user \(i\) operates on each bit of the string \(\Lambda_{i}\) in order to avoid any damage caused on the privacy. In PPDC, we design a kind of specific coding scheme for these bits. Let \(T(r_{i_{j}})\) denote the corresponding code of \(r_{i_{j}}\) in the coding scheme, where \(j=1,...,w\). The coding scheme is defined as follows:  
\[T(r_{i_{j}})\left\{ \begin{array}{ll}=0^{q},&if\ r_{i_{j}}=0\\ \stackrel{{\approx}}{{=}}\{0,1\}^{q}\setminus 0^{q},&if\ r_{i_{j}}=1 \end{array} \right. \tag{11}\]  
where \(q\in N\) is the accuracy controlling parameter and \(\stackrel{{\approx}}{{=}}\) denotes to sample uniformly at random. Figure 2 shows an example of the process user 1 deals with his original dataset. **Step 3**: The aggregator takes this step after aggravation all users' coded data. Let \(G(j)=T(r_{1_{j}})\oplus...\oplus T(r_{n_{j}})\) with bitwise XOR operation. Then there is a judgement rule designed to determine each bit of FM sketch \(S\), corresponding to the coding scheme (11). We define the rule as follows:  
\[s_{j}=\left\{ \begin{array}{ll}0,&if\ G(j)=0^{q}\\ 1,&if\ G(j)\
eq 0^{q}\end{array} \right. \tag{12}\]  
where \(s_{j}\) is the \(j\)th-LSB, or \((w-j)\)th-MSB in the bit field \(S\). Notice here that when PPDC judging each bit in FM sketch, it starts from the MSB to the LSB. **Step 4**: The calculation work is done by the aggregator. Based on the FM sketch \(S\), the aggregator can get a significant parameter \(Z(S)\), the position of the last bit in \(S\) that is 1, according to Equation (5).