Paper 2019/395

Full Database Reconstruction with Access and Search Pattern Leakage

Evangelia Anna Markatou and Roberto Tamassia

Abstract

The widespread use of cloud computing has enabled several database providers to store their data on servers in the cloud and answer queries from those servers. In order to protect the confidentiality of data in the cloud, a database can be stored in encrypted form and all queries can be executed on the encrypted database. Recent research results suggest that a curious cloud provider may be able to decrypt some of the items in the database after seeing a large number of queries and their (encrypted) results. In this paper, we focus on one-dimensional databases that support range queries and develop an attack that can achieve full database reconstruction, inferring the exact value of every element in the database. We consider an encrypted database whose records have values from a given universe of $N$ consecutive integers.Our attack assumes access pattern and search pattern leakage. It succeeds after the attacker has seen each of the possible query results at least once, independent of their distribution. If we assume that the client issues queries uniformly at random, we can decrypt the entire database with high probability after observing $O(N^2 \log N)$ queries.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
Searchable EncryptionEncrypted DatabasesLeakage-Abuse AttacksData Recovery
Contact author(s)
markatou @ brown edu
History
2019-09-18: revised
2019-04-18: received
See all versions
Short URL
https://ia.cr/2019/395
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/395,
      author = {Evangelia Anna Markatou and Roberto Tamassia},
      title = {Full Database Reconstruction with Access and Search Pattern Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2019/395},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/395}},
      url = {https://eprint.iacr.org/2019/395}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.