Skip to content

Encrypted Databases: New Volume Attacks against Range Queries

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publicationCCS'19
Subtitle of host publicationProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
Publisher or commissioning bodyAssociation for Computing Machinery (ACM)
Pages361-378
Number of pages47
ISBN (Print)978-1-4503-6747-9
DOIs
DateAccepted/In press - 16 Sep 2019
DatePublished (current) - 6 Nov 2019
EventACM CCS 2019: 26th ACM Conference on Computer and Communications Security - London, United Kingdom
Duration: 11 Nov 201915 Nov 2019
https://www.sigsac.org/ccs/CCS2019/

Conference

ConferenceACM CCS 2019
CountryUnited Kingdom
CityLondon
Period11/11/1915/11/19
Internet address

Abstract

We present a range of novel attacks which exploit information about the volume of answers to range queries in encrypted database. Our attacks rely on a strategy which is simple yet robust and effective. We illustrate the robustness of our strategy in a number of ways. We show how i) to adapt the attack for several variations of a basic usage scenario ii) to defeat countermeasures intended to thwart the premise of our basic attack and iii) to perform partial reconstruction of secret data when unique reconstruction is information theoretically impossible. Furthermore, over the state of the art, our attacks require one order of magnitude fewer queries. We show how to improve the attacks even further, under the assumption that some partial information is known to the adversary. We validate experimentally all of our attacks through extensive experiments on real-world medical data and justify theoretically the effectiveness of our strategy for the basic attack scenario. Our new attacks further underscore the difficulty of striking an appropriate functionality-security trade-off for encrypted databases.

    Research areas

  • Encrypted databases, Volume leakage attacks

Event

ACM CCS 2019: 26th ACM Conference on Computer and Communications Security

Duration11 Nov 201915 Nov 2019
CityLondon
CountryUnited Kingdom
Web address (URL)
Degree of recognitionInternational event

Event: Conference

Download statistics

No data available

Documents

Documents

  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via ACM at https://dl.acm.org/citation.cfm?doid=3319535.3363210. Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 457 KB, PDF document

DOI

View research connections

Related faculties, schools or groups