On the encipherment of search trees and random access files

The securing of information in indexed, random access files by means of privacy transformations must be considered as a problem distinct from that for sequential files. Not only must processing overhead due to encrypting be considered, but also must threats to encipherment arising from updating and the file structure itself be countered. A general encipherment scheme is proposed for files maintained in a paged structure on secondary storage. This is then applied to the encipherment of indexes organized as B-trees, a particular type of multiway search tree. Threats to the encipherment of B-trees, especially relating to updating, are examined, and counter-measures proposed for each. In addition, the effect of encipherment on file access and update, on paging mechanisms, and on files related to the enciphered index are discussed. Many of the concepts presented here may be readily transferred to other forms of multiway index trees and to binary search trees.