Lower bounds for the signature size of incremental schemes
Marc Fischlin · 2002
We show lower bounds for the signature size of incremental schemes which are secure against substitution attacks and support single block replacement. We prove that for documents of n blocks such schemes produce signatures of /spl Omega/(n/sup 1/(2+c)/) bits for any constant c>0. For schemes accessing only a single block resp. A constant number of blocks for each replacement this bound can be raised to /spl Omega/(n) resp. /spl Omega/(/spl radic/n). Additionally, we show that our technique yields a new lower bound for memory checkers.