Secure Sketch for Multi-Sets.
Ee‐Chien Chang, Vadym Fedyukovych, Qiming Li · IACR Cryptology ePrint Archive · 2006
Given the original set X where |X| = s, a sketch P is computed from X and made public. From another set Y where |Y | = s and P , we can reconstruct X if |X ∩ Y | ≥ |s − t|, where t < s is some threshold. The sketch P is secure if it does not reveal much information about X. A few constructions have been proposed, but they cannot handle multi-sets, that is, sets that may contain duplicate elements. We observe that the techniques in the set reconciliation protocol proposed by Minsky et al. [3] can be applied and give a secure sketch that supports multi-sets. If X is a subset of an universe with n elements, the running time of the encoding and decoding algorithms will be polynomial w.r.t. s and log n, and the entropy loss due to the sketch is less than 2t(1 + log n).