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
Contributor(s):Ian Torwick
Document Type:Preprint
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
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
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):License LogoDeutsches Urheberrecht