Paper 2011/562

A Group Testing Approach to Improved Corruption Localizing Hashing

Annalisa De Bonis and Giovanni Di Crescenzo

Abstract

Efficient detection of integrity violations is crucial for the reliability of both data at rest and data in transit. While ideally one would want to always find all changes in the input data, in practice this capability may be expensive, and one may be content with localizing or finding a superset of any changes. Corruption-localizing hashing \cite{esorics09} is a cryptographic primitive that enhances collision-intractable hash functions thus improving the detection property of these functions into a suitable localization property. Corruption localizing hash schemes obtain some superset of the changes location, where the accuracy of this superset with respect to the actual changes is a metric of special interest, called localization factor. In this paper we consider the problem of designing corruption localizing hash schemes with reduced localization factor. In \cite{cocoon11}, combinatorial group testing techniques have been exploited to construct the first corruption-localizing hash scheme with {\em constant} localization factor and sublinear storage and time complexity. In this paper we continue the approach of \cite{cocoon11} and present schemes that improve on previous constructions in that they achieve an arbitrarily small localization factor while insuring the same time and storage complexity of the schemes in \cite{cocoon11}.

Note: The paper has been presented at "ICALP 2011 Workshop on Algorithms and Data Structures for selection, identification and encoding (ICALP2011GT)". The workshop had no published proceedings.