You are looking at a specific version 20200309:130704 of this paper. See the latest version.

Paper 2020/296

Multidimensional Database Reconstruction from Range Query Access Patterns

Akshima and David Cash and Francesca Falzon and Adam Rivkin and Jesse Stern

Abstract

This work considers the security of systems that process encrypted multi-dimensional range queries with only access pattern leakage. Recent work of Kellaris et al. (CCS 2016) showed that in one dimension, an adversary could use the access patterns of several uniformly random range queries to reconstruct a plaintext column of numbers “up to reflection.” We extend this attack to two dimensions and find that the situation is much more complicated: Information theoretically it is complex to describe even what is possible to recover for the adversary in general. We provide a classification of these limits under certain technical conditions. We also give a faster algorithm that works for “dense” databases that contain at least one record for each possible value. Finally we explore the implications for our classification with real data sets.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Searchable encryptionencrypted databasesaccess pattern attacks
Contact author(s)
akshima @ uchicago edu,davidcash @ uchicago edu,ffalzon @ uchicago edu,amrivkin @ uchicago edu,jesseastern @ uchicago edu
History
2020-03-09: received
Short URL
https://ia.cr/2020/296
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.