Hardening Database Padding for Searchable Encryption

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.