id: 05940042
dt: a
an: 05940042
au: De Bonis, Annalisa; Di Crescenzo, Giovanni
ti: Combinatorial group testing for corruption localizing hashing.
so: Fu, Bin (ed.) et al., Computing and combinatorics. 17th annual
    international conference, COCOON 2011, Dallas, TX, USA, August 14‒16,
    2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22684-7/pbk).
    Lecture Notes in Computer Science 6842, 579-591 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: algorithms; cryptography; group testing; superimposed codes
ci: 
li: doi:10.1007/978-3-642-22685-4_50
ab: Summary: Corruption-localizing hashing is a recently introduced
    cryptographic primitive that enhances the well-known primitive of
    collision-intractable hashing. In addition to allowing detection of
    changes in input data, they also provide a superset of the changes
    location, where the accuracy of this superset is formalized as a
    metric, called localization factor. In this paper we consider the
    problem of designing corruption-localizing hash schemes with reduced
    localization factor. We define a new and natural notion of localizing
    codes, and prove that any such code can be used in conjunction with
    collision-intractable hashing, to obtain corruption-localizing hashing,
    a general result of independent interest. Then we propose two
    localizing codes based on combinatorial group testing techniques (i.e.,
    superimposed codes), resulting in the first corruption-localizing hash
    scheme with constant localization factor against an unbounded number of
    corruptions of distinct and unbounded lengths.
rv: