Robert Soule
New York University

Hiding Secret Points amidst Chaff


Motivated by the representation of biometric and multimedia
objects, we consider the problem of hiding noisy point-sets using a secure
sketch. A point-set X consists of s points from a d-dimensional discrete
domain [0,N?$B!]1]d. Under permissible noises, for every point hx1, .., xdi 2
X, each xi may be perturbed by a value of at most ^N. In addition,
at most t points in X may be replaced by other points in [0,N ?$B!] 1]d.
Given an original X, we want to compute a secure sketch P. A known
method constructs the sketch by adding a set of random points R, and
the description of (X [ R) serves as part of the sketch. However, the
dependencies among the random points are difficult to analyze, and there
is no known non-trivial bound on the entropy loss. In this paper, we first
give a general method to generate R and show that the entropy loss
of (X [ R) is at most s(d log^A + d + 0.443), where ^A = 2^N + 1. We
next give improved schemes for d = 1, and special cases for d = 2. Such
improvements are achieved by pre-rounding, and careful partition of the
domains into cells. It is possible to make our sketch short, and avoid
using randomness during construction. We also give a method in d = 1
to demonstrate that, using the size of R as the security measure would
be misleading.

AUTHORS : Ee-Chien Chang and Qiming Li.