Performance Evaluation of Perfect Hashing-based OKVS(Oblivious Key-Value Store)

When using a standard hash table for searching and inserting data, collisions can occur.A collision happens when two different data entries are assigned the same hash value.This can slow down data processing, reduce memory efficiency, and create security risks, such as intentional collision-based attacks.To solve this issue, methods like chaining or open addressing are often used.However, these methods have a drawback: lookup time can increase from O(1) to O(n), making searches much slower as the dataset grows.In this study, we propose a collision-free perfect hashing function for a private set intersection (PSI) cryptographic protocol.We compare its performance with two widely used techniques: Bloom filters, known for their high memory efficiency, and cuckoo hashing, which improves Bloom filter collision handling.A collision-free perfect hashing function ensures fast O(1) lookups and high security for static datasets, where data does not change often.However, it is less suitable for dynamic datasets that require frequent updates, as the entire hash table would need to be rebuilt.We tested our method on static datasets of various sizes (100K, 1M, 10M, 30M, 50M entries) and measured memory usage, execution speed, and accuracy.Results showed that the Perfect Hashing-based OKVS(Oblivious Key-Value Store) PSI protocol was 25 times faster than the Bloom Filter-based protocol and achieved 100% accuracy.However, memory consumption increased significantly as the dataset size grew.In future work, we aim to develop and evaluate a collision-free perfect hashing function designed for dynamic datasets that require frequent updates.