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
AN - SCOPUS:77954608051
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
T2 - 12th International Conference on Information Security and Cryptology, ICISC 2009
Y2 - 2 December 2009 through 4 December 2009
ER -