Information theoretic approach to the private set intersection problem

Example for the transformation from sets to incidence vectors. Figure from the paper.

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.

Current Headlines

Srivastava Named Inaugural Director of Semiconductor Initiatives and Innovation

State-of-the-Art 3D Nanoprinter Now at UMD

UMD, Partners Receive $31M for Semiconductor Research

Two NSF Awards for ECE Alum Michael Zuzak (Ph.D. ’22)

Applications Open for Professor and Chair of UMD's Department of Materials Science and Engineering

Ghodssi Honored With Gaede-Langmuir Award

Milchberg and Wu named Distinguished University Professors

New features on ingestible capsule will deliver targeted drugs to better treat IBD, Crohn’s disease

Forty years of MEMS research at the Hilton Head Workshop

Baturalp Buyukates (ECE Ph.D. ’21) Honored by IEEE ComSoc