Welcome to the resource topic for 2011/562
Title:
A Group Testing Approach to Improved Corruption Localizing Hashing
Authors: Annalisa De Bonis, 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}.
ePrint: https://eprint.iacr.org/2011/562
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .