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

By Carmit Hazay, Yehuda Lindell. Journal of Cryptology, 2008

369 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/c990c616cbac83156f8a65262b26f08ae1382e6b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? (2012, background): “Most prior work on PSI has focused on developing custom protocols specific to the problem [7–11, 14, 15, 20, 24].”
Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection (2009, methodology): “Using the Hazay-Lindell construction [19] one can easily convert a secure computation protocol for OPRF functionality into secure computation of the set intersection problem.”
Location Privacy via Private Proximity Testing (2011, background): “Many other papers have studied private set intersection: [10, 18, 9, 7, 21, 22, 8, 19].”
Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution (2012, background): “Private set intersection has been widely studied in many contexts, including in the presence of malicious adversaries [9, 13, 5, 20, 21, 7].”
Secure Two-Party Computation is Practical (2009, methodology): “OPRF was subsequently used in different constructions, such as protocols for set intersection and pattern matching secure against malicious and covert adversaries [16], or protocols for private itemset support counting [22].”
Efficient Secure Computation with Garbled Circuits (2011, background): “, [32, 47]) concluded that the generic garbled circuit technique is not suitable for solving real world computational problems, and instead developed custom solutions for particular problems [25, 32, 47].”
Constant-Round Multi-party Private Set Union Using Reversed Laurent Series (2012, background): “This problem, for various types of set operations, has received a lot of attention in both the two-party [10, 4, 14, 7, 6, 17, 9, 15, 8] and multi-party [19, 11, 23] settings.”
ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation (2020, background): “This has several applications in PSI [48, 58] and encrypted databases [2, 22].”
Strathprints Institutional Repository (neutral): “Hazey and Lindell [24] proposed another approach for PSI which is based on oblivious pseudorandom function (OPRF) evaluation.”
Fast and Private Computation of Cardinality of Set Intersection and Union (2012, methodology): “Among these, Private Set Intersection (PSI) [15, 29, 18, 26, 19, 27, 12, 11, 22], and Private Set Union (PSU) [29, 19, 21, 16, 36] have recently attracted a lot of attention from the research community.”
Labeled PSI from Fully Homomorphic Encryption with Malicious Security (2018, methodology): “Roughly speaking, to prove that the protocol π of Figure 2 has one-sided simulation [29] we must show that for all malicious PPT receivers A there exists a simulator S such that the interaction of A in the real protocol π is indistinguishable from the output of S when interacting with the ideal func”
Efficient Batched Oblivious PRF with Applications to Private Set Intersection (2016, methodology): “OPRFs have been used for PSI elsewhere, generally in the malicious adversarial model [13, 10, 9].”
Verifiable Delegation of Computation over Large Datasets (2011, background): “the entire work on threshold cryptography [21], or protocols on set intersection and pattern matching such as [34]).”
Fast Private Set Operations with SEPIA (2012, background): “Furthermore, certain works [11, 9, 17] have developed interesting custom cryptographic protocols for secure set operations.”