On private Hamming distance computation

Kok Seng Wong, Myung Ho Kim

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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
Volume69
Issue number3
DOIs
Publication statusPublished - Jan 1 2013
Externally publishedYes

Fingerprint

Hamming distance
Hamming Distance
Data privacy
Network protocols
Privacy
Servers
Server
Homomorphic
Cryptosystem
Biometrics
Cloud computing
Cloud Computing
Information retrieval
Information Retrieval
Cryptography
Data mining
Correctness
Multiplicative
Data Mining
Output

Keywords

  • 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

Cite this

On private Hamming distance computation. / Wong, Kok Seng; Kim, Myung Ho.

In: Journal of Supercomputing, Vol. 69, No. 3, 01.01.2013, p. 1123-1138.

Research output: Contribution to journalArticle

Wong, Kok Seng ; Kim, Myung Ho. / On private Hamming distance computation. In: Journal of Supercomputing. 2013 ; Vol. 69, No. 3. pp. 1123-1138.
@article{4c44ee0d758c4ae78421a9ab1b0ccb55,
title = "On private Hamming distance computation",
abstract = "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.",
keywords = "Privacy preserving computation protocol, Private Hamming distance, Secure two-party computation, Similarity measurement",
author = "Wong, {Kok Seng} and Kim, {Myung Ho}",
year = "2013",
month = "1",
day = "1",
doi = "10.1007/s11227-013-1063-z",
language = "English",
volume = "69",
pages = "1123--1138",
journal = "Journal of Supercomputing",
issn = "0920-8542",
publisher = "Springer Netherlands",
number = "3",

}

TY - JOUR

T1 - On private Hamming distance computation

AU - Wong, Kok Seng

AU - Kim, Myung Ho

PY - 2013/1/1

Y1 - 2013/1/1

N2 - 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.

AB - 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.

KW - Privacy preserving computation protocol

KW - Private Hamming distance

KW - Secure two-party computation

KW - Similarity measurement

UR - http://www.scopus.com/inward/record.url?scp=84920260578&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84920260578&partnerID=8YFLogxK

U2 - 10.1007/s11227-013-1063-z

DO - 10.1007/s11227-013-1063-z

M3 - Article

VL - 69

SP - 1123

EP - 1138

JO - Journal of Supercomputing

JF - Journal of Supercomputing

SN - 0920-8542

IS - 3

ER -