Welcome to the resource topic for 2006/090
Title:
Secure Sketch for Multi-Sets
Authors: Ee-Chien Chang, Vadym Fedyukovych, Qiming Li
Abstract: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\cap Y|\ge |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. (ISIT 2001) 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).
ePrint: https://eprint.iacr.org/2006/090
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .