R. Bayer
Abstract
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 threats to encipherment arising from updating and the file structure itself must be countered. A general encipherment scheme is proposed for files maintained in a paged structure in secondary storage. This is applied to the encipherment of indexes organized as B-trees; a B-tree is a particular type of multiway search tree. Threats to the encipherment of B-trees, especially relating to updating, are examined, and countermeasures are 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 may be readily transferred to other forms of multiway index trees and to binary search trees.
- 1 BAYER, R., MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Informatica 1, 3 (1972), 173-189.Google Scholar
Digital Library
- 2 CARROLL, J.M., .4.ND MCLELLAND, P.M. Fast "infinite key" privacy transformations for resource sharing systems. Proc. AFIPS 1970 FJCC, Vol. 37, AFIPS Press, Montvale, N.J., pp. 223-230.Google Scholar
- 3 FABRY, R.S. Capability-based addressing. Comm. ACM 17, 7 (July 1974), 403-411. Google ScholarDigital Library
- 4 FEISTEL, H. Cryptography and computer privacy. Sci. Amer. 228, 5 (May, 1973), 15-23.Google ScholarCross Ref
- 5 FRIEDMAN, T.D., AND I-IOFFMAN, L.J. Execution time requirements for encipherment programs. Comm. A CM 17, 8 (Aug. 1974), 445-449. Google ScholarDigital Library
- 6 KNUTH, D.E. The Art of Computer Programming, Vol. 3: Sorting ann Searching. Addison- Wesley, Reading, Mass., 1972. Google ScholarDigital Library
- 7 MELLEN, G.E. Cryptology, computers, and common sense. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 569-579.Google Scholar
- 8 SMITH, J.L., NOTZ, W.A., AND OSSECK, P.R. An experimental application of cryptology to a remotely accessed data system. Proc. ACM 27th Nat. Conf., 1972, pp. 282--297. Google ScholarDigital Library
- 9 TURN, R. Privacy transformations for databank systems. Proc. AFIPS 1973 NCC, Vol. 42, AFIPS Press, Montvale, N.J., pp. 589-601.Google Scholar
- 10 WEDEKIND, H. On the relation of access paths in a data base system. In Data Base Management, J.W. Klimbie and K.L. Koffeman, Eds., North-Holland Pub. Co., Amsterdam; 1974, pp. 385-397.Google Scholar
- 11 WILKES, M.V. Time-Sharing Computer Systems. American Elsevier, London, 1971. Google ScholarDigital Library
Index Terms
- On the encipherment of search trees and random access files
Recommendations
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 ...
On the encipherment of search trees and random access files
VLDB '75: Proceedings of the 1st International Conference on Very Large Data BasesThe 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 ...
Dense multiway trees
B-trees of order m are a “balanced” class of m-ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion ...
Comments