File-Injection Attacks on Searchable Encryption, Based on Binomial Structures

One distinguishable feature of file-inject attacks on searchable encryption schemes is the 100% query recovery rate, i.e., confirming the corresponding keyword for each query. The main efficiency consideration of file-injection attacks is the number of injected files. In the work of Zhang et al. (USENIX 2016), \(|\log _2|K||\) injected files are required, each of which contains |K|/2 keywords for the keyword set K. Based on the construction of the uniform (s, n)-set, Wang et al. need fewer injected files when considering the threshold countermeasure. In this work, we propose a new attack that further reduces the number of injected files where Wang et al. need up to 38% more injections to achieve the same results. The attack is based on an increment (s, n)-set, which is also defined in this paper.