.png){kind=icon}
.png){kind=icon}
Return
COMMONSENSE: Efficient Set Intersection (SetX) protocol based on compressed sensing
.png){kind=icon}
OA
AI
DOI：10.1016/j.peva.2025.102520.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 U 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 An 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 & Oacute; B (We do have a more sophisticated protocol for the general case). Our protocol is for Alice to encode A into a CS sketch M1A and send it to Bob, where M is a CS matrix with l rows and 1A 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.
Keywords:
Set reconciliation
Set intersection
Blockchains
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
P
IF:
0.8
Papers:
38
Citations:
851