Refine
Year of publication
- 1997 (1)
Document Type
- Preprint (1)
Language
- English (1) (remove)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1) (remove)
Keywords
- security of data (1) (remove)
Institute
- Mathematik (1) (remove)
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.