CommonSense: Efficient Set Intersection (SetX) protocol based on compressed sensing

Set reconciliation (SetR) is an important research problem that has been studied for over two decades. In this problem, two large sets A and B of objects (tokens, files, records, etc.) are stored respectively at two different network-connected hosts, which we name Alice and Bob respectively. Alice and Bob need to communicate with each other to learn the set union A ∪ B (which then becomes their reconciled state), at low communication and computation costs. In this work, we study a different problem intricately related to SetR: Alice and Bob collaboratively compute A ∩ B . We call this problem SetX (set intersection). Although SetX is just as important as SetR, it has never been properly studied in its own right. Rather, there is an unspoken perception by the research community that SetR and SetX are equally difficult (in costs), and hence “roughly equivalent.” Our first contribution is to show that SetX is fundamentally a much “cheaper” problem than SetR, debunking this long-standing perception. Our second contribution is to develop a novel SetX solution, the communication cost of which handily beats the information-theoretic lower bound of SetR. This protocol is based on the idea of compressed sensing (CS), which we describe here only for the special case of A ⊆ B (We do have a more sophisticated protocol for the general case). Our protocol is for Alice to encode A into a CS sketch M 1 A and send it to Bob, where M is a CS matrix with l rows and 1 A is the binary vector representation of A . Our key innovation here is to make l (the sketch size) just large enough (for the sketch) to summarize B ∖ A (what Alice misses). In contrast, in existing protocols l needs to be large enough to summarize A (what Alice knows), which is typically much larger in cardinality. Our third contribution is to design a CS matrix M that is both “friendly” to (the performance of) applications and “compliant” with CS theory.