Bucketization Techniques for Encrypted Databases: Quantifying the Impact of Query Distributions

An ongoing problem in Database As a Service (DAS) is how to increase the efficiency of retrieving encrypted data from remote untrusted servers without compromising security. Bucketization is a privacy preserving technique for executing SQL queries over encrypted data on a DAS server. Bucketization partitions encrypted attributes into queryable tables (buckets), thereby disguising which records are requested. While a number of bucketization techniques are optimized for uniform query access, many Internet and private network access patterns reflect a non-uniform or Zipf-like trend. If query access is non-uniform, existing techniques may be subject to substantial performance degradation. In order to evaluate that possibility, this thesis presents new bucketization technique, Query Sensitive Bucketization (QSB), that capitalizes on the probability distribution of non-uniform queries. Two existing uniform bucketization techniques were implemented to (1) evaluate their performance when the distribution of queries is non-uniform, and (2) evaluate their performance relative to QSB. Among the measures used for performance analysis, a new security metric is presented, which quantifies the risk of an adversary estimating the true value distribution of an encrypted data store. Unlike existing security metrics, the new metric expresses information disclosed by the pattern of query access over an encrypted bucket set. Results showed that QSB improves query efficiency over uniform techniques, while maintaining a high level of data security. QSB is not only an efficient example of query-based bucketization for DAS, but a conceptual model for future research, in which data are organized to accommodate a variety of query access patterns, thereby improving query efficiency and database security.

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Bowling Green State University

Year dc:date

2013

Author dc:creator

• Raybourn, Tracey

Contributors dc:contributor

• Kresman, Ray

• Computer Science
• Database security
• Query Distributions
• Database Bucketization
• Data Privacy

Statement dc:rights

• unrestricted
• This thesis or dissertation is protected by copyright: all rights reserved. It may not be copied or redistributed beyond the terms of applicable copyright laws.

Language dc:language

English

Repository record dc:identifier

http://rave.ohiolink.edu/etdc/view?acc_num=bgsu1363638271

OAI identifier oai:identifier

oai:etd.ohiolink.edu:bgsu1363638271