Performance-optimized Indexes for Inequality Searches on Encrypted Data in Practice

Jan Lehnhardt, Tobias Rho, Adrian Spalka, Armin B. Cremers

2015

Abstract

For information systems in which the server must operate on encrypted data (which may be necessary because the service provider cannot be trusted) solutions need to be found that enable fast searches on that data. In this paper we present an approach for encrypted database indexes that enable fast inequality, i.e., range searches, such that also prefix searches on lexicographically ordered but encrypted data are possible. Unlike common techniques that address this issue as well, like hardware-based solutions or order-preserving encryption schemes, our indexes do not require specialized, expensive hardware and use only well-accredited software components; they also do not reveal any information about the encrypted data besides their order. Moreover, when implementing the indexing approach in a commercial software product, multiple application-centric optimization opportunities of the index’s performance did emerge, which are also presented in this paper. They include basic performance-increasing measures, pipelined index scans and updates and caching strategies. We further present performance test results proving that our indexing approach shows good performance on substantial amounts of data.

Paper Citation

in Harvard Style

Lehnhardt J., Rho T., Spalka A. and Cremers A. (2015). Performance-optimized Indexes for Inequality Searches on Encrypted Data in Practice . In Proceedings of the 1st International Conference on Information Systems Security and Privacy - Volume 1: ICISSP, ISBN 978-989-758-081-9, pages 221-229. DOI: 10.5220/0005231702210229

in Bibtex Style

@conference{icissp15,
author={Jan Lehnhardt and Tobias Rho and Adrian Spalka and Armin B. Cremers},
title={Performance-optimized Indexes for Inequality Searches on Encrypted Data in Practice},
booktitle={Proceedings of the 1st International Conference on Information Systems Security and Privacy - Volume 1: ICISSP,},
year={2015},
pages={221-229},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005231702210229},
isbn={978-989-758-081-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 1st International Conference on Information Systems Security and Privacy - Volume 1: ICISSP,
TI - Performance-optimized Indexes for Inequality Searches on Encrypted Data in Practice
SN - 978-989-758-081-9
AU - Lehnhardt J.
AU - Rho T.
AU - Spalka A.
AU - Cremers A.
PY - 2015
SP - 221
EP - 229
DO - 10.5220/0005231702210229