Skip to content

Encrypted Databases: New Volume Attacks against Range Queries

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

Standard

Encrypted Databases : New Volume Attacks against Range Queries. / Gui, Zichen; Johnson, Oliver T; Warinschi, Bogdan.

CCS'19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery (ACM), 2019. p. 361-378.

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

Harvard

Gui, Z, Johnson, OT & Warinschi, B 2019, Encrypted Databases: New Volume Attacks against Range Queries. in CCS'19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery (ACM), pp. 361-378, ACM CCS 2019, London, United Kingdom, 11/11/19. https://doi.org/10.1145/3319535.3363210

APA

Gui, Z., Johnson, O. T., & Warinschi, B. (2019). Encrypted Databases: New Volume Attacks against Range Queries. In CCS'19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (pp. 361-378). Association for Computing Machinery (ACM). https://doi.org/10.1145/3319535.3363210

Vancouver

Gui Z, Johnson OT, Warinschi B. Encrypted Databases: New Volume Attacks against Range Queries. In CCS'19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery (ACM). 2019. p. 361-378 https://doi.org/10.1145/3319535.3363210

Author

Gui, Zichen ; Johnson, Oliver T ; Warinschi, Bogdan. / Encrypted Databases : New Volume Attacks against Range Queries. CCS'19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery (ACM), 2019. pp. 361-378

Bibtex

@inproceedings{9bed718841a44a4fb46dae67ce0ee140,
title = "Encrypted Databases: New Volume Attacks against Range Queries",
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.",
keywords = "Encrypted databases, Volume leakage attacks",
author = "Zichen Gui and Johnson, {Oliver T} and Bogdan Warinschi",
year = "2019",
month = "11",
day = "6",
doi = "10.1145/3319535.3363210",
language = "English",
isbn = "978-1-4503-6747-9",
pages = "361--378",
booktitle = "CCS'19",
publisher = "Association for Computing Machinery (ACM)",
address = "United States",

}

RIS - suitable for import to EndNote

TY - GEN

T1 - Encrypted Databases

T2 - New Volume Attacks against Range Queries

AU - Gui, Zichen

AU - Johnson, Oliver T

AU - Warinschi, Bogdan

PY - 2019/11/6

Y1 - 2019/11/6

N2 - 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.

AB - 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.

KW - Encrypted databases

KW - Volume leakage attacks

U2 - 10.1145/3319535.3363210

DO - 10.1145/3319535.3363210

M3 - Conference contribution

SN - 978-1-4503-6747-9

SP - 361

EP - 378

BT - CCS'19

PB - Association for Computing Machinery (ACM)

ER -