Hardening Database Padding for Searchable Encryption
- 1 April 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2503-2511
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- An Efficient Non-interactive Multi-client Searchable Encryption with Support for Boolean Queries2016
- Private Large-Scale Databases with Distributed Searchable Symmetric Encryption2016
- Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records2015
- Leakage-Abuse Attacks Against Searchable Encryption2015
- Dynamic Searchable Encryption via Blind Storage2014
- Dynamic searchable symmetric encryption2012
- Searchable symmetric encryption2006
- A mathematical theory of communicationACM SIGMOBILE Mobile Computing and Communications Review, 2001
- LOF2000
- A dual algorithm for the one-machine scheduling problemMathematical Programming, 1976