  Cloud data storage solutions offer customers cost-effective and reduced data
management. While attractive, data security issues remain to be a core concern.
Traditional encryption protects stored documents, but hinders simple
functionalities such as keyword search. Therefore, searchable encryption
schemes have been proposed to allow for the search on encrypted data. Efficient
schemes leak at least the access pattern (the accessed documents per keyword
search), which is known to be exploitable in query recovery attacks assuming
the attacker has a significant amount of background knowledge on the stored
documents. Existing attacks can only achieve decent results with strong
adversary models (e.g. at least 20% of previously known documents or require
additional knowledge such as on query frequencies) and they give no metric to
evaluate the certainty of recovered queries. This hampers their practical
utility and questions their relevance in the real-world.
  We propose a refined score attack which achieves query recovery rates of
around 85% without requiring exact background knowledge on stored documents; a
distributionally similar, but otherwise different (i.e., non-indexed), dataset
suffices. The attack starts with very few known queries (around 10 known
queries in our experiments over different datasets of varying size) and then
iteratively recovers further queries with confidence scores by adding
previously recovered queries that had high confidence scores to the set of
known queries. Additional to high recovery rates, our approach yields
interpretable results in terms of confidence scores.
