Violin: Powerful Volumetric Injection Attack Against Searchable Encryption With Optimal Injection Size

Symmetric Searchable Encryption (SSE) enables querying over encrypted data stored on servers, protecting the privacy of both client queries and the data. However, the response results of the query can leak certain statistical information, allowing an active attacker to inject files and exploit these leakages to recover the queried keyword. Recently, Zhang et al. (USENIX Security 2023) proposed a volumetric injection attack, called BVMA, based on response volume patterns. This attack requires larger file injections and has a moderate recovery rate. In this work, we propose a powerful volumetric injection attack, <inline-formula><tex-math notation="LaTeX">$\mathsf {Violin}$</tex-math></inline-formula>, that utilizes response length and size patterns, achieving a higher recovery rate and smaller injection size. Specifically, <inline-formula><tex-math notation="LaTeX">$\mathsf {Violin}$</tex-math></inline-formula> requires <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(\log n)$</tex-math></inline-formula> injection files with a total size of <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(n\log n)$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> is the number of keywords. Furthermore, we propose a file injection method with optimal injection amount (i.e., injected files number and size) based on Pascal’s triangle rule under threshold countermeasure. We implement <inline-formula><tex-math notation="LaTeX">$\mathsf {Violin}$</tex-math></inline-formula> and compare it with the existing injection attacks. Experimental results indicate that <inline-formula><tex-math notation="LaTeX">$\mathsf {Violin}$</tex-math></inline-formula> achieves a recovery rate approaching 100%, surpassing the state-of-the-art BVMA while requiring smaller file sizes. Under threshold countermeasure, <inline-formula><tex-math notation="LaTeX">$\mathsf {Violin}$</tex-math></inline-formula> achieves a saving of 22% in injection file size and a remarkable 95% decrease in injected file number compared to BVMA.