Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Doctor of Philosophy

Program

Electrical and Computer Engineering

Supervisor

Essex, Alexsander

Abstract

Private Set Intersection (PSI) enables two parties to compute the intersection of sets without exposing elements outside the intersection. Existing PSI protocols are often designed for a balanced setting, where both parties have sets of comparable magnitude. However, many real-world scenarios are unbalanced, with one party's set much larger than the other. Additionally, many unbalanced PSI protocols require pre-processing of the larger set, making them inefficient in the updateable setting, where the set has elements continually being added to it. We propose a new protocol for unbalanced PSI that is efficient in the additively updateable setting. Our protocol has a communication cost linear in the smaller set and computational cost that is constant in the sender's and receiver's individual set cardinalities, making this approach suitable, for example, in a setting where the sender wishes to match a real-time network data stream against a private intrusion detection rule set. Compared to previous work in the unbalanced and updatable setting, our system has lower computational and communication complexity. For a receiver set size of 10,000 rules, our implementation performed over 27,000 queries per second on a cloud-compute instance costing $1.50 per hour with the encrypted set intersection data sent back to the receiver remaining constant under 1MB.

Summary for Lay Audience

National security agencies have information about the signature behaviours of specific cyber attackers that could be used to detect intrusions on a company's network. A problem is that the agency's information is confidential and cannot be openly shared with companies. They also do not have the mandate to observe a domestic company's network. A secure protocol that can ensure the confidentiality of the signatures and the privacy of the network traffic is needed. To operate on live network traffic, such a protocol would have to meet strict efficiency requirements. Private Set Intersection (PSI) protocols are solutions to this privacy paradigm. However, most existing PSI protocols are designed for a balanced setting, where both parties have set sizes of comparable magnitude. In many real-world scenarios, the set sizes differ by orders of magnitude, this is referred to as the unbalanced setting. Additionally, many unbalanced PSI protocols require pre-processing of the larger set. However, when dealing with network traffic the set is not known ahead of time and so cannot be pre-processed. When a set is being added to during the run-time of the protocol we refer to it as the additively updatable setting. We propose a new protocol for unbalanced PSI that is efficient in the additively updateable setting. Our protocol has a communication cost that is linear in the smaller set and a computational cost that is constant in the sender's and receiver's set cardinalities, making this approach suitable, for example, in a setting where the sender wishes to match a real-time network data stream against a private intrusion detection rule set. We prove the privacy of the protocol with strong cryptographic assumptions. We implemented the protocol to prove its efficiency in the desired settings. For a receiver set size of 10,000 rules, our implementation performed over 27,000 queries per second on a cloud-compute instance costing $1.50 per hour with the encrypted set intersection data sent back to the receiver remaining constant under 1MB.

Download

Share

COinS