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)
- 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
-
CC BY