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|\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)$.
Note: slight changes were made to the asbtract.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Secure sketchset differencemulti-seterror-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},
note = {\url{https://eprint.iacr.org/2006/090}},
url = {https://eprint.iacr.org/2006/090}
}
