Enabling Privacy-Preserving Top-k Hamming Distance Query on the Cloud

The top-k Hamming distance query is to find the k optimal objects with the smallest Hamming distance to the query data. It has a wide range of applications in many domains such as social networks, image retrieval and biological recognition. The existing privacy-preserving protocols do not support the top-k Hamming distance query in practice. To address this issue, we consider letting the user securely query the top-k Hamming distance on the cloud in a secure outsourcing manner. We propose two protocols to realize the privacy-preserving top-k Hamming distance query on the cloud. In the first protocol, two cloud servers are introduced to cooperatively complete the privacy-preserving top-k Hamming distance query. To preserve data privacy, the Paillier encryption and randomization techniques are leveraged to blind the user data, and the ciphertext data is stored on the first cloud server. The second cloud server calculates the Hamming distance on the ciphertexts. After that, the encrypted query results are returned to the query user for recovering the top-k query results. In the second protocol, we adopt the data aggregation strategy to further enhance the efficiency. By packaging data, the computation overhead of each participant is reduced and the communication overhead of the protocol is decreased, remarkably. Security analysis demonstrates that the data privacy is guaranteed in the proposed protocols. Experimental results evaluate the performance of the proposed protocols and confirm the superiority of the second protocol.