Search Key Substitution in the Encipherment of B-Trees.

Thomas Hardjono, Jennifer Seberry: Search Key Substitution in the Encipherment of B-Trees. VLDB 1990: 50-58

@inproceedings{DBLP:conf/vldb/HardjonoS90,
  author    = {Thomas Hardjono and
               Jennifer Seberry},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Search Key Substitution in the Encipherment of B-Trees},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {50-58},
  ee        = {db/conf/vldb/HardjonoS90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper suggests an improvement to the scheme by Bayer and Metzger for the encipherment of B- Trees. Search keys are "disguised" instead of encrypted, and together with the data pointers and tree pointers which remain encrypted, prevents the opponent or attacker from recreating the correct shape of the B-Tree. Combinatorial block designs are used as a method to substitute the search keyscontained within the nodes of the B-Tree. The substitution provides advantages in terms of the number of decryptions necessary to traverse the B- Tree, while the use of block designs are advantageous in terms of the small amount of information that needs to be kept secret. The method is aimed at enhancing the use of encryption for the nodes of the B-Tree, and not as a replacement of the encryption algorithm. Although in this paper it is used in the context of B-Trees, the method may beapplicable to other record storage organizations.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X

References

[1]: Dorothy E. Denning: Field Encryption and Authentication. CRYPTO 1983: 231-247
[2]: ...
[3]: ...
[4]: George I. Davida, David L. Wells, John B. Kam: A Database Encryption System with Subkeys. ACM Trans. Database Syst. 6(2): 312-328(1981)
[5]: Rudolf Bayer, J. K. Metzger: On the Encipherment of Search Trees and Random Access Files. ACM Trans. Database Syst. 1(1): 37-52(1976)
[6]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[7]: Ramez Elmasri, Shamkant B. Navathe: Fundamentals of Database Systems. Benjamin/Cummings 1989
[8]: ...
[9]: ...
[10]: ...
[11]: ...
[12]: Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2): 120-126(1978)
[13]: ...
[14]: ...