Paper 2020/296

Multidimensional Database Reconstruction from Range Query Access Patterns

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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Searchable encryptionencrypted databasesaccess pattern attacks
Contact author(s)
akshima @ uchicago edu
davidcash @ uchicago edu
ffalzon @ uchicago edu
amrivkin @ uchicago edu
jesseastern @ uchicago edu
2020-03-09: received
Short URL
Creative Commons Attribution


      author = {Akshima and David Cash and Francesca Falzon and Adam Rivkin and Jesse Stern},
      title = {Multidimensional Database Reconstruction from Range Query Access Patterns},
      howpublished = {Cryptology ePrint Archive, Paper 2020/296},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.