Efficient Range Search for Hamming Distance Using Function Secret Sharing

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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex> to achieve optimal search rates, and demonstrated the effectiveness and efficiency of the protocol. Compared to existing work, our scheme reduces communication overhead.