Abstract Security system designers favor worst-case security measures, such as those derived from differential privacy (DP), due to the strong guarantees they provide. However, these guarantees often result in high penalties on system performance. This paper introduces the Bayes security measure ($\beta^*$), which quantifies the expected advantage over random guessing of an adversary observing a mechanism's output. We demonstrate that $\beta^*$ is prior-independent, can be estimated efficiently in black-box scenarios, and enables designers to find low-risk parameters without sacrificing utility.
Introduction
In security engineering, measuring system safety typically involves a trade-off between two extremes. Average-case metrics, such as accuracy, are highly dependent on the attacker's prior knowledge, often leading to overly optimistic security assessments. Conversely, worst-case metrics like Differential Privacy are prior-independent but can be excessively pessimistic and threat-agnostic. In domains like traffic analysis or side-channel protection, meeting strict DP requirements often destroys system utility. Bayes security serves as a "middle way"—a metric that maintains prior independence while remaining threat-specific and less punishing to performance.
Methodology: Defining Bayes Security
Bayes security ($\beta^*$) is grounded in the concept of multiplicative risk leakage. It is defined as the ratio between the Bayes risk (the minimum error of an optimal attacker) and the random guessing error (the error made without access to data). To ensure robustness, the measure identifies the "least secure" configuration by finding the prior distribution that minimizes this ratio.
A significant theoretical contribution of this work is the Two-Secret Discovery. The authors prove that the minimum Bayes security always occurs when an adversary is tasked with distinguishing between exactly two secrets with a uniform (50/50) prior.
Mathematically, this connects Bayes security to the complement of the Total Variation (TV) distance between the two most distinguishable rows in a system's probability matrix. Furthermore, the authors derive algebraic composition rules, showing how security degrades when systems are combined in parallel or in sequence.
Empirical Evaluation
The framework was validated using synthetic channels and the US Census 1990 dataset, comprising approximately 2.4 million records. The authors applied the Randomized Response mechanism to protect sensitive attributes like age and income. The results showed that for the mechanism to maintain 95% utility, the DP parameter $\epsilon$ had to be 3.3—a level often considered "leaky." However, the Bayes security for this same configuration was 0.99999, demonstrating that the actual risk of identifying a specific record was negligible despite the high $\epsilon$ value.
Key Results and Insights
- Relationship to Differential Privacy: The paper establishes tight bounds relating $\beta^*$ to DP. Specifically, if a system is $\epsilon$-DP, its Bayes security is at least $2 / (1 + \exp(\epsilon))$.
- Interpretability: Unlike the abstract $\epsilon$ parameter, $\beta^*$ has a clear physical meaning, directly bounding the probability of an optimal attacker correctly guessing a secret.
- Black-Box Friendly: Bayes security can be consistently estimated by observing a system's inputs and outputs, avoiding the need for formal mathematical proofs of the underlying algorithms.
Conclusion
Bayes security provides a practical and interpretable alternative to traditional security measures. By focusing on the "worst-case pair" of secrets, it ensures that no specific subgroup of users is significantly more vulnerable than others, while allowing for significantly higher utility than standard DP approaches. Future research will focus on scaling the $O(n^2)$ computational requirement for massive secret spaces and exploring the metric's applications in privacy fairness.
Summary updated