Refine
Document Type
- Preprint (8)
- Article (1)
- Diploma Thesis (1)
- diplomthesis (1)
- Doctoral Thesis (1)
Has Fulltext
- yes (12)
Is part of the Bibliography
- no (12)
Keywords
- Kongress (5)
- Kryptologie (5)
- Online-Publikation (4)
- Commitment Scheme (2)
- Oblivious Transfer (2)
- San Jose (2)
- Blind Signature (1)
- Chinese Remainder Theorem (1)
- Commitment (1)
- Commitment schemes (1)
Institute
- Mathematik (11)
- Informatik (10)
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.
A memory checker for a data structure provides a method to check that the output of the data structure operations is consistent with the input even if the data is stored on some insecure medium. In [8] we present a general solution for all data structures that are based on insert(i,v) and delete(j) commands. In particular this includes stacks, queues, deques (double-ended queues) and lists. Here, we describe more time and space efficient solutions for stacks, queues and deques. Each algorithm takes only a single function evaluation of a pseudorandomlike function like DES or a collision-free hash function like MD5 or SHA for each push/pop resp. enqueue/dequeue command making our methods applicable to smart cards.