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

In the set reconciliation (SetR) problem, two parties Alice and Bob, holding sets A and B respectively, communicate to learn the symmetric difference A Δ B. In this work, we study a related but under-explored problem: set intersection (SetX) [7], where both parties learn A ∩ B instead. Existing solutions typically reuse SetR protocols due to the absence of dedicated SetX protocols and the misconception that SetR and SetX have comparable costs. Observing that SetX is fundamentally cheaper than SetR, we have developed a multi-round SetX protocol that outperforms the information-theoretic lower bound of SetR problem. In our SetX protocol, Alice sends Bob a compressed sensing (CS) sketch of A to help Bob identify his unique elements (those in B \ A). This solves the SetX problem, if A ⊆ 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 A \ B). As such, Alice and Bob communicate back and forth until both parties agree on A ∩ B. On real world datasets, experiments show that our SetX protocol reduces the communication cost by 8 to 10 times compared to the IBLT-based SetR protocol.