Stack and queue integrity on hostile platforms

When computationally intensive tasks have to be carried out on trusted, but limited, platforms such as smart cards, it becomes necessary to compensate for the limited resources (memory, CPU speed) by off-loading implementations of data structures on to an available (but insecure, untrusted) fast co-processor. However, data structures such as stacks, queues, RAMs and hash tables can be corrupted (and made to behave incorrectly) by a potentially hostile implementation platform or by an adversary knowing or choosing data structure operations. This paper examines approaches that can detect violations of data structure invariants, while placing limited demands on the resources of the secure computing platform.