Publications - Abstracts

Research Group of Prof.C.P.Schnorr, University of Frankfurt am Main

Practical Memory Checkers for Stacks, Queues and Deques

Marc Fischlin
Fachbereich Mathematik (AG 7.2) / Informatik
Johann Wolfgang Goethe-Universität Frankfurt am Main
PSF 111932
60054 Frankfurt/Main, Germany

e-mail: marc@informatik.uni-frankfurt.de
URL: http://www.mi.informatik.uni-frankfurt.de/

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 the .ps or gnuzipped .ps.gz version.

Click here to return.

Webmaster
Last modified: July 16, 1997