TY - INPR A1 - Fischlin, Marc T1 - Lower bounds for the signature size of incremental schemes N2 - 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. KW - Uniform resource locators KW - Message authentication KW - Security KW - security of data KW - computational complexity KW - incremental schemes KW - signature size KW - lower bounds KW - substitution attacks KW - single block replacement Y1 - 1997 UR - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/4234 UR - https://nbn-resolving.org/urn:nbn:de:hebis:30-12558 SN - 0-8186-8197-7 SN - 0-8186-8198-5 SN - 0-8186-8199-3 SN - 0272-5428 N1 - 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 SP - 1 EP - 22 ER -