 |
|
|
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.
Related Articles:
Forthcoming information-theoretic cryptography book co-written by alum Tyagi and former visitor Watanabe
Alum Ahmed Arafa wins NSF CAREER Award
Dana Dachman-Soled is Program Chair for ITC 2022
A gachapon ‘blind box’ for private information retrieval
Ulukus, Modiano guest-edit IEEE journal special issue on Age of Information
Alum Himanshu Tyagi promoted to Associate Professor at Indian Institute of Science
Alumna Jing Yang wins two IEEE Communications Society awards
Alumnus Ravi Tandon earns tenure at University of Arizona
Alum Himanshu Tyagi wins 2020 INSA Medal for Young Scientists
Alum Ahmed Arafa to join UNC Charlotte faculty this fall
January 7, 2020
|
