Cryptology ePrint Archive: Report 2017/024

Inference and Record-Injection Attacks on Searchable Encrypted Relational Databases

Mohamed Ahmed Abdelraheem and Tobias Andersson and Christian Gehrmann

Abstract: We point out the risks of providing security to relational databases via searchable encryption schemes by mounting a novel inference attack exploiting the structure of relational databases together with the leakage of searchable encryption schemes. We discuss some techniques to reduce the effectiveness of inference attacks against searchable encryption schemes. Moreover, we show that record-injection attacks mounted on relational databases have worse consequences than their file-injection counterparts on unstructured databases which have been recently proposed at USENIX 2016.

Category / Keywords: searchable symmetric encryption, inference attacks, complexity theory, subset sum problem, independent set problem, relational databases, privacy constraints, vertical fragmentation

Date: received 10 Jan 2017, last revised 12 Mar 2017

Contact author: moh ahm abdelraheem at gmail com

Available format(s): PDF | BibTeX Citation

Note: Modified the introduction and corrected some mistakes in the description of attacks.

Version: 20170312:191827 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]