A Group Testing Approach to Corruption Localizing Hashing

Thursday, February 16, 2012 - 2:00pm - 3:00pm
Keller 3-180
Annalisa De Bonis (Università di Salerno)
Efficient detection of integrity violations is crucial for the reliability of both data at rest and data in transit. In addition to detecting corruptions, it is often desirable to have the capability of obtaining information about the location of corrupted data blocks. While ideally one would want to always find all changes in the corrupted 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 is a cryptographic primitive that enhances collision-intractable hash functions thus improving the detection property of these functions into a suitable localization property. Besides allowing detection of changes in the input data, corruption-localizing hash schemes also 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 talk we will address the problem of designing corruption-localizing hash schemes with reduced localization factor and with small time and storage complexity. We will show that this problem corresponds to a particular variant of nonadaptive group testing, and illustrate a construction technique based on superimposed codes.
This group testing approach allowed to obtain corruption-localizing hash schemes that greatly improve on previous constructions.
In particular, we will present a corruption-localizing hash scheme that achieves an arbitrarily small localization factor
while only incurring a sublinear time and storage complexity.