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 the data stored in the cloud, a database can be stored in an encrypted form and all queries can be executed on top of 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. Previous work on full database reconstruction depends on a client issuing queries uniformly at random. Let $N$ be the number of elements in the database. Our attack succeeds after the attacker has seen each of the possible query results at least once, independent of their distribution. For the sake of query complexity analysis and comparison with relevant work, if we assume that the client issues queries uniformly at random, we can decrypt the entire database after observing $O(N^2 \log N)$ queries with high probability, an improvement upon Kellaris et al.'s $O(N^4 \log N)$.
Metadata
- Available format(s)
- 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
-
CC BY