Slide 1What this paper is aboutDAS and its implicationsPrevious SolutionsBefore we proceedExampleUniform Query DistributionAlgorithm BasicsAlgorithmVariance, ASEE and EntropyControlled Diffusion(CDf)ExperimentsResultsCritiqueSlide 15A Privacy – Preserving Index for Range queriesPaper By: Bijit Hore, Sharad Mehrotra, Gene TsudikPresented By: Akshay PhadkeWhat this paper is about Database as a Service (DAS) Improving the existing Bucketization Technique Identification of privacy measures in DAS. Development of a novel privacy-preserving re-bucketization technique.DAS and its implicationsDatabase-as-a-service in which organizations outsource data management to a service provider.Privacy because the data is stored at service provider.One possible solution: Q = Qsec + QunsecPrevious SolutionsBucketization for ranged queries Attribute domain is partitioned into a set indentified by a set.Deterministic encryption for join queries.Drawbacks: Lacks in-depth privacy scenarios.Privacy is subjective: no clear specification.Before we proceedEtuple: tuple stored in encrypted form. crypto-indices: indices created on sensitive attributes.Bucket_id: Set created is assigned a unique random tag.ExampleAllocating a large number of buckets to crypto-indices increases query precision but reducesprivacy. On the other hand, a small number of buckets increases privacy but adversely aects performance.Uniform Query DistributionTotal False Positives:Average Query Precision:Goal: Minimize the total number of false positives.Algorithm BasicsNumber of false positives depends on the the width of the bucket (i.e. minimum and the maximum values) and the sum of the frequencies. To solve the problem use Optimal Substructure property: Splitting the problems into two smaller sub problems.AlgorithmVariance, ASEE and EntropyMaximize Var(x)Controlled Diffusion(CDf)QoS is the maximum allowed performance degradation factor (K).CDf algorithm increases privacy of buckets.Diffusion carried out in a controlled manner. Elements diffused into composite buckets. d = K..|Bi| / fCBComposite buckets overlap whereas in case of optimal buckets, they don’t.Experiments Data Set - Synthetic Data Set - Real Data Set - Benchmark Query SetMeasurements - Decrease in Precision - Privacy Measure - Performance-Privacy Trade Off - Time takenResultsObserved decrease in query precision was less than 3For privacy measure: standard deviation increases by a large factor. Entropy grows more slowly.CritiqueAlthough starts promising, the paper becomes a mathematics paper and seems to loose focus of actual intent.Examples mentioned just have the first step and the final solution, no intermediate steps.The paper doesn’t explain the results.Thank
View Full Document
Unlocking...