On private Hamming distance computation

Kok Seng Wong, Myung Ho Kim

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)1123-1138
Number of pages16
JournalJournal of Supercomputing
Issue number3
Publication statusPublished - Jan 1 2013
Externally publishedYes


  • Privacy preserving computation protocol
  • Private Hamming distance
  • Secure two-party computation
  • Similarity measurement

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'On private Hamming distance computation'. Together they form a unique fingerprint.

Cite this