The Bayes Security Measure

Konstantinos Chatzikokolakis, Giovanni Cherubin, Catuscia Palamidessi, Carmela TroncosoarXiv 2020 · arXiv · OpenReview

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.

Comparison of security games for Bayes security and Local Differential Privacy.

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.
The relationship between Bayes security (beta) and the DP parameter epsilon.

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

Abstract

Security system designers favor worst-case security measures, such as those derived from differential privacy, due to the strong guarantees they provide. These guarantees, on the downside, result on high penalties on the system's performance. In this paper, we study the Bayes security measure. This measure quantifies the expected advantage over random guessing of an adversary that observes the output of a mechanism. We show that the minimizer of this measure, which indicates its security lower bound, i) is independent from the prior on the secrets, ii) can be estimated efficiently in black-box scenarios, and iii) it enables system designers to find low-risk security parameters without hurting utility. We provide a thorough comparison with respect to well-known measures, identifying the scenarios where our measure is advantageous for designers, which we illustrate empirically on relevant security and privacy problems.
BibTeX
@misc{chatzikokolakis2020bayes,
  author = {Konstantinos Chatzikokolakis and Giovanni Cherubin and Catuscia Palamidessi and Carmela Troncoso},
  title = {{The Bayes Security Measure}},
  year = {2020},
  eprint = {2011.03396},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2011.03396},
}
Figure