# Building Equi-Width Histograms on Homomorphically Encrypted Data
## 2 Equi-Width Histograms on Homomorphically Encrypted Data  
Different types of histograms, such as equi-depth, equi-width, and dynamic-width, offer varying levels of effectiveness depending on the characteristics of the underlying data distribution [35]. Equi-depth histograms are more effective for skewed data, whereas equi-width histograms perform better on uniformly distributed data. However, the adaptability of equi-depth histograms comes with increased complexity in both construction and maintenance. In this work, we chose to implement equi-width histograms because of their lower computational cost.  
Equi-width histograms capture the overall data distribution by grouping data points into fixed-width buckets. In such histograms, buckets have the same size (range), but the number of values that fit in each of them is variable. Each bucket can be represented as a tuple:  
\[b=(low,high,count),low,high,count\in\mathbb{N}, \tag{1}\]  
where \(low\) and \(high\) give the range of values which fit in the bucket and count is the number of data points within the \([low,high)\) range.  
Next, we present the implementation of equi-width histogram computation on encrypted data and illustrate its effectiveness in detecting outliers in IoT data. The overview of our approach is depicted in Figure 1. The proposed framework simulates a real-world setting where outlier detection is performed on encrypted IoT data using prior measurement distribution. To this end, we first preprocess the raw IoT data by scaling and converting it to integer values within the range \([0,100]\), as many homomorphic encryption frameworks do not support floating point operations. Next, we homomorphically encrypt the data and construct an encrypted equi-width histogram, which is then used for outlier detection across three different configuration scenarios described in the evaluation section.  
Figure 1: Pipeline of the proposed framework for privacy-preserving outlier detection in IoT data using private equi-width histograms.  
For the implementation, we chose the TFHE scheme in Concrete [33; 34] due to its superior flexibility in converting various operations into table lookups, outperforming other FHE schemes [36; 37; 38; 39]. A key advantage is its support for function composition [40], enabling secure multi-step computations without decryption. Additionally, Concrete allows limited floating point operations [41], but its Compile tool only supports integer inputs and outputs, as computations rely on table lookups' mapping integers to integer results.  
In Concrete, data is encrypted using Learning With Errors (LWE), which implies a series of constraints not only on the allowed operations and on the way that functions are implemented, but also on the size of the plain values. Moreover, this learning-based approach of translating arithmetic operations into table lookup operations is a probabilistic model which is prone to errors. The main drawback of Concrete is that it may not provide the expected answer in all test cases, but its default failure probability is very low (1 in 100,000).  
As a fully homomorphic encryption scheme, TFHE implemented in Concrete overcomes the drawback of the traditional encryption schemes in which the data is temporarily encrypted during transmission between the client and the server. The server decrypts it upon receipt, executes the necessary operations on the plaintext, re-encrypts the result, and returns it to the client. In Concrete, the only private key holder is the client, and the server-side operations are entirely performed on encrypted data, using the public evaluation key, which is mathematically related to the client's private key.