Practical memory checkers for stacks, queues and deques

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Marc FischlinGND
Document Type:Article
Date of Publication (online):2005/07/21
Year of first Publication:1997
Publishing Institution:Universit├Ątsbibliothek Johann Christian Senckenberg
Release Date:2005/07/21
Page Number:12
Source:Information Security and Privacy - ACISP '97 , Lecture Notes in Computer Science, Vol. 1270, Springer-Verlag, pp. 114-125, 1997 ,
Institutes:Informatik und Mathematik / Mathematik
Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoDeutsches Urheberrecht