Paper 2014/499

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

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

Abstract

In Financial Cryptography 2013, Bringer, Chabanne and Patey proposed two biometric authentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form. The protocols are based on secure computation of Hamming distance in the two-party setting. Their first scheme uses Oblivious Transfer (OT) 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. In this paper, we show that their protocol against malicious adversaries is not actually secure. We propose a generic attack where the Hamming distance can be minimized without knowledge of the real input of the user. Namely, any attacker can impersonate any legitimate user without prior knowledge. We propose an enhanced version of their protocol where this attack is eliminated. We provide a simulation based proof of the security of our modified protocol. In addition, for efficiency concerns, the modified version also utilizes Verifiable Oblivious Transfer (VOT) instead of COT. The use of VOT does not reduce the security of the protocol but improves the efficiency significantly.