Cryptology ePrint Archive: Report 2012/586

SHADE: Secure HAmming DistancE computation from oblivious transfer

Julien Bringer and Herve Chabanne and Alain Patey

Abstract: We introduce two new schemes for securely computing Hamming distance in the two-party setting. Our first scheme is a very efficient protocol, based solely on 1-out-of-2 Oblivious Transfer, that achieves full security in the semi-honest setting and one-sided security in the malicious setting. Moreover we show that this protocol is significantly more efficient than the previous proposals, that are either based on garbled circuits or on homomorphic encryption. Our second scheme achieves full security against malicious adversaries and is based on Committed Oblivious Transfer. These protocols have direct applications to secure biometric identification.

Category / Keywords: cryptographic protocols / Secure Multi-Party Computation, Hamming Distance, Oblivious Transfer, Biometric Identification

Date: received 16 Oct 2012

Contact author: alain patey at telecom-paristech fr

Available formats: PDF | BibTeX Citation

Version: 20121016:133630 (All versions of this report)

Discussion forum: Show discussion | Start new discussion