# Building Equi-Width Histograms on Homomorphically Encrypted Data
## 2 Equi-Width Histograms on Homomorphically Encrypted Data
### Detecting Outliers in Encrypted Data Using Private Histograms  
As homomorphic encryption schemes impose significant limitations in terms of available operations, performing more complex data analysis on homomorphically encrypted data is a challenging task. In this section, we show how our private equi-width histogram can be utilized for detecting outliers in homomorphically encrypted IoT sensor data streams by analyzing the distribution of data across buckets. Since outliers typically appear less frequently than normal values, data points can be labeled based on the number of elements within the same bucket. Therefore, to bypass the limitations of existing homomorphic encryption schemes, a mainly additive and comparison-based simple thresholding approach can be applied, where data falling into buckets with low counts is classified as an outlier. Values that belong to low-frequency buckets are identified as outliers, whereas values in high-frequency buckets are considered normal. As in the case of constructing a private histogram, we adopt a vectorized approach for outlier detection on FHE-encrypted data, leveraging frequency-based labeling. Specifically, we define a procedure that, given an input value and a bucket, determines whether the value falls within the bucket and whether the bucket's element count is below a predefined threshold (as shown in Algorithm 3). By vectorizing this procedure, we enable repeated application across an entire IoT sensor dataset, while adhering to the constraints of fully homomorphic encryption. To accomplish this, we define a map operation that processes an IoT data sample alongside lists representing bucket ranges, element counts per bucket, and a predefined threshold. This operation outputs a list in which each element corresponds to the result of applying the \(isInAbnormalBucket\) function (defined below) to the respective elements of the input lists. The function determines whether a given data point falls within a bucket and if the bucket's element count is below the specified threshold, as follows:  
\[ \begin{split} isInAbnormalBucket:\mathbb{N}^{5}\rightarrow\{0,1 \},isInAbnormalBucket(x,low,high,count,th)=\\ =\begin{cases}1,&\text{if }x\in[low,high)\text{ and }count<th\\ 0,&\text{otherwise}\end{cases}\\ \end{split}  \tag{6}\]  
\[ \begin{split} r=vectorialIsInAbnormalBucket(x,low,high,count,th)=\\ =map(isInAbnormalBucket(x,low,high,count,th))\\ =[isInAbnormalBucket(x,low_{0},high_{0},count_{0},th),\cdots,isInAbnormalBucket (x,low_{n-1},high_{n-1},count_{n-1},th)]\end{split}  \tag{7}\]  
where \(x\) and \(th\) are scalars and \(low\), \(high\), and \(count\) are lists defining the buckets in the histogram. This approach is formally defined in Algorithm 3. Figure 2: Vectorial approach of constructing equi-width histograms. ```
1:\(x\)\(\triangleright\) New data sample
2:\(low[],high[]\)\(\triangleright\) Bucket bounds in histogram
3:\(count[]\)\(\triangleright\) Element counts per bucket
4:\(th\)\(\triangleright\) Threshold for outlier detection
5:\(r[]\)\(\triangleright\) Vector with 1 at the index of the abnormal bucket if any
6:\(r\leftarrow[]\)
7:for\(i=0\) to \(low.length-1\)do
8:\(r.\)append(isInAbnormalBucket(\(x,low[i],high[i],count[i],th))\)
9:endfor
10:return\(r\)
```  
**Algorithm 3** Vectorial is in abnormal bucket. To compute the binary label of a specific value, we perform a reduce operation on the result provided by the \(vectorialIsInAbnormalBucket\) procedure by summing all the elements in the list. Reducing a list by summing is a recursive vectorial operation which is defined as follows:  
\[reduce(L,\oplus)= \begin{cases}0,&\text{if }L=[\;]\\ x+reduce(L^{\prime},\oplus),&\text{if }L=[x]+L^{\prime}\end{cases}  \tag{8}\]  
where \(L\) is the original list, \(x\) is the first element of the list, and \(L^{\prime}\) is the rest of the list. This operation generates a single value that is the sum of all the elements of the list, by adding the first element to the sum of the rest of the list, until the list is empty (see Algorithm 4).