Efficient fuzzy matching and intersection on private datasets

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

6 Citations (Scopus)


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 languageEnglish
Title of host publicationInformation Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers
EditorsDooghoon Lee, Seokhie Hong
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Number of pages18
Volume5984 LNCS
ISBN (Print)3642144225, 9783642144226
Publication statusPublished - 2010
Event12th International Conference on Information Security and Cryptology, ICISC 2009 - Seoul, Korea, Republic of
Duration: 2 Dec 20094 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5984 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other12th International Conference on Information Security and Cryptology, ICISC 2009
Country/TerritoryKorea, Republic of


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

Cite this