On confidentiality and algorithms

Recent interest in methods for certifying programs for secure information flow (noninterference) have failed to raise a key question: can efficient algorithms be written so as to satisfy the requirements of secure information flow? In this paper we discuss how algorithms for searching and sorting can be adapted to work on collections of secret data without leaking any confidential information, either directly, indirectly, or through timing behaviour. We pay particular attention to the issue of timing channels caused by the cache behaviour, and argue that it is necessary to disable the effect of the cache in order to construct algorithms manipulating pointers to objects in such a way that they satisfy the conditions of noninterference. We also discuss how randomisation can be used to implement secure algorithms, and discuss how randomised hash tables might be made practically secure.