A Privacy Model for Searchable Symmetric Encryption
TL;DR
A privacy model for searchable symmetric encryption protocols that makes adversarial power a central parameter and induces four privacy levels giving rise to a privacy lattice is proposed, enabling reasoning about how privacy guarantees change under different adversarial capabilities.
Abstract
: Searchable symmetric encryption enables efficient keyword search over encrypted outsourced data, making it a key primitive for cloud storage. Since searchable symmetric encryption protocols inevitably leak side information through repeated searches, access patterns, update behaviour, and timing, an analysis of their privacy properties is crucial. Prior work along this direction considers leakage functions capturing what is revealed, and privacy guarantees often remain difficult to compare across schemes. We propose a privacy model for searchable symmetric encryption protocols that makes adversarial power a central parameter. We formalise adversaries capabilities and organise them into four classes based on two orthogonal dimensions, observational power (low vs. high) and privacy guarantee strength (minimal vs. strong). These classes induce four privacy levels giving rise to a privacy lattice, capturing implication relations between guarantees under increasingly powerful adversaries. This enables reasoning about how privacy guarantees change under different adversarial capabilities. We validate the privacy model by showing that representative symmetric encryption protocols schemes from the literature naturally instantiate the proposed privacy classes.