{"ID":2898154,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.04077","arxiv_id":"2507.04077","title":"S-Leak: Leakage-Abuse Attack Against Efficient Conjunctive SSE via s-term Leakage","abstract":"Conjunctive Searchable Symmetric Encryption (CSSE) enables secure conjunctive searches over encrypted data. While leakage-abuse attacks (LAAs) against single-keyword SSE have been extensively studied, their extension to conjunctive queries faces a critical challenge: the combinatorial explosion of candidate keyword combinations, leading to enormous time and space overhead for attacks. In this paper, we reveal a fundamental vulnerability in state-of-the-art CSSE schemes: s-term leakage, where the keyword with the minimal document frequency in a query leaks distinct patterns. We propose S-Leak, the first passive attack framework that progressively recovers conjunctive queries by exploiting s-term leakage and global leakage. Our key innovation lies in a three-stage approach: identifying the s-term of queries, pruning low-probability keyword conjunctions, and reconstructing full queries. We propose novel metrics to better assess attacks in conjunctive query scenarios. Empirical evaluations on real-world datasets demonstrate that our attack is effective in diverse CSSE configurations. When considering 161,700 conjunctive keyword queries, our attack achieves a 95.15% accuracy in recovering at least one keyword, 82.57% for at least two, 58% for all three keywords, and maintains efficacy against defenses such as SEAL padding and CLRZ obfuscation. Our work exposes the underestimated risks of s-term leakage in practical SSE deployments and calls for a redesign of leakage models for multi-keyword search scenarios.","short_abstract":"Conjunctive Searchable Symmetric Encryption (CSSE) enables secure conjunctive searches over encrypted data. While leakage-abuse attacks (LAAs) against single-keyword SSE have been extensively studied, their extension to conjunctive queries faces a critical challenge: the combinatorial explosion of candidate keyword com...","url_abs":"https://arxiv.org/abs/2507.04077","url_pdf":"https://arxiv.org/pdf/2507.04077v1","authors":"[\"Yue Su\",\"Meng Shen\",\"Cong Zuo\",\"Yuzhi Liu\",\"Liehuang Zhu\"]","published":"2025-07-05T15:53:31Z","proceeding":"cs.CR","tasks":"[\"cs.CR\"]","methods":"[]","has_code":false}