Peijie Li (Delft University of Technology), Huanhuan Chen (Delft University of Technology), Kaitai Liang (University of Turku and Delft University of Technology), Evangelia Anna Markatou (Delft University of Technology)

Searchable Encryption (SE) has shown a lot of promise towards enabling secure and efficient queries over encrypted data. In order to achieve this efficiency, SE inevitably leaks some information, and a big open question is how dangerous this leakage is. While prior reconstruction attacks have demonstrated effectiveness in one-dimensional range query settings, extending them to high-dimensional datasets remains challenging. Existing methods either demand excessive query information (e.g., an attacker that has observed all possible responses) or produce low-quality reconstructions in sparse databases. In this work, we present REMIN, a new leakage-abuse attack against SE schemes in multi-dimensional settings, exploiting access and search pattern leakage from range queries. REMIN leverages unsupervised representation learning to transform query co-occurrence frequencies into geometric signals, enabling an attacker to infer relative spatial relationships among encrypted records. This approach allows accurate and scalable reconstruction of high-dimensional datasets under minimal leakage. Furthermore, we introduce REMIN-P, an active variant of the attack that incorporates a practical poisoning strategy. By injecting a small number of auxiliary anchor points, REMIN-P significantly improves reconstruction quality, particularly in sparse or boundary regions of the data space. We evaluate our attacks extensively on both synthetic and real-world datasets. Compared to state-of-the-art reconstruction attacks, our reconstruction attack achieves up to 50% reduction in mean squared error (MSE), all while maintaining fast and scalable runtime. Our poisoning attack can further reduce MSE by an additional 50% on average, depending on the poisoning strategy.

View More Papers

PAIEL: Protocol-Aware and Context-Integrated Protocol Explanation Using LLMs for...

Takeshi Kaneko (Panasonic Holdings Corporation), Hiroyuki Okada (Panasonic Holdings Corporation), Rashi Sharma (Panasonic R&D Center Singapore), Tatsumi Oba (Panasonic Holdings Corporation), Naoto Yanai (Panasonic Holdings Corporation)

Read More

Robust Fraud Transaction Detection: A Two-Player Game Approach

Qi Tan (College of Computer Science and Software Engineering, Shenzhen University), Yi Zhao (School of Cyberspace Science and Technology, Beijing Institute of Technology), Laizhong Cui (College of Computer Science and Software Engineering, Shenzhen University), Qi Li (Institute for Network Science and Cyberspace, Tsinghua University), Ming Zhu (Department of Computer Science and Technology, Tsinghua University), Xing…

Read More

RoundRole: Unlocking the Efficiency of Multi-party Computation with Bandwidth-aware...

Xiaoyu Fan (Tsinghua University and Shanghai Qi Zhi Institute), Kun Chen (Ant Group), Jiping Yu (Tsinghua University), Xin Liu (Tsinghua University), Yunyi Chen (Tsinghua University), Wei Xu (Tsinghua University and Shanghai Qi Zhi Institute)

Read More