Preprint
Filtern
Erscheinungsjahr
- 1997 (1) (entfernen)
Dokumenttyp
- Preprint (1) (entfernen)
Sprache
- Englisch (1)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1)
Schlagworte
- Message authentication (1) (entfernen)
Institut
- Informatik (1)
- Mathematik (1)
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.