Publication
Reflex: Speeding Up SMPC Query Execution through Efficient and Flexible Intermediate Result Size Trimming
Van Long Nguyen; Shaza Zeitouni; Carsten Binnig; Zsolt István
In: Computing Research Repository eprint Journal (CoRR), Vol. abs/2503.20932, Pages 1-15, arXiv, 2025.
Abstract
Secure Multi-Party Computation (MPC) enables collabora-
tive analytics without exposing private data. However, OLAP
queries under MPC remain prohibitively slow due to oblivi-
ous execution and padding of intermediate results with filler
tuples. We present Reflex, the first framework that enables
configurable trimming of intermediate results across different
query operators—joins, selections, and aggregations—within
full query plans. At its core is the Resizer operator, which can
be inserted between any oblivious operators to selectively
remove filler tuples under MPC using user-defined probabilis-
tic strategies. To make privacy trade-offs interpretable, we
introduce a new metric that quantifies the number of obser-
vations an attacker would need to infer the true intermediate
result sizes. Reflex thus makes the performance–privacy
space of secure analytics navigable, allowing users to bal-
ance efficiency and protection. Experiments show substantial
runtime reductions while maintaining quantifiable privacy
guarantees.