Information theoretic approach to the private set intersection problem

An airline company has a list of its customers, and a law enforcement agency has a list of suspected terrorists. The airline company and the law enforcement agency wish to determine the intersection of their respective lists without the airline company revealing the rest of its customers and the law enforcement agency revealing the rest of its suspects. This is an example of the Private Set Intersection (PSI) problem, a major research topic in the field of cryptography. PSI refers to the problem of determining the common elements in two sets (lists) without leaking additional information about the remaining elements in either of them.

In a new paper, Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective, Professor Sennur Ulukus (ECE/ISR), former student Karim Banawan (Ph.D. EE 2018), and current Ph.D. student Zhusheng Wang take an information theoretic approach, showing that the PSI problem can be successfully recast as a multi-message symmetric private information retrieval (MM-SPIR) problem with message size 1. They assume that the sets (or their corresponding incidence vectors) can be stored in replicated and non-colluding databases. Further, the set elements are generated in an independent and identically distributed fashion with a probability1/2 of adding any element to any of the sets.

Published January 7, 2020