# Building Equi-Width Histograms on Homomorphically Encrypted Data
## 2 Equi-Width Histograms on Homomorphically Encrypted Data
### Private Histogram Construction  
First, we define a function to determine whether a given value falls within a bucket defined by a specific range. While this may seem like a straightforward operation, implementing it directly on homomorphically encrypted data presents significant challenges. Homomorphic encryption imposes strict limits on the number of operations that can be performed on the same ciphertext, and conventional loops using a counter variable are not feasible, especially when the number of iterations is large. This restriction exists because each iteration increases the computational depth on the ciphertext, potentially exceeding the allowed limit. As only foreach loops and vectorial operations are allowed without any restrictions, alternative procedures need to be implemented to ensure compliance with the constraints imposed by the encryption scheme. Therefore, we implement the range-checking procedure in a vectorized manner, allowing us to efficiently determine whether a given data point x falls within a set of buckets, represented as lists of low values, \(low[]\), and of high values, \(high[]\). Given an input value x and two lists containing, on the same position, the minimum (\(low\)) and, respectively, the maximum (\(high\)) value of each bucket, applying the previously defined procedure in a vectorial approach involves iteratively checking whether \(x\) falls within the range defined by the corresponding low and high values. The result of each comparison is appended to a new list \(r[]\), maintaining the same index as the original range lists. Therefore, the vectorized implementation returns a list of the same size as the \(low[]\) and \(high[]\) lists containing a single value of 1 at the position corresponding to the bucket where \(x\) fits, while all the other elements of the result list are equal to 0. This vectorial approach to determine the bucket in which each value of the input fits can be formally described as a map operation, which takes a data sample and the lists containing the ranges of buckets as inputs and returns another vector as output, where each element of the output vector is the result of applying the \(isInBucket\) function to the corresponding elements of the input vectors, as follows:\[isInBucket:\mathbb{N}^{3}\rightarrow\{0,1\},isInBucket(x,low,high)= \begin{cases}1,& \text{if }x\in[low,high)\\ 0,&\text{otherwise}\end{cases}  \tag{2}\]  
\[r=vectorialIsInBucket(x,low,high)=map(isInBucket(x,low,high))\\ =[isInBucket(x,low_{0},high_{0}),\cdots,isInBucket(x,low_{n-1},high_{n-1})] \tag{3}\]  
where \(x\) is a scalar and \(low\) and \(high\) are lists. Algorithm 1 shows the vectorial implementation of the procedure. ```
0:\(x\)\(\triangleright\) New sampled data from IoT devices
0:\(low[]\), \(high[]\)\(\triangleright\) Lists of bucket bounds in histogram
0:\(r[]\)\(\triangleright\) List with 1 at the position of the matching bucket
1:\(r\leftarrow[]\)
2:for\(i=0\) to \(low.length-1\)do
3:\(r.\)append(isInBucket(\(x,low[i],high[i]))\)
4:endfor
5:return\(r\)
```  
**Algorithm 1** Vectorial is in bucket. Using the vectorial approach to determine the bucket in which the given value fits, we can compute the histogram of an input dataset by adding the result vectors for each value in the input set, as shown in Algorithm 2. To achieve this, we use the vectorial addition operation which is defined as the element-wise addition of their corresponding components. ```
0:\(x[]\)\(\triangleright\) New sampled data stream from IoT devices
0:\(low[]\), \(high[]\)\(\triangleright\) Lists of bucket bounds in histogram
0:\(h[]\)\(\triangleright\) Equi-width histogram
1:\(h\leftarrow[0,0,\ldots,0]\)
2:for all\(x_{i}\in x\)do
3:\(h\gets h+\text{vectorialIsInBucket}(x_{i},low,high)\)
4:endfor
5:return\(h\)
```  
**Algorithm 2** Building equi-width histogram on homomorphically encrypted data.