Paper 2014/499

Security and Efficiency Analysis of The Hamming Distance Computation Protocol Based On Oblivious Transfer

Mehmet Sabır Kiraz, Ziya Alper Genç, and Süleyman Kardaş


and Patey proposed two cryptographic protocols for the computation of Hamming distance in the two-party setting. Their first scheme uses Oblivious Transfer and provides security in the semi-honest model. The other scheme uses Committed Oblivious Transfer (COT) and is claimed to provide full security in the malicious case. The proposed protocols have direct implications to biometric authentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form. In this paper, we show that their protocol against malicious adversaries is not actually secure. Namely, we show a generic attack such that a malicious user can compute a Hamming distance which is different from the actual value. For biometric authentication systems, this attack allows a malicious adversary to pass the authentication without knowledge of the honest user's input with at most O(n) complexity instead of O(2^n), where n is the input length. We propose an enhanced version of their protocol where this attack is eliminated. The security of our modified protocol is proved using simulation-based paradigm. Also as for efficiency concerns, the modified protocol utilizes Verifiable Oblivious Transfer (VOT) which excludes the commitments to outputs (as they exist in COT). We show that the use of VOT does not reduce the security of the protocol but improves the efficiency significantly.

Note: Quality has been improved.

Available format(s)
Publication info
Preprint. MINOR revision.
Biometric IdentificationAuthenticationHamming distancePrivacyCommitted Oblivious Transfer
Contact author(s)
mehmet kiraz @ tubitak gov tr
2015-01-23: last of 4 revisions
2014-06-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mehmet Sabır Kiraz and Ziya Alper Genç and Süleyman Kardaş},
      title = {Security and Efficiency Analysis of The Hamming Distance Computation Protocol Based On Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2014/499},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.