The authors present a protocol for maintaining the integrity of stacks and queues processed by a potentially hostile processor (H), when resources of the trusted processor (T) are too limited to allow for processing of stacks and queues.

For a stack protocol, the authors use a random number generator and a one-way hash function. In effect, for each datum, the datum itself and a hash value are pushed onto the stack, and, upon popping, the topmost datum and a hash value are returned by H to T. T then tests the hashed value to check whether integrity of the stack was compromised. The authors show that the protocol is secure, as long the hash function is collision-resistant and second preimage-resistant. The authors also present a protocol for queue processing that uses a keyed one-way hash function.

The protocols for stacks and queues require constant memory in T, and transfer a constant amount of data. This is an improvement over previous approaches, which were of the order O(log n). The authors briefly address the issue of application, particularly in the context of secure RAM management, in the context of the Java virtual machine, and in the context of distributed processing.