Efficient fuzzy matching and intersection on private datasets

Qingsong Ye; Ron Steinfeld; Josef Pieprzyk; Huaxiong Wang

doi:10.1007/978-3-642-14423-3_15

Efficient fuzzy matching and intersection on private datasets

Qingsong Ye^*, Ron Steinfeld, Josef Pieprzyk, Huaxiong Wang

^*Corresponding author for this work

Department of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

6 Citations (Scopus)

Abstract

At Eurocrypt'04, Freedman, Nissim and Pinkas introduced a fuzzy private matching problem. The problem is defined as follows. Given two parties, each of them having a set of vectors where each vector has T integer components, the fuzzy private matching is to securely test if each vector of one set matches any vector of another set for at least t components where t < T. In the conclusion of their paper, they asked whether it was possible to design a fuzzy private matching protocol without incurring a communication complexity with the factor . We answer their question in the affirmative by presenting a protocol based on homomorphic encryption, combined with the novel notion of a share-hiding error-correcting secret sharing scheme, which we show how to implement with efficient decoding using interleaved Reed-Solomon codes. This scheme may be of independent interest. Our protocol is provably secure against passive adversaries, and has better efficiency than previous protocols for certain parameter values.

Original language	English
Title of host publication	Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers
Editors	Dooghoon Lee, Seokhie Hong
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	211-228
Number of pages	18
Volume	5984 LNCS
ISBN (Print)	3642144225, 9783642144226
DOIs	https://doi.org/10.1007/978-3-642-14423-3_15
Publication status	Published - 2010
Event	12th International Conference on Information Security and Cryptology, ICISC 2009 - Seoul, Korea, Republic of Duration: 2 Dec 2009 → 4 Dec 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5984 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	12th International Conference on Information Security and Cryptology, ICISC 2009
Country	Korea, Republic of
City	Seoul
Period	2/12/09 → 4/12/09

Access to Document

10.1007/978-3-642-14423-3_15

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Efficient fuzzy matching and intersection on private datasets'. Together they form a unique fingerprint.

Cite this

Ye, Q., Steinfeld, R., Pieprzyk, J., & Wang, H. (2010). Efficient fuzzy matching and intersection on private datasets. In D. Lee, & S. Hong (Eds.), Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers (Vol. 5984 LNCS, pp. 211-228). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS). Berlin; Heidelberg: Springer, Springer Nature. https://doi.org/10.1007/978-3-642-14423-3_15

Ye, Qingsong ; Steinfeld, Ron ; Pieprzyk, Josef ; Wang, Huaxiong. / Efficient fuzzy matching and intersection on private datasets. Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. editor / Dooghoon Lee ; Seokhie Hong. Vol. 5984 LNCS Berlin; Heidelberg : Springer, Springer Nature, 2010. pp. 211-228 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b3134e4b69594547bd8011efae8aeb61,

title = "Efficient fuzzy matching and intersection on private datasets",

abstract = "At Eurocrypt'04, Freedman, Nissim and Pinkas introduced a fuzzy private matching problem. The problem is defined as follows. Given two parties, each of them having a set of vectors where each vector has T integer components, the fuzzy private matching is to securely test if each vector of one set matches any vector of another set for at least t components where t < T. In the conclusion of their paper, they asked whether it was possible to design a fuzzy private matching protocol without incurring a communication complexity with the factor . We answer their question in the affirmative by presenting a protocol based on homomorphic encryption, combined with the novel notion of a share-hiding error-correcting secret sharing scheme, which we show how to implement with efficient decoding using interleaved Reed-Solomon codes. This scheme may be of independent interest. Our protocol is provably secure against passive adversaries, and has better efficiency than previous protocols for certain parameter values.",

author = "Qingsong Ye and Ron Steinfeld and Josef Pieprzyk and Huaxiong Wang",

year = "2010",

doi = "10.1007/978-3-642-14423-3_15",

language = "English",

isbn = "3642144225",

volume = "5984 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "211--228",

editor = "Dooghoon Lee and Seokhie Hong",

booktitle = "Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers",

address = "United States",

}

Ye, Q, Steinfeld, R, Pieprzyk, J & Wang, H 2010, Efficient fuzzy matching and intersection on private datasets. in D Lee & S Hong (eds), Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. vol. 5984 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5984 LNCS, Springer, Springer Nature, Berlin; Heidelberg, pp. 211-228, 12th International Conference on Information Security and Cryptology, ICISC 2009, Seoul, Korea, Republic of, 2/12/09. https://doi.org/10.1007/978-3-642-14423-3_15

Efficient fuzzy matching and intersection on private datasets. / Ye, Qingsong; Steinfeld, Ron; Pieprzyk, Josef; Wang, Huaxiong.

Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. ed. / Dooghoon Lee; Seokhie Hong. Vol. 5984 LNCS Berlin; Heidelberg : Springer, Springer Nature, 2010. p. 211-228 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

TY - GEN

T1 - Efficient fuzzy matching and intersection on private datasets

AU - Ye, Qingsong

AU - Steinfeld, Ron

AU - Pieprzyk, Josef

AU - Wang, Huaxiong

PY - 2010

Y1 - 2010

N2 - At Eurocrypt'04, Freedman, Nissim and Pinkas introduced a fuzzy private matching problem. The problem is defined as follows. Given two parties, each of them having a set of vectors where each vector has T integer components, the fuzzy private matching is to securely test if each vector of one set matches any vector of another set for at least t components where t < T. In the conclusion of their paper, they asked whether it was possible to design a fuzzy private matching protocol without incurring a communication complexity with the factor . We answer their question in the affirmative by presenting a protocol based on homomorphic encryption, combined with the novel notion of a share-hiding error-correcting secret sharing scheme, which we show how to implement with efficient decoding using interleaved Reed-Solomon codes. This scheme may be of independent interest. Our protocol is provably secure against passive adversaries, and has better efficiency than previous protocols for certain parameter values.

AB - At Eurocrypt'04, Freedman, Nissim and Pinkas introduced a fuzzy private matching problem. The problem is defined as follows. Given two parties, each of them having a set of vectors where each vector has T integer components, the fuzzy private matching is to securely test if each vector of one set matches any vector of another set for at least t components where t < T. In the conclusion of their paper, they asked whether it was possible to design a fuzzy private matching protocol without incurring a communication complexity with the factor . We answer their question in the affirmative by presenting a protocol based on homomorphic encryption, combined with the novel notion of a share-hiding error-correcting secret sharing scheme, which we show how to implement with efficient decoding using interleaved Reed-Solomon codes. This scheme may be of independent interest. Our protocol is provably secure against passive adversaries, and has better efficiency than previous protocols for certain parameter values.

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

U2 - 10.1007/978-3-642-14423-3_15

DO - 10.1007/978-3-642-14423-3_15

M3 - Conference proceeding contribution

SN - 3642144225

SN - 9783642144226

VL - 5984 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 211

EP - 228

BT - Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers

A2 - Lee, Dooghoon

A2 - Hong, Seokhie

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

ER -

Ye Q, Steinfeld R, Pieprzyk J, Wang H. Efficient fuzzy matching and intersection on private datasets. In Lee D, Hong S, editors, Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. Vol. 5984 LNCS. Berlin; Heidelberg: Springer, Springer Nature. 2010. p. 211-228. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-14423-3_15