Efficient Privacy Preserving Exact Rule Matching

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.