Lower bounds for the signature size of incremental schemes
- 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.
Author: | Marc FischlinGND |
---|---|
URN: | urn:nbn:de:hebis:30-12558 |
DOI: | https://doi.org/10.1109/SFCS.1997.646132 |
ISBN: | 0-8186-8197-7 |
ISBN: | 0-8186-8198-5 |
ISBN: | 0-8186-8199-3 |
ISSN: | 0272-5428 |
Contributor(s): | Ian Torwick |
Document Type: | Preprint |
Language: | English |
Year of Completion: | 1997 |
Year of first Publication: | 1997 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2005/07/20 |
Tag: | Message authentication; Security; Uniform resource locators; computational complexity; incremental schemes; lower bounds; security of data; signature size; single block replacement; substitution attacks |
Page Number: | 22 |
First Page: | 1 |
Last Page: | 22 |
Note: | Erschienen in: Proceedings 38th Annual Symposium on Foundations of Computer Science, editorial production by Ian Torwick, Los Alamitos, California ; Washington ; Brussels ; Tokyo : IEEE Computer Society, 1997, S. 438-447, ISBN: 0-8186-8197-7, ISBN 0-8186-8198-5, ISBN 0-8186-8199-3, doi:10.1109/SFCS.1997.646132 |
Source: | IEEE Symposium on Foundations of Computer Science (FOCS) 1997 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
HeBIS-PPN: | 224946889 |
Institutes: | Informatik und Mathematik / Mathematik |
Informatik und Mathematik / Informatik | |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Licence (German): | Deutsches Urheberrecht |