# Building Equi-Width Histograms on Homomorphically Encrypted Data
## 3 Evaluation Results
### Third Use Case (UC-3)  
UC-3 aims to increase the security of the overall process by computing the histogram and detecting outliers using the same circuit. However, this results in a higher complexity of the circuit and slower execution. In this scenario, the global complexity of the technique is evaluated.  
As in UC-1 and UC-2, the complexity of the model regarding the size of encrypted inputs increases with the size of data, while the size of the encrypted outputs is influenced only by the number of buckets in the equi-width histogram. However, as more operations are performed in the model that we define in UC-3, we notice a slight increase in the size of secret keys compared to the size of secret keys generated in UC-1 and UC-2. The total size of the inputs is expressed for UC-3 in a totally similar way to the size of inputs corresponding to UC-1 and UC-2 (see relations (9) and (10)). As in UC-2, performing experiments on a 50-bucket histogram using 2-full-days data samples is not feasible in UC-3.  
Since in UC-3, we compute the reference histogram and detect outliers using a single model, the size of inputs is considerably higher than in the case of circuits defined in UC-1 and UC-2. Therefore, the overhead introduced by encrypting the inputs is even higher than in UC-1 and UC-2, reaching an increase of almost \(\times 2\cdot 10^{6}\) in the size of inputs, as shown in Figure 11(a).  
Integrating both the histogram building and outlier detection phases into the same model, as defined in UC-3, increases the computational complexity of the circuit. This  
Figure 11: Variation of execution time, compile time, and key generation time for both histogram building and outlier detection phases of UC-2 with the size of the plain input data: (a) histogram building phase time variation, (b) outlier detection phase time variation.  
Figure 10: Variation of complexity in configuration UC-2 for different number of buckets and size of input data: (a) histogram building phase operation complexity, (b) outlier detection phase operation complexity.  
results in higher overall complexity due to the greater number of operations performed. The number of operations of each type performed by our prototype in UC-3 is roughly the sum of the operations from the circuits that separately handle histogram construction and outlier detection in UC-2. Consequently, the complexity of the circuit used in UC-3 provides a comprehensive view of the overall complexity of the proposed privacy-preserving outlier detection technique.  
Similar to UC-1 and UC-2, the effect of the number of samples to be labeled and the number of buckets in the reference histogram on the model's operation count is consistent. As shown in Figure 12b, doubling both the number of data samples and the number of buckets results in models with comparable operational complexity.  
We measured the time variation of the model in UC-3 relative to input size. Although the circuit in UC-3 is a combination of the two circuits from UC-2, the compile time, key generation time, and execution time of the UC-3 circuit do not simply add up to the sum of the corresponding times for the two individual circuits in UC-2. The execution and compile time for UC-3 follow the same pattern as the corresponding time components in UC-2. A local minimum can be identified for an input size of \((\#days,\#ofbuckets)=(2,10)\) for this prototype, as depicted in Figure 12c. However, taking into consideration the high complexity of the model in terms of both input size and number of operations, the training and execution (i.e., histogram construction and outlier detection) are slower than in UC-1 and UC-2.  
Figure 12: UC-3 configuration analysis: (**a**) correlation between the size of encrypted inputs and the size of clear inputs; (**b**) variation of complexity for different number of buckets and size of input data; (**c**) compile, execution, and key generation times variation with the size of the plain input data.