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

– 1]

d

. Under permissible noises, for every point

$\left \langle x_1,..,x_d\right \rangle \in X$

, each

x

i

may be perturbed by a value of at most

δ

. In addition, at most

t

points in

X

may be replaced by other points in [0,

N

– 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Δ+

d

+ 0.443), where Δ= 2

δ

+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.