Robert Soule New York University TITLE: Hiding Secret Points amidst Chaff ABSTRACT: 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.