**Secure Sketch for Multi-Sets**

*Ee-Chien Chang and Vadym Fedyukovych and 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)$.

**Category / Keywords: **Secure sketch, set difference, multi-set, error-tolerant cryptography

**Date: **received 8 Mar 2006, last revised 15 Mar 2006

**Contact author: **liqiming at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **slight changes were made to the asbtract.

**Version: **20060315:181400 (All versions of this report)

**Short URL: **ia.cr/2006/090

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]