Digital signatures are widely used to guarantee the integrity, authenticity and non-repudiation of a signed message. They can detect for example if modifications were done in a document after it was signed, but do not offer information on where exactly those modifications occurred. In this context, even a single bit change would invalidate the entire document. In this work, we consider the problem of detecting and locating modifications in signed data to ensure partial data integrity, and we achieve this by using combinatorial group testing.

The purpose of combinatorial group testing is to identify $d$ defective elements from a set of $n$ elements pooled into $t$ groups, where $t < n$. The groups are tested, instead of all elements individually.

In our scenario we assume that the data to be signed is divided into $n$ blocks and that a threshold $d$ is given for the maximum amount of modified blocks that the scheme can support. We propose signature and verification algorithms based on group testing to localize up to $d$ modified blocks in a digitally signed document. Our algorithms provide a reasonably compact signature size for controlled sizes of $d$ with respect to $n$. For instance, for fixed $d$ the standard signature size gets multiplied by a factor of $O(log n)$, while allowing the identification of up to $d$ modified blocks.

Based on joint work with Lucia Moura, Ricardo Cust\'odio and Daniel Panario.