Cryptology ePrint Archive: Report 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.

Category / Keywords: applications / Searchable encryption, encrypted databases, access pattern attacks

Date: received 6 Mar 2020

Contact author: akshima at uchicago edu, davidcash at uchicago edu, ffalzon at uchicago edu, amrivkin at uchicago edu, jesseastern at uchicago edu

Available format(s): PDF | BibTeX Citation

Version: 20200309:130704 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]