Hardening database padding for searchable encryption

Lei Xu, Xingliang Yuan, Cong Wang, Qian Wang, Chungen Xu

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (Scopus)


Searchable encryption (SE) is a practical crypto-graphic primitive to build encrypted databases. Recently there has been much attention in leakage-abuse attacks against SE. Among others, attacks based on inference of keyword frequency can easily identify query keywords from the access pattern, i.e., query results. To mitigate these attacks, database padding is considered as a conceptually simple yet effective counter-measure. Unfortunately, none of the existing studies formally understand the relationship between padding security strength and its overhead. Also, how to craft padding is not restricted in current countermeasures, where bogus files are likely to be distinguishable from real ones. In this paper, we propose an information theory based framework to analyse the security strength under certain padding overhead. First, we leverage relative entropy to measure the 'closeness' between the distributions of the original dataset and padded dataset. Second, we quantity the attack efforts against padding countermeasures by entropy analysis. Apart from theoretical findings, we further devise an algorithm via outlier detection for padding generation, which considers both the padded dataset distribution and the similarity between real and bogus files. Evaluations on a real-world dataset confirm our theoretical results and demonstrate the efficiency and effectiveness of our proposed padding generation algorithm.

Original languageEnglish
Title of host publicationIEEE INFOCOM 2019 - IEEE Conference on Computer Communications
EditorsWenjing Lou, Giovanni Pau, Tilman Wolf
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages9
ISBN (Electronic)9781728105154
ISBN (Print)9781728105161
Publication statusPublished - 2019
EventIEEE Conference on Computer Communications 2019 - Paris, France
Duration: 29 Apr 20192 May 2019
Conference number: 38th


ConferenceIEEE Conference on Computer Communications 2019
Abbreviated titleIEEE INFOCOM 2019
Internet address

Cite this