A Privacy-Preserving Index for Range QueriesBackgroundDatabase as a ServiceProblemSolutionEncryption and BucketizationTradeoffOptimizing Buckets for PerformanceBreaking BucketizationProtecting Against AttacksVariance and EntropyCompromiseDiffusionPrecision ResultsVariance ResultsEntropy ResultsPrivacy vs. PerformanceConclusionBijit Hore, Sharad Mehrotra, Gene TsudikKeiichi ShimamuraRise in use of cloud servicesOutsourcing of IT infrastructureIncreasing use of Database As a Service (DAS)Data is stored at service providerService provider cannot be trustedSecurity perimeter around data ownerClient is secure and trustedServer (service provider) is not trustedHow to maintain security and privacy using DAS?How to estimate and analyze the effectiveness of the solution?Split the query into two partsInsecure query that runs on the serverSecure query that runs on the clientBucketization for range queriesLarger buckets → more privacySmaller buckets → more performanceWant: maximum privacy and performanceReality: tradeoff between privacy and performanceWith knowledge ofBucketization schemeProbability distribution in each bucketthe attacker can form statistical estimates of the values of attributes used in bucketizationIncrease variance of values in a bucketMore different values in each bucket weakens statistical estimatesIncreasing variance of one bucket lowers the variance of othersAdd entropy More values in each bucket weakens statistical estimatesMore rows are returned per bucket, decreasing performanceMaximize variance and entropy for most privacySpecify a maximum performance degradationRedistribute elements from “optimized buckets” to “composite buckets”Tradeoff between privacy and performanceProvides a solution for range queries thatMaximizes privacyLimits performance
View Full Document
Unlocking...