Efficient Range Search for Hamming Distance Using Function Secret Sharing
Yuyi Li · 2024
In high-dimensional binary spaces, range search based on Hamming distance remains a crucial tool for ad-vancing research and applications across various fields due to its balance of simplicity, speed, and scalability. This paper presents a range search scheme for Hamming distance based on Function Secret Sharing (FSS), a novel cryptographic primitive that enables secure computation with low communication and computational costs. Additionally, we design a secure Hamming distance computation protocol that eliminates the need for third-party negotiation, allowing the query key to be generated by the querying party, which is more suitable for real-world applications and helps reduce communication overhead and computational costs. Finally, we provide a formal security proof of the proposed protocol and evaluate its performance through experiments, exploring the impact of different parameters. We conducted experiments on three real datasets, adjusting$d$and$r$to achieve optimal search rates, and demonstrated the effectiveness and efficiency of the protocol. Compared to existing work, our scheme reduces communication overhead.