Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries

Carmit Hazay; Yehuda Lindell

Paper 2009/045

Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries

Carmit Hazay and Yehuda Lindell

Abstract

In this paper we construct efficient secure protocols for \emph{set intersection} and \emph{pattern matching}. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that are based on polynomials. In addition to the above, we also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency. Our results are presented in two adversary models. Our protocol for secure pattern matching and one of our protocols for set intersection achieve security against \emph{malicious adversaries} under a relaxed definition where one corruption case is simulatable and for the other only privacy (formalized through indistinguishability) is guaranteed. We also present a protocol for set intersection that is fully simulatable in the model of covert adversaries. Loosely speaking, this means that a malicious adversary can cheat, but will then be caught with good probability.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. An extended abstract of this paper appeared in TCC 2008; this is the full version.
Keywords: secure set intersection secure pattern matching oblivious pseudorandom function evaluation
Contact author(s): lindell @ cs biu ac il
History: 2009-01-29: received
Short URL: https://ia.cr/2009/045
License: CC BY

BibTeX

@misc{cryptoeprint:2009/045,
      author = {Carmit Hazay and Yehuda Lindell},
      title = {Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2009/045},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/045}},
      url = {https://eprint.iacr.org/2009/045}
}