Paper 2005/145

Small Secure Sketch for Point-Set Difference

Ee-Chien Chang and Qiming Li

Abstract

A secure sketch is a set of published data that can help to recover the original biometric data after they are corrupted by permissible noises, and by itself does not reveal much information about the original. Several constructions have been proposed for different metrics, and in particular, set difference. We observe that in many promising applications, set difference alone is insufficient to model the noises. We propose to look into point-set difference, which measures noises that not only remove/introduce new feature points in the biometric objects, but may also perturb the points. In this paper, we first give an improvement for set difference construction that can be extended to multi-sets, where the sketch is small and there is an efficient decoding algorithm. We next give a sketch for point-set difference in both one and two-dimensional spaces. By using results in almost k-wise independence, the size of the sketch is reduced to near-optimal.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
error-tolerant cryptographysecure sketchpoint-set difference.
Contact author(s)
liqiming @ gmail com
History
2005-05-19: received
Short URL
https://ia.cr/2005/145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/145,
      author = {Ee-Chien Chang and Qiming Li},
      title = {Small Secure Sketch for Point-Set Difference},
      howpublished = {Cryptology ePrint Archive, Paper 2005/145},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/145}},
      url = {https://eprint.iacr.org/2005/145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.