Secure Sketch for Multi-Sets

Ee-Chien Chang; Vadym Fedyukovych; Qiming Li

Paper 2006/090

Secure Sketch for Multi-Sets

Ee-Chien Chang, 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 | \geq | 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 $2 t (1 + \log n)$ .

Note: slight changes were made to the asbtract.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Secure sketch set difference multi-set error-tolerant cryptography
Contact author(s): liqiming @ gmail com
History: 2006-03-15: revised; 2006-03-08: received; See all versions
Short URL: https://ia.cr/2006/090
License: CC BY

BibTeX

@misc{cryptoeprint:2006/090,
      author = {Ee-Chien Chang and Vadym Fedyukovych and Qiming Li},
      title = {Secure Sketch for Multi-Sets},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/090},
      year = {2006},
      url = {https://eprint.iacr.org/2006/090}
}