Finding similarities between two datasets is an important task in many research areas, particularly those of data mining, information retrieval, cloud computing, and biometrics. However, maintaining data protection and privacy while enabling similarity measurements has become a priority for data owners in recent years. In this paper, we study the design of an efficient and secure protocol to facilitate the Hamming distance computation between two semi-honest parties (a client and a server). In our protocol design, both parties are constrained to ensure that no extra information will be revealed other than the computed result (privacy is protected) and further, the output of the protocol is according to the prescribed functionality (correctness is guaranteed). In order to achieve these requirements, we utilize a multiplicative homomorphic cryptosystem and include chaff data into the computation. Two experimental results in this paper demonstrate the performance of both the client and the server.