Secure Sketch for Multi-Sets

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 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)