# Supporting Privacy of Computations in Mobile Big Data Systems +
## 6 Privacy Preserving Search for the Nearest Bank/ATM
### Circuit for Computing Manhattan Distance  
Let \((x_{a},y_{a})\) represent the coordinates of the mobile client at an intersection. Similarly, let \((x_{b},y_{b})\) represent the coordinates of a bank/ATM. Since the streets are arranged in a grid pattern, the shortest distance (\(D\)) between \((x_{a},y_{a})\) and \((x_{b},y_{b})\) equals the sum of the absolute differences between the respective coordinates: \(D=|x_{a}-x_{b}|+|y_{a}-y_{b}|\). This distance metric is more commonly referred to as the Manhattan distance.  
We design a Boolean circuit for computing the Manhattan distance between two points, \((x_{a},y_{a})\) and \((x_{b},y_{b})\). Assume that each coordinate is an \(l\) bit unsigned number. Figures 10 and 11 show the block diagram of our circuit. We use the _SUB_ and _ADD_ blocks of [PERSON] _et al._[21].  
Each \(SUB/ADD\) block is composed of \(l\) 1-bit subtractors/adders; each 1-bit subtractor/adder, in turn, is composed of 4 _XOR_ gates, 1 _AND_ gate. Note that \((l+1)^{th}\) output bit of \(SUB\) block equals the complement of carry-out bit from the \(l^{th}\) 1-bit subtractor.  
If \(x_{a}\geq x_{b}\), then the output of \(SUB\) block equals the absolute difference, \(|x_{a}-x_{b}|\). Otherwise, the output of \(SUB\) block equals the negative value, \(-|x_{a}-x_{b}|\), in \(2^{\prime}s\) complement form. Since \(x_{l+1}=1\) for negative values, we use \(x_{l+1}\) as one of the inputs for the _XOR_ gates in the \(INV\) block to compute the \(1^{\prime}s\) complement of the absolute difference. Then, we subsequently use \(x_{l+1}\) as a carry-in input bit for the \(ADD\) block. Thus, the output of the \(ADD\) block accounts for both \(x_{a}\geq x_{b}\) and \(x_{a}<x_{b}\) cases.  
Similarly, for the \(Y\) coordinates we use the \(SUB\) and \(INV\) blocks to compute the absolute difference in \(1^{\prime}s\) complement form. To account for the case when \(y_{l+1}=1\), we use an \(INC\) block that adds the value of the bit \(y_{l+1}\) to the output of the \(ADD\) block. The \(INC\) block is composed of \(l\) half-adder (\(HA\)) blocks, where each \(HA\) block, in turn, is composed of 1 _XOR_ and 1 _AND_ gate.  
Figure 11: Manhattan Distance Computation.  
Figure 10: Absolute difference between the \(X\) and \(Y\) coordinates.  
The output of the \(INC\) block represents the \((l+1)\)-bit Manhattan distance between \((x_{a},y_{a})\) and \((x_{b},y_{b})\). Using the circuit design of Figures 10 and 11, a list of distances between the location of the mobile client and any number (\(L\)) of ATM locations can be computed. Table 3 shows that our Boolean circuit for computing the Manhattan distance between two points has a total of \((15l+1)\)\(XOR\) gates and \(4l\)\(AND\) gates.  
Note: In a more direct alternative to compute Manhattan distance, we may first find \(min(x_{a},x_{b})\) and \(max(x_{a},x_{b})\), and always subtract \(min(x_{a},x_{b})\) from \(max(x_{a},x_{b})\) (similarly for the \(Y\) coordinates). While this approach would eliminate \(INV\) and \(INC\) blocks, it however would require the use of two comparator and conditional swap blocks [22], which together introduce \(12l\) new \(XOR\) gates and \(4l\)\(AND\) gates. Consequently, this alternative approach to compute Manhattan distance would require a total of \(24l\)\(XOR\) gates and \(7l\)\(AND\) gates. Thus, in comparison to this more direct alternative, our design shown above in Figure 10 and Figure 11 requires a significantly smaller number of \((15l+1)\)\(XOR\) and \(4l\)\(AND\) gates.