Publications - Abstracts

Research Group of Prof.C.P.Schnorr, University of Frankfurt am Main

Lower Bounds for the Signature Size of Incremental Schemes

Marc Fischlin
Fachbereich Mathematik (AG 7.2) / Informatik
Johann Wolfgang Goethe-Universität Frankfurt am Main
PSF 111932
60054 Frankfurt/Main, Germany

e-mail: marc@mi.informatik.uni-frankfurt.de
URL: http://www.mi.informatik.uni-frankfurt.de

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 \Omega(n^(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 \Omega(n) resp. \Omega(sqrt(n)). Additionally, we show that our technique yields a new lower bound for memory checkers.

Download the .ps, .dvi or gnuzipped .ps.gz version.

Click here to return.