CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing

In the set reconciliation ($\mathsf{\text{SetR}}$) problem, two parties Alice and Bob, holding sets $\mathsf{A}$ and $\mathsf{B}$, communicate to learn the symmetric difference $\mathsf{A}\mathrm{\Delta }\mathsf{B}$. In this work, we study a related but under-explored problem: set intersection ($\mathsf{\text{SetX}}$)~\cite{Ozisik2019}, where both parties learn $\mathsf{A}\cap \mathsf{B}$ instead. However, existing solutions typically reuse $\mathsf{\text{SetR}}$ protocols due to the absence of dedicated $\mathsf{\text{SetX}}$ protocols and the misconception that $\mathsf{\text{SetR}}$ and $\mathsf{\text{SetX}}$ have comparable costs. Observing that $\mathsf{\text{SetX}}$ is fundamentally cheaper than $\mathsf{\text{SetR}}$, we developed a multi-round $\mathsf{\text{SetX}}$ protocol that outperforms the information-theoretic lower bound of $\mathsf{\text{SetR}}$ problem. In our $\mathsf{\text{SetX}}$ protocol, Alice sends Bob a compressed sensing (CS) sketch of $\mathsf{A}$ to help Bob identify his unique elements (those in $\mathsf{B}\setminus \mathsf{A}$). This solves the $\mathsf{\text{SetX}}$ problem, if $\mathsf{A}\subseteq \mathsf{B}$. Otherwise, Bob sends a CS sketch of the residue (a set of elements he cannot decode) back to Alice for her to decode her unique elements (those in $\mathsf{A}\setminus \mathsf{B}$). As such, Alice and Bob communicate back and forth %with a set membership filter (SMF) of estimated $\mathsf{B}\setminus \mathsf{A}$. Alice updates $\mathsf{A}$ and communication repeats until both parties agrees on $\mathsf{A}\cap \mathsf{B}$. On real world datasets, experiments show that our $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{X}$ protocol reduces the communication cost by 8 to 10 times compared to the IBLT-based $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{R}$ protocol.