Paper 2012/586

SHADE: Secure HAmming DistancE computation from oblivious transfer

Julien Bringer, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Secure Multi-Party ComputationHamming DistanceOblivious TransferBiometric Identification
Contact author(s)
alain patey @ telecom-paristech fr
History
2012-10-16: received
Short URL
https://ia.cr/2012/586
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/586,
      author = {Julien Bringer and Herve Chabanne and Alain Patey},
      title = {SHADE: Secure HAmming DistancE computation from oblivious transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2012/586},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/586}},
      url = {https://eprint.iacr.org/2012/586}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.