Efficient Implementation of Set Reconciliation Using BCH-Based Secure Sketches

Set reconciliation is the problem of efficiently computing the difference be-tween two sets of data held by two different parties. We implement set recon-ciliation using the BCH-based secure sketch for the set-difference metric, as defined in [1], to solve this problem. This method publishes a secure sketch of a set A, which reveals little about the actual contents of A, assuming A is sufficiently large. However, given another set B which is sufficiently close to A, the set difference of A and B (and, thus, the exact contents of A) can be computed.