Locating modifications in signed data for partial data integrity

• We propose locating modifications in signed data to ensure partial data integrity.
• We use combinatorial group testing to locate which document blocks were modified.
• Efficient algorithms for signing and verifying are given and analyzed.
• Signature size is only moderately increased in this more robust scheme.
• The running time of our algorithms are compared with traditional signature schemes.

We consider the problem of detecting and locating modifications in signed data to ensure partial data integrity. We assume that the data is divided into n blocks (not necessarily of the same size) and that a threshold d is given for the maximum amount of modified blocks that the scheme can support. We propose efficient algorithms for signature and verification steps which 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)O(log⁡n), while allowing the identification of up to d modified blocks. Our scheme is based on nonadaptive combinatorial group testing and cover-free families.