## 3 Retrieving Private Data with Optimization Processes on Homomorphic Encryption Schemes
### The Combined Process of Cuckoo Hashing, Multi-Hashing, and Permutation-Based Hashing  
Theoretically, with hashing, the time complexity of data access can be reduced to \(O\left(1\right)\); however, the hash collision problem should first be tackled using hashing. When a hash collision occurs frequently, the time complexity of accessing the hash table will increase, and in the worst case, it may degrade the measure to \(O\left(n\right)\). This problem has been solved using Cuckoo hashing [25], a hashing algorithm that significantly reduces the probability of hash collision. The trick is to use \(h\left(h>1\right)\) hash functions to improve the usage rate of the Hash-Table (where \(h\) hash functions will make each data corresponding to \(h\) different hashing addresses), and the data access time of \(O\left(1\right)\) can be guaranteed. Therefore, with both the Client and Server doing cuckoo hashing, the bucket-wise comparison between the Client and the Server can produce the correct intersection. Among them, the Client's Hash Table has \(m\left(>1\,Y\,1\right)\) buckets, and each bucket has one slot, while the Server's Hash Table has \(m\left(>1\,Y\,1\right)\) buckets, and each bucket has \(s\) slots. First, let the Client and the Server agree on the value of \(h\) and which hash functions \(H_{1}\), \(H_{2}\),..., \(H_{h}\) to use, then both the Client and the Server insert their data into the Hash Tables by using the Cuckoo hashing. Then, when the Client sends \(y\) to the Server to confirm an intersection, we expect the Server also to check whether there is a \(y\) in the corresponding bucket through Cuckoo hashing within \(O\left(1\right)\) time complexity. However, the Server cannot know which Hash function was used to insert the elements in each bucket of the Client's Hash Table, so we need the Server to do multi-hashing. Multi-hashing means the Server must insert data into the buckets at the hashing addresses according to the outputs of all hash functions. In this way, no matter which hash function the Client uses to insert the data during Cuckoo hashing; the Server can always find the data in the bucket at the hashing address corresponding to one of the hash functions. After the Server completes multi-hashing, the data may be gathered in the earlier slots of each bucket if no processing is performed. In order to avoid data being located in specific slots and indirectly leaking the Hash Table information on the Server, all the slots in each bucket should be shuffled after all data was inserted into the Hash Table. The permutation-based hashing proposed by [26] is a hashing technique that reduces the data bit length that needs to be stored on the Hash Table by encoding a part of the data in the bucket's index. It can be used to cope with the problem that the bit number of the data is too high and reduce the memory required to store the data. Suppose the bucket size of the Hash Table is \(m\) (here we assume that \(m\) is a power of 2, interested readers can learn how to generalize to other sizes from [26]), and split the bit representation of the data \(x\) into \(x_{L}\) and \(x_{R}\), where \(\mid x_{R}\mid\) = log (\(m\)). Moreover, we denote the hashing address as Location (\(x\)) = \(f\left(x_{L}\right)\oplus x_{R}\), where the actual Hash Table data is represented by \(\mid x_{L}\mid\) bits and \(f\) is a random function whose range is in \(\left[0,\,m\right)\). Compared with the original approach, only \(\mid x_{L}\mid\) bits are needed to store the entire \(x\); that is, permutation-based hashing saves log (\(m\)) bits. Combined with the permutation-based hashing and the Cuckoo hashing, we can denote the data hashed with the \(i\)-th hash function and its new hashing address as \(<\)\(x_{L}\), \(i\)\(>\) and _Location\(i\)_ (\(x\)) = \(H_{i}\) (\(x_{L}\)) \(\oplus\)\(x_{R}\), respectively. This approach reduces the size of each data by (log (\(m\)) \(-\) [log (\(h\))]) bits, where [\(\cdot\)] denotes the ceiling function.