Quantifying Security in Volume-Hiding Searchable Symmetric Encryption Schemes With a Novel Scoring Metric

Size pattern leakage remains a critical issue in oblivious RAM (ORAM)-based Searchable Symmetric Encryption (SSE) schemes. Despite efforts to define security notions against size pattern leakage, existing studies either overly restrict analysis by focusing on maximum padding strategies or fail to offer meaningful quantitative comparisons across distinct schemes. In this paper, we introduce a novel scoring metric, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Response Length Obfuscation</i> (RLO), which fundamentally redefines how to assess volume-hiding schemes by measuring the hardness of guessing keywords based on the response lengths of queries. The proposed RLO-scoring utilizes Shannon entropy to measure the inability of guessing keywords for every feasible response length, providing a comprehensive measurement of security. Our main finding is that size pattern leakage should be perceived not merely as a binary categorization of leaked versus not leaked, but rather as a quantifiable continuum. This enables deeper evaluation of the security properties in various SSE schemes. Moreover, we propose how to capture adversarial attempts with size pattern leakage under an adaptive threat model, contrasting with previous work that depends on a selective model. We rigorously demonstrate the general applicability of the RLO-scoring through both theoretical analysis and experimental validation on diverse padding strategies with real-world Enron dataset and Ubuntu dataset corpus.