Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries
In this paper we construct efficient secure protocols for set intersection and pattern matching. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protoco
- PDF / 621,501 Bytes
- 21 Pages / 430 x 660 pts Page_size
- 39 Downloads / 200 Views
Abstract. In this paper we construct efficient secure protocols for set intersection and pattern matching. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that used secure polynomial evaluation. 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 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.
1
Introduction
In the setting of secure two-party computation, two parties wish to jointly compute some function of their private inputs while preserving a number of security properties. In particular, the parties wish to ensure that nothing is revealed beyond the output (privacy), that the output is computed according to the specified function (correctness) and more. The standard definition today (cf. [5] following [13,4,17]) formalizes security by comparing a real protocol execution to an “ideal execution” where an incorruptible trusted party helps the parties compute the function. Specifically, in the ideal world the parties just send their inputs (over perfectly secure communication lines) to the trusted party, who computes the function honestly and sends the output to the parties. A real protocol (in which parties interact arbitrarily) is said to be secure if any adversarial attack on a real protocol can essentially be carried out also in the ideal world (of course,
This research was supported by an Eshkol scholarship and Infrastructures grant from the Israel Ministry of Science and Technology.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 155–175, 2008. c International Association for Cryptologic Research 2008
156
C. Hazay and Y. Lindell
in the ideal world the adversary can do almost nothing and this guarantees that the same is true also in the real world). This definition of security is often called simulation-based because security is demonstrated by showing that a real protocol execution can be “simulated” in the ideal world. This setting has been widely studied, and it has been shown that any efficient two-party functionality can be securely computed [24,12,11]. These feasibility results demonstrate the wide applicability of secure computation, in principle. However, they fall short of what is needed in implementations because they are far from efficient enough to be used in practice (with a few exceptions). Thi
Data Loading...
