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? 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 cache behaviour and argue that it is necessary to disable the affect 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.

One aspect of security in mobile code is privacy: private (or secret) data should not be leaked to unauthorised agents. Most of the work on secure information flow has until recently only been concerned with detecting direct and indirect flows. Secret information can however be leaked to the attacker also through covert channels. It is very reasonable to assume that the attacker, even as an external observer, can monitor the timing (including termination) behaviour of the program. Thus to claim a program secure, the security analysis must take also these into account.