Graduate Thesis Or Dissertation
 

Keeping your Friends Secret: Improving the Security, Effciency and Usability of Private Set Intersection

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/dv140035w

Descriptions

Attribute NameValues
Creator
Abstract
  • Private set intersection (PSI) allows two parties, who each hold a set of items, to compute the intersection of those sets without revealing anything about other items. Recent advances in PSI have significantly improved its performance for the case of semi-honest security, making semi-honest PSI a practical alternative to insecure methods for computing intersections. However, these protocols have two major drawbacks: 1) the amount of data required to be communicated can be orders of magnitude larger than an insecure solution and 2) when in the presence of malicious parties the security of these protocols breaks down. In this work, four malicious secure PSI protocols are introduced along with three semi-honest protocols which have sublinear communication. These protocols are based on a combination of fast symmetric-key primitives and fully homomorphic encryption. Three of these protocols represent the current state of the art for their respective settings. The practicality of these protocols are demonstrated with prototype implementations. To securely compute the intersection of two sets of size 2²⁰ in the malicious setting requires only 13 seconds, which is ~ 450x faster than the previous best malicious-secure protocol (De Cristofaro et al, Asiacrypt 2010), and only 3x slower than the best semi-honest protocol (Kolesnikov et al., CCS 2016). Alternatively, when computing the intersection between set sizes of 2¹⁰ and 2²⁸, our fastest protocol require just 6 seconds and 5MB of communication.
License
Resource Type
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Academic Affiliation
Rights Statement
Publisher
Peer Reviewed
Language

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details RindalPeter2018.pdf 2018-10-09 Public Download