Exploiting Update Leakage in Searchable Symmetric Encryption

Dynamic Searchable Symmetric Encryption (DSSE) provides efficient techniques for securely searching and updating an encrypted database. However, efficient DSSE schemes leak some sensitive information to the server. Recent works have implemented forward and backward privacy as security properties to reduce the amount of information leaked during update operations. Many attacks have shown that leakage from search operations can be abused to compromise the privacy of client queries. However, the attack literature has not rigorously investigated techniques to abuse update leakage. In this work, we investigate update leakage under DSSE schemes with forward and backward privacy from the perspective of a passive adversary. We propose two attacks based on a maximum likelihood estimation approach, the UFID Attack and the UF Attack, which target forward-private DSSE schemes with no backward privacy and Level 2 backward privacy, respectively. These are the first attacks to show that it is possible to leverage the frequency and contents of updates to recover client queries. We propose a variant of each attack which allows the update leakage to be combined with search pattern leakage to achieve higher accuracy. We evaluate our attacks against a real-world dataset and show that using update leakage can improve the accuracy of attacks against DSSE schemes, especially those without backward privacy.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science and Applications

Department dc:contributor.department

Computer Science and Applications

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2024

Author dc:creator

• Haltiwanger, Jacob Sayid

Chair dc:contributor.committeechair

• Hoang, Thang

Committee members dc:contributor.committeemember

• Hicks, Matthew
• Williams, Daniel John

• Searchable Encryption
• Inference Analysis
• Database Privacy

Statement dc:rights

• Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International

Licence dc:rights.uri

• http://creativecommons.org/licenses/by-nc-sa/4.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:39532

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/118419