  Secure collaborative analytics (SCA) enable the processing of analytical SQL
queries across multiple owners' data, even when direct data sharing is not
feasible. Although essential for strong privacy, the large overhead from
data-oblivious primitives in traditional SCA has hindered its practical
adoption. Recent SCA variants that permit controlled leakages under
differential privacy (DP) show a better balance between privacy and efficiency.
However, they still face significant challenges, such as potentially unbounded
privacy loss, suboptimal query planning, and lossy processing. To address these
challenges, we introduce SPECIAL, the first SCA system that simultaneously
ensures bounded privacy loss, advanced query planning, and lossless processing.
SPECIAL employs a novel synopsis-assisted secure processing model, where a
one-time privacy cost is spent to acquire private synopses (table statistics)
from owner data. These synopses then allow SPECIAL to estimate (compaction)
sizes for secure operations (e.g., filter, join) and index encrypted data
without extra privacy loss. Crucially, these estimates and indexes can be
prepared before runtime, thereby facilitating efficient query planning and
accurate cost estimations. Moreover, by using one-sided noise mechanisms and
private upper bound techniques, SPECIAL ensures strict lossless processing for
complex queries (e.g., multi-join). Through a comprehensive benchmark, we show
that SPECIAL significantly outperforms cutting-edge SCAs, with up to 80X faster
query times and over 900X smaller memory for complex queries. Moreover, it also
achieves up to an 89X reduction in privacy loss under continual processing.
